Rozwiązywanie problemu zakleszczenia

Podejścia do zakleszczenia w przypadku zasobów odzyskiwalnych


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ć:

  • usunięcie procesu i zwolnienie wszystkich przydzielonych mu zasobów,
  • wywłaszczenie, czyli odebranie tych zasobów, których potrzebują inne procesy.
  • Zignorowanie problemu — zakleszczenie traktowane jest jako awaria systemu.
  • Zapobieganie zakleszczeniom — przeciwdziałanie powstaniu któregoś z warunków koniecznych.
  • Unikanie zakleszczeń — utrzymywanie rezerwy wolnych zasobów, umożliwiających bezpieczne zakończenie procesów.
  • Wykrywanie i likwidowanie zakleszczeń — dopuszczenie do zakleszczenia, ale wykrywanie i usuwanie takich stanów przez odzyskanie zasobów, niezbędnych do zakończenia zadań przez (niektóre) procesy.

Podejścia do zakleszczenia w przypadku zasobów zużywalnych


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ę.

  • Zignorowanie problemu — zakleszczenie traktowane jest jako awaria systemu.
  • Zapobieganie zakleszczeniom — przeciwdziałanie powstaniu któregoś z warunków koniecznych.
  • Wykrywanie i likwidowanie zakleszczeń — dopuszczenie do zakleszczenia, ale wykrywanie takich stanów i usuwanie zakleszczonych procesów.

Reprezentacja stanu systemu


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.

  • Graf
    • graf przydziału zasobów
    • graf oczekiwania (ang. wait-for graph)
  • Macierze
    • opis zasobów systemu
    • opis stanu przydziału jednostek
    • opis żądań procesów
    • opis deklaracji procesów odnośnie maksymalnych żądań zasobowych

Transformacja grafu przydziału do grafu oczekiwania


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.

slajd 6

Grafowa reprezentacja stanu — wykrywanie zakleszczenia


  • Wykrycie zakleszczenia polega na stwierdzeniu — w zależności od charakterystyki zasobów oraz zamówień procesów — cyklu lub supła w grafie oczekiwania.
  • Zależności pomiędzy własnościami grafu oczekiwania a stanem zakleszczenia są takie, jak zostało to określone dla grafu przydziału zasobów.
  • Podejście bazujące na grafowej reprezentacji stanu systemu jest ograniczone do szczególnych przypadków, wyszczególnionych w odniesieniu do grafu przydziału zasobów w poprzednim module.

Macierzowa reprezentacja stanu systemu


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).

  • C — m-elementowy wektor liczebności zasobów systemu
    • C[j] — całkowita liczba jednostek zasobu Zj, zarządzanych przez system
  • R — macierz n × m zamówień procesów
    • R[ij]< — liczba jednostek zasobu Zj zamówiona i oczekiwana przez proces Pi
  • A — macierz n × m przydzielonych jednostek zasobów
    • A[ij] — liczba jednostek zasobu Zj przydzielona procesowi Pi
  • F— m-elementowy wektor wolnych jednostek
    • F[j] — liczba jednostek zasobu Zj pozostających w dyspozycji systemu (nie przydzielona procesom)

Integralność macierzowej reprezentacji stanu systemu


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.

slajd 9

Macierzowa reprezentacja stanu — zakleszczenie


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.

Macierzowa reprezentacja stanu — wykrywanie zakleszczenia


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.

  • W— m-elementowy wektor liczby wolnych jednostek zasobów, uwzględniający jednostki zwrócone do systemu przez procesy, które mogą się zakończyć W[j]— liczba jednostek zasobu do rozdysponowania
  • K — n-elementowy wektor wartości logicznych, informujący o odzyskaniu zasobów procesu K[i] — wartość logiczna informująca, że proces Pi zwrócił do systemu przydzielone mu jednostki zasobów

Macierzowa reprezentacja stanu — wykrywanie zakleszczenia


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.

slajd 12

Przykład działania algorytmu wykrywania 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.

slajd 13

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.

slajd 14

Redukcja grafu przydziału


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.

  • Jeśli nie istnieje taki proces Pi którego żądania zasobowe mogą zostać zaspokojone przez dostępne jednostki zasobów, przejście do punktu
  • Usunięcie wierzchołka procesu Pi
  • Zwolnienie wszystkich jednostek zasobów odzyskiwalnych, przetrzymywanych przez proces PiPi
  • Przejście do punktu 1
  • Jeśli pozostały nie usunięte procesu, to są one zakleszczone.

