Deadlock in Operating System: Conditions, RAG, Prevention, Avoidance, Banker’s Algorithm, Detection & Recovery

Introduction to Deadlock

Modern operating systems allow many processes to execute concurrently. During execution, processes may require resources such as memory, files, devices, locks, printers, database objects, or other system resources. Since these resources are limited, the operating system has to decide when a resource can be assigned to a process.

Most resource requests are handled normally. A process receives the required resource, performs its operation, and eventually releases that resource. However, a special situation can occur when a group of processes starts waiting for resources held by one another.

If none of those processes can continue because each is waiting for another process to release a resource, the system may enter a deadlock.

Deadlock is therefore an important Operating System concept because it connects process management, resource allocation, synchronization, scheduling, and system performance.

What is Deadlock in Operating System?

A deadlock is a situation in which a set of processes becomes permanently blocked because every process in that set is waiting for a resource or event that can only become available after another process in the same set makes progress.

The important word is dependency. A process waiting for a resource is not automatically deadlocked. Waiting is normal in a multitasking operating system. Deadlock occurs when the waiting relationships form a situation from which the involved processes cannot progress under the current resource-allocation state.

Deadlock Example

Consider two processes and two resources:

Process	Resource Held	Resource Requested	Status
P1	R1	R2	Waiting
P2	R2	R1	Waiting

P1 cannot proceed because R2 is held by P2. P2 cannot proceed because R1 is held by P1. Therefore, neither process can reach the point where it releases its current resource.

This circular dependency is the basic idea behind the classical deadlock example.

Four Necessary Conditions for Deadlock

A classical deadlock requires four conditions to exist simultaneously. These are commonly referred to as the Coffman conditions. If at least one of these conditions can be prevented, the classical deadlock situation can be prevented.

1. Mutual Exclusion

Mutual exclusion means that a resource can be assigned to only one process at a particular time when the resource requires exclusive access.

For example, an exclusive lock cannot normally be owned by two processes simultaneously. While one process owns it, another process requesting the same lock must wait.

2. Hold and Wait

Hold and wait occurs when a process already holding one or more resources requests additional resources while continuing to hold the resources it already owns.

For example, P1 may hold R1 and request R2. If R2 is unavailable, P1 continues holding R1 while waiting.

3. No Preemption

No preemption means that a resource cannot simply be taken away from a process by the operating system while it is being used. The process normally has to release the resource voluntarily or reach an appropriate point where controlled preemption is safe.

4. Circular Wait

Circular wait occurs when a sequence of processes exists in which every process is waiting for a resource held by the next process in the sequence.

The last process eventually waits for a resource held by the first process, completing the cycle.

Resource Allocation Graph (RAG)

A Resource Allocation Graph (RAG) is a graphical representation used to show the relationship between processes and resources.

It is particularly useful when studying resource requests, resource assignments, and possible circular dependencies.

Components of RAG

• Process: generally represented by a circle.
• Resource: generally represented by a square or rectangle.
• Request Edge: Process → Resource.
• Assignment Edge: Resource → Process.

Resource Allocation Graph representing a circular resource dependency.

Request Edge

A request edge is drawn from a process to a resource when the process is waiting for that resource.

Assignment Edge

An assignment edge is drawn from a resource to a process when the resource has already been allocated to that process.

Cycle in Resource Allocation Graph

A cycle is an important indication of circular dependency. However, its interpretation depends on the number of instances of each resource type.

Methods for Handling Deadlock

An operating system can deal with deadlocks using different strategies. The major approaches are prevention, avoidance, detection and recovery, and in some systems, simply ignoring the possibility of deadlock.

Deadlock Prevention

Deadlock prevention works by ensuring that at least one of the four necessary conditions cannot be satisfied.

Preventing Mutual Exclusion

If a resource can safely be shared instead of being exclusively owned, sharing can reduce the possibility of deadlock.

However, many resources require exclusive access. Therefore, this method cannot be applied universally.

Preventing Hold and Wait

One approach is to require a process to request all the resources it needs before starting its execution phase that requires those resources.

Another approach is to make a process release its currently held resources before requesting additional resources.

The disadvantage is that resources may remain reserved even when the process is not currently using them.

Preventing No Preemption

If a resource can safely be preempted, the operating system may take it away from a process under suitable conditions.

