1

BLOKADY W

BLOKADY W

SYSTEMACH

SYSTEMACH

OPERACYJNYCH

OPERACYJNYCH

Jerzy Peja

Politechnika Szczeci ska

Wydział Informatyki

ul. ołnierska 49, 71-210 Szczecin

2

Agenda

Model systemu
Warunki powstawania blokady
Metody obsługi blokad
Zapobieganie blokadom
Unikanie blokad
Wykrywanie blokad
Wychodzenie z blokad
Ł czone podej cie do obsługi blokady

2

3

Deklaracja

Przy opracowywaniu niniejszego wykładu korzystano

z ogólnodost pnych slajdów do ksi ki

Podstawy

systemów operacyjnych (A. Silberschatz, P.B. Galvin,

G. Gagne) oraz do wykładów

Systemy operacyjne

(Jerzy Brzezi ski i Dariusz Wawrzyniak),

udost pnionych w ramach

Uczelni On-line

4

Problem blokady

Stan blokady: ka dy proces w zbiorze procesów czeka na

zdarzenie, które mo e by spowodowane tylko przez inny proces z

tego samego zbioru (zdarzeniem mo e by przydział lub

zwolnienie zasobu).
Przykład

W systemie s dwie stacje ta mowe
Ka dy z procesów P

1

i P

2

ma jedn ta m i czeka na drug .

Przykład

Semafory A i B maj warto 1

P

0

P

1

wait (A);

wait(B)

wait (B);

wait(A)

3

5

Przykład przejazdu przez most

Ruch tylko w jednym kierunku.
Ka dy odcinek mostu mo e by uwa any za zasób.
Je li wyst pi blokada, to mo na j rozwi za wtedy, gdy

jeden samochód cofnie si (wywłaszczy zasób i ponowi

prób ).
Kilka samochodów mogłoby by zablokowanych, je li

wyst pi blokada.
Mo liwe jest zagłodzenie.

6

Model systemu

Typy zasobów R

1

, R

2

, . . ., R

m

cykle CPU, przestrze pami ci, urz dzenia I/O

Ka dy zasób typu R

i

wyst puje W

i

egzemplarzach.

Klasyfikacja zasobów z punktu widzenia problemu blokady:

zasoby odzyskiwalne (zwrotne, trwałe, ang. reusable resources)
zasoby nieodzyskiwalne (zu ywalne, niezwrotne, ang. consumable

resources)

4

7

Zasoby odzyskiwalne

W stosunku do zasobów odzyskiwalnych u ywa si te terminu

szeregowozwrotne (ang. serially reusable), w celu podkre lenia, e

zasób mo e by wykorzystywany przez wiele procesów, ale nie w

tym samym czasie.
Liczba jednostek zasobów odzyskiwalnych jest ustalona.
Zasoby odzyskiwalne po ich zwolnieniu przez jaki proces mog

zosta ponownie u yte przez inny proces.
Ka dy proces korzysta z zasobu w nast puj cy sposób:

zamówienie (ewentualnie oczekiwanie na realizacj )
u ycie - korzystanie z zasobu (jego przetrzymywanie)
zwolnienie - oddanie zasobu do systemu

Przykłady zasobów odzyskiwalnych: procesor, pami , kanał

wej cia-wyj cia.

8

Zasoby nieodzyskiwalne

Jednostki zasobu nieodzyskiwalnego s tworzone przez jaki

proces, a nast pnie zu ywane (tym samym usuwane) przez inny

proces.
Nie ma ograniczenia na liczb tworzonych jednostek zasobu.
Liczba aktualnie dost pnych jednostek jest sko czona i mo e si

zmienia w czasie w wyniku zmian stanu systemu.
Przykłady zasobów nieodzyskiwalnych: kod znaku z klawiatury,

sygnał lub komunikat przekazany do procesu.

5

9

Korzystanie z zasobów nieodzyskiwalnych

Proces ubiega si o dowolny egzemplarz zasobu

nieodzyskiwalnego według nast puj cego schematu:

zamówienie (ewentualnie oczekiwanie na realizacj )
zu ycie — wykorzystanie zasobu (jego usuni cie)

Proces mo e wyprodukowa i przekaza zasób do systemu

10

Warunki powstawania blokady

Wzajemne wykluczanie: tylko jeden proces mo e u ywa zasobu

w danym czasie
Przetrzymywanie i oczekiwanie: proces przetrzymuj cy co

