Four Conditions For Deadlock

Deadlock is a situation that occurs when a process is requesting a resource that is occupied by another process in a computer or computer network. A deadlock has four common conditions i.e Mutual Exclusion, Hold and Wait, Non-Preemption, and Circular Wait.

In this article, I explain to you what is a deadlock? its characteristics or conditions and important methods that are used to avoid and prevent deadlocks. Here we go!

You May Also Like:

• GogoAnime APK
• Kahoot Winner APK
• YouTube Blue Apk
• Types Of Organization
• Types of System Call
• Process Scheduling & Queues
• Process States 

Deadlock

In a multiprogramming environment, several processes compete for resources. A situation may arise where a process is waiting for a resource that is held by other waiting processes. This situation is called a deadlock.

A system has a finite set of resources such as memory, I/O devices, Pointing Devices, etc. It also has a finite set of processes that need to use these resources. A process that wishes to use any of these resources, makes a request to that resource.

If the resource is free, the process gets it. If it is being used by another process, it waits for it to become free. The assumption is that the resource will eventually become free and the waiting process will then use the resource. But in some situations, the other process may also be waiting for some resource.

“A set of processes is in a deadlock state when every process in the set is waiting for an event that can only be caused by another process in the set.” Suppose we have two tape drives and two processes. Each process has got one tape drive for each process.

But both need two such tape drives to proceed with the execution. Each is waiting for the other process to release the other tape drive. This will never happen as the other is also waiting for the same thing. This situation is the deadlock.

The following are some examples of deadlock.

Example 1

The following figure is of a traffic deadlock. It makes the nature of deadlock very clear. None of the cars can pass unless at least one of them backs up or is removed.

Example 2

When two trains approach each other at a crossing, both shall come to a full stop and neither will start up again until the other has gone.

Example 3

Suppose we have a printer and a tape drive. Process A requests for the printer and gets it. Process B requests a tape drive and it is granted to it. Now A asks for the tape drive but the request is denied until B releases it. At this point, process B asks for the printer before releasing the tape drive.

Now both processes are waiting for each other to release the resource and are blocked. Both processes will remain in this situation forever. This situation is called a deadlock.

Resources

A resource is an object that is used by a process. It can be a piece of hardware such as:

• Tape drive
• Disk drive
• Printer

A resource can be a piece of information such as:

• File
• A record within a file
• A shared variable
• A critical section

A computer typically has many different resources. In some cases, there may be many instances of a resource of a given type. A process needing one of these resources can use any one of them. In other cases, there may be only one instance of a resource.

Type of Resources

Different types of resources are as follows:

Preemptible Resource

A preemptible resource is one that can be allocated to a given process for a period of time. Then it can be allocated to another process. Then it can be reallocated to the first process without any negative effects. Examples of preemptible resources include memory, buffers, CPU, and array processor.

Non-Preemptible Resources

Non-Preemptible resources cannot be taken from one process and given to another without side effects. One example is a printer. A printer cannot be taken away from one process and given to another process in the middle of a print job. Deadlocks usually involve non-preemptible resources.

The usual sequence of events that occur as a resource is used is as follows:

1. Request the resource One of two things can happen when a resource is requested. The request can be granted immediately if it is available. The request can be postponed or blocked until a later time.
2. Use of resource Once a resource has been acquired, it can be used.
3. Release the resource a process releases the resource when the process no longer needs it. usually, it is released as soon as possible.

Deadlock Condition

Deadlock occurs if the following four conditions take place simultaneously in a system:

Mutual Exclusion

At least one resource must be held in a non-sharable mode. It means that only one process at a time can use the resource. If another process requests the resource, the requesting process must be delayed until the resource has been released.

Hold and Wait

A process must be holding at least one resource and wait to acquire additional resources that are currently being held by other processes.

No Preemption

Resources cannot be preempted. A resource can be released only voluntarily by the process holding it after that process has completed its task.

Circular Wait

A set {P0, P1, P2…, Pn} of waiting processes must exist such that P0 is waiting for a resource that is held by P1, P1 is waiting for a resource that is held by P2, …., Pn-1 is waiting for a resource that is held by Pn, and Pn waiting for a resource that is held by P0.

Resource-Allocation Graph

The resource allocation graph is used to describe a deadlock graphically. The graph has two different types of nodes i.e. process nodes and resource nodes. Processes are represented by circles and resources are represented by rectangles.

For each instance of a resource, there is a dot in the resource node rectangle. For example, if there are two identical printers, the printer resource will have two dots. The edges among nodes represent resource allocation and request.

