International Institute of Professional Studies

Operating Systems
MTech 2k17 Sem VII

THE DINING
PHILOSOPHERS PROBLEM
PRESENTED BY -- Anushka Shastri

GUIDED BY -- Dr Kirti Mathur Ma’am

What is Dining
Philosophers Problem?

● The dining philosophers problem

is a classic synchronization
problem.
● It is used to evaluate situations
where there is a need of allocating
multiple resources to multiple
processes.
What is Dining
Philosophers Problem?

● Demonstrates a large class of

concurrency control problems.
● It was designed to illustrate challenges
of avoiding deadlock.
● It was originally formulated by Edsger
Dijkstra in 1965. Later, Tony Hoare
gave the problem its present
formulation.
Need of Dining
Philosopher Problem
● It is a simple representation of the
need to allocate several resources
among several processes.
● It represents a deadlock-free
system.
● It ensures a starvation-free
structure.
The Problem Statement

● Consider five philosophers who spend their

lives thinking and eating.
● The philosophers share a circular table
surrounded by five chairs, each belonging
to one philosopher.
● In the center of the table is a bowl of rice,
and the table is laid with five single
chopsticks.
The Problem Statement

● When a philosopher thinks, he does not

interact with her colleagues.
● From time to time, a philosopher gets
hungry.
● He tries to pick up the two chopsticks that
are closest to him, i.e. the chopsticks that
are between him and his left and right
neighbors.
The Problem Statement
● A philosopher may pick up only one
chopstick at a time.
● He cannot pick up a chopstick that is already
in the hand of a neighbor.
● When a hungry philosopher has both his
chopsticks at the same time, he eats without
releasing his chopsticks.
● When he is finished eating, he puts down both
of his chopsticks and starts thinking again.
Lets understand the problem with a code…...

● Let's use the given figure as a

reference to understand the
problem exactly.
● The five Philosophers are
represented as P0, P1, P2, P3, and
P4 and five chopsticks by C0, C1,
C2, C3, and C4.
Lets understand the problem with a code…...
Void Philosopher {

while(1) {

take_chopstick[i];

take_chopstick[(i+1) % 5] ;

... // EAT ...

put_chopstick[i];

put_chopstick[(i+1) % 5] ;

… // THINKING ..

}
Lets understand the problem with a code…...
● Suppose Philosopher P0 wants to eat, it will enter in Philosopher()
function, and execute take_chopstick[i] by doing this it holds C0
chopstick after that it execute take_chopstick[(i+1) % 5] by
doing this it holds C1 chopstick( since i =0, therefore (0 + 1) % 5
= 1)
● Similarly suppose now Philosopher P1 wants to eat, it will enter in
Philosopher() function, and execute take_chopstick(i) by doing
this it holds C1 chopstick after that it execute
take_chopstick[(i+1) % 5] by doing this it holds C2
chopstick( since i =1, therefore (1 + 1) % 5 = 2)
● But Practically Chopstick C1 is not available as it has already
been taken by philosopher P0, hence the above code generates
The solution of the Dining
Philosophers Problem
Semaphore: A semaphore S is an
● We use a semaphore to represent a chopstick integer variable, that apart from
initialization is accessed by only two
and this truly acts as a solution of the Dining
standard atomic operations - wait and
Philosophers Problem. signal.
● Wait and Signal operations will be used for the
Semaphore is simply a variable that is
solution of the Dining Philosophers Problem,
non-negative and shared between
for picking a chopstick wait operation can be threads. A semaphore is a signaling
executed while for releasing a chopstick signal mechanism, and a thread that is waiting
semaphore can be executed. on a semaphore can be signaled by
another thread. It uses two atomic
operations, 1)wait, and 2) signal for the
process synchronization.
Semaphores
The definition of wait() is as follows:
● All modifications to the integer value of the
semaphore in the wait() and signal() wait(S) {
operations must be executed indivisibly. while S <= 0
● That is, when one process modifies the ; // no-op
S--;
semaphore value, no other process can
}
simultaneously modify that same semaphore
value. The definition of signal() is as follows:
● In case of wait(S), the testing of the integer
value of S (S ≤ 0), as well as its possible signal(S) {
S++;
modification (S--), must be executed without
}
interruption.
The solution of the Dining Philosophers Problem

● The structure of the chopstick is an

array of a semaphore which is
represented as shown below -

semaphore chopstick[5]
● Initially, each element of the
semaphore C0, C1, C2, C3, and C4 are
initialized to 1 as the chopsticks are on
the table and not picked up by any of
the philosophers.
Solution of Dining Philosopher Problem

