five dining philosophers problem

Problem statement

Five silent philosophers sit at a round table with bowls of spaghetti. Forks are placed between each pair of adjacent philosophers. Each philosopher must alternately think and eat. However, a philosopher can only eat spaghetti when he has both left and right forks. Each fork can be held by only one philosopher and so a philosopher can use the fork only if it is not being used by another philosopher. After he finishes eating, he needs to put down both forks so they become available to others.

Now suppose there are two types of dining philosophers. One type always picks up his left fork first and the other type always picks up his right fork first - call these a lefty and a righty. Each type executes consecutive “wait”s on their forks (left followed by right for lefties, and the other way around for righties), eats, then put down the forks in the reverse order of the waits (right followed by left for lefties, and the other way around for the righties).

Question

Explain why every seating arrangement of lefties and righties, with at least one of each, avoids deadlock.

Answer

Deadlock may occur with all lefties due to circular wait. If each picks up his left fork, then the right fork will be held by another philosoher who waits such that the fork will never be released This leads to a circular wait and deadlock. The same is true for all righties.

Assume the case with all lefties and one rightie. The philosopher to the left (L) of the rightie (R) picks up his left fork while the rightie attemps to pick up his right fork. If R fails to do this, R will wait with neither fork held. L is then free to pick up his right fork and continue.

If R succeeds in acquiring his right fork, then both L and R will then attempt to hold the same fork. One of them will succeed and continue. This means that aleast one philosepher will be able to progress. There is no circular wait and no deadlock. The same argument hold for more than one rightie. As long as there is diversity, then there is no deadlock.

本博客所有文章除特别声明外，均采用 CC BY-SA 3.0协议 。转载请注明出处！