I'd now like to use a classical example to illustrate the livelock and deadlock properties that we had discussed earlier. And this example is referred to, for historical reasons, as the Dining Philosophers problem. So what we're going to do is we're going to try and model this made-up scenario where we have five philosophers sitting around a roundtable. Let's say they're A, B, C, D, E. And there are exactly five chopsticks placed between them. And so to eat, a philosopher needs to pick up its left and right chopstick and eat. And in fact, what philosophers do is they spend a lot of time thinking. And then when they get hungry they would like to pick up the chopsticks. Eat, and put down the chopsticks. And this process keeps repeating. So the interesting question for us is this very simple made-up scenario. How can this be modeled using threads and locks? So let's start by looking at structured locks. And let's pretend that each philosopher is modeled by a thread. And we somehow need to use locks to coordinate the use of chopsticks so that we can implement this protocol over here. So to do this, we will have something like, let's model the loop as a while loop. And what each philosopher does is first, think. And then when he's ready to eat with structured locks, we would like to do a synchronized, let's say, on the left chopstick. Because the chopsticks are shared resources. Synchronized on the right chopstick. And then, when we have both chopsticks, we eat. And then, when we're done we can go back to the while loop. So this solution captures the idea of what we want. The synchronization makes sure that only one philosopher gets a chopstick at a time. But let's illustrate what could happen or what could go wrong over here. So, if all the philosophers were thinking and exactly at the same time they wanted to eat, we could have the situation where each of them picks up their left chopstick, that's in SYNC(LEFT), and now they are waiting for their right chopstick. But if each philosopher is just holding on to its left and waiting for its right, we have a deadlock. There may be other scenarios where they think at different times and you don't have deadlock, but there is certainly one execution possibility where there is a deadlock, so that's an issue. Now, what if we try a solution with unstructured locks. And again, we can use the while loop to model the problem, and we have think. But we may consider the fact that the blocking operations that synchronized contributed to a deadlock. So, let's use the TRYLOCK operation for coordinating the chopsticks. So, let's try and get chopstick on the left of us first and S1 is a success flag if he succeeded or not. And if he did not succeed, we want to go back to the loop which usually we have the CONTINUE statement that enables us to go back to the start of the loop. Now if he did succeed, then we can go past this point and try and get the right chopstick And again we have to check if he succeeded or failed. If he failed, if not S2, we will do a CONTINUE. But there's actually one more very important thing we need to do, we need to release the lock on the left. So we have to UNLOCK(LEFT). Because otherwise we would have been holding onto the left chopstick and we could get into a livelock situation without releasing that chopstick. Now, so one nice thing about TRYLOCK is that you don't have a blocking operation, so you're guaranteed that there is no deadlock. A deadlock is when threads are indefinitely blocked on each other. With TRYLOCK, you always have a return value, it's either success or fail. However, let's talk a little more about livelock. What if we had the same scenario where all the processes were thinking for exactly the same amount of time, they all try to get their left chopstick, they all succeeded, then they all try to get their right, and they all failed. So then they would all go back to the start of the while loop and then repeat this process. But in this way, no one will get to eat, which is what you have to do after you acquire the locks. So what we see is that livelock is possible over here. And no deadlock. Whereas with structured locks, we have exactly the opposite situation. With the synchronized construct, you can have blocking, you can have deadlock. But you will not have livelock because you don't have a TRYLOCK and a loop where you're kind of retrying. So how do we fix this problem? Well, it turns out the way to fix it is really to modify the algorithm. And say have philosopher E pick up right first, the right chopstick and then left. Whereas all the other philosophers A, B, C, D continue doing what they were doing earlier. And what you'll see is that if E picks up its right chopstick, philosopher A is free to pick up both chopsticks or E is ready to go. And so with this modification, you can avoid livelock and deadlock. There still remains the challenge of starvation, because only two philosophers can eat at a time. And it's possible, with the way the synchronization goes, that some philosopher let's say, C, never gets a chance at eating. That's a more complex problem to address and is an advanced topic in operating systems using a synchronization primitive called semaphores. But through this Dining Philosopher's problem, we've illustrated how structured and unstructured locks could lead to issues like deadlock and livelock, and how modifying your algorithm could avoid those issues.
