The Dining Philosophers Problem

in this lecture we'll be discussing about another classic problem of synchronization which is known as the dining philosophers problem so first of all we'll be trying to understand what is the standing philosopher's problem and then we'll be seeing if we can solve this using semaphores all right so first let's see what is this dining philosopher's problem so in this dining philosopher's problem what we have is we have a round dining table in which we have let's say five philosophers who are seated around the table like this so the philosophers here they can be in two

states which is the thinking state and the eating state so the philosophers here they spend their whole life either thinking or eating so when the philosophers are thinking they don't interact with their colleagues here they just mind their own business and they think and when they are hungry they will try to eat this rice or noodles that are present in the plate that is placed before them now the thing is when the philosopher wants to eat the food that is placed in front of them they need to make use of this forks or the chopsticks

that are there that are placed adjacent to them so when a philosopher wants to eat he needs to make use of two forks or two chopsticks that are placed here they cannot eat with just one but they need two of them so when a philosopher gets hungry he will take up the two forks or chopsticks that are adjacent to him at his right and left and then he can start eating so when he starts eating nobody can disturb him or nobody can take the fork away from him and then when he finishes eating he will

be placing the forks or chopsticks back at their places so what is the problem here so if you look at this diagram carefully we can see that the chopsticks or the forks are limited there are five philosophers and how many folks are there one two three four five there are only five folks and i told you that when a philosopher wants to eat he needs to make use of two forks or two chopsticks so clearly we see that it is limited like for example when philosopher 1 will want to eat he will make use of

this and this 4 and at the same time if philosopher 2 gets hungry this philosopher 2 needs to make use of this fork and this fork but we see that this fork is being used by philosopher 1 so he will not be able to eat when philosopher 1 is using the for that is adjacent to him so we have to make sure that no two philosophers that are adjacent to each other try to eat at the same time so if they try to eat at the same time we are going to have a problem so

as i told you the philosophers can be in two states the thinking state or the eating state so when a philosopher is thinking he does not interact with his colleagues he just minds his own business and he thinks and he does not disturb anyone and now when he eats what happens when a philosopher gets hungry he tries to pick up the two forks that are closest to him left and right a philosopher may pick up only one fork at a time so this is also an important thing he needs two forks for eating but also

he cannot pick up both the forks at the same time he will have to pick up one fork and then after that he'll have to pick up the other fork so that is also an important thing that we need to keep in mind in this problem and also one cannot pick up a fork that is already in the hand of a neighbor so that also i've already shown here when a fork is being used by one of the philosopher no other philosophers can use that particular fork so i told you like when philosopher 1 is

eating he'll be making use of this fork and this fork which are at his right and left so at the same time if philosopher 2 tries to eat he also needs to make use of this fork and this form but this one is held by philosopher 1 so 2 will not be able to eat because he will not be able to get hold of this when one is eating so that is what we mean here and then when a hungry philosopher has both his forks at the same time he eats without releasing his forks when

he has finished eating he puts down both of his forks and starts thinking again so when a hungry philosopher gets hold of both the folks he will be eating and after he completes eating he will be placing the forks back where they were and then he will start thinking again so this is the scenario that we have in a dining philosopher's problem so what is the actual problem here i have already told you the problem is that since the forks are limited no two adjacent philosophers should be allowed to eat at the same time so

no two philosophers should try to access the same fork at the same time so that is the problem that we have here okay so now you may be thinking why are we discussing about this dining philosopher problem why are we creating a story like this and why are we trying to solve this problem so if you think about it this is actually a problem of operating system which deals with resource allocation so here all these philosophers they represent processes and the forks or the chopsticks that are placed here they represent resources that has to be

shared between processes so we see that we have limited resources and they have to be shared between processes in a synchronized manner without violating any rules so there may be resources that can be used by only one process at a time so if other processors try to access the same resource at the same time then we will be having problems in the operating system so that is why we are discussing about this dining philosopher's problem it is actually a problem of resource allocation and how the resources are being utilized when they have to be shared

among processes all right so now we have understood the problem statement of this dining philosophy problem and now we will be seeing how can we solve this using semaphores so one simple solution is to represent each fork or chopstick with a semaphore so we know that a chopstick or a fork should be used by only one philosopher at a time and when one philosopher is holding it no other philosopher should be allowed to take it away from him and it should not allow to access that same fork at the same time so we can do

that with the help of semaphores so a philosopher tries to grab a fork or chopstick by executing a weight operation on that semaphore so now what we'll be doing we'll be representing each of these forks or chopsticks with the help of a semaphore so we already know the features of semaphore and how they work so when a philosopher wants to grab a fork or chopstick he will be executing a weight operation on the semaphore or the chopstick so we know what happens when a weight operation is executed on a semaphore so when a weight is

