Unit - 4

Deadlocks

4.1 Introduction

Every process needs some resources to complete its execution. However, the resource is granted in sequential order.

1. The process requests some resources.
2. OS grants the resource if it is available otherwise let the process waits.
3. The process uses it and releases on completion.

A Deadlock is a situation where each of the computer processes waits for a resource that is being assigned to some another process. In this situation, none of the processes gets executed since the resource it needs, is held by some other process which is also waiting for some other resource to be released.

Let us assume that there are three processes P1, P2, and P3. There are three different resources R1, R2, and R3. R1 is assigned to P1, R2 is assigned to P2, and R3 is assigned to P3.

After some time, P1 demands R1 which is being used by P2. P1 halts its execution since it can't complete without R2. P2 also demands R3 which is being used by P3. P2 also stops its execution because it can't continue without R3. P3 also demands R1 which is being used by P1 therefore P3 also stops its execution.

In this scenario, a cycle is being formed among the three processes. None of the processes is progressing and they are all waiting. The computer becomes unresponsive since all the processes got blocked.

Fig 1 - Deadlock

Difference between Starvation and Deadlock

Necessary conditions for Deadlocks

1. Mutual Exclusion

A resource can only be shared in a mutually exclusive manner. It implies if two processes cannot use the same resource at the same time.

2.     Hold and Wait

A process waits for some resources while holding another resource at the same time.

3.     No preemption

The process which once scheduled will be executed till the completion. No other process can be scheduled by the scheduler meanwhile.

4.     Circular Wait

All the processes must be cyclically waiting for the resources so that the last process is waiting for the resource which is being held by the first process.

System model

In a multiprogramming system, numerous processes get competed for a finite number of resources. Any process requests resources, and as the resources aren't available at that time, the process goes into a waiting state. At times, a waiting process is not at all able again to change its state as other waiting processes detain the resources it has requested. That condition is termed as deadlock.

A system model or structure consists of a fixed number of resources to be circulated among some opposing processes. The resources are then partitioned into numerous types, each consisting of some specific quantity of identical instances. Memory space, CPU cycles, directories and files, I/O devices like keyboards, printers, and CD-DVD drives are prime examples of resource types. When a system has 2 CPUs, then the resource type CPU got two instances.

Under the standard mode of operation, any process may use a resource in only the below-mentioned sequence:

1. Request: When the request can't be approved immediately (where the case may be when another process is utilizing the resource), then the requesting job must remain waited until it can obtain the resource.
2. Use: The process can run on the resource (like when the resource is a printer, its job/process is to print on the printer).
3. Release: The process releases the resource (like, terminating or exiting any specific process).

A deadlock state can occur when the following four circumstances hold simultaneously within a system:

●        Mutual exclusion: At least there should be one resource that has to be held in a non-sharable manner; i.e., only a single process at a time can utilize the resource. If another process demands that resource, the requesting process must be postponed until the resource gets released.

●        Hold and wait: A job must be held at least one single resource and waiting to obtain supplementary resources which are currently being held by several other processes.

●        No preemption: Resources can't be anticipated; i.e., a resource can get released only willingly by the process holding it, then after that, the process has completed its task.

●        Circular wait: The circular - wait for situation implies the hold-and-wait state or condition, and hence all the four conditions are not completely independent. They are interconnected among each other.

Normally you can deal with the deadlock issues and situations in one of the three ways mentioned below:

●        You can employ a protocol for preventing or avoiding deadlocks, and ensure that the system will never go into a deadlock state.

●        You can let the system to enter any deadlock condition, detect it, and then recover.

●        You can overlook the issue altogether and assume that deadlocks never occur within the system.

But is recommended to deal with deadlock, from the 1st option

Key takeaway

A Deadlock is a situation where each of the computer processes waits for a resource that is being assigned to some another process. In this situation, none of the processes gets executed since the resource it needs, is held by some other process which is also waiting for some other resource to be released.

4.2 Deadlock characterization

In a deadlock, processes never complete their execution, and system resources are tied up, keeping different jobs from the beginning.

Necessary Conditions

A deadlock occurs in the operating system when at least two processes need some resource to finish their execution that is held by the different process.

A deadlock happens if the four Coffman conditions prove to be true. But, these conditions are not related. They are described as follows:

Mutual Exclusion

There ought to be a resource that must be held by one process at once.

In the figure below, there is a single instance of Resource 1 and it is held by Process 1 as it were.

