Dining Philosophers Problem with Solution

hello my name is Gary Sims and this is Gary explains now you're probably watching this on a desktop or a laptop or ax or a smartphone and it's probably a device with multiple cores you know what kind of it could be a quad-core an octa-core and you are running multiple programs at the same time now when you do that you can get a problem called resource contention which means two programs want to access the same resource at the same time now there's a way to illustrate this problem that's been used famously for many many years called the dining philosophers problem so I want to look today at resource contention deadlock and the dining philosophers problem so if you wanna know more about it please let me explain so in a computer system things like the memory things like the file system the networking the the video card the display can only be accessed generally by one program at a time you definitely don't want a program when you're writing let's say a spreadsheet and another program can overwrite the same spreadsheet at the same time that you're writing to it because you're gonna get a corrupted data these are the only up like a high level things like an Excel spreadsheet or a database also applies to low-level things like the file system or memory you certainly don't want to programs trying to access the same memory location at the same time because you're gonna end up with gibberish there was a very famous software engineer whose lay there many many fundamentals of software engineering called Dijkstra and he Waite wanted to illustrate this problem to other people and he came up with this idea of the dining philosophers so let's have a look at it so the idea behind the dining philosophers problem is there are five philosophers who are sitting on a round table and each one has a bowl of food in front of them but there is only one fork between each bowl which means there are five Forks and five bowls of food and to eat a philosopher needs to have a fork from the left and a fork from the right and then use both of them to feed himself now when he's not feeding he can actually be thinking and the problem runs like this because they're all independent they're all running in parallel once the program start each philosopher might let's say grab the fork on his left and then they would why to grab the fork on the right but the moment they've grabbed the fork on the left all the other philosophers were also grabbed the fork on the left which means now when they try to grab the fork on the right they can't because the person the philosopher on the right has grabbed it as their fork on the left and now what happens is all the philosophers are in their thinking mode and they're not eating and they're waiting for the fork on the right to become free and it will never happen because we're in a circle and you have deadlock and you have resource starvation and in fact in this picture the philosophers will starve because they will only ever think and they will never eat so everything about our modern day operating system whether it's Windows or Mac OS or Linux these kind of situations arise about not Forks but about the network or the memory or the file system and what you don't want is two processes two programs that kind of mutually exclusively lock each other out so program a says I want something that program B wants and program B says I want something that program a want and they both just sit there waiting for each other and there's no way to escape now there are many ways of solving this dining philosophers problem I want to show you what's probably the easiest way to understand let's imagine that we introduce a waiter into the room and he lays down a rule he says the only one flaw to her at a time can pick up one or maximum two forks and what this means is that they have to ask the way to permission can I please pick up the forks please and you might say yes and then only at that moment come one philosopher actually be in the process of picking up some Forks so it would work like this if philosopher number one wanted to pick up some Forks people asked permission he would ask permission and then the answer would be yes you can do that so the plotter would pick up the fork on the left and then the second fork the fork on the right and then say to the waiter I've picked up my Forks and then I take the philosopher on the left now what's a try and so she says okay can I pick up my forks and the waste Aziz please try and she picked up the fork on her left but when she tries to pick up the fork on her right she finds that actually it's already occupied so she renounces the fork on the left puts it down and says to the waiter I'll try again later now the third philosopher then says what can I pick up some Forks and the waiter said yes you can and so he picks up the fork on the left and he picked up his fork on the right and he starts eating and then now the fourth and the fifth philosopher both tried to pick up Forks but they don't have a pair and so they wait and now philosophers two and four and five are waiting while philosopher one and three are eating after 10 minutes or so they will put down their Forks and now the philosophers can ask again could we now pick up our Forks and what the waste does here is introduce the idea of a monitor a mechanism that can actually monitor what's going on and control the order in which things are happening and this is done using a thing called a lock and with a lot what happens is that by requesting access to something you gain the lock and other people cannot gain access to it while you hold the lock and then what happens is once you've picked up the two forks you can then free the lock saying well now anybody else can try if they want to so it's called a locking mechanism a modern-day operating systems have many many locks and they go in and out of these locked areas all the time to make sure there is not a clash of resources a clash of trying to do the same thing at the same time there's a couple of other quick things to mention here and that is that once philosophers 1 and 3 have actually finished eating they will put down their Forks and then maybe philosopher two and four will ask for the right to pick up Forks and they will succeed because those Forks are now free but philosopher 5 doesn't get a go until the third round now you can get the situation where once you get to the third round philosopher one asks again can he pick up the Forks and of course parole philosopher five never gets a chance so you also need to have in some scheduling here that gives a priority about who is allowed to ask for these Forks and in this case you might use something like minutes since the last time they ate which would bump up Philosopher's farm number five to the top of the queue so that he could always ask first for the forks and then one and two and three and four have to wait because they've actually already eaten and this one of a thing worth mentioning that is the locking needs to be atomic you can't have the situation where two of the philosophers asked for the lock asked for the right to pick up fork and the waiter says to both of them yes you can so there has to be a mechanism where when one program is asking for a lock another program can't gain the lock in that moment that's called an atomic operation now the operating system whether it's Windows or Mac or OSX will actually provide an atomic locking mechanism to guarantee that when one program is asking for a lock another program can't swoop in and get the lock before it or at the same time whatever and those are provided by the operating system and so there you have it the idea of dining philosophers a way to avoid deadlock in which two or more programs are asking for the same resource but they're waiting on each other to free up an existing resource you also got the idea of a monitor and the monitor employs the idea of a lock an atomic lock to make sure that there is kind of agreed order of things on who can pick up who can pick up the forks who can access the resources at any one time and software engineers who are dealing with multi-threaded multi process systems have to use this kind of locking all the time and it is a good skill to learn and this is the basic fundamentals of how you understand locking in a multi-threaded or a multi process system well my name is Gary Sims and this is Gary explained I really hope you enjoyed this video if you did please do give it a thumbs up please you know what I'm gonna ask you please subscribe please hit that Bell notification icons you become part of the notifications squad please share this on social media and I would love to read your comments below this video and well that's about it I'll see you in the next one

Channel: Gary Explains

Views: 50,867

Rating: 4.9449821 out of 5

Keywords: Gary Explains, Tech, Explanation, Tutorial, Dining Philosophers Problem, Dining Philosophers, Deadlock, operating system design, os design, Edsger W. Dijkstra, Edsger Dijkstra, Locks, Atomic operation, semaphores, mutex

Id: NbwbQQB7xNQ

Length: 8min 9sec (489 seconds)

Published: Mon Apr 30 2018