a. Describe the dining philosopher's problem and suggest any three ways to solve the problem without any starvation or deadlocks b. What are the necessary and sufficient conditions for a deadlock to take place? Describe each condition c. Describe a semaphore and the wait() and signal() methods associated with a semaphore d. How would you use a semaphore to achieve mutual exclusion?
a. Describe the dining philosopher's problem and suggest any three ways to solve the problem without any
starvation or deadlocks
b. What are the necessary and sufficient conditions for a deadlock to take place? Describe each condition
c. Describe a semaphore and the wait() and signal() methods associated with a semaphore
d. How would you use a semaphore to achieve mutual exclusion?
a)
Suppose that there is a bowl of noodles kept on a circular table and there are 5 people sitting around it. This means that there will be a total of 5 plates and 5 chopsticks. If any person wants to eat noodles they can only eat them by using both left and right chopsticks. So, while one person is eating, the neighbors to their immediate left and right will have to wait, think, and starve as well.
The Dining Philosophers Problem is used to design a scheduling technique such that no philosopher will starve.
Solution to the problem
One way to solve the problem is by using Semaphores.
A Semaphore is a tool used for concurrent processes that works by assigning an integer value. The two functions that are operated using semaphore are wait() and signal() .
Take a look at the solution:
void Philosopher
{
while(1)
{
wait(take_chopstick[x]);
wait(take_chopstick[(x + 1) % 5]) ;
// EATING THE NOODLE
signal(put_chopstick[x]);
signal(put_chopstick[(x + 1) % 5]) ;
// THINKING
}
}
Explanation:
The above code suggests that the wait() operation is first performed where take_chopstick[x] and take_chopstick[(x+1) % 5] are executed. This corresponds to the philosopher picking up both the left and the right chopsticks and then starting to eat while the others wait and think until their turn comes.
After eating, the signal() operation is performed where put_chopstick[x] and put_chopstick[(x+1) % 5] are executed. This means that the philosopher has eaten, after which the philosopher puts down the chopstick and starts to think again.
This is the solution to the problem, but it has some drawbacks as it will create a deadlock. For example, when all the philosophers pick up the left chopstick and then have to wait for the right one – this will create a deadlock situation.
To avoid this deadlock, some measures that could have been taken are:
There could be, at most, 4 people at the table.
The philosophers can alternatively eat and think. For example, if the first philosopher is eating, then the second should wait and think while the third eats, and so on.
Every philosopher must request each of their (shared) chopsticks from a waiter, who may refuse the request at first in order to avoid a deadlock. For convenience, we assume that all philosophers request their left chopstick first, then their right chopstick
Deadlock Avoidance:
- It is the simplest and most friendly method.
- It requires that each process declare the maximum number of resources of each type that it will need.
- The deadlock-avoidance algorithm dynamically checks the resource-allocation state to ensure the system can never be in a circular-wait condition.
- When a process requests a resource, the system must make sure that the allocation would leave the system in a safe state.
- It the system is in a safe state, then there would be no deadlock. However, if it is in an unsafe state, that there is a possibility (not certainty) of a deadlock.
- The avoidance approach requires that knowledge of all processes, all the resources available, the
- resources allocated presently and the future requests by the processes.
- For a single instance of a resource type we use the resource allocation graph.
- For multiple instance of a resource type, we use the banker’s algorithm.
- A major drawback of this method is that it is difficult to know at the beginning itself of the maximum resource required.
Step by step
Solved in 4 steps
