Systemy operacyjne

Zakleszczenia

Zakleszczenie ( deadlock)

Zbiór procesów jest w stanie zakleszczenia, jeżeli każdy Systemy operacyjne

z nich czeka na zdarzenie, które może zostać

-zakleszczenia

spowodowane wyłącznie przez jakiś inny proces z tego zbioru

Przykładowe zdarzenia:

dr inż. Zbigniew Suski

Zwolnienie zasobu,

Podniesienie semafora,

Zwolnienie zamka

SO – zakleszczenia

SO – zakleszczenia

Zbigniew Suski

1

Zbigniew Suski

2

Zakleszczenie - przykład

Zakleszczenie - przykład

Semaphore

S1(1), S2(1);

Sekwencja prowadząca do zakleszczenia:

PROCES P1:

P1 wykonał operacje S1.P()

S1.P();

S2.P();

P2 wykonał operacje S2.P()

.

P1 usiłuje wykonać S2.P() - czeka

.

S2.V();

na zwolnienie S2 przez P2

S1.V();

P2 usiłuje wykonać S1.P() - czeka

PROCES P2:

na zwolnienie S2 przez P1

S2.P();

S1.P();

Bę dą czekały w nieskoń czoność !!!

Samochody nie mają wstecznego biegu = brak

.

wywłaszcze

Do zakleszczenia mo

ń zasobów.

.

ż e (ale nie musi)

S1.V();

dojść.

S2.V();

SO – zakleszczenia

SO – zakleszczenia

Zbigniew Suski

3

Zbigniew Suski

4

Model systemu (na potrzeby analizy zakleszczeń) Zasoby odzyskiwalne

System składa się z zasobów typu Z , Z , . . ., Z (np.

Liczba jednostek zasobów odzyskiwalnych jest ustalona.

1

2

m

cykle procesora, przestrzeń adresowa pamię ci,

Zasoby odzyskiwalne po ich zwolnieniu przez jakiś urzą dzenia WE/WY)

proces mogą zostać ponownie użyte przez inny proces.

Każdy zasób typu Z ma W egzemplarzy.

i

i

Proces współpracuje z egzemplarzem zasobu

odzyskiwalnego według następującego schematu:

O zasoby rywalizują procesy ze zbioru P , P , ..., P

1

2

n

zamówienie (ewentualnie oczekiwanie na

Z punktu widzenia problemu zakleszczenia, zasoby

realizację)

można sklasyfikować następująco :

użycie — korzystanie zasobu (jego

przetrzymywanie)

zasoby odzyskiwalne (zwrotne, trwałe, ang.

reusable resources)

zwolnienie — oddanie zasobu do systemu

zasoby nieodzyskiwalne (zużywalne, niezwrotne,

Przykłady zasobów odzyskiwalnych: procesor, pamięć, ang. consumable resources)

kanał wejścia-wyjścia.

SO – zakleszczenia

SO – zakleszczenia

Zbigniew Suski

5

Zbigniew Suski

6

Opracował; Zbigniew Suski

1

Systemy operacyjne

Zakleszczenia

Zasoby nieodzyskiwalne

Korzystanie z zasobów nieodzyskiwalnych

Jednostki zasobu nieodzyskiwalnego są tworzone

przez jaki

Proces ubiega się o dowolny egzemplarz zasobu

ś proces, a następnie zużywane (tym samym

nieodzyskiwalnego według nast

usuwane) przez inny proces.

ępującego

schematu:

Nie ma ograniczenia na liczbę tworzonych jednostek

zamówienie (ewentualnie oczekiwanie na

zasobu.

realizację)

Ilość aktualnie dostępnych jednostek jest skończona i

zużycie — wykorzystanie zasobu (jego

może się zmieniać w czasie w wyniku zmian stanu

usunięcie)

systemu.

Proces może wyprodukować i przekazać zasób do

Przykłady zasobów nieodzyskiwalnych: kod znaku z

systemu.

klawiatury, sygnał lub komunikat przekazany do

procesu.

SO – zakleszczenia

