GATE Overflow Test Series | Operating Systems | Test 1 | Question: 25

Question

Consider the following solution to the classical Dining Philosophers Problem using Semaphores, where $5$ philosophers in a dining table are trying to eat using $5$ chopsticks each one placed to the right and left of each philosopher.
semaphores chopstick $[0\dots 4]$ all initialized to $1.$

repeat
wait(chopstick[i+(i%2)]);
wait(chopstick[(i+1-(i%2)) mod 5]);
. . .
eat
. . .
signal(chopstick[i]);
signal(chopstick[(i+1) mod 5]);
. . .
think
. . .
until false;

Which of the following properties are satisfied by the above solution? (Mark all the appropriate choices)

• A. Starvation freedom
• B. Deadlock freedom
• C. Mutual Exclusion
• D. Progress

Comments

I feel mutual exclusion is not satisfied because suppose Philosopher 0 takes 2 chopsticks numbered 0 and 1.Now suppose philosopher 3 comes and takes 2 chopsticks numbered 4 and 3. Now both of them will eat in the critical section happily. So here 2 of them have entered CS at the same time, hence mutual exclusion violated?! IF any mistakes from my side please ACK.

Answer 1

Here, the odd numbered philosopher is picking the right side chopstick first and the even numbered philosopher is picking the left side chopstick first. In this way maximum $4$ philosophers can pick the chopstick at any time and this avoids the possibility of a deadlock as in the classical dining philosopher problem solution where all $5$ of them can pick the left side chopsticks or the right side chopsticks. Since there is no deadlock, there is progress as well.

Since wait is used on each chopstick, mutual exclusion is satisfied.

Starvation freedom is not guaranteed as any one of the philosopher can not get the chopstick for an infinite time (it can be picked by the neighboring philosopher.

Correct answer: B;C;D.

Comments

@Meet2698 Mutual exclusion is there as philiphors are able to take the both forks in all situations and u can think this as similar to counting semaphore where instead of 1 resource ,we were having many resources,same is here ,we are having 5 chopticks and each philosopher ,require 2 forks ,

---

Yep, you are right @Aayush_00, I had the same doubt :

Correctness properties it needs to satisfy are :

1. Mutual Exclusion Principle –
   No two Philosophers can have the two forks simultaneously.
2. Free from Deadlock –
   Each philosopher can get the chance to eat in a certain finite time.
3. Free from Starvation –When a few Philosophers are waiting then one gets a chance to eat in a while.
4. No strict Alternation.
5. Proper utilization of time.

https://www.geeksforgeeks.org/dining-philosophers-problem/

---

@Meet2698 Mutual Exclusion simply means, two different entities/processes(here, philosophers) can’t access a shared resource(here, chopsticks) at a same time. And here, this condition is satisfied, as a wait is performed before accessing any chopstick.

Two philosophers being able to eat together is not a violation of mutual exclusion, as the resources they used to do so are different from each other. Besides, two philosophers being able to eat together is the best possible utilization of resources in this problem with 5 philosophers.
The fact that we can have two philosophers eating together is valid, I read from here, for your reference : http://boron.physics.metu.edu.tr/ozdogan/OperatingSystems/week7/node10.html