Graf przydziału zasobów i graf oczekiwania oraz ich własności

Własności grafów


Rozważmy graf składający się z wierzchołków i łuków, rozumianych jako uporządkowane pary wierzchołków. Podstawą definiowania istotnych dla zakleszczenia własności jest osiągalność wierzchołków. Wierzchołek u jest osiągalny z wierzchołka v wtedy i tylko wtedy, gdy istnieje w grafie skierowanym ścieżka rozpoczynająca się w wierzchołku v a kończąca w wierzchołku u.

Cykl w grafie oznacza, że istnieje ścieżka rozpoczynająca się i kończąca w tym samym wierzchołku, czyli jakiś wierzchołek jest osiągalny z samego siebie.

Supeł w grafie oznacza podzbiór wierzchołków, w którym każdy wierzchołek jest osiągalny z każdego innego, a jednocześnie z żadnego z tych wierzchołków nie jest osiągalny wierzchołek poza supłem. Jak łatwo zauważyć, supeł implikuje cykl.

slajd 19

Przykład cyklu w grafie


W przedstawionym grafie jest cykl, obejmujący wierzchołki v2, v3 i v4. Nie ma tu natomiast supła, gdyż żaden wierzchołek nie jest osiągalny z wierzchołka v5, w związku z czym wierzchołek v5 nie może należeć do supła, ale wierzchołek v5 jest osiągalny z każdego innego wierzchołka.

slajd 20

Przykłady supła w grafie


W obu przedstawionych przykładach jest supeł. W przykładzie pierwszym obejmuje on wszystkie wierzchołki. W przykładzie drugim supeł tworzą wierzchołki v2, v3 i v4.

slajd 21

Cykl w grafie przydziału — zakleszczenie


Przedstawiony graf reprezentuje stan systemu, w którym wystąpiło zakleszczenie. Każdy z procesów czeka na jakąś jednostkę zasobu Z1 lub Z2 , która jest zajęta przez inny proces. Nie ma jednak w systemie procesu, który mógłby się zakończyć, bo żaden nie ma wszystkich żądanych jednostek. Cechą szczególną grafu, reprezentującego ten stan jest cykl (P1Z1P2Z2 ).

W tym grafie występuje również supeł.

slajd 22

Cykl w grafie przydziału — brak zakleszczenia


W grafie przedstawionym na slajdzie również jest cykl, obejmujący te same procesy i zasoby, co na poprzednim slajdzie. Różnica polega na tym, że występują dwie jednostki zasobu Z2, z których jedna przydzielona jest procesowi P3. Proces P3 ma zatem (na razie) przydzielone niezbędne egzemplarze (właściwie jeden egzemplarz zasobu Z2), więc być może się zakończy. Jeśli P3 niczego więcej nie zażąda i rzeczywiście się zakończy, zwolni jednostkę zasobu Z2, która będzie mogła zostać przydzielona procesowi P2. Przy takim scenariuszu, pomimo cyklu w grafie przydziału, nie dojdzie do zakleszczenia. W bieżącym stanie systemu nie można zatem stwierdzić zakleszczenia, co jednak nie wyklucza faktu, że może istnieć stan osiągalny systemu, w którym zakleszczenie wystąpi.

slajd 23

Supeł w grafie przydziału — zakleszczenie


Kontynuując analizę poprzedniego przykładu, gdyby w trakcie przetwarzania procesu P3 okazało się, że do jego zakończenia potrzebna jest dodatkowo jedna jednostka zasobu Z1 , uzyskujemy stan przedstawiony na slajdzie. Jest to stan zakleszczenia. Interesującą własnością grafu przydziału, opisującego ten stan, jest supeł.

slajd 24

Brak supła w grafie przydziału — zakleszczenie


W grafie nie ma supła, jest tylko cykl. Proces P2 w jednym zamówieniu żąda 2 jednostek zasobu Z2. Nawet gdyby P3 się zakończył i zwolnił przydzieloną mu jednostkę zasobu Z2, i tak nie wystarczy to do zaspokojenia żądań pozostałych procesów. Wystąpiło więc zakleszczenie.

Przykład jest podobny do poprzedniego, ale proces P2 jednocześnie żąda jednostek dwóch różnych zasobów Z2 i Z3. Tak jak w poprzednim przypadku, nawet gdyby P3 się zakończył i zwolnił przydzieloną mu jednostkę zasobu Z2, i tak nie odblokuje to procesu P2, bo cały czas niedostępna jest jednostka zasobu Z3. Również występuje tu zakleszczenie.

