SYSTEMY OPERACYJNE

PROCESY I WĄTKI

2

PROCESY I WĄTKI

Proces

to

program,

który

jest

wykonywany.
Procesem jest program użytkownika,
zadanie

systemowe

(spooling,

przydział pamięci itp.).

Program jest bierny, jest zbiorem
bitów przechowywanych na dysku.

Program nie jest procesem.

Proces jest aktywny, dla procesu
licznik rozkazów wskazuje następną
instrukcję do wykonania. Wykonanie
procesu musi przebiegać w sposób

sekwencyjny

.

3

PROCESY I WĄTKI

Każdy proces ma:

-licznik instrukcji,

-stos,

-segment kodu,

-segment danych.

4

PROCESY I WĄTKI

System operacyjny odpowiada za
wykonywanie następujących
czynności:



tworzenie i usuwanie procesów,

 wstrzymywanie i wznawianie procesów,

 dostarczanie mechanizmów komunikacji

procesów,

 dostarczanie mechanizmów obsługi blokad.

   

5

PROCESY I WĄTKI

Proces stanowi jednostkę pracy w systemie.

Na system składają się:

 procesy systemu operacyjnego (wykonują
kod systemu),

 procesy użytkowników (wykonują kod
programów użytkowników).

Pseudoparalelizm - w systemie z podziałem
czasu (jednoprocesorowym) w każdej chwili
wykonuje się tylko jeden proces, ale z uwagi
na przełączanie powstaje wrażenie
równoczesnej pracy wielu procesów.

6

PROCESY I WĄTKI

Blok kontrolny procesu (Process Control Block) -
reprezentuje

proces w systemie

:

 stan procesu,

 numer procesu (identyfikator),

 licznik rozkazów, stosu,

 rejestry,

 informacje o pamięci zajętej przez proces,

 wykaz otwartych plików,

 informacja o planowaniu przydziału
procesora,

 informacja o wykorzystanych zasobach

(rozliczanie).

7

PROCESY I WĄTKI

Stan procesu:

nowy

-

proces

został

utworzony,

gotowy

-

proces

czeka

na

przydział

procesora,

wykonywany

- proces wykonuje

instrukcje,

(aktywny – po przydzieleniu procesora

przez planistę)

oczekujący

-

proces

czeka

na

wystąpienie

jakiegoś zdarzenia

(np. zakończenia operacji we-wy),

zakończony

-

proces

zakończył

działanie.

8

PROCESY I WĄTKI

9

PROCESY I WĄTKI

Tworzenie procesu

:

 za pomocą funkcji systemowej (np. fork() w
UNIX),

 proces utworzony przez inny proces
(macierzysty,

rodzic) nazywamy

potomnym,

 potomek uzyskuje nową pulę zasobów (od
SO) lub korzysta z zasobów rodzica (mniejsze
przeciążenie systemu).
 

Zakończenie procesu

:

 po ostatniej instrukcji,

 specjalna funkcją (np. exit() w UNIX),

 na żądania rodzica (abort() – np. po
przekroczeniu limitu zasobów),

 niekiedy: zakończenie kaskadowe: po
zakończeniu

rodzica procesy potomne są

kończone lub adoptowane przez inne procesy.

10

PROCESY I WĄTKI

Proces

macierzysty

i

potomny

mogą

wykonywać się współbieżnie.
Proces potomny często jest powoływany do
realizacji jakiegoś zadania dla procesu
macierzystego (wówczas czeka on na
zakończenie procesu potomnego.

Np. w Uniksie:
nowy proces – wywołanie systemowe

fork

– jest to

kopia procesu macierzystego

(wykonuje ten sam

program, z tego samego punktu i przy tym samym
stanie pamięci);
jeżeli ma wykonać inny program – polecenie

exec

:

załadowanie nowego programu do przestrzeni
adresowej procesu i rozpoczęcie wykonywania go);
zakończenie procesu –

exit

: system przekazuje

informację

procesowi

macierzystemu

(który

oczekiwał na to, wywołując funkcję

wait

) i zwalnia

zasoby przydzielone potomkowi.

11

PROCESY I WĄTKI

Relacje pomiędzy procesami

a) procesy niezależne:

 stan procesu nie jest współdzielony z innymi

procesami,

 wykonanie procesu jest zdeterminowane (wynik

zależy tylko od stanu początkowego),

 wykonanie procesu jest powtarzalne,

 zatrzymanie procesu (stop i restart) nie powoduje

