Deadlock Prevention in Operating Systems (OS)

Resource management is important to ensure that a computer system is running smoothly or not. Deadlock is one of the issues that can interrupt performance. It is a situation or condition in which processes are indefinitely waiting on other processes that, in turn, are also waiting for resources. Operating systems use several alternatives to manage deadlock, with the most practical and most used approach being deadlock prevention in OS, so that an operating system will never be in a deadlocked state. In this article, we will discuss what a deadlock in OS is, what deadlock prevention in OS is, deadlock prevention techniques, the feasibility of deadlock prevention, and a comparison of deadlock avoidance to deadlock prevention.

Table of Contents: 

• What is a Deadlock in OS?
• What is a Deadlock Prevention in OS?
• Importance of Preventing Deadlocks in OS
• Deadlock Prevention Techniques in OS
  • Mutual Exclusion
  • Hold and Wait
  • No Preemption
  • Circular Wait
• Feasibility of Deadlock Prevention
• Prevention vs Avoidance of Deadlock
• Conclusion

What is a Deadlock in OS?

A deadlock in an OS is a situation or condition where a set of processes is blocked because each process is waiting for a resource that is held by another process in the same set. This creates a cycle where no process can proceed. Deadlocks happen when these four conditions, mutual exclusion, hold and wait, no preemption, and circular wait, are met. It results in a complete halt in system activity involving those processes.

There are three main ways to handle deadlock in an operating system:

1. Deadlock Prevention or Avoidance: These methods take actions to make sure that the system never enters a deadlock state by preventing or avoiding the conditions that may cause deadlock.
2. Deadlock Detection and Recovery: They allow deadlocks to occur, detect them using algorithms, and then take action to recover.
3. Ignore the Problem (Ostrich Algorithm): It simply ignores deadlocks by assuming that they are rare and not worth the overhead of handling. This is used in systems like UNIX.

What is a Deadlock Prevention in OS?

Deadlock prevention in OS is a strategy to make sure that at least one of the necessary conditions for deadlock does not occur. It proactively avoids deadlocks by restricting how resources are requested. For example, it may require processes to request all needed resources at once or allow preemption of resources. By breaking one of the four deadlock conditions, such as mutual exclusion, hold and wait, no preemption, and circular wait, the system avoids entering a deadlock state.

Importance of Preventing Deadlocks in OS

1. Ensures Reliability of the System: Preventing deadlocks keeps the system responsive and also avoids the process freezing.
2. Efficient Resource Utilization: With the help of deadlock prevention, resources are not held indefinitely, and thus, it allows smoother task execution and better throughput.
3. Prevents System Freezing or Crashing: Deadlocks can lead to freezing or crashing of the different parts of the system, and this can be easily prevented by prevention.
4. Improves User Experience: Underlying systems that may cause lockup surprises may allow a more stable and predictable environment for the user.
5. Minimizes Complex Recovery: By allowing deadlocks to be prevented, the complex recovery option is also minimized.

Deadlock Prevention Techniques in OS

Deadlock prevention techniques work by violating at least one of the four necessary conditions for deadlock. By doing so, the system ensures that deadlocks cannot occur. Let’s look at how each condition can be violated to make resource requests safe:

1. Mutual Exclusion

Mutual exclusion is basically the inability of some resources to be shared and can be accessed by only one process at any given time. To prevent deadlock, the system tries to remove the mutual exclusion by making resources sharable where it is possible. For example, read-only files can be accessed by multiple processes simultaneously. However, not all resources (like printers) can be shared, so this method has limited use. Therefore, mutual exclusion is often necessary and cannot always be violated. 

To get this point, we can consider the following example that will give us an understanding of the mutual exclusion and how the violation of it will help avoid the deadlock. 

Consider a device like a printer that would be used by several people in an office. When a person is getting something printed then others will have to wait. This is a mutual exclusion because the printer cannot be shared. To prevent the deadlock, we avoid this condition if possible by using the sharable resources. 

Therefore, we can say that deadlock can be avoided by making systems such that their resources can be shared safely, although there will always be resources that need to use mutual exclusion (such as printers).

2. Hold and Wait 

Hold and wait is the condition that occurs when a process is holding one resource while waiting to acquire additional resources. To prevent this, the system may need various processes to request all the required resources at once before execution. If all the resources are not available, the process must wait without holding any other process. This reduces the chance of holding one resource while waiting for another. However, it may lead to low resource utilization and process delays.

To get this condition, we can consider the following example that will give us an understanding of the hold-and-wait and how the violation of it will help avoid the deadlock. 

