Chapter 5 - Livelock
Research the problem of livelock in a networked environment. Describe how it difffers from deadllock and give an example of the problem. Itdentify at least two different methods the operating system could use to detect and resolve livelock. As always include a relevant URL and add your name. Blog on!
12 Comments:
Example: Lets say you own an online computer company and you process all the online orders and promise delivery by a certain date. So you are just waiting on deliver, but delivery company is overwelmed.
Detect and resolve livelock.
1. Limiting interupt arrival rates.
2. Polling to provide fairness.
Kenneth Castro
Polling and auditing are the best methods to detect for livelock. In a multiprocessor environment, detecting a timeout would quickly throw the flag that a livelock has occured.
Once detected, Having an established master CPU resolve the livelock and redistribute to slaves in a pre-emptive measure would be a relatively graceful way to reach a solution.
http://www.learnthat.com/define/view.asp?id=1763
- Colin Allman
Livelock and deadlock are two similar problems that can occur in the processor but are slightly different from each other. A good example of livelock is when two people are in a stairway and one move to the right while the other move to the left. Both person are moving without making any progress. Deadlock will occur when two processes are watting for each other to finish before continuing to completion resulting in ether processer making any progress or completing their job.
For a livelock solution a bus unit detects a time out condition and activate a livelock resolution request. This will notify the control processor of a livelock in progress and the processor takes action on resolving the livelock
http://www.webopedia.com/TERM/L/livelock.html
http://www.webopedia.com/TERM/D/deadlock.html
http://www.google.com/patents/about/7500035_Livelock_resolution_method.html?id=c-3CAAAAEBAJ
Ruiz D
Livelock a situation where a message can move from node to node but never gets to its destination. Deadlock is when no message could move if all the buffers were full. The operating system can use Interrupts and polling to resolve livelock but, Prefix-based routing scheme in irregular networks has shown to be deadlock and livelock free.
Parallel Processing Letters, Dec2003, Vol. 13 Issue 4, p705-720, 16p
Terry Charping
Livelock is when one or more packets, or jobs, move in an endless loop through the network but never make it to a destination. The sources they need are available but they are passed back and forth and can never acquire the source they need. It is similar to deadlock but the packets that are deadlocked stop traveling as they are waiting for their next source to become available, therefore stopping all other packets from moving forward. To prevent this a small threshold amount of misrouting could be added to the packets, thus ending the cycle or an age could be added to the packets thus allowing the oldest packet to proceed first.
http://www.tkt.cs.tut.fi/kurssit/9636/K05/Chapters14-15.pdf
Retta Kasper
A thread often acts in response to the action of another thread. If the other thread's action is also a response to the action of another thread, then livelock may result. As with deadlock, livelocked threads are unable to make further progress. However, the threads are not blocked — they are simply too busy responding to each other to resume work. This is comparable to two people attempting to pass each other in a corridor.To avoid livelock and related problems, an operat- applications will become widespread. Client-server
ing system must schedule network interrupt handling applications, such as NFS, running on fast clients and
as carefully as it schedules process execution. We servers can generate heavy RPC loads. Multicast and
modified an interrupt-driven networking implemen- broadcast protocols subject innocent-bystander hosts
tation to do so; this eliminates receive livelock with- to loads that do not interest them at all.http://www.stanford.edu/class/cs240/readings/mogul.pdf
live lock is when you have only lateral moveing going on and neither job can be worked on because they keep alowwing the other to go ahead. dead lock is when everything come to a stand still and no move ment is seen.
One way to get rid of LIVELOCK is to set up a Queing system, each process needing the resorce(s) will wait in line. If there is a sort of cop directing traffic this too could prevent live lock. It would see where everything needs to go and what it will need then assigns them a number so that none will be useing the same resorces at the same time or at least wait till one is done first.
http://beyondrelational.com/quiz/sqlserver/dba/2011/questions/dead-lock-live-lock-blocking.aspx
derrick demaree
Livelock is an endless loop in program execution that keeps receiving wrong information. In other words, it's like a pizza guy that keeps on delivering wrong pizza.
Javier Jimenez
http://www.pcmag.com/encyclopedia_term/0,2542,t=livelock&i=46192,00.asp#fbid=fR_OfgW_Yym
Livelock is like ground hogs day, if you do not do anything to break the cycle or alter your day in some way it will keep repeating it self and nothing will get done. The way to aviod dead lock is with Deadlock avoidance and deadlock recovery. For livelock the best way to defeat that is for the system to detect it and use interupts to change the course of action. The ways to explain Livelock is two people are on the same stair case traveling in different directions, they meet in a narrow spot in the stairwell and neither will move so the other can move and complete there task.
http://www.tkt.cs.tut.fi/kurssit/9636/K05/Chapters14-15.pdf
Livelock is the same as Deadlock only difference is that, Livelock is still be processed by the cpu, an are not blocked til the end of time, they are being slowly pushed through, although its almost like backed up traffic that is slowly making its way through busy city streets.
Most systems use interface interrupt locks to to schedule network tasks.Works well at low overhead but as the work gets heavier it degrades the overall opertation capabalities an you get a Livelock.
Must modifies an network driven interface implementation, do do this would allow an eliminat recievelivelocks, an keep from degrading other aspects of sytem performance.
From an article by Jeffrey C Mogul an K.K Ramakrahsan.
deadlock is two or more competing action that are both waiting for the other to finish, and none of them does. for example, when two trains reach near each other at the crossing, they both stop and neither don't start until either train has gone. to resolve is by cooling-off/mediation or deterrance approach
http://en.wikipedia.org/wiki/Deadlock
http://en.wikipedia.org/wiki/Deadlock_provision
-Paul Laureano
A deadlock is a situation where in two or more competing actions are each waiting for the other to finish, and thus neither ever does. An example of dead lock is the phrase Catch 22.
A livelock is similar to a deadlock, except that the states of the processes involved in the livelock constantly change with regard to one another, none progressing. A real-world example of livelock occurs when two people meet in a narrow corridor, and each tries to be polite by moving aside to let the other pass, but they end up swaying from side to side without making any progress because they both repeatedly move the same way at the same time.
http://en.wikipedia.org/wiki/Livelock#Livelock
Post a Comment
<< Home