Java Dining Philosophers und Semaphore

[XHotSniperX]

Hallo

ich versuche gerade die Nebenläufigkeit in parallelen Programmen zu verstehen. Mitunter ist das Problem der Speisenden Philosophen. Ich habe ein Programm geschrieben in Java, welches dieses Problem simulieren soll.

Es sind die Klassen DiningPhil(main), Fork und Philosopher. In der Klasse Fork(Gabel) ist Semaphore drin.

Das wichtige werde ich hier posten:

DiningPhil

...  
for (int i=0; i<NUM_PHILS; i++){
    forks[i]= new Fork();
  }
  for (int i=0; i<NUM_PHILS; i++){ // jeder Philosoph hat Zugriff auf 2 Gabeln
    phils[i]= new Philosopher(i, forks[i], forks[(i+1)%NUM_PHILS]);
  }
  for (int i=0; i<NUM_PHILS; i++){ // Philosophen beginnen zu wirken
    phils[i].start();
  } 
}
...

Fork

class Fork{
  private final Semaphore sem = new Semaphore(1);
  
  public void take(){
    try{
      sem.acquire();
    }
    catch(InterruptedException e){
      e.printStackTrace();
    }  
  }

  public void putBack(){
    sem.release(); 
  } 
}

Philosopher

class Philosopher extends Thread{

... 

   private void thinking(){
     state = 0;  
     waitRandomTime();
   }
   
   private void hungry(){
     state = 1;
     left.take();
     right.take();
   }
   
   private void eating(){
     state = 2;
     waitRandomTime();
     left.putBack();
     right.putBack();  
   }

   public void run(){
     while(!gone){
       thinking();
       hungry();
       eating();
     }
   }
...
}

Das Problem ist jetzt, dass beim ausführen direkt alle Philosophen HUNGRIG sind und bleiben für immer. Jedes Mal. Wieso habe ich immer einen Deadlock? Die Müssten doch zu erst ne random Zeit DENKEN und dann erst HUNGRIG werden und ESSEN wollen.
Die Random Zeit liegt zwischen 1 und 10 Sekunden.

Habt ihr ne Idee woran das liegt?

 

[Darlis]

Vielleicht solltest du dein Programm ein paar Ausgaben machen lassen à la "Phil. X will linke Gabel" und "Phil. X hat linke Gabel", etc.

Aus deinem Codeschnipseln geht nicht hervor, ob gone jemals true werden kann, von daher werden sie wohl für immer denken und essen wollen.

 

[XHotSniperX]

achso nene gone ist für was anderes gedacht (falls ein philosoph weggeht). das kann man hier jetzt mal ausser acht nehmen und denken, dass gone immer false ist. die funktion möchte ich später erst integrieren.

Ah und da ist eine Ausgabe. Ich lade es mal als ein Applet hoch. Dann könnt ihr es im Browser laufen lassen. (mit Processing gemacht)

 

[destiny]

hmm, bei mir läufts scheinbar korret...

Obwohl, nicht alle "denken" zu Beginn, allerdings bekomme ich auch keine Deadlocks

 

[Darlis]

Bei mir läuft's auch ohne Probleme. Welche Java Version hast du denn? Bei mir läuft's mit 6u29 x64 (ja ich weis, veraltet)

 

[XHotSniperX]

