pp.03.01-SynchPhilosopher

Dinnierende Philosoph:innen

• Projekt: pp.03.01-SynchPhilosopher
• Bearbeitungszeit: 15 Minuten
• Musterlösung: 15 Minuten
• Kompatibilität: mindestens Java SE 19

Die dining philosophers sind ein Standardbeispiel für ein nebenläufiges System, in dem es zu Verklemmungen kommen kann. In diesem Modell, das zur Verdeutlichung von Problemen bei der Steuerung paralleler Prozesse verwendet wird, gibt es eine feste Anzahl Personen (z.B. 5), die im Kreis um einen Tisch angeordnet sind. Zwei benachbarte Menschen teilen das zwischen ihnen liegende Essstäbchen.

Butcher (2014, 16)

Der Lebenszyklus eines/r Philosoph:in ist:

1. denken
2. linkes Essstäbchen greifen
3. rechtes Essstäbchen greifen
4. essen
5. rechtes Essstäbchen zurücklegen
6. linkes Essstäbchen zurücklegen
7. weiter bei 1.

Die Essstäbchen stellen eine geteilte Ressource dar. Ein Stäbchen darf nur jeweils von einem Philosophen benutzt werden.

• Greifen von Esstäbchen ist kritischer Abschnitt

Wollen andere Philosophen ein benutztes Stäbchen verwenden, müssen sie aufgehalten werden, bis das Essstäbchen wieder frei ist. Eine Möglichkeit, dies zu erreichen ist die Modellierung dieses gegenseitigen Ausschlusses durch synchronized-Blöcke.

Quellcode von pp.Chopstick

In diesem Beispiel werden die Essstäbchen als Objekte modelliert. Die Klasse Chopstick ist leer. Im Moment hat ein Essstäbchen noch keine über Object hinausgehenden Eigenschaften oder Methoden. Man kann aber Instanzen von Chopstick als Monitor (“Schlossvariable”) benutzen.

package pp;

public class Chopstick {

}

Quellcode von pp.Philosopher

package pp;

import java.util.Random;

public class Philosopher extends Thread {
  static final int MAX_THINKING_DURATION_MS = 1000;
  static final int MAX_EATING_DURATION_MS = 3000;
  static final int MAX_TAKING_TIME_MS = 1000;

  private final Chopstick left;
  private final Chopstick right;
  private final Random random;
  private int eaten;
  private final int seat;

  private volatile boolean stop;

  private void log(String message) {
    synchronized (Philosopher.class) {
      for (var i = 1; i <= this.seat; i++) {
        System.out.print("                         ");
      }
      System.out.println(threadId() + " " + message);
    }
  }

  public void stopPhilosopher() {
    log("stopping");
    this.stop = true;
    interrupt();
  }

  public Philosopher(int seat, Chopstick left, Chopstick right) {
    this.stop = false;
    this.seat = seat;
    this.left = left;
    this.right = right;
    this.random = new Random();
    this.eaten = 0;
  }

  @Override
  public void run() {
    log("starting");
    try {
      while (!this.stop) {
        think();
        eat();
      }
    } catch (InterruptedException e) {
      Thread.currentThread().interrupt();
    }
    log("stopped; eaten=" + this.eaten);
  }

  private void think() throws InterruptedException {
    Thread.sleep(this.random.nextInt(MAX_THINKING_DURATION_MS));
  }

  private void eat() throws InterruptedException {
    log("try taking left");
    synchronized (this.left) {
      log("left acquired");
      Thread.sleep(this.random.nextInt(MAX_TAKING_TIME_MS));
      log("try taking right");
      synchronized (this.right) {
        log("right acquired");
        log("eating");
        this.eaten++;
        Thread.sleep(this.random.nextInt(MAX_EATING_DURATION_MS));
      }
      log("right released");
    }
    log("left released");
  }
}

Quellcode von pp.PhilosopherExperiment

package pp;

public class PhilosopherExperiment {

  static final int PHILOSOPHER_NUM = 5;
  static final int EXP_DURATION_MS = 20000;

  public static void main(String... args) throws InterruptedException {
    var chopsticks = new Chopstick[PHILOSOPHER_NUM];
    var philosophers = new Philosopher[PHILOSOPHER_NUM];
    for (var i = 0; i < PHILOSOPHER_NUM; i++) {
      chopsticks[i] = new Chopstick();
    }
    for (var i = 0; i < PHILOSOPHER_NUM; i++) {
      philosophers[i] = new Philosopher(i, chopsticks[i],
          chopsticks[(i + 1) % PHILOSOPHER_NUM]);
    }
    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();
    }
  }
}

Aufgaben

• Analysieren Sie den Quellcode. Machen Sie sich klar, welche Objekte in PhilosopherExperiment erzeugt werden und wie sie zusammenhängen. Wie können Sie erkennen, ob es zu einer Verklemmung gekommen ist?
• Machen Sie eine Reihe von Experimenten, indem Sie PhilosopherExperiment laufen lassen. Falls es zu einer Verklemmung kommt: Dokumentieren Sie den Ablauf, der zur Verklemmung geführt hat. Falls es zu keinem Deadlock gekommen ist, analysieren Sie, ob es “gerecht” zwischen den Philosophen zuging und dokumentieren Sie das Ergebnis.
• Modifizieren Sie die Parameter
  • PHILOSOPHER_NUM,
  • MAX_TAKING_TIME_MS,
  • EXP_DURATION_MS und
  • MAX_THINKING_DURATION_MS
  und wiederholen Sie die Experimente. Wie können Sie die Wahrscheinlichkeit eines Deadlocks vergrößern?
• Was kann man ändern, um Verklemmungen gänzlich zu vermeiden?

Literatur

Butcher, Paul. 2014. Seven Concurrency Models in Seven Weeks. When Threads Unravel. Dallas: The Pragmatic Programmers.