Systemy operacyjne / Szeregowanie zadań
Szeregowanie zadań
Cele szeregowania zadań
·ð zadowalajÄ…cy czas odpowiedzi,
·ð zadowalajÄ…ca przepustowość wykonywania procesów,
·ð efektywność wykorzystania procesora.
Typy szeregowania zadań
·ð dÅ‚ugoterminowe,
·ð Å›rednioterminowe,
·ð krótkoterminowe,
·ð wejÅ›cia/wyjÅ›cia.
Systemy operacyjne / Szeregowanie zadań
Systemy operacyjne / Szeregowanie zadań
Algorytmy porządkujące zbiór procesów w stanie gotowym (G) nazywamy
algorytmami szeregowania (scheduling).
Algorytmy te dzielÄ… siÄ™ na dwie klasy:
* bez wywłaszczania procesu
* z wywłaszczaniem procesu.
Wywłaszczanie (preemption) procesu polega na odebraniu mu procesora w wyniku
zajścia jakiegoś zdarzenia zewnętrznego.
W algorytmach bez wywłaszczeń procesor jest przydzielany innemu procesowi tylko
wtedy, gdy proces zajmujÄ…cy procesor ®ð Z.
Podstawowymi algorytmami szeregowania sÄ…:
1. kolejkowy bez wywłaszczeń (FIFO)
2. okrężny z wywłaszczaniem (RR)
3. priorytetowy z priorytetami statycznymi lub dynamicznymi
4. dwupoziomowy z kolejkami priorytetowymi
Informacje wykorzystywane w algorytmach szeregowania
·ð czas przebywania w pamiÄ™ci
·ð czas wykorzystania procesora
·ð priorytet procesu
·ð modyfikacje priorytetu procesu
Kryteria szeregowania (TSS)
·ð sprawiedliwy dostÄ™p do procesora
·ð maksymalna wydajność w sensie zajÄ™toÅ›ci CPU
·ð czas odpowiedzi dla użytkowników pracujÄ…cych w trybie interaktywnym
·ð czas odpowiedzi dla użytkowników pracujÄ…cych w trybie wsadowym
·ð maksymalna liczba prac przetwarzana w czasie
Zdarzenia powodujÄ…ce ponowne szeregowanie
·ð wyczerpaÅ‚ siÄ™ kwant czasu
·ð proces zakoÅ„czyÅ‚ dziaÅ‚anie (exit)
·ð procesowi brak pamiÄ™ci do kontynuacji dziaÅ‚ania
·ð proces wywoÅ‚aÅ‚ funkcjÄ™ sleep (®ð Z )
·ð pojawiÅ‚ siÄ™ proces o wyższym priorytecie
Systemy operacyjne / Szeregowanie zadań
Przegląd algorytmów szeregowania
Algorytm FIFO (FCFS)
Algorytm ten działa według następujących zasad:
* procesy są uporządkowane w kolejności przechodzenia ich w stan G
* procesor jest przydzielany procesowi najdłużej oczekującemu
* przydział ten trwa dotąd, dopóki dany proces nie zostanie przeniesiony w stan Z
Zalety:
* prosty w implementacji
* szybki w wykonaniu
Wady:
* możliwość zawładnięcia procesorem przez proces działający w długiej
(nieskończonej) pętli
* długi okres oczekiwania procesów (szczególnie krótkich) na wykonanie
Algorytm okrężny (RR)
Algorytm ten działa wg następujących zasad:
·ð procesy sÄ… uporzÄ…dkowane w sekwencjÄ™, poczÄ…tkowo w kolejnoÅ›ci
przechodzenia ich w stan G
·ð procesor jest przydzielany zawsze pierwszemu procesowi oczekujÄ…cemu w
sekwencji
·ð proces jest wywÅ‚aszczany po przekroczeniu okreÅ›lonego kwantu czasu i
przenoszony na koniec kolejki, a procesor jest przydzielany następnemu w
kolejce
Uwagi:
·ð każdy proces w stanie G otrzymuje procesor na kwant czasu, chyba że zmieni
swój stan ®ð Z
·ð upÅ‚ywajÄ…ce interwaÅ‚y czasowe sÄ… zliczane przez proces obsÅ‚ugi zegara (Pz),
który inicjuje operacje wywłaszczania
·ð w trybie systemowym zegar interwałów jest zatrzymywany
Zaletą - jest przydział procesora wszystkim istniejącym Pu w sposób równomierny,
przy czym żaden z nich nie może go zdominować
Wadą - jest dodatkowe zużytkowanie czasu procesora na obsługę Pz i
przełączanie procesów.
Algorytm priorytetowy (PR)
Systemy operacyjne / Szeregowanie zadań
Algorytm ten działa według następujących zasad:
·ð procesy należące do zbioru G sÄ… umieszczane w kolejkach priorytetowych
według priorytetów w sposób sekwencyjny
·ð procesor przydzielany jest kolejno procesom znajdujÄ…cym siÄ™ w kolejce o
najwyższym priorytecie według algorytmu FIFO, a następnie (gdy dana
kolejka staje się pusta) procesom z kolejki o niższym priorytecie
Uwagi.
Priorytety mogą być ustalane:
·ð statycznie - w chwili tworzenia procesu
·ð dynamicznie - w czasie istnienia procesu
Zmiany wartości priorytetów mogą być spowodowane:
* naruszeniem ograniczeń systemowych
* naruszeniem ograniczeń obliczeniowych
* wywołaniem sleep
* dostępem do sytemowych struktur danych
* rodzajem wywołania systemowego (open /dev/hd)
* ograniczeniem czasowym określającym chwilę uruchomienia procesu
Algorytm dwupoziomowy (SP)
Algorytm ten składa się z dwóch poziomów:
·ð algorytmu górnego poziomu zarzÄ…dzajÄ…cego pamiÄ™ciÄ… wirtualnÄ… (swapper)
·ð algorytmu niskiego poziomu zarzÄ…dzajÄ…cego dostÄ™pem do procesora
(scheduler)
Inne typy algorytmów szeregowania:
SPN - shortest process next,
wymaga wstępnej estymacji czasu wykonania,
przewidywalność czasu zakończenia długich procesów ograniczona,
możliwość zagłodzenia długich procesów.
SRT - shortest remaining time (preemptive SPN),
HRRN - highest response ratio next, gdzie R = ( w + s ) / s
w  czas spędzony w oczekiwaniu na procesor,
s  oczekiwany czas obsługi.
Feedback - preemptive + kolejki o różnych priorytetach zmieniane dynamicznie,
kara zadania wykonujące się długo,
nie wymaga a priori estymacji czasu wykonania procesów.
Systemy operacyjne / Szeregowanie zadań
Systemy operacyjne / Szeregowanie zadań
Szeregowanie w tradycyjnym systemie Unix
·ð wielopoziomy feedback z wykorzystaniem RR w każdej kolejce priorytetów,
·ð priorytety przeliczane raz na sekundÄ™,
·ð priorytet bazowy dzieli listÄ™ procesów na zbiory (ang. bands),
·ð proces utrzymywany priorytetem w swoim zbiorze.
Zbiory procesów:
1. swapper,
2. zarządzanie wejściem/wyjściem urządzeń blokowych,
3. zarzÄ…dzanie plikami,
4. zarządzanie wejściem/wyjściem urządzeń znakowych,
5. procesu użytkowe.
Szeregowanie w systemie Linux
Klasy szeregowania
SCHED_FIFO wÄ…tki FIFO czasu rzeczywistego,
SCHED_RR wÄ…tki RR czasu rzeczywistego,
SCHED_OTHER pozostałę wątki.
Systemy operacyjne / Szeregowanie zadań
·ð możliwość nadawania priorytetów w obrÄ™bie klasy,
Szeregowanie w Unix SVR4
Klasy priorytetów
159-100 real-time,
99-60 kernel,
59-60 time-shared.
Preemption points w jÄ…drze systemu operacyjnego.
Systemy operacyjne / Szeregowanie zadań
Szeregowanie w Windows 2000
Dwie klasy priorytetów
·ð real-time (niezmienne
priorytety),
·ð variable (dynamiczne
priorytety).
Priorytety procesów i wąśtków w
obrębie procesu (od +2 do  2 w
stosunku do procesu).
Systemy operacyjne / Szeregowanie zadań