waas? bei mir läufts nicht ( ich habe java 7 update 3. wieso das jetzt?

 

[Killkrog]

WinXP(x86) 6u30(x86) @ dualcore 1.6GHz => Funktioniert
Win7(x64) 6u30(x86) @ quadcore 4GHz => Deadlock

Werde mir das mal etwas genauer ansehen...

 

[XHotSniperX]

Auf meinem Mac (Lion, i7) läufts auch nicht.

 

[ice-breaker]

Wieso habe ich immer einen Deadlock? Die Müssten doch zu erst ne random Zeit DENKEN und dann erst HUNGRIG werden und ESSEN wollen.

In dem Moment wo es die erste Überschneidung deiner Zugriffe auf die Gabeln gibt, also 2 Philosophen durch die zufällige Wartezeit auf die selbe Gabel zugreifen wollen, werden diese sich deadlocken. Dies ist unumgänglich, aus diesem Grund wird es in deiner Implementierung immer einen Deadlock geben.

Wenn es dann erstmal den Deadlock um eine Gabel wird daraus automatisch ein Deadlock für den ganzen Tisch, da nun jeweils die Tischnachbarn der beiden Philosophen sich nach einer gewissen Zeit deadlocken werden, und dessen und dessen...
Bis der ganze Tisch deadlockt.

Wie du siehst: Eine zufällige Wartezeit ist keine Lösung für das dining philosophs Problem

 

[Darlis]

In dem Moment wo es die erste Überschneidung deiner Zugriffe auf die Gabeln gibt, also 2 Philosophen durch die zufällige Wartezeit auf die selbe Gabel zugreifen wollen, werden diese sich deadlocken.

So wie du das geschrieben hast, ist es nicht richtig. Wenn zwei Philosophen auf dieselbe Gabel zugreifen wollen, bekommt einer von den beiden diese auf jeden Fall.

Den Deadlock gibt es erst, wenn z.B. jeder Philosoph dir rechte Gabel hat und dann (vergeblich) wartet, bis sein linker Nachbar seine wieder auf den Tisch legt.

Das Problem des TE ist aber, dass es direkt zu Programmbeginn den Deadlock gibt und nicht erst später.

 

[ice-breaker]

So wie du das geschrieben hast, ist es nicht richtig. Wenn zwei Philosophen auf dieselbe Gabel zugreifen wollen, bekommt einer von den beiden diese auf jeden Fall.

Den Deadlock gibt es erst, wenn z.B. jeder Philosoph dir rechte Gabel hat und dann (vergeblich) wartet, bis sein linker Nachbar seine wieder auf den Tisch legt.

korrekt, hätte ich vielleicht besser ausführen sollen.

Das Problem des TE ist aber, dass es direkt zu Programmbeginn den Deadlock gibt und nicht erst später.

Das ist auch korrekt, wenn aber alle zu Beginn die gleiche Wartezeit berechnen...
Ich habe mich nun nochmal in deinen Code reingelesen und mir angeschaut wie Processing die Random-Zahlen erzeugt: Es wird einfach ein Random-Objekt erzeugt und genutzt. Es wird jedoch zu keinem Zeitpunkt ein eigener Seed hinzugefügt. Java nutzt als Seed standardmäßig System.nanoTime(); Nun ist es aber so, dass unter Windows Zeiten eigentlich nur über 10ms genau sind, denn nur so genau funktioniert die Windows Uhr. Java hat zwar Tricks um das genauer hinzubekommen, aber wie zuverlässig diese sind weiß ich nicht mehr. Wenn du also Pech hast wird auf unterschiedlichen Rechnern mit unterschiedlichen Java-Versionen der Random-Generator mit der gleichen Zeit initialisiert und es deadlockt sofort, während es auf anderen Rechnern scheinbar korrekt funktioniert, weil der Random-Generator mit verschiedenen Zeiten initialisiert wird (es aber nicht tut, der Algorithmus ist falsch!).





@XHotSniperX: Dein Ansatz ist schon vom Konzept falsch, das Problem vom Multithreading ist, dass man (leicht) beweisen kann, dass es falsch ist, aber das Verhalten muss in der Realität nicht auftreten. Weil es von vielen Dingen abhängig ist und von Race Conditions die auftreten müssen usw.
Wenn z.B. auf einem PC totz Threads das Programm trotzdem nur auf einem CPU-Kern ausgeführt wird, wirst du in den Ausgaben des Programms das nicht merken, es scheint sich korrekt zu Verhalten aber gleichzeitig wird dein Programm auch nie deadlocken, weil es auf Grund der Single-Executor-Thread-Ausführung gar nicht möglich ist, wird es dann aber auf mehreren Kernen ausgeführt wird kann es schonwieder ganz anders aussehen.
Schau dir mal JAX TV: Java-Programmierung im Multicore-Zeitalter an, das Video ist wirklich gut. Es wird auch eines der prominentesten Beispiele gezeigt wie sich ein gethreadetes Programm auf verschiedenen CPUs verschieden verhalten kann.

Threading, egal in welcher Sprache, ist nicht leicht! Es ist die Königsdisziplin, es ist schnell geschafft aber nur seltenst richtig!
Ich kann wirklich nur jedem Java Concurrency in Practice ans Herz legen, egal wieviel man denkt über Threading zu wissen und wie es richtig ist, bevor man das Buch nicht gelesen hat, weiß man es nicht!
Denn wechselseitiger Ausschluss (Locks) sind nur eines der Themen, Memory Visibility (wird in dem Video an einem Beispiel gezeigt) ist das viel viel viel schwierigere Problem, und wird so gut wie immer falsch gemacht.

 

[XHotSniperX]

@ice-breaker:
Dass es einen Deadlock geben wird in irgendeiner Zeit war mir klar. Aber nicht von Anfang an. Das mit der Random Uhr wusste ich nicht. Gut dann ist das also umso besser. Dann seh ich sofort, wenn es einen Deadlock gibt oder nicht

Ausserdem ist die Randomzeit nicht für die Lösung des Concurrent Problems gedacht, sondern die natürliche Eigenschaft eines Menschen, fürs Essen oder Deken nicht immer die gleiche Zeit zu gebrauchen.

 

[ice-breaker]

Die Semaphoren haben eine 2. Methode bei der man die Wartezeit angegeben kann Nimm die Methode, wenn dann einmal der Lock nicht bekommen wird gibst du den anderen wieder frei und versuchst es nach einer zufälligen Zeit nochmal von neu, dann sollte es nicht mehr deadlocken.

Das mit der Zeit ist einfach eine weit hergeholte Vermutung Es ist in der Doku angegeben, dass man die Random-Generatoren seeden soll. Ob System.nanoTime() auf einem bzw. deinem System für alle Random-Generatoren den gleichen Wert liefert und diese somit immer identisch warten ist weit hegeholt, ich denke nicht. Aber es reicht ja schon der unwahrscheinliche Zufall, dass nur 2 Philosophen gleichzeitig versuchen die gleiche Gabel zu nehmen.

 

[XHotSniperX]

Habs jetzt so gemacht:

Fork

...
  public boolean take(){
    return sem.tryAcquire(); 
  }
...

Philosopher

...
   private void hungry(){
     state = 1;
     while(true){
       boolean l = left.take();
       boolean r = right.take();
       if(l&&r)
         break;
       else if(l)
         left.putBack();
       else if(r)
         right.putBack();  
       delay(50);
     }  
   }
...

Und als Applet siehe Anhang.

Scheint korrekt zu sein. Denkt ihr auch?

 

[ice-breaker]

Die Logik sollte jetzt stimmen, kann jetzt keinen Deadlock mehr geben.
Den delay von 50ms solltest du aber am besten noch zufällig machen Damit nicht 2 Philosophen die sich konkurrieren es ggf. immer zum gleichen Zeitpunkt wiederversuchen, das senkt die Kollisionsrate.

 

[XHotSniperX]

Ok super hab das ergänzt und die Option noch eingefügt, dass man Philosophen per Tastenklick wegschicken kann. (Taste 0-6)

Könnt es ja selbst ausprobieren, wenn es euch Spass macht xD

Ich danke euch allen für die tolle Hilfe!