Przykład redukcji grafu przydziału


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.

slajd 16

Problem redukcji grafu zasobów nieodzyskiwalnych


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.

slajd 17

Likwidowanie zakleszczenia


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.

  • Zakończenie procesu
    • zakończenie wszystkich zakleszczonych procesów
    • usuwanie procesów pojedynczo, aż do wyeliminowania cyklu zakleszczenia,
  • Wywłaszczenie zasobów (zabieranie zasobów procesom)
    • wybór ofiary — które zasoby i komu odebrać
    • wycofanie — w jakim stanie pozostawić proces, któremu odebrano zasoby
    • głodzenie — w jaki sposób zagwarantować, że nie dojdzie do głodzenia procesu

Unikanie zakleszczeń


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.

  • Wymagana jest dodatkowa informacja o tym, jakie zasoby będą zamawiane przez proces.
    • W najprostszym przypadku jest to maksymalna liczba jednostek poszczególnych zasobów, niezbędna do zakończenia zadania przez proces.
  • Przy każdym zamówieniu zarządca decyduje, czy można je zrealizować, czy należy wstrzymać realizację, biorąc pod uwagę aktualny stan zasobów.
    • W przypadku zadeklarowania maksymalnej liczby jednostek zasobów system musi zapewnić, że nie dojdzie do cyklu w oczekiwaniu na zasoby.

Stan bezpieczny


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.

  • Stan systemu jest bezpieczny, jeśli istnieje porządek przydziału zasobów żądającym tego procesom (nawet w stopniu maksymalnym), gwarantujący uniknięcie zakleszczenia.
  • Formalnie: system jest w stanie bezpiecznym, jeśli istnieje ciąg bezpieczny, czyli taki ciąg procesów (P1, P2 ..... Pn), że w danym stanie przydziału zasobów zapotrzebowanie procesu Pi może być zaspokojone przez bieżąco dostępne zasoby oraz zasoby użytkowane przez wszystkie proces poprzedzające go w ciągu, czyli procesy Pj, gdzie j < i.

Przykład stanu i ciągu bezpiecznego


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:

  • P1 ma przydzielone 5 jednostek, może potrzebować jeszcze 5,
  • P2 ma przydzielone 2 jednostki, może potrzebować jeszcze 2,
  • P3 ma przydzielone 3 jednostki, może potrzebować jeszcze 3.

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ąć.

Grafowa reprezentacja stanu — unikanie zakleszczenia


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.

  • W celu uwzględnienia potencjalnych żądań, w grafie przydziału zasobów wprowadza się dodatkową krawędź deklaracji, wskazującą że proces może zamówić egzemplarz zasobu do realizacji zadania.
  • Gdy proces zamawia zasób, krawędź deklaracji zamieniana jest na krawędź zamówienia, a gdy go zwalnia, ale się nie kończy, krawędź przydziału zamieniana jest na krawędź deklaracji.
  • Zamówienie może być zrealizowane, gdy zamiana krawędzi zamówienia na krawędź przydziału nie spowoduje cyklu lub supła (zależnie od charakterystyki systemu) w grafie oczekiwania, uwzględniającym krawędzie deklaracji.

Graf przydziału z krawędziami deklaracji


Z grafu wynika, że zarówno proces P1 jak i P2 może zażądać jednostki zasobu Z2 do realizacji przetwarzania.

slajd 23

Grafowa reprezentacja stanu — zagrożenie


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.

slajd 24

Macierzowa reprezentacja stanu — unikanie 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.

  • Przed rozpoczęciem realizacji zadania proces musi zadeklarować maksymalną liczbę jednostek poszczególnych typów zasobów, których może potrzebować.
  • Na podstawie deklaracji i bieżącego stanu systemu zarządca musie rozstrzygnąć, czy przydział zasobów pozostawi system w stanie bezpiecznym. Jeśli tak, to zasoby mogą zostać przydzielone, a jeśli nie, to proces musi poczekać.

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ć.

  • D — macierz o wymiarach n × m określająca maksymalne zapotrzebowanie poszczególnych procesów na poszczególne zasoby
  • B — macierz o wymiarach n × m określająca zapotrzebowanie poszczególnych procesów na poszczególne zasoby, które jest jeszcze do zrealizowania (nie wykorzystana jeszcze część deklaracji)

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.

slajd 27

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.

slajd 28

Przykład działania algorytmu


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.

slajd 29

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).

slajd 30

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.

slajd 31

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.

slajd 32