najmniej jeden zasób czeka na przydział dodatkowych zasobów

b d cych w posiadaniu innych procesów
Brak wywłaszczania: zasoby nie podlegaj wywłaszczaniu.
Cykliczne oczekiwanie: istnieje zbiór czekaj cych procesów {P

0

,

P

1

, ..., P

n

}, takich e P

0

czeka na zasób przetrzymywany przez P

1

,

P

1

czeka na zasób przetrzymywany przez P

2

, ..., P

n

czeka na zasób

przetrzymywany przez P

0

.

Warunki 4 implikuje 2, wi c podane warunki nie s niezale ne.

Blokada mo e powsta wtedy i tylko wtedy, gdy w systemie

s spełnione równocze nie cztery warunki:

6

11

Graf przydziału zasobów

Graf skierowany jest zbiorem wierzchołków V i

kraw dzi E:
V składa si z dwóch podzbiorów:

P = {P

1

, P

2

, …, P

n

}, - zbiór zawieraj cy wszystkie procey w

systemie.
R = {R

1

, R

2

, …, R

m

}, zbiór składaj cy si ze wszystkich

typów zasobów w systemie.

Kraw d dania – skierowana kraw d P

1

→ R

j

Kraw d przydziału – skierowana kraw d R

j

→ P

i

12

Graf przydziału zasobów - oznaczenia

Proces

Typ zasobu z czterema egzemplarzami

P

i

da egzemplarza R

j

P

i

posiada (przetrzymuje) egzemplarz R

j

P

i

P

i

R

j

R

j

7

13

Przykład grafu przydziału zasobów

14

Przykład grafu przydziału zasobów z blokad

8

15

Przykład grafu przydziału zasobów z cyklem,

ale bez blokady

16

Podstawowe fakty

Je li graf nie zawiera cyklu

nie ma blokady.

Je li graf zawiera cykl

je li zasoby s w jednym egzemplarzu, to blokada,
je li zasoby s w wielu egzemplarzach, to istnieje

mo liwo blokady.

9

17

Metody post powania z blokadami

Zapewni , e system nigdy nie wejdzie w stan blokady.

Pozwoli na wej cie systemu w stan blokady, po czym j

usun .

Zignorowa problem i udawa , e system nigdy nie wejdzie

w stan blokady; stosowane przez wi kszo systemów

operacyjnych, w tym Unix.

18

Zapobieganie blokadom

Wzajemne wykluczanie - nie jest wymagane dla

zasobów dzielonych; musi zachodzi dla zasobów

niepodzielnych.
Przetrzymywanie i oczekiwanie - trzeba

zagwarantowa , e gdy proces da zasobu, to nie

posiada innych zasobów

mo na wymaga , by proces zamawiał i dostawał wszystkie

swoje zasoby zanim rozpocznie działanie lub dał zasobów

wtedy, gdy nie posiada adnych innych
niskie wykorzystanie zasobów, mo liwo zagłodzenia

Nadzorowanie sposobu w jaki mo e by

zrealizowane danie

10

19

Zapobieganie blokadom

Brak wywłaszczania:

Je li proces b d cy w posiadaniu zasobów da zasobu,

którego nie mo na natychmiast przydzieli , to musi zwolni

wszystkie posiadane zasoby
Wywłaszczone zasoby dodaje si do listy zasobów, na które

czeka proces
Proces zostanie wznowiony, gdy b dzie mógł odzyska

posiadane wcze niej zasoby oraz otrzyma nowo dany zasób

Cykliczne oczekiwanie - narzuca si uporz dkowanie

całkowite wszystkich typów zasobów i wymaga, by proces

zamawiał zasoby we wzrastaj cym porz dku ich numerów

20

Unikanie blokad

Wymaga, aby system posiadał pewn informacj o przyszłym

zapotrzebowaniu na zasoby

W najprostszym modelu wymaga si , by proces deklarował

maksymaln liczb zasobów ka dego typu, których b dzie

potrzebował.
Algorytm unikania blokady dynamicznie bada stan przydziału

zasobów, by zapewni , e nigdy nie dojdzie do cyklicznego

oczekiwania
Stan przydziału zasobów jest okre lony przez liczb dost pnych i

przydzielonych zasobów oraz przez maksymalne zapotrzebowanie

procesów

11

21

Stan bezpieczny

