Synchronization - Part 2

How to write concurrent code correctly and avoid problems like deadlocks and starvation.

Hi Friends,

Welcome to the 99th issue of the Polymathic Engineer newsletter.

This week, we will complete our deep dive into processes and thread synchronization by focusing on the challenges of writing concurrent code.

Here is the outline:

• Deadlock

• Starvation

• Priority inversion

• Readers-writers problem

• Producer-consumer problem

• Dining philosophers problem

• Monitors

Deadlock

In the previous article, we discussed how it's possible to synchronize multiple threads using mutexes and semaphores. However, we didn't analyze the problems that could arise if such primitives were not handled carefully.

The most well-known issue is deadlock. Deadlocks occur when two or more threads wait indefinitely for each other to release resources. You can think of it as a traffic jam where cars block each other's paths, and no one can move.

The following example helps to understand how a deadlock can happen:

Thread A                          Thread B

wait(semaphore_1);                wait(semaphore_2);
wait(semaphore_2);                wait(semaphore_1);
...                               ...
signal(semaphore_1);              signal(semaphore_2);
signal(semaphore_2);              signal(semaphore_1);

In this scenario, we're in trouble if A executes wait(semaphore_1) and B executes wait(semaphore_2). A will be waiting for semaphore_2, which B holds, while B waits for semaphore_1, which A holds. Neither thread can proceed, resulting in a deadlock.

In general, a deadlock can involve multiple threads in a circular wait condition. The key characteristic is that every thread in the set waits for an event that can only be caused by another thread.

Starvation

Starvation is a related but different problem. It occurs when a thread never obtains the resources it needs to complete its task. Unlike deadlock, where all involved processes are stuck in starvation, some processes continue to execute while others keep waiting indefinitely.

For instance, consider a scenario where we remove processes from a semaphore's waiting list in a Last-In-First-Out (LIFO) order. If new processes keep arriving and getting priority, older processes might never get their turn, leading to starvation.

To avoid starvation, we have to design our synchronization mechanisms carefully.

Some approaches you can use are ensuring that all processes request resources in the same order or using timeouts when waiting for resources to avoid indefinite waits.