Mit Google fortfahren
Betriebsmittelzuteilungsgraph: Deadlocks erkennen
Ein Betriebsmittelzuteilungsgraph zeigt, welche Betriebsmittel Prozesse bereits besitzen und auf welche sie noch warten. So kannst du Ressourcennutzungen modellieren und mögliche Deadlocks erkennen.
Hake ab, was du schon kannst — und komm am Ende hierher zurück!
Woraus besteht der Graph?
Stell dir mehrere Programme vor, die gleichzeitig einen Drucker, einen Scanner oder gemeinsam genutzte Datensätze benötigen. Ein Betriebsmittelzuteilungsgraph hält den aktuellen Zustand dieses Systems fest.
Betriebsmittelzuteilungsgraph
Ein Betriebsmittelzuteilungsgraph ist ein gerichteter bipartiter Graph. Seine Knoten gehören zu zwei getrennten Gruppen: Prozesse und Betriebsmittel. Jede Kante verbindet einen Prozess mit einem Betriebsmittel und besitzt eine Richtung.
Du verwendest zwei Arten von Knoten:
- Ein Kreis steht für einen Prozess, zum Beispiel $P_1$.
- Ein Quadrat steht für einen Betriebsmitteltyp, zum Beispiel $R_1$.
- Gibt es mehrere Exemplare eines Betriebsmittels, enthält sein Quadrat für jedes Exemplar einen Punkt.
Bipartit bedeutet: Eine Kante verbindet immer einen Prozess mit einem Betriebsmittel. Eine direkte Kante zwischen zwei Prozessen oder zwischen zwei Betriebsmitteln gehört nicht in diesen Graphen.
Die Richtung zeigt die Bedeutung: Prozess $\rightarrow$ Betriebsmittel heißt fordert an. Betriebsmittel $\rightarrow$ Prozess heißt ist zugeteilt.
$P_1 \rightarrow R_2$ bedeutet: Prozess $P_1$ wartet auf ein Exemplar von $R_2$.
$R_2 \rightarrow P_1$ bedeutet dagegen: Ein Exemplar von $R_2$ ist bereits Prozess $P_1$ zugeteilt.
Wie baust du einen Graphen auf?
Übersetze die Situation schrittweise. Entscheidend ist der aktuelle Zustand, nicht das, was später vielleicht geschehen könnte.
- Notiere alle Prozesse als Kreise.
- Notiere alle Betriebsmitteltypen als Quadrate.
- Zeichne für jedes zugeteilte Exemplar eine Kante vom Betriebsmittel zum besitzenden Prozess.
- Zeichne für jede offene Anforderung eine Kante vom wartenden Prozess zum Betriebsmittel.
Gegeben sind die Prozesse $P_1$, $P_2$ und $P_3$ sowie die Betriebsmittel $R_1$, $R_2$ und $R_3$. Von $R_3$ gibt es zwei Exemplare.
- $P_1$ besitzt $R_1$: $R_1 \rightarrow P_1$
- $P_2$ besitzt $R_2$: $R_2 \rightarrow P_2$
- $P_2$ besitzt ein Exemplar von $R_3$: $R_3 \rightarrow P_2$
- $P_3$ besitzt das zweite Exemplar von $R_3$: $R_3 \rightarrow P_3$
- $P_1$ fordert $R_2$ an: $P_1 \rightarrow R_2$
Die beiden von $R_3$ ausgehenden Zuteilungskanten gehören zu zwei verschiedenen Exemplaren. Ein einzelnes Exemplar darf nicht gleichzeitig zwei Prozessen zugeteilt sein.
Wähle in jeder Lücke die passende Form und prüfe anschließend deine Antworten.
Eine offene Anforderung zeigt vom zum . Eine bestehende Zuteilung zeigt in die Richtung. Mehrere Punkte in einem Betriebsmittelknoten stehen für mehrere dieses Typs.
Wann weist ein Zyklus auf einen Deadlock hin?
Ein Zyklus ist ein geschlossener Weg entlang der Pfeilrichtungen. Du gelangst vom Startknoten über mehrere Kanten wieder zum Startknoten zurück.
Deadlock
Bei einem Deadlock wartet jeder Prozess einer Gruppe auf ein Ereignis, das nur ein anderer Prozess derselben Gruppe auslösen kann. Keiner der beteiligten Prozesse kann deshalb fortfahren und seine bereits belegten Betriebsmittel freigeben.
Vier Bedingungen ermöglichen einen Deadlock:
- Wechselseitiger Ausschluss: Ein Betriebsmittel kann nicht gleichzeitig beliebig geteilt werden.
- Halten und Warten: Ein Prozess besitzt bereits ein Betriebsmittel und fordert ein weiteres an.
- Unentziehbarkeit: Ein zugeteiltes Betriebsmittel kann dem Prozess nicht einfach weggenommen werden.
- Zyklisches Warten: Die Prozesse warten in einem geschlossenen Kreis aufeinander.
Für die Auswertung des Graphen gilt:
- Kein Zyklus: Es liegt kein Deadlock vor.
- Zyklus und genau ein Exemplar jedes beteiligten Betriebsmittels: Der Zyklus weist einen Deadlock nach.
- Zyklus und mehrere Exemplare mindestens eines beteiligten Betriebsmittels: Ein Deadlock ist möglich, aber der Zyklus allein beweist ihn nicht.
Warum macht die Anzahl der Exemplare einen Unterschied? Ein Prozess außerhalb des Zyklus könnte ein weiteres Exemplar freigeben. Ein wartender Prozess erhält es, beendet seine Arbeit und gibt danach weitere Betriebsmittel frei. Dadurch kann sich der Zyklus auflösen.
Ein Zyklus ist immer ein Warnsignal. Zum sicheren Deadlock-Nachweis musst du zusätzlich die Anzahl der beteiligten Betriebsmittel-Exemplare beachten.
Wie analysierst du eine vollständige Situation?
Zwei Prozesse führen Überweisungen zwischen zwei Konten aus. Jedes Konto ist ein unteilbares Betriebsmittel und genau einmal vorhanden.
- $P_1$ besitzt die Sperre für Konto $K_1$ und fordert $K_2$ an.
- $P_2$ besitzt die Sperre für Konto $K_2$ und fordert $K_1$ an.
Die Kanten lauten:
- $K_1 \rightarrow P_1$
- $P_1 \rightarrow K_2$
- $K_2 \rightarrow P_2$
- $P_2 \rightarrow K_1$
Damit entsteht der Zyklus
$$P_1 \rightarrow K_2 \rightarrow P_2 \rightarrow K_1 \rightarrow P_1$$
Beide Konten sind jeweils nur einmal vorhanden. $P_1$ kann $K_2$ erst erhalten, wenn $P_2$ es freigibt. $P_2$ wartet zugleich auf $K_1$, das $P_1$ hält. Keiner kann seine Überweisung abschließen: Es liegt ein Deadlock vor.
Eine passende Gegenmaßnahme
Nummeriere die Konten und verlange, dass jeder Prozess sie nur in aufsteigender Reihenfolge sperrt. Dann darf ein Prozess beispielsweise erst $K_1$ und danach $K_2$ anfordern, aber nicht umgekehrt.
Bei einer solchen festen Ordnung kann kein geschlossener Wartekreis entstehen: Entlang jeder weiteren Anforderung steigt die Nummer. Ein Zyklus müsste irgendwann zu einer kleineren Nummer zurückkehren und würde damit die Regel verletzen.
Aufgabe: Ein Druckprozess $P_D$ besitzt den Drucker $D$ und fordert den Scanner $S$ an. Ein Scanprozess $P_S$ besitzt $S$ und fordert $D$ an. Beide Betriebsmittel sind genau einmal vorhanden. Stelle die Kanten auf und entscheide, ob ein Deadlock besteht.
Lösung:
- $D \rightarrow P_D$
- $P_D \rightarrow S$
- $S \rightarrow P_S$
- $P_S \rightarrow D$
Es entsteht der Zyklus
$$P_D \rightarrow S \rightarrow P_S \rightarrow D \rightarrow P_D$$
Da $D$ und $S$ jeweils genau ein Exemplar besitzen, weist der Zyklus einen Deadlock nach.
Karteikasten
Überlege zuerst selbst und drehe die Karte anschließend zum Prüfen um.
Alles auf einen Blick
- Betriebsmittelzuteilungsgraph
- Bestandteile
- Prozesse als Kreise
- Betriebsmittel als Quadrate
- Exemplare als Punkte
- Kanten
- Prozess zu Betriebsmittel: Anforderung
- Betriebsmittel zu Prozess: Zuteilung
- Analyse
- kein Zyklus: kein Deadlock
- Zyklus mit Einzelexemplaren: Deadlock
- Zyklus mit Mehrfachexemplaren: weitere Prüfung
- Vorbeugung
- einheitliche Reihenfolge
- kein zyklisches Warten
- Bestandteile
Abschluss-Check
Du kannst einen Betriebsmittelzuteilungsgraphen nun in drei Schritten untersuchen: Kantenrichtungen lesen, Zyklen suchen und die Anzahl der Exemplare prüfen.