Stan Bezpieczny

Stan systemu jest bezpieczny, jeśli istnieje porządek, w 

którym system może przydzielić zasoby każdemu 
procesowi (nawet w stopniu maksymalnym), stale 
unikając zakleszczenia.

System jest w stanie bezpiecznym tylko wtedy, gdy istnieje 

ciąg bezpieczny.

Ciąg procesów <P1, P2, …, Pn> jest bezpieczny w danym 

stanie przydziałów, jeśli dla każdego procesu  Pi jego 
potencjalne zapotrzebowanie na zasoby może być 
zaspokojone przez bieżąco dostępne zasoby oraz 
zasoby użytkowane przez wszystkie procesy Pj. Po ich 
zakończeniu proces Pi może otrzymać wszystkie 
potrzebne mu zasoby, dokończyć przewidzianą pracę, 
oddać przydzielone zasoby i zakończyć działanie. Kiedy 
proces Pi będzie zakończony, wtedy niezbędne zasoby 
może otrzymać proces Pi+1 itd. Jeśli żaden taki ciąg 
nie istnieje, to system określa się jako będący w stanie 
zagrożenia.

Stan Bezpieczny

Stan bezpieczny nie jest stanem zakleszczenia.

Zakleszczenie  jest stanem zagrożenia.

Stan zagrożenia może prowadzić do zakleszczenia.

Dopóki stan jest bezpieczny, dopóty system 

operacyjny może unikać stanów zagrożenia ( i 
zakleszczeń).

Zakleszczen

ie

Stan 
zagrożenia

Stan 
bezpieczny

Unikanie zakleszczeń

1. W najprostszym i najbardziej użytecznym modelu 

wymaga się, aby każdy proces deklarował 
maksymalną liczbę zasobów każdego typu, 
których będzie potrzebował:

1.

Algorytm unikania zakleszczeń (deadlock avoidance) 
sprawdza dynamicznie stan przydziału zasobów, aby 
zapewnić, że nigdy nie dojdzie do czekania cyklicznego.

2.

Stan przydziału zasobów jest określony prze liczbę 
dostępnych i przydzielonych zasobów oraz maksymalne 
zapotrzebowanie procesów.

2. Kiedy proces żąda dostępnego zasobu, system 

musi sprawdzić czy natychmiastowe 
przydzielenie tego zasobu zachowa system w 
stanie bezpiecznym.

3.

 

Unikanie zakleszczeń – gwarancja, że nigdy nie 

pojawi się stan zagrożenia.

Likwidowanie zakleszczenia

1. Zakończenie procesu:

1.

Zaniechanie wszystkich zakleszczonych procesów.

2.

Usuwanie procesów pojedynczo, aż do wyeliminowania 
cyklu zakleszczenia.

2. Wywłaszczanie zasobów:

1. Wybór ofiary – minimalizacja kosztów.
2.  Wycofanie – powrót do jakiegoś bezpiecznego stanu z 
którego można będzie go wznowić.
3. Głodzenie – proces mógł być wydelegowany do roli ofiary 
tylko skończoną liczbę razy. 

3.

 

Mieszane metody

Algorytm Grafu Przydziału Zasobów

Metoda wykorzystywana dla zasobów, których 

każdy typ ma pojedynczy egzemplarz.

Dodatkowy typ krawędzi – krawędź deklaracji (Pi -> 

Zj). Oznacza, że proces Pi może zamówić kiedyś 
zasób Zj.

Krawędź deklaracji (linia przerywana)przechodzi w 

krawędź zamówienia, gdy proces zamawia zasób.

Po zwolnieniu zasobu krawędź zamówienia 

przechodzi z powrotem w krawędź deklaracji.

Zamówienie może być spełnione tylko wtedy, gdy 

nie doprowadzi do powstania cyklu w grafie.

Graf przydziału zasobów, graf oczekiwania

Algorytm Bankiera

