1 Wykład nr 8: ZakleszczeniaSystemy operacyjne Wykład nr 8: Zakleszczenia Piotr Bilski
2 Pojęcia podstawowe Zakleszczenie to nieskończone oczekiwanie procesów na zasoby, których nie mogą otrzymać Przewidywanie zakleszczeń – graf przydziału zasobów Unikanie i zapobieganie zakleszczeniom Wykrywanie i likwidowanie zakleszczeń
3 Założenia System posiada skończoną ilość zasobówPoszczególne zasoby mogą być zwielokrotnione Działania na zasobach odbywają się poprzez funkcje systemowe Proces korzysta z zasobu poprzez: Zamówienie Użycie Zwolnienie
4 Warunki wystąpienia zakleszczeniaWzajemne wykluczanie – istnieje zasób niepodzielny Przetrzymywanie i oczekiwanie – istnieje proces posiadający zasób i czekający na inny Brak wywłaszczeń – procesu nie można pozbawić zasobu Czekanie cykliczne – istnieje cykl procesów czekających na zasoby przetrzymywane przez inne procesy w cyklu
5 Graf przydziału zasobówSłuży do opisu zależności zasobów między procesami Zawiera zbiory wierzchołków i krawędzi Wierzchołki to procesy (P) i zasoby (Z) Krawędź od procesu do zasobu to krawędź zamówienia Krawędź od zasobu do procesu to krawędź przydziału
6 Graf przydziału - przykład
7 Przykład zakleszczeniaP1→Z2→P2→Z4→P3→Z1→P1 P2→Z4→P3→Z1→P2 P1 P2 P3 Z1 Z3
8 Przykład cyklu bez zakleszczeniaP1→Z1→P2→Z3→P1 P4 P1 P2 P3 Z3 Z1
9 Obsługa zakleszczeń Protokół gwarantujący brak zakleszczeń (zapobieganie lub unikanie zakleszczeń) Po wystąpieniu zakleszczenia wykrycie i usunięcie go Ignorowanie zakleszczeń
10 Zapobieganie zakleszczeniomZaprzeczenie warunku wzajemnego wykluczania – trudne (niektóre zasoby niepodzielne)! Aby zamówić zasób, proces nie może posiadać innych zasobów (protokoły) Zapobieganie oczekiwaniu na zasób Numerowanie zasobów i wymaganie zamawiania ich w porządku rosnącym Wada – słabe wykorzystanie zasobów
11 Unikanie zakleszczeń Konieczna informacja o kolejności i typach zamawianych zasobów Każdy proces deklaruje, jaką maksymalną liczbę zasobów określonego typu będzie potrzebować Decyzję o przyznaniu zasobów podejmuje system Algorytm unikania zakleszczenia zapobiega powstawaniu cykli
12 Stan bezpieczny Jest to sytuacja, w której jest możliwy przydział zasobów poszczególnym procesom bez powstawania zakleszczenia Warunek konieczny: istnienie ciągu bezpiecznego procesów W przeciwnym wypadku występuje stan zagrożenia
13 Stan bezpieczny - przykładProcesy Max zapotrzebowanie Aktualne zapotrzebowanie P0 10 5 P1 4 2 P2 9 System dysponuje 12 jednostkami zasobów Potrzeby procesu Pi muszą być zaspokojone od razu, lub po zwolnieniu zasobów przez procesy Pj, gdzie i>j Ciąg
14 Algorytm grafu przydziału zasobówStosowany, gdy każdy zasób ma tylko jeden egzemplarz Oparty na grafie przydziału zasobów Krawędź deklaracji informuje o możliwości zamówienia zasobu przez proces Podczas rzeczywistego zamówienia krawędź deklaracji zamieniana jest na krawędź zamówienia, przy zwolnieniu -odwrotnie
15 Graf przydziału zasobów - przykładStan zagrożenia (cykl!)
16 Algorytm bankiera Stosowany, gdy zasoby mają wiele egzemplarzyKażdy proces deklaruje maksymalną liczbę egzemplarzy zasobu do użycia System decyduje, czy przydział zasobu nie powoduje ryzyka zakleszczenia
17 Algorytm bankiera – struktury danychDostępne Maksymalne … m … n m Maksymalne[i,j]=k Proces Pi może zamówić k egzemplarzy zasobu Zj
18 Algorytm bankiera – struktury danych (c.d.)Przydzielone Potrzebne Przydzielone[i,j]=k Proces Pi ma przydzielone k egzemplarzy zasobu Zj … n m … n m Potrzebne[i,j]=k Proces Pi potrzebuje jeszcze k egzemplarzy zasobu Zj
19 Algorytm bezpieczeństwaRoboczy i Skończone to wektory o długości m i n. Najpierw: Roboczy=Dostępne, Skończone[i] = F Znajdujemy i, dla którego Skończone[i] == F Potrzebnei <= Roboczy Roboczy = Roboczy + Przydzielone Jeśli Skończone[i] == T, dla każdego i, to system jest w stanie bezpiecznym
20 Algorytm zamawiania zasobówZamówienia to wektor zamówień poszczególnych zasobów przez proces Podczas zamówienia wykonywane są operacje: Jeśli Zamówienia > Potrzebne – zgłoś błąd Jeśli Zamówienia > Dostępne – czekaj Przydziel zasoby: Dostępne = Dostępne – Zamówienia Przydzielone = Przydzielone + Zamówienia Potrzebne = Potrzebne - Zamówienia
21
22 Realizacja (c.d.) Zamówienia1 = (1,0,2) Zamówienia1 <= Dostępne? AB C 3 2 Przydzielone Potrzebne A B C P0 7 4 3 P1 2 P2 6 P3 1 P4 Dostępne A B C P0 1 P1 3 2 P2 P3 P4 A B C 2 3
23 Wykrywanie zakleszczeńJeśli zakleszczenie może wystąpić, to potrzebne są algorytmy: Sprawdzający stan systemu na obecność zakleszczenia Likwidujący zakleszczenie Istnieją wersje algorytmów dla pojedynczych i wielokrotnych typów zasobów
24 Wykrywanie zakleszczeń dla zasobów pojedynczychWykorzystuje graf oczekiwania Zawiera wyłącznie wierzchołki procesów powiązane zależnościami zasobów: Pi→Pj Pi → Zq, Zq → Pj Zakleszczenie może zaistnieć, gdy w grafie istnieje cykl
25 Wykrywanie zakleszczeń dla zasobów pojedynczych - przykładgraf oczekiwania
26 Wykrywanie zakleszczeń dla zasobów wielokrotnychStruktury wykorzystywane: Wektor Dostępne, macierze Przydzielone i Zamówienia Algorytm odbiera zasoby procesowi, jeśli posiada on wszystko, czego potrzebuje
27 Wykrywanie zakleszczeń dla zasobów wielokrotnych - przykładPrzydzielone Zamówienia Dostępne A B C P0 P1 2 P2 P3 1 P4 A B C A B C P0 1 P1 2 P2 3 P3 P4
28 Zakleszczenie - przykładPrzydzielone Zamówienia Dostępne A B C P0 P1 2 P2 1 P3 P4 A B C A B C P0 1 P1 2 P2 3 P3 P4
29 Likwidowanie zakleszczeńMetody są stosowane w przypadku wykrycia zakleszczenia Dwa podejścia: Zaniechanie wszystkich zakleszczonych procesów Usuwanie pojedynczych procesów do momentu wyeliminowania zakleszczenia Problemem są zasoby użytkowane przez proces w momencie zaniechania
30 Likwidowanie zakleszczeń – c.d.Kryteria wyboru procesu do zaniechania: Priorytet Wiek i pozostały czas życia Ilość wykorzystywanych zasobów Ilość zasobów potrzebnych Charakter procesu (pierwszo- czy drugoplanowy)