Chapter 5 -- 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 operatinbg system could use to detech and resolve livelock. As always, summarize, cite a relevant URL, and include your name.
Blog on!
17 Comments:
Timothy
Deadlock happens when the data going through is stopped with no place to go until something is moved out and livelock keeps jumping around until it finds a place.
example deadlock
public class Deadlock {
static class Friend {
private final String name;
public Friend(String name) {
this.name = name;
}
public String getName() {
return this.name;
}
public synchronized void bow(Friend bower) {
System.out.format("%s: %s has bowed to me!%n",
this.name, bower.getName());
bower.bowBack(this);
}
public synchronized void bowBack(Friend bower) {
System.out.format("%s: %s has bowed back to me!%n",
this.name, bower.getName());
}
}
public static void main(String[] args) {
final Friend alphonse = new Friend("Alphonse");
final Friend gaston = new Friend("Gaston");
new Thread(new Runnable() {
public void run() { alphonse.bow(gaston); }
}).start();
new Thread(new Runnable() {
public void run() { gaston.bow(alphonse); }
}).start();
}
}
// thread 1
getLocks12(lock1, lock2)
{
lock1.lock();
while (lock2.locked())
{
// attempt to step aside for the other thread
lock1.unlock();
wait();
lock1.lock();
}
lock2.lock();
}
// thread 2
getLocks21(lock1, lock2)
{
lock2.lock();
while (lock1.locked())
{
// attempt to step aside for the other thread
lock2.unlock();
wait();
lock2.lock();
}
lock2.lock();
}
PPE-110 and SPEs 120-134
http://www.tkt.cs.tut.fi/kurssit/9636/K05/Chapters14-15.pdf
http://java.sun.com/docs/books/tutorial/essential/concurrency/deadlock.html
http://stackoverflow.com/questions/1036364/good-example-of-livelock
http://www.freepatentsonline.com/y2008/0071955.html
Livelock differs from deadlock in that livelock has “2 or more processes continuously change their state in response to changes in the other process(es) without doing any useful work.” An example of this is 2 people trying to build an arch with only 1 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.” A method used to resolve livelock is the use of the DAA (Deadlock Avoidance Algorithm), which has one of the processes let go of its resources. Algorithm 2 DAA or Algorithm 3 DAA can be used. Algorithm 3 in hardware is better to use because it resolves livelock more actively and efficiently than algorithm 2. Both approaches are listed below.
Algorithm 2. DAA (approach 2)
DAA (event)
1 case (event)
2 a request:
3 if the resource is available
4 grant the resource to the requester
5 else if the request would cause request deadlock (R-dl)
6 deny the request and inform the potential R-dl (i.e., livelock)
(let the requester take care of this livelock situation)
7 else
8 make the request be pending
9 end-if
10 break;
11 a release:
12 if any process is waiting for the released resource
13 if the grant of the resource would cause grant deadlock
14 grant the resource to a lower priority process waiting
15 else
16 grant the resource to the highest priority process waiting
17 end-if
18 else
19 make the resource become available
20 end-if
21 end-case
Algorithm 3. DAA (approach 3)
DAA (event) f
1 case (event) f
2 a request:
3 if the resource is available
4 grant the resource to the requester
5 else if the request would cause request deadlock (R-dl)
6 if the priority of the requester greater than that of the owner
7 make the request be pending
8 ask the current owner of the resource to release the resource
9 else
10 ask the requester to give up resource(s)
11 end-if
12 else
13 make the request be pending
14 end-if
15 break
16 a release:
17 the same as Algorithm 2
18 g end-case
http://www.cs.rpi.edu/academics/courses/fall04/os/c10/index.html
http://www.cocoadev.com/index.pl?LiveLock
http://codesign.ece.gatech.edu/publications/jaehwan/paper/codes_2004.pdf
Deadlock is the state in which the whole system is locked up as a result of all resources being locked up by the processes and can neither allocate or deallocate any of the resources to free the deadlock.
Livelock is a state when processes are locked waiting on a vital resource to finish processing a job, however they are not locked from continuing to work within its own process, thereby slowing down processing to almost a standstill, or entering them into a continuous loop waiting for the other process to complete and release the require resource…example:
Process A executes file A
Process B executes file B
Process A requires file B to complete file A
Process B will not release file B until complete
Process B requires file A to complete file B
Process A will not release file A until complete
Process B releases file B line by line, allowing process A to execute, however,
Process B continues to release file B one line at a time from the beginning each time.
Process A performs the same action, releasing only one line at a time from the beginning of file each time.
Process A restarts entire file A processing every time it receives data from Process B.
Process B restarts entire file B processing every time it receives data from Process A.
Since the size of the files is unknown, the processing is locked into a slow loop until Process B is complete and releases file B to Process A, or vice versa.
http://www.cocoadev.com/index.pl?LiveLock
https://netfiles.uiuc.edu/jkelm2/www/kelm-rtm-livelock.pdf
http://sendhil.spaces.live.com/blog/cns!30862CF919BD131A!367.entry
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. Livelock is a special case of resource starvation; the general definition only states that a specific process is not 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.
Livelock is a risk with some algorithms that detect and recover from deadlock. If more than one process takes action, the deadlock detection algorithm can repeatedly trigger. This can be avoided by ensuring that only one process takes action
According to yourdictionary.com, Livelock refers to an endless loop in program execution. It occurs when a process repeats itself, because it continues to receive erroneous information. It can also occur when a process that calls another process is itself called by that process, and there is no logic to detect this situation and stop the operation.
According to Springer Berlin, in a network environment, a Livelock is a situation in which packets keep moving indefinitely in a network without any packet ever reaching its destination. It is known that even maximum advance algorithms might livelock on some networks.
A Livelock differs from a “deadlock”, in that the processing still continues to take place, rather than just waiting in an idle loop. It is similar to a deadlock except that neither process is blocked nor waiting; both are in a continuous state of change.
An example of a Livelock according to cocoadev.com, occurs in Atomic Thread Safety if one accessor locks the system then sleeps, if there is no mechanism in place to block another thread if it tries to access the data that thread will spin over the same instructions until it is slept automatically - a simple case of Livelock.
A more 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.
Two different methods the operating system could use to detect and resolve Livelock:
1)Prevention. Prevent one of the four conditions from occurring: mutual exclusion, resource holding, no preemption, and circular wait.
2)Avoidance. Using the Banker’s Algorithm by Dijkstra.
In summary, Livelock is a form of deadlock. If a system doesn’t support prevention or avoidance then it must be prepared to detect and recover from the livelocks and deadlocks that will occur.
Michael Simpson
References:
http://www.yourdictionary.com/computer/livelock
http://www.springerlink.com/content/k5luq4vl756qgr3q/
http://www.cocoadev.com/index.pl?LiveLock
Deadlock is a situation when two processes, each having a lock on one piece of data, attempt to acquire a lock on the other's piece. Each process would wait indefinitely for the other to release the lock, unless one of the user processes is terminated. SQL Server detects deadlocks and terminates one user's process.
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. Another way Operating Systems avoid livelock is through polling. A livelock also occurs when read transactions monopolize a table or page, forcing a write transaction to wait indefinitely.
http://dba.fyicenter.com/Interview-Questions/SQL-Server-DBA/What_is_a_deadlock_and_what_is_a_live_lock_How_.html
http://www.stanford.edu/class/cs240/readings/mogul.pdf
Livelock is 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 is 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. A deadlock is also called a deadly embrace.
Livelock can be resolved with a design structure for resolving the occurrence of livelock at the interface between the processor core and memory subsystem controller. 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.
Ted McHugh
http://www.faqs.org/patents/app/20080301374
http://www.webopedia.com/TERM/L/livelock.html
http://www.webopedia.com/TERM/D/deadlock.html
Livelock is a lot like deadlock, except that is is always actively trying to fix the situation, but going nowhere. It is called a special case of “resource starvation” in which a certain process is not progressing. It is different from deadlock because it is actively trying to get the job done. With deadlock the process can’t even begin because it is waiting for another process to end..and neither ever do.
http://www.allinterview.com/showanswers/23533.html
I used this source and inquired about the aformentioned situations in a poker game Sunday night. I hope it is sufficient.
Ryan O’Neal
Livelock is slightly different from deadlock (both involve process waiting for resources to free up while at the same time blocking each other) livelock differs in that the processes are in a constant state of change.
An example would be two people trying to pass each other in a narrow hallway. Both try to move around one another but continually block each others movement.
They can be prevented with mutual exclusion, and resource holding.
http://www.mathworks.com/access/helpdesk/help/toolbox/simevents/ug/bqwdoak.html
http://en.wikipedia.org/wiki/Deadlock
Livelock occurs when a process repeats itself.It also can occur when another process itself is called by that process, and there is no logic to detect this situation and stop the operation. A livelock differs from a "deadlock," in that processing continues to take place, rather than just waiting in an idle loop.
Catherine Alexander
Catherine Alexander i forgot to put my sources so here they are
www.amswers.com
enx.org
Livelock is a situation of constant motion but, achieving no forward progress. Livelock shares the "stand still" with Deadlock. Livelock can lead to; Starvation: Systems with a non-zero service
cost and unbounded input rate may experience
starvation. For example, if an operating system
kernel spends all of its time servicing interrupts
then user processes will starve and Infinite Execution: The individual processes of
an application may run successfully, but the application
as a whole may be stuck in a loop [15].
For example, a natıve browser loads web page A
that redirects to page B that erroneously redirects
back to page A. Another example is a
process stuck traversing a loop in a corrupted
linked list. Some of the ways of the that livelock can be avoided is implementing Mutual exclusion and Semaphores. Another example of Livelock, 2 threads detect deadlock and try to step around each other. If not programmed correctly they will get stuck in a loop of "side stepping" Here is the code example:
// thread 1
getLocks12(lock1, lock2)
{
lock1.lock();
while (lock2.locked())
{
// attempt to step aside for the other thread
lock1.unlock();
wait();
lock1.lock();
}
lock2.lock();
}
// thread 2
getLocks21(lock1, lock2)
{
lock2.lock();
while (lock1.locked())
{
// attempt to step aside for the other thread
lock2.unlock();
wait();
lock2.lock();
}
lock2.lock();
}
Jesse L.
Sources:
http://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-633.pdf
http://www.wotug.org/paperdb/send_file.php?num=40
http://stackoverflow.com/questions/1036364/good-example-of-livelock
http://www.cocoadev.com/index.pl?LiveLock
Flippant comments aside, one example which is known to come up is in code which tries to detect and handle deadlock situations. If two threads detect a deadlock, and try to "step aside" for each other, without care they will end up being stuck in a loop always "stepping aside" and never managing to move forwards.
By "step aside" I mean that they would release the lock and attempt to let the other one acquire it. We might imagine the situation with two threads doing this (pseudocode):
// thread 1
getLocks12(lock1, lock2)
{
lock1.lock();
while (lock2.locked())
{
// attempt to step aside for the other thread
lock1.unlock();
wait();
lock1.lock();
}
lock2.lock();
}
// thread 2
getLocks21(lock1, lock2)
{
lock2.lock();
while (lock1.locked())
{
// attempt to step aside for the other thread
lock2.unlock();
wait();
lock2.lock();
}
lock2.lock();
}
Race conditions aside, what we have here is a situation where both threads, if they enter at the same time will end up running in the inner loop without proceeding. Obviously this is a simplified example. A naiive fix would be to put some kind of randomness in the amount of time the threads would wait.
The proper fix is to always respect the lock heirarchy. Pick an order in which you acquire the locks and stick to that. For example if both threads always acquire lock1 before lock2, then there is no possibility of deadlock
http://stackoverflow.com/questions/1036364/good-example-of-livelock
Richard
Livelock is slightly different from deadlock (both involve process waiting for resources to free up while at the same time blocking each other) livelock differs in that the processes are in a constant state of change.
An example would be two people trying to pass each other in a narrow hallway. Both try to move around one another but continually block each others movement.They can be prevented with mutual exclusion, and resource holding.
according to "java.sun.com" livelock is 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: Alphonse moves to his left to let Gaston pass, while Gaston moves to his right to let Alphonse pass. Seeing that they are still blocking each other, Alphone moves to his right, while Gaston moves to his left. They're still blocking each other.
A deadlock is a situation where in two or more competing actions are waiting for the other to finish, and thus neither ever does. It is often seen in a paradox like the "chicken or the egg."
“ When two trains approach each other at a crossing, both shall come to a full stop and neither shall start up again until the other has gone.
Deadlock happens when data going throug is stopped with no place to go. In both situations there is no productivity and they both require immediate attention. there are different ways in which one can deal with this problem. it is like there is a lock with no room for people to move around and are stuck in their tracks. there have be space made to allow things to continue on.
livelock occurs when multiple processes constantly change state making the system unable to resolve. In deadlock the processes wait for the other to resolve, neither doing anything. Its the swaying strangers vs. the goofy gophers.
http://www.webopedia.com/TERM/L/livelock.html
Post a Comment
<< Home