Stan bezpieczny - kiedy proces da dost pnego zasobu, to

system musi ustali , czy natychmiastowy przydział zasobu

zachowa bezpieczny stan systemu
System jest w stanie bezpiecznym, gdy istnieje bezpieczna

sekwencja procesów.
Sekwencja <P

1

, P

2

, ..., P

n

> jest

bezpieczna, je li dla ka dego P

i

jego potencjalne zapotrzebowanie na zasoby mo na zaspokoi

przez bie co dost pne zasoby oraz zasoby b d ce w posiadaniu

procesów P

j

, gdzie j<i.

Je li dane przez P

i

zasoby nie s natychmiast dost pne, to P

i

mo e

czeka a wszystkie procesy P

j

(j<i) zostan zako czone.

Gdy P

j

ko czy si , to P

i

mo e otrzyma potrzebne zasoby, wykona

si , zwróci przydzielone zasoby i zako czy si .
Gdy P

i

ko czy si , P

i+1

mo e otrzyma dane zasoby, itd.

22

Podstawowe fakty

Je li system jest w stanie bezpiecznym

nie ma blokady.

Je li system nie jest w stanie bezpiecznym

istnieje

mo liwo powstania blokady

Mo na unika blokady zapewniaj c, e system nigdy nie

wejdzie do stanu niebezpiecznego

12

23

Stan bezpieczny, zagro ony i blokady

24

Algorytm grafu przydziału zasobów

Dla zasobów wyst puj cych pojedynczo:

Kraw d deklaracji P

i

→ R

j

wskazuje, e proces P

i

mo e

z da zasobu Z

k

; reprezentowana lini przerywan .

Kraw d deklaracji przechodzi na kraw d

dania, gdy

proces za da zasobu.
W chwili zwolnienia zasobu kraw d przydziału przechodzi

na kraw d deklaracji.
Trzeba a priori zadeklarowa zapotrzebowanie na zasoby
Koszt algorytmu szukania cyklu w grafie zasobów: n

2

.

13

25

Graf przydziału zasobów w przypadku unikania

blokady

26

Stan zagro enia w grafie przydziału zasobów

14

27

Algorytm bankiera

Dla zasobów wielokrotnych
Ka dy proces musi a priori zło y maksymalne

zapotrzebowanie na zasoby
Proces daj cy zasobu by mo e b dzie musiał czeka ,

mimo e zasób jest dost pny
Gdy proces dostanie wszystkie potrzebne zasoby, to

zwróci je w sko czonym czasie
Koszt stwierdzenia czy stan jest bezpieczny: m x n

2

28

Struktury danych algorytmu bankiera

Dost pne: Wektor o rozmiarze m; je li Dost pne[j] = k, to

jest dost pnych k egzemplarzy zasobu typu R

j

.

Max: macierz (n x m); je li Max [i,j] = k, wtedy proces P

i

mo e za da co najwy ej k egzemplarzy zasobu typu R

j

.

Przydzielone: macierz (n x m); je li Przydzielone[i,j] = k, to

P

i

przydzielono aktualnie k egzemplarzy typu R

j

.

Potrzebne: macierz (n x m); je li Potrzebne[i,j] = k, to aby

zako czy swoje zadanie proces P

i

mo e potrzebowa

jeszcze k egzemplarzy typu R

j

.

Potrzebne [i,j] = Max[i,j] – Przydzielone [i,j].

Let

n

= number of processes, and

m

= number of resources types.

15

29

Algorytm bezpiecze stwa

1. Niech

Praca i Koniec b d wektorami

odpowiednio o długo ci m i n. Zainicjujmy:

Praca = Dost pne
Koniec[i] = false dla i = 1,2, …, n.

2. Znajd takie i, e zachodz oba warunki:

(a)

Koniec[i] = false

(b)

Potrzebne

i

≤ Praca

Je li nie istnieje takie i, przejd

do kroku

4.

3.

Praca = Praca + Przydzielone

i

Koniec[i] = true

Przejd do kroku 2.

4. Je li

Koniec[i] == true dla ka dego i, to

system znajduje si w stanie bezpiecznym.

30

Algorytm dania zasobu dla procesu P

i

dane

i

= wektor dania P

i

. If dane

i

[j] = k, to wtedy proces P

i

chce otrzyma k egzemplarzy zasobu typu R

j.

1. Je li dane

i

≤ Potrzebne

i

