- Operating Systems Course
- Operating System Tutorial
- History of Operating System
- Personal Computer OS
- OS Processes
- OS Process Model
- OS Process Creation
- OS Deadlocks
- OS Deadlock Recovery
- OS Two-Phase Locking
- OS Memory Management
- OS Mono programming
- OS Shared Pages
- Operating System Input/Output
- OS Input/Output Devices
- OS Input/Output Software Layers
- OS Disk Hardware
- OS Files
- OS File Naming
- OS File Types
- OS Hierarchical Directory System
- OS Directory Operations
- OS File Operations
- Multimedia Operating System
- OS Multiprocessors
- Operating System Security
- OS User Authentication
- OS Trap Doors
- OS Viruses
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:
- Deadlock resources
- Deadlock Conditions
- Deadlock Modeling
- Deadlock Detection
- Deadlock Recovery
- Deadlock Avoidance
- Deadlock Prevention
- Two-Phase Locking
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.
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:
- Processes are shown in the graph as circles.
- Resources are shown in the graph as squares.
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.
- Detecting deadlocks with one resource of each type: In this case, only one resource of each type exists. Such a type of system might have one plotter, one scanner, one tape drive, and one DVD recorder, but no more than one of each class of resource.
- Detecting deadlocks with multiple resources of each type: When there are multiple copies of some of the resources, a different method of deadlock detection is required.
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:
- Resource trajectories
- Safe and unsafe states
- The Banker's algorithm for a single resource
- The Banker's algorithm for multiple resource
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. |
« Previous Topic Next Topic »