Philosophen-Deadlock

CDW · Dez 6, 2008

Eingereicht von Ook!

Es handelt sich um das Philosophenproblem
Die Philosophen führen die Tätigkeiten immer und wiederholt in dieser Reihenfolge aus:
1. Denken
2. Gabeln nehmen
3. Essen
4. Gabeln wieder hinlegen

Implementiert das Philosophenproblem, dem Benutzer soll es möglich sein die unterschiedlichen Zeitwerte einzugeben (Denkzeit, Esszeit, Verhungerzeit).
Eure Anwendung soll dann den Ablauf mit fünf Philosophen und den vom Benutzer eingegeben Werten durchführen und schauen, ob es zu einem Deadlock kommt oder nicht...

Eine Erweiterung wäre ein Keller (Servierzeit) welcher mit in den Ablauf eurer Anwendung einfließen könnte.
Der Kellner muss jedes mal, wenn ein Philosoph seinen Teller geleert hat, diesen neu auffüllen (die besagte Servierzeit).

lagalopex · Dez 8, 2008

Es soll also das Problem simuliert werden, um zu zeigen, dass ein Deadlock entsteht!?
Das ist es ja gerade, was das Philosophenproblem verdeutlichen soll.

Aber was soll die Verhungerzeit sein? Zum Prüfen auf den Deadlock? Denn zwischen Hunger verspüren und Verhungern ist noch ein gewaltiger Unterschied. Und je nach gewählten Werten können sie verhungern ohne dass ein Deadlock entstand.
Wenn einer verhungert, stehen seine Gabeln dann wieder zur Verfügung!?

Was soll das mit dem Kellner? Der trägt zum Problem an sich ja nichts bei... es sei denn er braucht seehr lange...
Ook!?

Ook! · Dez 8, 2008

Aber was soll die Verhungerzeit sein? Zum Prüfen auf den Deadlock? Denn zwischen Hunger verspüren und Verhungern ist noch ein gewaltiger Unterschied.

Hehe... du kannst es aber auch runterbrechen

Beispiel für die Verhungerzeit:
- Philosoph denkt...
- Zeit abgelaufen, er hat Hunger...
- Er kann nicht essen weil der Kellner gerade keine Zeit hat oder die Gabeln belegt sind
=> Es vergeht die "Verhungerzeit", die Zeit, in der ein Philosoph etwas essen will, jedoch nichts bekommt und somit stirbt.

Und je nach gewählten Werten können sie verhungern ohne dass ein Deadlock entstand.

Jop, siehst du richtig... soll eben eine Simulation sein, die genau das ermöglicht.

Wenn einer verhungert, stehen seine Gabeln dann wieder zur Verfügung!?

Ne, wenn einer stirbt, dann ist die Simulation vorbei

Was soll das mit dem Kellner? Der trägt zum Problem an sich ja nichts bei... es sei denn er braucht seehr lange...

Der Kellner soll eigentlich nur eine Art "Extra" sein, die die Implementation erschweren soll... wirklich etwas mit dem Problem hat der Kerl nichts zutun, das siehst du richtig

LionC · Dez 8, 2008

so mal eine obj. orient. Lösung in cpp(mit der pthread-API)(noch ungetestet):

Code:

#include <cstdlib>
#include <cstdio>
#inlcude <pthread>

class Philosoph
{
public:

Philosoph(int th, int ea, int pl)
{
thinktime=th;
eattime=ea;
place=pl;
if(pl==4){right=0;} else{right=pl;}
if(pl==0){left=4;} else{left=pl-1;}
gabel[0]=false;
gabel[1]=false;
pthread_create(&thread,NULL,NULL,this.domyjob,(void*)NULL);
}

void gabelnehmenl()
{
while(!gabeln[left])
{}
gabeln[left]=false;
gabel[0]=true;
}

void gabelnehmenr()
{
while(!gabeln[right])
{}
gabeln[right]=false;
gabel[1]=true;
}

void think()
{
unsigned long start = time(NULL);
unsigned long end = start + thinktime;
while(time(NULL)!=end){}
}

void eat()
{
unsigned long start = time(NULL);
unsigned long end = start + eattime;
while(time(NULL)!=end){}
}

void gabellegen()
{
if(gabel[0]){gabel[0]=false; gabeln[place-1]=true;}
if(gabel[1]){gabel[1]=false; gabeln[place]=true;}
}

void* domyjob(void* arg)
{
while(true)
{
think();
gabelnehmenl();
gabelnehmenr();
eat();
gabellegen();
}
return NULL;
}

protected:
pthread_t thread;
int thinktime;
int eattime;
int place;
int left;
int right;
bool gabel[2];
};