void Philosopher {

while(1) {

wait( take_chopstickC[i]);

wait( take_chopstickC[(i+1) % 5] ) ;

. . EATING THE NOODLE . . .

signal( put_chopstickC[i] );

Signal( put_chopstickC[(i+1) % 5]) ;

. . . THINKING

}
Solution of Dining Philosopher Problem

● Let value of i = 0( initial value ), Suppose Philosopher P0 wants to

eat, it will enter in Philosopher() function, and execute
wait( take_chopstickC[i] ).
By doing this it holds C0 chopstick and reduces semaphore C0 to 0.
After that it execute wait( take_chopstickC[(i+1) % 5] ).
By doing this it holds C1 chopstick( since i =0, therefore (0 + 1) %
5 = 1) and reduces semaphore C1 to 0.
Solution of Dining Philosopher Problem

● Similarly, suppose now Philosopher P1 wants to eat, it will enter in

Philosopher() function, and execute wait( take_chopstickC[i] ).
By doing this it will try to hold C1 chopstick but will not be able to do
that, since the value of semaphore C1 has already been set to 0 by
philosopher P0.
Therefore it will enter into an infinite loop because of which philosopher
P1 will not be able to pick chopstick C1.
Solution of Dining Philosopher Problem

● Whereas if Philosopher P2 wants to eat, it will enter in Philosopher() function, and

execute wait( take_chopstickC[i] ); by doing this it holds C2 chopstick and reduces
semaphore C2 to 0.
After that, it executes wait( take_chopstickC[(i+1) % 5] ); by doing this it holds C3
chopstick( since i =2, therefore (2 + 1) % 5 = 3) and reduces semaphore C3 to 0.
Hence the above code is providing a solution to the dining philosopher problem, A
philosopher can only eat if both immediate left and right chopsticks of the philosopher
are available else philosopher needs to wait. Also at one go two independent
philosophers can eat simultaneously (i.e., philosopher P0 and P2, P1 and P3 & P2 and
P4 can eat simultaneously as all are the independent processes and they are following
the above constraint of dining philosopher problem)
Drawbacks of Dining Philosopher Problem
● From the above solution of the dining philosopher
problem, we can figure out that no two
neighboring philosophers can eat at the same
point in time.
● The drawback of the above solution is that this
solution can lead to a deadlock condition.
● This situation happens if all the philosophers pick
their left chopstick at the same time.
● It will lead to the condition of deadlock and none
of the philosophers can eat.
● This will result in a condition of starvation.
Possible Solutions
To avoid deadlock, some of the solutions are as follows -

➔ Maximum number of philosophers on the table should not be more than four.
◆ in this case, chopstick C4 will be available for philosopher P3, so P3 will start eating and
after the finish of his eating procedure, he will put down his both the chopstick C3 and C4,
i.e. semaphore C3 and C4 will now be incremented to 1.
◆ Now philosopher P2 which was holding chopstick C2 will also have chopstick C3 available,
hence similarly, he will put down his chopstick after eating and enable other philosophers
to eat.
➔ A philosopher at an even position should pick the right chopstick and then the left chopstick
while a philosopher at an odd position should pick the left chopstick and then the right
chopstick.
Possible Solutions
➔ Only in case if both the chopsticks ( left and right ) are available at the same time, only then a
philosopher should be allowed to pick their chopsticks
➔ All the four starting philosophers ( P0, P1, P2, and P3) should pick the left chopstick and then
the right chopstick, whereas the last philosopher P4 should pick the right chopstick and then the
left chopstick.
➔ This will force P4 to hold his right chopstick first since the right chopstick of P4 is C0, which is
already held by philosopher P0 and its value is set to 0, i.e C0 is already 0, because of which P4
will get trapped into an infinite loop and chopstick C4 remains vacant.
➔ Hence philosopher P3 has both left C3 and right C4 chopstick available, therefore it will start
eating and will put down its both chopsticks once finishes and let others eat which removes the
problem of deadlock.
Conclusion
The design of the problem was to illustrate the challenges of avoiding deadlock, a deadlock
state of a system is a state in which no progress of system is possible. Consider a proposal
where each philosopher is instructed to behave as follows:

● The philosopher is instructed to think till the left fork is available, when it is available,
hold it.
● The philosopher is instructed to think till the right fork is available, when it is available,
hold it.
● The philosopher is instructed to eat when both forks are available.
● then, put the right fork down first
● then, put the left fork down next
● repeat from the beginning.
THANK
YOU