• Introduction
• Examples of Deadlock
• Condition for Deadlock
  • Mutual Exclusion
  • Hold and wait
  • No Preemption
  • Circular wait
• Method for handling Deadlock
  • Ignoring the Deadlock
  • Deadlock Prevention
  • Deadlock Avoidance
  • Deadlock Detection and Rollback
• Starvation vs Deadlock
• Safe and Unsafe state

Introduction:

Deadlock is a special unwanted scenario where non of the process in the system is in the running state that is all the process are in the waiting state, waiting for some kind of resources which is held by another process in the system.

Diag-1: Deadlock

Example of Deadlock:

• A real-world example would be traffic, which is going only in one direction.
• Here, a bridge is considered a resource.
• So, when Deadlock happens, it can be easily resolved if one car backs up (Preempt resources and rollback).
• Several cars may have to be backed up if a deadlock situation occurs.
• So starvation is possible.

Diag-2: Deadlock Example

Condition for Deadlock

There are four conditions for the deadlock to happen:

Mutual Exclusion(ME):

• This states that at a time only one process can enter the critical section of code.
• Critical section of code(CS) is nothing but a segment of code which contains variable shared among multiple process.
• If allowed to access parallel, it can lead to data loss or inconsistencies.

Hold and Wait:

• This means a process is holding up resources and waiting for another resources which is held by other processes.

No Preemption:

• A process once acquired the resources cannot be forced to release the resources until the process voluntarily releases it.

Circular Wait:

• It states that set of process say {Po, P1, P2, P3..} of waiting process must exist such that Po is waiting for resource held by P1 ,similarly P1 needs resources held by P2 and so on

All the four conditions must be satisfied for a deadlock to happen.

Methods for Handling Deadlock:
Methods that are used in order to handle the problem of deadlocks are as follows:

• Ignoring the Deadlock
• Deadlock Prevention
• Deadlock Avoidance
• Deadlock detection and recovery

Ignoring the Deadlock:

According to this method, it is assumed that deadlock would never occur, and hence no special provision for handling the deadlock. It can be beneficial for those operating systems that is only used for browsing and for the normal task.

Deadlock Prevention:

There are four essential conditions for the deadlock to occur:

• Mutual Exclusion
• Hold and wait
• No preemption
• Circular wait

Thus as a process to prevent deadlock if we become able to violate any condition among the above four and do not let them occur together then the deadlock can be prevented.

We will elaborate deadlock prevention approach by examining each of the four necessary conditions separately.

Mutual Exclusion:

This ensures that only thread can access the non-shared resource at a time and failing to do so can lead to data inconsistencies or data loss. In contrast, shareable resources do not require mutually exclusive access thus cannot be involved in a deadlock. A good example of a sharable resource is Read-only files because if several processes attempt to open a read-only file at the same time, then they can be granted simultaneous access to the file.

Generally, deadlock cannot be prevented by denying the mutual exclusion condition because there are some resources that are non-sharable and failing to do so can lead to data inconsistencies or data loss.

Hold and wait:

Hold and wait condition occurs when a process holds a resource and is waiting for some other resources held by other in order to complete its execution.

This can be avoided either:

• Each process must requests and gets all its resources before beginning its execution.
  This leads to low utilization of resources, since resource may be allocated but unused for a long period and also practically its difficult to get required resources aprior.
• A process can request for a resource when it does not occupy any resource.
  There is a possibility of starvation. A process that needs several popular resources may have to wait indefinitely because at least one of the resources that it needs is always allocated to some other process.

No Preemption:

The third necessary condition for deadlocks is that there should be no preemption of the resources that have already been allocated. In order to ensure that this condition does not hold the following rules can be used.

• If a process that is holding some resource requests another resource and if the request cannot be allocated to it, it must release all the resources currently allocated to it.
• When a process requests some resources, if they are available, then allocate them. If in case the requested resource is not available and is being held by some process which is again waiting for some resource, the operating system preempts it from the waiting process and allocate it to the requesting process. And if that resource is being used, then the requesting process must wait.

The second protocol can be applied to those resources whose state can be easily saved and restored later for example CPU registers and memory space, and cannot be applied to resources like printers and tape drivers.

Circular Wait:

The fourth condition for deadlock to occur is that each process waits for the resource held by its next process in a cycle. In order to ensure violate this condition a priority can be assigned to each process.

There will be a condition that any process cannot request for a lesser priority resource. This method ensures that not a single process can request a resource that is being utilized by any other process and due to which no cycle will be formed.

Comparision:

The deadlock can be prevented by avoiding any one of the deadlock occurrence necessary condition: Mutual Exclusion, Hold n wait, No preemption and circular wait.

Deadlock Avoidance:

The deadlock Avoidance method is used by the operating system in order to check whether the system is in a safe state or in an unsafe state. The request for any resource will be granted if the resulting state of the system does not cause any deadlock in the system.

