In the Dining Philosophers problem, when each philosopher would grab their leftm
ID: 3758272 • Letter: I
Question
In the Dining Philosophers problem, when each philosopher would grab their leftmost chopstick, and then their rightmost chopstick, and then start eating. If the chopsticks were in an array, then philosopher I would grab chopsticks i and (i+1)%N (N is the number of philosophers)
How many semaphores would you need to implement this?
Show how the wait and signal operations on the semaphores would be placed on one philosopher’s thread to ensure the philosopher has sole access to their chopsticks.
One (not very good) way of fixing the potential deadlock issue is to instead of placing a semaphore around each chopstick, we place it around the rice. This way, only one philosopher can be eating at a time (and there is no need for competition over chopsticks). Show what semaphores you’d need now, and how they would impact the wait and signal operations of one philosopher.
I said above that this was a “not very good” solution to the problem. Do you agree? Why or why not?
Explanation / Answer
Solution:
For this problem the number of semaphores must be as many as the number of chopsticks.
Iterate
waiting(chopstick[j]);
waiting(chopstick[(j+1) mod n]);
Eat
signal_after_eating(chopstick[j]);
signal_after_eating(chopstick[(j+1) mod n]);
Think
until false;
The philosophers will wait for the chopsticks to eat and the philosophers after eating will signal using their semaphore values and go to think. After the signal the waiting philosophers will get the chopsticks to eat. In this way a dead lock can be avoided
Yes, the above solution is not good because, if there are 5 philosophers and 5 chopsticks then at least 2 philosophers have a chance of eating with 4 chopsticks and one chopstick will be left over and assuming the other 3 are thinking, but the solution of restricting only philosopher to eat is not a proper way.