SO – zakleszczenia

Zbigniew Suski

7

Zbigniew Suski

8

Warunki konieczne wystąpienia zakleszczenia Warunki konieczne wystąpienia zakleszczenia –

Wzajemne wyłą czanie. Przynajmniej jeden zasób jest w przypadku zasobów nieodzyskiwalnych

niepodzielny, tzn. że zasobu może używać w danej chwili tylko jeden proces. Następny zamawiający zostanie

Wzajemne wyłą czanie. Jednostka zasobu może być opóźniony.

zużyta przez jeden proces.

Przetrzymywanie i oczekiwanie. Musi istnieć proces

Przetrzymywanie i oczekiwanie. W stanie oczekiwania mający przydzielony jakiś zasób i oczekujący na zasób, proces nie produkuje jednostek zasobów.

który jest przetrzymywany przez inny proces.

Brak wywłaszczeń . Nie można zmusić procesu do

Brak wywłaszczeń . Zasoby nie podlegają wywłaszczaniu, wyprodukowania jednostki zasobu lub zrobić to za niego.

tzn. mogą być zwalniane tylko z inicjatywy

przetrzymującego je procesu.

Czekanie cykliczne. Musi istnieć zbiór czekających procesów {P , ... ,P } takich,

czeka na

0

k

że P0

Czekanie cykliczne. Musi istnieć zbiór czekających wyprodukowanie jednostki zasobu przez P , P czeka na 1

1

procesów {P , ... ,P } takich,

czeka na zasób

0

k

że P0

wyprodukowanie jednostki zasobu y przez P , ... P czeka 2

k

przetrzymywany przez P , P na zasób przetrzymywany

1

1

na wyprodukowanie jednostki zasobu przez P .

0

przez P , ... P czeka na zasób przetrzymywany przez P .

2

k

0

Warunki te muszą być spełnione jednocześnie.

Warunki te muszą być spełnione jednocześnie.

SO – zakleszczenia

SO – zakleszczenia

Zbigniew Suski

9

Zbigniew Suski

10

Reprezentacja stanu systemu

Konstruowanie grafu przydziału zasobów

Graf przydziału zasobów odzyskiwalnych

W wyniku zamówienia jednostki zasobu Zj przez

Graf skierowany o zbiorze wierzchołków W i kraw

proces Pi w grafie pojawia si

ędzi K

ę krawędź zamówienia

Pi → Zj.

Zbiór W składa się z dwóch podzbiorów:

Realizacja zamówienia może nastąpić wówczas, gdy

P = { P , ... , P } – procesy (kółka)

1

n

są wolne jednostki żądanego zasobu, a jej wynikiem

Z = { Z , ... , Z } - typy zasobów (prostok

jest zmiana kierunku krawędzi żądania, tym samym

1

m

ąty)

zamiana na krawędź przydziału Zj → Pi.

Egzemplarze danego zasobu reprezentowane przez

W wyniku zwolnienia jednostka zasobu jest

kropki wewnątrz prostokąta

odzyskiwana przez system a krawędź przydziału

Krawędź żądania - skierowana krawędź P → Z

znika.

i

k

Krawędź przydziału - skierowana krawędź Z → P

k

i

SO – zakleszczenia

SO – zakleszczenia

Zbigniew Suski

11

Zbigniew Suski

12

Opracował; Zbigniew Suski

2

Systemy operacyjne

Zakleszczenia

Przykładowy graf przydziału zasobów

Własności grafu przydziału zasobów

Dany jest graf skierowany G = (N, E), gdzie

N — zbiór wierzchołków ,

E ⊆ N × N — zbiór łuków (skierowanych krawędzi).

Niech dla v∈ N zdefiniowany bę dzie zbiór O(v) = {u∈ N: (v,u)∈ E} ∪ {u∈ N: ∃ w∈ N (v,w)∈ E ∧ u∈ O(w)}

W grafie G wystę puje cykl, gdy:

∃ v∈ N v∈ O(v)

W grafie występuje supeł (wę zeł, zatoka, ang. knot), gdy:

