1. Introduction

While studying deadlocks, we often focus on situations where processes become permanently blocked and stop executing. However, there exists another concurrency problem that is equally important but often more difficult to identify: Livelock.

In a livelock situation, processes are not blocked. They continue executing, responding to events, and changing their states. Despite this activity, no useful work is completed and the system makes no actual progress.

Thus, although deadlock and livelock appear different in behavior, both ultimately prevent processes from accomplishing their intended tasks.

Understanding the distinction between deadlock and livelock is important for designing robust synchronization and resource-allocation mechanisms.

2. Definitions

2.1 Deadlock

A deadlock is defined as:

A condition in which a set of processes are permanently blocked because each process is waiting for a resource held by another process in the set.

Characteristics:

• Processes are blocked

• No process can proceed

• Resources remain allocated

• System progress stops completely

2.2 Livelock

A livelock is defined as:

A condition in which processes continuously change their states in response to each other but fail to make any useful progress.

Characteristics:

• Processes remain active

• State changes continue

• CPU execution continues

• Useful work never completes

3. Fundamental Difference

The key distinction can be summarized as:

Deadlock
=
Waiting Forever

Livelock
=
Trying Forever
Without Success

In deadlock:

Processes Stop

In livelock:

Processes Keep Moving

but progress remains impossible.

4. Conceptual Visualization

Deadlock

P1 waits for P2
P2 waits for P1

Result:

No Movement
No Progress

Processes remain blocked indefinitely.

Livelock

P1 retries
P2 retries

P1 retries again
P2 retries again

P1 retries again
P2 retries again

Result:

Continuous Activity
No Progress

5. Deadlock Example

Consider two resources:

Resource A
Resource B

Two processes:

P1
P2

Step 1

P1 acquires:

Resource A

Step 2

P2 acquires:

Resource B

Step 3

P1 requests:

Resource B

and waits.

Step 4

P2 requests:

Resource A

and waits.

State:

P1 holds A → waiting for B

P2 holds B → waiting for A

Neither process can proceed.

Result:

Deadlock

6. Livelock Example

Suppose two processes attempt to avoid deadlock by releasing resources whenever contention occurs.

Step 1

P1 requests resource.

Step 2

P2 requests same resource.

Step 3

P1 notices conflict and backs off.

Step 4

P2 also notices conflict and backs off.

Step 5

Both retry simultaneously.

Step 6

Conflict occurs again.

Step 7

Both back off again.

Cycle:

Try
↓
Fail
↓
Retry
↓
Fail
↓
Retry

repeats forever.

Result:

Livelock

Processes execute continuously but never complete.

7. Detailed Comparison

8. Why Livelock Occurs

Livelock often occurs when processes attempt to be "too cooperative."

Instead of waiting:

Process Releases Resource

and retries.

If multiple processes behave similarly:

Release
Retry
Release
Retry
Release
Retry

they may continuously interfere with one another.

The system remains active but achieves nothing.

9. Common Causes of Livelock

9.1 Excessive Retrying

Processes repeatedly retry failed operations.

Example:

Acquire Lock
↓
Fail
↓
Retry Immediately

Repeated endlessly.

9.2 Aggressive Deadlock Prevention

Some deadlock prevention mechanisms repeatedly release and reacquire resources.

Improper implementation may create livelock.

9.3 Symmetric Behavior

When competing processes react identically.

Example:

Both Back Off
Both Retry
Both Back Off
Both Retry

This creates endless synchronization conflicts.

10. Real-World Analogy

Deadlock Analogy

Imagine two cars facing each other on a very narrow road.

Neither driver reverses.

Car A waits
Car B waits

Result:

Traffic Stopped

This is deadlock.

Livelock Analogy

Imagine two people walking toward each other in a hallway.

Both attempt to avoid collision.

Both move left

Collision avoided?

No.

Then:

Both move right

Again:

Both move left

Again:

Both move right

This continues indefinitely.

They remain active but cannot pass.

This is livelock.

11. Livelock in Operating Systems

Livelock can appear in:

• Lock acquisition protocols

• Network protocols

• Database systems

• Distributed systems

• Deadlock recovery mechanisms

Particularly in systems using:

Retry-Based Recovery

or

Backoff Strategies

without proper coordination.

12. Relationship with Deadlock Prevention

Interestingly, some deadlock prevention techniques can accidentally introduce livelock.

Example:

Process A releases resource

to avoid deadlock.

Simultaneously:

Process B releases resource

Both retry immediately.

Conflict repeats forever.

Thus:

Deadlock Prevented

but

Livelock Created

13. Detecting Livelock

Detecting livelock is more difficult than detecting deadlock.

Reason:

Processes Are Still Running

The operating system observes:

• CPU activity

• State transitions

• Resource requests

Everything appears active.

Yet:

No Useful Work Completes

This makes automated detection challenging.

14. Techniques to Prevent Livelock

Several strategies are used to prevent livelock.

14.1 Randomized Backoff

Instead of retrying immediately:

Wait Random Time

before retrying.

Example:

P1 waits 2 ms

P2 waits 7 ms

Their actions become desynchronized.

This greatly reduces livelock probability.

14.2 Retry Limits

Allow only a limited number of retries.

Example:

Maximum Retries = 5

After that:

Use Alternative Strategy

14.3 Priority-Based Access

Assign priorities.

Example:

Higher Priority Process Proceeds

while others wait.

This prevents endless mutual backing off.

14.4 Fair Scheduling

Ensure every process eventually receives service.

Fairness mechanisms reduce repeated conflicts.

15. Deadlock vs Livelock vs Starvation

16. System Impact

Deadlock Impact

Resources Locked
CPU Mostly Idle
System Frozen

Livelock Impact

Resources Constantly Used
CPU Consumed
No Useful Output

Livelock may actually waste more CPU time than deadlock because processes continue executing useless operations.