Musterlösungen

Laboraufgabe “Dinierende Philosoph:innen”

Das Problem der Verklemmung resultiert in der ursprünglichen Lösung aus der Verletzung der “global ordering rule”: Die Philosophen sind an einem runden Tisch angeordnet, der über Arrays repräsentiert wird.

• chopsticks ist ein Array, in dem Chopstick-Objekte gespeichert werden.
• philosophers ist ein Array, in dem die Philosopher-Objekte (erben von Thread) gespeichert werden.

Jeder Philosoph mit Index \(i\) im Array philosophers greift folgendermaßen auf die Essstäbchen zu:

• links: chopsticks[i]
• rechts: chopsticks[i+1]

Da es aber nur so viele Essstäbchen wie Philosophen gibt, würde beim letzten Philosophen der Zugriff auf das rechte Essstäbchen fehlschlagen:

chopsticks[philosophers.length]

bzw.

chopsticks[PHILOSOPHER_NUM]

Um die Kreiseigenschaft mit diesen Arrays abzubilden, wird für den Zugriff auf das rechte Essstäbchen modulo der Anzahl der Philosophen gerechnet:

• links: chopsticks[i]
• rechts: chopsticks[(i + 1) % PHILOSOPHER_NUM]

Dadurch dreht sich beim Zugriff des “letzten Philosophen”, also dem mit Index PHILOSOPHER_NUM] die Reihenfolge des Zugriffs um: Zuerst wird auf das Essstäbchen mit Index PHILOSOPHER_NUM-1 zugegriffen, danach auf das Stäbchen mit Index 0. Die richtige Reihenfolge müsste aber wie bei den anderen Zugriffen der numerischen Reichenfolge folgen. Um dieses Problem zu beheben und sicher Verklemmungen zu vermeiden, muss daher beim letzten Philosophen also zuerst auf das rechte Essstäbchen und dann auf das linke zugegriffen werden.

Um dies zu erreichen, könnte die Methode eat() von Philosopher umgebaut werden. Da diese Methode aber von allen Philosophen verwendet wird (also auch von denen, bei denen die “reguläre” Reienfolge verwendet werden muss), würde diese Lösung recht unübersichtlich ausfallen.

Einfacher ist es, diese Methode unangetastet zu lassen und beim letzten Philosophen im Array nur umzudrehen, welches Stäbchen links und welches rechts liegt. Dazu muss die main-Methode von PhilosopherExperiment modifiziert werden:

public static void main(String... args) throws InterruptedException {
  var chopsticks = new Chopstick[PHILOSOPHER_NUM];
  var philosophers = new Philosopher[PHILOSOPHER_NUM];
  for (int i = 0; i < PHILOSOPHER_NUM; i++) {
    chopsticks[i] = new Chopstick();
  }
  // first n-1 philosophers
  for (var i = 0; i < (PHILOSOPHER_NUM - 1); i++) {
    philosophers[i] = new Philosopher(i, chopsticks[i],
        chopsticks[(i + 1)]);
  }
  // nth philosophers: initialize with right+left instead of left+right
  philosophers[PHILOSOPHER_NUM - 1] = new Philosopher(PHILOSOPHER_NUM - 1,
      chopsticks[0], chopsticks[PHILOSOPHER_NUM - 1]);
  for (var i = 0; i < PHILOSOPHER_NUM; i++) {
    philosophers[i].start();
  }
  Thread.sleep(EXP_DURATION_MS);
  for (var i = 0; i < PHILOSOPHER_NUM; i++) {
    philosophers[i].stopPhilosopher();
  }
}

Laboraufgabe “wait/notifyAll für Ringpuffer”

Analyse des Quellcode

Analysieren Sie den Quellcode.

• Es handelt sich um einen Ringspeicher. Das Warten solange der Speicher leer ist (take) bzw. solange der Speicher voll ist (put) ist aber noch nicht umgesetzt.

Laufverhalten

Lassen Sie das Hauptprogramm mehrfach laufen und beobachten Sie das Verhalten. Entspricht dies der Spezifikation?

• Dementsprechend kann es in Probeläufen dazu kommen, dass Elemente des Rinpuffers überschrieben werden, denn es wird aufgrund des Testtreibers (main-Methode) seltener entnommen als hinzugefügt. Das zeigt sich dann daran, dass eigentlich vorhandene Elemente von take nicht mehr entnommen werden können, da sie überschrieben wurden. Das zeigt die folgende Beispielausgabe:

Producer-1: put=1
Producer-2: put=1
Producer-2: put=2
Producer-2: put=3
Producer-2: put=4
Producer-2: put=5
Producer-2: put=6
Producer-2: put=7

Ab hier eigentlich voll, aber es geht weiter:

Producer-2: put=8

Dadurch wurde das erste Element “1” mit “8” überschrieben. Es wird auch entsprechend hier gelesen:

Consumer-1: taken=8

Modifikation von put und take, so dass gewartet wird, falls der Puffer voll ist

Modifizieren Sie die Methode put so, dass gewartet wird, falls der Puffer voll ist (this.count == this.items.lentgh). Dazu muss take alle wartenden Threads aufwecken, wenn ein Element entfernt wurde, weil im Puffer danach wieder etwas Platz ist.

