edited by
6,380 views
21 votes
21 votes

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?

  1. Deadlock is possible in (i) and (ii).
  2. Deadlock is possible in (i).
  3. Starvation is possible in (i).
  4. Deadlock is not possible in (ii).
  5. Starvation is not possible in (ii)
edited by

5 Answers

Best answer
20 votes
20 votes
  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.
edited by
7 votes
7 votes

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

3 votes
3 votes
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.
1 votes
1 votes
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).
Answer:

Related questions