żadnych zmian w wykonywaniu procesu.

b) procesy współpracujące:

 stan procesu

może być współdzielony z innymi

procesami,

 wyniku

wykonania

procesu

nie

można

przewidzieć,

gdyż

zależy

od

wykonywanej

sekwencji działań,

 wynik jest niedeterministyczny (nawet przy tych

samych danych wejściowych),

12

PROCESY I WĄTKI

Wątek

sterowania to

sekwencja instrukcji

(tzw.

lekki proces) działający w tej samej wirtualnej
przestrzeni adresowej, co tworzący go (ciężki)
proces.

Stan wątku jest zdefiniowany przez małą,
odrębną ilość danych (własny stan rejestrów i
stos).

Każdy wątek ma oddzielne rejestry i stos
wywołań, współdzieli natomiast w ramach tego
samego procesu segment danych, segment
kodu, tablicę otwartych plików, itp.

13

PROCESY I WĄTKI

Cechy wątków:

 każdy wątek jest wykonywany sekwencyjnie,

 każdy wątek posiada własny licznik rozkazów i

stos,

 wątki dzielą czas procesora tak, jak procesy,

 w systemie wieloprocesorowym wątki mogą

być

wykonywane równolegle,

 stan wątku jest definiowany małą ilością

danych,

 wątek ma te same podstawowe cechy co

proces
(stany, możliwość tworzenia wątków
potomnych,

korzystania z urządzeń

zewnętrznych, itd...).

 między wątkami tego samego procesu nie ma

ochrony pamięci (nie jest możliwa i nie jest
potrzebna),

 wątki ze sobą współpracują, a nie

współzawodniczą

(tak jak procesy).

14

PROCESY I WĄTKI

Tradycyjny proces (ciężki) jest równoważny
zadaniu
z jednym wątkiem.

W zadaniu złożonym z wielu wątków podczas
zablokowania jednego wątku może się
wykonywać inny wątek tego zadania;
współpraca wielu wątków w tym samym
zadaniu pozwala zwiększyć przepustowość i
poprawić wydajność.

Wątki umożliwiają połączenie równoległości
z sekwencyjnym wykonaniem:

(1) model dyspozytor - pracownik
(2) model zespołu
(3) model potoku

15

PROCESY I WĄTKI

Zalety

stosowania wątków:

 tańsze powołanie wielu wątków niż
utworzenie wielu procesów,

 przełączanie procesora między wątkami jest
łatwiejsze (szybsze) niż między zwykłymi
(ciężkimi) procesami,

 lepsze wykorzystanie zasobów systemu
komputerowego,

 nieograniczone współdzielenie danych
procesu przez wątki;

 lepsza realizacja przetwarzania
współbieżnego na maszynach o pamięci
współdzielonej.

Wątek, to podstawowa jednostka wykorzystania
procesora.

16

PROCESY I WĄTKI

Problemy

stosowania wątków:

 przy blokowanych odwołaniach wątków do
systemu – proces nie może oddać sterowania
systemowi, musi

czekać na swoje wątki;

 aby sprawdzić, czy odwołania wątków będą
blokować system używa się kodu
sprawdzającego (jacket) (wątków używa się
głównie w zadaniach z blokującymi
odwołaniami w celu poprawy wydajności);

 ponieważ nie ma wywłaszczania, zatem wątki
muszą same oddawać sterowanie procedurze
wykonawczej procesu.

17

PROCESY I WĄTKI

Jądro nie jest procesem, ale zarządcą
procesów.
Oprócz procesów użytkownika istnieje
kilka uprzywilejowanych procesów
zwanych

wątkami jądra

, które:

 działają w trybie jądra (w przestrzeni
adresowej jądra)

 nie komunikują się z użytkownikami
(nie trzeba terminali)

 tworzone są w chwili startu systemu i
działają do czasu wyłączenia systemu.

18

PROCESY I WĄTKI

Zmiana trybu pracy zachodzi, gdy:

 proces wywołuje funkcję systemową;

 CPU wykonujący proces sygnalizuje

wyjątek

, np. wykonanie nieprawidłowej

instrukcji; jądro obsługuje wyjątek na
rzecz procesu, który go spowodował;

 urządzenie zewnętrzne zgłasza
procesorowi

sygnał przerwania

, np.

zmiana statusu, zakończenie operacji
we-wy, itp.; 

19

PROCESY I WĄTKI

Urządzenia działają asynchronicznie,
więc przerwania nadchodzą w
nieprzewidywalnych momentach.

