W wykładzie 6 zajmiemy się zagadnieniem zakleszczeń. Zakleszczenie to sytuacja, w której pewien zbiór procesów nie może kontynuować działań, ponieważ każdy proces do niego należący przetrzymuje zasoby potrzebne innym procesom z tego zbioru, a jednocześnie czeka na zasoby przydzielone innym procesom.
Zakleszczenie jest zjawiskiem niezwykle niepożądanym w systemie i dlatego opracowano rozmaite metody radzenia sobie z nimi. W niniejszym wykładzie omówimy te metody. Są nim zapobieganie, unikanie i wykrywanie. Pokażemy także powiązany z tymi metodami tzw. algorytm bankiera.
Zakleszczenie to zbiór procesów będących w impasie wywołanym przez to, że każdy proces należący do tego zbioru przetrzymuje zasoby potrzebne innym procesom z tego zbioru, a jednocześnie czeka na zasoby przydzielone innym procesom.
Rozważmy system, w którym są procesor i drukarka. Żeby coś wydrukować, proces musi otrzymać oba te zasoby. Przypuśćmy, że dwa procesy chcą drukować. Jednemu z nich system przydzielił drukarkę a drugiemu procesor. Pierwszy trzyma więc procesor i oczekuje na przydział drukarki, który nigdy nie nastąpi, ponieważ tę trzyma drugi proces oczekujący na przydział procesora.
Do podobnej sytuacji może dojść na wąskim moście o ruchu dwukierunkowym. Gdy na ten most wjadą z przeciwnych kierunków dwa samochody, będą się wzajemnie blokować. Porównując to do poprzedniej sytuacji, zauważymy, że mamy do czynienia z dwoma zasobami (dwie połówki mostu). Żeby przejechać, trzeba mieć przydzielone je obydwie. W tym wypadku każdy z samochodów zajął po jednym zasobie (jednej połówce mostu) i czeka na przydział tej drugiej połówki. Znając upór polskich kierowców, można przypuszczać, że nieprędko któryś z nich ustąpi i się wycofa (dojdzie do wywłaszczenia). Inny rodzaj chamstwa drogowego nosi nazwę pociągu i polega na tym, że kierowcy z jednej strony mostu formują spójną kolumnę i bez przerwy jadą przez most, nie dając możliwości przejechania komukolwiek z drugiej strony mostu (mamy wówczas do czynienia z zagłodzeniem).
Rozważania o zakleszczeniu będziemy prowadzić w ramach pewnego modelu systemu. Zakłada się w nim, że w systemie jest m rodzajów zasobów oznaczanych Z(1), Z(2), ..., Z(m). Dla każdego i=1, 2, ..., m, E(i) oznacza liczbę egzemplarzy zasobu Z(i).
Procesy korzystający z zasobu wykonuje następujące działania:
Aby mogło dojść do zakleszczenia, muszą zachodzić cztery następujące warunki. Nie gwarantują one zakleszczenia, ale jeśli choć jeden z nich nie jest spełniony, do zakleszczenia nie dojdzie.
Graf przydziału zasobów jest obiektem matematycznym, za którego pomocą łatwo jest analizować zakleszczenia. Zauważmy, że jeden z warunków koniecznych zakleszczenia mówi właśnie o cyklu w jakimś grafie. Fakt istnienia, bądź nie, cyklu w tym grafie ściśle wiąże się więc z występowaniem zakleszczeń.
Graf przydziału zasobów jest skierowany.
Wierzchołkami tego grafu są procesy działające w systemie P(1), P(2), ..., P(n) oraz zasoby systemowe Z(1), Z(2), ..., Z(m).
Krawędź żądania od procesu P(i) do zasobu Z(j) oznacza, że proces P(i) zażądał przydzielenia zasobu Z(j).
Krawędź przypisania od zasobu Z(j) do procesu P(i) oznacza, że zasób Z(j) jest przydzielony procesowi P(i).
Jeśli w tym grafie występuje cykl, może to oznaczać istnienie zakleszczenia. Wyobraźmy sobie dwa procesy P(1) i P(2) oraz dwa zasoby Z(1) i Z(2), z których każdy ma tylko jeden egzemplarz. Procesowi P(1) przydzielono zasób Z(1), a procesowi P(2) przydzielono zasób Z(2). Jednocześnie proces P(1) zażądał zasobu Z(2) a proces P(2) zażądał zasobu Z(1). Te procesy są w stanie zakleszczenia. Oto graf przydziału zasobów, na którym zobaczysz czteroelementowy cykl będący zakleszczeniem.
Cykl w grafie przydziału zasobów nie wystarcza do tego, żeby było zakleszczenie. Gdyby w poprzednim przykładzie były dwa egzemplarze Z(1), to oczywiście zakleszczenia by nie było, tak jak na poniższym rysunku.
Jeśli w grafie przydziału zasobów jest cykl i wszystkie zasoby w tym cyklu są jednoegzemplarzowe, to na pewno ma miejsce zakleszczenie.
Jedną z metod jest zapewnienie, że system nigdy nie znajdzie się w stanie zakleszczenia. Można też dopuścić do powstania zakleszczenia, wykryć to, a potem zlikwidować zaistniałą sytuację. Niestety wiele w wielu systemach ignoruje się ten problem i udaje się, że zakleszczenia występują jedynie w przekazach ludowych i legendach. Jednym z tych systemów jest Unix.
Wyróżniamy w zasadzie trzy metody radzenia sobie z zakleszczeniami:
Zapobieganie zakleszczeniom polega na zaprzeczeniu co najmniej jednemu z czterech warunków koniecznych zakleszczenia. Gdy co najmniej jeden z tych warunków nie jest spełniony, mamy pewność, że do zakleszczenia nie dojdzie.
Brak wzajemnego wykluczania (pierwszy warunek) oznacza eliminację całego problemu. W rzeczywistości korzystanie z większości zasobów i urządzeń wymaga wyłączności, więc zapobieganie zakleszczeniom nie może polegać na eliminacji tego warunku.
Brak przetrzymywania i oczekiwania można zrealizować na przykład w ten sposób, że proces musi zażądać kompletu potrzebnych zasobów zanim przystąpi do działania. Można też zezwolić na żądanie przydzielenia zasobów tylko tym procesom, które nie są w posiadaniu żadnego zasobu. Niestety prowadzi to do niskiego wykorzystania zasobów i możliwości zagłodzenia procesów, które jednocześnie wykorzystują wiele zasobów.
Wywłaszczanie można zrealizować na przykład tak, że proces żądający zasobu, który nie jest obecnie dostępny, musi zwrócić wszystkie posiadane przez siebie zasoby. Następnie jest on umieszczamy w kolejce oczekiwania na zasób, którego zażądał, i zasoby, które przymusowo zwolnił. Proces ten będzie wznowiony dopiero wtedy, gdy wszystkie te zasoby będą dostępne i proces je otrzyma.
Wykluczenie czekania cyklicznego można osiągnąć poprzez ponumerowanie wszystkich rodzajów zasobów i wprowadzenie zasady, że proces musi żądać zasobów w kolejności rosnących numerów zasobów (np. nie może zażądać zasobu 4 po przydzieleniu mu zasobu 7).
Gdy stosujemy metodę unikania zakleszczeń wszystkie warunki konieczne są prawdziwe. Nie dopuszczamy do zakleszczeń poprzez badanie stanu systemu przed każdym żądaniem przydziału zasobów i niekiedy odrzucamy to żądanie nawet wtedy, gdy są wolne zasoby, ale uznaliśmy, że spełnienie tego żądania może prowadzić do zakleszczenia. Unikanie zakleszczeń zwykle wymaga dodatkowej wiedzy o procesach. Najprostszą i najbardziej przydatną informacją tego rodzaju są dane o maksymalnym dopuszczalnym zapotrzebowaniu na zasoby w każdym procesie.
W algorytmie unikania dynamicznie bada się stan przed każdym żądaniem i sprawdza się, czy jego spełnienie może doprowadzić do czekania cyklicznego.
Realizując unikanie zakleszczeń, możemy na przykład przez cały czas utrzymywać stan bezpieczny, tzn. taki, w którym istnieje ciąg bezpieczny.
Ciąg procesów P(1), P(2), ..., P(n) nazywamy bezpiecznym, gdy dla i=1, 2, ..., n maksymalne potrzeby procesu P(i) mogą być zaspokojone za pomocą obecnie dostępnych zasobów i zasobów będących w posiadaniu procesów P(1), P(2), ..., P(i-1). Intuicja kryjąca się za tą definicją polega na tym, że zakładamy, iż proces, którego maksymalne potrzeby zaspokojono, kończy się i zwalnia posiadane przez siebie zasoby. Proces P(i) może więc korzystać z zasobów zwolnionych przez poprzednie procesy w ciągu, ponieważ zakładamy, że one już skończyły swoje zadania.
Jeśli system jest w stanie bezpiecznym, nie ma zakleszczeń, ponieważ istnieje możliwa do zrealizowania kolejność wykonania i zakończenia wszystkich procesów. Stan niebezpieczny nie oznacza jednak konieczności istnienia zakleszczenia (np. proces nie zawsze musi żądać wszystkich zadeklarowanych przez siebie zasobów). Unikanie polega jednak na utrzymywaniu systemu w stanie bezpiecznym.
Algorytm bankiera służy do sprawdzenia, czy stan jest bezpieczny. Polega on na skonstruowaniu ciągu bezpiecznego. Przypuśćmy, że jest n procesów P(1), P(2), ..., P(n) oraz m procesów Z(1), Z(2), ..., Z(n). W trakcie realizacji algorytmu bankiera wykorzystuje się następujące tablice.
Stan systemu jest zadany przez tablice Potrzeby, Przydział i Dostępne. Zadaniem algorytmu jest stwierdzenie, czy ten stan jest bezpieczny. W algorytmie wykorzystamy tablice Koniec i Robocze. Oto kolejne kroki:
Przypuśćmy, że proces P(j) zażądał zasobów opisanych za pomocą tablicy Żądane[1..m] (Żądane[i] to liczba egzemplarzy zasobu P(i), których żąda proces P(j)). Rozważmy obsługę tego żądania w systemie, w którym stosujemy algorytm bankiera przy realizacji strategii unikania zakleszczeń.
| Dostępne | := | Dostępne | - | Żądane |
| Przydział[j] | := | Przydział[j] | + | Żądane |
| Potrzeby[j] | := | Potrzeby[j] | - | Żądane |
Rozważmy sytuację, w której są trzy procesy P(1), P(2) i P(3) oraz dwa rodzaje zasobów Z(1) i Z(2), które mają po 3 egzemplarze. Oto stan systemu opisany tablicami Przydział, Max i Dostępne.
| Przydział | Max | Dostępne | ||||
|---|---|---|---|---|---|---|
| Proces | Z(1) | Z(2) | Z(1) | Z(2) | Z(1) | Z(2) |
System jest w stanie bezpiecznym, ponieważ istnieje ciąg bezpieczny P(3), P(2), P(1). W obecnym stanie możemy spełnić maksymalne potrzeby P(3). Zakładamy więc, że P(3) zwolni posiadany jeden egzemplarz zasobu Z(2). To z kolei pozwoli na spełnienie maksymalnych żądań P(2) i zwolnienie jego zasobów. Wówczas będzie można spełnić maksymalne żądania P(1).
Stosując tę metodę radzenia sobie z zakleszczeniami, dopuszczamy powstawanie zakleszczeń, ale umiemy je wykrywać, likwidować i przywracać normalne działanie systemu po tym zabiegu.
Gdy w systemie występuje po dokładnie jednym egzemplarzu każdego zasobu, można skorzystać z grafu oczekiwania. Jest to uproszczona postać grafu przydziału zasobów.
Graf oczekiwania jest skierowany.
Wierzchołkami tego grafu są procesy działające w systemie P(1), P(2), ..., P(n).
Krawędź oczekiwania od procesu P(k) do procesu P(l) oznacza, że proces P(k) czeka na zwolnienie zasobu przez proces P(l).
Istnienie cyklu w tym grafie oznacza zakleszczenie. Wykrywanie zakleszczenia może więc polegać na utrzymywaniu tego grafu i okresowe sprawdzanie istnienia w nim cyklu. Koszt takiego algorytmu (np. poprzez wyszukiwanie w głąb) jest proporcjonalny do liczby krawędzi grafu, która maksymalnie może wynieść n^2.
Oto przykładowy graf oczekiwania. Proces P(1) oczekuje na zwolnienie jakiegoś zasobu przez proces P(2), zaś proces P(2) oczekuje na zwolnienie jakiegoś zasobu przez proces P(3). Gdy teraz proces P(3) zażąda zasobu będącego w posiadaniu procesu P(1), w grafie pojawi się nowa (zaznaczona na czerwono krawedź), która spowoduje powstanie cyklu w grafie oczekiwania, czyli zakleszczenie:
Wykrywanie zakleszczeń można przeprowadzić też metodą podobną do algorytmu bankiera. Wykorzystuje się w nim tablice Dostępne, Przydział, Koniec i Robocze, takie jak poprzednio oraz tablicę:
Po wykryciu zakleszczenia należy je zlikwidować. Można na przykład przerwać wszystkie zakleszczone procesy. Jest to jednak zbyt brutalna metoda. Lepiej jest przerywać zakleszczone procesy po jednym do chwili, w której zakleszczenie zniknie. Zwykle powinno wystarczyć przerwanie jednego procesu. Oto kryteria, z których można skorzystać przy wyborze procesu do przerwania:
W wykładzie 6 poznaliśmy pojęcie zakleszczenia oraz konsekwencje wystąpienia takiej sytuacji w systemie operacyjnym.
Poznaliśmy też różnorakie podejścia do radzenia sobie z zakleszczeniami. Były to zapobieganie, unikanie i wykrywanie z odtwarzaniem. Warto dobrze przyswoić sobie różnice między zapobieganiem i unikaniem, ponieważ z naszych doświadczeń wynika, że te dwa jakże odmienne pojęcia są często mylone.
Przedstawiliśmy też dwie wersje algorytmu bankiera. Jedna służyła do implementacji unikania zakleszczeń, a druga była metodą ich wykrywania.
Czasem warto stosować strategie mieszane. Można podzielić zasoby na klasy i w każdej z tych klas stosować inną metodę (zapobieganie, unikanie albo wykrywanie z odtwarzaniem), najlepszą w wypadku tej klasy zasobów.
Aktualnie przydzielone zasoby (i maksymalne zapotrzebowania) są następujące:
| Aktualny przydział | Maksymalne zapotrzebowanie | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
|
Czy ten system jest w stanie bezpiecznym? Podaj sekwencję kończenia procesów świadczącą o tym.