Übungsblatt zur 5. Übung Kommunikationsmodelle

Kommunikationsmodelle
SS 2015
Prof. Dr. Winfried E. Kühnhauser (i.A. A. Schindler)
Institut für Praktische Informatik und Medieninformatik
Verteilte Systeme und Betriebssysteme
Technische Universität Ilmenau
19. Juni 2015
Übungsblatt zur 5. Übung
Thema: Synchronisation mittels Botschaften
Allgemeine Bemerkungen
In verteilten Systemen werden zur Synchronisation (zeitlichen Abstimmung) von ablaufenden
Programmen – die im Betriebssystemkontext als Prozesse bezeichnet werden – die blockierenden Eigenschaften synchroner send- bzw. receive-Aufrufe genutzt.
Im Folgenden soll genau dies für die Programme/Prozesse, mit denen die nachfolgenden 3
Probleme beschrieben werden sollen, realisiert werden.
Als Lösung der jeweiligen Aufgabe sind ein Schema der Lösung und eine Darstellung auf
Programmiersprachniveau (möglich auch verständlicher Pseudocode) ausreichend. Dazu muss
eine geeignete Zerlegung des Problems in über Botschaften kommunizierende nebenläufige
(d.h. im allgemeinen Fall auch parallel, also „gleichzeitig“ ausführbare) Programme erfolgen.
Insbesondere muss die Wirkung der verwendeten Botschaften erkennbar sein bzw. erläutert
werden, wenn folgende Kommunikationsoperationen zur Verfügung stehen:
•
•
•
•
send_async() – asynchrones Senden
send_sync() – synchrones Senden
receive_async() – asynchrones Empfangen
receive_sync() – synchrones Empfangen
An welchen Stellen sind ggf. die asynchronen Operationen ausreichend?
(Hinweis: Es muss kein lauffähiges Programm vorgestellt werden.)
Aufgabe Team 1:
(„Das Zigarettenraucher-Problem“/ “The Cigarette Smokers‘ Problem“ – S. S. Patil 1971):
Szenario:
Betrachtet wird eine Gruppe aus vier Personen. Drei davon sind Raucher, die vierte Person
raucht selbst nicht, sondern beeinflusst die Handlungen der Raucher durch ihre Vorgaben. Wir
wollen sie deshalb als „Medium“ (im Sinne von Vermittler) bezeichnen.
Um eine Zigarette selbst anzufertigen, werden drei „Zutaten“ benötigt: Papier, Tabak und
Streichhölzer.
-1-
Einer der Raucher besitzt eine unerschöpfliche („unendliche“) Menge Papier, der nächste eine
„unendliche“ Menge Tabak und der dritte eine „unendliche“ Anzahl Streichhölzer.
Das „Medium“ hat von allen Zutaten unendliche Mengen.
Die vier Personen führen immer wieder das Folgende aus:
1. Das „Medium“ legt zwei Zutaten auf den Tisch (welche, siehe unten).
2. Der Raucher, der die fehlende „Zutat“ besitzt, nimmt die zwei „Zutaten“, fertigt sich
eine Zigarette, raucht diese und bittet danach das „Medium“ weiterzumachen.
3. Das Medium legt daraufhin wiederum zwei Zutaten auf den Tisch … usw. (siehe 1.).
Der Algorithmus, nach dem das „Medium“ verfährt, wird durch folgenden Pseudocode beschrieben:
while (true) do {
wähle nach Zufallsprinzip 2 Zutaten „i“ und „j“ aus der Menge{1,2,3};
platziere beide gewählten Zutaten gleichzeitig auf dem Tisch;
}
Die Handlungen des Mediums und der drei Raucher sind dabei in genannter Weise zu synchronisieren.
Hinweis:
Man beachte, dass auch die Entnahme der “Zutaten” durch die Raucher “atomar” sein müssen,
d.h. der Raucher, welcher die Zutaten entnehmen darf, wird durch beide vorgegebene Zutaten
festgelegt. Ein „Wettkampf“ zweier Raucher (A entnimmt Zutat „i“, B entnimmt Zutat „j“) ist
nicht zulässig – und kann zu mit „normalen“ Mitteln nicht auflösbaren Zuständen, so genannten Verklemmungen (Deadlocks) führen.
Aufgabe Team 2
(„Der schlafende Friseur“/ “Sleeping Barber“ – Dijkstra 1968):
Szenario:
In einem Frisiersalon gibt es einen Friseur, einen Frisierstuhl und n Stühle für wartende Kunden.
Das zu lösende Problem besteht darin, den Friseur und die Kunden so zu synchronisieren,
dass folgende Bedingungen eingehalten werden:
•
•
•
•
Wenn keine Kunden da sind, schläft der Friseur.
Wenn ein Kunde eintrifft, während der Friseur schläft, weckt der Kunde diesen und
nimmt im Frisierstuhl Platz.
Wenn ein Kunde eintrifft, während der Friseur arbeitet und es noch einen freien Wartestuhl gibt, setzt sich der Kunde und wartet.
Wenn ein Kunde eintrifft, der Friseur arbeitet und alle Wartestühle besetzt sind, verlässt der Kunde den Frisiersalon sofort wieder.
-2-
•
Wenn der Friseur einen Kunden bedient hat, verlässt der Kunde den Salon, und einer
der wartenden Kunden nimmt im Frisierstuhl Platz (gegebenenfalls: siehe auch Bedingung 1!)
Aufgabe:
Bilden Sie das Szenario mittels synchroner Kommunikationsoperationen nach (siehe Allgemeine Bemerkungen zu Beginn).
Hinweis:
Der Frisiersalon muss hier keine „tote“ Immobilie sein, sondern könnte im simulierten Szenario als aktive Instanz z.B. auch die Rolle eines zentralen Servers übernehmen.
Aufgabe Team 3
(„Das Achterbahn-Problem“/ “The Roller Coaster Problem“ – J. S. Herman 1989):
Szenario:
Es gebe n „Vergnügungssüchtige“ (zukünftig: Passagiere) und m Achterbahn-Wagen (zukünftig: Wagen).
•
•
•
•
Jeder Passagier wartet wiederholt darauf, eine Fahrt zu unternehmen.
Jeder Wagen fasst c Passagiere, wobei gilt c < n.
Ein Wagen darf nur losfahren, wenn er voll besetzt ist.
Wenn ein Wagen gefüllt ist, fährt er los. Wenn er wieder anhält, steigen alle Passagiere aus.
Weiterhin gilt:
•
Es gibt nur eine „Bahn“ – und die Wagen dürfen [und können] sich nicht überholen.
D.h. sie fahren stets in der Reihenfolge, in der sie gestartet sind.
Aufgabe:
Passagiere und Wagen sollen durch Prozesse nachgebildet werden, die natürlich synchronisiert werden müssen.
•
•
•
Wenn ein „Wagen“ ankommt, sollten c „Passagiere“ eine Prozedur „Ich_steige_ein() “
aufrufen.
Dann sollte ein wartender Wagen eine Prozedur „Abfahrt()“ aufrufen.
Danach (d.h. nach Ende der Fahrt) sollten dieselben c „Passagiere“ dieses „Wagens“
eine Prozedur „Ich_steige_aus( )“ aufzurufen.
Für die „Passagiere“ und die „Wagen“ ist ein Programmschema (siehe Allgemeine Bemerkungen zu Beginn) zu entwickeln.
-3-
Hinweise:
Lösen Sie zur Vereinfachung das Problem zunächst nur für einen einzelnen Wagen und erweitern Sie diese Lösung dann entsprechend der Aufgabenstellung.
Eine Lösung sollte Verhungern vermeiden, jeder wartende Passagier kommt an die Reihe. Die
Lösung sollte ebenfalls effizient sein, d.h. die Wagen (bzw. der Wagen) soll[en] so besetzt
werden, dass jeder Passagier so oft wie möglich mitfahren kann.
Untersuchen Sie die von Ihnen entwickelte Lösung auf jeden Fall bezüglich der genannten
Eigenschaften.
-4-

Download Report