What are some more examples of livelock? I am still struggling to distinguish between deadlock and livelock.
ekr
Imagine you're walking down a hallway and you see someone headed in the other direction. To make room for them to pass you, you move to your right. They intend to give you room, so they move in the same direction. You each see the other person moving in that direction, so you both switch directions at the same time, repeatedly. Neither of you is "dead" per se, since you're still operating, but you're not making any meaningful progress.
russt17
Two dogs chasing each other around the base of a tree and never catching each other?
Or this ones kind of a stretch cause I think livelock is usually with multiple processors, but a horse with a fishing rod taped to its back and a carrot dangling in front of it. Horse runs forever but never gets the carrot.
solovoy
I also don't really understand the difference that clearly. For the car example on the slide, both deadlock and livelock have the same "difficult situation". The only difference seems to be in the deadlock case, the system doesn't do anything or chooses not to do any thing. While in the livelock case, the system chooses to do something, but doesn't work it out. My question would be, does this mean if the system can do some meaningless/failed work in deadlock situation, the deadlock situation can be turned into a livelock situation?
kayvonf
If this slide was an animated gif (or if you recall the way I animated the slide in lecture), it would become more clear what the difference between deadlock and livelock is. Can someone elaborate on this?
TypicalChazz
My understanding:
Deadlock - The system does literally nothing. Literally, the code just 'hangs'.
Livelock - The system performs work to avoid deadlock, but not the work that the system actually needs to get done. I like to think of livelock as a state in which the system continually performs the artifactual work necessary to avoid deadlock, but never ends up doing the actual work it needs to do.
arjunh
@TypicalChazz makes a good point; livelock typically arises in situations where the system tries to avoid deadlock. In the 'hallway' example, if you both move in the same direction while trying to pass the other, then both of you would enter a state of deadlock if neither of you made any further moves (neither of you can do anything; you can't move forward and you can't move in the other direction).
However, if you both keep on 'mirroring' each others moves (both move left, both move right), then you'd enter a state of livelock (you can't move forward, but you are still moving, albeit doing no meaningful work).
subliminal
This may help anyone still having problems understanding deadlock, livelock and lock starvation. I had come across these java examples some time back, and coding up the situations and observing the results had helped me understand what was happening exactly.
flyne
From what I understand, livelock is a situation where the process is not making any real progress. Does that mean livelock is not always deadlock avoidance. If it's not, can someone think of an example that is livelock and not deadlock avoidance.
afzhang
In deadlock there are 2 operators that need each other to make progress, so neither can make ANY progress. The entire system is just stuck and sits idle, not doing anything. In livelock the system is constantly doing something (e.g. the cars moving back, and then forward again, and then back again) but still unable to make any progress.
muyangya
Here I found another example that makes a lot of sense to me. Here's a condition when livelock may occur in computer programs: Image there are two threads, each run a series of operations repeatedly until a condition becomes true, but in such a way that they cancel the others' work out just before they come to test the condition, forcing them both to restart forever.
To visualize this situation, imagine two workers trying to build an arch. First, they look around for a keystone; if one is not there, they will craft one, but otherwise they will put it next to where they are building their wall, and then make up the arch, finishing off by putting the keystone in - UNLESS it has moved in the meantime, in which case they let the archway collapse and start over.
Imagine there is just a single keystone. Worker A takes it next to his wall, and starts building his arch. Along comes Worker B, finds the keystone, and moves it next to his wall, and begins on his arch. Worker A, having got his arch all ready, turns around and finds he has no keystone. He lets his nice arch collapse, goes off, and takes the keystone back to his wall and starts building. B, on turning around, finds the keystone gone, lets his wall collapse, and repeats the cycle. Like Sisyphus, they are condemned to repeat this insanity for all eternity.
What are some more examples of livelock? I am still struggling to distinguish between deadlock and livelock.
Imagine you're walking down a hallway and you see someone headed in the other direction. To make room for them to pass you, you move to your right. They intend to give you room, so they move in the same direction. You each see the other person moving in that direction, so you both switch directions at the same time, repeatedly. Neither of you is "dead" per se, since you're still operating, but you're not making any meaningful progress.
Two dogs chasing each other around the base of a tree and never catching each other?
Or this ones kind of a stretch cause I think livelock is usually with multiple processors, but a horse with a fishing rod taped to its back and a carrot dangling in front of it. Horse runs forever but never gets the carrot.
I also don't really understand the difference that clearly. For the car example on the slide, both deadlock and livelock have the same "difficult situation". The only difference seems to be in the deadlock case, the system doesn't do anything or chooses not to do any thing. While in the livelock case, the system chooses to do something, but doesn't work it out. My question would be, does this mean if the system can do some meaningless/failed work in deadlock situation, the deadlock situation can be turned into a livelock situation?
If this slide was an animated gif (or if you recall the way I animated the slide in lecture), it would become more clear what the difference between deadlock and livelock is. Can someone elaborate on this?
My understanding:
Deadlock - The system does literally nothing. Literally, the code just 'hangs'.
Livelock - The system performs work to avoid deadlock, but not the work that the system actually needs to get done. I like to think of livelock as a state in which the system continually performs the artifactual work necessary to avoid deadlock, but never ends up doing the actual work it needs to do.
@TypicalChazz makes a good point; livelock typically arises in situations where the system tries to avoid deadlock. In the 'hallway' example, if you both move in the same direction while trying to pass the other, then both of you would enter a state of deadlock if neither of you made any further moves (neither of you can do anything; you can't move forward and you can't move in the other direction).
However, if you both keep on 'mirroring' each others moves (both move left, both move right), then you'd enter a state of livelock (you can't move forward, but you are still moving, albeit doing no meaningful work).
This may help anyone still having problems understanding deadlock, livelock and lock starvation. I had come across these java examples some time back, and coding up the situations and observing the results had helped me understand what was happening exactly.
From what I understand, livelock is a situation where the process is not making any real progress. Does that mean livelock is not always deadlock avoidance. If it's not, can someone think of an example that is livelock and not deadlock avoidance.
In deadlock there are 2 operators that need each other to make progress, so neither can make ANY progress. The entire system is just stuck and sits idle, not doing anything. In livelock the system is constantly doing something (e.g. the cars moving back, and then forward again, and then back again) but still unable to make any progress.
Here I found another example that makes a lot of sense to me. Here's a condition when livelock may occur in computer programs: Image there are two threads, each run a series of operations repeatedly until a condition becomes true, but in such a way that they cancel the others' work out just before they come to test the condition, forcing them both to restart forever.
To visualize this situation, imagine two workers trying to build an arch. First, they look around for a keystone; if one is not there, they will craft one, but otherwise they will put it next to where they are building their wall, and then make up the arch, finishing off by putting the keystone in - UNLESS it has moved in the meantime, in which case they let the archway collapse and start over. Imagine there is just a single keystone. Worker A takes it next to his wall, and starts building his arch. Along comes Worker B, finds the keystone, and moves it next to his wall, and begins on his arch. Worker A, having got his arch all ready, turns around and finds he has no keystone. He lets his nice arch collapse, goes off, and takes the keystone back to his wall and starts building. B, on turning around, finds the keystone gone, lets his wall collapse, and repeats the cycle. Like Sisyphus, they are condemned to repeat this insanity for all eternity.