[Solved]: Provide some help regarding the "Dining Philosophers Problem"?

Problem Detail: 

I have an assignment based on operating systems and the question is divided into two sub-questions.

The first is: Prove any seating arrangement of lefties and righties, with at least one of each avoiding deadlock.

The second: Prove any seating arrangement of lefties and righties with at least one of each avoiding starvation.

I understand the concept behind this problem and that I can use semaphores, or monitors etc. but the resources I have found online mainly explain in coding, but I need help understanding which is the best way to answer this question in theory by choosing one of the ways to prevent deadlock and starvation.

Asked By : Osiris93

Answered By : Ariel

Righties: will never try to acquire the left fork before they have the right one.

Lefties: will never try to acquire the right fork before they have the left one.

Deadlock: Assume that you reached deadlock, this means that none of the philosophers can eat (so each philosopher holds at most one fork, and cannot pick up the other one). Sine you have both righties and lefties, there exists two adjacent philosophers with opposite orientation, lets denote them by $p_r,p_l$. Notice that $p_r,p_l$ cannot pick up any forks, if one of them holds the fork in between, $f_{p_r,p_l}$ , then it means he already got the other fork, since $f_{p_r,p_l}$ lies right to the leftie $p_l$ and left to the rightie $p_r$. So $f_{p_r,p_l}$ is available, and thus if $p_r$ or $p_l$ can pick up the other fork, they can pick up $f_{p_r,p_l}$ and eat, contradicting deadlock. $p_l$ cannot pick up the fork to his left, hence (because the system is in deadlock) the philosopher left to $p_l$ is a rightie, and already picked up the fork to his right (or to $p_l$'s left). Let us denote the $k'th$ neighbor to $p_l$ from the left by $p_l^k$, so we have shown $p_l^1$ is a rightie and owns the fork to his right. $p_l^2$ (left neighbor of $p_l^1$) must also be a rightie and own his right fork, otherwise either he or $p_l^1$ can eat. It is easy to see (by induction) that for all $k$, $p_l^k$ is a rightie owning his right hand fork. however $p_r=p_l^{n-1}$ (where $n$ is the number of philosophers), so $p_r$ is a rightie owning his right fork, contradicting the fact that $p_r,p_l$ do not own any forks.

This is illustrated in the following figure. Red squares are forks, arrow from a philosopher to a fork indicates that he is waiting to use this fork (not ownership). All philosophers left of $p_l$ are righties waiting to use their left fork (already owning their right one). This goes on until you reach $p_r$, who you know is waiting for his right fork and not the left one (which leads to contradiction).

Starvation: Starvation means that there exists a philosopher which is stuck waiting to eat. Suppose that some right hand philosopher $p_r$ is stuck waiting to pick up his right fork (the proof is very similar in case he's waiting for his left). Let us denote by $p_r^k$ the k'th neighbor of $p_r$ to the right. We know that the protocol is deadlock free, so there exists minimal $m$ such that $p_r^m$ is eating. We can see by induction that all $p_r^{j}$ for $j<m$ are lefties holding their left fork. This is clear for $p_r^1$ (otherwise $p_r^1$ would be either eating or leaving the fork right of $p_r$ available, in any case $p_r$ will eventually be able to pick up the fork to his right). Suppose $j,j+1<m$ and $p_r^j$ is a leftie holding his left fork. Since both $p_r^j,p_r^{j+1}$ are not eating (by minimality of $m$), $p_r^{j+1}$ is a leftie holding his left fork. When $p_r^m$ is done eating, $p_r^{m-1}$ will be able to pick his right fork and eat, when he's done $p_r^{m-2}$ will be able to pick his right fork and eat,... Finally, $p_r^1$ will be done eating, allowing $p_r$ to pick his right fork, contradicting the fact that he is stuck.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/45763