Differences (if any) among livelock and starvation in Operating systems

What are the differences (if any) am开发者_如何学运维ong the starvartion and livelock Or just they are the synonyms used? If there is a difference please some one afford an example.

Note: I have seen the wikipedia...but confused...

Thanks

Livelock is a special case of resource starvation where two processes follow an algorithm for resolving a deadlock that results in a cycle of different locked states because each process is attempting the same strategy to avoid the lock.

Starvation itself can occur for one process without another process being cyclically blocked; in this case no livelock exists, just a single unfortunate process that gets no resources allocated by the scheduler.

Starvation and Livelock (by Java docs) state:

Starvation and Livelock

Starvation and livelock are much less common a problem than deadlock, but are still problems that every designer of concurrent software is likely to encounter.

Starvation

Starvation describes a situation where a thread is unable to gain regular access to shared resources and is unable to make progress. This happens when shared resources are made unavailable for long periods by "greedy" threads. For example, suppose an object provides a synchronized method that often takes a long time to return. If one thread invokes this method frequently, other threads that also need frequent synchronized access to the same object will often be blocked.

Livelock

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, so...

LiveLock

Livelock is a form of deadlock. In a deadlocked computation there is no possible execution sequence which succeeds. but In a livelocked computation, there are successful computations, but there are one or more execution sequences in which no process enters its critical section.

#Example scenario

process P1

c1 = 1 
c2 = 1
while (true){
 nonCriticalSection;
 c1 = 0;
 while(c2!=1){
  c1=1; 
  c1=0;
 }
 criticalSection1;
 c1 =1;
}

process P2

c1 = 1 
c2 = 1
while (true){
 nonCriticalSection;
 c2 = 0;
 while(c1!=1){
  c2=1; 
  c2=0;
 }
 criticalSection1;
 c2 =1;
}

In this scenario, How can starvation happen?

For example,

1. P1 sets c1 to 0
2. P2 sets c2 to 0
3. P2 checks c1 and resets c2 to 1.
4. P1 completes a full cycle;
   • checks c2
   • enters critical section
   • resets c1
   • enters non-critical section
   • sets c1 to 0
5. P2 sets c2 to 0

So now the same thing happens again and again, so P1 again may get a chance to execute and P2 will be stuck in the while loop. We don't force our algorithm to give a chance to P2. P1 may run a million times even before P2 gets a chance from OS since we don't enforce anything. So which means there can be some sequence that P2 starved. Since P1 can process and P2 starves, we call sequences as starvation.

Livelock is actually both threads that will be stuck in a while loop without doing anything. Since the above lines may give livelock the same as deadlock but the deadlock you don't do anything. but in live lock, some instructions will be executed but these executing instructions are not enough to allow a process to its critical section.

In this above pseudo-code how livelock will see with following line of executions.

1. P1 sets c1 to 0.
2. P2 sets c2 to 0.
3. P1 checks c2 and remains in the loop.
4. P2 checks c1 and remains in the loop.
5. P1 resets c1 to 1.
6. P2 resets c2 to 1.
7. P1 resets c1 to 0.
8. P2 resets c2 to 0.

P1 and P2 will be in the while loop doing some executions.

Difference from deadlock and livelock

When deadlock happens, No execution will happen. but in livelock, some executions will happen but those executions are not enough to enter the critical section.

Difference between Livelock and Starvation

In starvation, some processes will enter the critical section while some of them are not allowed to critical section due to some reasons(os scheduling, priority) but in livelock, the Critical section will be empty and processes are competing to enter the critical section with doing soemthing.