Deadlock, Starvation and Livelock | Operating System - Computer Science Engineering (CSE) PDF Download

Deadlock

A deadlock occurs when each member of a group of actions is waiting for another member to release a lock. In contrast, a livelock is similar to a deadlock, but in a livelock, the states of the processes constantly change relative to each other, with none making any progress. Thus, livelock is a special case of resource starvation, as it involves processes that are not progressing.

Starvation

• Starvation is a problem closely related to both livelock and deadlock.
• In a dynamic system, requests for resources are continuous, necessitating a policy to decide who gets the resource and when.
• Even with a reasonable policy, some processes may never get serviced, despite not being deadlocked.
• Starvation occurs when certain threads, often described as "greedy," monopolize shared resources for extended periods.
• This makes resources unavailable to other threads.
• For example, consider an object with a synchronized method that takes a significant amount of time to complete.
• If one thread calls this method frequently, other threads needing synchronized access may frequently find themselves blocked.

Livelock

Livelock occurs when two or more processes endlessly repeat the same interaction, continuously responding to changes in each other without making any progress. Unlike deadlock, where all processes are in a waiting state, processes in livelock are actively running concurrently but unable to perform any useful work.

Each of the two processes requires two resources and uses the polling primitive enter_reg to attempt to acquire the necessary locks. If the attempt fails, the process simply tries again. For instance, if Process A acquires Resource 1 first and Process B acquires Resource 2, neither process will make further progress, regardless of which one runs next. Instead of blocking, both processes repeatedly consume CPU time without making progress. This scenario is not a deadlock, as no process is blocked, but it is functionally equivalent to a deadlock: livelock.

What leads to Livelock? 

• Livelock can arise in unexpected ways.
• In some systems, the maximum number of allowed processes is limited by the number of entries in the process table.
• This makes these table slots finite resources.
• If a fork operation fails due to a full table, a reasonable approach is to wait for a random time before trying again.
• For instance, consider a UNIX system with 100 process slots.
• If ten programs are running and each needs to create 12 subprocesses, the table will be exhausted after each process creates 9 subprocesses.
• At this point, the 10 original processes and the 90 new ones will have filled the table.
• The original processes will then enter an endless loop of forking and failing.
• This situation is essentially a deadlock.
• Although the probability of this occurring is low, it is still possible.

Difference between Deadlock, Starvation, and Livelock

A livelock is similar to a deadlock, but in a livelock, the states of the involved processes constantly change relative to each other, with none making any progress. Livelock is a specific form of resource starvation in which a particular process is unable to make progress.