Describe your own example which may encounter deadlocks.
a. show that the four necessary conditions for deadlock indeed holds in this example.
b. state a simple way for avoiding deadlocks in this case.

Answer

In the philosopher meal problem, if five philosophers process concurrently, they all pick up the chopsticks on the left-hand side. Later, when any of them try to pick up the chopsticks on the right-hand side, they will find that the right chopsticks have been taken away and hold by another philosopher. If any philosopher does not put down the chopsticks in his hand at some time, then the phenomenon of circular waiting will occur.

The pseudo code is roughly as follows:

Semaphore chopstick [5]={1,1,1,1,1,};

pi(){

while(){

P(chopstick[i]);

P(chopstick[(i+1)%5]);

eat…

V(chopstick[i]);

V(chopstick[(i+1)%5]);

think…

}

}

This explanation meets the four conditions for deadlock:

1. Mutual exclusion: the use of chopsticks between any philosopher and the adjacent philosopher on the left and right are mutually exclusive.


2. No preemption: any philosopher cannot snatch the chopsticks already in the hands of neighboring philosopher for his own use, unless the neighboring philosopher actively puts it down.


3. Hold and wait: each philosopher holds a chopstick that the philosopher on his left wants and he is waiting for the chopstick hold by the philosopher on his right.


4. Circular wait: every philosopher is holding his own resources (not releasing them) and waiting for the others to release the resources they hold and at the mean time no new resources are provided.