Po nadejściu przerwania wykonywany

jest

wątek jądra

. Działa on w trybie

jądra, więc odpowiadający mu program
musi być uważany za część jądra,
chociaż umieszczoną w procesie.

20

KLASYFIKACJA PROCESÓW

Klasyfikacja procesów I:

 związane z urządzeniami I/O (I/O-bound)

 związane z procesorem (CPU-bound).

Klasyfikacja procesów II:

 interaktywne

 wsadowe

 czasu rzeczywistego

21

PLANOWANIE PROCESÓW –

PRZYDZIAŁ PROCESORA

Jedno z podstawowych zadań jądra SO:

przydział procesora

(processes scheduling) –

szeregowanie procesów.

Poziomy szeregowania:

-

wysoki

: szeregowanie zadań – określa się

kolejkę

zadań, do których mają być

przydzielone zasoby

systemu;

-

pośredni

: obsługa procesów w stanie gotowy

– zawieszony;
-

niski

: któremu procesowi w stanie gotowości

ma być

przydzielony procesor.

22

PLANOWANIE PROCESÓW –

PRZYDZIAŁ PROCESORA

Kolejka zadań

(task queue) – zbiór zadań

oczekujących na przydział PAO (wszystkie
procesy systemu).

Kolejka procesów gotowych

(read queue) –

procesy z przydzieloną PAO (gotowe do
wykonania, czekające na przydział procesora).

Kolejka procesów do urządzenia

(device

queue) – procesy oczekujące na operację we /
wy na danym urządzeniu.

Procesy mogą przenosić się pomiędzy
kolejkami.
Decyzja – któremu procesowi ma być
przydzielony procesor.
Inne kolejki – np. oczekiwanie na zdarzenie,
na zakończenie procesu potomnego, itp.

23

PLANOWANIE PROCESÓW –

PRZYDZIAŁ PROCESORA

Algorytmy

przydziału procesora (processes

scheduling) – szeregowania procesów:

Jeśli dwa lub więcej procesów znajdują się w
stanie gotowy do wykonania, to o kolejności
przydziału jednostki centralnej decyduje planista.

Planista

(scheduler) powinien gwarantować:

 sprawiedliwość przydziału CPU,

 dobrą wydajność CPU,

 mały czas odpowiedzi,

 mały czas przetwarzania (turnaround time),

 dużą przepustowość (throughput).

24

PLANOWANIE PROCESÓW –

PRZYDZIAŁ PROCESORA

Planista

(scheduler) jest to proces systemowy:



długoterminowy

(p. zadań) – wybiera kolejne

zadania do załadowania do PAO (wysoki

poziom

szeregowania); steruje poziomem

wieloprogramowości (liczbą procesów
współbieżnych)



krótkoterminowy

(p. procesora) – wybiera

proces spośród procesów gotowych (w pamięci)
i przydziela mu procesor (niski poziom
szeregowania).

Różnica pomiędzy planistami zależy od
częstotliwości ich uaktywnień: p.d. – co kilka
minut, p.k. – co 100 ms.

25

PLANOWANIE PROCESÓW –

PRZYDZIAŁ PROCESORA

Decyzje o przydziale procesora są podejmowane,
gdy:
1. proces przeszedł od stanu aktywności do
stanu

oczekiwania, np. z powodu operacji we/wy

lub czekania na zakończenie procesu
potomnego;
2. proces przeszedł od stanu aktywności do
stanu

gotowości, np. wskutek przerwania;

3. proces przeszedł od stanu oczekiwania do
stanu

gotowości, np. po zakończeniu operacji

we/wy;
4. proces kończy działanie.

Planowanie nazywamy:
w sytuacjach 1 i 4 - niewywłaszczeniowym, a
w sytuacjach 2 i 3 - wywłaszczeniowym.

26

PLANOWANIE PROCESÓW –

PRZYDZIAŁ PROCESORA

Planowanie bez wywłaszczenia - proces używa
procesora tak długo, aż przejdzie w stan
oczekiwania lub zakończenia.

Planowanie z wywłaszczeniami – drogie i
ryzykowne

(może komplikować działania przy

wywołaniach systemowych).

27

PLANOWANIE PROCESÓW –

PRZYDZIAŁ PROCESORA

Ekspedytor

(dyspozytor - dispatcher) – moduł,

który faktycznie przekazuje procesor do
dyspozycji procesu wybranego przez planistę
krótkoterminowego;

