Das „Dining philosophers problem“ – yeah, Informatik!
Das „Dining-Philophers-Problem“ ist eine Parallelisierungsaufgabe aus der Informatik. Fünf Philosophen sitzen um einen Tisch mit für Tellern und fünf Gabeln dazwischen. Wenn einer von ihnen essen möchte, benötigt er beide Gabeln neben seinem Teller.
By Benjamin D. Esham / Wikimedia Commons, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=56559
Damit können jeweils nur zwei Philosophen gleichzeitig essen und es muss jeweils ein Teller zwischen ihnen sein, an dem nicht gegessen wird. Eine historische Lösung des Problems kann man direkt in einer Publikation von Dijkstra nachlesen (S.29). Das hätte man einfach formalisieren können. Oder halt selbst nachdenken.
In der Informatikwelt sind die Philosophen Prozesse, die um die Betriebssystemressourcen auf dem Tisch konkurrieren. Dabei muss man vermeiden, dass sich die Prozesse gegenseitig blockieren: Wenn alle gleichzeitig wollen, gibt es Streit und keiner kann die Ressourcen belegen, die er zum Essen braucht (informatisch: Verklemmung). Es darf aber auch keine Situation eintreten, in der alle so höflich sind, sich immer gegenseitig den Vortritt zu lassen (informatisch: Aushungerung). Und natürlich soll der Zugriff auf die Ressourcen fair und effizient sein.
Die Herausforderung:
Man „denkt“ beim Formalisieren nicht nur für einen Prozess, sondern für fünf, die miteinander in einer definierten Umgebung interagieren.
Wer darf dann überhaupt miteinander essen?
Um das zu formalisieren, nehmen wir mal eine simple minimale Datenstruktur – ein Feld mit einem booleschen Element für jeden Prozess – d.h. jeder hat sein Flag, dass er auf „ich will essen“ setzen kann. Dann gibt es fünf zulässige Konstellationen:
10100 10010 01010 01001 00101
Das ist schonmal hübsch, da es tatsächlich nur fünf zulässige Fälle gibt. Boolesche Werte zu scannen und zu manipulieren ist ressourcenmäßig auch nicht so üppig aufwändig.
Eine Entscheidung, ob man zwei Philosophen an den Tisch lässt, kann man verlässlich fällen, wenn drei von ihnen ihr Interesse bekundet haben.
Damit nicht genug: Die Prozesse müssen sich weiterhin untereinander steuern können, damit sie sich gegenseitig an den Tisch lassen können.
Ansatz
Man lässt immer drei Prozesse in einen Empfangsbereich, die beiden anderen bleiben draußen und stellen sich an. Dann lässt man die mögliche Konstellation von zwei Philosophen an den Tisch. Derjenige, der nicht zum Zuge kommt, bleibt in einem zweiten Wartebereich vor dem Tisch stehen (= sein Flag im Array bleibt gesetzt).
Wenn einer der am Tisch Essenden aufsteht, kippt er sein Flag im Array, lässt einen aus der Schlange im Empfangsbereich rein und stellt sich draußen hinten wieder an.
Ein besonderes Problem ist die Konstellation:
10101
Bei sowas sollte man die Reihenfolge der Prüfung mal variieren, damit nicht immer die gleichen zwei zum Zuge kommen und der Dritte „verhungert“ (das ist bei fünf Prozessen nicht sehr wahrscheinlich, aber durchaus mal möglich).
Wie macht man das mit dem Warten eigentlich?
Die einfachste Lösung besteht darin, die Prozesse in Endlosschleifen mit einer Abbruchbedingung (Prüfung einer globalen Variable) zu schicken, wenn sie im Empfangsbereich oder vor dem Tisch stehen. Dabei verbraten Sie bloß reichlich Rechenzeit – informatisch heißt das „aktives Warten“ (busy wait) – also dauernd herumquengeln, ob man nicht endlich dran ist. Moderne Betriebssysteme bekommen das hin, mit sowas umzugehen, aber netter ressourcenschonender Programmierstil ist das nicht.
Semaphoren als Lösung
Semaphoren sind Datenstrukturen, die einen negativen oder positiven ganzahligen Wert annehmen können und zusätzlich einen Counter besitzen. Positive Werte geben die Anzahl der zur Verfügung stehenden Ressourcen an, negative die Anzahl der Prozesse, die bereits auf die Zuteilung einer Ressource warten.
Der Counter ist wie der Wert des Semaphors für Anwendungsprogramme nicht einsehbar. Innerhalb eines Prozesses kann ein Anwendungsprogramm eine sogenannte P‑Operation auf einen Semaphor ausführen. Wenn der Semaphor einen positiven Wert hat, wird dieser um eins erniedrigt (= eine Ressource vergeben) und der Prozess darf weitermachen. Wichtig dabei: Das Betriebssystem entscheidet, welcher Prozess die Ressource erhält (meist FIFO, muss aber nicht).
Wenn der Wert negativ oder null ist, wird auch um eins erniedrigt und der Prozess muss warten (Auf Betriebssystemebene wird dem Prozess der Prozessor entzogen, er bleibt im Speicher aktiv, verbraucht aber außer Speicher kaum weitere Ressourcen mehr).
Wenn der Prozess fertig ist, führt er eine V‑Operation auf den Semaphor aus, der sich dadurch um Eins erhöht. Semaphoren müssen, um die Interaktion von Prozessen steuern zu können, globale Datenstrukturen sein.
Kritische Abschnitte
Da Prozesse den Zustand bzw. Wert von Semaphoren nicht abfragen, sondern nur inkrementieren oder dekrementieren können, „erfahren“ sie voneinander nur über globale Variablen oder sonstige Datenstrukturen, in unserem Fall z.B. das Array mit den booleschen Elementen.
Wenn man auf globalen Datenstrukturen mit mehreren Prozessen arbeitet, muss man sicherstellen, dass das immer nur ein Prozess tun kann. Man sperrt solche Strukturen oder auch kritische Abschnitte durch einen extra Semaphor (P‑Operation), macht seine Arbeit und entsperrt diesen Semaphor wieder (V‑Operation). Solche Semaphoren haben nur 0 und 1 als Zustände und werden oft als „mutex“ bezeichnet. Damit wird verhindert, dass zwei Prozesse solche Datenstrukturen gleichzeitig verändern (oder lesen) und damit Inkonsistenzen entstehen.
Meine Lösung (mittlerweile nach Rückmeldungen)
In der Vorlesung wird eine recht eigenwillige Beschreibungssprache verwendet. Das hat damit zu tun, dass man nicht oft nur wenig über der Maschinensprache bewegt, die dann deutlich eingeschränkter im Befehlssatz ist. Wenn man auf globale Datenstrukturen lesend oder schreibend zugreift, muss man das „atomar“ machen (dafür sorgen, dass man alleine ist).
TYPE philId = (0..4);
hungry_phils : SEMAPHORE == 3; // wir haben vorerst drei Plätze
privsem : ARRAY (0...4) OF SEMAPHORE == [EACH == 0]; // persönlicher Warteplatz am Tisch
mutex_helper : SEMAPHORE == 1;
hungry_phils_array : ARRAY BOOLEAN OF slot == [EACH == FALSE];
swap_check : BOOLEAN == FALSE;
philosopher : PROCESS (id : IN philId)
BEGIN
LOOP
--denken
P(hungry_phils);
P(mutex_helper);
hungry_phils_array[id] == true;
IF swap_check
IF hungry_phils_array[0] AND hungry_phils_array[2]
let_eat[0,2];
ELSEIF hungry_phils_array[0] AND hungry_phils_array[3]
let_eat[0,3];
ELSEIF hungry_phils_array[1] AND hungry_phils_array[3]
let_eat[1,3];
ELSEIF hungry_phils_array[1] AND hungry_phils_array[4]
let_eat[1,4];
ELSEIF hungry_phils_array[2] AND hungry_phils_array[4]
let_eat[2,4];
ENDIF
ELSE
IF hungry_phils_array[4] AND hungry_phils_array[2]
let_eat[4,2];
ELSEIF hungry_phils_array[4] AND hungry_phils_array[1]
let_eat[4,1];
ELSEIF hungry_phils_array[0] AND hungry_phils_array[3]
let_eat[0,3];
ELSEIF hungry_phils_array[1] AND hungry_phils_array[3]
let_eat[1,3];
ELSEIF hungry_phils_array[0] AND hungry_phils_array[2]
let_eat[0,2];
ENDIF
ENDIF
IF NOT swap_check
swap_check == TRUE;
ELSE
swap_check == FALSE;
ENDIF
V(mutex_helper);
P(privsem[id]);
--essen
P(mutex_helper);
hungry_phils_array[id] == false;
P(mutex_helper);
V(hungry_phils);
REPEAT;
let_eat : PROCEDURE (id1 : CARDINAL,id2 : CARDINAL)
BEGIN
V(privsem[id1]);
V(privsem[id2]);
END
END
Da steckt deutlich mehr Gehirnschmalz drin, als es den Anschein hat – z.B. war es gar nicht so einfach, immer dafür zu sorgen, dass zwei Philosophen gleichzeitig essen. In alternativen Lösungsvorschlägen aus dem Tutorium wäre auch ein Einzelessen möglich gewesen.
Wie geht in der Vorlesung weiter?
Semaphoren sind bisher Blackboxen. Jetzt wird geschaut, wie ein Betriebssystem Semaphore realisiert (das geht übrigens manchmal nicht ohne „busy waiting“). Letztlich geht es im Zuteilung von Rechenzeit an Prozesse. Ich kann gedanklich momentan nur leidlich mithalten und brauche letztlich zu viel Zeit für Lösungen. Das wird in der Klausur später spannend …
This work by Maik Riecken is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International
Pingback: Als fertig ausgebildete Lehrkraft selbst Prüfungen ablegen « Gesellschaft « riecken.de