Fig 2: Single instance

Hold and Wait

A process can hold numerous resources and still demand more resources from different processes that are holding them.

In the graph given beneath, Process 2 holds Resource 2 and Resource 3 and is mentioning Resource 1 which is held by Process 1.

Fig 3: Hold and wait

No Preemption

A resource can't be pre-empted forcefully from a process. A process can just release a resource wishfully.

In the graph underneath, Process 2 can't preempt Resource 1 from Process 1. It might be discharged when Process 1 gives up it intentionally after its execution is finished.

Fig 4: No pre-emption

Circular Wait

A process is waiting for the resource held continuously by another process, which is waiting for the resource held by the third process, etc, till the last process is waiting for a resource held by the first process. These structures around the chain.

For instance: Process 1 is assigned Resource 2 and it is requesting Resource 1. Likewise, Process 2 is assigned Resource 1 and it is requesting Resource 2. This structures a circular wait loop.

Fig 5: Circular wait

Key takeaway

A deadlock occurs in an operating system when two or more processes require a resource held by the other process to complete their execution.

If all four Coffman requirements are met, a deadlock ensues. These requirements, however, do not have to be mutually exclusive.

4.3 Resource allocation graph

The resource allocation graph is the pictorial representation of the state of a system. As its name suggests, the resource allocation graph is the complete information about all the processes which are holding some resources or waiting for some resources.

It also contains the information about all the instances of all the resources whether they are available or being used by the processes.

In Resource allocation graph, the process is represented by a Circle while the Resource is represented by a rectangle. Let's see the types of vertices and edges in detail.

Fig 6 - Vertices

Vertices are mainly of two types, Resource and process. Each of them will be represented by a different shape. Circle represents process while rectangle represents resource.

A resource can have more than one instance. Each instance will be represented by a dot inside the rectangle.

Fig 7 – Edges

Edges in RAG are also of two types, one represents assignment and other represents the wait of a process for a resource. The above image shows each of them.

A resource is shown as assigned to a process if the tail of the arrow is attached to an instance to the resource and the head is attached to a process.

A process is shown as waiting for a resource if the tail of an arrow is attached to the process while the head is pointing towards the resource.

Fig 8 - Waiting for a resource

Example

Let’s consider 3 processes P1, P2 and P3, and two types of resources R1 and R2. The resources are having 1 instance each.

According to the graph, R1 is being used by P1, P2 is holding R2 and waiting for R1, P3 is waiting for R1 as well as R2.

The graph is deadlock free since no cycle is being formed in the graph.

Fig 9 - Deadlock free

Deadlock Detection using RAG

If a cycle is being formed in a Resource allocation graph where all the resources have the single instance, then the system is deadlocked.

In Case of Resource allocation graph with multi-instanced resource types, Cycle is a necessary condition of deadlock but not the sufficient condition.

The following example contains three processes P1, P2, P3 and three resources R2, R2, R3. All the resources are having single instances each.

Fig 10 - Example

If we analyse the graph, then we can find out that there is a cycle formed in the graph since the system is satisfying all the four conditions of deadlock.

Allocation Matrix

Allocation matrix can be formed by using the Resource allocation graph of a system. In Allocation matrix, an entry will be made for each of the resource assigned. For Example, in the following matrix, en entry is being made in front of P1 and below R3 since R3 is assigned to P1.

Request Matrix

In request matrix, an entry will be made for each of the resource requested. As in the following example, P1 needs R1 therefore an entry is being made in front of P1 and below R1.

Avial = (0,0,0)

Neither we are having any resource available in the system nor a process going to release. Each of the process needs at least single resource to complete therefore they will continuously be holding each one of them.

We cannot fulfil the demand of at least one process using the available resources therefore the system is deadlocked as determined earlier when we detected a cycle in the graph.

Key takeaway

The resource allocation graph is the pictorial representation of the state of a system. As its name suggests, the resource allocation graph is the complete information about all the processes which are holding some resources or waiting for some resources.

It also contains the information about all the instances of all the resources whether they are available or being used by the processes.

4.4 Methods for Handling Deadlocks: deadlock prevention, avoidance and deadlock detection, recovery from deadlock

Deadlock prevention algorithms guarantee that in any event one of the essential conditions (Mutual exclusion, hold and wait, no preemption, and circular wait) does not remain constant.

This methodology includes structuring a system that violates one of the four fundamental conditions required for the event of a deadlock.

