Deadlock 3: Dining Philosophers

this video is about a classic problem in computer science known as the dining philosophers problem it's a fun little problem that teaches a bit about the concepts of deadlock and starvation quite literally because the concept is that we have a table and around it are seated five philosophers now a philosopher's life is spent alternating between periods of contemplation and periods of eating they need sustenance every once in a while so in front of each of these philosophers is a plate and in the center of the table they get an infinite supply of spaghetti which I'll represent with these squiggly lines unfortunately there are only five Forks at this table now the conceit of this problem is that philosopher's requires two forks at the same time in order to eat spaghetti some have argued that this problem makes more sense if you give them chopsticks rather than Forks but the classic formulation uses Forks and that's what we'll use so philosophers think for a while and then they grab Forks and eat however each Fork can only be used by one philosopher at a time that means we have mutual exclusion additionally we don't allow philosophers to take Forks from other philosophers therefore we have no preemption lastly if a philosopher grabs one fork but the other Fork is not available then that philosopher will keep holding on to the first fork until the second one becomes available that means we have a hold and wait condition all in all this means we have the potential for deadlock in fact we're going to look at some incorrect code that leads to deadlock or at least has the potential to lead to deadlock in this problem that code looks like this so in this code we have an array of phors named Fork there's one semaphore for each fork around the table each value is initially one indicating that only one person can use a fork at a time and the indices of the forks in this array correspond to the indices of the forks around the table in this diagram now we represent each philosopher with its own process so here is a function that is launched in the main function using this parallel began statement and we launch five philosopher threads with different ID numbers so we have philosopher 0 1 2 3 & 4 and these correspond to the little subscript numbers of these philosophers in the diagram there so what does it philosopher do well this loop goes on forever and the philosopher thanks for a while and there's no telling how long this will take and then when it's done thinking it grabs one fork then the other fork I'll go into this more detail in a moment when it has both Forks it eats and then it releases both Forks so some way means that the semaphore if that particular index is decremented so the philosopher is claiming that specific fork now the fork that is claimed is defined in terms of I so the philosophers are numbered 0 through 4 and so philosophers 0 is going to claim first fork 0 and then fork 0 plus 1 mod 5 so mod 5 is the remainder via division by 5 this is often represented in C based languages using the % so for philosophers 0 we need Forks 0 and 1 and if we look at the diagram that's what we see here philosopher 0 has fork 0 on one side and fork 1 on the other similarly philosopher one would need fork 1 and fork 1 plus 1 mod 5 which is 2 in fact the only reason for the mod 5 to be in there is because a philosopher for so if Lhasa for for will claim fork for and then also for plus 1 mod 5 which equals 0 because the remainder of 5 divided by 5 is 0 so this modulus gives us a nice way of representing the fact that the table is circular so essentially all this code is saying is that after thinking for a while if philosopher grabs the fork on the right then the fork on the left then eats and then puts the forks back one by one how can this lead to deadlock well let's draw a resource allocation diagram to see in fact if we simply keep these philosophers as circles and then put each of these Forks in a little box then we can draw the diagram itself around this table so because each fork is a semaphore with an initial value of 1 there is only one dot inside each of these fork resources and so let's say that we have these 5 philosophers executing the same time and remember that they always grab the fork on their right first in other words they grab the fork that has the same subscript number so philosopher 0 grabs and successfully claims Forks 0 now the next thing this philosopher what attempt to do is grab fork 1 let's say that before that happens philosopher 1 grabs that fork and thus claims that resource at the same time or close enough for 2 as claimed by philosopher 2 fork 3 is claimed by philosopher 3 and fork for is claimed by philosopher 4 so every philosopher has picked up one fork now there are no Forks left to claim so when philosopher zero attempts to get fork won we draw the arrow from the process to the fork to indicate that this resource has been requested but is not claimed similarly philosopher one attempts to claim for - or requests it lost for two requests for three plus for three requests for four and philosopher four requests fork 4 plus 1 mod 5 which is zero and now we have a cycle in this directed graph hence we have deadlock so the solution I showed you is no good how can we fix it so recall that even if you have all of the three conditions that make deadlock possible it only occurs if you have a circular wait condition so there is an easy way to reorder the fork requests that prevents a circular weight from occurring so I'm going to cross out this incorrect part and we're going to fix this solution with a few simple changes an easy way to make sure that a circular wait condition never arises is to have a global ordering of resources so what this means is that any time that any process requests a resource or rather a group of resources it has to request them in the same order that any other process would the problem with this current solution is that process 0 through 3 requests the lower numbered fork first process 0 requests 0 & 1 process one request 1 & 2 and so on but process four requests for for first and then 4 plus 1 mod 5 which is 0 that means that the order of fork requests here differs from the order being used by all other philosophers a simple way to change this is to replace this internal I and this I plus 1 mod 5 with the following so in the case of the first fork being claimed instead of claiming fork I we claim the minimum of I and I plus 1 mod 5 so if we are philosopher 0 then we are looking for the minimum between 0 & 1 so we're still getting fork 0 if we're philosopher 1 we're looking at 1 & 2 plus 4 2 looks at Forks 2 & 3 & 3 looks at Forks 3 & 4 but philosopher 4 looks at Forks 4 & 0 the minimum of those two is zero so that philosopher will attempt to claim 4 zero before fork 4 similarly the second fourth claim is the maximum of those same two values so the same two forks are being claimed except we're always making sure that the one that has the lower subscript index or the lower array index is claimed first why does this global ordering prevent deadlock if we go back to this diagram and think about how the resource requests would occur with our modified code we would see that this claim could not happen because process for Lassa fur for that is would need to claim for 0 before it could even request fort 4 so that means that this claiming of Fort four would not happen this request would happen and then +4 4 would have to wait until philosopher zero was done but because this edge is gone it means that this request is transformed into a claiming of that fork so the fork would be successfully claimed by philosopher three and at this point philosopher three has two forks fork three and fork for this means philosopher three is able to eat and will eventually give up both Forks at which point they'll be able to be claimed by other processes and the whole program continues and the philosophers get to eat without dying from starvation so a very simple change to this code avoids deadlock now you can also change the order in which the forks are put back but that's not really necessary now this is only one of many ways to solve the dining philosophers problem but a useful takeaway lesson from this is that one way to assure a circular white condition will not occur is to have a global ordering of resources for all processes

Channel: Jacob Schrum

Views: 40,662

Rating: 4.956284 out of 5

Keywords: dining philosophers, deadlock, processes, threads, concurrency, starvation, semaphore, mutual exclusion, preemption, hold and wait, circular wait, resource allocation graph, graph, directed, cycle

Id: _ruovgwXyYs

Length: 12min 19sec (739 seconds)

Published: Mon Aug 08 2016