Internet Research
Starting with Chapter 5, I will post a research topic in this blog every week. Each student is expected to comment on the topic by 1) summarizing his/her findings, 2) citing URLs validating his/her statements, and 3) including the student's name.
Please, do NOT fall into the "me too" mode. I expect the blog comments to be different and citing different sources. So it may be best for students to submit early!
This week the topic is livelock. Research the problem of livelock in a netowrked environment. Describe how it differs from deadlock and give an example of the problem. Identify at least two different methods of operating system could use to detect and resolve livelock. Cite your sources!
Blog on!
16 Comments:
Livelock differs from deadlock in that ....
http://www.ieee.org
Jane
http://www.pcmag.com/encyclopedia_term/0,2542,t=livelock&i=46192,00.asp#
Livelock differs from deadlock in that process continues to take place. Livelock is a contiues loop of execution.
Niki
Livelock is a risk with some algorithms that detect and recover from deadlock. ...
http://en.wikibooks.org/wiki/Operating_System_Design/Concurrency/Deadlock
Livelock is a risk with some algorithms that detect and recover from deadlock. ...
Livelock differs from deadlock in that instead of stopping what they are doing, they continue to execute, but make no progress toward the ultimate goal.
My source
In order to address the problem of livelock, this passage might help to find a solution to the dilemma.
So we can't write a checker which takes a concurrent program as input and always determines whether it's free of (say) deadlock.
But just as we can study individual programs and conclude whether or not they will halt, for many real-world concurrent programs, we can determine whether or not they are susceptible to deadlock. For example, communications protocols generally have a finite number of options and are amenable to automated checking. Thus automated tools (such as SPIN) are valuable aid in catching and eliminating real-world bugs.
I feel that while the overhead in monitoring the resources may be intensive, but it seems to be the best solution to halt anything that ceases to progress. In our text, an administrator can find the processes which are slowing or halting the progression of standard programs and halt them prematurely allowing for a greater allowance of resources. One thing that I always prefer when faced with a resource intensive operating system is to have as much RAM as I can. While that may not fall into the resources as stated before, it allows for greater flexibility when using a number of different processes.
written by Steve Hanson
Livelock differs from deadlock in that the processes involved in the livelock are constantly changing but never progressing. A human example of livelock would be two people who meet face-to-face in a hall and each moves aside to let the other pass, but they end up swaying from side to side without making any progress because they always move the same way at the same time.
To avoid livelock, an alogorithm must include some mechanism to guarantee progress over time. An example would be a scheduling retry scheme where an aborted session will make an execution request again after a waiting time based on its critical level.
My Source
Posted by Lisa Vidal
Livelock is when a thread (or several threads) runs through a loop that fails without any "progress in the system as a whole" essentially if a system repeats itself to no effect (or spins).
Deadlock
occurs when two processes are each waiting for the other to complete before proceeding and the result is that both processes hang.
Livelock is resolved by introducing a livelock detection mechanism (which includes livelock detection utility or logic) within the processor to detect a livelock condition and dynamically change the duration of the delay stage(s) in order to alter the “harmonic” fixed-cycle loop behavior. The livelock detection logic (LDL) counts the number of flushes a particular instruction takes or the number of times an instruction re-issues without completing. The LDL then compares that number to a preset threshold number. Based on the result of the comparison, the LDL triggers the implementation of one of two different livelock resolution processes. These processes include dynamically configuring the delay queue within the processor into one of two different configurations and changing the sequence and timing of handling memory access instructions, based on the specific configuration of the delay queue.
Ex:A complex example of LiveLock occurs when two (or more) 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.
http://www.cocoadev.com
http://www.freshpatents.com/
http://webopedia.com
http://en.wikipedia.org/wiki/Deadlock
A deadlock is like a paradox...competing actions try to finish but are waiting for the other to finish for ifself to finish...Livelock is almost like a deadlock but the states of the actions are constantly changing with each other
The difference between livelock and deadlock is that livelock keeps attempting the process and deadlock stops all processes that are trying to use resources.
Ex 1: Livelock can occur when a process or group of processes are stuck in an infinite loop. An example of this is when a process command is searching for non-existant data but does not receive an error. The use of a cache coherency manager can send the multi-level processor request for verification that the data does exist.
Ex 2: By adding a temporal attribute to the application state, we say that if the program does not make forward progress within some time bound it is livelocked. For example, if the temporal rule “a response is sent for every request within 10 seconds” fails then the server is deemed to be at a standstill.
http://www.faqs.org/patents/app/20080320230
http://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-633.pdf
Becky
http://en.wikipedia.org/wiki/Deadlock
A deadlock is like a paradox...competing actions try to finish but are waiting for the other to finish for ifself to finish...Livelock is almost like a deadlock but the states of the actions are constantly changing with each other
jamey
LiveLock
What is it? Livelock is according to Webopedia.com a condition where two or more processes or tasks continually change their state in response to changes in the other process or task. This causes none of the processes to complete. Dictionary.com defines livelock as a situation in which some critical stage of a task is unable to finish because its clients perpetually create more work for it to do after they have been serviced but before it can clear its queue. The difference between livelock and deadlock is that with deadlock the process is waiting for something and is blocked, but with livelock the process is not waiting for anything or blocked by anything and has an infinite amount of work to do and can never catch up. The hallway analogy is used in both examples; where two people are in a hallway and both of them move to the side to let the other pass but none of them can ever get by because they keep stepping in the same direction continually blocking each other. With deadlock there is no movement. According to Freepatentsonline.com a multi-MAC chip for an Ethernet generates different variables for each MAC layer so that each MAC has distinctive backoff interval when there is a collision. This keeps a livelock state from ever occurring. Another method of preventing livelock is called back-off or exponential-back-off. 2. Computer.org talks about this method. Meta-scheduling is a process that allows users to schedule multiple jobs across multiple sites this has potential for livelock. This method allows several jobs to be scheduled across multiple lines without the need for locking down the nodes. Exponential-back-off determines a suitable back-off period. This procedure reduces livelock and as a bonus shortens the scheduling time for each job.
Tara
Livelock
• Packets continue to move through network, but do not advance towards
destination
Deadlock
• Occurs in interconnection network when group of agents (e.g. packets) are unable to act because of waiting each other to release some resource
source: http://www.tkt.cs.tut.fi/kurssit/9636/K05/Chapters14-15.pdf
This comment has been removed by the author.
Livelock is a special case of resource starvation, example in real life would be two people try to pass each other in hallway can try to polite and go around the other person, only they keep going the same way and no one will progress. the difference of livelock vs deadlock, is that livelock the resources are not completely locked but instead nothing gets done because othe two files try to process are dancing around each other. where as deadlock two files are required from each other and neither are giving up their information which causes a complete lock.
http://en.wikipedia.org/wiki/Deadlock#Livelock
Livelock is a locked system where two or more processes continually block the forward progress of the other without making any forward progress itself. 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 example of livelock occurs when two people meet in a small hall and each tries to move aside to let the other pass but they end up swaying side to side without letting each other pass because they both repeatedly move the same way at the same time.
http://en.wikipedia.org/wiki/Deadlock
DeWaun Carmichael
A livelock is one, where a request for an exclusive lock
is repeatedly denied because a series of overlapping shared
locks keeps interfering. SQL Server detects the situation
after four denials and refuses further shared locks. A
livelock also occurs when read transactions monopolize a
table or page, forcing a write transaction to wait
indefinitely.
http://www.allinterview.com
Post a Comment
<< Home