Warunki konieczne wystąpienia zakleszczenia

Warunki konieczne wystąpienia zakleszczenia


Jednoczesne zaistnienie wszystkich warunków koniecznych nie musi oznaczać wystąpienia zakleszczenia. Niespełnienie natomiast któregoś z tych warunków oznacza brak ryzyka zakleszczenia, co jest podstawą metod zapobiegania zakleszczeniom.

  • Wzajemne wykluczanie — przynajmniej jeden zasób musi być niepodzielny, czyli używanie egzemplarza tego zasobu przez jeden proces uniemożliwia używanie go przez inny proces do czasu zwolnienia.
  • Przetrzymywanie i oczekiwanie — proces, któremu przydzielono jakieś jednostki, oczekuje na dodatkowe jednostki blokowane przez inny proces.
  • Brak wywłaszczeń — jednostki zasobu zwalniane są tylko z inicjatywy odpowiednich procesów.
  • Cykl w oczekiwaniu — istnieje podzbiór {P1 ,...., Pk} ⊆ P taki, że P1, czeka na jednostkę zasobu przetrzymywaną przez P2, P2 na jednostkę przetrzymywany przez P3 ,..., Pk czeka na jednostkę przetrzymywany przez P1.

Warunki konieczne w odniesieniu do zasobów nieodzyskiwalnych


  • Wzajemne wykluczanie — jednostka zasobu może być zużyta przez jeden proces.
  • Przetrzymywanie i oczekiwanie — w stanie oczekiwania proces nie produkuje jednostek zasobów.
  • Brak wywłaszczeń — nie można zmusić procesu do wyprodukowania jednostki zasobu lub zrobić to za niego.
  • Cykl w oczekiwaniu — istnieje podzbiór {P1 ,...., Pk} ⊆ P taki, że P1, czeka na wyprodukowanie jednostki zasobu przez P2, P2 czeka wyprodukowanie jednostki przez P3 ,..., Pk czeka na wyprodukowanie jednostki przez P1.

Reprezentacja stanu systemu — graf przydziału zasobów odzyskiwalnych


Graf przydziału zasobów jest wygodną formą graficzną reprezentacji stanu sytemu na potrzeby analizy zjawisk związanych z zakleszczeniem. Poza tym można wykazać na podstawie pewnych własności tego grafu, że wystąpił pewien szczególny stan, np. właśnie stan zakleszczenia lub zagrożenia, co w połączeniu z powszechnie znanymi algorytmami analizy grafów ułatwia wykrywanie takich stanów.

Graf przydziału zasobów odzyskiwalnych (krótko graf zasobów odzyskiwalnych, graf przydziału lub graf alokacji) jest to skierowany graf dwudzielny, w którym jedną grupę wierzchołków tworzą procesy, a drugą zasoby. Krawędzie skierowane od procesów do zasobów reprezentują zamówienia, a krawędzie skierowane od zasobów (ich jednostek) do procesów reprezentują przydział.

  • Zbiór wierzchołków obejmuje procesy (reprezentowane przez kółka) i zasoby (reprezentowane przez prostokąty) czyli W= P ∪ Z.
  • Egzemplarze danego zasobu reprezentowane przez kropki wewnątrz prostokąta.
  • Zbiór skierowanych krawędzi (łuków) obejmuje
    • krawędzie zamówienia (ang. request edge) PiZj
    • krawędzie przydziału (ang. assignment edge) ZjPi

Przykład grafu zasobów odzyskiwalnych


Przedstawiony graf reprezentuje stan systemu z dwoma procesami P1 i P2 oraz dwoma rodzajami zasobów: Z1 i Z2 . Zasób Z1 składa się z jednego egzemplarza a zasób Z2 z dwóch. Krawędź skierowana od jednostki zasobu Z2 do wierzchołka procesu P1 oznacza, że jednostka ta przydzielona jest procesowi P1. Podobnie druga jednostka zasobu Z2 przydzielona jest procesowi P2. Jedyna jednostka zasobu Z1 przydzielona jest procesowi P2. Z faktu, że żadna krawędź skierowana nie wychodzi z wierzchołka procesu P2, wynika, że nie potrzebuje on innych zasobów do kontynuacji przetwarzania. Krawędź skierowana od wierzchołka proces P1 do wierzchołka zasobu Z1 oznacza zamówienie procesu P1 na jednostkę zasobu Z1. Ponieważ nie ma wolnej jednostki zasobu Z1, proces P1 musi czekać na jej zwolnienie.

