Livelock
Research the problem of livelock in a networked environment. Describe how it differs from deadlock and give an example of the problem. Identify at least two different methods the operating system could use to detect and resolve livelock. Cite your sources by including a relevant URL and be sure to include your name.
Blog on!
14 Comments:
LIVELOCK
A condition that occurs when two or more processes continually change their state in response to changes in the other processes. The result is that none of the processes will complete. An analogy is when two people meet in a hallway and each tries to step around the other but they end up swaying from side to side getting in each other's way as they try to get out of the way.
DEADLOCK
A condition that occurs when two processes are each waiting for the other to complete before proceeding. The result is that both processes hang. Deadlocks occur most commonly in multitasking and client/server environments. Ideally, the programs that are deadlocked, or the operating system, should resolve the deadlock, but this doesn't always happen.
Ways to prevent are found at www.cs.ucla.edu/~kohler/class/04f-aos/ref/mogul96eliminating.pdf
Livelock can be avoided by limiting the rate at which interrupts are imposed on a system. Another way to avoid livelock by using a round-robin polling system.
Lonnie
http://paulbridger.net/livelock
Livelock
Livelock is when multiple threads continue to run (ie. do not block indefinitely like in deadlock), but the system as a whole does not make progress due to repeating patterns of non-productive resource contention.
Livelock may arise from attempts to avoid threads blocking (which can hurt performance) via a try-lock. A try-lock attempts to lock a mutex but does not block if the mutex is already locked. The following example should make usage of the Boost try-lock clear.
Deadlock
Deadlock is where one or more threads wait for resources that can never become available.
The classic case is where two threads both require two shared resources, and they use blocking mutexes to lock them in opposite order. Thread A locks resource X while thread B locks resource Y. Next, thread A attempts to lock resource Y and thread B attempts to lock resource X: since both resources are already locked (by the other thread), both threads wait indefinitely.
The following diagram should make the sequence clear.
Avoid livelock via careful scheduling of network interrupt handling.
Livelock is a condition that occurs when two or more processes that are trying to change each others processes. Same as two persons walk into each other and both try to move to the other side but both keep blocking each other.
Deadlock is different from Livelock due to the processors are waiting for the other to complete their procidure. It happens when the user is trying to multitasking more than two processes or when is down loading to many programs at the same time.
http://www.webopedia.com/TERM/L/livelock.html
http://www.webopedia.com/TERM/D/deadlock.html
LIVELOCK
A case where two processes keep changing state waiting for each other to finish some processing, say if both are waiting for a resource:
encyclopedia.thefreedictionary .com/dict.asp?Word=LIVELOCK
Deadlock, in contrast, is a case where two (or more)processes get hung up waiting for each other to finish:
encyclopedia.thefreedictionary .com/dict.asp?Word=DEADLOCK
A simple case is where A calls B repeatedly, B must be swapped in in place of A and B tries to return, swapping with A, which calls B again.
This type of livelock can not be detected except by the thrashing of the hardware: It arises in Interrupt-driven systems, when the processes are busy using the same interrupt mechanisms to process interrupts, so each is waiting for one or more others. This can happen with both network processing and traditional I/O devices:
www.cs.ucla.edu/~kohler/class/04f -aos/ref/mogul96eliminating.pdf,
p.1
This type of livelock can be fixed by slowing the rate or length of interrupt processing:
www.cs.ucla.edu/~kohler/class/04f -aos/ref/mogul96eliminating.pdf,
p3
Another possibility, since either polling or interrupts could livelock, is to alternate them:
www.cs.binghamton.edu/~kchiu/cs552 -f04/slides/livelock.ppt,
p.26
Joyce
Livelock:
When two or more processes continually change their state in response to changes in the other processes.
webopedia.com/term/l/livelock.html
Deadlock:
When two processes are each waiting for the other to complete before proceding.
webopedia.com/term/d/deadlock.html
You can provide a "backoff mechanism" which makes an agent wait a predetermined time bfore rearbitrating for the bus allowing the requested resource to become available. Or you could try the "stretch" solution which enables immediate arbitration of the system bus. It them waits a random amount of time before it uses the resource.
www.patentstorm.us/patents/5758104-description.htm
The problem of livelock in a network environment is caused when two or more processes continue to black the fowarding progress of the other without making any foward progress itslef. Unlike the deadlock however, in a livelock the processes do not get blocked or stand still in waiting. Instead the two processes continue to change in state.
An example of livelock would be if two people were walking down a narrow hallway and both try to be nice and move to the side to let the other pass by. But because they are both are trying to be nice at the same time, they continuously block eachothers way through the hallway.
Two ways an operating system could detect and resolve livelock are
1)To drop incoming processes and make sure only one process is in progress at a time
2)Use back pressured network packets in the system where you insist that no processes should be dropped even when congestion starts to build up. Have congested nodes send back pressure feedback to neighboring nodes letting them know the unavailabilty of rescources so that way they may stop fowarding processes until enough rescources become available.
I got my information from
http://ieeexplore.ieee.org/Xplore/login.jsp?url=/iel5/6725/17999/00832530.pdf?arnumber=832530
and
The course text book
McHoes, Ann McIves, Flynn, Ida M., "Understanding Operating Systems", 5th edition. 2008.
Just a note I forgot to put my name
The problem of livelock in a network environment is caused when two or more processes continue to black the fowarding progress of the other without making any foward progress itslef. Unlike the deadlock however, in a livelock the processes do not get blocked or stand still in waiting. Instead the two processes continue to change in state.
An example of livelock would be if two people were walking down a narrow hallway and both try to be nice and move to the side to let the other pass by. But because they are both are trying to be nice at the same time, they continuously block eachothers way through the hallway.
Two ways an operating system could detect and resolve livelock are
1)To drop incoming processes and make sure only one process is in progress at a time
2)Use back pressured network packets in the system where you insist that no processes should be dropped even when congestion starts to build up. Have congested nodes send back pressure feedback to neighboring nodes letting them know the unavailabilty of rescources so that way they may stop fowarding processes until enough rescources become available.
I got my information from
http://ieeexplore.ieee.org/Xplore/login.jsp?url=/iel5/6725/17999/00832530.pdf?arnumber=832530
and
The course text book
McHoes, Ann McIves, Flynn, Ida M., "Understanding Operating Systems", 5th edition. 2008.
-David Del Castillo
This comment has been removed by the author.
This comment has been removed by the author.
This comment has been removed by the author.
Deadlock differs from livelock because deadlock is waiting for a used resource to become free while livelock is both processes trying to fix the problem so to speak. Livelock is similar to two people walking through a narrow corridor and each person trying to make a path for the other person but as they keep moving back in forth they are directly in front of one another. Livelock is a risk for some algorithms used to recover from deadlock. This can be avoided by one process either randomly or by priority takes action.
-Steven Walker
http://en.wikipedia.org/wiki/Deadlock#Livelock
Livelocks occur when there is a half to forward progress in a distributed system. Deadlock on the other wand generally occurs due to buffer constraints in a packetswitched interconnect.
Many softwares have some kind of livelock detection. SimEvents software is one example and it stops and displays an error message when livelock occurs. A way to resolve the problem in SimEvents is by changing the values of the max events per block and max events per model parameters.
http://67.79.90.147:2196/ehost/pdf?vid=15&hid=112&sid=19887a22-a7ce-4d93-befc-63a4c8b1270c%40sessionmgr104
Electronic Design; 3/30/2006, Vol. 54 Issue 7, p61-61, 1p
http://www.mathworks.com/access/helpdesk/help/toolbox/simevents/index.html
Daniel Brooks
Livelock is when two or more processes continually block the forward progress of the other without making any forward progress itself. It's very similar to deadlock, with the difference being the in deadlock, rather then attempting to continue, the processes stop, each waiting for the other to finish. Both amount to the same thing, but would be solved in different ways.
You can solve the problem of the livelock using a round-robin polling system. Or it can also be solved by dropping incoming processes, allowing only one to work at a time. That slows things down, though.
Thomas Kelley
webopedia.com/term/l/livelock.html
and the textbook
Livelock is almost the same thing as Deadlock except that the states of the processes involved are in constant change. Livelock is a special case of resource starvation.
Url:http://en.wikipedia.org/wiki/Livelock#Livelock
Jessie
Post a Comment
<< Home