This technique is difficult for resources whose state cannot be safely interrupted or restored.

Preventing Circular Wait

A common strategy is to assign an ordering to resource types and require processes to request resources according to that order.

Deadlock Avoidance

Deadlock avoidance does not necessarily eliminate the four necessary conditions. Instead, it evaluates resource requests and grants them only when doing so keeps the system in a state from which all processes can potentially complete.

The central concepts in deadlock avoidance are safe state and unsafe state.

Safe State

A state is safe if there exists at least one possible sequence in which all processes can obtain their remaining resources, complete their execution, and release the resources they hold.

Unsafe State

An unsafe state means that the operating system can no longer guarantee such a completion sequence using the current resource information.

Banker’s Algorithm

Banker’s Algorithm is a classical deadlock-avoidance technique. It checks whether granting a resource request can leave the system in a safe state.

The algorithm assumes that the maximum possible resource requirement of each process is known. Before granting selected requests, the operating system performs a safety check.

Data Structures Used in Banker’s Algorithm

Term	Meaning
Available	Number of currently available instances of each resource type.
Max	Maximum number of resources of each type that a process may require.
Allocation	Resources currently allocated to the process.
Need	Remaining resources that the process may still require.

Banker’s Algorithm Solved Numerical Example

Consider five processes P1, P2, P3, P4 and P5 and three resource types A, B and C.

Step 1: Given Allocation and Maximum Requirement

Process	Allocation (A B C)	Max (A B C)
P1	0 1 0	7 5 3
P2	2 0 0	3 2 2
P3	3 0 2	9 0 2
P4	2 1 1	2 2 2
P5	0 0 2	4 3 3

Available = (3, 3, 2)

Step 2: Calculate Need Matrix

Use the formula:

Process	Max	Allocation	Need
P1	(7, 5, 3)	(0, 1, 0)	(7, 4, 3)
P2	(3, 2, 2)	(2, 0, 0)	(1, 2, 2)
P3	(9, 0, 2)	(3, 0, 2)	(6, 0, 0)
P4	(2, 2, 2)	(2, 1, 1)	(0, 1, 1)
P5	(4, 3, 3)	(0, 0, 2)	(4, 3, 1)

Step 3: Initialize Work

Initially:

Step 4: Check P1

P1 requires:

Compare:

Therefore P1 cannot be selected at this point.

Step 5: Check P2

P2 requires:

Since:

P2 can complete.

After P2 completes, its allocated resources are released:

Step 6: Check P4

P4 requires:

Since:

P4 can complete.

Step 7: Check P5

P5 requires:

Since:

P5 can complete.

Step 8: Check P1 Again

P1 requires:

Current Work is (7, 4, 5). Therefore:

P1 can complete.

Step 9: Check P3

P3 requires:

Since:

P3 can also complete.

Since all five processes can be marked as completed in a valid order, the given state is a safe state.

Safety Algorithm

The safety algorithm determines whether the current resource allocation state is safe.

Resource Request Algorithm

The resource-request algorithm determines whether a particular process request can be granted without making the system unsafe.

Step 1: Check Request Against Need

If this condition fails, the process is requesting more resources than its declared maximum remaining requirement.

Step 2: Check Available Resources

If sufficient resources are not currently available, the process must wait.

Step 3: Pretend to Grant the Request

If both conditions are satisfied, temporarily update the resource values:

• Available = Available − Request
• Allocation = Allocation + Request
• Need = Need − Request

Step 4: Perform Safety Test

Run the safety algorithm on the temporary state. If the state remains safe, the request can be granted. Otherwise, the temporary allocation must be cancelled and the process waits.

Deadlock Detection

In deadlock detection, the system does not necessarily prevent every potentially unsafe allocation. Instead, it allows resource allocation according to its normal policy and periodically or when appropriate checks whether a deadlock has formed.

Detection with Single Resource Instance

When each resource type has only one instance, a Wait-For Graph can be used.

In a wait-for graph, only processes are represented. An edge Pi → Pj means that Pi is waiting for a resource currently held by Pj.

In the single-instance case, such a cycle represents a deadlock among those processes.

Detection with Multiple Resource Instances

When resource types have multiple instances, cycle detection alone is insufficient. The available resource vector, current allocations, and outstanding requests must also be considered.

