Deadlock in Multithreaded Applications- Deadlock Vs Livelock

 

Deadlock in Multithreaded Applications

In a multithreaded application, multiple threads often need to share resources such as mutex locks, semaphores, files, or I/O devices. These resources are typically non-sharable, meaning that only one thread can use them at a time.

To access a shared resource safely, threads use mutex locks:

• A thread locks the mutex before entering a critical section

• The thread unlocks the mutex after finishing

• If a mutex is already locked, any thread attempting to lock it will block

If mutex locks are not acquired and released carefully, threads may enter a state where none of them can proceed. This situation is known as deadlock.

---

Example: Deadlock Using POSIX Mutex Locks

Consider two mutex locks:

• first_mutex

• second_mutex

And two threads:

• Thread One

• Thread Two

Thread One

pthread_mutex_lock(&first_mutex);
pthread_mutex_lock(&second_mutex);
/* critical section */
pthread_mutex_unlock(&second_mutex);
pthread_mutex_unlock(&first_mutex);

Thread Two

pthread_mutex_lock(&second_mutex);
pthread_mutex_lock(&first_mutex);
/* critical section */
pthread_mutex_unlock(&first_mutex);
pthread_mutex_unlock(&second_mutex);

---

How Deadlock Occurs

Deadlock can occur under the following sequence:

1. Thread One acquires first_mutex

2. Thread Two acquires second_mutex

3. Thread One waits for second_mutex

4. Thread Two waits for first_mutex

At this point:

• Thread One holds first_mutex and waits for second_mutex

• Thread Two holds second_mutex and waits for first_mutex

• Neither thread can proceed

➡️ Deadlock has occurred

---

Why Deadlock Is Hard to Detect

• Deadlock depends on thread scheduling

• It may only occur under specific timing conditions

• The same program may:

  • Run correctly many times

  • Suddenly deadlock under a different schedule

This makes deadlock difficult to reproduce, test, and debug.

---

Livelock

Livelock is another form of liveness failure, similar to deadlock but fundamentally different in behavior.

Definition

Livelock occurs when threads are not blocked, but they continuously retry actions that fail, making no progress.

---

Example: Livelock Using pthread_mutex_trylock()

• Threads attempt to acquire a lock using trylock()

• If the lock is unavailable, they release held locks and retry

• If both threads retry at the same time, they may interfere indefinitely

Result

• Threads keep running

• Locks are repeatedly acquired and released

• No thread completes its work

---

Real-World Analogy

• Deadlock: Two people block each other in a doorway and stop moving

• Livelock: Two people keep stepping aside for each other, but still block progress

---

Deadlock vs Livelock

Aspect	Deadlock	Livelock
Thread state	Blocked	Running
CPU usage	No	Yes
Progress	None	None
Cause	Circular waiting	Repeated retries
Resolution	Break deadlock conditions	Introduce randomness or backoff

---

Avoiding Livelock

• Introduce random delays before retrying

• Use exponential backoff

• Avoid simultaneous retries

This technique is widely used in networking protocols such as Ethernet.

---

Key Takeaways 

• Deadlock occurs when threads block forever, waiting on each other

• Livelock occurs when threads actively run but fail to make progress

• Both are liveness failures

• Careful lock ordering and retry strategies are essential in multithreaded design