I think I may have missed this during the live lecture – what would be a computer systems example of livelock? It makes sense in real-life situations, but I can't quite conceptualize what it would look like in a program.
@nickbowman A simple example came to my mind is just that a program adds the "try" block around the trial, e.g. to access some resource, which is potential to cause the deadlock. As long as the trial fails, some error will be thrown and the program will abort instead of waiting. The the resources held by it previously will be released. Then there will be a re-trial of the program.
I think @orz's example would be an example of a faulty implementation of preemption from slide 8? As in, if we had some processors that all need the same resources, in livelock a processor might continually give up and reacquire one resource, rather than holding onto the one resource in deadlock.
A common example of livelock in real life is when two people walking towards one another attempt to move in the same direction to dodge each other, but end up getting stuck in a back and forth dance instead.
I wonder if the Two Generals' Problem is also an example of livelock. If we attempt to solve it by having each general repeatedly send acknowledgements to ensure the other that their messages were resolved, then both generals would be stuck in livelock. This problem shows up in computer networking with the TCP protocol, where in order to close a TCP connection, we would like to be as sure as possible that the other side received our signal that the connection is over.
I wonder if livelock can be prevented if, once it is detected by the OS (all the threads of a process giving "backing up their cars"), the OS arbitrarily chooses one to give more resources than usual to (basically doesn't give the other threads time slices for a while, to increase the chances of one car making it through the entire intersection.)
Building on the connection related to TCP, one example is when two computers are attempting to send a packet on a common wire (say ethernet without switching). If they have a collision and each packet is garbled, they might back off for some amount of time before trying again. We need this back off to be stochastic as otherwise they would back off for the same amount of time and again collide, resulting in a livelock.
Another example of livelock is when two people offer to pay for a bill and both continue to offer to pay for the bill, both people get stuck in the back and forth of offering to pay for the bill which is livelock.
What would be the difference between livelock and deadlock in the example with the queues? The example where queue A is trying to do work on elements pushed out of queue B and queue B is trying to do work on elements pushed out of queue A is shown as an example of deadlock if both queues are finished, but it seems to me that this could be livelock as well if they're both constantly pinging to ask if the queue has work to do, what am I missing?
@yonkus I think the main reason why it is a deadlock is that both A and B depend on each other's finishing their works, and do not pop out their working queue while spinning. I think it would be a livelock if A and B try to pop out the current work to start over
Please log in to leave a comment.
One real life example is in a zoom meeting, where two persons try to say something at the same time, and then both try to be polite and stay silent so that the other party could continue, and then both parties try to say something again at the same time, and so on...