Obowiązki ekspedytora to:

 przechowywanie stanu bieżącego procesu,

 przełączanie kontekstu (rejestry, itd.),

 przełączanie systemu do trybu
użytkownika,

 wykonanie skoku do adresu z bloku
kontrolnego

tj. odpowiedniej komórki w programie

użytkownika

w celu wznowienia działania

programu.
Opóźnienie ekspedycji (dispatch latency) to
czas, który ekspedytor zużywa na
wstrzymanie jednego procesu i uaktywnienie
innego (zwykle 1-100 ms).

28

PLANOWANIE PROCESÓW –

PRZYDZIAŁ PROCESORA

Definicje:



Wykorzystanie procesora

(CPU utilization)

–procent czasu, przez który procesor
pozostaje zajęty - najlepiej by było gdyby
procesor był nieustannie zajęty pracą;
- powinno się mieścić od 40% (słabe
obciążenie systemu) do 90% (intensywna
eksploatacja).



Przepustowość

(throughput) - liczba

procesów kończących się w jednosce czasu.

29

PLANOWANIE PROCESÓW –

PRZYDZIAŁ PROCESORA

Definicje cd.:



Czas cyklu przetwarzania

(turnaround

time) – czas między utworzeniem procesu w
systemie a chwilą jego zakończenia
(suma czasów czekania na wejście do
pamięci, czekania w kolejce procesów
gotowych, wykonywania operacji we/wy,
wykonania przez CPU);



Czas oczekiwania

(waiting time) - suma

okresów,
w których proces czeka w kolejce procesów
gotowych do działania.

30

PLANOWANIE PROCESÓW –

PRZYDZIAŁ PROCESORA

Definicje cd.:



Czas odpowiedzi

(response time) - ilość

czasu między wysłaniem żądania a
pojawieniem się odpowiedzi, bez
uwzględnienia czasu potrzebnego
na wyprowadzenie odpowiedzi (np. na ekran):

- czas odpowiedzi jest na ogół uzależniony

od

szybkości działania urządzenia

wyjściowego

- miara zastępująca miarę czasu cyklu
przetwarzania w systemach

interaktywnych.

31

PLANOWANIE PROCESÓW –

PRZYDZIAŁ PROCESORA

Kryteria oceny

algorytmów

przydziału

procesora:



efektywność

(efficiency) – utrzymywanie

obciążenia procesora przez cały czas,



przepustowość

(throughput) –

maksymalizacja liczby zadań wykonywanych
w określonym czasie,



czas obrotu

– czas pobytu w systemie

jednego

procesu,



czas oczekiwania

(waiting time) –

minimalizacja

czasu oczekiwania przez

użytkowników wsadowych na wyniki ich
zadań (kolejka procesów gotowych),



czas odpowiedzi

(response time) –

minimalizacja

czasu odpowiedzi dla

użytkowników interakcyjnych

(z podziałem

czasu).

32

KLASYFIKACJA PROCESÓW

Algorytmy

przydziału procesora dzielą się na:

 algorytmy z wywłaszczeniem – procesor
może być odebrany procesowi w trakcie jego
wykonywania:

przejście procesu ze stanu

oczekiwania do stanu gotowości lub procesu
aktywnego do stanu

gotowości;

 algorytmy bez wywłaszczenia – proces
utrzymuje procesor aż do zakończenia pracy:

przejście procesu aktywnego do stanu oczekiwania
lub zakończenie procesu;

33

PROCESY – PRZYDZIAŁ PROCESORA

Algorytmy przydziału procesora:

 pierwszy nadszedł, pierwszy obsłużony (

FCFS

–first

come first served; FIFO–first in first out), bez

wywłaszczenia.
 wg najkrótszego zadanie (

SJF

- shortest job first),

algorytm optymalny, dający minimalny średni

czas oczekiwania dla określonego zbioru procesów.
 wg stosunku reaktywności (

HRRN

-highest

response

ratio

next)



rotacyjne

(round-robin scheduling) – dla systemów

z podziałem czasu procesora; cykliczna kolejka

procesów;

gdy rośnie t, alg. rotacyjny  alg. FCFS oraz

maleje częstotliwość przełączania procesora, 

wydłuża się czas oczekiwania procesu na procesor;


priorytetowe

(polityka planowania i mechanizm

planowania),

każdy proces ma przydzielony

priorytet (wg wielkości

pamięci, liczby plików,

itp.).

34