executed it implies that that particular process wants to use at semaphore and it wants to get hold of it and when it gets hold of it no other processes will be allowed to use that semaphore so similarly we'll be applying this on the chopsticks or the forks that we have here so the philosopher will execute a weight operation on the chopstick when he wants to use it and then he releases his fork or chopstick by executing the signal operation on the appropriate semaphores so after the philosopher finished eating he will have to put back the

chopsticks or the forks at their places so at that time how will he do he will be doing so by executing the signal operation on the chopstick order fork because we are assuming that they are semaphores so when a signal operation is executed what happens we have already studied that in sum of course signal operation means we are releasing it so a philosopher will be releasing his fork or chopstick by executing the signal operation so how will be implementing this is we are having five chopsticks or five forks we have seen that in the diagram

so each of these chopsticks will be represented as a semaphore so what we are doing is we are having an array of chopsticks with the data type semaphore so the data type is semaphore and we have five number of chopsticks so we are using an array so what we mean by this chopstick five is that we are having an array of five elements so we'll be having chopstick 1 chopstick 2 chopstick 3 chopstick 4 and chopstick 5. so these are the 5 chopsticks we have and they are all declared as semaphores and here all the

elements of the chopsticks are initialized to 1. so here the semaphore that we are going to use is a binary semaphore not a counting semaphore but a binary semaphore and we know that in binary sum of four it can take two values either one or zero so don't confuse this with the counting semaphore here chopstick five actually means it's an array of chopsticks that we are having chopstick one two three four and five and each of these chopsticks can have two values either zero or one so initially all the elements of the chopsticks are initialized

to one so in a binary semaphore when it is initialized to one means it is free it can be used by the processes that wants to use it and if the value is zero that means it is currently being held by some processes it is not free so that is what we mean here so all the chopsticks will be initialized to 1 initially all right so this is how we are going to make use of the semaphores to solve this problem so now we'll be seeing the structure of the philosopher that means we'll be seeing

how the code is written in order to accomplish this so here is the code this is a structure of any philosopher i here what will happen when a philosopher wants to eat his food that means when he is hungry and when he wants to eat what is the first thing that he need to do he need to get hold of the two chopsticks that are adjacent to him so he need to get the chopstick at his left and right how will he do that so as i told you we are going to assume that these

chopsticks are semaphores so he will have to execute a weight operation on two forks or chopsticks that are adjacent to him so for philosopher i he need to execute a weight operation on chopstick number i and then also on the chopstick i plus 1 modulo 5. so why we are making use of this mode 5 is because as i told you the philosopher will need to access the two folks that are adjacent to him so let's say that we are talking about philosopher 1 so he'll need to access fort number one and fork number two

so chopstick i will mean chopstick or fork number one and chopstick i plus one will mean chopstick number two so this calculation will be going on but think of the scenario when we reach the fifth philosopher so the fifth philosopher will need to make use of which chopstick he will make use of chopstick number five so if we just write here i plus one then what happens five plus one will give us six which means chopstick number six but there is no chopstick number six so after the chopstick number five it has to make use

of chopstick number one again it is placed in a circular fashion so it goes like one two three four five again one two three four five so philosopher number five will need to make use of chopstick five and chopstick one so that is why we are making use of this mode five here so for example when we reach the fifth chopstick what will happen here it will be chopstick number five i is equal to five and here we will have 5 plus 1 equal to 6 and 6 modulo 5 will give us 1 so we

will get chopstick 5 and chopstick 1. so that is why this calculation is done here so this is just a pseudo code when you will be writing the real code for this you have to carefully design this one okay so what basically it means is that the philosopher needs to execute weight operation on the two adjacent chopsticks that are placed near him okay once he execute this weight operations if these chopsticks are available he will be getting hold of them one by one and once he has hold of both of them then he can begin

eating so he will be doing the eating operation here and after eating he has to place the chopsticks back where they were so that other philosophers can make use of those chopsticks so what will he do he'll have to use the signal operation on the chopsticks so the same chopsticks that he used here he will be executing the signal operations for those chopsticks so signal of chopstick i and signal of chopstick i plus 1 mod 5 so that means he has released the chopsticks and then he will start thinking again so here we see that

when philosopher i is making use of the two adjacent chopsticks if the philosopher next to him or the philosopher adjacent to him tries to also eat at the same time he will also try to execute weight on one of these chopsticks and at that time he will not be able to get it because it is currently being held by this philosopher i so we see that two philosophers adjacent to each other will not be able to eat at the same time and they will not get the same chopstick at the same time so using sum

of four we have solve that problem okay so now we have found the solution to that problem but just by doing this have we solved all the problems let's see so here although the solution guarantees that no two neighbors are eating simultaneously it could still create a deadlock so we have proved that the solution guarantees that no two neighbors are eating simultaneously we have already explained that but this could still create a deadlock and how is that suppose that all five philosophers become hungry simultaneously and each grab their left chopstick all the elements of chopstick