Sytuacja analogiczna do banku, który nie 

zainwestuje gotówki tak, aby uniemożliwić 
zaspokojenie wymagań wszystkich jego 
klientów).  Algorytm służy do sprawdzenia, czy 
stan jest bezpieczny.

1. 

Proces przy wejściu do systemu deklaruje 

maksymalną liczbę egzemplarzy każdego zasobu, które 
będzie potrzebował.

2. Przy zamawianiu zasobów przez użytkownika, 
system określa, czy ich przydzielenie pozostawi system 
w stanie bezpiecznym:

- przy odpowiedzi pozytywnej – zasoby są 

przydzielane,

- w przypadku odpowiedzi negatywnej – proces musi 

czekać.

Algorytm Bankiera

Do zaimplementowania algorytmu potrzebne są 

następujące struktury:

dostępne:

wektor określający liczbę dostępnych zasobów Z(i): 

D[i])

,

 

maksymalne:

macierz określająca maksymalne żądania każdego 

procesu P(j):  

Max[j,i]

,

przydzielone:

macierz  określająca  liczbę  zasobów  każdego  typu 

Z(i), 

przydzielonych  do  każdego  z  procesów  P(j): 

Pd[j,i]

,

potrzebne:

macierz  określająca  pozostałe  do  spełnienia 

zamówienia 

każdego z procesów: 

Pt[j,i]

.

Pt[j,i] 

= 

Max[j,i]

  - 

Pd[j,i]

 

koniec:

wektor K[j] o wartościach true, gdy proces P(j) może 

być 

zakończony  w  dotychczasowej  konfiguracji 

przydziałów, 

robocze:

wektor R(i) o wartościach odpowiadających liczbie

zasobów 

Z(i) 

dostępnych 

po 

zakończeniu 

wszystkich

procesów, dla których K[i] = true.

Algorytm Bankiera

1. Wypełnij tablicę K wartościami false, a tablicę R zawartością 

tablicy D.

2. Znajdź takie j, że:

-  K[j] = false
-  Pt[j]  R      j – nr kolejnego procesu dodawanego na 
końcu już 

skonstruowanego ciągu 

bezpiecznego.

3. Jeżeli nie ma takiego j, to idź do kroku 6.

4. Jeżeli jest takie j, to:

- R = R + Pd[j]
- K[j] = true

po dodaniu procesu P(j) do 

konstruowanego ciągu 

bezpiecznego zakłada się, że ten 

proces kończy się i zwalnia wszystkie swoje zasoby.

5. Wróć do kroku 2.

6. Jeżeli dla każdego j = 1, 2, ...n  K[j]=true, to stan jest 

bezpieczny; 

     w przeciwnym przypadku stan nie jest bezpieczny.

Algorytm Bankiera

Obsługa żądania procesu przez a

lgorytm bankiera 

Zd[j,i] 

– tablica żądań

 

zasobów Z(i) przez proces P(j); 

1. Jeśli Zd > Pt[j], tzn. proces żąda więcej zasobów niż 
zadeklarowane na początku maximum M[j]  >>> zlecenie 
odrzucone.  

2. Jeśli Zd > D, tzn. proces żąda więcej zasobów niż jest ich 
dostępnych  >>> zlecenie odrzucone. 

3. Jeśli żaden z ww. warunków nie jest spełniony, 
konstruujemy stan, jaki powstałby po spełnieniu tego żądania 
i sprawdzamy, czy jest on 

bezpieczny. 

Nowy stan otrzymuje się następująco:
D = D – Zd;

Pd[j] = Pd[j] + Zd;

Pt[j] = Pt[j] – Zd;

4. Jeśli taki stan jest bezpieczny, żądanie jest spełniane.

Jeśli stan nie jest bezpieczny, proces P(j) musi czekać 

(mimo, że zasoby są wolne – jest to koszt unikania 
zakleszczeń).