Vänta på graf

En väntan-på-graf i datavetenskap är en riktad graf som används för detektering av dödläge i operativsystem och relationsdatabassystem .

Inom datavetenskap måste ett system som tillåter samtidig drift av flera processer och låsning av resurser och som inte tillhandahåller mekanismer för att undvika eller förhindra dödläge stödja en mekanism för att upptäcka dödlägen och en algoritm för att återhämta sig från dem.

En sådan dödlägesdetekteringsalgoritm använder sig av en väntan-på-graf för att spåra vilka andra processer en process för närvarande blockerar. I en väntan-på-graf representeras processer som noder, och en kant från process $P_{i}$ till $P_{j}$ innebär $P_{j}$ håller en resurs som $P_{i}$ behöver och därför väntar ${\displaystyle P_{i}} på att$$P_{j}$ ska släppa sitt lås på den resursen. Om processen väntar på att mer än en enskild resurs ska bli tillgänglig (det triviala fallet), kan flera kanter representera en konjunktiv (och) eller disjunktiv (eller) uppsättning av olika resurser eller ett visst antal ekvivalenta resurser från en samling . Möjligheten för ett dödläge antyds av grafcykler i konjunktivfallet och av knutar i disjunktivfallet. Det finns ingen enkel algoritm för att upptäcka möjligheten till dödläge i det sista fallet.

Vänta-på-graf-schemat är inte tillämpligt på ett resursallokeringssystem med flera instanser av varje resurstyp.

•   Silberschatz, Abraham; Galvin, Peter; Gagne, Greg (2003). Operativsystemskoncept . John Wiley & Sons, Inc. s. 260 . ISBN 0-471-25060-0 .