slajd 26

Własności grafu zasobów odzyskiwalnych a stan zakleszczenia


Spostrzeżenia z poprzednich przykładów są podstawą do wyciągnięcia pewnych wniosków, prezentowanych najczęściej w formie twierdzeń.

W przypadku zasobów pojedynczych (posiadających tylko jedną jednostkę) warunkiem koniecznym i dostatecznym wystąpienia zakleszczenia jest cykl w grafie przydziału. Warto podkreślić, że ze względu na liczebność egzemplarzy dopuszczalne są w tym przypadku tylko żądania pojedyncze.

W przypadku systemu, gwarantującego natychmiastowy przydział, gdy analizowany stan jest zupełny, supeł w grafie przydziału jest warunkiem dostatecznym (ale nie koniecznym ) zakleszczenia.

W przypadku zasobów, posiadających kilka jednorodnych egzemplarzy, przydzielanych natychmiastowo w wyniku pojedynczych żądań, warunkiem koniecznym i dostatecznym zakleszczenia jest supeł w grafie przydziału. Cykl w tym przypadku jest tylko warunkiem koniecznym, co wynika z faktu, że jest warunkiem koniecznym powstania supła.

  • Zasoby pojedyncze:
    • cykl ⇔ zakleszczenie
  • Przydział natychmiastowy (stan zupełny)
    • supeł ⇔ zakleszczenie
  • Zasoby reprezentowane przez wiele egzemplarzy w systemie z przydziałem natychmiastowym (w stanie zupełnym), dopuszczającym pojedyncze żądania:
    • supeł ⇔ zakleszczenie

Reprezentacja stanu systemu — graf przydziału zasobów zużywalnych


Konstrukcja grafu zasobów nieodzyskiwalnych jest niemal taka sama jak w przypadku grafu zasobów odzyskiwalnych. Różnica w stosunku do grafu zasobów odzyskiwalnych sprowadza się do interpretacji krawędzi, konkretnie krawędzi skierowanej od wierzchołka zasobu do wierzchołka procesu. Krawędź ta — nazywana krawędzią produkcji — oznacza, analogicznie do przypadku zasobu odzyskiwalnego, możliwość uwolnienia jednostki zasobu, co w tym przypadku interpretowane jest jako utworzenie takiej jednostki. W związku z tym krawędź produkcji skierowana jest od wierzchołka zasobu, a nie od kropki, reprezentującej jego egzemplarz. Poza tym, od zasobu mogą wychodzić krawędzie skierowane do różnych procesów, gdyż ten sam zasób może mieć wielu producentów. W systemie z zasobami odzyskiwalnymi też było to możliwe, jednak krawędzie wychodziły od różnych kropek, gdyż egzemplarz używany był w trybie wyłącznym.

  • 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 obejmuje
    • krawędzie zamówienia (ang. request edge) Pi → Z j
    • krawędzie utworzenia (czyli produkcji, ang. producer edge) Zj → Pi,
  • Każdy zasób musi mieć krawędź utworzenia.

Zdarzenia w systemie z zasobami nieodzyskiwalnymi


W przypadku dostępu do zasobów nieodzyskiwalnych występują te same zdarzenia, które wyszczególnione zostały dla zasobów odzyskiwalnych. Różnica dotyczy jednak kontekstu zachodzenia tych zdarzeń. W przypadku zasobów nieodzyskiwalnych proces nabywający nie musi ich produkować (ani produkujący nabywać), podczas gdy w przypadku zasobów odzyskiwalnych po nabyciu jednostek przez proces oczekiwało się ich zwolnienia. W przypadku zasobów odzyskiwalnych zdarzenie d zachodziło zatem na ogół w następstwie zdarzenia a w tym samym procesie. W przypadku zasobów nieodzyskiwalnych odpowiadające sobie zdarzenia a i d będą zachodzić na ogół w różnych procesach.

  • Zamówienie (ang. request) jednostki zasobu przez procesu Pi — rf
  • Nabycie (ang. acquisition) jednostki zasobu przez proces Pi — ai
  • Utworzenie (ang. production) jednostki zasobu przez proces Pi — di

