Du verwendest einen veralteten Browser. Es ist möglich, dass diese oder andere Websites nicht korrekt angezeigt werden. Du solltest ein Upgrade durchführen oder ein alternativer Browser verwenden.
Modellieren Sie das Problem der speisenden Philosophen so, dass kein Deadlock
eintreten kann. Dass Problem besteht kurz darin, dass n Philosophen an einem kreisrunden
Tisch sitzen und Spaghetti essen wollen. Dass schafft ein Philosoph nur, wenn er über 2
Gabeln verfügt. Vor jedem Philosophen steht ein Teller mit Spaghetti, zwischen 2 Tellern
liegt jeweils eine Gabel. Es ist nicht schlimm, dass nicht alle Philosophen gleichzeitig essen
können, da Philosophen gerne denken und einfach warten bis die Nachbarn ihre Gabel nach
dem Essen wieder an die alte Stelle zurücklegen. Es gibt aber ein Problem, wenn alle
Philosophen gleichzeitig die rechts von ihnen liegende Gabel (oder alle die linke Gabel)
ergreifen. Dann entsteht ein Deadlock, weil kein Philosoph essen kann, da er nicht an die
zweite Gabel herankommt.
Mein Programm läuft soweit, nur nach ein paar Sekunden erreich ich den Deadlock - nun hab ich schon was gegrübel wie ich den den Deadlock vermeiden kann, bin aber auf keine Lösung gestoßen die nicht letzendlich vom Zufall abhängt.
Jemand ein Idee wie ich das geregelt krieg ohne das es Zufallsgesteurt ist?
Ganz pragmatisch zusammengefasst (man findet da auch ausführliche Webseiten drüber): Ein Philosoph darf nur dann beide Gabeln nehmen, wenn er sich beide nehmen kann, ohne dass ihm jemand dazwischenkommt.
Ohne code, beschreibung was man macht etc. mal wieder schwer zu beantworten. Im ersten Ansatz schmeiß ich dir mal das Schlüsselwort synchronized an den Kopf. Damit lässt sich das Problem vermeiden.
Ohne code, beschreibung was man macht etc. mal wieder schwer zu beantworten. Im ersten Ansatz schmeiß ich dir mal das Schlüsselwort synchronized an den Kopf. Damit lässt sich das Problem vermeiden.
wenn jeder philosoph eine gabel im zugriff hat und darauf wartet das der andere die fehlende zweite gabel frei gibt warten alle auf den anderen ohne ende ;-)
eine gabel ist eine selbst geschriebene semaphore:
Code:
public class MySemaphore
{
private final int max_allowed;
private int currentInUse=0;
public MySemaphore(int allowed)
{
max_allowed = allowed;
}
public synchronized void acquire() throws InterruptedException
{
while (currentInUse == max_allowed)
wait();
currentInUse++;
return;
}
public synchronized void release()
{
if (currentInUse - 1 > 0)
currentInUse--;
notifyAll();
}
}
public class Fork extends MySemaphore
{
private String name;
public Fork(String name)
{
super(1);
this.name = name;
}
public String getName() {return name;}
}
es gibt N philosophen thread und n sempahoren (gabeln), jeder philosoph arbeitet so:
Code:
package auf2_Philosophen;
public class Philosoph implements Runnable
{
String name;
Fork forkLeft;
Fork forkRight;
public Philosoph(String name)
{
this.name = name;
}
public void setForkLeft (Fork l) {forkLeft = l;}
public void setForkRight(Fork r) {forkRight = r;}
public void run()
{
while(true)
{
thinkAboutIt();
try {spachteln();} catch (InterruptedException e) { e.printStackTrace();}
}
}
private void thinkAboutIt()
{
System.out.println(name + " denkt ....");
}
private void spachteln() throws InterruptedException
{
System.out.println(name + " versucht rechte Gabel zu nehmen");
forkRight.acquire();
System.out.println(name + " hat rechte Gabel");
System.out.println(name + " versucht linke Gabel zu nehmen");
forkLeft.acquire();
System.out.println(name + " hat linke Gabel");
System.out.println(name + " hat 2 Gabeln und isst");
forkRight.release(); forkLeft.release();
System.out.println(name + " hat seine Gabeln zurück gelegt");
}
public void print()
{
System.out.println(name + " L:" + forkLeft.getName() + " R:" + forkRight.getName());
}
}
2. Mensch... das sind Philosophen (verdammich ). Und Philosophen denken... Warum also nicht auch daran, sich beide Gabeln "gleichzeitig" zu schnappen?
Aber mal Scherz beiseite. Es geht im Prinzip nur um die Antwort, wie man Deadlocks verhindert. Und das geht nunmal (wie vom 1. Gast schon ganz pragmatisch erwähnt) mit "synchronized". "Gleichzeitigkeit" ist bei Mensch und Maschine nie wirklich gegeben, sondern lediglich in individuellen Grenzen toleriert. Deine Philosophen-Threads kannst du nur nacheinander starten. Deswegen hat der erste Philosoph bereits zwei Gabeln in der Hand, bevor der letzte sich auch nur eine greifen konnte (sprich: sein Thread gestartet wurde.).
Entscheidend für dein Problem, das hier trotzdem ein Deadlock entsteht, ist die Tatsache, das jede einzelne Gabel von "max_allowed" Philosopen benutzt werden kann (synchronized this!) und eigentlich nur eine davon existiert. Die Klasse Fork müsste eigentlich ungefähr so aussehen:
Code:
public class Fork
{
private boolean inuse = false;
public synchronized boolean aquire()
{
if(inuse) return false;
inuse = true;
return true;
}
public synchronized void release()
{
inuse = false;
}
}
Und dann darf pro Philosoph natürlich nur ein Objekt instanziert werden. Ein Philosoph sieht dann ungefär so aus:
Code:
public class Philosoph
extends Thread
{
private final Fork left;
private final Fork right;
public Philosoph(int count)
{
if(count <= 0) throw new RuntimeException("illegal value");
left = new Fork();
Philosoph tmp = null;
for(int n = 0; n < count - 1; n++) tmp = new Philosoph(tmp);
right = tmp.left;
start();
}
private Philosoph(Philosoph left)
{
right = (left != null)? left.left : new Fork();
this.left = new Fork();
start();
}
public void run()
{
try {
boolean aquired = false;
while(!aquired) aquired = left.aquire();
aquired = false;
while(!aquired) aquired = right.aquire();
Thread.sleep(10000);
left.release();
right.release();
} catch(InterruptedException e) {
// do nothing
}
}
}
So. Ich hab' das mal so hier im Editorfenster hardcoded. Das bedeutet, das ich das 1. nicht getestet habe und 2. das sich Syntaxfehler eingeschlichen haben könnten. Aber von der Logik her sollte das funzen... ohne Deadlocks!
Hier ist 'ne prinzipiell identische Form meiner Lösung. Die Änderungen belaufen sich auf folgende Dinge.
1. Klasse Philosoph zwecks Ausgabe in die Konsole leicht verändert. Ablauf bleibt der selbe.
2. Unnötiges "synchonized" aus Fork.release() entfernt.
3. Klasse Fork als statische Memberklasse eingefügt. Erleichtert lediglich "copy & paste".
4. "main()"-Methode zum testen hinzugefügt.
5. Einen geringfügigen Fehler in der Verteilung der Gabeln beseitigt.
Code:
public final class Philosoph
extends Thread
{
private final Fork left;
private final Fork right;
private String name;
public Philosoph(int count)
{
if(count <= 0) throw new RuntimeException("illegal value");
left = new Fork();
Philosoph tmp = this;
for(int n = 1; n < count; n++) {
tmp = new Philosoph(tmp);
tmp.name = "Philosoph " + n;
}
name = "Philosoph " + count;
right = tmp.left;
start();
}
private Philosoph(Philosoph left)
{
right = (left != null)? left.left : new Fork();
this.left = new Fork();
start();
}
public void run()
{
try {
try {
boolean eat = false, aql = false, aqr = false;
while(!eat) {
System.out.println(name + " thinks...");
Thread.sleep(1000);
while(!aql) aql = left.aquire();
System.out.println(name + " got left Fork");
System.out.println(name + " thinks about philosopy...");
Thread.sleep(1000); // forced Deadlock before
while(!aqr) {
aqr = right.aquire();
if(!aqr) {
left.release();
aql = false;
System.out.println(name + " released left Fork");
}
}
System.out.println(name + " got right Fork");
eat = aql && aqr;
}
System.out.println(name + " eats");
Thread.sleep(10000);
left.release();
System.out.println(name + " released left Fork");
right.release();
System.out.println(name + " released right Fork");
} catch(InterruptedException e) {
// do nothing
}
}
private static class Fork
{
private boolean inuse = false;
/**
* Gabel nehmen
* ... wird "synchronized" entfernt kann es zu DeadLocks kommen.
* Es verhindert den Versuch zweier Philosophen, gleichzeitig
* die Gabel zu nehmen.
* @return boolean Erfolg/Misserfolg
*/
public synchronized boolean aquire()
{
if(inuse) return false;
inuse = true;
return true;
}
/**
* Gabel weglegen
* ... "synchronized" ist hier nicht erforderlich.
* Die Gabel kann ja nur von einem Philosophen genommen werden.
* Deswegen kann sie auch nur ven einem gleichzeitig weggelegt
* werden.
*/
public void release()
{
inuse = false;
}
}
public static void main(String args[])
{
new Philosoph(10);
}
}
Die Idee aus dem Link von Landei, das die Philosophen die erste Gabel weglegen sollen wenn sie die Zweite nicht bekommen können sowie die Tatsache, das sie zunächst Nachdenken sollen habe ich mir gespart. Das lässt sich bei Interesse aber noch nachliefern.
danke für die vielen ansätze, ansich plausibel, wie einer der vorsprecher bemerkt hat, sind das hausaufgaben. Als nebenbedinung ist das hier allerdigns noch mit im spiel:
Die Philosophen sollen durch Threads dargestellt werden. Sie versuchen 2 Gabeln
zu erwischen; dann essen sie und anschließend legen sie beide Gabel zurück. Die Gabeln
sollen durch Semaphor-Objekte aus dem Paket java.util.concurrent repräsentiert
werden. Das Problem ist nur dann lösbar, wenn sich nicht alle Philosophen identisch
verhalten. Die Vermeidung des Deadlock soll natürlich nicht auf bloßem Zufall beruhen!
die semaphore aus dem concurrent package arbeitet ja praktsich wie meine, sieht versucht den lock zu bekommen, ansonsten gehts sie auf wait() und wartet auf ein notify(all)
krieg ich das deadlock save gelöst mit der sempahoren semantik ? ich hab daran mittlerweile kapituliert weil ich im grunde immer wieder vom zufall abhänge, was nicht sein soll (laut aufgabenstellung)
Hab' ich mir gedacht, auch wenn's nicht in dieses Schema passt. Aber da ja ein eigenes Konzept vorhanden ist, nehme ich mal an, das dieses Thema nicht gegen die Boardregeln verstösst. BTT.
Zu deinem Problem... Ich hab' mich über diese Semaphoren-Geschichte mal kurz informiert und muss sagen, dass das für die Aufgabenstellung ziemlich überzogen ist da man für eine Gabel ja nur eine "permission" (in Benutzung oder nicht) braucht, mit Semaphoren allerdings weit mehr möglich sind, weil dort ein int dafür "verschwendet" wird. Faktisch stellt sich mir zudem auch keine Möglichkeit dar, wie ein Philosoph mit bekommen sollte ob der Griff nach der Gabel erfolgreich war oder nicht. Dazu fehlt bei "aquire()" ein Rückgabewert (boolean). Erschwerend kommt dann noch hinzu, das ein Philosoph bei einem Fehlversuch eine zweite Gabel zu bekommen, keine Möglichkeit hat die erste wieder fallen zu lassen und alles von vorne zu versuchen (Ist für die Verhinderung des Deadlocks ebenfalls erforderlich. Und ob nun Semaphore-Objekt oder nicht... Das ist wahrscheinlich der Löwenanteil der Lösung).
Hosiki hat gesagt.:
Die Vermeidung des Deadlock soll natürlich nicht auf bloßem Zufall beruhen!
Was genau ist ein DeadLock? Letztenendes doch ein Ereignis, welches auf blossem "Zufall" beruht. Es ist ja gerade bei der Geschichte mit den Philosophen der Zufall, der alle zur gleichen Zeit dazu bewegt, sich die jeweils linke Gabel zu nehmen. Wenn das passiert hat jeder eine Gabel in der Hand und für keinen ist eine zweite da. Das bedeutet, dass alle Threads danach in der Warteschleife hängen um eine zweite zu bekommen. Was aber nicht geht, weil keiner Anfangen kann zu essen. Und da fällts auch mir wie Schuppen aus den Haaren... ein simples "synchronized" reicht da ohnehin nicht. Ich schreibe da mal eine Zeile in meinen Code, die den Deadlock forcieren dürfte.
Die Vermeidung von Deadlocks mit synchronized? synchronized ist der Grund für Deadlocks.
Ohne Synchronisation kein (aktiver) Monitor, ohne Monitor keine Semaphore, ohne Sempahore kann es nicht
zu der Situation kommen, dass 2 Threads gegenseitig auf Resourcen warten.
Und die Lösug dafür ist wait/notify.
Ihr sprecht hier von was anderem: Synchronized ist die Lösung für Race Conditions.
@hdi: Ok... das hat bei genauer Betrachtung durchaus Sinn... wenn man sich im Klaren darüber ist, was Deadlocks sind und wie sie zustande kommen. Obwohl... "synchronized" wäre dann nur meistens und nicht immer der Grund dafür. Sind wir uns einig, das es in meinem Code oben auch ohne "synchronized" zu einem Deadlock kommt? Wenn nicht, dann folgendes: Jeder Philosoph kann sich zunächst die linke Gabel greifen. Die Tatsachen, das sich zwei Philosophen eine Gabel teilen müssen, und das der Vorgang sich die rechte Gabel zu greifen erst beginnt, wenn alle die Linke bereits in der Hand haben, macht "synchronized" hier recht überflüssig. Theoretisch hätte ich also keinen Monitor. An diesem Punkt möchte ich nochmals klarstellen, das ich wirklich wenig Ahnung von "Semaphoren" habe. Ich sehe nur, das die Gabeln alle "inuse" sind und genau dort habe ich meinen Monitor. Kann es sein, das genau dieser boolsche Wert eine Semaphore ist? Fakt ist, das nun alle Philosophen darauf warten, das ihr jeweils rechter Nachbar seine Linke Gabel wieder freigibt. Und genau das ist des Rätsels Lösung. Die Philosopen müssen (auch wenn weiterhin absolut kein interesse daran besteht ) die Linke Gabel wieder freigeben, wenn der Versuch, sich die Rechte zu greifen fehlschlug. Ich ändere das mal... ("synchronized" bleibt aber drin...)
@Hosiki: Nun sind es wohl nicht einfach nur mehr Hausaufgaben... "hdi" hat mich da auf etwas gebracht, was mich dazu anspornt, mir diese Geschichte mit den Semaphoren mal genauer anzuschauen.
Ohne Synchronisation gibt es nie Deadlocks. Nur, weil du das Schlüsselwort synchronized nicht benutzt, heisst das nicht, dass du nicht synchronisierst! Ob jetzt "synchronized" oder selber einen Monitor zusammenbauen mit booleschen Variablen wie "eat" usw kommt auf's selbe raus, zumindest von der Idee her. Wobei eine Boolesche Variable keine Sempahore sind, Semaphore arbeiten atomar was eine normale Boolesche nicht tut. Da steckt noch bisschen mehr dahinter: http://www.artima.com/insidejvm/ed2/threadsynch.html
ich würde also lieber mit synchronized arbeiten und nicht mit irgendwelchen eigenen booleans und while-Schleifen.
Wie gesagt, die Lösung für Deadlocks bei synchronized sind die Methoden wait() und notify().
). Und Philosophen denken... Warum also nicht auch daran, sich beide Gabeln "gleichzeitig" zu schnappen?