Consider a person using a scanner, and then he or she needs a printer to complete his or her task. Now, if he holds the scanner while waiting for the printer, then others may end up waiting for the printer, which is occupied. In this case, a deadlock occurs if another person is doing just the opposite of this. 

To prevent this case, the system would demand that the person request the scanner and the printer simultaneously. When both are unavailable, then the other does not get any; this prevents the wait-and-hold condition from eliminating the risk of deadlock.

In the diagram that is given below,

• Resource 1 is allocated to Process 2
• Resource 2 and Resource 3 are allocated to Process 1
• Process 1 is waiting for Resource 1 while holding Resource 2 and Resource 3
• Process 2 is waiting for Resource 2 while holding Resource 1

This creates a circular dependency, resulting in a deadlock.

Two Ways to Eliminate Hold and Wait

Here are the two ways by which we can eliminate the hold-and-wait condition.

1. By Eliminating Wait (Request All at Once)

• The process must request all the required resources in advance before starting the execution.
• If all resources are not available, then the process waits without holding any.

Example: Process 1 declares beforehand that it needs Resource 1, Resource 2, and Resource 3. It starts only when all are available.

2. By Eliminating Hold (Release Before Request)

• The process must release all the currently held resources before making a new request.
• This avoids holding resources while waiting, and thus breaking the hold-and-wait condition.

Example: Before requesting Resource 1, Process 1 releases Resource 2 and Resource 3, so it doesn’t hold while waiting.

3. No preemption

No preemption is the condition in which a process cannot be forced to release a resource; it must do so voluntarily. To prevent deadlock, the OS can be allowed to preempt means to take back a resource from a process if it’s needed by another process. 

To get this third condition, we can consider the following example that will give us an understanding of the no-preemption and how the violation of it will help avoid the deadlock.

Suppose Process A holds Resource X and requests Resource Y, which is currently held by Process B. In this case, instead of allowing Process A to wait, the system preempts Resource X from Process A, which means Process A must release Resource X and re-request it later, along with Resource Y.

This will prevent the deadlock by making sure that no process holds a resource while waiting for another, and thus breaking the potential circular wait. 

Note: This only works well for CPU or memory, but not for resources like printers or disk I/O that are non-preemptible.

4. Circular Wait

Circular wait is the condition that occurs when a group of processes are each waiting for a resource held by the next process in a circular chain. This is one of the necessary conditions for a deadlock. To prevent circular wait, the system imposes a fixed order in which the resources must be requested for the complete process. Each process must request resources in increasing order of their assigned numbers, and cannot request a lower-numbered resource after acquiring a higher-numbered one.

We can consider the following example that will give us an understanding of the circular wait and how the violation of it will help avoid the deadlock.

Let’s say resources are ordered as:
R1 (1), R2 (2), R3 (3)

• If Process A needs R2 and R3, it must request R2 first, then R3.
• If Process B needs R1 and R3, it must request R1 before R3.

By following this rule, circular waiting is impossible, as no process can hold a higher-numbered resource and request a lower-numbered one.

Feasibility of Deadlock Prevention

1. In practice, it is impossible to completely remove mutual exclusion, because many resources (for example, printers) simply cannot be shared in this situation.
2. Removing hold and wait by making processes request all resources they will need at one time essentially brings resource utilization down and wait time up.
3. Preempting resources is very difficult or unsafe, especially for non-preemptable resources (files or printers).
4. You can avoid circular wait by putting ordering constraints on the acquisition of resources, which is probably the most practical for the deadlock avoidance strategies.
5. Deadlock prevention increases complexity in the system and may impose some penalties in performance or resource utilization, at worst.
6. Deadlock prevention is a more suitable option for simplified, real-time systems, where predictability is most important.
7. For general-purpose systems, deadlock detection and recovery, or deadlock avoidance, are likely more effective in terms of efficiency and flexibility for avoiding deadlock.

Prevention vs Avoidance of Deadlock

Conclusion

Prevention of deadlock in operating systems is an important strategy that removes some of the conditions required to guarantee the absence of deadlocks in the system. Although effective in theory, its implementation has several challenges that include difficulty in using fewer of its resources, complexity during the process, and infeasibility of some resources, such as the use of printers. From the above-discussed techniques, avoiding circular wait through resource ordering is the most practical. However, in general-purpose systems, deadlock avoidance or detection, and recovery methods offer more flexibility and better performance.

More Related Topics:

• Process in Operating System
• Segmentation in Operating System
• Types of Operating System
• Thrashing in Operating System
• CPU Scheduling in Operating System

Deadlock Prevention in Operating Systems (OS) – FAQs