1. Introduction

So far, we have studied the first three necessary conditions for deadlock:

• Mutual Exclusion

• Hold and Wait

• No Preemption

Now we arrive at the fourth and final condition:

Circular Wait

This condition completes the deadlock cycle and is often considered the final requirement that transforms resource waiting into a true deadlock.

While processes may frequently wait for resources during normal execution, deadlock occurs only when a circular dependency forms among processes. In such a situation, every process in the cycle is waiting for another process in the same cycle, making progress impossible.

Without Circular Wait:

• Some processes may be blocked temporarily

• Resources are eventually released

• Waiting processes continue execution

• The system continues to make progress

However, once a circular dependency is established:

Every Process Waits
For Another Process
In The Same Cycle

and no process can proceed.

This condition represents the final step in deadlock formation.

2. Definition of Circular Wait

Circular Wait is defined as:

A set of processes exists such that each process is waiting for a resource held by the next process in the set, forming a closed cycle.

In simpler terms:

P1 Waiting For P2
P2 Waiting For P3
P3 Waiting For P1

The waiting relationship forms a loop.

Since every process depends on another blocked process:

No Process Can Continue

This closed dependency loop is called a Circular Wait.

3. Understanding the Core Idea

Consider three processes:

P1

P2

P3

and three resources:

Resource A

Resource B

Resource C

Suppose:

P1 Holds A
Waiting For B

P2 Holds B
Waiting For C

P3 Holds C
Waiting For A

The dependency chain becomes:

P1 → P2 → P3 → P1

Notice that the chain returns to its starting point.

Every process is waiting.

Every required resource is already allocated.

No resource can be released.

Result:

Deadlock

This is the essence of Circular Wait.

4. Why Circular Wait Is Dangerous

Circular Wait is often viewed as:

The final trigger that converts ordinary waiting into deadlock.

Consider a dependency chain:

P1 Waiting For P2

P2 Waiting For P3

If:

P3 Not Waiting

then:

P3 Finishes

and releases its resources.

Eventually:

P2 Continues

and later:

P1 Continues

No deadlock occurs.

However, when the chain becomes:

P1 → P2 → P3 → P1

every process depends on another blocked process.

Consequently:

No Process Finishes

No Resource Released

No Progress Possible

The system becomes permanently blocked.

5. Step-by-Step Deadlock Formation

Consider:

Processes:
P1, P2, P3

Resources:
A, B, C

Step 1 – P1 Acquires Resource A

P1 → A

Step 2 – P2 Acquires Resource B

P2 → B

Step 3 – P3 Acquires Resource C

P3 → C

Current allocation:

P1 Holds A

P2 Holds B

P3 Holds C

Step 4 – Additional Requests Appear

Now:

P1 Requests B

P2 Requests C

P3 Requests A

However:

B Held By P2

C Held By P3

A Held By P1

Step 5 – Circular Dependency Forms

Waiting relationships:

P1 Waiting For P2

P2 Waiting For P3

P3 Waiting For P1

Dependency cycle:

P1 → P2 → P3 → P1

The cycle is complete.

Deadlock occurs.

6. Resource Allocation Graph (Very Important)

Operating systems commonly represent resource dependencies using a:

Resource Allocation Graph (RAG)

A Resource Allocation Graph is a directed graph used to model:

• Resource ownership

• Resource requests

• Process dependencies

Graph Components

Process Nodes

Represented using circles.

○ P1
○ P2
○ P3

Resource Nodes

Represented using rectangles.

□ A
□ B
□ C

Types of Edges

Allocation Edge

Resource → Process

Meaning:

Resource Assigned

Example:

A → P1

Request Edge

Process → Resource

Meaning:

Resource Requested

Example:

P1 → B

Resource Allocation Graphs are extensively used in deadlock analysis.

7. Why Cycles Matter in Graphs

The operating system analyzes Resource Allocation Graphs to determine whether deadlock may exist.

Case 1 – No Cycle

Example:

P1 Waiting For P2

P2 Waiting For P3

P3 Not Waiting

Eventually:

P3 Finishes

Then:

P2 Continues

Then:

P1 Continues

Result:

No Deadlock

Case 2 – Cycle Exists

Example:

P1 → P2

P2 → P3

P3 → P1

Now:

Every Process Waiting

No process can proceed.

No resource can be released.

Result:

Deadlock

Important Observation

For systems with one instance of each resource type:

A cycle in the Resource Allocation Graph implies deadlock.

This is a very important examination point.

8. Circular Wait and Dependency Chains

Circular Wait is closely related to Hold and Wait.

The distinction is important:

Example of Hold and Wait:

P1 Waiting For P2

P2 Waiting For P3

This is only a chain.

Example of Circular Wait:

P1 Waiting For P2

P2 Waiting For P3

P3 Waiting For P1

This is a cycle.

The cycle is what causes deadlock.

9. Operating System Perspective

The operating system continuously maintains information about:

Allocated Resources

Pending Requests

Waiting Relationships

Using this information, the OS can:

Detect Cycles

Predict Unsafe States

Initiate Recovery Actions

These activities form the basis of:

• Deadlock Detection

• Deadlock Avoidance

• Deadlock Recovery

10. Deadlock Prevention Strategy

One of the most effective methods for preventing Circular Wait is:

Resource Ordering

The operating system assigns a fixed numerical order to every resource type.

Example:

1 → Printer

2 → Scanner

3 → Disk

4 → Database

Processes must request resources only in increasing order.

Valid Request Sequence

Printer → Scanner → Disk

Invalid Request Sequence

Disk → Printer

Not permitted.

This ordering rule prevents cycles from forming.

11. Why Resource Ordering Works

Suppose all processes obey:

Increasing Resource Order

Then a cycle such as:

P1 → P2 → P3 → P1

cannot form.

Why?

Because resource requests always move in the same direction.

There is no way to return to an earlier resource.

Therefore:

Circular Dependencies Impossible

and:

Deadlock Prevented

This technique breaks the Circular Wait condition directly.

12. Advantages of Breaking Circular Wait

Eliminating Circular Wait provides several benefits.

Prevents Deadlock

Deadlock Impossible

if the ordering rule is followed.

Simplifies Resource Management

Dependencies become easier to analyze.

Predictable Allocation

Resource acquisition follows a consistent pattern.

Structured Resource Requests

13. Disadvantages of Resource Ordering

Despite its effectiveness, resource ordering has limitations.

13.1 Reduced Flexibility

Processes must obey strict ordering rules.

Less Freedom

during execution.

13.2 Difficult for Large Systems

Large systems may contain hundreds of resource types.

Managing a global order becomes challenging.

Ordering Complexity

13.3 Possible Resource Underutilization

Processes may acquire resources earlier than actually needed.

Resources Reserved Prematurely

This can reduce utilization.

14. Real-World Analogy

Imagine four mechanics working in a garage.

Current situation:

Mechanic A Holds Wrench
Waiting For Screwdriver

Mechanic B Holds Screwdriver
Waiting For Hammer

Mechanic C Holds Hammer
Waiting For Pliers

Mechanic D Holds Pliers
Waiting For Wrench

Dependency cycle:

A → B → C → D → A

Everyone waits.

Nobody releases tools.

Work stops completely.

This is a real-world example of Circular Wait.

15. Relationship with Other Conditions

Circular Wait alone does not create deadlock.

All four conditions must exist simultaneously.

Deadlock occurs only when:

Mutual Exclusion
        +
Hold and Wait
        +
No Preemption
        +
Circular Wait

are all present together.

16. How Operating Systems Handle Deadlocks

Modern operating systems generally adopt one of four strategies.

16.1 Prevention

Break at least one necessary condition.

Example:

Eliminate Circular Wait

using resource ordering.

16.2 Avoidance

Allocate resources carefully to avoid unsafe states.

Example:

Banker's Algorithm

16.3 Detection

Allow deadlocks to occur and detect them dynamically.

Example:

Cycle Detection

in Resource Allocation Graphs.

16.4 Recovery

Once detected:

Terminate Processes

or

Rollback Execution

to break the deadlock.

These approaches form the foundation of modern deadlock management.