Przegląd algorytmów szeregowania

Poniżej zostaną omówione algorytmy szeregowania dla klasy procesów zwykłych (współdzielących czas procesora, ang. time-sharing processes), czyli, zgodnie z nomenklaturą systemów uniksowych, należących do klasy SCHED_OTHER. Tam, gdzie będzie to niezbędne, omówione zostaną także algorytmy dla pozostałych klas procesów.

Algorytm szeregowania powinien zapewniać każdemu procesowi dostęp do procesora w skończonym czasie (żywotność). Powinien także zapewniać sensowny czas reakcji procesom zorientowanym na wejście-wyjście, jak np. edytory tekstu czy serwery WWW. Algorytm powinien być na tyle elastyczny, aby efektywnie wykorzystywał czas procesora zarówno w systemie nieobciążonym, jak i obciążonym.

Do opisu algorytmów zostanie użyty pseudokod. Przyjęto następujące oznaczenia:

• Procesy są reprezentowane przez swoje bloki kontrolne. Blok kontrolny ma typ Process.
• Proces bieżący reprezentowany jest przez zmienną current.
• Odwołanie się do pola XXX w bloku kontrolnym procesu p zapisuje się p.XXX -- tak, jak odwołanie do pola rekordu.

1999-05-21