, to przejd do kroku 2. W przeciwnym

przypadku zgło wyst pienie bł du, poniewa proces przekroczył

deklarowane maksimum.

2. Je li dane

i

≤ Dost pne, to przejd do kroku 3. W przeciwnym

przypadku P

i

musi czeka , poniewa zasoby nie s dost pne.

3. System próbuje przydzieli

dane zasoby procesowi P

i

zmieniaj c stan

w nast puj cy sposób:

Dost pne = Dost pne -

dane

i

;

Przydzielone

i

= Przydzielone

i

+ dane

i

;

Potrzebne

i

= Potrzebne

i

–

dane

i;;

•

Je li stan jest bezpieczny

zasoby s przydzielane procesowi P

i

.

•

Je li stan nie jest bezpieczny

P

i

musi czeka i odtwarzany jest

poprzedni stan przydziału zasobów.

16

31

Przykład algorytmu bankiera

5 procesów (od P

0

do P

4

); 3 typy zasobów: A (10 egzemplarzy),

B (5 egzemplarzy), i C (7 egzemplarzy).
Sytuacja chwili T

0

:

Przydzielone Max

Dost pne

A B C

A B C

A B C

P

0

0 1 0

7 5 3

3 3 2

P

1

2 0 0

3 2 2

P

2

3 0 2

9 0 2

P

3

2 1 1

2 2 2

P

4

0 0 2

4 3 3

32

Przykład (c.d.)

Zawarto macierzy Potrzebne jest definiowana jako

Max –

Przydzielone.

Potrzebne

A B C

P

0

7 4 3

P

1

1 2 2

P

2

6 0 0

P

3

0 1 1

P

4

4 3 1

System jest w stanie bezpieczny, poniewa ci g procesów

<P

1

, P

3

, P

4

, P

2

, P

0

> spełnia kryterium bezpiecze stwa.

17

33

Przykład: proces

P

1

da (1,0,2)

Sprawd , czy dane

≤ Dost pne (tj. czy (1,0,2) ≤ (3,3,2) true).

Przydzielone Potrzebne Dost pne

A B C

A B C

A B C

P

0

0 1 0

7 4 3

2 3 0

P

1

3 0 2

0 2 0

P

2

3 0 1

6 0 0

P

3

2 1 1

0 1 1

P

4

0 0 2

4 3 1

Wykonanie algorytmu bezpiecze stwa pokazuje, e ci g <P

1

, P

3

,

P

4

, P

0

, P

2

> spełnia wymagania bezpiecze stwa.

Czy danie przez proces P

4

przydziału (3,3,0) mo e by

zrealizowane?
Czy danie przez proces P

0

przydziału (0,2,0) mo e by

zrealizowane?

34

Wykrywanie blokady

Dopuszcza si wej cie systemowi w stan blokady

Algorytm wykrywania blokady

Schemat wychodzenia z blokady.

18

35

Pojedyncze zasoby ka dego typu zasobu

Utrzymuje si graf oczekiwa :

w zły odpowiadaj procesom.
P

i

→ P

j

je li P

i

oczekuje na P

j

.

Okresowo wykonuje si algorytm szukania cyklu w grafie.

Algorytm wykrywania cyklu w grafie wymaga n

2

operacji,

gdzie n jest liczb wierzchołków w grafie.

36

Graf przydziału zasobów i graf oczekiwa

Resource-Allocation Graph

Corresponding wait-for graph

19

37

Zasoby wielokrotne

Dost pne: wektor o długo ci m, okre laj cy liczb

dost pnych zasobów ka dego typu.

Przydzielone: macierz (n x m) okre la liczb zasobów

ka dego typu aktualnie przydzielonych ka demu procesowi.

dane: macierz (n x m), okre laj ca bie ce danie

ka dego procesu; je li dane[I, j] = k, to proces P

i

da

dodatkowego przydziału

k egzemplarzy typu R

j

.

38

Algorytm wykrywania blokady

1. Niech Praca i Koniec b d wektorami o rozmiarach odpowiednio

m i n. Pocz tkowo:

(a) Praca = Dost pne
(b) dla i = 1,2, …, n, je li Przydzielone

i

≠ 0, to

Koniec[i] = false; w przeciwnym przypadku, Koniec[i] = true.

2. Znajd taki indeks i, e spełnione s oba warunki:

(a) Koniec[i] == false
(b)

dane

i

