The dining philosopher's problem.

[themuzicman]

Believe it or not, this came from my Operating Systems Concepts class, in dealing with resource management and deadlocks.

You have 5 philosophers around a table. Each has a plate of spaghetti (which is a never ending pasta bowl). Between each plate is a fork.

Now, each philosopher can either philosophize or eat, but not both, but he must be doing one or the other. When he is philosophizing, he needs no utensils. However, when eating, he requires the fork on either side of his plate.

Thus, when the philosopher on either side of one of them is eating, they cannot eat.

Each philosopher, when preparing to eat, first picks up the fork on his right, and then the fork on his left.

Now, if each philosopher decides to eat at the same time, they'll pick up the fork on their right, but the one on their left is gone, so they each are waiting for the fork on the left, and they all starve.

What rule(s) do you implement to keep the philosophers from starving?

Michael

[Sparko]

Rule 1:

Ask the waitress to give them some more forks.

Problem solved.

[Sparko]

If that is outside the bounds of your problem,

Then just implement a time for each to eat while the others talk. Start with #1 eating for 5 minutes, while 2-5 talk. then #2 eats for 5 minutes while 1,3-5 talk, and so on.

Or if you wan to maximize the number of people eating at one time, start with 1 & 3 eating for a set time, then switch to 3 & 5, then 5 & 2, then 2 & 4, then 4 & 1. repeat.

[jason]

What rule(s) do you implement to keep the philosophers from starving?
Consulting my handy copy of Tanenbaum,

You want to do something like the following to avoid deadlock.

#define N 5
#define LEFT (i-1)%N
#define RIGHT (i+1)%N
#define THINKING 0
#define HUNGRY 1
#define EATING 2
typedef int semaphore;
int state[N];
semaphore mutex = 1;
semaphore s[N];

void philosopher(int i){
while(TRUE){
think();
take_forks();
eat();
put_forks();
}
}

void take_forks(int i){
down(&mutex);
state[i] = HUNGRY;
test(i);
up(&mutex);
down(&s[i]);
}

void put_forks(int i){
down(&mutex);
state[i] = THINKING;
test(LEFT);
test(RIGHT);
up(&mutex);
}

void test(int i){
if(state[i]==HUNGRY&&state[LEFT]!=EATING&&state[RIGHT]!=EATING){
state[i]=EATING;
up(&s[i]);
}
}

Each philosopher runs void philosopher(int[i]) and the put_forks()/take_forks() routines makes sure that you get the proper mutual exclusion and avoid a dead lock.

It is nice simple solution that does work and doesn't use busywaiting or any thing like that.

Jason

[Sparko]

Consulting my handy copy of Tanenbaum,

You want to do something like the following to avoid deadlock.

#define N 5
#define LEFT (i-1)%N
#define RIGHT (i+1)%N
#define THINKING 0
#define HUNGRY 1
#define EATING 2
typedef int semaphore;
int state[N];
semaphore mutex = 1;
semaphore s[N];

void philosopher(int i){
while(TRUE){
think();
take_forks();
eat();
put_forks();
}
}

void take_forks(int i){
down(&mutex);
state[i] = HUNGRY;
test(i);
up(&mutex);
down(&s[i]);
}

void put_forks(int i){
down(&mutex);
state[i] = THINKING;
test(LEFT);
test(RIGHT);
up(&mutex);
}

void test(int i){
if(state[i]==HUNGRY&&state[LEFT]!=EATING&&state[RIGHT]!=EATING){
state[i]=EATING;
up(&s[i]);
}
}

Each philosopher runs void philosopher(int[i]) and the put_forks()/take_forks() routines makes sure that you get the proper mutual exclusion and avoid a dead lock.

It is nice simple solution that does work and doesn't use busywaiting or any thing like that.

Jason

Yeah. or they could just ask for more forks. :-)

[rmwilliamsjr]

Consulting my handy copy of Tanenbaum,

You want to do something like the following to avoid deadlock.

#define N 5
#define LEFT (i-1)%N
#define RIGHT (i+1)%N
#define THINKING 0
#define HUNGRY 1
#define EATING 2
typedef int semaphore;
int state[N];
semaphore mutex = 1;
semaphore s[N];

void philosopher(int i){
while(TRUE){
think();
take_forks();
eat();
put_forks();
}
}

void take_forks(int i){
down(&mutex);
state[i] = HUNGRY;
test(i);
up(&mutex);
down(&s[i]);
}

void put_forks(int i){
down(&mutex);
state[i] = THINKING;
test(LEFT);
test(RIGHT);
up(&mutex);
}

void test(int i){
if(state[i]==HUNGRY&&state[LEFT]!=EATING&&state[RIGHT]!=EATING){
state[i]=EATING;
up(&s[i]);
}
}

Each philosopher runs void philosopher(int[i]) and the put_forks()/take_forks() routines makes sure that you get the proper mutual exclusion and avoid a dead lock.

It is nice simple solution that does work and doesn't use busywaiting or any thing like that.

Jason
but does it avoid starvation?

[themuzicman]

NO! that's the problem. THe person on either the right or the left could be eating all the time, leaving the one in the middle to starve!

[jason]

Yeah. or they could just ask for more forks. :-)
But it is a classic computer science deadlocking problem.

Of course you can always buy more hardware, the problem is how do you solve a problem without having unlimited resources.

