The Dining Philosophers Problem
The problem refers to multiple philosophers (threads) seated at a circular table. On the table, there are 5 plates and 5 forks, so each philosopher has one fork to the left and one to the right. While sitting at the table, philosophers can perform two actions: eat or think. To eat, a philosopher needs two forks (which they can only use if they are not taken by their neighbors).
The solution must consider developing an algorithm to avoid a deadlock (a situation where each philosopher holds one fork and waits for the neighbor to release the other fork).
As a solution, we have the following approach: we will have N locks (considering we have N threads), and each philosopher will use two locks. To avoid deadlock, everything will work as follows:
- Each of the first N - 1 threads will first lock lock[i], then lock[i + 1], perform an action, release lock[i], and then release lock[i + 1].
- The N-th thread will first lock lock[0], then lock[N - 1] (in reverse compared to the rest of the threads), perform an action, release lock[0], and then release lock[N - 1].
Pseudocode:
Lock[] locks = new Lock[N];
philosopher(int id) {
while (true) {
if (id != N - 1) {
locks[id].lock();
locks[id + 1].lock();
// eat
locks[id].release();
locks[id + 1].release();
// think
} else {
locks[0].lock();
locks[N - 1].lock();
// eat
locks[0].release();
locks[N - 1].release();
// think
}
}
}