int main()
{
bool gabeln[5] = {true,true,true,true,true};
Philosoph Kafka(2,2,0), Nietzsche(2,2,1), Sartre(2,2,2), Jesus(2,2,3), Gott(2,2,4);
pthread_join(Kafka.thread);

pthread_join(Nietzsche.thread);

pthread_join(Sartre.thread);

pthread_join(Jesus.thread);

pthread_join(Gott.thread);
return 0;
}

hab ich gestern abend geschrieben, threadsynchronisierung und comments kommen noch.

ist bis jetzt nur der kern
p.s. ich weß das gott und jesus keine philosophen sind^^

lagalopex · Dez 9, 2008

Also dein Code (LionC) lässt sich nicht übersetzen und ist auch logisch, dass es nicht geht... zu viele Fehler...
das nächste mal vielleicht vorher testen X(

probier es morgen auch mal, wenn ich etwas Zeit finde

Hab jetzt schon etwas angefangen. Sollen die Zeiten individuell einstellbar sein, oder global für alle Philosophen?

denke
warte bis kellner frei ist
warte die angegeben zeit bis serviert ist
gib kellner wieder frei
nehm die linke gabel
nehm die rechte gabel
prüfe ob schon verhungert
esse die angegebene zeit
setze die verhungern-zeit zurück
lege rechte und linke gabel zurück

Durch den Kellner wird das ganze recht schön angeordnet, so dass es eben nichtmehr so häufig zum deadlock kommt.

odigo · Dez 9, 2008

Original von lagalopex
Also dein Code (LionC) lässt sich nicht übersetzen und ist auch logisch, dass es nicht geht... zu viele Fehler...
das nächste mal vielleicht vorher testen X(

LionCs Code ist dann wohl ein klarer Fall von

Code:

void think()

ChiefWiggum · Dez 9, 2008

Code:
Original von odigo

Original von lagalopex
Also dein Code (LionC) lässt sich nicht übersetzen und ist auch logisch, dass es nicht geht... zu viele Fehler...
das nächste mal vielleicht vorher testen X(

Zum Vergrößern anklicken....

LionCs Code ist dann wohl ein klarer Fall von

Code:

void think()

Code:

void think()

Oo Also wenn ich denke kommt acuh was dabei heraus^^

also eher

Code:

gedanken *think()

^^

Painii · Dez 9, 2008

Hab mal eine Lösung in Java geschrieben.
Leider bricht das Programm nicht ab wenn ich keinen deadlock habe (also schlagen sich die Philosophen immer weiter den Bauch voll

), da muss ich mir noch was überlegen.
Ist auch nur die "einfache" Variante, also ohne dass man auf Kellner o.ä. warten muss.

Annahme: Um die Gabeln zu nehmen braucht 1 Philosoph 1 Sekunde.
Ein Philosoph:

Code:

public class Philosoph extends Thread{
	private Tisch tisch; //Tisch wo die Gablen liegen
	private int denkz,essz,verhz;
	private boolean dead=false;
	private int pos;	//Platz am Tisch
	boolean links=false,rechts=false;	//Welche Gabeln halte ich? (rechts und links)
	public Philosoph(int denkzeit,int esszeit, int verhungerzeit,Tisch tisch){
		this.denkz=denkzeit;
		this.essz=esszeit;
		this.verhz=verhungerzeit;
		this.tisch=tisch;
		tisch.place(this);
		for(int i=0;i<this.tisch.sitze.length;i++){
			if(this.equals(this.tisch.sitze[i]))this.pos=i;
		}
	}
	public void run(){
		while(!dead&&!isInterrupted()){	//Philosoph lebt, kann also denken und essen
			long start=0;		//Startpunkt 0
			long zeit=start;	//zeit die gezählt wird
			boolean gabeln;		//wenn true sind beide gabeln da -> kann essen
			try{
				this.sleep(denkz*1000);	//Beim schlafen hat man die besten Ideen
			}
			catch(InterruptedException e){	//Ein Philosoph ist tot
				break;
			}
			zeit=zeit+denkz;		//Zeit die zum denken gebraucht wurde
			do{
				gabeln=this.gabeln();	//versuche Gabeln zu nehmen bis es klappt
				zeit=zeit+1;	//wartezeit für gabeln 1 sekunde
			//	System.out.println("zeit:"+(zeit-start));
				if((zeit-start)>verhz){		//Philosoph ist verhungert während er auf gabeln gewartet hat
					this.dead=true;	
					break;
				}
			}while(gabeln==false);	//wir kommen raus wenn: essen==true, der philosoph also beide gabeln hat
									//oder der Philosoph tot ist
			try{					
				this.sleep(essz*1000);	//Mittagsschlaf kann nicht schaden, wenn der Philosoph tot ist ist die zeit auch egal
			}catch(Exception e){	//Ein Philosoph ist tot
				break;		
			}
			if(!dead){		//Philosoph ist nicht tot, hat also gegessen
				try{
					this.tisch.gabeln[pos-1]=true;	//Gabel links weglegen
				}
				catch(ArrayIndexOutOfBoundsException e){//pos=0, dann ist links die Gabel 4
					this.tisch.gabeln[4]=true;
				}
				this.tisch.gabeln[pos]=true;
				this.links=false;
				this.rechts=false;
			}
			//Philosoph ist satt oder tot
			//Wenn Philosoph satt beginnt die Schleife neu (weil !dead)
			//Sonst hört die Schleife auf
		}
		if(this.dead){
			this.tisch.ende();
			System.out.println(this.toString());
		}
	}
	public boolean gabeln(){
	
		if(this.tisch.gabeln[pos]==true){	//nimm gabel links von dir
			this.tisch.gabeln[pos]=false;
			this.links=true;
		}	
		try{
			if(this.tisch.gabeln[pos-1]==true){
				this.tisch.gabeln[pos-1]=false;	//nimm gabel rechts von dir
				this.rechts=true;

			}
		}
		catch(ArrayIndexOutOfBoundsException e){	//wird abgerufen wenn pos=0, dann muss gabel=4 sein
			if(this.tisch.gabeln[4]==true){
				this.tisch.gabeln[pos]=false;	//nimm gabel rechts von dir
				this.rechts=true;
			}
		}	
		if(this.links&&this.rechts){return true;}	//wir haben beide gabeln, können essen
		else return false;	//wir haben nicht beide gabeln, also warten wir noch auf eine
	}
	public String toString(){
		String retour = "";
		retour=retour+"Philosoph "+name+" ist tot";
		return retour;
	}
	public String name="";
	public void setNamee(String a){
		this.name=a;
	}
}

Tisch wo die Philosophen sitzen, mit main-methode zum starten - Die Werte führen zu einer Endlosschleife, erzeugen also kein deadlock (zumindest nicht bei 10 minuten laufzeit des programms):

Code:

public class Tisch {
	public boolean[] gabeln;
	public Philosoph[] sitze;
	public boolean voll=false;
	public int frei=0;
	public Tisch(){
		gabeln=new boolean[5];
		sitze=new Philosoph[5];
		for(int i=0;i<5;i++){
			gabeln[i]=true;
		}
	}
	public void place(Philosoph a){
		if(!voll){
			sitze[frei]=a;
			frei++;
		}
		if(frei>sitze.length)voll=true;
	}
	public void ende(){
		for(int i=0;i<sitze.length;i++){
			sitze[i].interrupt();
		}
	}
	public static void main(String[] args){
		Philosoph a,b,c,d,e;
		Tisch x=new Tisch();
		a=new Philosoph(4124,125,2999,x);
		b=new Philosoph(124,3,9994,x);
		c=new Philosoph(435,2,19990,x);
		d=new Philosoph(682,3,29995,x);
		e=new Philosoph(19674,2,99999,x);
		a.setNamee("a");
		b.setNamee("b");
		c.setNamee("c");
		d.setNamee("d");
		e.setNamee("e");
		a.start();
		b.start();
		c.start();
		d.start();
		e.start();
		
	}
}

sw33tlull4by · Dez 9, 2008

Ich glaube das pruefen auf ein Deadlock ist ein semientscheidungsproblem, dh glaube ich kaum das du besser werden wirst, denn was ist wenn das Programm sich beendet und der Deadlock erst in der naechten runde auftritt.
Abgesehen davon finde ich diese Version des Philosophenproblems sehr schoen da man den Kellner als eine Art Programm sehen kann was immer wieder zu verarbeitende Informationen nachliefert, die Philosophen sind dann Programme welche die Daten verarbeiten , es kommt zu einem Fehler wenn ein Philosoph keine Daten zum verarbeiten vorfindet wenn er arbeiten muss und es kann zu einem Deadlock kommen.
Sehr realitaetsnah.
mfg

sw33t

lagalopex · Dez 9, 2008

Painii:
Bei dir warten sie ja ewigkeiten.
Der erste denkt zum Beispiel über eine Stunde... ist aber schon nach 50 Minuten verhungert...
Der Deadlock entsteht ja gerade wenn alle Philosophen gleichzeitig die erste Gabel nehmen und dann alle auf die zweite warten... was bei dir natürlich Ewigkeiten dauert.
Selbst wenn im Microsekundenbereich gedacht/gegessen/... wird, dauert es noch ne ganze weile...

Wieso macht ihr eigentlich alle so ein krassen pollen auf ne variable?! Man kann doch doch schön mit mutexen arbeiten...

Code:

#include <iostream>

#include <pthread.h>
#include <unistd.h>

using namespace std;

unsigned long long usecs()
{
	timespec ts;
	clock_gettime(CLOCK_MONOTONIC, &ts);
	return ts.tv_sec * 1000000 + ts.tv_nsec / 1000;
}

enum status {status_think, status_wait0, status_serve, status_wait1, status_wait2, status_eat, status_dead};

class philosopher
{
public:
	philosopher(pthread_mutex_t *left_spoon, pthread_mutex_t *right_spoon, pthread_mutex_t *waiter, timespec *think, timespec *serve, unsigned long long *starve, timespec *eat)
		 : l(left_spoon), r(right_spoon), w(waiter), time_think(*think), time_eat(*eat), time_serve(*serve), time_starve(*starve)
	{
		me = status_think;
		time_last = usecs();
		pthread_create(&id, 0, wrapper, this);
	}
	~philosopher()
	{
		pthread_join(id, 0);
	}

	status stat()
	{
		if (usecs() - time_last > time_starve && me != status_eat)
			return status_dead;
		return me;
	}
	bool isdead()
	{
		return me == status_dead;
	}
private:
	static void *wrapper(void *ptr)
	{
		return static_cast<philosopher *>(ptr)->thread();
	}
	void *thread()
	{
		while (true) {
			me = status_think;
			nanosleep(&time_think, 0);
			if (w) {
				me = status_wait0;
				pthread_mutex_lock(w);
				me = status_serve;
				nanosleep(&time_serve, 0);
				pthread_mutex_unlock(w);
			}
			me = status_wait1;
			pthread_mutex_lock(l);
			me = status_wait2;
			pthread_mutex_lock(r);
			me = status_eat;
			if (usecs() - time_last > time_starve) {
				me = status_dead;
				break;
			}
			nanosleep(&time_eat, 0);
			time_last = usecs();
			pthread_mutex_unlock(r);
			pthread_mutex_unlock(l);
		}
		return 0;
	}
	status me;
	pthread_mutex_t *l, *r, *w;
	pthread_t id;
	timespec time_think, time_eat, time_serve;
	unsigned long long time_starve, time_last;
};

class table
{
public:
	table(unsigned int number_of_philosophers) : num_p(number_of_philosophers)
	{
		forks = new pthread_mutex_t[num_p];
		for (unsigned int i = 0; i < num_p; ++i)
			pthread_mutex_init(&forks[i], 0);
		waiter = new pthread_mutex_t; // NULL ohne waiter
		pthread_mutex_init(waiter, 0);
		p = new philosopher *[num_p];
		timespec think, serve, eat;
		readtsus("Time to think in us: ", &think);
		readtsus("Time to serve in us: ", &serve);
		readtsus("Time to eat in us: ", &eat);
		unsigned long long starve;
		cout << "Time till starved in us: " << flush;
		cin >> starve;
		for (unsigned int i = 0; i < num_p; ++i)
			p[i] = new philosopher(&forks[i], &forks[(i + 1 >= num_p)? 0 : i + 1], waiter, &think, &serve, &starve, &eat);
	}
	~table()
	{
		for (unsigned int i = 0; i < num_p; ++i)
			delete p[i];
		delete[] p;
		delete waiter;
		delete[] forks;
	}
	void monitor()
	{
		timespec t = {0, 250000000};
		while (!alldead()) {
			cout << " ";
			for (unsigned int i = 0; i < num_p; ++i)
				printstat(p[i]->stat());
			cout << "\r" << flush;
			nanosleep(&t, 0);
		}
		cout << "\nAll dead..." << endl;
	}
	bool alldead()
	{
		for (unsigned int i = 0; i < num_p; ++i)
			if (!p[i]->isdead())
				return false;
		return true;
	}
private:
	void readtsus(const char *promt, struct timespec *t)
	{
		unsigned long long x;
		cout << promt << flush;
		cin >> x;
		t->tv_nsec = (x % 1000000) * 1000;
		t->tv_sec = x / 1000000;
	}

	void printstat(status s)
	{
		static char txt[][2] = {"T", "0", "S", "1", "2", "E", "D"};
		cout << txt[s];
	}
	unsigned int num_p;
	pthread_mutex_t *forks;
	pthread_mutex_t *waiter;
	philosopher **p;
};



int main()
{
	table t(5);
	t.monitor();
}

MontyPerl · Feb 2, 2009

Auch ein triviales Beispiel in C mit pthreads.h. Die Zeiten werden hier mit "rand() % 5" in Sekunden festgelegt, man könnte natürlich einfach in die philosopher-Struct ein "eattime" reinpacken, damits deterministisch ist. (Nicht im Sinne von rand() deterministisch, sondern eher "statisch".) Das sterben hab ich hier als verlieren von Gewicht implementiert.

Code:

#include <stdio.h>
#include <time.h>
#include <pthread.h>

typedef struct {
    pthread_mutex_t *leftFork, *rightFork;
    int weight;
    char *name;
} philosopher;


void think(philosopher *p) {
    int awhile = rand() % 5;
    printf("%s: hmmmmm\n", p->name);
    sleep( awhile );
}

void eat(philosopher *p) {
    int awhile = rand() % 5;
    printf("%s: i'm hungry\n", p->name);
    pthread_mutex_lock(p->leftFork);
    sleep(1);   /* no reason for any kind of haste */
    pthread_mutex_lock(p->rightFork);
    sleep( awhile );
    p->weight += awhile*15;    /* yammi */
    pthread_mutex_unlock(p->leftFork);
    pthread_mutex_unlock(p->rightFork);
}

void *philosophise(void *arg) {
    philosopher *p = arg;
    while (p->weight > 0) {
        think(p);
        eat(p);
    }
    printf("%s died of starvation.\n", p->name);
}

int main(void) {
    pthread_mutex_t forkOne   = PTHREAD_MUTEX_INITIALIZER;
    pthread_mutex_t forkTwo   = PTHREAD_MUTEX_INITIALIZER;
    pthread_mutex_t forkThree = PTHREAD_MUTEX_INITIALIZER;
    philosopher nietzsche = { &forkOne, &forkTwo,   91, "Friedrich" };
    philosopher sartre    = { &forkTwo, &forkThree, 76, "Jean Paul" };
    philosopher descartes = { &forkThree, &forkOne, 84, "Rene" };
    srand( time(NULL) );
    pthread_t n, s, d;
    pthread_create(&n, NULL, &philosophise, &nietzsche);
    pthread_create(&s, NULL, &philosophise, &sartre);
    pthread_create(&d, NULL, &philosophise, &descartes);
    while (nietzsche.weight > 0 || sartre.weight > 0 || descartes.weight > 0) {
        nietzsche.weight -= 10;
        sartre.weight    -= 10;
        descartes.weight -= 10;
        sleep(1);
    }
    pthread_join(n, NULL);
    pthread_join(s, NULL);
    pthread_join(d, NULL);
    return 0;
}

Die "Todesnachricht" erscheint natürlich nur, wenn der betreffende thread (oder Prozess in linux) nicht deadlocked.

Philosophen-Deadlock

0

0

0

0

0

0

0

0

sw33tlull4by

Guest

0

0