Wechselseitiger Ausschluss

Tom, Lisa und Jenny sind Vertreter/-innen für ein Werk, das Staplerfahrzeuge herstellt. Sie reisen zu anderen Unternehmen (Kunden), stellen dort neuentwickelte Stapler vor und helfen bei Problemen, die die Kunden beim Einsatz der Stapler haben. Natürlich schließen sie auch gerne Verträge über den Kauf von Staplern ab. Sie verständigen dann jeweils sofort das Lager, damit die bestellten Stapler als "reserviert" markiert werden.
Bevor die drei zu ihren Kunden aufbrechen, erkundigen sie sich im Lager, wie viele Stapler vorrätig sind, damit sie nicht Verträge über die Lieferung von Waren abschließen, die gar nicht in ausreichender Menge vorhanden sind. Trotzdem kommt dieser Fall eines Tages aber vor.

Erklären Sie, wie es dazu kommen kann und stellen Sie die Situation in einem Sequenzdiagramm dar.

Lösung

Race condition und Lösungen

Im folgenden Beispiel gibt es nur ein einziges Objekt der Klasse Counter. Drei Threads, die gleichzeitig laufen, erhöhen je 1 Million-mal diesen Counter.
Am Ende der Arbeit meldet jeder Thread den aktuellen Zustand des Counters. Man würde erwarten, dass der Thread, der als letztes fertig wird, die Zahl 3000000 ausgibt.

Starten Sie das Programm mehrmals und sehen Sie sich die Ausgabe an.
Wie lässt sich die Ausgabe erklären?

Im rechts stehenden Sequenzdiagramm ist zu sehen, was passiert, wenn zwei Threads gleichzeitig die Methode increment() des Counter-Objekts aufrufen. Stellen Sie sich vor, das Attribut counter hat zu Beginn den Wert 4. Der blaue Thread ist etwas früher dran als der grüne, trotzdem erfolgt die Anweisung counter = i des blauen Threads erst nach der Anweisung i = counter des grünen Threads. Das hat zur Folge, dass sowohl die grüne Variable i als auch die blaue jeweils auf 5 erhöht werden. Am Ende wird zweimal derselbe Wert 5 in die Variable counter geschrieben, so dass sie folglich nur um eins erhöht wurde, obwohl die Methode increment() zweimal aufgerufen wurde.

Man nennt diesen Effekt eine race condition. Sie entsteht dadurch, dass die Anweisungen in der Methode increment() von mehr als einem Thread gleichzeitig ausgeführt werden.

Definition:
Einen Programmabschnitt, der nicht von mehreren Thread gleichzeitig durchlaufen werden darf, nennt man kritischer Abschnitt (engl.: critical section). Eine Maßnahme um zu erreichen, dass ein kritischer Abschnitt nur jeweils von einem Thread gleichzeitig "betreten" wird, nennt man wechselseitiger Ausschluss (engl.: mutual exclusion).

Im folgenden werden mehrere Möglichkeiten dargestellt, wie wechselseitiger Ausschluss in Java erreicht werden kann.

Lösung 1: Synchronized-Methode (Monitor)

Wir brauchen eine Möglichkeit, um zu verhindern, dass mehr als ein Thread gleichzeitig den kritischen Abschnitt (in unserem Fall die Methode increment) betritt. Dies leistet das Schlüsselwort synchronized bei der Deklaration der Methode increment. Es weist den Compiler an, Code zu generieren, der zur Laufzeit sicherstellt, dass jeweils nur einen Thread je Counter-Objekt die Methode "betreten" darf. Nachfolgende Threads werden blockiert (d.h. in der Ausführung angehalten) bis der erste Thread die Methode wieder verlassen hat. Erst dann wird einer der blockierten Threads wieder fortgesetzt.

Vergleichen Sie die Deklaration der Methode increment im folgenden Programm mit der Deklaration im vorangegangenen Programm.
Starten Sie das Programm mehrmals. Erklären Sie die Ausgabe!

Eine Möglichkeit zum wechselseitigen Ausschluss wie das synchronized-Konzept von Java nennt man Monitor. Oft bietet ein Monitor darüber hinaus noch eine Möglichkeit zum passiven Warten und zum Benachrichtigen wartender Threads, mehr dazu im folgenden Kapitel.
Deklariert man mehrere Methoden einer Klasse als synchronized, so darf je Objekt der Klasse jeweils nur maximal ein Thread eine dieser Methoden betreten. Anders formuliert: In allen synchronized-Methoden eines Objekts befindet sich zu jedem Zeitpunkt maximal ein Thread.

