TIFR CSE 2011 | Part B | Question: 26

Question

Consider the following two scenarios in the dining philosophers problem:

1. First a philosopher has to enter a room with the table that restricts the number of philosophers to four.
2. There is no restriction on the number of philosophers entering the room.

Which of the following is true?

• A. Deadlock is possible in (i) and (ii).
• B. Deadlock is possible in (i).
• C. Starvation is possible in (i).
• D. Deadlock is not possible in (ii).
• E. Starvation is not possible in (ii)

Comments

starvation is possible in i

---

animation https://www.youtube.com/watch?v=XjlFoND00oY

Answer 1

1. is a solution to Dining Philosophers problem mentioned in Galvin. Of course this assumes that the number of forks is $5$ and the number of philosophers is $4$. This guarantees no deadlock, but starvation is possible as here a philosopher who finishes his meal can again get access to the forks whereas some philosopher may not get fork ever leading to his starvation. So, option (C) is TRUE.
    
2. is the Dining Philosophers problem with no restriction on the number of philosophers which can cause deadlock and deadlock implies starvation. So, options (D) and (E) are FALSE.

Comments

@Arjun sir, I have a query... In the problem, we are assuming that the number of chopstics is 5. Is the number of chopsticks to be 5 a valid assumption all the time? 

---

Any idea about this?

 

@Arjun sir, I have a query... In the problem, we are assuming that the number of chopstics is 5. Is the number of chopsticks to be 5 a valid assumption all the time? 

@ankitgupta.1729

 

---

I am not satisfied with the explanation in (i). Can someone come up with other answers please?

Answer 2

I'd recommend everyone to watch the NPTEL video on it, and not other substandard YouTube videos.

---

The dining philosophers problem is by default characterised on five philosophers and five forks (or chopsticks)

Some of the deadlock free solutions:

1. Restrict the number of philosophers to 4, without changing anything else (forks remain 5)
    
2. Allow a philosopher to pick up a fork if and only if both the required forks are available.
    
3. Number the philosophers from 1 to 5. Odd numbered philosophers pick their left fork first, and then the right fork. Even numbered philosophers pick their right fork first, then the left fork.

---

Since restricting the number of philosophers to 4 is a deadlock free solution, Options A and B are incorrect.

By the same logic, increasing the number of philosophers would make deadlock more likely. (Imagine $2^{50}$ philosophers with just 5 forks). So $(ii)$ is vulnerable to deadlock, and hence, starvation too. Option D and E are incorrect.

Starvation is definitely possible in $(i)$ if a philosopher gets hungry more often and keeps picking up both the forks again and again.

 

Option C

Comments

@JashanArora Great Explanation Bro just cleared it short and sweet

---

@Arjun sir just see this once for this problem this explanation should be best answer   go through this once

Answer 3

There deadlock may possible or may not possible but it is sure that Starvation possible in case of (i)

option C is definite  from 1st case hence it is True only.

Comments

Hello Bikram

'Possibility' word  itself contains 'may or may not' implicitly.

and i think when there is one such arrangement that cause deadlock then we say Deadlock is possible.So according to you in case one deadlock is possible , please tell me how?

and in first case 'starvation' is a possibility for an arrangement like when two philosophers are fast enough that they are the one who are eventually always eating. But i don't think starvation is definite case for part one.

please tell me if i'm getting something wrong.

Answer 4

First of all, In Dining Philosopher two things are definitely going to happen:

1. Starvation, as one philosopher always has to wait for every other philosophers to finish.

2. No deadlock, since resource/s of the waiting philosopher is/are always available.

Above Point 2 eliminates every probability of a deadlock in Dining Philosopher problem so option a,b,e are out except d. Examining closely Option d, we find that the number of philosophers keep on increasing but the rate at which philosopher is done with its job leads to a deadlock.

Therefore, option c is the answer, with absolute starvation in (i).

Comments

The idea is to capture the concept of multiple processes competing for limited resources. How can you assume "No dearth  of resources" ?

---

i think it will be the case when there would be five philosophers then condition of deadlock arrive for sure correct if i am wrong

---

bikram sir will we assume 5 forks for the 4 philosophers as well