Planowanie przydziału procesora jest to określenie kolejności przydziału jego mocy obliczeniowej procesom z kolejki procesów gotowych do działania. Poniżej zostaną omówione najciekawsze z algorytmów planowania przydziału procesora. FCFS (ang. first-come, first-served) oznacza "pierwszy zgłoszony - pierwszy obsłużony". Algorytm ten opiera się na prostej zasadzie, którą właściwie wyjaśnia jego nazwa. Najlepiej do implementacji algorytmu nadaje się kolejka FIFO, w której blok kontrolny procesu wchodzącego do kolejki dołączany jest na jej koniec, zaś wolny procesor przydzielany jest procesowi z początku kolejki.

Wadą wspomnianej metody przydziału procesora jest to, że średni czas oczekiwania może być bardzo długi. Jeżeli rozważymy przyjście w danym momencie czasu trzech procesów, których długości faz procesora wynoszą:

Proces Czas trwania fazy
    P1
    P2
    P3
           21 ms
           6 ms
           3 ms

przekonamy się, że nadejście procesów w kolejności P1,P2,P3 wyglądać będzie na diagramie Gantta następująco dla algorytmu FCFS:

[Diagram Gantta]

Dla procesu P1 czas oczekiwania wynosi więc 0 ms, dla procesu P2 21 ms, dla procesu P3 zaś 27 ms. Średni czas oczekiwania wynosi więc: (0+21+27)/3 = 16 ms. Dla sytuacji, w której procesy nadeszłyby w kolejności P3, P2, P1 diagram Gantta wyglądałby następująco:

[Diagram Gantta]

Dla takiego przypadku średni czas oczekiwania wyniósłby: (0+3+9)/3 = 4 ms. Widzimy więc, że zastosowanie algorytmu niesie ze sobą pewne ryzyko.

W warunkach dynamicznych działanie algorytmu również nie jest zadowalające. W przypadku, gdy mamy do czynienia z dużym procesem ograniczonym przez procesor oraz małymi (szybciej się wykonującymi) procesami ograniczonymi przez wejście-wyjście i proces ograniczony przez procesor jako pierwszy uzyska dostęp do procesora, procesy wejścia-wyjścia oczekiwać będą w kolejce procesów gotowych stosunkowo długo, a urządzenia wejścia wyjścia w tym czasie nie będą mogły być używane. Po zakończeniu wykonania procesu ograniczonego przez procesor, proces ten przejdzie do kolejki oczekującej na wejście-wyjście, natomiast małe procesy ograniczone przez wejście-wyjście wykonają się w krótkim czasie i zwolnią procesor, który może wtedy być bezczynny. Następnie powróci nasz duży proces, który ponownie będzie obsługiwany przez procesor, a procesy mniejszych rozmiarów będą musiały czekać. Sytuację wyżej opisaną, w której procesy oczekują na zwolnienie procesora przez jeden duży proces, nazywamy efektem konwoju (ang. convoy effect).

Algorytm ten, z uwagi na to, że pozwala procesowi na zajmowanie procesora przez dłuższy czas, nie nadaje się do stosowania w środowiskach z podziałem czasu, w których każdy użytkownik powinien dostawać przydział procesora w równych odstępach czasu. Taki algorytm, który po objęciu kontroli nad procesorem nie umożliwia do niego dostępu, nazywamy niewywłaszczającym. Algorytm SJF (ang. shortest-job-first), czyli "najkrótsze zadanie najpierw", opiera swe działanie na powiązaniu procesu z długością jego najbliższej fazy. Procesor zostaje przydzielony procesowi, który ma najkrótszą następną fazę procesora. W przypadku, gdy dwa procesy mają następne fazy procesora równe, stosuje się algorytm FCFS.

Porównajmy działanie tego algorytmu do algorytmu FCFS. Załóżmy więc, że mamy 3 następujące procesy:

Proces Czas trwania fazy
    P1
    P2
    P3
           6 ms
           9 ms
           3 ms

Diagram Gantta dla tych procesów wygląda następująco:

[Diagram Gantta]

Jeżeli procesy przychodzą w kolejności P1, P2, P3 to dla algorytmu SJF średni czas oczekiwania wynosi (3+9+0)/3 = 4ms, zaś dla algorytmu FCFS wyniósłby (0+6+15)/3 = 7 ms.

Algorytm SJF daje minimalny średni czas dla danego zbioru procesów. Mówimy, że algorytm SJF jest optymalny.

Dużym problemem w algorytmie SJF jest określenie długości następnego zamówienia na przydział procesora. Przy planowaniu długoterminowym (zadań), za czynnik ten możemy przyjąć limit czasu procesu, określony przez użytkownika, który zadanie przedłożył. Algorytm SJF jest więc chętnie używany w planowaniu długoterminowym. Natomiast w przypadku planowania krótkoterminowego, nie ma sposobu na określenie długości następnej fazy procesora. Dlatego też oszacowuje się tę wartość, obliczając ją na ogół jako średnią wykładniczą pomiarów długości poprzednich faz procesora [1].