≤ Praca

Je li nie ma takiego i, to przejd do kroku 4.

20

39

Algorytm wykrywania blokady (c.d.)

3.

Praca = Praca + Przydzielone

i

Koniec[i] = true

przejd do kroku 2.

4. Je li Koniec[i] == false, dla pewnego takiego, e 1

≤ i ≤ n, to

system jest w stanie blokady. Co wi cej, je li Koniec[i] == false,

to P

i

jest zablokowany.

Zło ono

algorytmu wykrywania, czy system jest w stanie

zablokowanym jest klasy O(

m

x

n

2

).

40

Przykład algorytmu wykrywania blokad

5 procesów (od P

0

do P

4

); 3 typy zasobów: A (7 egzemplarzy),

B (2 egzemplarze), i C (6 egzemplarzy).
Sytuacja chwili T

0

:

Przydzielone

dane

Dost pne

A B C

A B C

A B C

P

0

0 1 0

0 0 0

0 0 0

P

1

2 0 0

2 0 2

P

2

3 0 3

0 0 0

P

3

2 1 1

1 0 0

P

4

0 0 2

0 0 2

Ci g <P

0

, P

2

, P

3

, P

1

, P

4

> dla ka dego

i daje Koniec[i] = true.

21

41

Przykład algorytmu wykrywania blokad (c.d.)

P

2

da kolejnego egzemplarza typu C.

dane

A B C

P

0

0 0 0

P

1

2 0 1

P

2

0 0 1

P

3

1 0 0

P

4

0 0 2

Czy system jest bezpieczny?

Mo na odebra zasoby przetrzymywane przez proces P

0

, ale i tak nie

ma wystarczaj cych zasobów do zaspokojenia da innych

procesów.
Istnieje blokada, w której tkwi procesy P

1

, P

2

, P

3

, i P

4

.

42

Stosowanie algorytmów wykrywania blokady

Kiedy i jak cz sto wywoływa algorytm wykrywania

blokady zale y od:

Jak cz sto jest prawdopodobne wyst pienie blokady?
Jak wiele procesów nale y wyprowadzi ze stanu

blokady?

•

Jeden dla ka dego oddzielnego cyklu

Je li algorytm wykrywania blokady jest wykonywany w

dowolnych chwilach, to w grafie zasobów mo e powsta

wiele cykli. W ogólnym przypadku po ród wielu

zablokowanych procesów wskazanie „sprawcy” blokady

mo e okaza si niewykonalne.

22

43

Wychodzenie z blokady: zako czenie procesu

Usuni cie wszystkich wykonywanych procesów tkwi cych w

blokadzie.

W danej chwili usun jeden proces, a do wyeliminowania cyklu

blokady.

W jakiej kolejno ci powinny by usuwane procesy?

Priorytet procesu.
Jak długo proces wykonywał ju obliczenia oraz ile czasu potrzeba

mu do zako czenia przydzielonej mu pracy.
Jakie zasoby s przydzielone procesowi?
Ile zasobów potrzebuje proces do zako czenia działania?
Ile procesów trzeba b dzie zako czy ?
Czy proces jest interakcyjny czy wsadowy?

44

Wychodzenie z blokady: wywłaszczanie

zasobów

Wybranie ofiary – minimalizacja kosztu.

Wycofanie i wznowienie procesu – powrót do pewnego stanu

bezpiecznego i ponowne uruchomienie procesu w tym stanie.

Zagłodzenie – te same procesy mog by zawsze wybierane jako

ofiary; nale y zadba , aby proces był ofiara tylko sko czona

(mał ) liczb razy; przy ocenie kosztów wywłaszczania nale y

uwzgl dni liczb wycofa i ponowie .

23

45

Ł czone podej cie do post powania

z blokadami

Ł czone s trzy podstawowe podej cia

zapobieganie
unikanie
wykrywanie

pozwalaj ce na zastosowanie optymalnego podej cia dla ka dego

z zasobów w systemie.

Podział zasobów na hierarchicznie uporz dkowane klasy.

U ycie najbardziej odpowiednich technik do obsługi blokad w

ramach ka dej z klas.

46

Korek w ruch drogowym: wiczenie domowe

24

DZI KUJ PA STWU

DZI KUJ PA STWU

Je li s pytania, to z

Je li s pytania, to z

przyjemno ci na nie

przyjemno ci na nie

odpowiemy

odpowiemy