∃

∀

N′⊆ N

v∈ N′ ( ∀ u∈ N′ u∈ O(v) ∧ ∀ u∈ N\N′ u∉ O(v) ) SO – zakleszczenia

SO – zakleszczenia

Zbigniew Suski

13

Zbigniew Suski

14

Graf przydziału zasobów z cyklem (zakleszczenie) Graf przydziału zasobów z cyklem (brak zakleszczenia) SO – zakleszczenia

SO – zakleszczenia

Zbigniew Suski

15

Zbigniew Suski

16

Inaczej mówiąc

Metody postępowania z zakleszczeniami

Jeżeli graf G( V, E) nie posiada cykli to zakleszczenie

Ignorowanie problemu – zakleszczenie jest traktowane nie występuje.

jak awaria

Jeżeli graf zawiera cykl, to

Metody zapewniające, że zakleszczenie nie będzie

miało miejsca:

jeżeli dla każdego rodzaju zasobu istnieje tylko

jeden egzemplarz, wtedy mamy do czynienia z

zapobieganie zakleszczeniom,

zakleszczeniem.

unikanie zakleszczeń.

jeżeli dla każdego zasobu istnieje więcej niż

Metody pozwalające na wejście w zakleszczenie i potem jeden egzemplarz, istnieje możliwość powstania

usuwające ten stan:

zakleszczenia

wykrywanie zakleszczeń,

wychodzenie z zakleszczenia.

SO – zakleszczenia

SO – zakleszczenia

Zbigniew Suski

17

Zbigniew Suski

18

Opracował; Zbigniew Suski

3

Systemy operacyjne

Zakleszczenia

Zapobieganie zakleszczeniom

Zapobieganie zakleszczeniom

Zapobieganie polega na zapewnieniu, aby przynajmniej

Przetrzymywanie i oczekiwanie

jeden z warunków koniecznych zakleszczenia nie był

Należy zagwarantować, że jeżeli którykolwiek z

spełniony

procesów zamawia zasób, to nie może przetrzymywać

żadnych innych zasobów. Rozwiązania:

Wzajemne wyłączanie

Każdy proces zamawia i otrzymuje wszystkie

Charakterystyka niektórych zasobów uniemożliwia

zasoby, zanim rozpocznie działanie

podjąć jakichkolwiek kroków w celu zapobiegania.

Pozwolenie procesowi na zamawianie zasobów

Wzajemne wykluczanie musi być zachowane w

może mieć miejsce tylko wówczas, gdy proces nie

przypadku dostępu do zasobów niepodzielnych.

ma żadnych zasobów.

Zasoby współdzielone nie wymagają dostępu w

trybie wyłącznym - używanie zasobu przez jeden

WADY: Niewielkie wykorzystanie zasobów i możliwość proces nie blokuje dostępu do niego innym

nieskończonego głodzenia.

procesom.

SO – zakleszczenia

SO – zakleszczenia

Zbigniew Suski

19

Zbigniew Suski

20

Zapobieganie zakleszczeniom

Zapobieganie zakleszczeniom

Brak wywłaszczeń

Czekanie cykliczne

Gdy proces mający jakieś zasoby zgłasza

W celu przeciwdziałania cyklowi w oczekiwaniu

zapotrzebowanie na inny zasób, który nie może

procesów na zasoby, należy zapewnić, że wszystkie

być mu natychmiast przydzielony, wówczas zasoby

zasoby będą zamawiane w tej samej dla wszystkich

tego procesu są zwalniane i dopisywane do listy

procesów kolejności.

zasobów, których proces oczekuje.

Można to osiągnąć poprzez wymuszenie

Proces zostanie wznowiony dopiero wtedy, gdy

całkowitego liniowego uporządkowania wszystkich

będzie można przywrócić dawne jego zasoby oraz

typów zasobów i wymaganie, aby każdy proces

przydzielić zasób, który zamawiał.

zamawiał zasoby we wzrastającym porządku ich

ALTERNATYWNIE: odbieranie żądanych zasobów

