To tylko jedna z 5 stron tej notatki. Zaloguj się aby zobaczyć ten dokument.
Zobacz
całą notatkę
Systemy operacyjne / Szeregowanie zada ń 1 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 ń 2 Systemy operacyjne / Szeregowanie zada ń 3 Systemy operacyjne / Szeregowanie zada ń 4 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 . Systemy operacyjne / Szeregowanie zada ń 5 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 Systemy operacyjne / Szeregowanie zada ń 6 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 ń 7 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
(…)
…
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,
• 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…
…
159-100
99-60
59-60
Dwie klasy priorytetów
• real-time (niezmienne priorytety),
• variable (dynamiczne priorytety).
real-time,
kernel,
time-shared.
Priorytety procesów i wąśtków w obrębie
procesu (od +2 do –2 w stosunku do
procesu).
Preemption points w jądrze systemu operacyjnego.
Systemy operacyjne / Szeregowanie zadań
Systemy operacyjne / Szeregowanie zadań
19
18
…
… 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
9
Systemy operacyjne / Szeregowanie zadań
Systemy operacyjne / Szeregowanie zadań
Zaletą - jest przydział…
... zobacz całą notatkę
Komentarze użytkowników (0)