Raucherproblem

Das Raucherproblem ist eine Problemstellung der Prozesssynchronisation und wurde von Suhas S. Patil 1971 formuliert. Es beschreibt ein bestimmtes Verhalten von parallel ablaufenden Tätigkeiten, die gezwungen sind, gewisse Ressourcen gemeinsam zu nutzen, und stellt die Frage nach Möglichkeiten der Absprache, um einen reibungslosen Ablauf zu ermöglichen.

Problembeschreibung

Motivation für die Problemstellung ist ein Betriebssystem, das unabhängige Prozesse organisiert, die auf Zuteilung von Ressourcen warten (auch schlafen genannt). Steht dem Betriebssystem eine Ressource zur Verfügung, die es einem Prozess erlauben würde, fortzufahren, sollte der Prozess informiert werden (auch aufwecken genannt). Prozesse, für die gerade keine Ressourcen verfügbar sind, sollen im Wartezustand belassen werden.

Bildliche Beschreibung

Das Problem wird bildlich durch einen Tabakwarenhändler und drei Raucher beschrieben, die zusammen an einem Tisch sitzen. Zum Rauchen benötigen die Raucher folgende Dinge: Tabak, Zigarettenpapier und Streichhölzer. Jeder der Kettenraucher hat einen unendlichen Vorrat an genau einer Ressource: Raucher A hat unendlich viel Tabak, Raucher B unendlich viel Zigarettenpapier und Raucher C unendlich viele Streichhölzer. Der Tabakwarenhändler hat von allen drei Zutaten unendlich viel Vorrat.

Ist der Tisch leer, wählt der Tabakwarenhändler zwei der drei Zutaten zufällig aus und legt sie auf den Tisch. Einer der Raucher kann nun mit seiner passenden dritten Zutat eine Zigarette drehen und rauchen. Da die Raucher immer rauchen wollen, nimmt der entsprechende Raucher die Zutaten auf und beginnt zu rauchen. Der Händler kann nun wieder zufällig Zutaten auf den Tisch legen. Der gerade belieferte Raucher könnte für ihn passende Zutaten aber erst dann vom Tisch nehmen, wenn er seine Zigarette zu Ende geraucht hat. Sind die zufälligen Zutaten für einen anderen Raucher geeignet, so kann dieser sie vom Tisch nehmen und rauchen. Der Tabakwarenhändler legt immer neues Material auf den Tisch, wenn dieser leer ist. Andernfalls muss er warten.

Technische Beschreibung

Technisch lässt sich das Problem durch mehrere Threads und Semaphore beschreiben. Der Tabakwarenhändler entspricht drei verschiedenen Threads TA, TB und TC, die jeweils auf eine gemeinsame Semaphore tischleer warten (die den freien Tisch anzeigt), die Ressourcen freigeben und dann den passenden Raucher-Thread informieren.

Beispielhaft sei ein Pseudo-Programmcode für Thread TA genannt:

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

Patil stellte noch zwei weitere Bedingungen als Einschränkungen auf, um zu zeigen, dass Semaphore als Lösung für manche Probleme nicht ausreichend sind. Er forderte erstens, dass der Tabakwarenhändler sein Verhalten nie ändert und dass zweitens keine bedingten Semaphoren und Felder von Semaphoren erlaubt sind. Mit dieser Einschränkung ist der Pseudo-Programmcode ungültig und das Problem sogar unlösbar. David Parnas fand jedoch, dass die zweite Einschränkung unangebracht sei, denn damit wären viele Probleme unlösbar.

Lässt man die zweite Einschränkung außer Betracht, ist das Problem, einen passenden Programmcode für die Raucher zu finden. Die naheliegende Lösung, dass die Raucher auf die einzelnen Zutaten warten und sie nehmen, kann zu einem Deadlock führen. Hat der Raucher A mit Streichhölzern folgenden Programmcode

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

und die anderen Raucher entsprechenden Code mit den passenden Zutaten, dann kann es passieren, dass der Verkäufer Tabak und Papier auf den Tisch legt und Raucher A den Tabak nimmt, während ihm Raucher B zuvorkommt und das Papier nimmt. Beide Raucher würden nun unendlich lange gegenseitig darauf warten, die andere Zutat zu bekommen, denn sie kommen nicht dazu, anzuzeigen, dass der Tisch frei ist.

Lösung

David Parnas stellte eine Lösung ohne bedingte Semaphoren vor. Allen Downey verwendet für eine etwas besser lesbare Lösung bedingte Verzweigungen. Sie basiert auf drei zusätzlichen Threads, die die Zuweisung der Zutaten übernehmen. Jeder der Threads wartet auf eine andere der drei Zutaten. Die drei Threads sind über boolesche Variablen und einen Mutex synchronisiert, sodass jeder Thread weiß, ob ein anderer bereits die Zuweisung begonnen hat. Der Programmcode für den Thread, der auf Tabak wartet, könnte so aussehen:

tabak.warten()
mutex.warten()
   if papierSchonGenommen:
      papierSchonGenommen = false
      raucherMitStreichholz.freigeben()
   else if streichholzSchonGenommen:
      streichholzSchonGenommen = false
      raucherMitPapier.freigeben()
   else
      tabakSchonGenommen = true
mutex.freigeben()

Ist die Variable papierSchonGenommen wahr, weiß dieser Thread, dass der auf Papier wartende Thread schon gelaufen ist. Also lagen Papier und Tabak auf dem Tisch und dieser Thread erlaubt dem Raucher mit Streichholz, sich die Zutaten zu nehmen und zu rauchen. Dessen Programmcode sieht dann so aus:

raucherMitStreichholz.warten()
zigaretteDrehen()
tischfrei.freigeben()
rauchen()

Vereinfachte Lösung

Eine weitere Vereinfachung des Problems, dass der Tabakwarenhändler die Raucher direkt informiert, macht die Lösung sehr einfach: Man definiert ein Array binärer Semaphoren (A), mit je einem Semaphor pro Raucher. Dem Verkäufer ist ebenfalls ein Semaphor zugeordnet: v.

Der Pseudo-Programmcode für den Verkäufer lautet:

while true {
    down(v);
    Wähle zwei Raucher zufällig aus, der dritte wird Raucher k. Raucher k kann nun rauchen
    up(A[k]);
}

Der Pseudo-Programmcode für Raucher i lautet:

while true {
    down(A[i]);
    Drehe eine Zigarette
    up(v);
    Rauche die Zigarette
}

Siehe auch

• Philosophenproblem
• Erzeuger-Verbraucher-Problem
• Deadlock

Literatur

• Andrew S. Tanenbaum: Modern Operating Systems. 2. Auflage. Prentice-Hall, Upper Saddle River (N.J.) 2001, ISBN 0-13-031358-0
  • Moderne Betriebssysteme. 2. Auflage. Pearson Studium, München 2002, ISBN 3-8273-7019-1
• Allen B. Downey: The Little Book of Semaphores. SoHo Books, New York 2008, ISBN 978-1-4414-1868-5
• Suhas Patil: Limitations and capabilities of Dijkstra’s semaphore primitives for coordination among processes (= Computation Structure Group Memo. Bd. 57). MIT, Cambridge 1971