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