slajd 10

Zdarzenia w systemie z zasobami odzyskiwalnymi


Jak wspomniano przy omawianiu współbieżności, stan systemu zmienia się pod wpływem zdarzeń, związanych z działaniem procesów. Z punktu widzenia zagadnień związanych z realizacją dostępu do zasobów istotne są zdarzenia: zamówienia jednostki zasobu, nabycia zamówionej jednostki i zwolnienia nabytej jednostki. Zamówienie oraz zwolnienie są zdarzeniami, które wynikają z przetwarzania procesu. Nabycie jest zdarzeniem w procesie Pi , którego wystąpienie uwarunkowane jest dostępnością jednostek zasobu. Brak wolnych jednostek uniemożliwia zajście tego zdarzenia i powoduje wstrzymanie (zablokowanie) procesu.

  • Zamówienie (ang. request) jednostki zasobu przez procesu Pi — ri
  • Nabycie (ang. acquisition) jednostki zasobu przez proces Pi — ai
  • Zwolnienie (ang. release) jednostki zasobu przez proces Pi — di

Zmiana stanu systemu a graf zasobów odzyskiwalnych


Skutkiem wystąpienia zdarzenia w systemie jest zmiana stanu i związana z tym transformacja grafu przydziału.

Jeśli zawsze zamawiana jest jedna jednostka zasobu, w grafie zasobów odzyskiwalnych występuje zawsze pojedyncza krawędź zamówienia. Mówi się wówczas o żądaniach pojedynczych.

W przypadku żądania kilku jednostek w jednym zamówienia możne wystąpić kilka równoległych krawędzi zamówienia.

  • W wyniku zamówienia jednostki zasobu Zj przez proces Pi w grafie pojawia się krawędź zamówienia PiZj.
  • Realizacja zamówienia może nastąpić wówczas, gdy są wolne jednostki żądanego zasobu, a jej wynikiem jest zmiana kierunku krawędzi żądania, tym samym zamiana na krawędź przydziału ZjPi
  • W wyniku zwolnienia jednostka zasobu jest odzyskiwana przez system a krawędź przydziału znika.

Przykład przejść pomiędzy stanami w przypadku zasobów odzyskiwalnych


W pierwszym z przedstawionych stanów dopuszczalne jest zdarzenie zwolnienia jednostek zasobów przydzielonych procesowi P2 , gdyż proces P1 jest wstrzymany ze względu na niedostępność jednostki zasobu Z1 . Zakładając, że jednostki zwalniane są pojedynczo i najpierw zwolniona zostaje jednostka zasobu Z1 , uzyskujemy następny stan reprezentowany przez kolejny graf przydziału. W stanie tym dopuszczalne są już dwa zdarzenia:

  • zwolnienie jednostki zasobu Z2 przez proces P2,
  • nabycie jednostki zasobu Z1 przez proces P1.

Niezależnie od tego, które z wymienionych zdarzeń zajdzie jako pierwsze, w osiągniętym stanie dopuszczalne jest drugie zdarzenie. Transformację można by więc kontynuować aż do osiągnięcia stanu zwolnienia wszystkich jednostek zasobów Z1 i Z2 , przechodząc przez różne stany pośrednie, zależnie od kolejności zdarzeń dopuszczalnych. Narysowanie całej takiej sieci przejść pozostawia się jako ćwiczenie.

slajd 13

Przykład przejść procesu w systemie z dwoma jednostkami zasobu


