Wykres oczekiwania
Graf oczekiwania w informatyce to skierowany graf używany do wykrywania zakleszczeń w systemach operacyjnych i systemach relacyjnych baz danych .
W informatyce system, który umożliwia jednoczesne działanie wielu procesów i blokowanie zasobów, a który nie zapewnia mechanizmów unikania lub zapobiegania zakleszczeniom, musi obsługiwać mechanizm wykrywania zakleszczeń i algorytm odzyskiwania z nich.
Jeden z takich algorytmów wykrywania zakleszczeń wykorzystuje wykres oczekiwania do śledzenia, które inne procesy aktualnie blokuje dany proces. Na grafie oczekiwania procesy są reprezentowane jako węzły, a krawędź od procesu do implikuje trzyma zasób, którego potrzebuje, a zatem czeka na , aby zwolnić blokadę tego zasobu. Jeśli proces czeka na udostępnienie więcej niż jednego zasobu (przypadek trywialny), wiele krawędzi może reprezentować spójny (i) lub rozłączny (lub) zestaw różnych zasobów lub pewną liczbę równoważnych zasobów z kolekcji . Możliwość zakleszczenia jest implikowana przez cykle wykresów w przypadku koniunkcji i przez węzły w przypadku rozłącznym. Nie ma prostego algorytmu wykrywania możliwości zakleszczenia w ostatecznym przypadku.
Schemat oczekiwania na wykres nie ma zastosowania do systemu alokacji zasobów z wieloma instancjami każdego typu zasobu.
- Silberschatz, Abraham; Galwin, Piotr; Gagne, Greg (2003). Pojęcia dotyczące systemu operacyjnego . John Wiley & Sons, Inc., str. 260 . ISBN 0-471-25060-0 .