And yes I know you are joking, but it is a serious problem that is nicely illustrated this way.

Jason

[jason]

but does it avoid starvation?
No and it is not possible to avoid starvation unless you are willing to tear the forks off of people. The system presumes people will release a resource they are not using. There is no way to solve that problem without being willing to take the fork out of somebodies hand by force.

Jason

[jason]

NO! that's the problem. THe person on either the right or the left could be eating all the time, leaving the one in the middle to starve!
Nothing can be done about that. Without more forks a person who hogs both forks and refuses to give them up must be forced to do so or else starvation will occur. You can't do anything a about it without forcibly removing the fork from a person.

So you can employ a waiter that kills any diner that wont give up a fork after a while, but short of that you are stuck.

Jason

[learning]

Did you ever read the parable of what heaven and hell was like. A room full of people with bowls of soup, but the spoons had one to two foot handles. In the room in hell they can't get the spoons in their mouths, they are elbowing each other trying to do so, but can't. In heaven, they are reaching across the table (very easy as the spoons are long handled) and feeding each other.

So, the philosopher who is hungry, could feed the philosopher who is talking, so as to shut him up and get a chance to eat later? :)

[rmwilliamsjr]

No and it is not possible to avoid starvation unless you are willing to tear the forks off of people. The system presumes people will release a resource they are not using. There is no way to solve that problem without being willing to take the fork out of somebodies hand by force.

Jason
tear forks off as in limit time or poll

[jason]

tear forks off as in limit time or poll
The problem is that this could make a real mess of things.

What if I simply need to eat for five minutes straight before I can get back to thinking properly ?

Jason

[Minnesota]

To prove that there does not exist a truely distributed deterministic,
symmetric solution to the Dining philosopher's problem.

Assumption: Every action of each philosopher is a test and set action.

The granularity of accessing the shared variables is low
in the sense that when a philosopher is testing the right
neighbour's state in terms of holding the fork he caannot
test the left neighbour's state.

Proof : By Contradiction


Suppose that there exists a truely distributed, symmetric and
deterministic solution to the problem. We show that there is a
schedule that deadlocks the system or some contradiction to
the basic assumptions to the problem occurs.


The Schedule is as follows:


Each philosopher process is sheduled in a round robin manner.
The scheduler assigns some number to them which need not be
known to them and the scheduler lets the philosophers execute
exactly one atomic action in each round. Since the solution is
symmetric, the state of the philosophers are the same at the
end of each round. Also in each round each of them executes
the same atomic action.


Now suppose in one turn a philopher tests the left forks
availability and since that is available to all so in the
next step everybody grabs the left fork and the system
deadlocks.
Similar thing happens if they test the right fork first and
grab them.


If they test the left and right sequentially and then grab
then all the five will be having both the forks and that
violates the restrictions of the problem.

Hence proved. (http://www-i2.informatik.rwth-aachen.de/Forschung/MCS/Mailing_List_archive/con_hyperarchive_1993/0097.html)

[Cynic Sage]

:shrug:meh...
I can eat spaghetti using only one fork.

EDIT:

Dang Mistake, I misread the question. I thought you were implying that 2 forks were needed to eat Spaghetti of a plate.

whoops:blush:

[Sparko]

what about my example above using times slices? assign each philosopher a time slot to eat for say 5 minutes, then switch to the next philosopher for 5 minutes, etc. The same way a computer runs multiple programs and users.

[themuzicman]

The solutioun is twofold:

1) If a philosopher picks up the right, and the left is unavailable, he puts it back down and philosophizes for a random but parameterized (i.e. 1 to 8 minutes) period of time (which is different for each philosphizing), and then attempts to eat again.

2) Before picking up each fork, he must check with the philosopher on each side to find out how many times they've attempted and failed to pick up a fork. If a philosopher on either side has more failures than he, he releases both forks and philosophizes again.

QED

Michael

[jason]

what about my example above using times slices? assign each philosopher a time slot to eat for say 5 minutes, then switch to the next philosopher for 5 minutes, etc. The same way a computer runs multiple programs and users.
It works, but it doesn't work to solve the problem that this problem models.

The problem itself deals with how to avoid deadlocks when there is limited resources available and everybody has to share.

Incidentally, has anybody considred the hygeine problem this would be ?

Jason

[NeilUnreal]

It’s interesting how often these theoretical problems arise in real life. One of the main reasons to acquire a mental catalog of them is to learn to recognize them (and not merely to avoid them!). When one encounters a poorly understood engineering problem, the first instinct is to look for a work-around. Being able to reclassify the problem as a well-know computer science problem will alert one to what -- if any -- solutions exist, and will prevent a fruitless search for a work-around that doesn’t exist.

For example, much earlier in my programming career, I was helping to design an interrupt-driven serial driver for placement on a chip with very limited resources. Buffering even a single byte of the I/O consumed a large number of logic gates, and so we wanted to avoid it. However, no matter how hard we worked on the problem, we always had some residual sliver of time during which either an interrupt or a byte could be lost. (We called it the “gap of doom,” as in: “That byte fell through the gap of doom.”) I suspect if we had taken the time to fully understand the problem and reclassify it, we would have seen that it was intractable without a buffer and would have take that approach from the start instead of at the end.

Theory in the head saves time in the trenches.

-Neil