Das Problem des ungünstigsten Moments

Man betrachte erneut die mit einer while-Schleife realisierte Sperre des aktiven Wartens, welche zu Beginn eines kritischen Abschnitts durchlaufen werden muss:

Code

while (lock == 1);
lock = 1;


Listing 1: Sperre zu Beginn des kritischen Abschnitts


Eine Übersetzung des Java-Quellcodes aus Listing 1 in Assembler könnte (in Anlehnung an die Assembler-Befehle aus dem bekannten Sum- bzw. Count-Program) in etwa so aussehen:

Code

10: LOAD 25           ; Wert aus Speicherzelle 25 in Akkumulator kopieren
11: EQUAL #1          ; Prüfe: Ist ACC == 1? (Eigentlich: ist lock == 1?)
12: JUMP 14           ; Prüfung ergab FALSE
13: JUMP 10           ; Prüfung ergab TRUE
14: LOAD #1           ; Der neue Wert der lock-Variablen...
15: STORE 25          ; ...wird in die Speicherzelle 25 geschieben


Listing 2: Sperre in Assembler

Aus zwei Befehlen des Java-Quellcodes sind sechs Assembler-Befehle geworden. In Speicherzelle 25 steht der aktuelle Wert der lock-Variablen. Der gesamte Codeabschnitt steht in den Speicherzellen 10 bis 15, das heißt ab Speicherzelle 16 geht es weiter mit dem ersten Befehl des kritischen Abschnitts. Die konkreten Speicheradressen sind in diesem Beispiel zufällig gewählt, es obliegt dem Compiler bei der Übersetzung diese virtuellen Adressen festzulegen.

Hinweis

Es sei an dieser Stelle daran erinnert, dass direkt nach jedem Assembler-Befehl ein Kontextwechsel auf der CPU stattfinden könnte.


Ungünstigster Moment

Falls der Kontextwechsel zufällig im ungünstigsten Moment erfolgt, so könnte sich ein Problem ergeben. Dieser ungünstigste Moment liegt direkt nach dem EQUAL-Befehl, sofern die lock-Variable noch den Wert Null hat (es befindet sich also noch kein Prozess in seinem kritischen Bereich). Die Prüfung der Bedingung ist gerade erfolgt, aber der Wert der lock-Variablen (Speicherzelle 25) wurde noch nicht verändert, d.h. die Sperre wurde noch nicht gesetzt.

Code

10: LOAD 25           ; Wert aus Speicherzelle 25 in Akkumulator kopieren
11: EQUAL #1          ; Prüfe: Ist ACC == 1? (Eigentlich: ist lock == 1?)
                ; --> Ungünstigster Moment,
                ; --> falls direkt hier ein Kontextwechsel erfolgt!
12: JUMP 14           ; Prüfung ergab FALSE
13: JUMP 10           ; Prüfung ergab TRUE
14: LOAD #1           ; Der neue Wert der lock-Variablen...
15: STORE 25          ; ...wird in die Speicherzelle 25 geschieben


Listing 3: Ungünstigste Stelle für einen Kontextwechsel


Aufgabe 1

Aufgabe
Kontextwechsel im ungünstigsten Moment

Was passiert, wenn ein Kontextwechsel im ungünstigsten Moment erfolgt und der andere Prozess nun ebenfalls seinen kritischen Abschnitt betritt, also den Wert der lock-Variablen prüft?


Aufgabe 2

Aufgabe
Mehrere ungünstigste Momente

Analysiert man den Assembler-Code genauer, so fällt auf, dass es insgesamt drei Stellen für den ungünstigsten Moment gibt. Die erste Stelle ist direkt nach dem EQUAL-Befehl. Wo sind die anderen beiden Stellen?


Ein Kontextwechsel im ungünstigsten Moment kann also dazu führen, dass zwei (vielleicht auch noch mehr!) Prozesse oder Threads sich gleichzeitig in ihrem kritischen Abschnitt befinden. Zwar ist die Wahrscheinlichkeit, dass dieses passiert, sehr gering, aber selbst ein extrem kleines Risiko ist nicht hinnehmbar.


Aus der
Praxis
Selbst das kleinste Risiko ist zu groß!

Denke an eine Steuerungssoftware in einem Kernkraftwerk: Zwei Prozesse gleichzeitig in ihrem kritischen Abschnitt könnten eine Kernschmelze bedeuten.

Oder an einen Bordcomputer im Flugzeug (Stichwort: Autopilot): Zwei Prozesse gleichzeitig in ihrem kritischen Abschnitt könnten der Grund für einen Absturz sein.


Allein die Gedankenspiele Kernkraftwerk und Flugzeug rechtfertigen also, dass ein Mechanismus geschaffen wird, welcher eine Sperrvariable innerhalb einer atomaren Aktion abfragen und setzen kann.


Definition: Atomare Aktion

Definition

Unter einer atomaren Aktion (oder atomaren Operation) versteht man nach Mandl 2013 Codebereiche, die in einem Stück, also atomar, ausgeführt werden müssen und (logisch) nicht unterbrochen werden dürfen.

Der Begriff atomar wird gerne im Sinne von unteilbar verwendet. Hier ist eher ununterbrochen gemeint, wobei der in Klammern getätigte Einschub (logisch) eine Lockerung der Nicht-Unterbrechbarkeit darstellt. Auf diese Lockerung wurde bei der Definition zum kritischen Abschnitt bereits eingegangen.

Nach dem bis jetzt im Rahmen dieses Lernmoduls erlangten Wissensstand ist eine atomare Aktion nichts weiter als ein einzelner Assemblerbefehl, wie er beispielsweise oben in Listing 2 oder Listing 3 zu sehen ist. Denkbar ist aber auch, dass mehrere Assemblerbefehle ununterbrochen ausgeführt werden müssen.


Anmerkung

Das Ziel besteht nun darin, eine Möglichkeit zu schaffen, wie die beiden Zeilen aus Listing 1 zu einer atomaren Aktion verschmelzen können.

Eine Möglichkeit bietet dafür der TSL-Befehl, welcher im folgenden Kapitel erläutert wird.