Threads notify/notifyAll Philosophen-Problem

minzee

Bekanntes Mitglied
Hi :)

Eine Frage zu einem Programm, das ich aus einem Buch habe (Parallele und verteilte Anwendungen in Java, Hanser-Verlag, ISBN 978-3-446-43888-0). Listing 3.9:

Java:
class Table
{
    private boolean[] forkUsed;

    private int left(int i)
    {
        return i;
    }

    private int right(int i)
    {
        if(i + 1 < forkUsed.length)
            return i + 1;
        else
            return 0;
    }

    public Table(int number)
    {
        forkUsed = new boolean[number];
        for(int i = 0; i < forkUsed.length; i++)
            forkUsed[i] = false;
    }

    public synchronized void takeFork(int number)
    {
        while(forkUsed[left(number)] || forkUsed[right(number)])
        {
            try
            {
                wait();
            }
            catch(InterruptedException e)
            {
            }
        }
        forkUsed[left(number)] = true;
        forkUsed[right(number)] = true;
    }

    public synchronized void putFork(int number)
    {
        forkUsed[left(number)] = false;
        forkUsed[right(number)] = false;
        notifyAll();
    }
}

class Philosopher extends Thread
{
    private Table table;
    private int number;

    public Philosopher(Table table, int number)
    {
        this.table = table;
        this.number = number;
        start();
    }

    public void run()
    {
        while(true)
        {
            think(number);
            table.takeFork(number);
            eat(number);
            table.putFork(number);
        }
    }

    private void think(int number)
    {
        System.out.println("Philosoph " + number + " denkt.");
        try
        {
            sleep((int) (Math.random() * 20000));
        }
        catch(InterruptedException e)
        {
        }
    }

    private void eat(int number)
    {
        System.out.println("Philosoph " + number + " fängt zu essen an.");
        try
        {
            sleep((int) (Math.random() * 20000));
        }
        catch(InterruptedException e)
        {
        }
        System.out.println("Philosoph " + number + " hört auf zu essen.");
    }
}

public class Philosophers
{
    private static final int NUMBER = 5;

    public static void main(String[] args)
    {
        Table table = new Table(NUMBER);
        for(int i = 0; i < NUMBER; i++)
            new Philosopher(table, i);
    }
}
In der Methode putFork gibt es ein notifyAll (Zeile 45). Hierzu ein Zitat aus dem Buch:
Damit kann eventuell der linke oder rechte oder beide Nachbarn essen. Aus diesem Grund ist notifyAll statt notify nötig. Ein weiterer Grund für notifyAll ist, dass die Wartebedingung auch wieder parametrisiert ist, so dass es mehrere Wartebedingungen gibt.
Das hört sich für mich so an, als ob ein notify nicht reichen würde, weil dann die Nachbarn nie essen könnten.

Ich denke mir jedoch, dass ein notify reicht. Darum habe ich aus dem notifyAll ein notify gemacht und NUMBER (Zeile 100) auf 3 reduziert. Selbst in diesem Fall scheint das Programm zu funktionieren.

Was sagt ihr dazu? Ist das notifyAll wirklich nötig, oder verstehe ich den Buchautor nur falsch?

P. S. falls jemand dieses Philosopen-Problem noch nicht kennt: 5 Philosophen sitzen zum Essen und Philosophieren an einem gemeinsamen Tisch. Jeder Philosoph hat einen Teller. Zwischen den Tellern liegen die Gabeln - zu 5 Tellern gibt es 5 Gabeln. Zum Essen benötigt ein Philosoph die Gabeln rechts UND links von seinem Teller. Isst der linke oder rechte Sitznachbar, kann der Philosoph nicht essen, weil ihm dazu nicht beide Gabeln zur Verfügung stehen.
 
Zuletzt bearbeitet:

Flown

Administrator
Mitarbeiter
Du hast 5 Philosophen und jeder ist mit einem Thread realisiert. Am Anfang denken alle und irgendwann beginnt einer Gabeln zu nehmen und zu essen.

Wenn jetzt sagen wir 2 essen können 3 das nicht also werden die Threads schlafen gelegt. Wenn du jetzt mit notify arbeitest, dann wird genau einer der 3 schlafenden Threads(Philosophen) aufgeweckt. Das heißt, die anderen haben gar nicht die Chance die Gabeln für sich zu beanspruchen.

Doch wenn du ein notifyAll machst, erwachen alle 3 Philosophen und versuchen sich die Gabeln zu schnappen. So erhälst du race-conditions, anders nicht.
 

minzee

