Raucherproblem

Kern des Raucherproblems

Das Raucherproblem ist eine Problemstellung der Prozesssynchronisation, die Suhas S. Patil 1971 formulierte. Es zeigt, wie parallel ablaufende Tätigkeiten (Prozesse oder Threads) Ressourcen gemeinsam nutzen müssen, ohne sich gegenseitig zu blockieren. Zentral ist die Abstimmung: Ein Prozess soll aufgeweckt werden, sobald die für ihn nötigen Ressourcen bereitstehen; Prozesse ohne verfügbare Ressourcen sollen warten. Das Problem ist wichtig, weil eine unpassende Synchronisation zu einem Deadlock führen kann. Ein Deadlock ist eine Verklemmung, bei der Prozesse dauerhaft aufeinander warten und keiner fortfahren kann.

Modell mit Händler und Rauchern

Bildlich gibt es einen Tabakwarenhändler und drei Kettenraucher an einem Tisch. Für eine Zigarette werden Tabak, Zigarettenpapier und Streichhölzer benötigt.

• Raucher A besitzt unendlich viel Tabak.
• Raucher B besitzt unendlich viel Zigarettenpapier.
• Raucher C besitzt unendlich viele Streichhölzer.
• Der Händler besitzt von allen drei Zutaten unendlich viel.

Ist der Tisch leer, legt der Händler zufällig zwei Zutaten darauf. Der Raucher, der die passende dritte Zutat besitzt, kann die beiden Zutaten nehmen, eine Zigarette drehen und rauchen. Der Händler darf erst dann wieder Material hinlegen, wenn der Tisch leer ist. Ein Raucher, der gerade raucht, kann passende Zutaten erst nach dem Rauchen vom Tisch nehmen. Deshalb muss die Steuerung sicherstellen, dass nur der passende Raucher reagiert und der Tisch anschließend wieder freigegeben wird.

Technische Formulierung und Deadlock

Technisch wird das Problem mit mehreren Threads und Semaphoren beschrieben. Ein Semaphor ist ein Synchronisationsmittel: Mit warten wird auf eine Freigabe gewartet, mit freigeben wird sie signalisiert. Der Händler wird durch die drei Threads TA, TB und TC dargestellt. Sie warten jeweils auf die gemeinsame Semaphore tischleer, geben zwei Ressourcen frei und informieren danach den passenden Raucher-Thread. Für TA lautet der Beispielcode:

tischleer.warten() tabak.freigeben() papier.freigeben()

Patil schränkte das Problem zusätzlich ein: Der Händler dürfe sein Verhalten nicht ändern, und bedingte Semaphore sowie Felder von Semaphoren seien nicht erlaubt. Unter diesen Einschränkungen ist der gezeigte Pseudocode ungültig und das Problem unlösbar. David Parnas hielt besonders die zweite Einschränkung für unangebracht, weil dadurch viele Probleme unlösbar würden.

Ohne diese zweite Einschränkung besteht die Aufgabe darin, einen passenden Code für die Raucher zu finden. Die scheinbar einfache Lösung, dass jeder Raucher einzeln auf Zutaten wartet, kann einen Deadlock erzeugen. Legt der Verkäufer Tabak und Papier hin, kann Raucher A den Tabak und Raucher B das Papier nehmen. Beide warten dann unendlich lange auf die jeweils andere Zutat. Niemand meldet, dass der Tisch wieder frei ist.

Lösung mit zusätzlichen Zuweisungs-Threads

David Parnas stellte eine Lösung ohne bedingte Semaphore vor. In einer besser lesbaren Fassung von Allen Downey werden bedingte Verzweigungen verwendet. Drei zusätzliche Threads übernehmen die Zuweisung der Zutaten; jeder wartet auf eine bestimmte Zutat. Boolesche Variablen und ein Mutex synchronisieren diese Threads. Ein Mutex ist eine Sperre, die nur einem Thread gleichzeitig den Zugriff auf den geschützten Bereich erlaubt.

Wartet der Tabak-Thread und stellt fest, dass papierSchonGenommen wahr ist, folgt daraus: Papier und Tabak lagen auf dem Tisch. Er setzt papierSchonGenommen auf false und gibt raucherMitStreichholz frei. Falls stattdessen streichholzSchonGenommen wahr ist, wird raucherMitPapier freigegeben. Andernfalls merkt sich der Thread mit tabakSchonGenommen = true, dass Tabak bereits angekommen ist.

Der passende Raucher wartet auf sein Signal, dreht eine Zigarette, gibt anschließend den Tisch frei und raucht. So werden die beiden auf dem Tisch liegenden Zutaten gezielt genau dem Raucher zugeordnet, der die dritte Zutat besitzt.

Vereinfachte direkte Signalisierung

Eine einfachere Variante lässt den Händler die Raucher direkt informieren. Dazu gibt es ein Array binärer Semaphore A mit genau einer Semaphore pro Raucher sowie die Semaphore v für den Verkäufer. Binäre Semaphore haben dabei nur zwei Zustände.

Der Verkäufer wartet in einer Endlosschleife mit down(v), wählt zufällig zwei Raucher aus und bestimmt damit den dritten als Raucher k. Dieser kann rauchen, daher signalisiert der Verkäufer up(A[k]). Raucher i wartet mit down(A[i]), dreht eine Zigarette, gibt mit up(v) den Verkäufer frei und raucht anschließend. Die direkte Benachrichtigung verhindert, dass mehrere Raucher einzelne Zutaten aufnehmen und dadurch eine Verklemmung entsteht.