This guarantees the system stays free from the deadlock.

Anyway, most deadlock prevention algorithms have poor resource usage, and consequently, bring about diminished throughputs.

Mutual Exclusion

The mutual exclusion condition must hold for non-sharable resources. For instance, a printer can't be at the same time shared by a few processes.

Sharable resources, conversely, don't require mutually exclusive access and in this manner can't be associated with a deadlock.

Read-only files are a genuine case of a sharable resource. If many processes endeavor to open a read-only file at the same time, they can be able to access the file simultaneously.

A process will never wait for a sharable resource. As a rule, be that as it may, we can't prevent deadlock by denying the mutual exclusion condition, since certain resources are inherently non-sharable.

Hold and Wait

To avoid this condition processes must be kept from holding at least one resource while at the same time waiting for at least one other. There are a few conceivable outcomes for this:

Necessitate that all processes demand all resources one at the same time. This can be a wastage of system resources if a process needs one resource in the initial stage of its execution and does not need some other resource until some other time.

Necessitate that processes holding resources must discharge them before requesting new resources, and after that re-acquire the resources alongside the new ones out of a single new demand. This can be an issue if a process has somewhat finished an activity utilizing a resource and, at that point neglects to get it re-allocated after releasing it.

Both of the strategies portrayed above can prompt starvation if a process requires at least one well-known resources.

No Preemption

Preemption of process resource allocations can anticipate this state of deadlocks when it is conceivable.

One methodology is that if a process is compelled to hold up when mentioning another resource, at that point every other resource recently held by this process are certainly discharged, (appropriated), constraining this process to re-acquire the old resources alongside the new resources in a single request.

Another methodology is that when a resource is requested and not accessible, at that point the system hopes to perceive what different processes right now have those resources and are themselves blocked waiting for some other resource. On the off chance that such a process is discovered, at that point, a portion of their resources may get acquired and added to the list of resources for which the process is waiting.

Both of these methodologies might be relevant for resources whose states are effectively saved and resorted, for example, registers and memory, yet are commonly not applicable to different devices, for example, printers and tape drives.

Circular Wait

One approach to stay away from circular wait is to number all resources, and to require that processes request resources just in carefully expanding (or diminishing) order.

In contrast, to demand resource Rj, a process should initially discharge all Ri with the end goal that i >= j.

One major test in this plan is deciding the overall request of the various resources.

Approach

A natural number is allotted to each resource.

Each process is permitted to demand the resources either in just ascending or descending order of the resource number.

If ascending request is followed, if a process requires a lesser number of resources, at that point it must release every one of the resources having a bigger number and the other way around.

This methodology is the most functional methodology and implementable.

Nonetheless, this methodology may cause starvation however will never prompt deadlock.

Deadlock Avoidance

Deadlock-prevention algorithm prevents the occurrence of deadlock by limiting how demands can be made. The restrictions guarantee that at any rate one of the vital conditions for deadlock can't happen and, thus, deadlock can't occur.

Conceivable drawbacks of preventing deadlocks by this strategy, in any case, result in low device usage and decreased system throughput.

An alternative strategy for staying away from deadlocks is to require extra data about how resources are requested.

In this respect each request requires that system keeps record about the resources as of now available, the resources at present assigned to each process, and the future demands and releases of each process.

The different algorithms that utilize this methodology vary in the sum and type of data required. The least complex and most valuable model necessitates that each process proclaim the most maximum number of resources of each instance that it might require.

Given this as earlier data, it is conceivable to develop a algorithm that guarantees that the system will never enter a deadlock state. Such a calculation characterizes the deadlock avoidance approach.

A deadlock avoidance approach powerfully looks at the resource-assignment state to guarantee that a circular wait condition can never exist.

The resource-allocation state is characterized by the number of available and allotted resources and the most extreme requests of the processes.

Safe State

A state is safe if the system can assign resources to each process (up to its most extreme) in some sequence and still will be able maintain a deadlock free state.

In other words, a system is in a safe state if there exists a safe sequence.

An arrangement of processes <P1, P2, ... , Pn> is a safe arrangement for the present allocation state if, for each Pi, the resource requests that Pi make can be fulfilled by the currently accessible resources in addition to the resources held by all Pj, with j < i.

In this circumstance, the resources that Pi needs are not quickly available, at that point then Pi can wait until all Pj have completed.

