Suppose that we modify the Dining Philosophers problem as follows: The host of t

Question

Suppose that we modify the Dining Philosophers problem as follows: The host of the dinner finds that with n guests they have n+1 chopsticks. To be fair, the host puts one chopstick between each pair of philosophers, and puts one in the center of the table.

Propose a deadlock-free, starvation-free solution to this version of the Dining Philosophers problem that also has bounded waiting. There will be an upper limit to the amount of time (or the number of eating cycles) that any hungry philosopher must wait to eat.

Explain why your solution is deadlock free, starvation free, and has bounded waiting.

Explanation / Answer

Deadlock free solution to the dining philosophers problem:

1. number all forks from 1-5 from left to right (Pick any person then left to right)
2. people can grab only the lowest numbered fork first
3. Name persons from a-e from right to left (Pick any person then left to right)
4. Then starting from person e, fork 1 and 2 are available for person e . So he/she picks fork 1 since its the          lowestnumber.
5. Doing the same with other people and forks. But when we get to person A, he cannot pick fork 1 because      person e already picked that one. He also cannot pick fork 5 since he hasn't picked the smallest fork, which was fork 1, yet. So, peson B picks fork 5 now he has 2 forks: 4 and 5. So that person can eat lunch.

for most example of this deadlock solution is

Five philosophers are sitting around a circular table. On the table is a bowl of noodles. Between each pair of philosophers is a chopstick laid out on the table such that the first philosopher's right chopstick is the left chopstick of the second philosopher, whose right chopstick is the left chopstick of the third philosopher and so forth. Hence there are five chopsticks available in total.

Each philosopher thinks for a while, then gets hungry and decides to eat. In order to eat, a philosopher has to have a pair of chopsticks. He picks up the chopsticks on either side of him to grab some noodles from the bowl and then eats. If one of the chopsticks is already being used, the philosopher must wait for it to become available.

In a concurrent system, each philosopher is implemented as a thread and each chopstick is a shared resource.

The intuitive approach to solving this problem is to have each philosopher first pick up his left chopstick then his right. However, this will lead to deadlock as all four of the necessary and sufficient conditions for deadlock come into play: blocking shared resources (chopsticks), no pre-emption (one philosopher cannot ask his adjacents to drop their chopsticks), holding while acquiring (a philosopher holds his left chopstick before trying to pick up his right) and circular waiting (each philosopher shares chopsticks).

Clearly our naive scheme doesn't quite work as planned. However, as all conditions for deadlock are both necessary and sufficient, we should be able to prevent the deadlock by breaking any one of the conditions

An obvious way around this is that philosophers who can't get both chopsticks should put them down, go back to thinking and try again later. This is trying to break the third deadlock property above: 'holding while acquiring'. However, if the philosophers are unlucky and keep doing this all in synchrony, none of them will actually get to eat! Each will drop a chopstick only to try and grab it once more. This solution breaks the problem of deadlock but in doing so, we have introduced another potential problem - that of livelock. The philosophers will not grind to a halt but instead can just go round in circles trying to decide who should have the chopsticks but never getting anywhere. The philosophers won't eat and will starve (quite literally!). This solution isn't much good either.

There are several possible viable solutions that solve both the issue of deadlock and ensure liveness, four of which are presented here:

    Order the chopsticks, so that the philosopher has to pick up chopstick N, then chopstick N+1. This means that one of the philosophers will pick up his right chopstick first, while all of the others are picking up the left chopstick first. This is the same as having odd numbered philosophers pick up their chopsticks left/right, and even numbered philosophers pick up theirs right/left. This solution relies on breaking the circular wait. Also, every philosopher will get to eat at some point.

    A philosopher who wants to eat first picks up the sole salt shaker on the table, then picks up his chopsticks, eats and then puts the salt shaker back. This solution while viable isn't great, as it means that only one philosopher can eat at any one time. This solution breaks the 'holding while acquiring' deadlock condition and if we further stipulate that the philosophers agree to go around the table and pick up the salt shaker in turn, this solution is also fair and ensures no philosopher starves.
    Each philosopher flips a coin. Heads, he picks up the right chopstick first, tails, the left. If the second chopstick is busy, he puts down the first and tries again. With probability 1, he will eventually eat. Again, this solution relies on defeating circular waiting whenever possible and then resorts to breaking 'acquiring while holding' as assurance for the case when two adjacent philosophers' coins both come up the same. Again, this solution is fair and ensures all philosophers can eat eventually.
    The chef sees the philosopher's predicament, scorns the philosophers for letting his fine meal of noodles go cold and agrees with the philosophers that he'll dictate who should eat and when to prevent any confusion.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.