How does it work?

• The general idea behind deadlock avoidance is to prevent deadlocks from ever happening, by preventing at least one of the above mentioned conditions.
• This requires more information about each process AND tends to lead to low device utilization. ( I.e. it is a conservative approach. )
• In some algorithms, the scheduler only needs to know the maximum number of each resource that a process might potentially use.
• In more complex algorithms the scheduler can also take advantage of the schedule of exactly what resources may be needed in what order.
• When a scheduler sees that starting a process or granting resource requests may lead to future deadlocks, then that process is just not started or the request is not granted.
• A resource allocation state is defined by the number of available and allocated resources and the maximum requirements of all processes in the system.
• It is the simplest and most useful model that each process declares the maximum number of resources of each type it may need.

Safe State and Unsafe State:

• A system is said to be in a safe state if the system can allocate resources to each process(up to its maximum requirement) in some order without leading to deadlock.
• The sequence in which the process can be executed without leading to deadlock is known as a safe sequence. Thus a formally a system is in a safe state if there exists a safe sequence.

• In an unsafe state, the operating system cannot prevent processes from requesting resources in such a way that any deadlock occurs.
• It is not necessary that all unsafe state are deadlocks; an unsafe state state may lead to deadlock.

Thus a safe state is nota deadlocked state and conversely a deadlocked state is an unsafe state.

Deadlock Avoidance Example(Bankers Algorithm):

Consider a system having 12 instances of the resource and at time t0, the process P1 holds 5 resources, the process P2 holds 2 resources and the process P3 holds 2 resources, Thus only 3 instances of resource is free.

• At time t0, the system is in a safe state.
• Now comes the safe sequence which can avoid deadlock.
• If the process is run in sequence <P2, P1, P3>, it satisfies the safety condition.
• The process P2 can immediately be granted resources and then return them.
• After the return, the system will have 5 instances of the resource and the process P1 can be granted resources and then return.
• Now the system will have 10 resources that can be given to process P3.
• Thus there exists a safe sequence <P2, P1, p3> which can avoid deadlock.

A system can from safe state to an unsafe state

• Suppose at time T1, the process P3 requests for a resource and is allocated. Thus free resource left is 2 and P3 needed 6 more.
• Thus now only process P2 can be allocated its resource and the system is left with 4 resources once it returns.
• If the process P1 requests 5 resources, it has to wait as system has just 4.
• And at the same time, if P3 demands 6 more, even the process P3 has to wait which result in deadlock.
• The mistake was granting the request from P3 for one more tape. If we made P3 wait until either of the other processes had finished and released its resources, then we could have avoided the deadlock.

Note: 

• In a case, if the system is unable to fulfill the request of all processes then the state of the system is called unsafe.
• The main key of the deadlock avoidance method is whenever the request is made for resources then the request must only be approved only in the case if the resulting state is a safe state.

Deadlock detection and recovery:

With this method, the deadlock is detected first by using some algorithm of the resource-allocation graph. After the deadlock is detected, there is some mechanism to recover from the deadlock- resource preemption and process termination.

There are three basic approaches to recover from deadlock:

• Inform the system operator, and allow him/her to take manual intervention
• Terminate one or more processes involved in the deadlock
• Resource Preemption

Diag-1: Deadlock Recovery

Process Termination:

• Two basic approaches, both of which recover resources allocated to terminated processes:
  • Terminate all processes involved in the deadlock. This definitely solves the deadlock, but at the expense of terminating more processes than would be absolutely necessary.
  • Terminate processes one by one until the deadlock is broken. This is more conservative, but requires doing deadlock detection after each step.
• In the latter case there are many factors that can go into deciding which processes to terminate next:
  1. Process priorities.
  2. How long the process has been running, and how close it is to finishing.
  3. How many and what type of resources is the process holding. ( Are they easy to preempt and restore? )
  4. How many more resources does the process need to complete.
  5. How many processes will need to be terminated
  6. Whether the process is interactive or batch.
  7. ( Whether or not the process has made non-restorable changes to any resource. )

Resource preemption:

When preempting resources to relieve deadlock, there are three important issues to be addressed:

Selecting a victim:
Deciding which resources to preempt from which processes involves many of the same decision criteria outlined above. Selecting the same victim each time should be avoided.

Rollback:
Ideally one would like to roll back a preempted process to a safe state prior to the point at which that resource was originally allocated to the process.

Unfortunately it can be difficult or impossible to determine what such a safe state is, and so the only safe rollback is to roll back all the way back to the beginning. ( I.e. abort the process and make it start over. )

Starvation:
One option would be to use a priority system and increase the priority of a process every time its resources get preempted. Eventually, it should get a high enough priority that it won’t get preempted anymore.

Starvation Vs Deadlock:

Here, are some important differences between Deadlock and starvation:

Categories: Operating system (OS)