will now be equal to zero when each philosopher tries to grab his right chopstick he will be delayed forever so think of a scenario when all the philosophers get hungry at the same time so what will they do they will simultaneously grab their left chopsticks so let's say that all of them have grabbed their left chopsticks now what will happen all the elements of chopsticks will be now equal to zero so whenever a philosopher will grab his chopstick he will execute a weight operation on that chopstick so when he executes a weight operation the chopsticks

value which is a semaphore will be changed from one to zero initially they were all one they will be changed to zero which means that it is now being held by a particular philosopher so now when each philosopher tries to grab his right chopstick he will be delayed forever so let's look at the diagram and understand this so here the scenario that we are talking about is all the philosophers get hungry at the same time and what happens let's say that all of them will grab their left chopsticks at the same time so we already

explained that they cannot pick up both the forks at the same time they have to pick up one and then the other so let's say that all of them picked up the left chopsticks that were at their left so philosopher 1 will pick up his left chopstick which is this one two will pick up his left chopstick which is this one three will pick up this four will pick up this and five will pick up this now if you see all the chopsticks are picked up by one of the philosophers now let's say one is

trying to eat so what will he do he have already got one of the chopstick now he needs a second chopstick to start eating so which is the second chopstick it is this one but can he get it no because five is holding it similarly two has got hold of this chopstick which is at his left now for starting to eat he also needs the chopstick that is at his right which is this one but it is being held by one it is not able to eat it similarly three also will not be able to

get the right one because it is held by two four also will not be able to get this because it is held by three and five also will not be able to get because it is held by four so according to this problem when a philosopher has one of the chopstick he also needs the other one and he will keep waiting for getting the other one to start eating but you see here that each of them are waiting for each other and nobody is going to release it because all of them wants to eat and

they all have one chopstick each so each of them they will be waiting for each other and they will keep waiting here and nobody is going to release it so at this situation we say that we have reached a deadlock so this scenario is known as a death lock so this kind of same situation can even happen with resources that are shared among processes in our operating system so this is something that we have to avoid so that is what we have just said here so that is the problem that we are going to face

here we have solved one problem which is no two philosophers adjacent to each other should start eating at the same time we have solved that using the semaphores here but still this problem persists which could lead to a deadlock so now we have to find if there are any ways that we can propose in which we can avoid this debt lock so let's see if there are any remedies that we can follow in order to avoid this debt lock so here we'll be discussing some of the possible remedies to avoid the deadlock so the first

one is allow at most four philosophers to be sitting simultaneously at the table so here instead of allowing five of them to sit we will be allowing only four of them to sit simultaneously at the table so the number of folks will remain the same but the philosophers will only be 4 here so what will happen even if all of them get hungry at the same time and pick up let's say the left forks what will happen philosopher 1 will pick up this 2 will pick up this 3 will pick up this and 4 will

pick up this one so we assume there is no five now so we see that one fork is still free over here so what will happen philosopher one will pick this up and he will start eating and then after he finishes he'll keep it down and when he keeps it down two will get hold of this and he will also start eating and after he finishes he'll keep it down and three will get his chance and four will also get his chance so we see that if we avoid one of them then we can avoid

the deadlock situation so that is one possible remedy that we can have to avoid the deadlock then the second remedy is allow a philosopher to pick up his chopsticks only if both chopsticks are available to do this he must pick them up in a critical section so here we saw that in the first scenario when all of them got hungry at the same time they just picked up the fork that was available and did not see if the other fork is available or not so instead of doing that we will allow the philosophers to pick

up their chopsticks only after making sure that both the chopsticks that they need are available so if one wants to eat he will make sure that both this and this chopsticks are available and then only he will pick up one by one so that is another solution that we can have in order to avoid this deadlock and then the final solution that we have is use an asymmetric solution that is an odd philosopher picks up first his left chopstick and then his right chopstick whereas an even philosopher picks up his right chopstick and then his

left chopstick so this is an asymmetric solution that is proposed in which it says that the odd philosophers or philosophers means here we have numbered the philosophers from one to five so the odd numbers here one three and five these are the odd philosophers and the odd philosophers should pick up first their left chopstick and then they write chopstick so that order should be followed and then if it is an even philosopher he should first pick up his right chopstick and then his left chopstick so by doing this what will happen so we saw that

in the first scenario all of them when they were hungry at the same time they all picked up their left chopsticks and all of them ended up waiting for each other so instead of doing that we will allow the odd philosophers to pick up their left chopstick first and then they will be picking up the right if it is available and for the even philosophers they will be first picking up the right chopstick and then the left chopstick so by doing this we can ensure that that locks are prevented so these are some of the

possible remedies to avoid the deadlock in a dining philosopher's problem even by using the semaphores so we saw that just by using semaphores we did not guarantee avoiding deadlocks but we have to make this small changes in order to avoid the deadlock in this situation we solved one of the problem using sum of fours but in order to avoid deadlocks we have to follow these remedies as well so this is another classic problem of synchronization in operating system so that is all about the dining philosopher's problem i hope this was clear to you thank you

for watching and see you in the next one [Music] you