Zmiana stanu systemu w przypadku zasobów nieodzyskiwalnych

W systemie z zasobami zużywalnymi zrealizowanie zamówienia oznacza usunięcie jednostki zasoby, czyli kropki reprezentującej tę jednostkę w grafie. Jeśli chodzi o tworzenie, to ograniczeniem jest przypadek, gdy proces tworzący czeka na realizację własnego zamówienia.

  • W wyniku zamówienia zasobu Zj przez proces Pi, w grafie pojawia się krawędź zamówienia PiZj.
  • Po zrealizowaniu zamówienia przez system, krawędź ta znika wraz z kropką reprezentującą jednostkę zasobu.
  • Krawędź utworzenia istnieje zawsze — nie ma ograniczenia na liczbę tworzonych jednostek zasobu.
  • Jednostki zasobu Zj tworzone są przez Pi wówczas, gdy istnieje krawędź utworzenia ZjPi i proces Pi nie oczekuje na realizację żądań (nie ma krawędzi zamówienia PiZk).

Przykład przejść pomiędzy stanami w przypadku zasobów zużywalnych


Przykład pokazuje współpracę dwóch procesów za pośrednictwem zasobu nieodzyskiwalnego Z1, który można utożsamiać np. z semaforem uogólnionym. Proces P2 potencjalnie podnosi ten semafor. Podniesienie o 1 jest pierwszym zdarzeniem w systemie. Drugim zdarzeniem jest próba opuszczenia go o 2, co powoduje zablokowanie procesu P1. Następnie następuje podniesienie o 2 (oczywiście przez proces P2), co umożliwia nabycie (czyli rzeczywiste opuszczenie) przez proces P1.

slajd 31

Przykład analizy grafu przydziału zasobów nieodzyskiwalnych


Analiza graf przydziału zasobów nieodzyskiwalnych jest trudniejsza, niż w przypadku zasobów odzyskiwalnych. Chociaż można wskazać pewne własności, które umożliwiałyby wykrycie np. stanu zakleszczenia, dotyczą one szczególnych przypadków. Trudno np. rozważać system z zasobami pojedynczymi. Jedyną sensowną metodą jest redukcja grafu przydziału, co zostanie przedstawione w następnym module. Ale i takie podejście nie zawsze gwarantuje precyzyjne określenia rzeczywistego stanu.

W przedstawionym przykładzie procesy P3 i P4 są zablokowane ze względu na niedostępność jednostek odpowiednio zasobu Z3 i Z4. Jednostki tych zasobów mogą zostać wyprodukowane odpowiednio przez procesy P1 i P2 pod warunkiem odblokowania tych procesów. Dalszy przebieg przetwarzania zależy od kolejności zdarzeń w systemie lub decyzji zarządcy zasobów. Przydzielając jednostkę zasobu Z1 procesowi P1 a jednostkę zasobu Z2 procesowi P2 (lub odwrotnie), system wchodzi w stan zakleszczenia, niezależnie od tego czy zasoby Z1 i Z2 są odzyskiwalne, czy nie. Przydzielenie jednostek obu zasobów jednemu z procesów doprowadzi do zakleszczenia drugiego. Na przykład, jeśli P1 uzyska jednostki obu zasobów wyprodukuje Z3, co odblokuje P3, a dalej umożliwi wyprodukowanie jednostki zasobu Z1. Dla P2 zabraknie jednak jednostki zasobu Z2. W przypadku zasobów odzyskiwalnych, odpowiednie jednostki zostałyby po prostu zwolnione po zakończeniu procesów — jednostka zasobu Z2 wróciłaby wówczas do systemu. Zgodnie z definicją zakleszczenia, każdy z procesów da się odblokować (nie ma więc zakleszczenia), ale odblokowanie P1 powoduje zakleszczenie P2 i P4, a odblokowanie P2 powoduje zakleszczenie P1 i P3.

slajd 32

Własności grafu zasobów zużywalnych a stan zakleszczenia


Wyszczególnione własności podobne są do tych, które omówione zostały dla zasobów odzyskiwalnych.

  • Ogólnie:
    • zakleszczenie ⇒ cykl
  • Przydział natychmiastowy (stan zupełny)
    • supeł ⇒ zakleszczenie
  • Przydział natychmiastowy (stan zupełny), pojedyncze żądania:
    • supeł ⇔ zakleszczenie