Zapobieganie zakleszczeniom polega na narzuceniu restrykcji na generowanie zamówień lub na ich realizację. Restrykcje te mają na celu zagwarantowanie, że nie będzie spełniony któryś z warunków koniecznych zakleszczenia. Może to jednak prowadzić do słabego wykorzystania zasobów i ograniczenia przepustowości systemu.
Unikanie zakleszczeń polega na takiej realizacji zamówień, żeby zawsze zagwarantować odpowiednią liczbę wolnych zasobów, niezbędnych dla zakończenia zadań. Strategia unikania zakleszczeń wymaga znajomości przyszłego zbioru zamówień procesów na zasoby. Innymi słowy, przed przydzieleniem pierwszego zasobu procesowi system musi wiedzieć, jakie zasoby będą żądane przez proces w dalszej kolejności, aż do momentu ich całkowitego zwolnienia. Oczywiście zamówienia mogą być realizowalne tylko w zakresie wcześniejszych deklaracji. Przekroczenie zadeklarowanych ograniczeń musi spowodować odrzucenie zamówienia.
Wykrywanie zakleszczeń wymaga okresowego uruchomienia odpowiedniego algorytmu. Jest to dodatkowe obciążenie dla systemu, gdyż w wielu przypadkach efektem będzie stwierdzenie braku zakleszczenia.
Likwidowanie zakleszczeń polega na zmuszeniu jakiegoś procesu (lub kilku procesów) do ustąpienia w rywalizacji o zasoby. Może to oznaczać:
Likwidowanie zakleszczeń w przypadku zasobów nieodzyskiwalnych polega na usuwaniu procesów. Nie można to mówić o wywłaszczaniu, ponieważ zasoby są zużywane zaraz po przydzieleniu. Z tego samego powodu, w ramach zapobiegania nie ma sensu przeciwdziałać warunkowi koniecznemu, mówiącemu o braku wywłaszczeń.
W związku z tym, że zasoby nie są zwalniane po przydzieleniu nie ma pojęcia stanu bezpiecznego, który jest podstawą unikania zakleszczenia. A więc w przypadku zasobów nieodzyskiwalnych również tego podejścia nie stosuje się.
W poprzednim module została omówiona reprezentacja stanu systemu w postaci grafu przydziału zasobów. Na potrzeby detekcji zakleszczenia lub zagrożenia reprezentację tę można jednak uprościć do grafu oczekiwania, w którym występują tylko procesy, a skierowane krawędzie wskazują, które procesy od których oczekują zwolnienia jednostek zasobów.
Reprezentacja macierzowa opiera się na wektorach i macierzach reprezentujących stan zasobów oraz żądania procesów. W odpowiednich strukturach macierzowych pamiętane są liczby jednostek zasobów poszczególnych typów, związanych z poszczególnymi procesami. Typom zasobów odpowiadają kolumny, a procesom wiersze.
Reprezentacja macierzowa ułatwia określenie w zwartej formie pewnych relacji na liczbach jednostek zasobów. Może to poprawić czytelność kodu programu, aczkolwiek w praktyce macierze, opisujące stan systemu, mogą zawierać dużo pustych miejsc (tzw. macierze rzadkie). Reprezentacja takiej macierzy w postaci tablicy oznacza spore marnotrawstwo pamięci.
Uogólniając, macierze lepiej nadają się do wyrażania zależności ilościowych, co jest szczególnie przydatne przy analizie zasobów odzyskiwalnych. Zależności pomiędzy konkretnymi procesami natomiast łatwiej odczytać z grafu, co z kolei częściej przydaje się przy analizie zasobów nieodzyskiwalnych.
Z grafu przydziału zasobów można uzyskać graf oczekiwania przez usunięcie wierzchołków zasobowych i złączenie odpowiednich krawędzi. Jeśli zatem z usuwanego wierzchołka wychodzi krawędź przydziału lub produkcji, a dochodzi krawędź zamówienia, w grafie oczekiwania pojawi się krawędź skierowana od procesu zamawiającego do procesu przetrzymującego (lub produkującego) jednostkę zasobu.
Uproszenie grafu przydziału do grafu oczekiwania ułatwia bezpośrednie zastosowanie znanych algorytmów wykrywania cykli lub supłów (węzłów, zatok) w grafie.
Zakres informacji, opisujących stan systemu, musi obejmować zasoby, jakimi w ogóle dysponuje system, zasoby przydzielone poszczególnym procesom, żądania zasobowe procesów, ewentualnie na potrzeby analizy bezpieczeństwa — deklaracje odnośnie maksymalnych żądań. Na tej podstawie można uzyskać inne przydatne informacje, np. liczbę wolnych jednostek zasobów poszczególnych typów.
Macierz C wynika z konfiguracji systemu i nie jest elementem bieżącego stanu.
Macierze R i A związane są bieżącym stanem systemu.
Macierz F wynika z C oraz A (jest to różnica tych dwóch macierzy).
Z pierwszej formuły wynika, że procesom nie można przydzielić w sumie więcej jednostek zasobów poszczególnych typów, niż liczba jednostek, zarządzana przez system.
Druga formuła właściwie definiuje wektor wolnych jednostek. Wszystkie jednostki, nie będące w posiadaniu któregoś z procesów, są wolne.
Trzecia formuła mówi, że proces nie może żądać więcej jednostek, niż jest w dyspozycji systemu. Zatem to, co już ma przydzielone i to, co jeszcze zamawia, łącznie nie może przekroczyć liczby jednostek, którymi dysponuje system.
Przedstawiona formuła oznacza, że jest jakiś podzbiór procesów P’, oczekujących na zamówione zasoby, ale nawet gdyby wszystkie procesy spoza tego zbioru zakończyły działanie, to i tak dla każdego procesu ze zbioru P’ jakiś zasób Zj nie będzie dostępny w wystarczającej liczbie jednostek.
Zadaniem algorytmu jest przede wszystkim ustalenie, czy wystąpiło zakleszczenie. Jeśli zakleszczenie wystąpiło, można również uzyskać informację o procesach, które zostały zakleszczone. Stwierdzenie natomiast braku zakleszczenia dotyczy wyłącznie bieżącego stanu (analizowanego przez algorytm) i oznacza, że stan zakończenia przetwarzania wszystkich procesów jest osiągalny. Nie oznacza to jednak, że przy pewnej sekwencji zamówień w przyszłości i ich natychmiastowej (nie kontrolowanej) realizacji do zakleszczenia nie dojdzie.
Oprócz macierzy, opisujących stan systemu, czyli C, R, A i F, potrzebne są jeszcze zmienne pomocnicze. W miarę analizy, żądania pewnych procesów można uznać za możliwe do zrealizowania. Procesy takie uznane zostaną zatem za zakończone, co zostanie odnotowane w wektorze K. Jednostki zasobów, przetrzymywane przez te procesy, wrócą do systemu i zostaną uznana za wolne. Łączna liczba wolnych jednostek, uwzględniająca jednostki odzyskane po zakończonych procesach, przechowywana będzie w wektorze W.
Wektor W przechowuje informację o liczbie jednostek poszczególnych rodzajów zasobów dostępną dla procesów. Początkowo zatem jego wartość inicjalizowana jest zawartością wektora F. W analizie istotne są tylko te procesy, które mogą zwolnić jakieś jednostki. Wartość na pozycji, odpowiadającej tym procesom, w tablicy K jest false. Z kolei procesy, które w tablicy K mają wartość true, uznane są za zakończone lub nieistotne.
W bloku decyzyjnym poszukiwany jest proces, który może zwolnić jakieś jednostki (nie jest uznany za zakończony), a którego zamówienie może zostać zaspokojone dostępnymi w systemie jednostkami (przechowywanymi w wektorze W).
Jeśli taki proces się znajdzie, zostaje on uznany za zakończony, a zwalniane przez niego jednostki zasobów dołączane są do wektora W. Następuje powrót do bloku decyzyjnego i poszukiwanie kolejnego procesu.
Jeśli warunek (koniunkcja) w bloku decyzyjnym jest nie spełniony, to albo nie ma kolejnego procesu „do zakończenia”, albo dla żadnego z procesów nie zakończonych nie ma wystarczającej liczby jednostek któregoś z zasobów. Sprawdzane jest to w kolejnym bloku decyzyjnym. Jeśli w wektorze K są wartości false, to odpowiednie procesy są nie zakończone, zatem zakleszczone: ∀Pi: (K [i] = false ⇒ Pi jest zakleszczony).
Jeśli wszystkie procesy udało się doprowadzić do zakończenie (∀Pi : K [i] = true) nie ma zakleszczenia.
Jak wynika z opisu stanu, przydział nie przekracza liczby jednostek, którymi dysponuje system. Żaden z procesów nie przekracza też tej liczby w swoich żądaniach.
Roboczy wektor W początkowo przechowuje wolne jednostki poszczególnych typów zasobów. Liczba wolnych jednostek wystarczająca jest dla zrealizowania żądania procesu P3. W przypadku pozostałych procesów brakuje jednostek któregoś zasobu. Dla procesu P1 brakuje jednostek zasobu Z1, a dla procesów P2 i P4, jednostek zasobu Z3. Po zakończeniu procesu P3 przydzielone mu jednostki trafiają do systemu i do dyspozycji zarządcy są odpowiednio 2, 2, 1 jednostki. Taka liczba jest wystarczająca dla procesu P4, ale uzyskany po jego zakończeniu stan wolnych jednostek (odpowiednio 2, 4, 2) nie wystarczy ani dla procesu P1 (z mało jednostek zasobu Z1), ani dla procesu P2 (za mało jednostek zasobu Z3). Procesy P1 i P2 są więc zakleszczone.
Redukcja grafu przydziału jest metodą uniwersalną — nadaje się do stosowania w przypadku zasobów odzyskiwalnych i nieodzyskiwalnych, jak również w systemach, gdzie współistnieją zasoby obu tych klas. Redukowalność grafu jest też używana czasami w definicjach stanu zakleszczenia.
Redukcja polega na usuwaniu wierzchołków procesów wraz z incydentnymi krawędziami w tych przypadkach, w których żądania procesu można zrealizować. Usunięcie wierzchołka procesu oznacza zwolnienie jednostek zasobów odzyskiwalnych i utworzenie w odpowiedniej liczbie jednostek zasobów nieodzyskiwalnych.
Przykład pokazuje redukcję grafu zasobów odzyskiwalnych. Zamówienie procesu P2 może być zrealizowane, więc odpowiedni wierzchołek ulega redukcji. Po zredukowaniu P2, jednostka zasobu Z1 staje się wolna i można zredukować P1. W wyniku redukcji nie pozostał żaden proces, więc nie ma zakleszczenia.
Jak już wspomniano w poprzednim module, problem sprawiają czasami zasoby nieodzyskiwalne. Przykład powyższy był już analizowany, a wynikiem była niejednoznaczność co do zakleszczonych procesów. Interpretacja wyniku redukcji nastręcza tych samych problemów. Redukując przez P1 nie da się zredukować procesów P2 i P4 , a redukując przez P2 nie da się zredukować P1 i P3.
Likwidacja zakleszczenia polega na powiększeniu przydziału zasobowego pewnych procesów, kosztem innych. W ten sposób przynajmniej część procesów uda się zakończyć. W celu odzyskania zasobów, przetrzymujące je procesy można usunąć z systemu. Tracony jest wówczas cały efekt dotychczasowego przetwarzania i to jest zasadniczy koszt tego podejścia. Najlepiej usunąć procesy, które tworzą cykl. Sam wybór procesu może być uzależniony od czasu działania w systemie (im dłużej proces działa, tym potencjalnie więcej jest do stracenia) lub priorytetu procesu. Nie ma natomiast sensu usuwać procesów, które są wprawdzie zakleszczone, ale nie współtworzą cyklu, gdyż żaden z zakleszczonych procesów nie czeka na przetrzymywane przez nie zasoby. W skrajnym przypadku można usunąć wszystkie zakleszczone procesy.
Alternatywą dla usuwania procesów jest odbieranie zasobów. Z odbieraniem zasobów wiąże się problem odtworzenia stanu. Jeśli stan zasobu jest istotny dla przetwarzania procesu, należy stan ten zapamiętać, albo ponowić ciąg instrukcji zmierzających do osiągnięcia tego stanu. Zapamiętanie stanu zasobu jest mniej lub bardziej kłopotliwe w zależności od rodzaju zasobu, a dokładniej od złożoności pamięciowej takiej operacji. Nie stanowi na ogół problemu zapamiętanie stanu procesora — jest to kwestia zapamiętania od kilkudziesięciu do kilkuset bajtów. Można zachować stan pamięci fizycznej pod warunkiem dostępności przestrzeni wymiany. Znaczenie bardziej kłopotliwe może być zapamiętanie stanu urządzeń wejścia-wyjścia, gdyż efekty ich pracy, widziane są na zewnątrz, a więc wymykają się spod kontroli systemu operacyjnego.
Problemem związanym z ponownym wykonaniem pewnego fragmentu przetwarzania jest uniknięcie głodzenia, czy wręcz uwięzienia, gdyż zakleszczenie może wystąpić ponownie.
W podejściach polegających na unikaniu stosowane są takie same algorytmy, jak w przypadku wykrywania, ale nie w odniesieniu do stanu bieżącego, ale do stanów osiągalnych ze stanu bieżącego. Bazując na informacji o potencjalnych przyszłych zamówieniach, przewidywany jest najgorszy możliwy stan osiągalny systemu i analizowany pod kątem wystąpienia zakleszczenia. Jeśli nie ma zakleszczenia, stan uważany jest za bezpieczny, w przeciwnym przypadku jest to stan zagrożenia. Opisywane podejście sprowadza się właśnie do unikania takich stanów.
Biorąc pod uwagę maksymalne deklaracje zasobowe poszczególnych procesów, można wyznaczyć maksymalne potrzeby zasobowe, do zaspokojenia których musi być przygotowany zarządca zasobów. Zakładając przypadek pesymistyczny, w którym pojawią się zamówienia właśnie z tymi maksymalnymi żądaniami, można stwierdzić (używając algorytmu wykrywania zakleszczenia), czy wystąpi wówczas zakleszczenie. Stwierdzenie zakleszczenia oznacza, że stan bieżący nie jest bezpieczny. W przeciwnym razie można wyznaczyć jedną lub kilka sekwencji w realizacji zamówień, w której proces wcześniejszy zwalnia po swoim zakończeniu zasoby dla procesów następnych.
Bazując na macierzowej reprezentacji stanu, można wykorzystać zaprezentowany wcześniej algorytm detekcji zakleszczenia. Jeśli stan jest bezpieczny, to kolejność, w jakiej procesy wybierane są do realizacji jest właśnie ciągiem bezpiecznym.
Z maksymalnego zapotrzebowania oraz bieżącego przydziału wynika, że proces P1 może zażądać jeszcze 5 jednostek (deklaruje 10, a 5 już ma), proces P2 może zażądać jeszcze 2 jednostek, a proces P3 jeszcze 7 jednostek. Do rozdysponowania pozostały jeszcze 3 jednostki, gdyż 9 zostało przydzielonych (5+2+2). W wariancie pesymistycznym żądań zasobowych te 3 wolne jednostki wystarczą dla procesu P2. Po zakończeniu P2 odzyskane zostaną przydzielone mu jednostki, łącznie będzie więc 5 wolnych jednostek. Taka liczba jednostek będzie wystarczająca dla P1, a po odzyskaniu przydzielonych mu jednostek ich liczba wzrośnie do 10. Oczywiście uwzględniając ograniczenia na wielkość zamówień, uzyskane jednostki muszą być wystarczające dla P3. Ciąg bezpieczny to P2, P1 , P3.
Po zrealizowaniu żądania procesu P3 stan systemu jest następujący:
W systemie pozostały 2 wolne jednostki, którymi można zaspokoić potencjalne potrzeby procesu P2. Po zakończeniu P2 liczba jednostek do rozdysponowania zwiększy się do 4, ale może się to okazać niewystarczające zarówno dla P1, jak i dla P3. Gdyby któryś z nich zażądał więcej niż 4 jednostek (co jest zgodne z ich deklaracjami), doszłoby do zakleszczenia. Zrealizowanie żądania procesu P2 wprowadza system w stan niebezpieczny. Stan ten nie oznacza jednak jeszcze zakleszczenia — jest to dopiero zagrożenie. Przy sprzyjającym zbiegu okoliczności (sprzyjającej sekwencji żądań) zakleszczenia można uniknąć.
Stosowalność algorytmu podlega tym samym ograniczeniom, o których była mowa w przypadku algorytmu wykrywania zakleszczenia, opartym na reprezentacji grafowej. Poza tym, podejścia polegające na unikaniu stosowane są dla zasobów odzyskiwalnych.
Z grafu wynika, że zarówno proces P1 jak i P2 może zażądać jednostki zasobu Z2 do realizacji przetwarzania.
Graf po lewej stronie obrazuje stan systemu po zrealizowania zamówienia procesu P1 na jednostkę zasobu Z2, a graf po prawej obrazuje stan systemu po zrealizowaniu takiego samego zamówienia na rzecz procesu P2. Nie tworząc nawet grafu oczekiwania, łatwo można dostrzec cykl w stanie systemu po lewej stronie. W przypadku pojedynczych zasobów odzyskiwalnych jest to warunek konieczny i dostateczny zakleszczenia, a więc zagrożenie (na razie, ponieważ P2 nie zażądał jeszcze jednostki zasobu Z2).
Tego ryzyka nie ma w stanie systemu po prawej. Nawet jeśli proces P1 zażąda jednostki zasobu Z2, nie będzie zakleszczenia.
Prezentowany algorytm — tzw. algorytm bankiera — jest sformalizowaną i nieco uogólnioną formą rozumowania przedstawionego we wcześniejszym przykładzie, dotyczącym ciągu bezpiecznego.
Oprócz macierzy, opisujących stan systemu, czyli C, R, A i F, oraz pomocniczych W i K, potrzebne są jeszcze macierze, związane z maksymalnymi deklaracjami zasobowymi. Deklaracje odnośnie maksymalnego zapotrzebowania procesów na jednostki zasobów poszczególnych typów, przechowywane są w macierzy D.
Macierz B = D – A. Maksymalne potrzeby odjąć bieżący przydział daje liczbę jednostek, której zażądania zarządca może się jeszcze spodziewać.
Algorytm uruchamiany jest w reakcji na złożenie zamówienia przez proces.
Najpierw następuje weryfikacja poprawności zamówienia w stosunku do deklaracji. Jeśli żądana liczba zasobów jest większa, niż nie zrealizowana część deklaracji, jest błąd przekroczenia deklarowanych ograniczeń.
Następnie sprawdzana jest dostępność żądanej liczby jednostek zasobów. Jeśli nie ma tylu jednostek, ilu żąda proces, żądanie jest oczywiście okładane do czasu zwolnienia odpowiedniej liczby jednostek przez inne procesy.
Jeśli wymagana liczba jednostek jest dostępna, następuje tymczasowa realizacja zamówienia. Jest to swego rodzaju symulacja, chociaż w prezentacji modyfikowane są wszystkie macierze, opisujące bieżący stan. Następnie sprawdza się, czy uzyskany w ten sposób stan jest bezpieczny. Jeśli jest to stan bezpieczny, zamówienie zostaje zaakceptowane (macierze są już zaktualizowane). W przypadku wykrycia zagrożenia, realizacja zamówienia jest odkładana, co wymaga wycofania zmian w opisie stanu systemu.
Sprawdzenie bezpieczeństwa polega na uruchomieniu takiego samego algorytmu, jak w przypadku detekcji zakleszczenia, przy czym zamówieniami są maksymalne potrzeby zasobowe, wynikające z deklaracji i bieżącego przydziału — czyli macierz B. Analizowany jest zatem przypadek skrajny, w którym wszystkie procesy oczekują realizacji swoich deklaracji w stopniu maksymalnym.
Wartości macierzy B wynikają z różnicy pomiędzy D i A.
System dysponuje wolnymi zasobami w liczbie: 3 jednostek zasobu Z1 oraz 3 jednostek zasobu Z2 (przydzielone jest 5 z 8). Taka liczba jest wystarczająca tylko do zaspokojenia maksymalnych potrzeb procesu P3. Jeśli jednak P3 się zakończy, zwolni przydzielone zasoby i liczba wolnych jednostek wzrośnie do 3, 4 (odpowiednio zasobu Z1 i Z2). Jak wynika z ostatniej kolumny, wystarczy to procesowi P4 lub P5. Po P4 i P5 obsłużyć można P1 i na końcu P2. Istnieją zatem 2 ciągi bezpieczne.
Przykład działania algorytmu sprawdzania bezpieczeństwa zaprezentowano na następnym slajdzie.
Roboczy wektor W początkowo przechowuje wolne jednostki poszczególnych typów zasobów, czyli 3, 3.
po zakończeniu procesu P3 : 3+0=3, 3+1=4,
po zakończeniu procesu P4 : 3+1=4, 4+0=4,
po zakończeniu procesu P5 : 4+0=4, 4+2=6,
po zakończeniu procesu P1 : 4+2=6, 6+2=8,
po zakończeniu procesu P2 : 8+2=8, 6+0=8.
System jest w stanie bezpiecznym, a ciąg bezpieczny to: P3 , P4 , P5, P1 , P2 (lub P3, P5, P4, P1, P2).
Tabela prezentuje stan systemu po przydzieleniu jednej jednostki zasobu Z1 procesowi P2 . Zmieniła się liczba wolnych jednostek oraz maksymalne potrzeby procesu P2. Zamówienie takie można zrealizować, pod warunkiem, że zaprezentowany stan jest bezpieczny.
Przykład działania algorytmu sprawdzania bezpieczeństwa zaprezentowano na następnym slajdzie.
Roboczy wektor W początkowo przechowuje wolne jednostki poszczególnych typów zasobów, czyli 2, 3.
po zakończeniu procesu P3 : 2+0=2, 3+1=4,
po zakończeniu procesu P4 : 2+1=3, 4+0=4,
po zakończeniu procesu P5 : 3+0=3, 4+2=6
Dla procesów P1 i P2 brakuje jednostek zasobu Z1 . Stan nie jest bezpieczny. Przy maksymalnych deklarowanych żądaniach zasobowych jednostek wystarczy tylko dla procesów P3 , P4 i P5.
Zgodnie z zasadą unikania zakleszczenia, nie można zrealizować zamówienia procesu P2.