Resource Allocation Graph

Ein Resource Allocation Graph (kurz RAG) ist ein Gerichteter Graph, der die Beziehungen von Prozessen und Ressourcen in Verbindung stellt. Er hilft beim Finden von Deadlocks.

Die Knoten können in 2 Teilmengen unterteilt werden:

• , die Menge aller Prozesse eines Systems
• , die Menge aller Ressourcen eines Systems

Zusätzlich definieren wir:

• Anforderungskante - gerichtete Kante wenn ein Prozess die Ressource haben möchte
• Zuweisungskante - gerichtete Kante wenn ein Prozess Zugriff auf die Ressource hat

Beispiele

fordert Instanz von an:

hat eine Instanz von :

Grundlegende Fakten

Es gilt:

• Wenn der Graph keinen Zyklus hat, kann es nicht zu einem Deadlock kommen.
• Wenn der Graph einen Zyklus enthält, kommt es darauf an:
  • Falls nur eine Instanz je Ressourcen-Typ existiert, kommt es garantiert zu einem Deadlock
  • Falls mehrere Instanzen je Ressourcen-Typ existieren, besteht die Möglichkeit eines Deadlocks