The system can simulate completion of processes whose remaining requests can currently be satisfied. When a process is assumed to finish, its allocated resources are returned to the available pool.

Deadlock Recovery

Once a deadlock has been detected, the operating system needs to break the dependency so that useful work can continue.

1. Process Termination

One or more processes involved in the deadlock may be terminated. Terminating a process releases the resources held by that process.

The operating system may consider process priority, amount of work already completed, number of resources held, restart cost, and importance of the process before selecting a victim.

2. Resource Preemption

If the resource supports safe preemption, a resource can be removed from one process and assigned to another process.

The affected process may need to wait, restart, or be rolled back depending on the resource and application.

3. Process Rollback

Rollback restores a process to an earlier safe state, often using checkpoint information. After releasing selected resources, the system can allow other processes to complete.

Deadlock Ignorance

Some operating systems or environments may choose not to maintain a comprehensive deadlock-handling mechanism for every possible situation. This approach is sometimes described using the Ostrich approach.

The reasoning is that the cost of continuously preventing or detecting every possible deadlock may be greater than the expected benefit for a particular environment.

The disadvantage is that an actual deadlock may require an application restart, process termination, or user intervention.

Deadlock Prevention vs Avoidance vs Detection & Recovery

Deadlock vs Starvation

Deadlock and starvation both involve processes waiting, but they are different problems.

Common Mistakes Students Make

• Considering every waiting process deadlocked: Waiting is normal in an operating system.
• Forgetting the four necessary conditions: Deadlock analysis should consider all four conditions.
• Assuming every RAG cycle proves deadlock: Resource-instance count matters.
• Confusing safe and unsafe states: An unsafe state does not necessarily mean deadlock has already occurred.
• Using Max instead of Need: Banker’s safety test compares remaining Need with Work.
• Adding Need instead of Allocation: After a process is assumed to complete, its Allocation is returned to Work.
• Incorrect matrix subtraction: Calculate Max − Allocation separately for every resource type.

Key Takeaways

• Deadlock is a state of permanent blocking caused by unresolved resource dependencies.
• The four necessary conditions are mutual exclusion, hold and wait, no preemption and circular wait.
• A Resource Allocation Graph represents processes, resources, requests and assignments.
• Deadlock prevention works by breaking at least one necessary condition.
• Deadlock avoidance checks whether resource allocation can keep the system safe.
• Banker’s Algorithm is a classical deadlock-avoidance algorithm.
• The most important Banker’s Algorithm formula is: Need = Max − Allocation.
• A safe sequence demonstrates that processes can potentially complete in a valid order.
• Deadlock detection identifies a deadlock after it has formed.
• Recovery can use process termination, resource preemption or rollback.

Practice Questions

1. Define deadlock in an operating system with a suitable example.
2. Explain the four necessary conditions for deadlock.
3. What is a Resource Allocation Graph?
4. Differentiate between request edge and assignment edge.
5. Explain deadlock prevention with suitable techniques.
6. What is the difference between deadlock prevention and avoidance?
7. Explain safe and unsafe states.
8. What is Banker’s Algorithm?
9. Explain the formula Need = Max − Allocation.
10. Solve a Banker’s Algorithm numerical and find the safe sequence.
11. Explain the safety algorithm.
12. What is the purpose of the resource-request algorithm?
13. Explain deadlock detection for single-instance resources.
14. Explain different deadlock recovery techniques.
15. Differentiate between deadlock and starvation.

Frequently Asked Questions

Chapter Summary

Conclusion

Deadlock is one of the most important topics in Operating Systems because it demonstrates how processes and limited resources can interact in unexpected ways. The key to understanding the topic is not simply memorizing its definition but learning how resource dependencies are created and how those dependencies can be controlled.

The four necessary conditions provide the foundation for deadlock analysis. Resource Allocation Graphs help visualize the relationships, while prevention and avoidance provide ways of reducing the risk of deadlock. Banker’s Algorithm is particularly important for numerical questions because it provides a systematic way to determine whether a state is safe.

For exam problems involving Banker’s Algorithm, remember the practical sequence: calculate Need, set Work equal to Available, find an eligible process, add its Allocation to Work, and repeat until a safe sequence is obtained or no eligible process remains.

Understanding these steps makes deadlock questions much easier to solve in semester examinations, competitive examinations, viva, interviews and Operating System revision.

---

---