PROCESY – PRZYDZIAŁ PROCESORA

FCFS – FIRST COME FIRST SERVED

przydział czasu w kolejności zgłaszania się

procesów

 najprostsza implementacja (kolejka FIFO)

 brak wywłaszczania

 kłopotliwy w systemach z podziałem czasu,

w których ważne jest uzyskiwanie procesora

w regularnych odstępach czasu.

Zalety

:

- sprawiedliwy, niski narzut systemowy;
- nie ma groźby zagłodzenia procesów,

proces

zawsze dostanie się do CPU (po pewnym

czasie).

35

PROCESY – PRZYDZIAŁ PROCESORA

FCFS – FIRST COME FIRST SERVED cd.

Wady

:

- długi średni czas oczekiwania i duża
wariancja czasu oczekiwania,
- niewydajne wykorzystanie CPU (efekt
konwoju -

procesy czekają aż wielki

proces odda procesor),
- krzywdzący dla procesów krótkich (są
wstrzymywane przez procesy długie) oraz
ograniczonych przez we/wy bowiem
faworyzuje dłuższe zadania.

36

PROCESY – PRZYDZIAŁ PROCESORA

FCFS – FIRST COME FIRST SERVED cd.

Przykład:
P1 – 24 ms; P2 – 3 ms, P3 – 3 ms.
Procesy nadchodzą w kolejności: P1, P2, P3:
Diagram Gantta dla FCFS:

Czas oczekiwania dla P1= 0; P2= 24; P3 = 27
Średni czas oczekiwania: (0 + 24 + 27)/3 = 17
ms
Wariancja czasu oczekiwania: (0^2 + 24^2 +
27^2)/3 –17^2 =435 –289 = 146 ms

37

PROCESY – PRZYDZIAŁ PROCESORA

FCFS – FIRST COME FIRST SERVED cd.

Przypuśćmy, że procesy nadejdą w porządku
P2, P3, P1.
Diagram Gantta dla FCFS

Czas oczekiwania dla P1 =6; P2= 0; P3 = 3
Średni czas oczekiwania: (6 + 0 + 3)/3 = 3ms
Średni czas oczekiwania znacznie lepszy.
Dlaczego?

38

PROCESY – PRZYDZIAŁ PROCESORA

SJF- SHORTEST JOB FIRST cd.

[bez wywłaszczenia]



Algorytm wiąże z każdym procesem

długość jego najbliższej fazy procesora.

Procesor jest przydzielany procesowi o

najkrótszej następnej fazie procesora.
Przy równych fazach procesora mamy
FCFS.

 SJF jest

optymalny

(umieszczenie

krótkiego procesu przed długim bardziej
zmniejsza czas oczekiwania krótkiego niż
zwiększa długiego).

 Algorytm może być wywłaszczający -
usuwa proces, jeśli nowy proces w kolejce
procesów gotowych ma krótszą następną
fazę procesora od czasu do zakończenia
danego procesu.

39

PROCESY – PRZYDZIAŁ PROCESORA

SJF- niewywłaszczający

Proces

Czas trwania fazy [ms]

P1

6

P2

8

P3

7

P4

3

Diagram Gantta dla SJF

Średni czas oczekiwania: (3 + 16 + 9 + 0)/4 = 7
ms

40

PROCESY – PRZYDZIAŁ PROCESORA

SRTF- SHORTEST REMAINING TIME
FIRST

[z wywłaszczeniem]



Najpierw zadanie o najkrótszym

pozostałym

czasie fazy procesora.

 Przy pojawieniu się innego procesu o
krótszym
pozostałym czasie następuje
wywłaszczenie.

41

PROCESY – PRZYDZIAŁ PROCESORA

SRTF – Shortest Remaining Time First

Proces

Czas przybycia

Czas trwania

fazy

P1

0

8 ms

P2

1

4

P3

2

9

P4

3

5

Diagram Gantta dla SRTF

Średni czas oczekiwania: [(10-1) + (1-1) + (17-
2) + (5-3)]/4 = 26/4=6.5

42

PROCESY – PRZYDZIAŁ PROCESORA

ZADANIE:

Proces

Czas przybycia

Czas trwania

fazy

P1

0

8 ms

P2

2

5

P3

4

1

P4

5

2

Narysować diagramy Gannta i policzyć średnie
czasy oczekiwania dla algorytmów:

a) SJF oraz
b) SRTF.

Uzasadnić wyniki; który z ww. algorytmów jest
optymalny?

43

