In computer systems, competition on limited resources such as CPU, drives, printers, database records, etc. requires proper synchronization otherwise, undesired effects may arise. In today's operating systems post, we are going to talk about deadlocks and starvation when a process or thread hangs up but never stop or finish the intended task. The primary goal of this post is to clarify the key difference between the two. For detailed information on the topic, the reader is advised to consult other resources.
Let us get started...
What is a deadlock?
Deadlock (often called circular wait) is a situation in which processes or threads are blocked from accessing a resource due to waiting for a condition that is never satisfied. For example, if one thread (T1) is acquiring a resource (R1) and waiting for another resource (R2) while another thread (T2) is holding that resource (R2) and waiting for the first resource (R1). In this case, neither thread is going to complete the job (i.e. a deadlock situation).This was an abstract example, let us now take a real life example. Imagine two students, one has a ruler and the other has a pen, each one wants to draw something that requires both the ruler and the pen at the same time. If each student waits the other to give him or her the ruler (or the pen). Both will end up waiting forever not drawing anything. In a deadlock situation, none of the participating processes can execute. Each process gets blocked while waiting for resources acquired by other process.
What is starvation?
Starvation is similar to deadlock in the sense that a process or thread is blocked from having access to a resource. The main difference is that the blocked process cannot have access to the resource not because of waiting but because it does not get a chance. To be more specific, this kind of situation occurs in priority based scheduling algorithms causing low priority processes not to have access to the resource simply because high priority processes are given priority most or all of the time. There is a rumor that when IBM 7094 at MIT was shutdown in 1973, a low priority process was found which had been submitted in 1967 and had not yet been run. Regardless of the authenticity of the incident, it tells us how ugly starvation can be.
Let us now take few examples...
Deadlocks are not tied to computing, they occur in other fields as well. Let us mention few examples…
- Communication: if multiple parties are engaging in a conversation. If each party waits the others to start communication, no conversation is gong to take place. Meaning each party is waiting another to initiate the communication
- Database: when transactions are waiting for one another to release locks. As a result, no record is updated
- Concurrency: when competing threads wait each other to proceed
Now we know what a deadlock and starvation mean. Next, we will mention what conditions lead to a deadlock and starvation...
In order for a deadlock to occur, four conditions have to be present...
- Mutual exclusion meaning only one process can use a resource at a time
- Hold and wait condition: a process must hold a resource and wait to acquire another held by other process
- No preemption: meaning we cannot take away a resource held by a process forcefully
- Circular wait: a process must wait for resources in a circular fashion
Take a look at the following diagram…
No resource deadlocks
Multithreaded operating systems use synchronization primitives (ex. mutex, semaphore) to orchestrate access to resources. As a result, as processes are waiting each other to do some work, deadlocks may occur because of semaphores for example. In this case, the semaphore is considered as a resource and can lead to deadlocks if they are used in the wrong order. Synchronization is beyond the scope of this article, for more information you may refer to the following articles: this and this
Similarly, starvation can happen because of the following conditions...
- Uncontrolled resource management (some processes might not get a chance to access resources)
- Strict process priority enforcement (low priority processes might not get a chance to access resources)
- Random selection (if not picked up, some processes do not to have access to resources)
- Resource scarcity (self explanatory)
The points above, simply mean some processes are favoured over other ones leading to access denial. Let us continue...
What is a live lock ?
A situation similar to starvation is called a live lock. In this case, processes are not blocked due to low priority however, they execute without any progress. How is that? if each process tries to acquire a resource but realizes that a deadlock will occur then both back off. In real life, this situation occurs when two people bump into each other then try to avoid collision. One tries to go left and it happens that the other one moves in the same direction. This may happen 2 or 3 times but of course it is not a real block, we are humans and we can figure a way out. In the next sections, we will talk about dealing with deadlocks and how to avoid them...
Dealing with deadlocks
There are different ways to deal with a deadlock situation. Take a look at the following list...
- Ignore the problem hoping it will never happen
- Detect deadlock and recover from it
- Dynamically avoid deadlock by careful resource allocation
- Prevent deadlock by removing at least of the the 4 necessary conditions
here is how to do that...
Deadlocks can be avoided by attacking the four conditions that lead into a deadlock situation. Let us see how...
- Eliminating mutual exclusion: the best example is printer spooler. The spooler has exclusive access to the printer but not every single process. Not all processes can be spooled so that a deadlock never happens
- Hold and wait: request resources before start so that process never waits for a resource it needs but it may not know the required resources it needs at start. Process may become conservative and requests resources they might need. This ties up resources other processes could be using. Another variation is to give up all resources before making any new request but this has the problem if someone grabs the resources in the mean time.
- No preemption: take the resource away but this might not work with any resource for example taking the printer away in the middle of a print job
- Circular wait: processes request resources in a numerical order. A process holding resource (n) can not wait for resource (m) if (m) is less than (n)
Similarly, starvation can be avoided by attacking the conditions that lead into starvation...
- Use aging to gradually increases the priority of the process that has been waiting long for the resources. This prevents a process with low priority to wait indefinitely for a resource
- Independent resource management
- Do not enforce strict priorities
- Avoid random selection
- Provide more resources
Recovering from deadlock and starvation
If a deadlock or starvation occurs, what should we do?
- Deadlock requires external intervention
- Starvation may or may not require external intervention
- Preemption: take a resource from some other processes
- Rollback: checkpoint a process periodically then use saved state to restart the process if it is in deadlock
- killing processes: try to chose a process that can be rerun from the start. Pick one that has not run too far already
Before we close, let us briefly talk about two phase locking technique used to prevent deadlocks in databases...
Two phase locking
- Used in databases by eliminating the hold and wait condition
- In phase one, process tries to lock all data it needs and no work is done
- In second phase, perform updates then release locks
That is it for today. Let us summarize…
Deadlock occurs when processes are granted exclusive access to resources. Each deadlock process needs a resource held by another deadlock process. Starvation on the other hand happens when a process does not get a chance to use a resource due to scheduling priority
Thanks for reading. Please use the comments section below for feedback.