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ń).