BuS: Banker's Algorithmus

[Jayomat]

hallo zusammen,
ich muss gestehen das ich nicht in der Vorlesung war, deßhalb würde es mich freuen wenn mir einer hier ca. erklären kann wie ich das verlinkte "bild" zu verstehen habe. Ich werde nicht wirklich schlau daraus so vollkommen ohne Erklärung dazu. Habe natürlich schon gegoogled, aber scheinbar scheinen "alle" anderen Unis eine andere Darstellung zu wählen, nur wir tollen Elitestudenten haben ne eigene bekommen

Danke für jeden sinnvollen Hinweis

[mozaiq]

Hi

Problem ist, dass es verschiedene Versionen des Algorithmus gibt: Deadlock detection bzw safety detection und deadlock prevention. Daher kann es leicht passieren, dass man im Internet widersprüchliche Informationen findet. Der in der Vorlesung vorgestellte Algortihmus ist safety detection.
Das Beispiel ist an der Stelle relativ einfach. Es existiert ein BM mit 12 Exemplaren und 3 Prozesse dies haben wollen. Dabei gibt Allocation an, was zum Start schon besetzt ist. Hier hat also P1 5 BM, P2 hat 2 BM und P3 hat ebenfalls 2 BM. Damit sind 3 BM noch nicht vergeben und können verteilt werden. Daran kann man auch schon auf Anhieb erkennen, das nur ein Prozess laufen kann, der noch maximal 3 BM zusätzlich benötigt, da nicht mehr vorhanden sind. Hier ist Maximum da. Das ist der Wert, der maximal, also damit der Prozess laufen kann, benötigt wird. heißt also konkret: P1 braucht insg. 10 BM, P2 braucht 4 und P3 9. Was dort nicht aufgelistet wird, was man sich aber auch einfach denken kann, wäre der Übersicht halber eine Zeile Need, die angibt, was noch benötigt wird je Prozess. Die Werte dafür sind die Differenzen aus max und alloc. Diese need Werte entscheiden auch, ob ein Prozess laufen kann oder nicht. Hier wären sie für P1 5, da 10 benötigt werden und 5 bereits gehalten werden, P2 2 (4-2) und P3 9-2=7. Damit ein Prozess laufen kann, muss Need(i)<=free sein, hier also <=3. Das erfüllt offensichtlich nur P2, welcher daher auch zuerst läuft. Die vierte Zeile spiegelt genau das wieder. 5 4 2 1 gibt an, was von wem belegt wird, während P2 läuft. Also die aktuellen Alloc Werte. In Zeile 5 endet P2, wodurch dieser Prozess die gehaltenen BM frei gibt. dementsprechend ist alloc nun 5 0 2 5. Da need(3)=7!<=5=free, kann P3 nicht laufen. Dafür aber P1, da need(1)=5=free. Same prodecure, P1 läuft und gibt danach seine BM wieder frei, alloc Werte entsprechend. Dann darf endlich P3 ran, nimmt sich seine BM, gibt sie danach wieder frei und somit ist am Ende alloc = 0 0 0 12, da kein Prozess mehr was hält und alle 12 BM frei sind.
Die Folge <P2,P1,P3> gibt an, in welcher Reihenfolge die Prozesse abgearbeitet werden (können).
Der sichere Zustand (5,2,2) ist dabei der Ausgangszustand für alloc

So, ich hoffe, dass das verständlich war