• solange der Speicher voll ist, warten:

  Da this.count bei jedem Hinzufügen um 1 erhöht und bei jedem Lesen um 1 verringert wird, kann man an einem Vergleich der Instanzvariablen this.count mit der Größe des Container-Arrays this.items (hier 8) feststellen, ob noch Platz im Speicher ist. In dem Fall muss der Aufrufer durch wait() blockiert werden.

while (this.count == this.items.length) {
    wait();
}

Durch den Aufruf von wait() an this, also an der jeweiligen Instanz von BoundedBuffer wird der Warteraum von this verwendet. In diesem Warteraum werden die durch den Aufruf von put an einem bereits vollen Ringpuffer blockierten Threads warten.

Gibt es mehrere Instanzen von BoundedBuffer beeinflussen sie sich bzw. die Threads, die sie nutzen, nicht gegenseitig.

• nun ist etwas Platz im Speicher: Alle wartenden Threads benachrichtigen:

  Threads, die möglicherweise durch Aufruf von wait() an this blockiert sind, müssen nun aufgeweckt werden. Dies erfolgt durch den Aufruf von notifyAll() an this. In diesem Beispiel würde es auch funktionieren, einen beliebigen wartenden Thread mit notify() zu wecken, da es nicht passieren kann, dass an this Threads sowohl auf die eine Bedingung (nicht mehr voll), als auch auf die anderen Bedingung (nicht mehr leer) warten. Es würde also mit notify() immer ein auf die richtige Bedingung wartender Thread geweckt werden.

• synchronized:

  Der Aufruf von wait() und notify()/notifyAll() darf nur auf einem Bereich gegenseitigen Ausschluss geschehen. Deshalb werden die beiden Methoden put und take mit synchronized geschützt.

Modifikation von take und put, so dass gewartet wird, falls der Puffer leer ist

Modifizieren Sie die Methode take so, dass gewartet wird, falls der Puffer leer ist (items.count==0). Dazu muss put alle wartenden Threads aufwecken, wenn ein Element hinzugefügt wurde, weil im Puffer danach wieder etwas zu holen ist.

• solange der Speicher leer ist, warten:

  Da count beginnend mit 0 bei jedem Hinzufügen um 1 erhöht und bei jedem Lesen um 1 verringert wird, kann man an der Instanzvariablen count feststellen, ob der Speicher leer ist. In dem Fall muss der Aufrufer durch wait() blockiert werden.

while (this.count == 0) {
    wait();
}

• nun ist etwas neues im Speicher: Alle wartenden Threads benachrichtigen:

Threads, die möglicherweise durch Aufruf von wait() an this blockiert sind, müssen nun aufgeweckt werden. Dies erfolgt durch den Aufruf von notifyAll() an this. In diesem Beispiel würde es auch funktionieren, einen beliebigen wartenden Thread mit notify()zu wecken, da es nicht passieren kann, dass an this Threads sowohl auf die eine Bedingung (nicht mehr voll), als auch auf die anderen Bedingung (nicht mehr leer) warten. Es würde also mit notify() immer ein auf die richtige Bedingung wartender Thread geweckt werden.

Laboraufgabe “await/signal für Ringpuffer”

Modifizieren Sie die Methoden put und take so, dass zwei getrennte Bedingungsvariablen verwendet werden.

• Statt synchronized wird hier ReentrantLock für den gegenseitigen Ausschluss verwendet, da mit newCondition Bedingungsvariablen zum Lock erzeugt werden können. Es eergeben sich also die folgenden zusätzlichen Instanzvariablen mit Initialisierung:

final Lock lock = new ReentrantLock();
final Condition notFull = this.lock.newCondition();
final Condition notEmpty = this.lock.newCondition();

• Die beiden Bedingungsvariablen sollen die beiden Situationen repräsentieren, in denen gewartet werden muss: “Speicher schon voll”, “Speicher noch leer”.
• Dementsprechend müssen die kritischen Regionen (hier die kompletten Rümpfe der Methoden put und take) mit gegenseitigem Ausschluss geschützt werden:

this.lock.lock();
try {
    // hier der restliche Methodenrumpf
} finally {
    this.lock.unlock();
}

• Auf das Eintreten der jeweiligen Bedingung warten:
  An den beiden Bedingungen ändert sich nichts. Lediglich das Warten (Blockieren des Aufrufer-Threads) erfolgt nun durch Aufruf von await() an jeweils einer der beiden Bedingungsvariablen.

while (this.count == this.items.length) {
    this.notFull.await();
}

bzw.

while (this.count == 0) {
    this.notEmpty.await();
}

• Das Lösen der Blockierung geschieht hier durch Aufruf von signal() (signalAll() ist im Allgemeinen nicht erforderlich, da durch Bedingungsvariablen immer “bedingungsgenau” gewartet werden kann). Der Aufruf muss “überkreuz” erfolgen. D.h. in der Methode, in der an notFull await() aufgerufen wurde, muss signal() an notEmpty aufgerufen werden und umgekehrt.