PROCESY – PRZYDZIAŁ PROCESORA

PLANOWANIE METODĄ HRRN

Stosunek reaktywności:

R = 1+ w/t

, gdzie

w

oznacza czas oczekiwania

na

procesor zaś

t

-fazę procesora

 Największy stosunek reaktywności jako

następny

(ang. highest response ratio

next -HRRN);

 Faworyzuje krótkie zadania, lecz po

pewnym czasie

oczekiwania dłuższy proces

uzyska CPU;

 Podobnie jak SJF i SRTF również algorytm

HRRN

wymaga oszacowania dla następnej fazy

procesora;

44

PROCESY – PRZYDZIAŁ PROCESORA

PLANOWANIE METODĄ HRRN cd.

Proces

Czas przybycia

Czas trwania fazy

P1

0

8

P2

1

4

P3

2

9

P4

3

5

Diagram Gantta dla HRRN (niewywłaszczający)

Średni czas oczekiwania: (0 + (8-1)+ (17-2) + (12-3))/4 =

31/4=7.75

45

PROCESY – PRZYDZIAŁ PROCESORA

PLANOWANIE METODĄ HRRN cd.

 Faworyzuje krótkie zadania jednak
oczekiwanie dłuższych zadań zmienia ich
współczynnik i w konsekwencji pozwala im
uzyskać dostęp do CPU;

 Ma dobry czas odpowiedzi;

 Nie ma groźby zagłodzenia procesów