When all Pj have completed, Pi can acquire the majority of its required resources, complete its assigned task, and return its allotted resources, and will terminate.

At the point when Pi ends, Pi+l can get its required resources, and so on.

In the event that no such sequence exists, at that point the system state is said to be unsafe.

A safe state is definitely not a deadlock state. On the other hand, a deadlock state is a unsafe state. All the unsafe state are not deadlock.

Consider a system with 10 magnetic tape drives and 3 processes P0, P1, and P2 respectively. The maximum requirement and current needs by each process is shown in table below.

Process P0 is having 4 tape drives, P1 is having 2 tape drives and P2 is having 2 tape drives.

For a safe sequence process P0 needs 4 more tape drives to completes its execution. Similarly process P1 needs 2 and P2 needs 6. Total available resources are 2.

Since process P0 needs 5 tape drives, but available is only 2, so process P1 will wait till gets resources. Process P1 needs only 2 so its request will be fulfilled and as P1 will finish its execution it will return all resources.

Now currently available resources are 4. Then process P2 will wait as available resources are 4 and P2 needs 6.

The system will now fulfil the needs of P0. Process P0 will execute and release its all resources. Now available resources are 8. And in the last request of process P2 will be fulfilled.

So, the safe sequence will be <P1, P0, P2>.

There is one thing to be note here that any system can go from a safe state to unsafe state if any process request more resources.

Deadlock Detection

Deadlock detection is the process of really verifying that a deadlock exists and distinguishing the processes and resources engaged in the deadlock.

The essential thought is to check allocate against resource availability for all conceivable allocation sequences to decide whether the system is in deadlocked state.

Obviously, the deadlock detection algorithm is just 50% of this procedure. When a deadlock is recognized, there should be an approach to recover a few choices exists:

1. Single instance of resource: Here to detect deadlock, we can run a algorithm to check for cycle in the Resource Allocation Graph. Presence of cycle in the graph is the adequate condition for deadlock.

In the above graph, resource 1 and resource 2 have single occasions. There is a cycle R1 → P1 → R2 → P2. Thus, Deadlock is confirmed.

2.     Multiple instance of resources: Detection of the cycle is essential yet not adequate condition for deadlock detection, for this situation, the system might be in halt fluctuates as per various circumstances.

Recovery from deadlock

At the point when a Deadlock Detection Algorithm verifies that a deadlock has happened in the system, the system must recover from that deadlock. There are two methodologies of breaking a Deadlock:

1. Process Termination: To wipe out the deadlock, we can just kill at least one process. For this, we utilize two techniques:
   1. Abort all the Deadlocked Processes: Aborting every one of the processes will break the deadlock, however with incredible costs. The deadlocked processes may have computed for quite a while and the consequence of those incomplete calculations must be disposed of and there is a likelihood to recalculate them later.
   2. Abort one process in turn until the deadlock is removed: Abort one deadlocked process in turn, until the deadlock cycle is removed from the system. Because of this technique, there might be reasonable overhead, because after aborting the process, we need to run a deadlock detection algorithm to check whether any processes are yet deadlocked.
2. Resource Preemption: To remove deadlock we can utilize resource preemption. We preempt a few resources from processes and give those resources to different processes. This strategy will raise three issues –
   1. Choosing a victim: We should figure out which resources and which processes are to be preempted and the request to limit the expense.
   2. Rollback: We should figure out what action will be taken for the process from which resources are preempted. One solution is all rollback. That implies aborting the process and restarts it.
   3. Starvation: In a system, the equivalent process might be constantly picked as a victim. Subsequently, that process will never finish its assigned task. This circumstance is called Starvation and must be kept away from. One arrangement is that a process must be picked as a victim just a limited number of times.

Key takeaway

Deadlock prevention algorithms guarantee that in any event one of the essential conditions (Mutual exclusion, hold and wait, no preemption, and circular wait) does not remain constant.

Deadlock detection is the process of really verifying that a deadlock exists and distinguishing the processes and resources engaged in the deadlock.

The essential thought is to check allocate against resource availability for all conceivable allocation sequences to decide whether the system is in deadlocked state.

References:

1. Silberschatz, Galvin, Gagne, "Operating System Concepts", John Wiley and Sons, 10th edition, 2018
2. Stallings, “Operating Systems –Internals and Design Principles”, 9/E, Pearson Publications, 2018
3. Andrew S. Tanenbaum, “Modern Operating Systems”, 4/E, Pearson Publications, 2015