Übungsblatt zur 4.Übung: Betriebssysteme

Betriebssysteme
WS 2015/16
Prof. Dr. Winfried E. Kühnhauser
Institut für Praktische Informatik und Medieninformatik
Verteilte Systeme und Betriebssysteme
Technische Universität Ilmenau
23. November 2015
Übungsblatt zur 4.Übung:
Synchronisation
Aufgabe Team 1: Semaphore („The Sleeping Barber Problem”)
Geben Sie für das im Folgenden dargestellte Synchronisationsproblem eine Lösung mittels
Semaphoren an:
In einem Friseurladen gibt es einen Friseur, einen Frisierstuhl (an dem der Friseur arbeitet)
und n Stühle für wartende Kunden. Entwickeln Sie einen Algorithmus, der unter den nachfolgenden Annahmen Friseur und Kunden so synchronisiert, dass jeder wartende Kunde (irgendwann) bedient wird.
1. Der Friseur und alle Kunden agieren parallel.
2. Falls keine Kunden da sind, geht der Friseur schlafen.
3. Wenn ein Kunde kommt, während der Friseur schläft, weckt der Kunde den Friseur
und setzt sich in den Frisierstuhl (und wird bedient).
4. Wenn ein Kunde eintrifft, während der Friseur arbeitet und ein freier Kundenstuhl
vorhanden ist, setzt der Kunde sich und wartet.
5. Trifft ein Kunde ein während der Friseur arbeitet und alle Kundenstühle belegt sind,
verlässt der Kunde den Friseurladen sofort wieder.
6. Wenn der Friseur mit dem Bedienen eines Kunden fertig ist, verlässt dieser Kunde den
Friseurladen, und einer der wartenden Kunden (falls vorhanden) belegt den Frisierstuhl und wird bedient. (Sonst gilt Bedingung 2.)
Diskutieren Sie auch Verhungerungsfreiheit und Fairness Ihrer Lösung.
Hinweis:
Zur Lösung sind selbstverständlich binäre Semaphore geeignet! Eine kürzere Lösung ist
jedoch mittels Zählsemaphoren möglich, die nicht nur die Werte 0 und 1 annehmen können,
sondern allgemein ganzzahlige Werte zwischen 0 und n (n ist dabei eine dem Problem angepasste ganze Zahl > 1). Der Wert eines Zählsemaphors wird dabei durch die entsprechenden
Operationen in Einerschritten nach oben oder unten geändert. Wird beim Wert 0 ein weiteres
Herunterzählen versucht, blockieren Zählsemaphore genauso wie binäre Semaphore.
-1-
Aufgabe Team 2: Semaphore („Das Achterbahnproblem“ – Englisch: „The Roller Coaster
Problem“)
Das Achterbahnproblem nach J.S. Herman (1989) wird durch das folgende Szenario beschrieben:
Eine Anzahl n von „Vergnügungssüchtigen“ (im Folgenden Passagiere genannt) versucht,
möglichst oft eine Fahrt mit einem der m zur Verfügung stehenden Achterbahnwagen zu
unternehmen. Dabei gelten allerdings folgende Bedingungen:
1. Ein Wagen darf nur losfahren, wenn er voll besetzt ist. (Dabei gilt: Jeder Wagen fasst
c Passagiere, wobei die Gesamtzahl der beteiligten Passagiere mehr als nur einen Wagen füllt, d.h. c < n.)
2. Wenn ein Wagen vollständig besetzt ist, fährt er los.
3. Wenn der Wagen nach Abschluss der Fahrt wieder anhält, steigen alle Passagiere aus
und bemühen sich erneut, in einem „neuen“ Wagen eine weitere Fahrt zu unternehmen. (Unter entsprechenden Umständen kann es natürlich auch wieder der gleiche
Wagen sein.)
4. Wagen dürfen sich nicht überholen (was ja beim gegebenen Achterbahn-Problem auch
technisch nicht möglich ist), d.h. die Reihenfolge der Wagen bleibt immer gleich.
Weiterhin gilt: Passagiere und Wagen sollen durch Prozesse simuliert werden, die synchronisiert werden müssen. Für eine der möglichen Lösungen könnten die folgenden Hinweise
hilfreich sein: Bei der Ankunft eines Wagens sollte dieser eine Prozedur „Einsteigen“ aufrufen, danach sollten c Passagiere ihrerseits eine Prozedur „In_Wagen_Einsteigen“ aufrufen.
Nach beendeter Fahrt sollte ein anhaltender Wagen eine Prozedur „Aussteigen“ aufrufen, und
die sich im Wagen befindenden c Passagiere sollten daraufhin eine Prozedur „Wagen_Verlassen“ aufrufen.
Entwickeln Sie eine Lösung des Synchronisationsproblems mit binären oder Zählsemaphoren
(siehe Hinweis zu Aufgabe 1). Diskutieren Sie ebenfalls Verhungerungsfreiheit und Fairness
Ihrer Lösung.
Aufgabe Team 3: Kaffee-Automat
EinKaffeeautomat,seineKundenundeinLieferant,derdenAutomatenregelmäßigmit
KaffeeundKaffeebechernauffüllt,sollensichmittelsbinärerSemaphoresynchronisieren.
Ordnen Sie jedem Teilnehmer Funktionalität so zu, dass folgendes Verhalten realisiert wird:
1. Der Automat kann entweder einen Kunden bedienen oder durch den Lieferanten nachgefüllt werden. Beide Vorgänge sind nicht gleichzeitig möglich!
2. Ein Kunde muss nach Aufforderung durch den Automaten eine Ein-Euro-Münze als
Bezahlung einwerfen, erst danach bekommt er seinen Kaffe. (Um eine ungeeignete
Betriebsweise auszuschließen, soll angenommen werden, dass sich nur Kunden anmelden, die eine Ein-Euro-Münze parat haben – und nach Aufforderung natürlich auch
einwerfen!)
3. Der Lieferant bekommt durch den Automaten mitgeteilt, dass dieser für den Auffüllvorgang bereit ist.
-2-
4. Ein einmal gestarteter Vorgang – Bedienen bzw. Auffüllen – kann nicht mehr unterbrochen werden. Eine neue Anmeldung – durch den nächsten Kunden oder den Lieferanten – wird erst nach Abschluss dieses Vorgangs akzeptiert.
5. Jeweils der nächste Kunde und der Lieferant können sich unabhängig voneinander
beim Automaten anmelden, die Reihenfolge der Bedienung hängt dann davon ab, in
welcher Reihenfolge die Anmeldungen erfolgen.
6. Lieferant und Kunde bekommen den Abschluss des jeweiligen Vorgangs durch den
Automaten mitgeteilt.
7. Falls der Kaffeevorrat verbraucht ist oder keine Becher mehr vorhanden sind, versetzt
der Automat sich selbst in einen Wartezustand, und wartet bis er durch den Lieferanten wieder befüllt ist.
ZurVereinfachungkönnenSieannehmen,dasseszusätzlichzudenSemaphorfunktionenP(semaphore)undV(semaphore)auchnochdieFunktionx=getvalue(semaphore)
gibt,dieaufxalssogenannterRückkehrwertdenaktuellenWertdesSemaphorszurückgibtohneetwasamWertdesSemaphorszuändern,oderSiekönnenzusätzlichzuSemaphorenglobaleBool’sche(logische)–d.h.zweiwertige–Variableverwenden.
-3-

Download Report