If the edge goes from resource to process node, it indicates that the process has acquired the resource. If the edge goes from the process node to the resource node, it indicates that the process has requested the resource. We can use these graphs to determine if a deadlock has occurred or may occur.

For example, if all resources only have one instance (all resource node rectangles have one dot) and the graph is circular, a deadlock has occurred. If some resources have several instances, a deadlock may occur. If the graph is not circular, a deadlock cannot occur because the circular wait condition will not be satisfied.

Below is an example of a deadlock system. Process X has resource B and is waiting for resource A. Process Y has resource A and is waiting for resource B. Note there exists a cycle in the directed graph.

Figure:

The diagram below is an example of a resource graph that has a cycle but does not represent a deadlocked system. It is possible for process Z to continue execution. When process Z is completed, it will release resource A.

It will allow process X to acquire it and continue processing. A cycle is a necessary, but not sufficient condition for deadlock. All deadlocked systems will exhibit all of the above four conditions. Not every system that exhibits the above four conditions will be deadlocked.

Method For Handling Deadlock

A deadlock can be handled in several ways:

1. We can use specific protocols to prevent or avoid deadlocks so that a system may never enter a deadlock state.
2.  Detect the deadlock and recover it.
3. We can totally ignore the deadlock problem.

Deadlock Prevention

We can prevent deadlock by ensuring that at least one of the four necessary conditions for deadlock cannot occur. If at least one condition is not satisfied, a deadlock will not occur.

Mutual Exclusion

Mutual exclusion conditions must hold for non-sharable resources. For example, only one process can have access to a printer at a time, otherwise, the output is disturbed. Some resources can be made shareable like a read-only file.

Several processes can be granted read-only access to a file without inferring from each other. However, deadlock cannot be prevented by only denying mutual exclusion conditions because some resources are intrinsically non-shareable.

Hold And Wait

Deadlock can be prevented by denying the hold and waiting for a precondition. This can be implemented in two different ways.

1. One approach is that a process requests all the resources that it needs in one single request at a process start-up. The system will not grant any resource in the list until it can grant all the required resources.
2. A less restrictive approach is to allow a process to request resources only when it is currently holding no resources. If a process needs a new resource, it must first release all the resources it has and then put the request. It may include a request for the reallocation of a resource it just released.

Problems With This Approach

Each of these strategies has some performance or resource utilization issues.

• If we allocate all resources at the beginning of the process, it may hold resources when it does not need them. It reduces resource utilization. This is especially serious if a process does not know what resource is it will actually need for a given execution until it has started working on the data. The process must request all the resources it might need.
• A process that needs several popular resources might face starvation. Some processes may never execute sine some other process always has control of some required resources.

Non Preemption

Preemption of resources means that we take away sources from processes when they are waiting for other resources. This could work in the following ways:

1. As soon as a process request for a resource that is not available, all of its held resources are released. The process is now waiting for all previously held resources plus the resource that is requested. Suppose a process holds a tape drive and requests a line printer. If the line printer is not available, the tape drive is taken away and the process is put into a state of waiting for both a tape drive and a line printer.
2. When a process requests a resource that is available, it gets it. Otherwise, the system checks those processes that are holding the requested resource and may be waiting for some more resources. In this case, the resource is taken away from the waiting process and allocated to the requesting process. This cannot happen, the process has to wait. during the wait, some other process may get some of its resources.

Problems With This Approach

• It only works if the resources are preemptible. Suppose a process has printed output on a line printer and is waiting for some other resource before it can generate more output. The line printer really cannot be taken away without disturbing the output.
• This scheme can also lead to starvation for a process that needs several popular resources at the same time. It may keep losing the resources it gets because they do not all become available at the same time.

Circular Wait

We can prevent deadlock by making circular wait impossible. We can define an order by which the process is to get resources to prevent circular wait. For example, each resource type is assigned a number. The process can only get resources in increasing order of those resource numbers.

Suppose the tape drive has a number 1, the disk drive has a number 5, and the printer has a number 12. A process wants to read the disk drive and print out the results. It will first need to allocate disk drive then the printer. It will be prevented from going it in reverse order.

Problems With This Approach

Problems with this approach are as follows:

• The order of resource numbering may prove arbitrary and inconvenient. This is not a very serious problem. There are often natural ways of number resources. For example, processes generally use input devices before output devices.
• The order of numbering can force a process to request resources before they need them. It reduces resource utilization. Suppose a process did some work on the tape before reading input from a card reader. It would still have to request a reader at the start of processing.