Berücksichtigt Petersons 2-Prozess-Algorithmus zum gegenseitigen Ausschluss sterbende Prozesse?

9

Ich denke, dass in Petersons Algorithmus zum gegenseitigen Ausschluss , wenn der Prozess, der zuerst in den kritischen Abschnitt eintritt, sterben oder abgebrochen wird, der andere Prozess für immer eine Schleife durchläuft und darauf wartet, in den kritischen Abschnitt einzutreten.

Wenn in Prozess 1 Prozess 1 gestoppt wird, werden die restlichen Prozesse hinter Prozess 1 bis zu der Stelle ausgeführt, an der sich Prozess 1 befindet, dann aber eine Schleife.

Geben Sie hier die Bildbeschreibung ein

Was passiert, wenn der Prozess, der den kritischen Abschnitt erreicht, zuerst stirbt, bevor er ihn verlässt?

programming-languages concurrency mutual-exclusion Ganadara
quelle
Ich habe Ihre Frage entsprechend bearbeitet. Da Sie nicht kommentiert haben, wie der Algorithmus auf mehr als zwei Prozesse erweitert werden kann, habe ich diesen Teil der Frage geändert. Ich denke, das Problem ist bereits in der Zwei-Prozess-Version vorhanden. Ich verstehe das Bild aber immer noch überhaupt nicht.
Raphael

Antworten:

1

Dies hängt davon ab, wie Sperren implementiert werden. Wenn Sie es wie im Wikipedia-Artikel tun, dh den kritischen Abschnitt mit einem Booleschen Wert pro Prozess¹ schützen, sind Sie mit Sicherheit in Schwierigkeiten. Wenn ein Prozess stirbt, wird sein Flag niemals zurückgesetzt, sodass der andere Prozess für immer wiederholt wird.

In der Praxis können Sie Ihren Code vor vielen Arten des Sterbens schützen. Nehmen Sie zum Beispiel diese Implementierung im Java-Stil:

flag[1] = true;
turn = 1;
while ( flag[0] == true && turn == 1 ) { Thread.yield(); }
try {
  // critical section
}
finally {
  flag[1] = false;
}

Dadurch wird sichergestellt, dass das Flag zurückgesetzt wird, was auch immer im kritischen Abschnitt passiert, solange das System den Fehler behandelt. In Java gilt dies auch für Stapel- und Heap-Überläufe. Wenn der Prozess nicht buchstäblich verschwindet ( kill², Prozessorausfall, Netzwerkunterbrechung, ...), sind Sie sicher. Beachten Sie, dass die meisten unkritischen Programme in diesen Fällen fehlschlagen. Wie kann sie mit einem Fehler umgehen, den sie nicht ausführen? - Das muss also in vielen Fällen akzeptiert werden. Bei Bedarf können Sie beim Neustart mit Inkonsistenzen umgehen.

Wenn Sie geeignete Sperren auf Sprachebene verwenden, kann das Laufzeitsystem verschwindende Sperrenbesitzer verarbeiten, dh Sperren mit toten Besitzern freigeben. Sie können dies selbst simulieren, indem Sie jedem Prozess einen Totmannschalter geben, den die anderen lesen können, oder direkt prüfen, ob der Prozess des Schlossbesitzes noch aktiv ist (sofern das System dies unterstützt).

  1. Das lässt sich sowieso nicht gut skalieren.
  2. In Java sollte meiner Meinung finalizenach auch auf ausgeführt werden kill, aber dies wird durch die Spezifikation nicht garantiert. kill -9ist wahrscheinlich ein Todesurteil für jede Lösung, bei der der Sterbevorgang etwas unternehmen muss.
Raphael
quelle
1

Schauen Sie sich die Annahmen an, insbesondere, dass kein Prozess auf unbestimmte Zeit im kritischen Bereich verbleibt (dazu gehört sicherlich auch das Weggehen). Ich glaube nicht, dass es einen Weg gibt, dieses allgemeine Problem mit einem Synchronisationsmechanismus zu lösen.

n

vonbrand
quelle