Philosophers' Dinner Problem

Illustration of the problem of philosophers' dinner.

The dinner philosophers problem or dinner philosophers problem (dining philosophers problem) is a classic science problem of computing proposed by Edsger Dijkstra in 1965 to represent the process synchronization problem in an operating system. It should be noted that the interpretation is based on Chinese thinkers, who ate with two chopsticks, where it is more logical that the diner who sits next to them is needed to be able to eat.

Problem statement

Five philosophers sit around a table and spend their lives eating and thinking. Each philosopher has a bowl of noodles and a fork to the left of his plate. Two forks are needed to eat the noodles and each philosopher can only take those to the left and right of him. If any philosopher picks up one fork and the other is busy, he will wait, fork in hand, until he can pick up the other fork, and then start eating.

If two adjacent philosophers try to pick up the same fork at once, a race condition occurs: they both compete to pick up the same fork, and one of them goes without food.

If all the philosophers take the fork to their right at the same time, then they will all be left waiting forever, because someone must release their missing fork. No one will because everyone is in the same situation (waiting for someone to put down their forks). Then the philosophers will starve. This deadlock is called a deadlock or deadlock.

The problem is to find an algorithm that allows philosophers to never starve.

Various possible solutions

• By cyclical shift

You start with a philosopher, who can eat if he wants, and then he passes his turn to the one on the right. Each philosopher can only eat on his turn. Problem: If the number of philosophers is very high, one can starve before his turn.

• Several shifts

Several shifts are established. To make it clearer, let's suppose that each philosopher who can eat (it's his turn) has a token that he then passes to the right. If, for example, there are 7 diners, we can put 3 tokens in alternate positions (two philosophers would remain between two of the tokens).

Fixed time shifts are established. For example, every 5 minutes the chips (and turns) are passed to the right.

Based on how long it usually takes philosophers to eat and get hungry again, the set turn time may make it a worse solution than the previous one. If the turn time is close to the average time it takes a philosopher to eat, this variant gives very good results. If, in addition, the mean time to eat is similar to the mean time to be hungry again, the solution is close to the optimum.

• Colas de forks

When a philosopher wants to eat, he gets in line for the two forks he needs. When a fork is free he takes it. When he takes the two forks, he eats and sets the forks free.

Viewed from the other side, each fork can only have two philosophers in the queue, always the same ones.

This creates the aforementioned problem that if everyone wants to eat at the same time and everyone starts taking the fork to their right, the system deadlocks.

• Resolution of conflicts in tails of forks

Every time a philosopher has a fork he waits for a random time to get the second fork. If the second fork is not free in that time, it drops the one it has and re-queues its two forks.

If a philosopher A drops a fork (because he has eaten or waited too long with fork in hand) but still wishes to eat, he re-queues for that fork. If the adjacent philosopher B is already in that fork tail (he's hungry) he takes it and if he doesn't go back to take it A.

It is important that the timeout is random or the system will hang.

• The dining room door

The philosophers are instructed to leave the table when they are not hungry and not return to it until they are hungry again (each philosopher always sits in the same chair). The goalkeeper's mission is to control the number of philosophers in the room, limiting their number to n-1, because if there are n-1 diners, surely at least one can eat with both forks.