numeracji.

przetrzymującym je procesom, gdy procesy te są w

stanie oczekiwania na inne zasoby.

SO – zakleszczenia

SO – zakleszczenia

Zbigniew Suski

21

Zbigniew Suski

22

Unikanie zakleszczeń

Unikanie zakleszczeń

Kiedy proces zamawia dostępny zasób, system musi decydować czy

Metoda ta wymaga dodatkowej informacji o tym, jak system znajdzie się w stanie bezpiecznym.

będzie następowało zamawianie zasobów. System

System jest w stanie bezpiecznym tylko wtedy, gdy istnieje bierze pod uwagę zasoby bieżąco dostępne, zasoby

sekwencja bezpieczna wszystkich procesów.

przydzielone każdemu z procesów oraz przyszłe

Sekwencja < P1, P2, …, Pn> jest bezpieczna, jeż eli dla każ dego Pi, zamówienia i zwolnienia.

jego zapotrzebowanie na zasoby moż e być zaspokojone przez dostępne bieżące zasoby oraz zasoby procesów przetrzymywane

Algorytm

unikania

zakleszczenia

dynamicznie

przez wszystkie procesy Pj, gdzie j<i.

sprawdza

stan

przydziału

zasobów,

aby

Jeżeli zapotrzebowane zasoby procesu Pi nie są natychmiast zagwarantować, że nie dojdzie do spełnienia warunku dostępne, to Pi moż e poczekać , aż zakoń czą się wszystkie czekania cyklicznego.

procesy Pj.

Stan przydziału zasobów może być określony przez

Gdy zakończy się proces Pj , Pi moż e otrzymać wymagane zasoby, dokończyć swoją pracę, zwolnić wszystkie zasoby i liczbę dostępnych i przydzielonych zasobów oraz

zakończyć działanie.

przez maksymalne zapotrzebowania procesów.

Gdy Pi koń czy się , Pi+1 moż e uzyskać jego zasoby itd..

SO – zakleszczenia

SO – zakleszczenia

Zbigniew Suski

23

Zbigniew Suski

24

Opracował; Zbigniew Suski

4

Systemy operacyjne

Zakleszczenia

Unikanie zakleszczeń

Wykrywanie zakleszczenia

Podstawowe implikacje

Jeżeli w systemie nie stosuje się algorytmów zapobiegania ani unikania zakleszczeń, czyli zezwala się na zaistnienie zakleszczenia, to powinny funkcjonować:

Jeżeli system znajduje się w stanie bezpiecznym

blokada nie występuje.

algorytmy sprawdzające stan systemu w celu wykrycia

Jeżeli system znajduje się w stanie niebezpiecznym wystąpienia zakleszczenia,

istnieje możliwość wystąpienia blokady.

algorytmy wychodzenia ze stanu zakleszczenia.

Unikanie zagwarantowanie aby system nigdy nie

wchodził do obszaru stanów niebezpiecznych.

W przypadku zasobów pojedynczych wykorzystuje się graf oczekiwań (węzły odpowiadają procesom, Pi→Pk jeżeli Pi czeka na zasób będący w posiadaniu Pk).

W przypadku zasobów wielokrotnych wykorzystuje się

Algorytm bankiera

algorytm podobny do algorytmu bankiera.

Kiedy wykonywać algorytm ?

SO – zakleszczenia

SO – zakleszczenia

Zbigniew Suski

25

Zbigniew Suski

26

Wychodzenie ze stanu zakleszczenia

Wychodzenie przez usuwanie procesów powoduje

odzyskanie wszystkich zasobów przydzielonych

usuwanym procesom.

Wychodzenie przez wywłaszczanie polega na

stopniowym odbieraniu zasobów jednym procesom i

przydzielaniu innym, aż pętla zakleszczenia zostanie przerwana.

Problemy:

wybór ofiary,

wycofanie i wznowienie procesu,

głodzenie procesów.

SO – zakleszczenia

Zbigniew Suski

27

Opracował; Zbigniew Suski

5