Deadlock, Livelock, Race condition and Starvation

Circle of hands from bemeyes

Deadlock, Livelock, Race condition and Starvation are the four nightmares when you develop a multi-threaded application. This article covers a detailed explanation of these with general examples.

1. Deadlock

Assume there is a traffic intersection where there are multiple roads that converge at a single intersection without any traffic lights. If multiple vehicles approach the intersection from all the roads at the same time, but there is not enough space for all the vehicles to move simultaneously, they may end up deadlocked.

Each driver may wait for the other to go first, but neither can move without the other and as a result, they both end up stuck and unable to proceed. This can cause a traffic jam.

This kind of problem occurs in the compute programs too when multiple threads try to access a shared resource like a file or a printer. For instance, there are two threads T1 and T2 both running. Both threads want to read the same file and print its content in a printer.

• T1 has acquired the lock on the file abc.doc. T2 has acquired the lock on the printer.
• T1 wants to acquire the printer to print the file, however, the printer has been locked by T2.
• T2 wants to acquire the file abc.doc to print it, however, the file has been locked by T1.
• Both T1 and T2 will not release the locks forever, both will not acquire the resources forever.
• This situation is a deadlock.

2. Livelock

Imagine you are walking in a narrow hallway. Another person walks on the opposite side and you both meet face-to-face. Now you both are trying to pass each other, and both of you keep moving to the same side to let the other pass, you may end up in a livelock where you keep blocking each other’s way and are unable to move forward.

This kind of problem happens in computers too where two or more processes or threads are blocked and unable to make progress but constantly changing their state in response to changes made by other processes or threads, without making any real progress towards completing their tasks. This can result in a frustrating and unproductive situation in the computer systems.

Let’s take the same printer example from the above deadlock section.

• T1 has acquired the lock on the file and waiting for the printer to print the file, but the printer has been locked by T2.
• T2 has acquired the lock on the printer and waiting for the file, but the file has been locked by T2.
• After some time, at the same time, both threads realize that they will not get the lock, it releases their lock.

• Now it's possible that earlier, T1 will acquire the lock on the Printer and T2 will acquire the lock on the file.
• T1 wants to acquire the file, which has been locked by T2. T2 wants to acquire the printer, which has been locked by T1.

• This will continue to exchange the resources forever. Both threads will never acquire the file and printer at the same time. This situation is called Livelock.

The difference between deadlock and livelock is, In the deadlock situation, two threads wait for another resource forever without releasing the acquired lock.

Whereas, in the livelock, both the thread release their lock at some point, however, both will not acquire all the resources they needed. They end up in keep trying forever and wasting the compute resources.

3. Race Condition

Imagine you and your girlfriend (or boyfriend) are using a common bank account which has a current balance of $100.

You both access the account at the same time and attempt to withdraw money from it. You want to withdraw $20 and your girlfriend wants to withdraw $30. After both withdrawals, don’t you expect the account balance to be $50? ($100 — $20 — $30 = $50).

Let’s see how a system handles this transaction concurrently.

• You read the account balance as $100
• Your girlfriend also read the current balance as $100
• You withdraw $20 and update the current balance to $80
• Your girlfriend withdraw $30, without reading the most up-to-date balance, update the balance as $70

This is how a poorly written system will handle concurrent transactions. This situation is called the Race condition.

The Race condition is the most common issue in multi-threaded applications. The behaviour of a program or system depends on the order and timing of different events or processes. When multiple processes or threads access shared resources (e.g. variables, files, databases) concurrently and in an unpredictable order, a race condition may arise. It can cause unexpected and unpredictable behaviour in a program, such as data corruption, program crashes, or incorrect results.

To avoid race conditions, developers need to use synchronization techniques such as locks, semaphores, or monitors to ensure that only one thread or process can access shared resources at a time, or use atomic operations to perform a single, indivisible operation on a shared resource, or use data versioning, during every update, check if the version of the current data matches the version when you read the data.

4. Starvation

Imagine you are in a restaurant waiting to be served, but the waiter is serving only a few customers who have been VIPs. You and other customers are hungry and waiting for your food to arrive. As a result, you will wait for an extended period, unable to receive the food, even though the necessary resources (cooks and waiters) are available. In this scenario, the VIP customers are receiving priority treatment, while the other customers are being starved of the resources they need to have their orders processed. You will be starved.

Starvation occurs in computing when a process is unable to get the resources it needs to make progress, even though the resources are available. In other words, the process is blocked or delayed indefinitely, unable to complete its work.

Starvation can happen due to various reasons, such as a resource being held by a higher-priority process, a scheduling algorithm that does not fairly allocate resources, or a system that is overloaded.

Starvation can have serious consequences for a system’s performance and can cause the affected process to become unresponsive or crash. Starvation is especially problematic in real-time systems where processes must meet strict deadlines and delays can have severe consequences.

To avoid starvation, you need to use a fair scheduling algorithm, that ensures no process is consistently denied the resource it needs. Additionally, you can monitor the system for signs of starvation and adjust system parameters as needed to ensure that processes have access to the resources they need to make progress.

Conclusion

Deadlock, livelock, race condition, and starvation can arise in concurrent computing. They lead to unpredictable results, crashes and unresponsive processes, which can have severe consequences in real-time systems. To prevent these problems, synchronization techniques, scheduling algorithms, and resource allocation policies must be used to ensure fair and consistent access to resources. By implementing these strategies, concurrent systems can operate efficiently and reliably, improving their overall performance.