Deadlock

We have previously discussed semaphores and other solutions to the critical section problem or producer-consumer problem and during that, if we go deeper, there are such cases which can lead to a Deadlock.

One example of such a problem is “semaphores with a waiting list” can lead to a Deadlock:

Two or more processes are waiting indefinitely for an event which can be caused by another event and that another event is also waiting for an event which is caused by another, and this leads to a Deadlock.

Explanation of the picture above:

Suppose, Po executes => wait(S) and P1 executes => wait(Q). So, for P0, wait(Q) will not open until P1 executes signal(Q) and P1 cannot able to execute it until P0 executes signal(S) and vice-versa.

So, the above condition leads to a Deadlock due to Indefinite Blocking or Starvation because processes are waiting indefinitely within a semaphore.

Question: So, What is a deadlock?

Answer: Explained above is a good example for understanding deadlocks. Moreover, A set of processes are said to be in a deadlock, if they wait for happening of an event caused by others in the same set.

Question: What is the difference between Starvation and Deadlock?

Answer: Starvation = Long waiting, Deadlock = Infinite waiting

Note: Operating Systems generally do not provide deadlock prevention facilities, they are provided by application programmers.

Some points to be noted:

• Resources = CPU cycles, files, I/O devices (printers, DVD drives) et cetera.
• Two CPUs = resource type CPU has two instances.
• Synchronization Tools = mutex locks, semaphores (these are a common source of deadlock)

Note: A lock technically, is nothing but protecting a data structure.

Note: A process must request a resource before using it and must release the resource after using it.

Note: A process cannot request 3-printers if the system has only 2-printers.

Note: If a process requests a resource that is currently allocated to another process, it can be added to a queue of processes waiting for that resource.

Deadlock with the same resource type:

Deadlock with different resource type:

Necessary conditions for a Deadlock to exist

If a deadlock is there, following 4-conditions must be TRUE  and if anyone fails, deadlock is not there.

1. Mutual Exclusion: At least one resource must be held in a non-sharable mode. Only one process can use the resource at one time.
2. Hold and Wait
3. No Preemption: While one process is using a resource, OS is not supposed to pull that resource and give it to another.
4. Circular Wait

R = Type of resource

P = Any process

Rj = An instance of a resource type

Pi = An instance or a thread

Methods for handling deadlocks

1. Deadlock Ignorance
2. Deadlock Prevention
3. Deadlock Avoidance
4. Deadlock Detection and Recovery

Deadlock Prevention

If any of the following fails, we can prevent deadlock.

• Mutual Exclusion
• Hold and Wait
• No Preemption
• Circular Wait

Mutual Exclusion (Not Practical)

The main culprit here is “Resource” as it says that more than one process cannot use me at the same time.

Solution?

1. More than one process can access a resource at the same time. But there is still one problem with it, if for example, a printer resource type is accessed by more than one process at the same time, then the end result is inconsistent. So, as a result, disabling mutual exclusion is dangerous.
2. Spooling: Create a set of jobs and a daemon (process/server) is there to take one job at a time from that pool and assign it a resource (in this case, a printer). But there is still one problem with it, it is not a feasible solution at all.

Hold and Wait (Not Practical)

Solution?

1. Request all resources required before execution. If a process does not want to wait and if a process does not get all required process, do not start executing. But still one problem, a process cannot predict what type and how many resources it is going to use in the future.
2. A process should not hold a resource when it is not using it, or when it wants a new type of resource, it should release the other ones, if there work is completed.

No Preemption (Not Practical)

Solution?

1. Preemption: Take resources away from a process currently using one. But still a problem, a resource (example = printer) cannot be taken away from a process currently using it and cannot be given to any other process in the system, and if done, can lead to a data inconsistency problem.

Circular Wait (Practical)

Solution?

1. Order Resources Numerically: So, the trick is, a process should be restricted in a way that it will only ask for an instance of a resource in increasing order. Problem? = no problem. But if a process requires a lower number instance of a resource type, it must release all the other instances of that resource type and has to start from the beginning.

Deadlock Avoidance

This requires additional information about “how resources are going to be requested“.

Example:

So, from the picture above, the system must know in advance that P1 wants Tape Drive first and then Printer. Similarly, P2 wants Printer first and then Tape Drive.

Some points to be noted:

• A system must know in advance that what process needs what type of resource and how many instances of a resource type.
• This knowledge in advance is going to help, as the system will then know in advance then if an instance of a resource is given to a process will it be going to raise a deadlock like a situation in the future or not.
• That is why a prior knowledge of the sequence of requests of instances of a resource type is helpful.

Note: A deadlock avoidance algorithm dynamically examines the resource allocation state to ensure that a circular-wait condition can never exist in the future.

Safe State = If a system can allocate resources to each process in some order and still avoid a deadlock. So, there exists a safe sequence.

Unsafe state = If no such safe sequence.

Example:

Let’s assume there are 12 Magnetic Tapes and P0, P1, P2 requires:

• P0 requires 10
• P1 requires 4
• P2 requires 9

At time T0:

• P0 holds 5
• P1 holds 2
• P2 holds 2

Now available are = 3

Safe State = Yes

Safe Sequence = <P1, P0, P2>

At time T1:

P2 wants 1 more and is allocated then now the system is no longer in the safe state.

Note: Numbers mentioned above are instances of resource type Magnetic Tape.

Deadlock Avoidance Algorithms

There are generally two types of deadlock avoidance algorithms:

1. For single-instance resource type
2. For multi-instance resource type

Resource Allocation Graph (single-instance resource type)

Conventions used in the graph are:

• Pi -> Rj = this indicates a claim edge, that states that in future, Pi is going to use the Rj and when in the future Pi requests for Rj, then this claim edge will convert into request edge.
• Pi <- Rj = this is assignment edge when the requested resource instance is given to the Pi, the request edge is converted into assignment edge.

Note: All claim edges must already appear in the resource allocation graph.

Note: Assignment edge does not lead to a deadlock cycle or cycle. So, in order to check that we use a cycle detection algorithm to detect such cycles on assignment.

Banker’s Algorithm (multi-instance resource type)

The bank should never allocate its available cash in such a way that it could no longer satisfy the needs of all its customers.

Whenever a process enters, then it has to provide some information, and that information is, how many and what type of resources it is going to use in the future.