Four Necessary Conditions for Deadlock

• Mutual Exclusion: At least one resource must be held in a non-shareable mode.
• Hold and Wait: A process holds at least one resource and waits for others.
• No Preemption: Resources cannot be forcibly taken; must be released voluntarily.
• Circular Wait: A set of processes are waiting for each other in a circular chain.

Circular Wait (Explanation):

• In circular wait, each process is waiting for a resource held by another process.
• This forms a cycle (e.g., P1 → P2 → P3 → P1).
• None of the processes can proceed, causing a deadlock.

Example:

• P1 holds R1 and waits for R2
• P2 holds R2 and waits for R3
• P3 holds R3 and waits for R1

Deadlock is a situation in an Operating System where two or more processes are unable to continue execution because each process is waiting for a resource that is held by another process.

Two Situations Where Deadlock Occurs

• Mutual Exclusion: A resource can be used by only one process at a time. If another process requests the same resource, it must wait until the resource is released.
• Circular Wait: Deadlock occurs when a group of processes form a circular chain where each process is waiting for a resource held by the next process in the chain.

Circular Wait

• Circular wait is one of the necessary conditions for deadlock.
• It occurs when a group of processes are waiting for resources in a circular chain.
• In this situation, each process holds at least one resource and waits for another resource held by the next process in the cycle.

Example:

• Process P1 holds Resource R1 and waits for R2.
• Process P2 holds Resource R2 and waits for R3.
• Process P3 holds Resource R3 and waits for R1.

This creates a circular waiting condition.

Cycle in Resource Allocation Graph (RAG)

If a cycle exists in a Resource Allocation Graph, it does not always guarantee deadlock.

• If each resource type has only one instance, then a cycle definitely indicates deadlock.
• If resource types have multiple instances, then a cycle may exist without deadlock.

So, a cycle is:

• A necessary condition for deadlock
• But not always a sufficient condition

Deadlock Detection using Resource Allocation Graph

To detect deadlock using Resource Allocation Graph (RAG), we follow these steps −

• If RAG contains no cycles, then there is no deadlock in the system.
• If RAG is of single instance resources and it contains a cycle, then there is a deadlock in the system.
• If RAG is of multiple instance resources and it contains a cycle, then deadlock may or may not exist. To check for deadlock, we need convert multiple instance RAG to single instance RAG, by treating each instance of a resource as a separate resource type.

In the graph:

• Resource R1 has only one instance.
• Resource R2 has two instances.
• P1 is holding R1 and requesting R2.
• P2 is holding one instance of R2 and requesting R1.
• P3 is using another instance of R2.

A cycle exists in the graph: P1 → R2 → P2 → R1 → P1

But this graph does not indicate deadlock.

Reason:

Resource R2 has multiple instances. One instance of R2 is currently allocated to P3.

If P3 finishes its work and releases R2, then:

• P1 can obtain R2 and complete execution.
• After P1 completes, it releases R1.
• Then P2 can obtain R1 and continue execution.

Since the processes can still proceed and resources can eventually be released, the system is not permanently blocked.

The Need matrix is calculated as: Need = Max - Allocation For each process, we subtract the Allocation from the Max to get the Need Matrix.

Step-by-step checking for our system:

• P0: Needs [0, 0, 0, 0] ≤ Available [1, 5, 2, 0] → yes, so finish P0.
• Update Available by adding P0's allocation: [1, 5, 2, 0] + [0, 0, 1, 2] = [1, 5, 3, 2]
• P1: Needs [0, 7, 5, 0] ≤ Available [1, 5, 3, 2] → no, cannot finish yet.
• P2: Needs [1, 0, 0, 2] ≤ Available [1, 5, 3, 2] → yes, finish P2.
• Update Available : [1, 5, 3, 2] + [1, 3, 5, 4] = [2, 8, 8, 6]
• P3: Needs [0, 0, 2, 0] ≤ Available [2, 8, 8, 6] → yes, finish P3.
• Update Available : [2, 8, 8, 6] + [0, 6, 3, 2] = [2, 14, 11, 8]
• P4: Needs [0, 6, 4, 2] ≤ Available [2, 14, 11, 8] → yes, finish P4.
• Update Available : [2, 14, 11, 8] + [0, 0, 1, 4] = [2, 14, 12, 12]
• P1 (rechecked): Needs [0, 7, 5, 0] ≤ Available [2, 14, 12, 12] → yes, finish P1.
• Update Available : [2, 14, 12, 12] + [1, 0, 0, 0] = [3, 14, 12, 12]

Since all processes can finish in this order, the system is in a safe state.

Safe sequence: <P0, P2, P3, P4, P1>

Deadlock in an operating system occurs when two or more processes are stuck and cannot proceed because they are each waiting for a resource that another process holds. Essentially, the processes are in a "waiting loop," and none can continue because they are all waiting for each other to release resources.

Example: Imagine two people on a narrow staircase. One is going up, and the other is going down. Neither can move because the other person is blocking their path, and neither is willing to back up. They are stuck, waiting for the other to move first, which will never happen.

Necessary condition for occuring deadlock / Coffman Conditions

For a deadlock to happen, four conditions must all be true at the same time. These are called the Coffman conditions, named after the researchers who explained them.

1. Mutual Exclusion: A resource can only be used by one process at a time. If a process is using a resource, no other process can use it until the first process releases it.
2. Hold and Wait: A process is holding at least one resource and is waiting for additional resources that are currently held by other processes.
3. No Preemption: Resources cannot be taken away from a process forcefully. A process can only release resources voluntarily when it is no longer needed.
4. Circular Wait: A cycle exists where each process in the cycle is waiting for a resource that the next process holds. For example, Process A is waiting for Process B's resource, Process B is waiting for Process C's resource, and Process C is waiting for Process A's resource.

🎥 Video Solution: Deadlock & its Necessary Condition

✅ Can Deadlock Involve Only a Single Process?

In general, a deadlock cannot occur with only one process. The key characteristic of deadlock is that multiple processes are waiting for each other to release resources. A single process cannot create circular waiting, which is required for deadlock.