Metody porównywania algorytmów szeregowania

Do porównywania różnych algorytmów szeregowania zaproponowano wiele kryteriów. Wybór odpowiedniego miernika wydajności zależy od przewidywanego zastosowania systemu. Inne kryteria będą brane pod uwagę wtedy, gdy system pełni rolę stacji roboczej dla pojedynczego użytkownika, inne gdy system jest dużym serwerem obsługującym wielu użytkowników i wiele programów interakcyjnych, jeszcze inne gdy system służy do celów obliczeniowych. Wśród stosowanych kryteriów wymienić można następujące:

• Wykorzystanie procesora

Jeśli w systemie są procesy gotowe do wykonania, to powinny być wykonywane. Dąży się do zmaksymalizowania współczynnika wykorzystania procesora. Najczęściej nie jest możliwe uzyskanie 100% wykorzystania procesora, ale system powinien szybko obsługiwać procesy, które przetrzymują jakieś zasoby, aby umożliwić innym procesom użycie tych zasobów. Przyjmuje się, że współczynnik powyżej 90% oznacza bardzo dobre wykorzystanie czasu procesora.
• Przepustowość

Jest to liczba, która określa liczbę procesów kończonych w jednostce czasu. Współczynnik ten ma sens w odniesieniu do konkretnego programu lub ewentualnie -- grupy programów podobnego typu.
• Czas wykonania

Liczba ta jest odwrotnością poprzednio wymienionej. Jest to czas cyklu przetwarzania procesu, tj. czas upływający od chwili powołania nowego procesu do chwili jego usunięcia z systemu. Czas ten jest sumą czasów spędzonych przez proces na procesorze, w kolejce procesów gotowych oraz w stanie uśpienia.^2.3
• Czas oczekiwania

Proces po obudzeniu albo wywłaszcza bieżący proces, albo trafia do kolejki procesów gotowych. Czas spędzony przez proces w kolejce procesów gotowych nazywany jest czasem oczekiwania. Na tę wielkość algorytm szeregowania ma bezpośredni wpływ, gdyż to właśnie planista podejmuje decyzję, któremu z procesów gotowych przydzielić procesor.
• Czas odpowiedzi

Proces, który zasnął w oczekiwaniu na zdarzenie (np. wykonanie operacji wejścia-wyjścia), budzi się, wykonuje pewne czynności w trybie jądra i wraca do trybu użytkownika. Czas pomiędzy zajściem zdarzenia a powrotem procesu do trybu użytkownika (co wiąże się np. z rozpoczęciem prezentowania danych) nazywa się czasem odpowiedzi.

Porównanie czasu odpowiedzi i czasu oczekiwania przedstawia rys. 1.1 (HTML: niedostępny). Zob. też [5], str. 128.
 

Porównując każdy z parametrów dla różnych algorytmów szeregowania, można brać pod uwagę różne wartości z nim związane:

• Wartość średnia

Zwykle rozpatruje się wartości średnie. Porównuje się np. średni czas odpowiedzi, średni czas obrotu, średnie wykorzystanie procesora.
• Wartość ekstremalna

Porównuje się np. maksymalne czasy odpowiedzi, jeśli chcemy zapewnić użytkownikom odpowiedni komfort pracy, lub minimalną przepustowość dla procesów wsadowych.
• Wariancja wartości

Dąży się do jej minimalizacji. Argumentem przemawiającym za rozpatrywaniem miernika wydajności pod tym kątem może być np. żądanie, aby system niekoniecznie był bardzo szybki, ale za to przewidywalny. Użytkownicy uruchamiający procesy wsadowe wolą mieć pewność, że ich program skończy obliczenia z dużym prawdopodobieństwem np. w ciągu godziny, niż sytuację, gdy program raz wykonuje się 20 minut, a innym razem kilka godzin.

W [1] opisano trzy podstawowe metody porównywania algorytmów szeregowania:

• Ocena analityczna

Metoda ta polega na stworzeniu modelu matematycznego dla danego algorytmu i obciążenia roboczego systemu. Obciążenie robocze systemu uzyskuje się albo z danych pobranych z rzeczywistych systemów, albo przyjmując pewne schematy zachowania się programów, np. programy zorientowane na wejście-wyjście to takie, które zużywają z dużym prawdopodobieństwem krótkie kwanty czasu procesora a następnie zasypiają w oczekiwaniu na zdarzenie, które nadchodzi z pewną częstotliwością (np. interakcja użytkownika z programem).

Ocena analityczna pozwala na przybliżoną ocenę algorytmów szeregowania w wyidealizowanym systemie. Dzięki tej metodzie można wstępnie porównać mierniki wydajności badanych algorytmów.

• Symulacja

Metoda jest bardzo podobna do poprzedniej. Należy przyjąć jakiś model zachowania programu -- sztuczny lub na podstawie śladu wykonania programu w rzeczywistym systemie. Ocena algorytmów polega na ich zaprogramowaniu i symulacji badanego systemu. Dokładność tej metody zależy w dużej mierze od stopnia złożoności symulacji. Metoda ta daje możliwość uzyskania statystycznych danych do dalszej obróbki. Umożliwia także badanie tych mierników wydajności, dla których metoda analityczna jest zbyt skomplikowana.

Symulację stosuje się także czasami zamiast metody wymienionej niżej w sytuacji, gdy w rzeczywistym systemie nie można w czasie rzeczywistym wykonać potrzebnych obliczeń.

• Implementacja

Metoda polega na zaimplementowaniu algorytmu, który chcemy przebadać w rzeczywistym systemie operacyjnym. Jeszcze do niedawna zadanie to było albo trudne, albo wręcz niewykonalne z powodu niedostępności kodu źródłowego. Niektóre systemy (jak np. SVR4) umożliwiały dopisywanie własnych algorytmów szeregowania i w ten sposób, bez modyfikacji kodu źródłowego samego systemu, pełnowartościową symulację -- badanie w warunkach rzeczywistych.

Powstały także systemy "`akademickie'', niezoptymalizowane, ale posiadające wszystkie cechy systemu operacyjnego i zdolne do wykonywania aplikacji. Najsłynniejszym był Minix, z którego powstał Linux.

1999-05-21