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

Question

What are the differences (if any) among 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

Answer 1

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.

Answer 2

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.