Polityki Planowania CPU: FCFS, SJF, Priorytet i Round Robin

Wybór planisty przez procesor

Planista w systemie operacyjnym decyduje, który z wielu gotowych procesów otrzyma dostęp do procesora, jak długo i co się stanie, gdy pojawi się proces o wyższej priorytetu. Każda polityka planowania jest kompromisem pomiędzy trzema liczbami: czasem oczekiwania (czas, w którym proces czeka w kolejce, ale nie wykonuje się), czasem trwania (całkowity czas od przybycia do zakończenia) i czasem reakcji (czas do pierwszego bajtu danych wyjściowych). Optymalizacja pod kątem jednej z tych wartości zwykle pogarsza inne, dlatego w rzeczywistych systemach stosuje się różne planisty dla serwerów wsadowych, komputerów biurowych i kontrolerów czasu rzeczywistego.

FCFS i SJF: dwa bieguny

Algorytm First-Come, First-Served (FCFS) uruchamia procesy w kolejności przybycia do ukończenia, bez przerwań. Jest to algorytm prosty w implementacji i sprawiedliwy w dosłownym sensie, ale cierpi na efekt konwojowy: jeden długi proces na początku kolejki zmusza wszystkie krótkie procesy stojące za nim do czekania, podnosząc średni czas oczekiwania, nawet jeśli całkowita ilość wykonanej pracy pozostaje niezmieniona.

Algorytm Shortest Job First (SJF) zamiast tego zawsze wybiera proces gotowy do uruchomienia o najkrótszym pozostałym czasie wykonywania (burst time). Jest to dowodowo optymalne dla minimalizacji średniego czasu oczekiwania wśród polityk bez przerwań – klasyczny wynik argumentu o wymianie – ale wymaga znajomości czasów wykonywania w wyprzedzeniu, co schedulery szacują jedynie (zwykle za pomocą wykładniczo ważonej średniej z przeszłych czasów wykonywania). Jego wersja preemptive, Shortest Remaining Time First (SRTF), może prowadzić do wyzyskania długich procesów bez końca, jeśli krótkie procesy nieustannie przybywają.

avg waiting time (non-preemptive) = (1/n) * sum(start_i - arrival_i)
SJF minimises this sum for a fixed, known set of burst times
— but a single misestimated burst can cascade delay onto everyone behind it

Rotacja i przedziały czasowe

Rotacja zapewnia każdemu gotowemu procesowi stały przedział czasowy (np. 10–100 ms), a następnie przerywa go i umieszcza na końcu kolejki, jeśli nie zakończył się. Ogranicza to najgorszy możliwy czas reakcji do w przybliżeniu (n − 1) × przedział czasu dla n gotowych procesów, dlatego też jest domyślna dla systemów interaktywnych. Rozmiar przedziału czasu to kluczowy element: zbyt duży powoduje, że rotacja degeneruje się w kierunku FCFS z efektem konwoju; zbyt mały prowadzi do tego, że system zużywa coraz większą część czasu procesora na przełączanie kontekstu – zapisywanie i przywracanie rejestrów, czyszczenie potoków i wpisów TLB – które nie wykonują żadnej użytecznej pracy.

Planowanie priorytetowe i ryzyko wypadnięcia w stan dormancy

Planowanie priorytetowe uruchamia proces o najwyższej priorytecie jako pierwszy, zarówno statycznie, jak i dynamicznie. Naturalnie mapuje się na rzeczywiste potrzeby (wątek kursora myszy powinien przejąć kontrolę nad kompilacją wsadową), ale sztywny podział na priorytety może powodować wypadnięcie w stan dormancy procesów o niskiej priorytecie, jeśli wysokie priorytety będą stale przybywać. Standardowym rozwiązaniem jest 'aging': stopniowe podwyższanie efektywnej priorytetu procesu czekającego w kolejce gotowej im dłużej pozostaje w niej, co gwarantuje, że ostatecznie zostanie uruchomiony, niezależnie od okoliczności.

effectivePriority(p) = basePriority(p) - k * waitingTime(p)
// lower number = higher priority; waitingTime grows every tick
// eventually even the lowest-priority process outranks new arrivals

Wielopoziomowe kolejki sprzętowe

Jądra produkcyjne (np. CFS z Linuksa, Windows, klasyczny Unix) wykorzystują warianty wielopoziomowej kolejki sprzętowej: kilka kolejek działających na zasadzie rundy (round robin) o różnych priorytetach i rozmiarach przedziału czasowego (quantum), gdzie proces zużywający cały przedział czasowy (zachowanie obciążone obliczeniami) jest obniżany do niższej priorytetu kolejki z dłuższym przedziałem czasowym, a proces oddający zasoby wcześnie (np. związane z I/O, zachowanie interaktywne) pozostaje na tej samej lub awansuje do wyższej priorytetu kolejki z krótszym przedziałem czasowym. Scheduler nie musi wiedzieć wcześniej o prawdziwej naturze procesu – wnioskuje ją na podstawie obserwowanego zachowania i adaptuje, łącząc responsywność rundy z efektywnością zbliżoną do algorytmu SJF dla naprawdę krótkich impulsów.

Często zadawane pytania

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz CPU Scheduling i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.