Przedstawiony przykład obrazuje funkcjonowanie procesu w systemie z dwoma jednostkami zasobu odzyskiwalnego. Proces Pi, ubiegając się o jednostki zasobu, zmieniają swój stan. Możliwe stany procesu są następujące:

  • si0 — stan, w którym proces nie ma przydzielonej żadnej jednostki zasobu i żadnej nie żąda,
  • si1 — stan, w którym proces nie ma jeszcze przydzielonej żadnej jednostki zasobu, ale zamówił jedną jednostkę,
  • si2 — stan, w którym proces ma przydzieloną jedną jednostkę zasobu i niczego więcej nie żąda,
  • si3 — stan, w którym proces ma przydzieloną jedną jednostkę zasobu i zażądał drugą,
  • si4 — stan, w którym proces ma przydzielone dwie jednostki zasobu.

W stanie si4 proces nie może zażądać kolejnej jednostki, ponieważ przekroczyłby możliwości systemu. Może natomiast zwolnić jedną jednostkę, wracając do stanu si2. W stanie si2 również może zwolnić jedną jednostkę. W stanie si2 dopuszczalne są więc dwa zdarzenia — zwolnienie jednostki lub zamówienie następnej.

slajd 14

Przykład przejść dwóch procesów w systemie z dwoma jednostkami zasobu


Przykład kolejny obrazuje funkcjonowanie dwóch procesów — Pi oraz Pj, rywalizujących o zasoby. Zmiany stanu procesu Pi pokazane są w poziomie, a procesu Pj w pionie. Stan systemu, na który składa się stan sik proces Pi oraz stan sjl procesu Pj, oznaczony został jako σkl.

Wobec rywalizacji dwóch procesów o zasoby pewne stany jednego procesu są nieosiągalne, jeśli określony stan osiągnął drugi proces. Na przykład: stan σ42 oznaczałby, że proces Pi ma przydzielone dwie jednostki zasobu, a Pj — jedną jednostkę, podczas gdy system dysponuje w sumie dwoma jednostkami.

slajd 15

Na slajdzie przedstawiona jest kontynuacja grafu przejść między stanami, przy czym dla poprawy czytelności zrobiona została „zakładka”, polegająca na powtórzeniu stanów σ02, σ12, σ22, σ32, które pojawiły się również na slajdzie poprzednim.

slajd

Definicja zakleszczenia procesu


Na bazie rozważanego modelu przetwarzania współbieżnego zdefiniowane zostanie zakleszczenie procesu. Wcześniej jednak wymagane jest zdefiniowanie wstrzymania procesu.

Przykładem stanu systemu, w którym wstrzymany jest proces Pi jest σ32 w poprzednim przykładzie. Jedyne dopuszczalne zdarzenia w tym stanie związane są z procesem Pj , który może zwolnić przydzieloną jednostkę, albo zażądać następnej. W stanie σ41 zablokowany jest z kolei proces Pj , gdyż zażądał on pierwszej jednostki zasobu, podczas gdy obie przydzielone są procesowi Pi. Pj musi więc czekać na zwolnienie przynajmniej jednej z jednostek przez Pi.

Przykładem zakleszczenia z kolei jest stan σ33, w którym żadne zdarzenie nie jest dopuszczalne. Jest to zatem zakleszczenie obu procesów, czyli całego systemu.

Przydział natychmiastowy


Odnosząc zjawisko zakleszczenia do grafu przydziału, należy wyodrębnić pewne własności tego grafu, ułatwiające stwierdzenie stanu zakleszczenia.

Własnością systemu, która przejawia się w grafie przydziału, podlegającym analizie, jest natychmiastowość przydziału. Oznacza ona, że jeśli zamawiane egzemplarze zasobu są dostępne (wolne), to są przydzielane bez żadnej zwłoki. Stan systemu, w którym przydzielono wszystkie dostępne egzemplarze, zamówione przez procesy, określany będzie jako zupełny (ang. expedient). Graf przedstawiony na slajdzie nie reprezentuje takiego stanu, gdyż jedna z dwóch jednostek zasobu Z2 pozostaje wolna, a ubiegają się o nią dwa procesy.

slajd 18