Przeciwdziałanie zakleszczeniu

Zasadniczo można wyróżnić dwa rodzaje podejść do rozwiązania problemu zakleszczenia. Jedno polega na niedopuszczeniu do powstania zakleszczenia, drugie dopuszcza zakleszczenie, ale jego istotą jest wykrywanie (detekcja, ang. deadlock detection) i usuwanie tego stanu. Niedopuszczenie do zakleszczenia sprowadza się do zapobiegania (ang. deadlock prevention) lub unikania (ang. deadlock avoidance). Zapobieganie jest metodą dość zachowawczą, polegającą na przeciwdziałaniu zajściu jednego z warunków koniecznych wystąpienia zakleszczenia. Unikanie jest z kolei metodą pośrednią pomiędzy zapobieganiem a detekcją. Jej istotą jest przewidywanie przyszłych zdarzeń w systemie i sprawdzanie, czy w osiągalnych stanach występuje zakleszczenie. Stosuje się przy tym takie same metody, jak w przypadku wykrywania. Jeśli stan zakleszczenia jest osiągalny, to mamy do czynienie ze stanem niebezpiecznym (stanem zagrożenia), którego należy unikać, realizując żądania procesów. Przewidywanie przyszłych zdarzeń wymaga jednak pewnych przesłanek. Najczęściej muszą być znane maksymalne potencjalne potrzeby zasobowe współpracujących procesów.

Algorytmy wykrywania zakleszczenia, omawiane w tym module, opierają się na dwóch reprezentacjach stanu systemu, macierzowej i grafowej. Reprezentacja w postaci grafu przydziału zasobów została już omówiona w poprzednim module. Tutaj zostanie jedynie omówiona reprezentacja uproszczona w postaci grafu oczekiwania. Zostanie też omówiona reprezentacja macierzowa, oparta na wektorach i macierzach, zorientowana przede wszystkim na aspekty ilościowe w dostępności procesów do zasobów.

  • Wykrywanie zakleszczenia
  • Usuwanie zakleszczenia
  • Unikanie zakleszczeń
  • Zapobieganie zakleszczeniom

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

Podejście hybrydowe do rozwiązywania problemu zakleszczenia

Zapobieganie zakleszczeniom — wzajemne wykluczanie


Zapobieganie, podobnie jak unikanie, jest podejściem polegającym na niedopuszczaniu do zakleszczenia. W przeciwieństwie do unikania, decyzja o akceptacji lub odłożeniu realizacji zamówienia podejmowana jest wyłącznie w oparciu o bieżący stan systemu. Nie są tu uwzględniane żadne dane na temat przyszłych zachowań procesów. Podejście takie musi być zatem bardziej zachowawcze — w większym stopniu i często nadmiarowo ograniczające aktywność procesów.

Zapobieganie polega na kontrolowaniu zaistnienia warunków koniecznych. Wystarczy nie dopuścić do spełnienia jednego z nich, a nie dojdzie do zakleszczenia.

Ze względu na sposób korzystania z niektórych zasobów nie można podjąć żadnych kroków w celu przeciwdziałania warunkowi wzajemnego wykluczania.

  • Konieczność zagwarantowania wzajemnego wykluczania wynika z charakterystyki zasobu — wzajemne wykluczanie musi być zachowane w przypadku dostępu do zasobów niepodzielnych.
  • Zasoby współdzielone nie wymagają dostępu w trybie wyłącznym, więc używanie zasobu przez jeden proces nie blokuje dostępu do niego innym procesom.

Zapobieganie zakleszczeniom — przetrzymywanie i oczekiwanie


Podejście ma wiele wad. Uzyskanie wszystkich zasobów przed rozpoczęciem przetwarzania może oznaczać przetrzymywanie zasobów, które przez długi czas nie będą wykorzystywane (np. rezerwacja przestrzeni dyskowej dla stopniowo powiększanego pliku). W konsekwencji mamy do czynienia ze słabym wykorzystaniem zasobów, blokowanie dostępu innym procesom i tym samym zmniejszenie przepustowości systemu.

Sama realizacja praktyczna tego podejścia może być kłopotliwa, gdyż na początku przetwarzania wymagana jest wiedza o zasobach, niezbędnych do realizacji całego przetwarzania, podczas gdy pewne potrzeby ujawniają się dopiero w trakcie samego przetwarzania (np. zapotrzebowanie na dynamicznie alokowaną pamięć, czy przestrzeń dyskową).

Problemem może też być głodzenie procesu ze względu na fakt, że nigdy nie będą jednocześnie dostępne wszystkie zasoby żądane przez proces.

  • Przeciwdziałanie warunkowi przetrzymywania i oczekiwania polega na uniemożliwieniu procesowi zamawiania zasobów w czasie, gdy proces sam przetrzymuje jakieś zasoby i blokuje do nich dostęp.
  • Metoda 1: proces musi zamówić i uzyskać wszystkie zasoby, zanim rozpocznie realizację zadania, do którego zasoby te są potrzebne.
  • Metoda 2: przed zamówieniem dodatkowych zasobów proces musi zwolnić zasoby przydzielone dotychczas (ewentualnie zamówić je ponownie łącznie z nowymi zasobami).

