In an operating system, there are many processes (processes are programs that are currently being executed) running continuously. All of these processes are important for the functioning of the computer. It defines the basic unit of work that has to be implemented by the system. Processes follow sequential execution.
These processes require some resources to run or finish their execution. Sequential order is followed here. The process first requests for a resource. If it is available, the OS grants the resource. If not, the process has to wait. After the process has used the resource, it is released. If a problem arises during the waiting and releasing, it means that there is a deadlock situation.
What is Deadlock?
A deadlock is a common situation in operating systems where a process waiting for a resource can be executed because that resource is currently held by another process and is being utilised for its execution, therefore, the process does not get executed. Moreover, many other processes may also be waiting for a resource to be released. A deadlock situation is created
Let us assume that there are two processes called P1 and P2. Resources R1 and R2 are assigned to them respectively. So if P1 needs R2 to complete its execution, but it is held by P2, P1 has to wait. Similarly, P2 may be waiting for R1 that is held by P1. Thus, P2 has to wait until P1 has released the resource. As a result, a deadlock situation arises and both processes are not able to complete their execution. As the processes are blocked, the system may become unresponsive.
Condition for Deadlock
There are certain conditions that have to occur for a deadlock. They are as follows:
1. Mutual Exclusion
This means that resources can be used in a mutually exclusive way. So, two processes will not be able to access the same resource at a particular point in time. At least one resource has to be acquired by a process in a non-shareable mode. If not, more than one process will not be able to access a resource at a time.
2. Hold and Wait
This is a condition where a process is holding at least one resource for its execution. This process is also waiting for another resource, which is being held by another process.
3. No Pre-emption
This means that if a resource is assigned to a particular process, it cannot be pre-empted. The resource cannot be allocated to another process unless it is released. The resource has to voluntarily release for another process to utilise it.
4. Circular Wait
In this situation, several processes are waiting for a resource that is allocated to a particular process. This waiting happens is the cyclic manner where the last process waits for the initial process to release a resource.
For example, process P1 waits for a process held by P2, that is waiting for a resource assigned to P3. P3 is waiting for a resource that is currently held by P4. P4 is waiting for P1 to release a resource.
We will now focus on the different processes for handling deadlocks.
Deadlock Detection in OS
In deadlock detection, the operating system considers that a deadlock situation will occur and then it will identify it. No methods for prevention or avoidance of deadlocks are applied here. So, the OS analyses if there is a deadlock. If detected, recovery methods are applied.
Deadlocks are detected using the Resource Allocation graph. For resources that have a single instance, is a process cycle is found, a deadlock will definitely occur. If the resources have multiple instances, cycle detection is not enough to ensure a deadlock will be detected. A safety algorithm must be used in this case. This algorithm converts the resource allocation graph into two – request matrix and allocation matrix.
Deadlock Prevention
In an OS, deadlocks can be prevented by inhibiting the conditions that cause it in the first place. They are:
1) By Mutual Exclusion
If a resource can be used by one or more processes at the same time, the mutual exclusion will not occur. The process will not have to wait for a resource. Thus, it is possible to prevent a deadlock. Mutual exclusion can be prevented by a process called spooling.
Spooling will work for printers. The printer’s memory stores all the jobs sent to it by different processes. The printer executes the tasks according to the FCFS (First Come First Serve) basis.
Thus, the processes do not have to wait for the printer. This process may be effective in preventing mutual exclusion but cannot be applied to all resources.
So, mutual exclusion cannot be prevented practically.
2) Elimination of Hold and Wait
The condition can be prevented by assigning all the necessary resources to the processes before their execution starts. This way the processes do not have to wait for any resources after its execution starts. But this might lead to low utilisation of system resources.
Suppose a process requires a printer for a task a different point of time. But, that printer has already been allocated to it at present. Therefore, that printer will remain blocked until the process has finished its execution. Moreover, multiple resources may require more than one resource at a time.
There is also a possibility of starvation. This is because a process may hold on to a resource for a long time for execution, as the resource has been allocated to it initially.
Thus, the hold and wait cannot be prevented.
3) Preventing No Pre-emption
A deadlock can arise when a process cannot be stopped once it has started execution. Resources can be pre-empted from certain processes. You can do this when some process of a higher priority demands the resource. But this can only be done if you save the current state of the process from which the resource is being pre-empted. You might restart that process at a later date. But, this method may be challenging.
4) Elimination of Circular Wait
The condition can be eliminated by numbering the resources. This priority number will be useful as the process will not able to request for a resource that is lesser in priority. Thus, a resource currently being used by another process cannot be requested. A cycle will not be formed.
5) Deadlock Avoidance
You might avoid deadlocks using Banker’s algorithm. Here, the process must notify the different type of resources of each type it needs. The algorithm checks the process requests. If there is a safe state, the resources will be allocated. If not, there will be no allocation.
The algorithm will be provided by the following inputs:
- Maximum number of resources required by processes
- Maximum number of freely available resources
- Resources allocated to the processes currently
The resource request will be granted if it is less than or equal to the maximum requirement of that process. Resources will also be granted if the request is less than or equal to a maximum number of free resources.
Deadlock Ignorance or Ostrich Algorithm
Deadlocks are ignored using an algorithm called Ostrich algorithm. Using this approach, the operating system assumes that there are no chances of encountering a deadlock. It is similar to how an ostrich puts its head into the ground and pretends as if there is no problem at all. This method is used if the cost of deadlock prevention is very high and they occur rarely.
Unix and Windows operating systems use this algorithm. The deadlocks are handled by restarting the system.
What is Starvation in OS?
Starvation is a condition where a process does not get the resources or resource it requires for a long time. In that case, the process may be postponed. The cause of starvation are as follows:
- If there are not enough resources for the processes.
- Improper resource allocation that does not let a process obtain a resource for an indefinite point of time.
- A process having low priority may have to wait for a long time. This happens if the higher priority process does not release the required resource. This is due to the priority scheduling algorithm that allocates resources according to the priority of a process.
Starvation can be prevented using a process called Aging. This increases the priority of the process that has been waiting indefinitely for a resource. Thus, it gets access to the resource it requires.
Conclusion
Deadlocks are common problems in operating systems. While some operating systems use the Ostrich approach to ignore them, others may handle them differently. If a deadlock is a possibility, the system might save the states of the processes and restore the system back to the last checkpoint. It will allocate resources differently so no further deadlocks occur.