Lösung 2: Die Klasse Semaphore

Ein Semaphor ist ein Objekt, das einen Zähler enthält, dessen Wert angibt, von wie vielen Prozessen ein kritischer Abschnitt im Augenblick gerade noch betreten werden darf.
(Bem.: Eine andere Interpretation besteht darin, dass es $n$ gleichartig Ressourcen gibt. Der Wert des Zählers gibt an, wie viele im Augenblick gerade zur Verfügung stehen.)

Der Semaphor besitzt zwei Methoden:

acquire() prüft, ob der Zähler größer als 0 ist.
- Ist dies der Fall, so wird der Zähler um eins erniedrigt und mit der danach folgenden Anweisung fortgefahren. Dem Prozess wird damit das Betreten des kritischen Bereichs gestattet.
- Ist dies nicht der Fall, so wird der Prozess in einen Wartezustand versetzt.
release() prüft, ob es zu diesem Semaphor Prozesse im Wartezustand gibt.
- Falls dies der Fall ist, wir einer davon "aufgeweckt" und darf damit den kritischen Bereich betreten.
- Ist dies nicht der Fall, so wird der Zähler um 1 erhöht.

Aufgaben

Aufgabe 1

Erläutern Sie, inwiefern es im Schienenverkehr kritische Abschnitte gibt und wie in diesen Fällen das Prinzip des wechselseitigen Ausschlusses sichergestellt wird.

Aufgabe 2

Eine naive (und Vorsicht: falsche!) Implementierung des wechselseitigen Ausschlusses sieht so aus:

class NaiveCounter {
   long counter = 0;
   boolean locked = false;
 
   public void increment() {
      while (locked) {
 
      }
      locked = true;
      long i = counter;
      i++;
      counter = i;
      locked = false;
   }
}

Probieren Sie den Code im folgenden Programmkasten aus. Was stellen Sie fest?
Begründen Sie mit Hilfe eines Sequenzdiagramms, weshalb der Ansatz scheitert.

Aufgabe 3

Erstellen Sie eine Klasse Konto zur Verwaltung eines Bankkontos. Sie soll folgende Methoden bereitstellen:

double getBalance() gibt den Kontostand in Euro zurück.
void setBalance(double newBalance) setzt den Kontostand in Euro.

Da auf die Konto-Objekte per Internetbanking zugegriffen wird und der Webserver jeden Request in einem eigenen Thread bearbeitet, müssen die Methoden der Klasse Konto threadsicher implementiert werden.

a) Erstellen Sie die Klasse Konto in zwei Varianten (Konto1, Konto2):
- Die Klasse Konto1 nutzt das synchronized-Schlüsselwort.
- Die Klasse Konto2 nutzt einen Semaphor.
b) Erstellen Sie ein Testprogramm, das 10 Threads instanziert, die jeweils eine Million-mal 1 Euro auf ein Konto einzahlen und jeweils 1 Million-mal 1 Euro vom Konto abheben. Überprüfen Sie den Kontostand am Ende der Programmausführung.

Aufgabe 4 (für Interessierte!)

Man kann zeigen, dass naive Ansätze wie in der vorangegangenen Aufgabe nie echten wechselseitigen Ausschluss erreichen. Wie schaffen es dann aber das synchronized-Schlüsselwort oder die Klasse Semaphor?

Beide nutzen spezielle vom Mikroprozessor bereitgestellte Anweisungen, die garantiert atomar sind, d.h. der Prozessor stellt hardwareseitig sicher, dass während ihrer Ausführung keine andere Anweisung ausgeführt wird, auch nicht von einem anderen Prozessorkern.

In diesem Auszug des instruction sets eines eines X86-Prozessors wird insbesondere die atomare XCHG-Anweisung vorgestellt, die den Wert eines Registers mit dem einer Speicherzelle vertauscht. Register sind Speicherzellen innerhalb des Prozessorkerns, die garantiert nur jeweils von einem Thread genutzt werden.

Beschreiben Sie, wie diese Anweisung genutzt werden kann, um wechselseitigen Ausschluss zu erreichen.
Warum sind diese atomaren Anweisungen - verglichen mit nicht-atomaren Anweisungen, die dasselbe leisten - mit einer kleinen Performance-Einbuße verbunden?

In Kapitel 2.1 dieses wissenschaftlichen Artikels noch weitere Beispiele ähnlicher atomarer Anweisung anderer Prozessoren.