Definicja problemu zakleszczenia

Model systemu


Model systemu na potrzeby analizy problemu zakleszczenia obejmuje procesy i zasoby. Zasób, dokładniej jego rodzaj lub typ, może być reprezentowany przez wiele jednorodnych jednostek, np. pamięć jako zasób może być reprezentowana w formie jednostek zwanych stronami, paragrafami, bajtami, zależnie od sposobu przydziału (alokacji). Traktowanie jednostek jako jednorodne lub różnorodne (jednostki różnych typów zasobów) zależy czasami do sposobu wykorzystania zasobu przez proces. Jeśli w systemie są dwie różne drukarki, np. laserowa, umożliwiający tylko wydruk czarno-biały oraz atramentowa, drukująca kolorowo, to tylko od oczekiwań procesów lub użytkowników zależy, czy są to jednorodne, czy różnorodne egzemplarze. Jeśli procesy żądają po prostu wydruku, niezależnie od jakości i kolorów, egzemplarze można traktować jako jednorodne. Jeśli natomiast pojawiają się żądania wydruku kolorowego, każda z tych drukarek jest innym rodzajem zasobu.

Analizując stan systemu zakłada się, że procesy kiedyś kończą swoje przetwarzanie. Istotnym pytaniem jest, co się dzieje z zasobami tych procesów po zakończeniu. W zależności od odpowiedzi na to pytanie rozróżnia się zasoby:

  • odzyskiwalne — zwracane do systemu po zakończeniu procesu,
  • nieodzyskiwalne — konsumowane przez proces (skonsumowanie jest istotnym elementem ich użycie).

Przy tej okazji warto przypomnieć, że zasoby klasyfikuje się również jako współdzielone i wyłączne oraz wywłaszczalne i niewywłaszczalne. Jak się jednak okaże przy omawianiu warunków koniecznych wystąpienia zakleszczenia, problem dotyczy tylko zasobów wyłącznych i niewywłaszczalnych. Natomiast odzyskiwalność lub nieodzyskiwalność zasobów wpływa na sposób analizy stanu systemu i postępowania w rozwiązywaniu problemu zakleszczenia.

  • System składa się z zasobów m różnych typów (rodzajów) ze zbioru Z = {Z1, Z2 ....., Zm}.
  • Zasób każdego typu może być reprezentowany przez wiele jednorodnych jednostek (egzemplarzy).
  • O zasoby rywalizują procesy ze zbioru P = {P1, P2 ....., Pn}
  • Klasyfikacja zasobów z punktu widzenia problemu zakleszczenia:
    • zasoby odzyskiwalne (zwrotne, trwałe, ang. reusable resources)
    • zasoby nieodzyskiwalne (zużywalne, niezwrotne, ang. consumable resources)

Zasoby odzyskiwalne


Założenie o stałej liczbie jednostek zasobów odzyskiwalnych jest konieczne w celu analizy możliwości systemu w zakresie obsługi żądań. Założenie to jest adekwatne dla typowych realiów funkcjonowania systemów komputerowych (nikt w trakcie działania systemu nie dokłada dynamicznie pamięci, czy procesora). Dynamiczne rozszerzenie dostępnych zasobów (np. dołożenie pamięci dyskowej) wymaga rekonfiguracji w związku z tym reinicjalizacji algorytmów zarządzania zasobami.

Proces może zażądać kilka jednostek zasobu w jednym zamówieniu, skierowanym do zarządcy zasobu. Można też rozważać system, w którym zamówienie ze strony procesu obejmuje jednostki zasobów różnych typów. Zarządca będzie utożsamiany z jądrem systemu operacyjnego. Po użyciu, a najpóźniej po zakończeniu swojego działania proces zwalnia te zasobu — oddaje je ponownie do dyspozycji zarządcy, który z kolei może przydzielić je innym procesom.

W stosunku do zasobów odzyskiwalnych używa się też terminu szeregowo - zwrotne (ang. serially reusable), w celu podkreślenia, że zasób może być wykorzystywany przez wiele procesów, ale nie w tym samym czasie.

  • Liczba jednostek zasobów odzyskiwalnych jest ustalona.
  • Zasoby odzyskiwalne po ich zwolnieniu przez jakiś proces mogą zostać ponownie użyte przez inny proces.
  • Proces ubiega się o dowolny egzemplarz zasobu odzyskiwalnego według następującego schematu:
    • zamówienie (ewentualnie oczekiwanie na realizację)
    • użycie — korzystanie zasobu (jego przetrzymywanie)
    • zwolnienie — oddanie zasobu do systemu
  • Przykłady zasobów odzyskiwalnych: procesor, pamięć, kanał wejścia-wyjścia.

Zasoby nieodzyskiwalne


W przypadku zasobów nieodzyskiwalnych warto podkreślić fakt, że ich egzemplarze są tworzone przez jakiś proces. Zasobem takim nie jest np. papier do drukarki, pomimo że ulega zużyciu. Po pierwsze — nie jest to zasób, którym w typowych systemach komputerowych zarządza system operacyjny. Po drugie — dostępność tego zasobu nie zależy w żaden sposób od bieżącego stanu jakiegokolwiek procesu. Żaden z procesów nie może go wyprodukować. W analizie zakleszczenia chodzi natomiast o ustalenie niezbędnych działań związanych z procesami, zmierzających do precyzyjnego zidentyfikowania przyczyny zakleszczenia i ewentualnego jej usunięcia lub niedopuszczenia do powstania.

  • Jednostki zasobu nieodzyskiwalnego są tworzone przez jakiś proces, a następnie zużywane (tym samym usuwane) przez inny proces.
  • Nie ma ograniczenia na liczbę tworzonych jednostek zasobu.
  • Liczba aktualnie dostępnych jednostek jest skończona i może się zmieniać w czasie w wyniku zmian stanu systemu.
  • Przykłady zasobów nieodzyskiwalnych: kod znaku z klawiatury, sygnał lub komunikat przekazany do procesu.

Korzystanie z zasobów nieodzyskiwalnych


Podobnie jak w przypadku zasobów odzyskiwalnych proces ubiega się o jednostki, składając zamówienie do zarządcy, albo realizując jakiś specyficzny protokół synchronizacji. Z punktu widzenia zarządcy lub innych współpracujących procesów przydział oznacza zużycie. Proces może natomiast wytworzyć jednostki danego zasobu i udostępnić je innym procesom, które tego zażądają. Na potrzeby analizy stanu zakleszczenia zakłada się, że jeśli proces, który tworzy dany zasób, nie jest zablokowany w oczekiwaniu na inne zasoby systemu, może wyprodukować nieograniczoną liczbę jednostek, czyli taką liczbę, jakiej oczekują inne procesu.

  • Proces ubiega się o dowolny egzemplarz zasobu nieodzyskiwalnego według następującego schematu:
    • zamówienie (ewentualnie oczekiwanie na realizację)
    • zużycie — wykorzystanie zasobu (jego usunięcie)
  • Proces może wyprodukować i przekazać zasób do systemu.