Bekanntes Mitglied
Hm, also grundsätzlich stimmst du mir zu, dass das Programm auch mit notify funktioniert? Und das notifyAll ist nur, damit schneller mehr Philosophen zu essen beginnen können?
 
Zuletzt bearbeitet:

nvidia

Bekanntes Mitglied
Hm, also grundsätzlich stimmst du mir zu, dass das Programm auch mit notify funktioniert? Und das notifyAll ist nur, damit schneller mehr Philosophen zu essen beginnen können?

Du hast den Satz des Autors nicht verstanden. Persönlich würde ich die Finger von notify/notifyAll lassen und schauen ob es nicht eine brauchbare Abstraktion im Concurrent-Package gibt die für meinen Anwendungsfall passt. notify() lässt sich nur unter bestimmten Bedingungen verwenden und um einschätzen zu können wann, sollte man wissen wie man Invarianten formuliert, wissen was es mit den "impliziten" Condition Queues und Condition Predicates und der Condition API auf sich hat, das Problem von "spurious wakeups" und "missed signals" kennen. Das Aufgezählte wird übrigens in "Java Concurrency in Practice" behandelt und ich bin zu faul das alles wiederzugeben. :)
 

Flown

Administrator
Mitarbeiter
Ich stimme dir zwar zu das notify und notifyAll funktioniert aber nicht in der gleichen weise.

Das heißt, notify weckt "1" Thread.
notifyAll weckt "ALLE".

Wie ich im letzten Post schon geschildert habe, bilden sich somit race condition und können auch zum deadlock führen.
 

minzee

Bekanntes Mitglied
Du hast den Satz des Autors nicht verstanden. Persönlich würde ich die Finger von notify/notifyAll lassen und schauen ob es nicht eine brauchbare Abstraktion im Concurrent-Package gibt die für meinen Anwendungsfall passt
Ich will das mal universell lernen. Wenn ich es mit wait und notify in Java verstehe, dann verstehe ich es auch in anderen Programmiersprachen :)
Du hast den Satz des Autors nicht verstanden.
Würdest du die Aussage des Autors bitte mal irgendwie anders formulieren? Vielleicht kapier ich es dann.
 
Zuletzt bearbeitet:

nvidia

Bekanntes Mitglied
Ein weiterer Grund für notifyAll ist, dass die Wartebedingung auch wieder parametrisiert ist, so dass es mehrere Wartebedingungen gibt

Alle Threads warten im selben Condition Queue (dem des Tischs) auf unterschiedliche Bedingungen, weshalb man bei einer solchen Konstellation notifyAll verwenden sollte wird in den einschlägigen Büchern [1] oder im Internet erläutert.

[1] Java Concurrency in Practice, Kapitel 14
 

minzee

Bekanntes Mitglied
Gelten für jeden Philosophen nicht die gleichen Bedingungen? Um essen zu können, müssen die Gabeln links und rechts vom Philosophen frei sein.
 

arilou

Bekanntes Mitglied
Wenn die rechte Gabel von Philosoph 3 frei wird, gelten für Philosoph 2 und Philosoph 4 verschiedene Bedingungen. notify weckt nun nur einen auf - das kann zufällig gerade derjenige sein, der aus der freiwerdenden Gabel profitiert, es kann aber auch der andere sein, der dann nur feststellt, dass bei ihm immernoch nichts möglich ist.
 

minzee

Bekanntes Mitglied
Irgendwie verwirrt man dein Beispiel, aber ich glaube, wir meinen das selbe. Es geht einfach nur darum, dass man mit notifyAll die Threads besser auslastet.

Hier mal ein Beispiel:

8 Philosophen (jeder Philosoph läuft in einem eigenen Thread):

Code:
      >0<             
  <1>     !7!         
                   
!2!         !6!         
                    
  <3>     <5>                  
      >4!
Legende:
>x< essen
<x> warten
!x! philosophieren
>x! Wechsel von essen auf philosophieren

Hier warten die Philosophen 1, 3 und 5 darauf, essen zu können.

Arbeitet man mit notify, könnte Java versuchen, Thread 1 (Philosoph 1) zum Laufen zu bringen. Da 0 noch isst, war dieser Versuch vergebens. Die Philosophen 1, 2 und 5 müssen weiterhin warten.

Arbeitet man mit notifyAll, versucht Java alle wartenden Threads 1, 3 und 5 zum Laufen zu bringen. Bei 3 und 5 gelingt das Java. Die Philosophen 3 und 5 können zu essen beginnen. Richtig so?

Das ist der Grund, warum im Programm mit notifyAll gearbeitet wird, richtig? Mit notify würde es ebenfalls funktionieren, jedoch würden dann öfters mal Threads nicht optimal genutzt werden.
 
