Jobs Hub

Deadlocks in Operating System

Sometimes, for many computer applications, a process needs exclusive access to several resources.

Let's suppose, for example, that there are two processes and each wants to record a scanned document on a pen drive. Process X requests permission to use the scanner and is granted it. And process Y is programmed differently and requests the pen drive recorder first, which is also granted. Now X asks for the pen drive recorder, but the request is denied until Y releases it.

Now, instead of releasing the pen drive recorder, Y asks for the scanner. At this point, both processes are blocked and will remain blocked forever. This situation is called "deadlock."

Deadlocks can also occur between computer machines at times. For example, many offices have a LAN (local area network) connected to multiple computers.

Often, devices such as scanners, DVD recorders, printers, and tape drives are connected to the network as shared resources, available to any user on any machine.

Now, unfortunately, all these devices can be reserved remotely; this situation is also called deadlock.

Here is a list of the topics we will cover in this and two other posts about deadlocks in operating systems:

Two of these eight topics are covered in separate posts: "deadlock recovery" and "two-phase locking." The remaining six topics are covered in this post.

Deadlock Resources in Operating System

When processes have been given exclusive access to computer devices, files, etc., deadlocks can happen. A resource can be a computer hardware device or a piece of information.

Generally, a computer has many resources that can be acquired. You can also say that a resource is anything that can be used by only one process at a time.

Requesting the resource, using it, and finally releasing it are the three sequences of events required to use it.

If a resource is not available when it is requested, the requesting process is forced to wait.

In some operating systems, the process is automatically blocked whenever a resource request fails and awakened when it becomes available. And in other operating systems, the resource request fails with an error code, and it is up to the calling process to wait a little while and then try again.

Deadlock Conditions in Operating System

According to computer scientist and programmer Coffman et al., the following four conditions described in the table below must hold for deadlock to occur.

Condition Description
Mutual exclusion condition Each resource in a mutual exclusion condition is either currently assigned to exactly one process or is available.
Hold and wait condition Processes that are currently holding previously granted resources can request new resources while on hold and wait.
No preemption condition Resources previously granted to a process cannot be taken away forcibly in a no preemption condition. The process that is holding them must explicitly release them.
Circular wait condition There must be a circular chain of two or more processes in a circular wait condition, each of which is waiting for a resource held by the next member of the chain.

Deadlock Modeling in Operating System

A computer scientist and programmer named Holt showed how the four conditions for deadlock can be modeled using directed graphs. This graph is depicted below.

deadlock modeling

In the above resource allocation graphs, the figures A, B, and C represent:

Figure Represents
(A) Holding a resource
(B) Requesting a resource
(C) Deadlock

According to Hold, these graphs have the following two types of nodes:

Deadlock Detection in Operating System

The system does not attempt to prevent deadlocks when deadlock detection and recovery techniques are used. However, it allows them to occur, attempts to detect them whenever this occurs, and then takes action to recover after the fact.

The following two cases for deadlock detection will be discussed in this section.

Deadlock Avoidance in Operating System

To build a good computer system, deadlock avoidance must be practiced. In other words, the system must be able to decide whether granting a resource is safe or unsafe. And the system must only make the allocation when it is totally safe.

And the system must only make the allocation when it is totally safe.

Therefore, in every system, deadlock avoidance must be performed. Deadlock avoidance can be performed in one of the following ways or algorithms:

Deadlock Prevention in Operating System

Deadlock avoidance is basically not possible because it requires information about future requests that isn't known.

If we can ensure that at least one of the four conditions for deadlock is never satisfied, then deadlock will be structurally impossible.

Now, the table below briefly describes each of the four conditions for deadlocks (that we have learned about or discussed in previous tutorials).

Condition Description
Attacking the Mutual Exclusion Condition If no resource were ever assigned exclusively to a single process, then we would never have any deadlocks. But allowing two processes to write on the printer at the same time will lead to chaos. By spooling printer output, several processes can produce output at the same time. In this model, the only process that actually requests the physical printer is the printer daemon. Since the daemon never asks for any other resources, we can stop the printer from getting stuck in a deadlock.
Attacking the Hold and Wait Condition If we can prevent processes that hold resources from waiting for more resources, we can eliminate deadlocks. A way to achieve this goal is to require all the processes to request all their resources before starting the execution. If everything is available, then the process will be allocated whatever it needs and can run to completion. If one or more resources are unavailable, nothing will be allocated and the process will be delayed.
Attacking the No Preemption Condition If a process has been assigned the printer and is in the middle of printing its output, forcing the printer away because a needed plotter is not available is tricky at best and impossible at worst.
Attacking the Circular Wait Condition In several ways, the circular wait can be eliminated. One way is to have a rule saying that a process is entitled only to a single resource at any moment. If it needs a second one, then it must release the first one. For a process that needs to copy a huge file from a tape to a printer, this restriction is unacceptable.

Operating System Quiz

« Previous Topic Next Topic »