Zapobieganie zakleszczeniom — brak wywłaszczeń


Wywłaszczenie musi zostać zrealizowane we właściwym momencie. Sensowny jest moment, kiedy proces zamawia zasób, ale zasób ten nie jest natychmiast dostępny. Zwalniane są wówczas zasoby przez niego przetrzymywane (od tego momentu są wolne) i dopisywane do bieżącego zamówienia. Wznowienie procesu nastąpi po zrealizowaniu całego zamówienia.

Inny dogodny moment ma miejsce, kiedy proces zamawia zasób, który jest przetrzymywany przez inny oczekujący proces. Zasób ten (lub zasoby) jest wówczas odbierany procesowi oczekującemu i przydzielany zamawiającemu. Jeśli zasób nie jest dostępny, ale jest przetrzymywany przez proces nie zablokowany w oczekiwaniu (domniemamy, że proces działa i używa tego zasobu), proces zamawiający sam przechodzi w stan oczekiwania. W stanie oczekiwania proces może stracić swoje zasoby, o ile pojawią się żądania od inny procesów. Wznowienie procesu następuje po odzyskaniu zasobów utraconych w czasie oczekiwania i uzyskaniu zasobów nowo zamawianych.

  • Dopuszczenie wywłaszczeń oznacza możliwość odebrania procesowi zasobu.
  • Metoda 1: zwolnienie zasobów procesu w momencie zamówienia dodatkowych zasobów, przetrzymywanych przez inne procesy.
  • Metoda 2: odbieranie żądanych zasobów przetrzymującym je procesom, gdy procesy te są w stanie oczekiwania na inne zasoby.

Zapobieganie zakleszczeniom — cykl w oczekiwaniu


Wcześniejsze warunki konieczne związane są z projektem systemu lub charakterystyką zasobów. Cykl wynika natomiast z funkcjonowania samych procesów aplikacyjnych, więc znaczenie łatwiej można to kontrolować. Przeciwdziałanie cyklowi jest więc najczęściej stosowaną metodą zapobiegania zakleszczeniom.

Opisana metoda wymaga, żeby jednostki zasobów, oznaczone tym samym numerem, zamawiane były w jednym zleceniu dla zarządcy.

  • W celu przeciwdziałania cyklowi w oczekiwaniu procesów na zasoby, należy zapewnić, że wszystkie zasoby będą zamawiane w tej samej dla wszystkich procesów kolejności.
  • Metoda: nadanie unikalnych numerów wszystkim typom zasobów, czyli odwzorowanie zbiorów f : Z → N, i zamawianie zasobów zgodnie z zasadą: f(Zj) > f(Zi) ⇒ jednostka (lub jednostki) zasobu Zj są zamawiane po zrealizowaniu zamówienia na jednostki zasoby Zi,
  • Inaczej: nie można zamawiać jednostek zasobu Zi jeśli są przydzielone jednostki zasobu Zj gdy f(Zj) ≥ f(Zi) .

Łączenie metod postępowania z zakleszczeniami


Ze względu na różnice w charakterystyce zasobów, pewne metody można stosować w przypadku określonych rodzajów zasobów, ale nie można w przypadku innych rodzajów. Przykłady tego typu przewijały się w omawianych podejściach do rozwiązywania problemu zakleszczenia. Podejście zintegrowane polega na tym, żeby zasoby o podobnej charakterystyce łączyć w grupy, a liniowe uporządkowanie grup z kolei ułatwia przeciwdziałanie cyklowi przy alokacji.

  • W zależności od rodzaju zasobu systemu komputerowego stosowane są różne metody postępowania.
  • Zasoby dzieli się na liniowo uporządkowane grupy. Żądania procesów realizowane są w kolejności wynikającej z porządku grup, w których znajdują się żądane zasoby.
  • W obrębie zasobów w danej grupie stosowana jest właściwa dla tej grupy strategia realizacji żądań.

Przykład grup zasobów


  • Pamięć pomocnicza — obszary pamięci w strefie wymiany na dysku
  • Zasoby zadania — pliki, urządzenia itp.
  • Pamięć główna — obszary pamięci w obrębie fizycznej przestrzeni adresowej
  • Zasoby wewnętrzne — zasoby używane przez system do zarządzania procesami (np. bloki kontrolne, kanały wejścia-wyjścia)

Przykład metod w obrębie grup zasobów


  • Wstępny przydział w przypadku pamięci pomocniczej jest możliwy, gdyż wymagany rozmiar obrazu procesu jest na ogół znany w momencie ładowania programu do pamięci.
  • Zapotrzebowanie na pliki i urządzenia może być znane z góry (np. w systemach wsadowych).
  • O możliwości wywłaszczenia pamięci fizycznej wspomniano już przy usuwaniu zakleszczenia.
  • Zasoby wewnętrzne można uporządkować np. zgodnie z adresem w pamięci.