Now that you've learned about threads and locks, let's look at a fundamental correctness property of concurrent programs, and that's referred to as LIVENESS. Now, you all have probably had the experience of, when writing a sequential program, and it has a bug in it, you run it and nothing shows up on the screen. And then you wait, and then you figure out, maybe there's an infinite loop. And then you go and try and fix the bug. Unfortunately, in concurrent programs, there are many other ways to have this symptom. One is DEADLOCK. Which we've already seen before in the case of join operations. If two threads join on each other, they create a deadlock cycle, and the program doesn't exit for that reason. So it's not an infinite loop, it's just two threads blocked on each other indefinitely. There are other ways of getting deadlock with locking operations. For instance, if thread T1 does a SYNC, synchronized operation on A, and a synchronize operation on B, And thread T2 does a synchronized operation on B, and then a synchronized operation on A nested within it, We get another form of deadlock. Because thread one is going to acquire lock A and wait for lock B, thread two is going to acquire lock B and wait for lock A. Some executions might succeed fine, but in one possible execution, T1 may get A at the same time as which T2 gets B, and then each is waiting on the other indefinitely. So that's a case of deadlock, where the program just does not make any progress and violates the liveness property. There's another more subtle form of liveness errors that's referred to as LIVELOCK. What happens in livelock is the threads are not blocked, but yet they're in a mode in which they are not making any progress, sort of like stalemate in a game of chess. So one possible example for this is if we have an object, let's say a mutable integer object x, and we have two threads, T1, in a loop. So thread T1 is going to increment x And then read the value of x and continue this while the result is less than 2. And thread T2 is going to decrement the value of x, read the result, and continue while the result is greater than -2. Now, if you have two threads executing and accessing the same mutable int x, we need synchronization, so that we can easily arrange by putting some synchronized x around this. But let's think of the possible execution sequences for x. Now one possibility is that only T1 executes. It keeps incrementing x till x becomes 2, and T1 exits. And then T2 executes, it keeps decrementing x till x reaches -2, and it too exits. But there's an interesting scenario in which T1 might see x=0, x=1. But before it gets a chance to increment x and reach x=2, T2 executes and decrements x countering what T1 has been doing. And makes x=0, x=-1. And before T2 gets a chance to decrement it to -2, T1 could kick in again to get x= 0, T2 could kick in at that time to get x = -1 and so on, you get the idea. So these two threads can be going back and forth like a continuous infinite ping pong match, where neither of them is making progress. It's not an infinite loop that you would get from sequential execution, but it is effectively an infinite loop when you consider all the concurrent interactions. So this is an example of livelock. Now, the third kind of issue that comes up with liveness is called STARVATION. So let's assume that we're writing a bunch of web servers, and a web server has access to multiple sockets like S1 to S100. And thread T1 will repeatedly read some value, let's say IN1 = S1.READ LINE. And PRINT IN1. And similarly threads T2, T3, up to T100 will do the same thing for their respective sockets. So T100 will also have IN100 = S100.READ LINE And PRINT IN100 while some condition. Now, we could have some synchronizations if needed, but we'll see that there's no deadlock. Each thread can just continue reading input from its socket. There's no concurrent interaction that causes a deadlock. There's no concurrent interaction that causes a livelock, but depending on how the threads are scheduled, it's possible that T100 never gets to execute. It starves, meaning that it never gets scheduled, because the other threads already are executing on the processors and may just have a continuous feed on their input sockets. So, what we see is that we have a new class of errors in concurrent programming related to deadlock, livelock, and starvation. And some of them are easier to avoid, and some are more challenging. And we will see examples of ways of addressing these issues as we learn more in this class.