<< Übung 2 | Index | Übung 4? >>

Betriebssysteme 1 - Übung 3

Aufgabe 1 Speisende Philosophen

Handarbeit. Ein sehr bekanntes Problem der Synchronisation ist das Problem der speisenden Philosophen. Es besteht folgende Situation: an einem runden Tisch sitzen fünf Philosophen. Vor jedem Philosophen steht ein Teller mit Nudeln und zwischen je zwei Tellern liegt ein Stäbchen. (es handelt sich offensichtlich um chinesische Philosophen) Die Philosophen agieren unabhägig voneinander und von Zeit zu Zeit wird jeder dieser Philosophen von den Nudeln auf seinem Teller essen. Er benötigt dazu die beiden Stäbchen rechts und links von seinem Teller.

Abbildung 1: Der Tisch der speisenden Philosophen

Da jedes Stäbchen nur von einem Philosophen gleichzeitig verwendet werden kann haben wir es hier mit einem XBM zu tun. Verwende die aus der Vorlesung bekannten Mittel wie Mutex oder Semaphore um den wechselseitigen Ausschluß des Stäbchens zu garantieren. Tritt bei deiner Lösung ein Problem auf obwohl die Anforderungen an einen wechselseitigen Ausschluß gewährleistet sind? Findest du eine Möglichkeit dieses Problem zu lösen?

Das Problem der Philosophen ist das folgende: Alle werden auf einmal hungrig und schauen nach links und rechts, ob beide Stäbchen da sind. Bei allen ist das der Fall. Jeder nimmt zuerst das rechte Stäbchen auf, und will zum linken greifen, doch das hat der linke Nachbar genommen. Jeder hält ein Stäbchen, dass er nicht mehr heraus geben will, und alle fünf verhungern. Es sind sehr dickköpfige Philosophen.

Es muss also ein Weg gefunden werden, das Überprüfen, ob die Stäbchen da sind, und das Aufnehmen derselben in einem durchzuführen. Die Philosophen könnten z. B. mit beiden Händen gleichzeitig nach links und rechts tasten, und wenn sie beide Stäbchen spüren, ohne dass da noch die Hand eines der Nachbarn dabei ist, dann können sie die Stäbchen aufnehmen.

Alternativ kann man einen Mutex (einen binären Semaphor) verwenden, um das Überprüfen und Aufnehmen der Stäbchen ununterbrechbar zu machen:

 

semaphore grep_sticks = 1;

void eat() {

  /* Solange versuch beide Stäbchen aufzunehmen, bis
   * es geklappt hat. Niemals ein einzelnes Stäbchen
   * behalten, sonst hold-and-wait-Situation und 
   * Deadlock-Gefahr! 
   */

  do {
    /* Zugriff auf die Stäbchen wird synchronisiert,
     * kritischen Bereich betreten 
     */
    down(grep_sticks);

    /* Überprüfen, ob beide Stäbchen da sind */
    if (linkes Stäbchen da) und (rechts Stäbchen da) {
      Nimm linkes Stäbchen;
      Nimm rechtes Stäbchen;
    }

    /* Kritschen Bereich verlassen */
    up(grep_sticks);

  } while (nicht beide Stäbchen in der Hand);

  /* Der Philosoph kann jetzt in Ruhe essen. */
  Satt essen;
  /* Stäbchen wieder frei geben. */
  Lege linkes Stäbchen hin;
  Lege rechts Stäbchen hin;
}

Ein Problem bleibt aber, dass ein Philosoph, der neben zwei sehr hunrigen Kollegen sitzt, trotzdem verhungern kann, weil ständig mindestens eins der Stäbchen fehlt. Genauer können zwei nimmersatte Philosophen die drei anderen verhungern lassen.

Die Lösung dafür ist nicht ganz einfach. Wenn man z. B. eine Warteschlange pro Stäbchen einführt, in die sich jeder Eintragen kann, falls ein Stäbchen nicht da ist, dann kann das wieder zu einem Deadlock führen weil jeder Philosoph ein Stäbchen als nächster bekommt, aber keiner bekommt beide.

Besser wäre es, die Exklusivität der Stäbchen aufzuheben, und nach einer Zeitspanne eine Unterbrechung zu erzwingen. Wenn einen Philosoph ein Stäbchen hat und sein mindestens einer Stunde nichts gegessen hat, dann muss ihm sein Nachbar das Stäbchen geben.

Aufgabe 2 Peterson für alle n

Basteln. Petersons Algorithmus für zwei Prozesse ist aus der Vorlesung bekannt. Betriebssystemern stellt sich nun sofort, nicht nur von professoraler Seite, die Frage wie man diesen Algorithmus so erweitern kann, daß er auch den wechselseitigen Ausschluß für 3 oder sogar n Teilnehmer ermöglicht.

Um anschließend aber auch zu wissen ob die produzierte Lösung denn nun auch korrekt ist und ob nicht doch aus Versehen ein Zustand erzeugt werden kann in dem eine der Anforderungen an einen wechselseitigen Ausschluß nicht erfüllt ist, baut man sich am besten gleich einen kompletten Zustandsübergangsgraphen.

Aufgabe 3 Schlafende Frisöre

Analyse. In einem Frisiersalon gibt es einen Friseur und N Stühle auf denen Kunden sitzen können. Ein Friseur kann natürlich nur einen Kunden zur Zeit bearbeiten. Der Friseur wartet bis er einen Kunden hat, schneidet diesem die Haare und legt sich dann wieder schlafen bis er einen neuen Kunden hat. Ein Kunde betritt den Laden, wenn der Friseur frei ist, läßt er sich die Haare schneiden, wenn nicht, dann setzt er sich auf einen der Warteplätze. Ist kein Stuhl mehr frei, dann verläßt er den Friseur um sich an einem anderen Tag die Haare schneiden zu lassen.

Ein Programmierer, sicher kein Teilnehmer dieses Kurses, hat sich sich die folgende Lösung ausgedacht - die leider falsch ist. Was ist das Problem und wie könnte man es besser machen?

 semaphore haare_schneiden(1)
semaphore wartesaal(N)
int freie_plaetze = N;

void customer()
  if (freie_plaetze > 0)
    /* hinsetzen */
    down(wartesaal);
    freie_plaetze = freie_plaetze - 1;
    /* frisoer winken */
    up(haare_schneiden);
    /* bekommt haare geschnitten */
    up(wartesaal);
    freie_plaetze = freie_plaetze +1;

  /* wieder rausgehen */
  verlasse_frisoer();

void barber()
  forever()
    /* warten bis kunde kommt */
    down(haareschneiden);
    /* kunde bekommt haare geschnitten */

Weitere Fragen

1. Was ist Nebenläufigkeit? Und wie hängt das mit Betriebsmitteln zusammen?
2. Was ist eine Race-Condition?
3. Was sind donnernde Herden und Convoys in diesem Zusammenhang und warum sind beide ein Problem?
4. Beschreibe das Beispiel der Speisenden Philosophen und des Sleeping Barbers.
5. Was ist das Reader-Writer-Problem? Und wie sehen Lösungen aus?
6. Welche Anforderungen kann man an ein Verfahren zum wechselseitigen Ausschluß stellen? (durchaus auch mehr als vier)
7. Was bedeutet TSL? Und welche Probleme werden damit gelöst?
8. Kann man diese Probleme auch mit Softwaremitteln lösen? Wie?
9. Was ist ein Semaphor?
10. Was sind Monitore? Was für Probleme gibt es mit ihnen?
11. Gibt es noch andere Synchronisationskonzepte?

Nach oben