(proces zawsze dostanie się do CPU (po

pewnym czasie);

46

PROCESY – PRZYDZIAŁ PROCESORA

WYZNACZANIE NASTĘPNEJ FAZY
PROCESORA

 SJF jest optymalny: daje minimalny średni

czas oczekiwania dla danego zbioru procesów;
 Nie ma sposobu na poznanie długości

następnej fazy, możemy ją jedynie oszacować;
 Można tego dokonać wyliczając średnią

wykładniczą poprzednich faz procesora;

t(n) = długość n-tej fazy procesora

a -liczba z przedziału [0,1], zwykle 0.5

Definiujemy średnią wykładniczą jako:

gdzie s(n+1) = przewidywana długość

następnej fazy.

47

PROCESY – PRZYDZIAŁ PROCESORA

WYZNACZANIE NASTĘPNEJ FAZY
PROCESORA

 a=0

s(n+1) = s(n)  niedawna historia nie ma

wpływu

 a=1

s(n+1) = t(n)  jedynie najnowsze

notowanie

długości fazy ma wpływ

a*(1-a) ≠ 0 i rozwiniemy wzór to:

Ponieważ a i (1-a) są mniejsze od 1 to starsze

składniki (przeszłość) mają coraz mniejszą

wagę.

48

PROCESY – PRZYDZIAŁ PROCESORA

PLANOWANIE ROTACYJNE (round robin)

 ustala się kwant czasu (10-100 ms);

 kolejka procesów jest traktowana jak

cykliczna

procedura FIFO;

 algorytm przegląda kolejkę i kolejno

przydziela każdemu procesowi kwant

czasu (jeśli proces się

w nim nie

zakończy – wraca do kolejki a długość

jego fazy procesora zmniejsza się o kwant

czasu);
 algorytm jest wywłaszczający;
 gdy jest N procesów a kwant czasu

wynosi Q,

max. czas oczekiwania może wynieść (N-

1)Q.

49

PROCESY – PRZYDZIAŁ PROCESORA

PLANOWANIE ROTACYJNE cd.

Efekty

:

-

gdy Q rośnie nieograniczenie; planowanie

rotacyjne

 FCFS,

- gdy Q zmierza do 0 zachodzi dzielenie

procesora – każdy proces dysponuje

procesorem o prędkości

1/N rzeczywistego,

- średni czas oczekiwania jest stosunkowo długi.

50

PROCESY – PRZYDZIAŁ PROCESORA

PLANOWANIE ROTACYJNE cd.

średni czas cyklu przetwarzania z kwantem =

6

Proces

Czas trwania fazy

P1

6

P2

3

P3

1

P4

7

Diagram Gantta dla RR(6)

Średni czas cyklu przetwarzania:

(6+9+10+17)/4=42/4=10,5

51

PROCESY – PRZYDZIAŁ PROCESORA

PLANOWANIE ROTACYJNE cd.

średni czas cyklu przetwarzania z kwantem

= 5

Proces

Czas trwania fazy

P1

6

P2

3

P3

1

P4

7

Diagram Gantta dla RR(5)

Średni czas cyklu przetwarzania:

(15+8+9+17)/4=49/4=12,25

52

PROCESY – PRZYDZIAŁ PROCESORA

PLANOWANIE ROTACYJNE cd.

- Dobry czas odpowiedzi dla krótkich
procesów;
- Efektywny w systemach z podziałem czasu;
- Sprawiedliwe traktowanie procesów;
- Kwant powinien być nieco dłuższy od czasu

wymaganego na typową interakcję;

- Procesy ograniczone przez CPU są
faworyzowane kosztem procesów
ograniczonych przez we/wy co prowadzi do
nieefektywnego wykorzystania we/wy;

- Nie powoduje zagłodzenia procesów

53

PROCESY – PRZYDZIAŁ PROCESORA

PLANOWANIE PRIORYTETOWE



szczególnym przypadkiem jest SJF

(priorytet = 1/(długości następnej fazy

procesora),

 zwykle priorytet określa jednak liczba

całkowita

(np. z przedziału [0,7] – im

niższa wartość tym wyższy priorytet),

 proces o niskim priorytecie może się nigdy

nie wykonać; rozwiązanie: postarzanie

procesów (zmniejszenie priorytetu o 1, np. co

10 min.),

 może być wywłaszczające (ale

niekoniecznie),

 określenie priorytetu:

- zewnętrznie - przez funkcję systemową,

- wewnętrznie- przez deklarację samego

procesu.

54

PROCESY – PRZYDZIAŁ PROCESORA

WIELOPOZIOMOWE

PLANOWANIE

KOLEJEK

Wielopoziomowe planowanie kolejek

(mulitilevel queue scheduling ) polega na

tym, że kolejka procesów gotowych zostaje

podzielona na oddzielne (pod)kolejki.

-

procesy pierwszoplanowe (foreground) –

interakcyjne, systemowe;

-

procesy drugoplanowe (background) –

wsadowe.

Każda z kolejek ma swój własny algorytm

szeregujący np.

-

pierwszoplanowa – RR

-

drugoplanowa - FCFS

55

PROCESY – PRZYDZIAŁ PROCESORA

WIELOPOZIOMOWE

PLANOWANIE

KOLEJEK

cd.

Między kolejkami także należy dokonać wyboru

algorytmu planowania.

- planowanie priorytetowe tzn. obsłuż

najpierw

wszystkie procesy pierwszoplanowe potem

drugoplanowe - możliwość zagłodzenia

procesu

drugoplanowego,

- porcjowanie czasu (time slice) - każda

kolejka

otrzymuje pewną porcję czasu

procesora, który

przydzielany jest

każdej z kolejek np.

80% kolejka pierwszoplanowa z

algorytmem RR

20% kolejka drugoplanowa z

algorytmem FCFS

56

PROCESY – PRZYDZIAŁ PROCESORA

WIELOPOZIOMOWE

PLANOWANIE

KOLEJEK cd.

57

PROCESY – PRZYDZIAŁ PROCESORA

WIELOPOZIOMOWE

PLANOWANIE

KOLEJEK

 Kolejki wielopoziomowe z sprzężeniem

zwrotnym (multilevel feedback queue

scheduling) umożliwiają przesuwanie

procesów między kolejkami.

 Proces, który zużywa za dużo procesora,

można zdymisjonować poprzez przesunięcie

go do kolejki

o niższym priorytecie i dzięki temu zapobiec

zagłodzeniu innych procesów.

 Postępowanie takie prowadzi do

pozostawienia procesów ograniczonych przez

we/wy oraz interakcyjnych w kolejkach o

wyższych priorytetach.

58

PROCESY – PRZYDZIAŁ PROCESORA

WIELOPOZIOMOWE

PLANOWANIE

KOLEJEK

59

PROCESY – PRZYDZIAŁ PROCESORA

WIELOPOZIOMOWE

PLANOWANIE

KOLEJEK

 Trzy koleki:

 Q

0

– kwant czasu 8 milisekund

 Q

1

– kwant czasu16 milisekund

 Q

2

– FCFS

 Planowanie:

- Nowe zadanie wchodzi do kolejkiQ

0

obsługiwanej przez FCFS. Zadanie dostaje

8 milisekund; jeśli się nie zmieści w tym

czasie zostaje przeniesione na koniec

kolejki Q

1

.

- W kolejce Q

1

zadanie jest znów

obsługiwane przez algorytm FCFS i dostaje

dodatkowe 16 ms. Jeśli ponownie nie

zmieści się w tym czasie zostaje

wywłaszczone do kolejki Q

2

.

60

PROCESY – PRZYDZIAŁ PROCESORA

WIELOPOZIOMOWE

PLANOWANIE

KOLEJEK

 Algorytm ten daje najwyższy priorytet

procesom o fazie nie większej niż 8ms,

procesy o fazie między 8ms i 24ms są także

szybko obsługiwane; długie procesy

wchodzą do kolejki 2 i są obsługiwane (FCFS)

w cyklach pracy procesora nie

wykorzystanych przez procesy z kolejek 0 i 1.

 Planowanie ze sprzężeniem zwrotnym jest

najogólniejszym i najbardziej złożonym

algorytmem planowania przydziału procesora

61

PROCESY – PRZYDZIAŁ PROCESORA

WIELOPOZIOMOWE PLANOWANIE KOLEJEK

Planista wielopoziomowych kolejek ze

sprzężeniem zwrotnym jest określony za

pomocą następujących parametrów:

 liczba kolejek,

 algorytm planowania dla każdej kolejki,

 metoda użyta do decydowania o

awansowaniu

procesu do kolejki o

wyższym priorytecie,

 metoda użyta do decydowania o

zdymisjonowaniu procesu do kolejki

o niższym

priorytecie,

 metoda wyznaczenia kolejki, do której

trafia

proces potrzebujący obsługi.

62

PROCESY – PRZYDZIAŁ PROCESORA

PLANOWANIE WIELOPROCESOROWE

Planowanie wieloprocesorowe (multiple-

processor scheduling) komplikuje się wraz ze

wzrostem liczby procesorów i ich architektury.

Trudno określić najlepszą metodę planowania.

Procesory mogą być homogeniczne

(identyczne) lub heterogeniczne (różne).

Planowanie wieloprocesorowe heterogeniczne

- na danym procesorze można wykonać

programy, które zostały przetłumaczone na

odpowiadający mu zbiór rozkazów (sieciowe

systemy operacyjne).

63

PROCESY – PRZYDZIAŁ PROCESORA

PLANOWANIE WIELOPROCESOROWE cd.

Planowanie wieloprocesorowe homogeniczne

- dzielenie obciążeń (load sharing) -

wspólna

kolejka dla wszystkich

procesorów;

- każdy procesor sam planuje swoje

działanie,

obydwa operują na tej samej kolejce

procesów

gotowych (ryzykowne -

wymaga bardzo

starannego

zaprogramowania) -

wieloprzetwarzanie symetryczne;

- jeden procesor jest nadrzędny

(master),

inne podporządkowane

(slave) -

wieloprzetwarzanie

asymetryczne.

64

PROCESY – PRZYDZIAŁ PROCESORA

PLANOWANIE

W

CZASIE

RZECZYWISTYM

Rygorystyczne systemy czasu rzeczywistego -

wymóg zakończenia zadania krytycznego w

gwarantowanym czasie

- rezerwacja zasobów (resource

reservation)

gwarantujących

wykonanie zadania,

- planista odrzuca zadanie, jeśli nie może

ich

zarezerwować.

Łagodne systemy czasu rzeczywistego -

procesy o decydującym znaczeniu, mają

priorytet nad słabiej sytuowanymi

- priorytety procesów czasu rzeczywistego

nie mogą maleć z upływem czasu (można

np. zakazać

dymisjonowania

procesów czasu rzeczywistego).

65

PROCESY – PRZYDZIAŁ PROCESORA

PLANOWANIE

W

CZASIE

RZECZYWISTYM cd.

Opóźnienie ekspediowania procesów do

procesora musi być małe, aby proces czasu

rzeczywistego nie musiał czekać (Solaris: bez

wywłaszczeń 100 ms i z wywłaszczeniami

2ms).

- Musimy zezwolić na wywłaszczanie funkcji

systemowych:

- poprzez wstawienie w długotrwałych funkcjach

systemowych punktów wywłaszczeń,

- wywłaszczanie całego jądra, struktury danych

jądra muszą być chronione za pomocą

mechanizmów synchronizacji.

Wysokopriorytetowe procesy nie mogą czekać

na zakończenie niskopriorytetowych;

sytuacja, gdy proces wysokopriorytetowy

czeka na zakończenie procesu o niższym

priorytetcie, nosi nazwę odwrócenia

priorytetów.