Ein klassisches Problem für nebenläufige Prozesse ist das Problem der Philosophen: n Philosophen sitzen am runden Tisch mit n Gabeln. Jeder Philosoph erlebt der Reihe nach folgende drei Zustände: "Denken", "Hungrig" und "Essen". Zum Denken braucht er keine Gabel. Wenn er hungrig wird, greift er zu den Gabeln an seinem rechten und an seinem linken. Wenn sie nicht frei sind, bleibt er hungrig und wartet, bis beide seine Nachbarn nicht mehr essen. Wenn die Gabeln frei sind, fängt er an zu essen. Dann müssen seine beiden Nachbarn gegebenenfalls hungrig warten, bis er fertig ist. Anschließend versinkt er wieder in den Denkzustand, bis er hungrig wird. Die Frage ist, ob es möglich ist, die Aktivitäten der Philosophen untereinander so zu koordinieren, daß niemand verhungert.
Die folgende Lösung dieses Problems für n = 5 illustriert die Verwendung von dynamischen und statischen Prozeßobjekten. Den Philosophen entsprechen 5 statisch erzeugte Prozesse; diese starten zusammen mit dem Hauptprogramm. Ihre Rümpfe sind jedoch so programmiert, daß sie gleich zu Anfang auf den Aufruf ihres Eingangs Initialisieren warten. Über diese erfahren sie, zu welchen beiden (dynamisch erzeugten) Gabel-Prozessen links bzw. rechts über einen Verweis Zugriff haben. Dieser Zugriff erfolgt über den Aufruf dessen Eingangs Aufheben. Nach dem erfolgreichen Aufheben der linken Gabel (d.h. wenn diese Gabel vom Nachbarn nicht benutzt wird) versucht der Philosoph, seine rechte Gabel aufzuheben. Falls dies innerhalb eines gewissen Zeitraums (im Programm 0,1 Sekunden) nicht gelingt, wird die Gabel abgelegt (über deren Eingang Ablegen), damit der Nachbar (ein anderer Philosoph-Prozeß) die Möglichkeit hat, diese aufzuheben.
Wenn die rechte Gabel auch aufgehoben werden kann (wenn dieser Gabel-Prozeß am Eingang Aufheben wartet), kann der Philosoph "speisen" (d.h. eine entsprechende Meldung ausgeben). Seine Speisung wird in einer Tabelle protokolliert und es wird überprüft, ob nicht ein anderer Philosoph verhungert, d.h. eine Anzahlen der Speisungen nicht zu sehr (im Programm 10) voneinander abweichen. Anschließend werden die beiden Gabeln abgelegt (hierdurch wird das "Denken" modelliert), und dann die nächste Mahlzeit versuchen, da der Philosoph "hungrig ist".
with Text_IO; -- PHILSOPH.ADA procedure Philosophen is type TPhilosoph is (Aristoteles, Schopenhauer, Hegel, Kant, Marx); -- weitere koennen hinzugefuegt werden -- dieses Programm illustriert das Problem mit n = 5 type TGabel is new TPhilosoph; -- Gabel-Namen werden nicht gebraucht -- der Philosoph Nr. I hat die Gabeln Nr. I und Nr. I+1; die rechte Gabel des letzten Philosophen ist Nr. 0
Anzahl_Mahlzeiten: constant := 100; -- kann ruhig erhöht werden Verhungert: constant := 10; -- ein Philosoph verhungert, wenn ein anderer viel mehr Mahlzeiten eingenommen hat Geduld: constant := 100; -- ein Philosoph verliert Geduld, wenn er zu oft erfolglos versucht, die Gabeln aufzuheben Wartezeit: constant := 0.1; -- Sekunden, kann veraendert werden
type TAnzahl_Speisungen is array (TPhilosoph) of Natural; Anzahl_Speisungen: TAnzahl_Speisungen := TAnzahl_Speisungen'(others => 0); -- Zaehler fuer jeden Philosophen
task type TGabel_Prozess is entry Aufheben; entry Ablegen; end TGabel_Prozess; type PGabel is access TGabel_Prozess; -- Verweis auf ein Gabel-Prozess task type TPhilosoph_Prozess is entry Initialisieren (Name: in TPhilosoph; Linke_Gabel, Rechte_Gabel: in PGabel); end TPhilosoph_Prozess;
Alle_Philosophen: array (TPhilosoph) of TPhilosoph_Prozess; -- 5 Philosoph-Prozesse entstehen hier -- sie warten aber gleich zu Beginn auf Initialisieren (wird im Hauptprogramm aufgerufen) Alle_Gabeln: array (TGabel) of PGabel; -- hier entstehen keine Gabel-Prozesse, nur Verweise -- die Gabel-Prozesse entstehen im Hauptprogramm durch new
task body TGabel_Prozess is begin Text_IO.Put_Line (Item => "Gabel liegt am Tisch"); loop select accept Aufheben; -- zuerst wartet auf den Aufruf Aufheben accept Ablegen; -- dann wartet auf den Aufruf Ablegen or terminate; -- wenn keine Aufrufe mehr vorliegen und alle Prozesse terminieren koennen end select; end loop; end TGabel_Prozess;
task body TPhilosoph_Prozess is Philosoph: TPhilosoph; -- der Name des Philosophen, modelliert durch diesen Prozess Links, Rechts: PGabel; -- Verweise auf die beiden Gabeln des Philosophen Beide: Boolean := False; -- True wenn der Philosoph beide Gabeln aufgehoben hat Mahlzeiten, Versuche: Natural := 0; -- Anzahl der Speisungen dieses Philosophen und der Versuche, die Gabeln aufzuheben begin -- jeder Philosoph-Prozess wartet zu Anfang auf den Aufruf des Eingangs Initialisieren: accept Initialisieren (Name: in TPhilosoph; Linke_Gabel, Rechte_Gabel: in PGabel) do Philosoph := Name; -- Parameterwerte werden vom Aufrufer (vom Hauptprozess) uebernommen Links := Linke_Gabel; Rechts := Rechte_Gabel; end Initialisieren; -- der Philosoph-Prozess kann nun selbstaendig weiterlaufen
Text_IO.Put_Line (Item => TPhilosoph'Image (Philosoph) & " denkt"); -- der Philosoph wird langsam hungrig und versucht seine Mahlzeiten einzunehmen: for IMahlzeit in 1 .. Anzahl_Mahlzeiten loop Text_IO.Put_Line (Item => TPhilosoph'Image (Philosoph) & " ist hungrig"); while not Beide loop Links.Aufheben; -- Philosoph wartet hier, bis die linke Gabel frei ist Text_IO.Put_Line (Item => TPhilosoph'Image (Philosoph) & " hat linke Gabel"); Versuche := Versuche + 1; select Rechts.Aufheben; -- Philosoph wartet hier, bis die rechte Gabel frei ist Beide := True; Text_IO.Put_Line (Item => TPhilosoph'Image (Philosoph) & " speist");
-- Speisung protokollieren und pruefen ob jemand nicht verhungert: Mahlzeiten := Anzahl_Speisungen (Philosoph) + 1; Anzahl_Speisungen (Philosoph) := Mahlzeiten; for I in TPhilosoph loop if Anzahl_Speisungen (I) < Mahlzeiten - Verhungert then Text_IO.Put_Line (Item => TPhilosoph'Image (I) & " verhungert"); abort Alle_Philosophen (I); -- anderen Prozess (des verhungerten Phiosohen) beenden end if; end loop;
or delay Wartezeit; -- oder wenn innerhalb der Wartezeit die rechte Gabel nicht aufgehoben werden kann, Links.Ablegen; -- wird dem Nachbarn eine Chance gegeben if Versuche >= Geduld then Text_IO.Put_Line (TPhilosoph'Image (Philosoph) & " verliert Geduld. Er hat " & Natural'Image (Anzahl_Speisungen (Philosoph)) & " Mahlzeiten eingenommen"); abort Alle_Philosophen (Philosoph); -- sich selbst beenden end if; end select; end loop; -- Philosoph hat die Mahlzeit eingenommen, Links.Ablegen; -- er braucht die Gabeln nicht mehr Rechts.Ablegen; -- jetzt koennen seine Nachbarn speisen Beide := False; Versuche := 0; -- Zaehler zuruecksetzen Text_IO.Put_Line (Item => TPhilosoph'Image (Philosoph) & " denkt"); end loop; -- die naechste Mahlzeit kann eingenommen werden Text_IO.Put_Line (Item => TPhilosoph'Image (Philosoph) & " geht nach Hause"); end TPhilosoph_Prozess;
ILinks, IRechts: TGabel; -- Aufzaehlungsobjekte indizieren Alle_Gabeln begin -- die 5 Philosoph-Prozesse starten hier und warten auf den Aufruf ihres Eingangs Initialisieren Text_IO.Put_Line (Item => "Der Tisch ist gedeckt");
-- die 5 Gabeln erzeugen: for IGabel in TGabel loop Alle_Gabeln (IGabel) := new TGabel_Prozess; -- die 5 Gabel-Prozesse entstehen und starten hier end loop; -- sie warten ab sofort auf den Aufruf ihres Eingangs Aufheben
-- die 5 wartenden Philosoph-Prozesse nacheinander weiterfahren lassen, d.h. ihren Eingang Initialisieren aufrufen; -- ueber Parameter werden ihnen ihre Namen, sowie den Verweis auf ihren beiden Gabeln mitgeteilt for IPhilosoph in TPhilosoph loop ILinks := TGabel'Val (TPhilosoph'Pos (IPhilosoph)); -- Index der linken Gabel des Philosophen = Index des Philosophen if IPhilosoph < TPhilosoph'Last then -- Index der rechten Gabel des Philosophen = Index des Philosophen + 1, bzw. = 0 fuer den letzten IRechts := TGabel'Val (TPhilosoph'Pos (TPhilosoph'Succ (IPhilosoph))); else -- letzter Philosoph IRechts := TGabel'First; -- sie sitzen an einem runden Tisch end if; Alle_Philosophen (IPhilosoph).Initialisieren (Name => IPhilosoph, Linke_Gabel => Alle_Gabeln (ILinks), Rechte_Gabel => Alle_Gabeln (IRechts)); -- Der Philosoph-Prozess Nr. IPhilosoph kann ab sofort weiterarbeiten end loop;
Text_IO.Put_Line (Item => "5 Philosophen warten, essen und denken"); -- das Hauptprogramm wartet auf das Ende der 5 Philosoph- und der 5 Gabel-Prozesse end Philosophen;
Die Frage, ob es einen Philosophen gibt, der verhungert, d.h. nie zum speisen kommt, weil er ständig von einem anderen Prozeß blockiert wird. Möglicherweise verhungern alle Philosophen, wenn sie sich gegenseitig blockieren. Dies sollte durch den Terminplaner verhindert werden. Dies ist der Algorithmus, der im Hintergrund läuft und die Betriebsmittel unter den wartenden Prozessen verteilt, d.h. bestimmt, welche der lauffähigen und wartenden Prozesse als nächstes die Betriebsmittel erhält. Es ist nicht bekannt, ob es einen Terminplaner-Algorithmus gibt, der garantiert, daß im obigen Programm kein Philosoph verhungert.
Die Textausgabe des obigen Programms kann in eine Textdatei umgeleitet werden. Die Untersuchung des Inhalts ergibt interessante Sachverhalte gerade über den Terminplaner. Über seine Intelligenz zeugt, wenn die Häufigkeit der zu Anfang zahlreiche Ausgaben "... hat linke Gabel" abnimmt: Er merkt die ständige gegenseitige Blockade und versucht, die Betriebsmittel (die Gabel) nach einen anderen Verfahren zuzuordnen. Fehlerhafte Zeilenumbrüche in der Ausgabe zeugen über die zeitliche Verzahnung der Prozesse: Die Ausgabe von Aristoteles unterbricht z.B. die Ausgabe von Marx. Hoffentlich meldet aber das Programm gegen Ende: "Kant geht nach Hause". Nach einigen weiteren Speisungen verabschieden sich alle Philosophen.
Rückmeldungen bitte an den Autor solymosi@tfh-berlin.de
Leitseite des Autors