Livelock in Operating System

In the case of a livelock, the OS repeatedly denies a request for an exclusive lock. This happens because many overlapping shared locks interfere with each other. Processes constantly change their status, further preventing them from completing the task.

Examples of Livelock

When two cars come face-to-face on a road and both of them move aside to let the other pass, they end up making zero progress. In fact, they waste their energy instead by moving the same way at the same time. Thus, they are unsuccessful in crossing each other.

Another example of livelock is when two processes need two resources. They use the primitive polling enter registry in order to acquire the necessary locks. If one attempt fails, another attempt is made.
Let’s assume that,

• Process A hold Y resource
• Process B holds resource X
• Process A require X resource
• Process B require Y resource

Let process A run first and acquire data resource X followed by process B that acquires resource Y. Irrespective of the process that runs first, none of the processes can further progress successfully. None of these processes are blocked, instead, they repeatedly exhaust CPU resources without making any progress and stop any processing block.

What Leads to Livelock?

When the total number of allowed processes in a system is defined by the total number of entries in the process table, livelock occurs. This is the reason why process table slots are known as Finite Resources.

Deadlock

A process enters the waiting state when another process holds the required resource. This situation is called a deadlock. Multiple processes share a specific type of resource in a multiprocessing OS called soft-lock or software. These resources are mutually exclusive. One of the examples of deadlock is one directional traffic, where a bridge is a resource.

Starvation

Starvation occurs when low priority processes get blocked by high priority processes during scheduling. It happens when shared resources are made unavailable by some threads for a long period of time.

Deadlock vs Starvation vs Livelock

A deadlock occurs when a process enters a waiting state as another waiting process is holding the resource it holds. Though similar to deadlock, in a livelock the states of the involved processes keep on changing to one another, without any progress. Thus, a livelock is a unique case of resource starvation.

In livelock, two or more processes repeat the same interaction continually without doing any useful work when changes in other processes occur. This is where livelock is different from deadlock as unlike in livelock, processes in deadlock are in the waiting state instead of running concurrently.

Following is the code for livelock:

var l1 = .... 
var l2 = .... 
      
        // First Thread
        Thread.Start( ()=> { 
              
    while (true) { 
          
        if (!l1.Lock(1000)) { 
            continue; 
        } 
          
        if (!l2.Lock(1000)) { 
            continue; 
        } 
          
    }); 
  
        //Second Thread 
        Thread.Start( ()=> { 
              
        while (true) { 
              
            if (!l2.Lock(1000)) { 
                continue; 
            } 
              
            if (!l1.Lock(1000)) { 
                continue; 
            } 
              
        }); 

Below is the code for deadlock:

var p = new object(); 
lock(p) 
{ 
    lock(p) 
    { 
        // deadlock as p is previously locked and we’ll never reach here... 
    } 

Following is the code for starvation:

Queue q = ..... 
  
          while (q.Count & gt; 0) 
{ 
    var c = q.Dequeue(); 
    ......... 

        q.Enqueue(c); 
    q.Enqueue(c); 
} 

Summary

In the case of a livelock, the OS repeatedly denies a request for an exclusive lock. Starvation occurs when low priority processes get blocked by high priority processes during scheduling. In livelock, processes run concurrently whereas in deadlock processes are in a waiting state.