Zuletzt bearbeitet:

Flown

Administrator
Mitarbeiter
Grundsätzlich richtig was du das schreibst, bis auf den letzten Absatz.

Das ist der Grund, warum im Programm mit notifyAll gearbeitet wird, richtig? Mit notify würde es ebenfalls funktionieren, jedoch würden dann öfters mal Threads nicht optimal genutzt werden.

Mit notify würden nicht für alle die gleichen Bedingungen herrschen!.
Aus deinem Beispiel würde hervorgehen, dass mit notify z.B. (kommt auf Java an) 3 aufgeweckt wird und zu essen beginnt.
Eigentlich sollten alle aufgeweckt werden, damit sie die Möglichkeit haben zu essen (auch Nummer 5 ist dazu in der Lage).
 

arilou

Bekanntes Mitglied
Mit notify() geht man das Risiko ein, dass der Ablauf steckenbleibt.

Beispiel: Der Philosoph A hat fertig gegessen, und ist bereit, seine Gabeln abzugeben (er ruft notify() auf).
Java weckt nun genau 1 wartenden Thread und erwischt einen, der von A's Gabeln nicht profitiert.
Da die wartenden Nachbarn von Philosoph A nicht erweckt werden, war's das mit dem Ablauf. Sie bekommen nicht mit, dass eine Gabel verfügbar ist, und warten bis Sankt Nimmerlein.

Mit notifyAll() werden bei jeder freiwerdenden Gabel alle wartenden Philosophen geweckt, so dass diejenigen, die profitieren können, auch sicher bei den erweckten dabei sind.

Ob notify() bei genau 5 Philosophen dennoch funktioniert, mag es sein. Auch kann es abhängig von der JVM sein (davon, wie sie ihre Thread-Warteschlangen genau handhabt, ob z.B. erweckte Threads sich dann wieder "hinten anstellen" müssen).
 

arilou

Bekanntes Mitglied
Aber du verstehst nun den Unterschied zwischen notify() und notifyAll() ?

Ich habe mir keine expliziten Gedanken genau zum Philosophenproblem bzw. zu "Philosophenproblem mit genau X Philosophen" gemacht - möglich dass notify() hier kein Problem bedeutet.
Aber im Zweifelsfall müsstest du das explizit (mathematisch) beweisen. Dazu hat kaum jemand Lust - und alle verwenden einfach notifyAll(), da braucht man sich keine Gedanken darum zu machen, ob der Ablauf in einen Deadlock laufen kann, wenn "der falsche Thread" aufgeweckt wird.
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
I Threads Multithreading, Producer/Consumer, notify() Java Basics - Anfänger-Themen 6
O Threads - Synchronize(), join(), wait(), notify(), yield() Java Basics - Anfänger-Themen 6
ralfb1105 Frage zu Thread Synchronisation mit wait() und notify() Java Basics - Anfänger-Themen 3
kilopack15 Verständnisfrage zur Verwendung von notify() bei Threads Java Basics - Anfänger-Themen 2
M notify und wait Java Basics - Anfänger-Themen 1
M Threads notify Java Basics - Anfänger-Themen 6
D Stack-Objekt - LIFO - wait(); notify(); Java Basics - Anfänger-Themen 0
D Probleme mit wait(), notify() Java Basics - Anfänger-Themen 0
M wait/notify bei Socket Java Basics - Anfänger-Themen 4
T Alle Threads .notify() Java Basics - Anfänger-Themen 13
Luk10 Monitor: wait() und notify() Java Basics - Anfänger-Themen 8
S Threads: wait() und notify() Java Basics - Anfänger-Themen 11
M lock notify synchronisation Java Basics - Anfänger-Themen 8
S Problem mit notify() Java Basics - Anfänger-Themen 4
S bin zu blöd für threads - wait, notify, synchronized Java Basics - Anfänger-Themen 11
B Problem: wait() -> notify() Java Basics - Anfänger-Themen 4
M Threads, wait() und notify() Java Basics - Anfänger-Themen 10
G Threads steuern mit wait und notify Java Basics - Anfänger-Themen 2
P wait und notify oder wie soll ich es lösen Java Basics - Anfänger-Themen 2
M Warum kann man dem Thread kein notify senden? Java Basics - Anfänger-Themen 15
I Exception bei Button mit wait() und notifyAll() Java Basics - Anfänger-Themen 3
C Anwendung von notifyAll() Java Basics - Anfänger-Themen 5
O 5 Philosophen-Problem Java Basics - Anfänger-Themen 10
S Speisende Philosophen Java Basics - Anfänger-Themen 13

Ähnliche Java Themen

Neue Themen


Oben