Deadlock is a very important topic in operating systems. Understanding the concepts is really important. In this article, we will critically analyze deadlock. We will also discuss starvation and livelock. We will differentiate all three terms using examples.
The first section will discuss deadlock. We will learn about the mandatory conditions for deadlock. The other two sections will cover starvation and livelock, respectively.
Key difference between Deadlock, Starvation and Livelock
Deadlock occurs when two or more processes are unable to proceed because each is waiting for the other to release a resource. Essentially, it's a situation where processes are stuck in a circular dependency, unable to progress without the release of resources held by another process.
On the other hand, starvation happens when a process is perpetually denied access to the resources it needs to execute. This denial often occurs because higher-priority processes continually seize the resources, leaving lower-priority processes without the necessary resources to complete their tasks.
Livelock occurs when multiple processes continuously change their states in response to each other's actions, but no progress is made in the system as a whole. It's akin to a deadlock in that processes are unable to proceed, but in livelock, they are actively trying to resolve the situation, resulting in a futile loop of activity without any actual progress being made.
Deadlock
A set of processes are said to be in deadlock if they wait for the happening of an event caused by other processes in the same set. In simple terms, a set of processes are in deadlock if a process, which has been allocated a resource, is waiting for some other process to release a resource which in turn is waiting for the previous process to do the same.
Before we move on to understanding deadlock, let's discuss a practical example of deadlock. Suppose you visit a bookstore to purchase a book on operating systems. You insist that you should be handed over the book before the payment to the owner of the bookstore, while the owner insists that you should pay him first before he gives you the book. In this case, you both are stuck. Neither you are able to get the book, nor the bookstore owner is able to get the money.
Consider the figure below:
There are two resources R1 and R2. In a computer system, a resource can be a file, memory, printer, etc. We also have two processes P1 and P2. When process P1 requests the Operating System for resource R2, the operating system allocates R2 to P1. Similarly, R1 is allocated to P2. Now, P1 again requests the operating system for resource R1, which is currently being held by process P2. P2 requests the operating system for another resource R2, which is currently being held by P1. However, P1 cannot release R2 unless it gets R1. Similarly, P2 cannot release R1 unless it gets R2. This condition where one process is unable to complete its execution because it is requesting for a resource which in turn is held by another process that is also requesting a resource from the current process, is known as deadlock. In such a case, none of the processes is willing to free the resource.
For meeting the mutual exclusion condition, one or more resources should be non-shareable. Suppose there is a single printer( resource) and there are two processes that are requesting the printer at the same time. A deadlock may arise if none of the processes are able to use the printer and wait for an infinite time.
Hold and wait
For a deadlock to occur, one of the processes must hold a resource and wait for the other resource. From the above example, we can see that process P1 holds resource R2 and is waiting for resource R1.
No preemption
None of the processes should be preempted. If any process is preempted, then it will release the resource it is holding and hence the other process waiting for the resource will get the released resource and will execute till its completion. It is, therefore, necessary that there is no preemption.
Circular wait
If we observe the example above, we find that the processes form a loop. One process is waiting for the other process to release the resource. A cycle is thus formed.
It is important to note that all the above four conditions should be met for a deadlock to occur.
Methods to deal with deadlock
Deadlock ignorance
Surprisingly this method is what most of our PCs use. In general, deadlock does not occur very often. The engineers, therefore, decided to ignore the deadlock and let it occur in case it occurs. The reason is that trying to prevent or avoid deadlock will impact the performance ( speed mainly) of the system. Since deadlock is a very rare event in computers, it would not be very wise to compromise the performance.
Deadlock avoidance and prevention
Although there are many flaws in implementing this in real life, there are various algorithms that are of great theoretical importance. Banker’s algorithm is one of the example.
Deadlock detection and recovery
In case a deadlock is detected, we allow it to occur and then preempt the process to deal with the deadlock.
Consider an example where there are ten people standing in a queue in front of the ticket counter. The person who is standing close to the counter will get the ticket first, while the tenth person will have to wait for nine people in front of him to get their tickets before he is able to get his. In other words, he has to “starve” for his ticket.
Starvation is a condition where the process with low priority gets indefinitely postponed while some high-priority processes keep executing. Starvation is different from deadlock. In a deadlock, the processes are blocked, and none of them are getting executed, whereas in starvation, the high-priority process gets executed while the low-priority process is indefinitely postponed.
Causes of starvation
Wrong or faulty resource allocation decisions.
If all the incoming processes have higher priority then the process which is stuck will continue to remain so.
Lack of resources is yet another reason for starvation. If ample resources are not available, allocation is likely to be flawed.
Ways to deal with starvation
The concept of aging must be implemented. If the priority increases, the waiting time increases. This will avoid starvation.
Flawed selection techniques like random selection must be avoided.
Having a resource manager for the proper allocation of resources is a sound way to deal with the problem of starvation.
Difference between starvation and deadlock
In a deadlock, the processes do not get executed because they are waiting for other processes to release the resource, whereas, in starvation, the processes with high priority are executed while the processes with low priority wait indefinitely.
Practically we let deadlock occur, although there are some algorithms for deadlock avoidance, whereas the concept of aging is used to overcome starvation.
In a deadlock, the resources are held by the processes and hence are in a blocked state, whereas resources are free from starvation.
Deadlock occurs when the four conditions- mutual exclusion, hold and wait, no-preemption, and circular wait are met while starvation happens to only the process with low priority.
Both deadlock and starvation can decrease the overall efficiency of the system.
Livelock
Livelock is similar to deadlock but not exactly deadlock. It is like a deadlock in the sense that two( or more) processes are blocking each other, but in livelock, each process is actively trying to resolve the problem on its own. A livelock happens when these processes' efforts to resolve the problem make it impossible for them to ever terminate.
Consider a situation where process P1 acquires resource R1 and process P2 acquires resource R2. Process P2 requires R1 and process P1 requires R2. This seems very similar to a deadlock. In livelock, however, both processes are in a running state and it is consuming time without making any effective progress.
Consider a situation where both P1 and P2 simultaneously decide that if they are unable to get the required resource, they will release the resource they are currently using. Both release their resources. Now again, P1 will acquire R1, and P2 will acquire R2. Again we come to the same condition.
In Livelock, the processes are in a running state but are unable to complete their execution.
Livelock typically occurs due to improper synchronization or communication between concurrent processes. In livelock, processes are stuck in a loop of actions, each responding to the other's actions without making progress. This often happens when processes are constantly trying to resolve conflicts or avoid deadlock situations but end up perpetuating the problem by continuously changing their states without achieving any forward movement.
Prevention of Livelock
Preventing livelock involves implementing effective strategies for resource allocation and process coordination. One approach is to use randomized or probabilistic algorithms to break the symmetry that leads to livelock scenarios. Additionally, designing robust communication protocols and resource management techniques can help ensure that processes do not get stuck in unproductive cycles of activity. Furthermore, careful design and testing of concurrent systems can help identify and mitigate potential livelock conditions before they occur in production environments.
Difference Between Deadlock, Starvation and Livelock
Criteria
Deadlock
Starvation
Livelock
Definition
Processes are unable to proceed, waiting indefinitely for resources held by others.
A process is perpetually denied resources it needs due to higher-priority processes seizing them.
Processes are actively changing states in response to each other's actions without making progress.
Progress
Complete halt in system progress.
Some processes make progress, while others are denied resources.
Processes remain active but do not make system-wide progress.
Resource Use
Resources are held and not released.
Resources may be unfairly allocated to higher-priority processes.
Resources are continuously used and released in a futile loop.
Resolution
Requires intervention or timeout mechanisms to release resources and break circular dependencies.
Priority adjustments or fair scheduling algorithms can alleviate resource denial.
Often necessitates redesigning communication protocols or resource management strategies to break the livelock loop.
Frequently Asked Questions
What is deadlock and livelock in MySQL?
In MySQL, deadlock occurs when two or more transactions are waiting for each other's locks, causing a standstill. Livelock, on the other hand, happens when transactions are continually changing states in response to each other's actions, resulting in no progress.
What are the four mandatory conditions for deadlock?
Mutual exclusion, hold and wait, no preemption, and circular wait.
Name an algorithm used in deadlock avoidance.
Banker’s algorithm
Which key concept is used for avoiding starvation?
Aging
Give an example of CPU scheduling where starvation occurs.
Priority scheduling
Conclusion
A set of processes are said to be in deadlock if they wait for the happening of an event caused by other processes in the same set.
Starvation occurs when processes with high priority get executed, leaving the process with low priority to wait indefinitely.
In Livelock, the processes are in a running state but are unable to complete their execution.
The concept of aging is used for dealing with starvation.
305+ registered