Planowanie przydziału procesora
Planowanie przydziału procesora
W pamięci operacyjnej znajduje się kilka
procesów jednocześnie.
Kiedy jakiś proces musi czekać, system
operacyjny odbiera mu procesor i oddaje do
dyspozycji innego procesu.
Planowanie przydziału procesora jest
podstawową funkcją każdego systemu
operacyjnego.
Fazy procesora i wejścia-wyjścia
Fazy procesora i wejścia-wyjścia
załaduj
przechowaj
dodaj Faza procesora
przechowaj
czytaj z pliku
Czekaj na urzÄ…dzenie
Faza wejścia-wyjścia
wejścia-wyjścia
przechowaj
dodaj
Faza procesora
zwiększ indeks
pisz do pliku
Czekaj na urzÄ…dzenie
Faza wejścia-wyjścia
wejścia-wyjścia
załaduj
przechowaj
Faza procesora
dodaj
przechowaj
czytaj z pliku
Czekaj na urzÄ…dzenie
Faza wejścia-wyjścia
wejścia-wyjścia
Czasy faz procesora
Czasy faz procesora
160
140
120
100
80
60
40
20
0
Czas trwania fazy
Cz
Ä™
s to
ś ć
wys t
Ä™
po wania fazy
1
3
5
7
9
11
13
15
Planowanie przydziału procesora
Planowanie przydziału procesora
Proces ograniczony przez wejście-wyjście
ma zazwyczaj dużo krótkich faz procesora.
Proces ograniczony przez procesor może mieć
mało, lecz bardzo długich faz procesora.
Planowanie przydziału procesora
Planowanie przydziału procesora
Decyzje o zmianie przydziału procesora podejmowane są, gdy:
1. proces przeszedł od stanu aktywności do czekania, np. na
zakończenie potomka, lub zamówił we-wy,
2. proces przeszedł od stanu aktywności do gotowości, np.
wskutek wystÄ…pienia przerwania,
3. proces przeszedł od stanu czekania do gotowości, np. po
zakończeniu we-wy,
4. proces kończy działanie.
Jeśli planowanie odbywa się tylko w przypadkach 1 i 4, to mamy
Jeśli planowanie odbywa się tylko w przypadkach 1 i 4, to mamy
do czynienia z planowaniem niewywłaszczeniowym,
do czynienia z
w przeciwnym wypadku planowanie jest wywłaszczeniowe.
Planowanie przydziału procesora
Planowanie przydziału procesora
Bez wywłaszczeń - proces, który otrzymał procesor, odda go
Bez wywłaszczeń - proces, który otrzymał procesor, odda go
dopiero przy przejściu do stanu oczekiwania lub po
dopiero przy przejściu do stanu oczekiwania lub po
zakończeniu. Nie wymaga zegara. Stosowane w systemach
zakończeniu. Nie wymaga zegara. Stosowane w systemach
Windows.
Windows.
Planowanie wywłaszczające jest ryzykowne.
Planowanie wywłaszczające jest .
Należy brać pod uwagę fakt, że proces w momencie
Należy brać pod uwagę fakt, że proces w momencie
wywłaszczenia może być w trakcie wykonywania funkcji
wywłaszczenia może być w trakcie wykonywania funkcji
systemowej.
systemowej.
Zabezpieczenia:
Zabezpieczenia:
system czeka z przełączeniem kontekstu do zakończenia f.s.
system czeka z przełączeniem kontekstu do zakończenia f.s.
przerwania są blokowane przy przejściu do ryzykownych
przerwania są blokowane przy przejściu do ryzykownych
fragmentów kodu jądra,
fragmentów kodu jądra,
nie wywłaszcza procesu, gdy wewnętrzne struktury jądra są
nie wywłaszcza procesu, gdy wewnętrzne struktury jądra są
niespójne.
niespójne.
Ekspedytor (dispatcher)
Ekspedytor (dispatcher)
Jest to moduł, który przekazuje procesor do dyspozycji procesu
Jest to moduł, który przekazuje procesor do dyspozycji procesu
wybranego przez planistę krótkoterminowego. Do jego zadań
wybranego przez planistę krótkoterminowego. Do jego zadań
należy:
należy:
przełączanie kontekstu,
przełączanie kontekstu,
przełączanie procesu do trybu użytkownika,
przełączanie procesu do trybu użytkownika,
wykonanie skoku do odpowiedniego adresu w programie w celu
wykonanie skoku do odpowiedniego adresu w programie w celu
wznowienia działania programu
wznowienia działania programu
Opóz
nienie ekspedycji - czas, jaki ekspedytor zużywa na
Opóz
nienie ekspedycji - czas, jaki ekspedytor zużywa na
wstrzymanie jednego procesu i uaktywnienie innego.
wstrzymanie jednego procesu i uaktywnienie innego.
Czas ten powinien być możliwie najkrótszy - ekspedytor powinien
Czas ten powinien być możliwie najkrótszy - ekspedytor powinien
więc być jak najszybszy.
więc być jak najszybszy.
Kryteria planowania
Kryteria planowania
Wykorzystanie procesora - w realnych systemach od 40%
Wykorzystanie procesora - w realnych systemach od 40%
(słabe) do 90% (intensywne),
(słabe) do 90% (intensywne),
Przepustowość - mierzona ilością procesów kończonych w
Przepustowość - mierzona ilością procesów kończonych w
jednostce czasu (dla długich - kilka na godzinę, dla krótkich -
jednostce czasu (dla długich - kilka na godzinę, dla krótkich -
kilka na sekundÄ™),
kilka na sekundÄ™),
czas cyklu przetwarzania - od nadejścia procesu do systemu, do
czas cyklu przetwarzania - od nadejścia procesu do systemu, do
jego zakończenia (suma czasów oczekiwania na wejście do
jego zakończenia (suma czasów oczekiwania na wejście do
pamięci, w kolejce procesów gotowych, okresów aktywności i
pamięci, w kolejce procesów gotowych, okresów aktywności i
operacji wejścia-wyjścia)
operacji wejścia-wyjścia)
Czas oczekiwania - suma czasów w których procesor czeka w
Czas oczekiwania - suma czasów w których procesor czeka w
kolejce p. gotowych,
kolejce p. gotowych,
Czas odpowiedzi - w systemach interakcyjnych - czas od
Czas odpowiedzi - w systemach interakcyjnych - czas od
wysłania żądania do rozpoczęcia odpowiedzi.
wysłania żądania do rozpoczęcia odpowiedzi.
Planowanie optymalne
Planowanie optymalne
Maksymalne wykorzystanie procesora,
wykorzystanie procesora,
maksymalna przepustowość,
przepustowość,
minimalny czas cyklu przetwarzania,
czas cyklu przetwarzania,
minimalny czas oczekiwania,
czas oczekiwania,
minimalny czas odpowiedzi.
minimalny czas odpowiedzi.
Planowanie metodÄ… FCFS
Planowanie metodÄ… FCFS
(pierwszy zgłoszony - pierwszy obsłużony)
(pierwszy zgłoszony - pierwszy obsłużony)
Zgłaszają się trzy procesy:
1. P1 o czasie trwania fazy: 24 ms
2. P2 o czasie trwania fazy: 3 ms
3. P3 o czasie trwania fazy: 3 ms
Diagram Gantta dla planowania FCFS:
0
Czas oczekiwania
24 27 30
Åšredni czas oczekiwania wynosi:
(0+24+27)/3 = 17 ms
Planowanie metodÄ… FCFS
Planowanie metodÄ… FCFS
A gdyby procesy zgłosiły się w kolejności:
1. P2
2. P3
3. P1
Diagram Gantta dla planowania FCFS:
0
3 6
Czas oczekiwania
30
Średni czas oczekiwania wyniósłby wtedy:
(0+3 +6)/3 = 3 ms
Planowanie metodÄ… FCFS
Planowanie metodÄ… FCFS
Pierwszy przykład pokazuje, że planowanie metodą FCFS
Pierwszy przykład pokazuje, że planowanie metodą FCFS
nie jest optymalne
nie jest optymalne
Średni czas oczekiwania bardzo zależy od kolejności
Średni czas oczekiwania bardzo zależy od kolejności
zgłoszenia procesów
zgłoszenia procesów
Efekt konwoju - małe procesy czekają na zwolnienie
Efekt konwoju - małe procesy czekają na zwolnienie
procesora przez jeden wielki proces
procesora przez jeden wielki proces
Algorytm FCFS jest niewywłaszczający
Algorytm FCFS jest niewywłaszczający
Algorytm ten jest nieużyteczny w systemach z podziałem
Algorytm ten jest nieużyteczny w systemach z podziałem
czasu, w których procesy powinny dostawać procesor w
czasu, w których procesy powinny dostawać procesor w
regularnych odstępach czasu
regularnych odstępach czasu
Planowanie metodÄ… SJF
Planowanie metodÄ… SJF
(najpierw najkrótsze zadanie)
(najpierw najkrótsze zadanie)
Zgłaszają się cztery procesy:
1. P1 o czasie trwania fazy: 6 ms
2. P2 o czasie trwania fazy: 8 ms
3. P3 o czasie trwania fazy: 7 ms
4. P4 o czasie trwania fazy: 3 ms
Diagram Gantta dla planowania SJF:
0
3 9 16 24
Åšredni czas oczekiwania wynosi:
(3+16+9+0)/4 = 7 ms
Dla metody FCFS wynosiłby:
(0+6+14+21)/4 =10,25 ms
Planowanie metodÄ… SJF
Planowanie metodÄ… SJF
Można udowodnić, że planowanie tą metodą jest
Można udowodnić, że planowanie tą metodą jest
optymalne
optymalne
Umieszczenie krótkiego procesu przed długim w
Umieszczenie krótkiego procesu przed długim w
większym stopniu zmniejsza czas oczekiwania krótkiego
większym stopniu zmniejsza czas oczekiwania krótkiego
procesu niż zwiększa czas oczekiwania procesu długiego
procesu niż zwiększa czas oczekiwania procesu długiego
Algorytm SJF jest często używany przy planowaniu
Algorytm SJF jest często używany przy planowaniu
długoterminowym
długoterminowym
Problem - nie można przewidzieć długości następnej fazy
Problem - nie można przewidzieć długości następnej fazy
procesora, można ją tylko szacować, najczęściej za pomocą
procesora, można ją tylko szacować, najczęściej za pomocą
średniej wykładniczej z poprzednich faz procesora:
średniej wykładniczej z poprzednich faz procesora:
Planowanie metodÄ… SJF
Planowanie metodÄ… SJF
fn+1 = Ä… tn + (1-Ä…) fn
fn+1 = Ä… tn + (1-Ä…) fn
gdzie:
gdzie:
Ä… - współczynnik wagi (0÷1)
Ä… - współczynnik wagi (0÷1)
tn - długość n-tej fazy procesora,
tn - długość n-tej fazy procesora,
fn - informacje o poprzednich fazach
fn - informacje o poprzednich fazach
gdy Ä… =0 - bierzemy pod uwagÄ™ tylko dawniejszÄ… historiÄ™,
gdy Ä… =0 - bierzemy pod uwagÄ™ tylko dawniejszÄ… historiÄ™,
a gdy Ä… =1 - bierzemy pod uwagÄ™ tylko ostatnie fazy.
a gdy Ä… =1 - bierzemy pod uwagÄ™ tylko ostatnie fazy.
Najczęściej ą =0,5
Najczęściej ą =0,5
Planowanie metodÄ… SJF
Planowanie metodÄ… SJF
Algorytm SJF może być wywłaszczający lub
Algorytm SJF może być wywłaszczający lub
niewywłaszczający.
niewywłaszczający.
Gdy do kolejki dochodzi nowy proces, który posiada fazę
Gdy do kolejki dochodzi nowy proces, który posiada fazę
procesora krótszą niż pozostały czas w bieżącym procesie,
procesora krótszą niż pozostały czas w bieżącym procesie,
algorytm wywłaszczający odbiera procesor bieżącemu
algorytm wywłaszczający odbiera procesor bieżącemu
procesowi i przekazuje go krótszemu.
procesowi i przekazuje go krótszemu.
Metoda ta nazywa siÄ™ SRTF (shortest remaining time first)
Metoda ta nazywa siÄ™ SRTF (shortest remaining time first)
czyli  najpierw najkrótszy pozostały czas .
czyli  najpierw najkrótszy pozostały czas .
Algorytm niewywłaszczający pozwala na dokończenie fazy
Algorytm niewywłaszczający pozwala na dokończenie fazy
procesora.
procesora.
Planowanie priorytetowe
Planowanie priorytetowe
Mechanizm bardzo podobny do SJF, ale kryterium
Mechanizm bardzo podobny do SJF, ale kryterium
szeregowania jest priorytet procesu.
szeregowania jest priorytet procesu.
Najpierw wykonywane są procesy o ważniejszym priorytecie.
Najpierw wykonywane są procesy o ważniejszym priorytecie.
Priorytety mogą być definiowane wewnętrznie, na podstawie
Priorytety mogą być definiowane wewnętrznie, na podstawie
pewnych cech procesu (np. wielkość pamięci, limity czasu,
pewnych cech procesu (np. wielkość pamięci, limity czasu,
zapotrzebowanie na urzÄ…dzenia we-wy itd..)
zapotrzebowanie na urzÄ…dzenia we-wy itd..)
Priorytety definiowane zewnętrznie mogą np. zależeć od
Priorytety definiowane zewnętrznie mogą np. zależeć od
ważności użytkownika, jego firmy czy też od innych
ważności użytkownika, jego firmy czy też od innych
politycznych uwarunkowań.
politycznych uwarunkowań.
Planowanie priorytetowe
Planowanie priorytetowe
Wady:
Wady:
Procesy o niskim (mało ważnym) priorytecie mogą nigdy nie
Procesy o niskim (mało ważnym) priorytecie mogą nigdy nie
dostać procesora (głodzenie, nieskończone blokowanie)
dostać procesora (głodzenie, nieskończone blokowanie)
Przykład: w 1973 r. w wycofywanym z eksploatacji na MIT
Przykład: w 1973 r. w wycofywanym z eksploatacji na MIT
komputerze IBM 7094 wykryto  zagłodzony proces o
komputerze IBM 7094 wykryto  zagłodzony proces o
niskim priorytecie, który został zapuszczony do wykonania
niskim priorytecie, który został zapuszczony do wykonania
w 1967 roku ;-((((
w 1967 roku ;-((((
RozwiÄ…zaniem problemu jest  postarzanie czyli podnoszenie
RozwiÄ…zaniem problemu jest  postarzanie czyli podnoszenie
priorytetu procesów oczekujących zbyt długo.
priorytetu procesów oczekujących zbyt długo.
Przykład: przydział mieszkania dla dziadka w Alternatywy 4
Przykład: przydział mieszkania dla dziadka w Alternatywy 4
Planowanie rotacyjne
Planowanie rotacyjne
(Round-Robin - RR)
(Round-Robin - RR)
Zaprojektowane specjalnie do systemów z podziałem
Zaprojektowane specjalnie do systemów z podziałem
czasu.
czasu.
Każdy proces otrzymuje kwant czasu (10-100ms), po
Każdy proces otrzymuje kwant czasu (10-100ms), po
upływie którego jest wywłaszczany i umieszczany na
upływie którego jest wywłaszczany i umieszczany na
końcu kolejki zadań gotowych.
końcu kolejki zadań gotowych.
Kolejny proces do wykonania jest wybierany zgodnie z
Kolejny proces do wykonania jest wybierany zgodnie z
algorytmem FCFS
algorytmem FCFS
Jeżeli jest n procesów gotowych a kwant czasu wynosi q,
Jeżeli jest procesów gotowych a kwant czasu wynosi
to każdy proces czeka nie dłużej niż (n-1)*q jednostek
czasu.
Planowanie metodÄ… RR, kwant
Planowanie metodÄ… RR, kwant
czasu = 25 ms
czasu = 25 ms
1. P1 o czasie trwania fazy: 24 ms
2. P2 o czasie trwania fazy: 3 ms
3. P3 o czasie trwania fazy: 3 ms
Diagram Gantta dla q=25 ms:
0
Czas oczekiwania
24 27 30
Åšredni czas oczekiwania wynosi:
(0+24+27)/3 = 17 ms
Przełączań kontekstu: 2
Planowanie metodÄ… RR, kwant
Planowanie metodÄ… RR, kwant
czasu = 4 ms
czasu = 4 ms
1. P1 o czasie trwania fazy: 24 ms
2. P2 o czasie trwania fazy: 3 ms
3. P3 o czasie trwania fazy: 3 ms
Diagram Gantta dla q=4 ms:
0
4 7 10 14 18 22 26 30
Åšredni czas oczekiwania wynosi:
(17)/3 = 5,66 ms
Przełączań kontekstu: 7
Planowanie metodÄ… RR, kwant
Planowanie metodÄ… RR, kwant
czasu = 1 ms
czasu = 1 ms
1. P1 o czasie trwania fazy: 24 ms
2. P2 o czasie trwania fazy: 3 ms
3. P3 o czasie trwania fazy: 3 ms
Diagram Gantta dla q=1 ms:
0
30
Przełączań kontekstu: 29
Planowanie rotacyjne, cd.
Planowanie rotacyjne, cd.
Wydajność algorytmu bardzo zależy od kwantu czasu q
Wydajność
Gdy q jest duże, to algorytm RR przechodzi w FCFS
Gdy q jest duże, to algorytm RR przechodzi w FCFS
Gdy q jest bardzo małe, to znaczna część czasu procesora
Gdy q jest bardzo małe, to znaczna część
poświęcona jest na przełączanie kontekstu
Dobra zasada:
Dobra zasada:
80% faz procesora powinno być krótszych niż jeden kwant
80% faz procesora powinno być krótszych niż jeden kwant
czasu.
czasu.
Wielopoziomowe planowanie kolejek
Wielopoziomowe planowanie kolejek
Kolejka procesów gotowych jest podzielona na oddzielne pod-
Kolejka procesów gotowych jest podzielona na oddzielne pod-
kolejki, na przykład:
kolejki, na przykład:
kolejka procesów pierwszoplanowych (foreground),
kolejka procesów pierwszoplanowych (foreground),
kolejka procesów drugoplanowych (background).
kolejka procesów drugoplanowych (background).
Przykładowe proponowane algorytmy planowania:
Przykładowe proponowane algorytmy planowania:
procesy pierwszoplanowe: RR
procesy pierwszoplanowe: RR
procesy drugoplanowe: FCFS
procesy drugoplanowe: FCFS
Procesy pierwszoplanowe majÄ… absolutny priorytet nad
Procesy pierwszoplanowe majÄ… absolutny priorytet nad
drugoplanowymi.
drugoplanowymi.
Aby nie  zagłodzić procesów 2-planowych, stosuje się podział
Aby nie  zagłodzić procesów 2-planowych, stosuje się podział
czasu na kolejki, przykładowo:
czasu na kolejki, przykładowo:
kolejka pierwszoplanowa - 80% czasu procesora,
kolejka pierwszoplanowa - 80% czasu procesora,
kolejka drugoplanowa - pozostałe 20%
kolejka drugoplanowa - pozostałe 20%
Kolejki wielopoziomowe ze
Kolejki wielopoziomowe ze
sprzężeniem zwrotnym
sprzężeniem zwrotnym
Mechanizm ten pozwala na przesuwanie procesów pomiędzy
Mechanizm ten pozwala na przesuwanie procesów pomiędzy
kolejkami
kolejkami
Proces, który używa za dużo procesora, można  karnie
Proces, który używa za dużo procesora, można  karnie
przenieść do kolejki o niższym priorytecie i przez to dać
przenieść do kolejki o niższym priorytecie i przez to dać
szerszy dostęp do procesora innym procesom.
szerszy dostęp do procesora innym procesom.
Dzięki temu procesy ograniczone przez we-wy i procesy
Dzięki temu procesy ograniczone przez we-wy i procesy
interakcyjne mogą pozostać w kolejkach o wyższch
interakcyjne mogą pozostać w kolejkach o wyższch
priorytetach.
priorytetach.
DÅ‚ugo oczekujÄ…ce procesy z kolejki niskopriorytetowej mogÄ…
DÅ‚ugo oczekujÄ…ce procesy z kolejki niskopriorytetowej mogÄ…
być przeniesione do ważniejszej - działa mechanizm
być przeniesione do ważniejszej - działa mechanizm
postarzania procesów (przeciwdziała ich głodzeniu).
postarzania procesów (przeciwdziała ich głodzeniu).
Planowanie ze sprzężeniem zwrotnym jest najbardziej
złożonym algorytmem planowania przydziału procesora.
Kolejki wielopoziomowe ze
Kolejki wielopoziomowe ze
sprzężeniem zwrotnym - przykład
sprzężeniem zwrotnym - przykład
Kolejka trzypoziomowa: K0, K1,K2
Kolejka trzypoziomowa: K0, K1,K2
Proces wchodzÄ…cy trafia do kolejki k0 i dostaje kwant czasu 8 ms.
Proces wchodzÄ…cy trafia do kolejki k0 i dostaje kwant czasu 8 ms.
Jeśli nie zakończy się w tym czasie, jest wyrzucany na koniec
Jeśli nie zakończy się w tym czasie, jest wyrzucany na koniec
niższej kolejki K1.
niższej kolejki K1.
Gdy kolejka K0 się opróżni i przyjdzie czas wykonywania
Gdy kolejka K0 się opróżni i przyjdzie czas wykonywania
naszego procesu, dostaje on kwant czasu 16 ms.
naszego procesu, dostaje on kwant czasu 16 ms.
Jeśli i w tym czasie proces nie skończy działania, jest wyrzucany
Jeśli i w tym czasie proces nie skończy działania, jest wyrzucany
na koniec kolejki K2, obsługiwanej w porządku FCFS
na koniec kolejki K2, obsługiwanej w porządku FCFS
(oczywiście pod warunkiem, że kolejki K0 i K1 są puste).
(oczywiście pod warunkiem, że kolejki K0 i K1 są puste).
Tak więc najszybciej wykonywane są procesy do 8 ms, nieco
Tak więc najszybciej wykonywane są procesy do 8 ms, nieco
wolniej procesy od 8 do 8+16=24 ms, a najdłużej czekają procesy
wolniej procesy od 8 do 8+16=24 ms, a najdłużej czekają procesy
długie (są obsługiwane w cyklach procesora nie wykorzystanych
długie (są obsługiwane w cyklach procesora nie wykorzystanych
przez kolejki 1 i 2)
przez kolejki 1 i 2)
Planowanie wieloprocesorowe.
Planowanie wieloprocesorowe.
Planowanie heterogeniczne - dla systemów sieciowych,
Planowanie heterogeniczne - dla systemów sieciowych,
rozproszonych, o różnych procesorach - bardzo trudne w
rozproszonych, o różnych procesorach - bardzo trudne w
realizacji
realizacji
Planowanie homogeniczne - dla procesorów tego samego typu.
Planowanie homogeniczne - dla procesorów tego samego typu.
Nie stosuje się oddzielnych kolejek dla każdego procesora -
Nie stosuje się oddzielnych kolejek dla każdego procesora -
możliwość przestojów niektórych procesorów.
możliwość przestojów niektórych procesorów.
Wieloprzetwarzanie symetryczne - każdy procesor sam wybiera
Wieloprzetwarzanie symetryczne - każdy procesor sam wybiera
procesy ze wspólnej kolejki - działanie musi być bardzo starannie
procesy ze wspólnej kolejki - działanie musi być bardzo starannie
zaprogramowane, aby uniknąć np. dublowania.
zaprogramowane, aby uniknąć np. dublowania.
Wieloprzetwarzanie asymetryczne - jeden procesor jest nadrzędny
Wieloprzetwarzanie asymetryczne - jeden procesor jest nadrzędny
(master) i on planuje przydział procesów, a pozostałe (slave)
(master) i on planuje przydział procesów, a pozostałe (slave)
wykonujÄ… przydzielone im zadania.
wykonujÄ… przydzielone im zadania.
Planowanie w czasie rzeczywistym
Planowanie w czasie rzeczywistym
W rygorystycznych systemach czasu rzeczywistego musi być
W musi być
zapewnione wykonanie zadania krytycznego w określonym
zapewnione wykonanie zadania krytycznego w określonym
czasie. Następuje rezerwacja zasobów niezbędnych do wykonania
czasie. Następuje rezerwacja zasobów niezbędnych do wykonania
zadania. Jeśli planista nie może zarezerwować zasobów -
zadania. Jeśli planista nie może zarezerwować zasobów -
rezygnuje z przydziału zadania do procesora.
rezygnuje z przydziału zadania do procesora.
W Å‚agodnych systemach czasu rzeczywistego procesy cz. rz.
W procesy cz. rz.
mają wyższy priorytet niż pozostałe zadania. Priorytet tych
mają wyższy priorytet niż pozostałe zadania. Priorytet tych
procesów nie może ulec obniżeniu!
procesów nie może ulec obniżeniu!
W krytycznych przypadkach musimy zezwolić na wywłaszczanie
W krytycznych przypadkach musimy zezwolić na wywłaszczanie
funkcji systemowych (muszą one posiadać punkty
funkcji systemowych (muszą one posiadać punkty
wywłaszczenia), lub nawet całego jądra (potrzebne mechanizmy
wywłaszczenia), lub nawet całego jądra (potrzebne mechanizmy
synchronizacji danych jÄ…dra).
synchronizacji danych jÄ…dra).
Wysokopriorytetowe procesy nie mogą czekać na zakończenie
Wysokopriorytetowe procesy nie mogą czekać na zakończenie
niskopriorytetowych.
niskopriorytetowych.
Ocena algorytmów planowania
Ocena algorytmów planowania
Modelowanie deterministyczne - zakładamy z góry konkretne
- zakładamy z góry konkretne
obciążenie systemu i definiujemy zachowanie się poszczególnych
obciążenie systemu i definiujemy zachowanie się poszczególnych
algorytmów w tych warunkach. Przykład - wyznaczanie średniego
algorytmów w tych warunkach. Przykład - wyznaczanie średniego
czasu oczekiwania z diagramu Gantta
czasu oczekiwania z diagramu Gantta
Modele obsługi kolejek - bazują na badaniach dot. analizy
- bazujÄ… na badaniach dot. analizy
obsługi kolejek w sieciach.
obsługi kolejek w sieciach.
Wzór Little a: n=L*W
Wzór Little a: n=L*W
gdzie: n- średnia długość kolejki, L - liczba nowych procesów na
gdzie: n- średnia długość
sekundę, W - średni czas oczekiwania w kolejce.
Symulacje - programuje siÄ™ model systemu i generuje dane
symulacyjne. Taśmy śladów z rzeczywistego systemu pomagają w
ustawieniu danych do symulacji
Implementacja - algorytm zaimplementowany w rzeczywistym
systemie. Metoda kosztowna ale dokładna.
Planowanie w systemie Solaris
Planowanie w systemie Solaris
Planowanie w wielopoziomowych kolejkach ze sprzężeniem
zwrotnym,
4 klasy procesów: real time, system, time sharing, interactive
Priorytet globalny i priorytety w obrębie klas
Proces potomny dziedziczy klasÄ™ i priorytet
Klasa domyślna - time sharing
Im większy priorytet, tym mniejszy kwant czasu
Klasa system - procesy jÄ…dra
Klasa interactive - wyższy priorytet mają aplikacje graficzne X11
WÄ…tki o tym samym priorytecie planowane sÄ… algorytmem RR
Planowanie w systemie Windows 2000
Planowanie w systemie Windows 2000
Planowanie priorytetowe z wywłaszczeniami
32 kolejki procesów, 6 klas priorytetów, 7 relatywnych
priorytetów w obrębie klas
Priorytet domyślny w klasie - normal
Wątek jest wykonywany aż zostanie wywłaszczony przez proces
o wyższym priorytecie, zużyje kwant czasu, wykonuje operację
we-wy lub inne blokujące wywołanie systemowe, bądz
też
zakończy się.
Proces wybrany na ekranie ma zwiększany trzykrotnie kwant
czasu