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