Możliwe są dwa sposoby realizacji algorytmu SJF - wywłaszczająca (ang. shortest-remaining-time-first) oraz niewywłaszczająca. Różnica pomiędzy tymi realizacjami widoczna jest w sytuacji, gdy w kolejce procesów gotowych pojawia się nowy proces o krótszej następnej fazie procesora niż pozostała faza "resztki" procesu aktualnie wykonywanego. W takim układzie algorytm wywłaszczający usuwa aktualny proces z procesora, zaś algorytm niewywłaszczający pozwala procesowi bieżącemu na zakończenie fazy procesora. Forma wywłaszczająca algorytmu SJF jest więc szybsza. Algorytm planowania priorytetowego jest ogólnym przypadkiem algorytm SJF. Zamiast długości następnej fazy z algorytmu SJF, procesowi przypisuje się priorytet. Procesy o wyższym proiorytecie mają pierwszeństwo w dostępie do procesora, przed procesami o priorytecie niższym. Procesom o równych priorytetach przydziela się procesor zgodnie z algorytmem FCFS.

Priorytety definiuje się wewnętrznie lub zewnętrznie. Wewnętrzna definicja priorytetu opiera się na własnościach procesu, np.: stosunek średniej fazy we/wy do średniej fazy procesora, wielkość obszaru wymaganej pamięci, liczba otwartych plików, itp. Do określenia priorytetów zewnętrznych używa się kryteriów spoza wnętrza systemu, np.: kwota opłat za użytkowanie komputera, znaczenie procesu dla użytkownika, itp.

Problem związany z planowaniem priorytetowym to nieskończone blokowanie (ang. indefinite blocking), nazywane głodzeniem (ang. starvation). Problem wiąże się z odkładaniem możliwości obsługi przez procesor tych procesów, które mają niski priorytet. W sytuacji, w której system jest bardzo obciążony, może zdarzyć się, że proces o niskim priorytecie będzie czekał w kolejce procesów gotowych w nieskończoność. Powoduje to duże opóźnienia wykonania procesu o niskim priorytecie, a może doprowadzić do niewykonania tego procesu.

Problem ten jest rozwiązywany poprzez postarzanie (ang. aging) procesów o niskich priorytetach. Postarzanie procesów o niskim priorytecie, które długo oczekują na obsługę procesora odbywa się co pewien okres czasu. W ten sposób, z procesu o niskim priorytecie, tworzy się proces o wysokim priorytecie, który na pewno zostanie obsłużony w pierwszej kolejności.

Algorytmy planowania priorytetowego mogą być postaci wywłaszczającej, bądź niewywłaszczającej. Działanie jest analogiczne jak dla algorytmu SJF, z tą różnicą, że kryterium wyboru jest priorytet, a nie czas trwania następnej fazy. Algorytm planowania rotacyjnego (ang. round-robin - RR) jest oparty na algorytmie FCFS, jednakże różni się od FCFS faktem, że możliwe jest wywłaszczanie. Algorytm ten jest chętnie stosowany w systemach z podziałem czasu.

Zasada działania algorytmu jest następująca. Z każdym procesem powiązany jest kwant czasu, najczęściej 10 do 100 ms. Procesom znajdującym się w kolejce (traktowanej jako cykliczna) procesów gotowych do wykonania, przydzielane są odpowiednie odcinki czasu, nie dłuższe niż jeden kwant czasu.

Do implementacji algorytmu, podobnie jak w przypadku FCFS, używa się kolejki FIFO - brany jest pierwszy proces z wyjścia kolejki, ustawiany jest timer na przerwanie po upływie 1 kwantu czasu i proces jest wysyłany do procesora. Jeżeli czas trwania fazy procesu jest krótszy od 1 kwantu czasu, proces sam zwolni procesor i rozpocznie się obsługiwanie kolejnego procesu z kolejki. Jeżeli proces ma dłuższą fazę od 1 kwantu czasu, to nastąpi przerwanie zegarowe systemu operacyjnego, nastąpi przełączenie kontekstu, a proces do niedawna wykonywany, trafi na koniec kolejki procesów gotowych do wykonania.

Zobaczmy, ile wynosi średni czas oczekiwania w porównaniu z metodą FCFS dla następujących danych:

Proces Czas trwania fazy
    P1
    P2
    P3
           21 ms
           6 ms
           3 ms

Dla kroku 7 ms diagram Gantta dla powyższych procesów wyglądał będzie następująco:

[Diagram Gantta]

Śreni czas oczekiwania wynosi więc: (0+13+16)/3 = 9,67 ms.

Wydajność algorytmu rotacyjnego zależy od kwantu czasu. W przypadku, gdy kwant czasu jest bardzo długi (dąży do nieskończoności) metoda RR działa jak FCFS. Natomiast w przypadku, gdy kwant czasu jest bardzo krótki (dąży do zera) planowanie RR nazywamy dzieleniem procesora (ang. processor sharing), gdyż zachodzi złudzenie, że każdy z n procesów ma własny procesor działający z prędkością 1/n prędkości prawdziwego procesora [1].

W przypadku algorytmu RR, podczas mówienia o wydajności, należy zastanowić się nad zagadnieniem przełączania kontekstu. Im mniejszy jest kwant czasu, tym system bardziej jest narażony na częste przełączenia kontekstu. Jeżeli czas przełączania kontekstu wynosi 10 procent kwantu czasu, to niemalże 10 procent czasu procesora jest tracone w wyniku przełączania kontekstu.

NASTĘPNA