Can this pseudocode solve the dining philosopher problem with maximum parallelism? Here mutex is a binary semaphore initialized to 1. Forks are assumed to be numbered from 0 to (N-1). There are a total of N philosophers numbered from 0 to (N-1).
void philosopher(int i) // ith philosopher
{
while (true)
{
think();
down(&mutex); // acquire lock
take_fork(i); // take left fork
take_fork((i+1)%N); // take right fork
up(&mutex); // release the lock
eat();
down(&mutex); // acquire lock
put_fork(i);
put_fork((i+1)%N);
up(&mutex); // release the lock
}
}
This should solve the dining philosopher problem with maximum parallelism, because the lock is released after one philosopher has acquired both forks. But will it? And will there be any issue of liveliness? I am confused.
To answer your question I would like to provide a trace of events that seems to lead your philosophers into an undesired state.
Consider a system with N>2 philosophers Ph(0),...,Ph(N-1) and the following sequence of actions:
Ph(1).think();
Ph(0).think();
Ph(1).down(&mutex);
Ph(1).take_fork(1);
Ph(1).take_fork(2);
Ph(1).up(&mutex);
Ph(0).down(&mutex);
Ph(0).take_fork(0);
Ph(0).take_fork(1);
Recall that fork(1) is already acquired by Ph(1). Now depending on the semantics of take_fork() different behavior can occur.
If take_fork() fails immediately if the fork cannot be acquired, then fork(0) would never be released.
If take_fork() hangs until the resource is released, then the mutex would never be released and none of the other philosophers would be able to make progress therefore only one philosopher will be eating at a time.