Deadlock and Circular Waiting in OS

Introduction

Deadlock is an important problem in operating systems because it can stop a group of processes or threads from making any progress. It usually appears when shared resources are held in such a way that every blocked member is waiting for another blocked member.

The main idea is simple, but the effect can be serious. A system may look like it is only slow, but in a deadlock, the involved processes or threads cannot move ahead by themselves.

What Deadlock Means

A deadlock occurs when a set of processes or threads is stuck because each one is waiting for a resource held by another member of the same set. Since no member can continue, none of them reaches the point where it can release the resource it already holds.

This definition has a few important parts:

• Set: Deadlock is not about one isolated process waiting normally. It involves a stuck group of processes or threads.

• Resource: A resource may be a lock, file, memory block, device, database row, or any exclusive object needed for execution.

• Held by another member: The needed resource is already occupied by someone inside the same blocked group.

• None can continue: Every member is waiting, so no one reaches the code or action that would release its current resource.

Circular Waiting Pattern

The simplest deadlock pattern uses two processes and two resources. Suppose process P1 holds resource A and waits for resource B, while process P2 holds resource B and waits for resource A.

Here, P1 cannot get B because P2 is holding it. P2 cannot get A because P1 is holding it. Both are blocked, and the waiting relation forms a cycle.

This is why deadlock is often described as a circular waiting problem. The issue is not just that a resource is busy; the issue is that the waiting chain comes back to the same blocked group.

Two-Lock Deadlock Example

A common deadlock appears when two threads need the same two locks but acquire them in opposite order. If the timing is unlucky, both threads can hold one lock and wait forever for the other.

For example:

Thread 1: lock(A), lock(B), work
Thread 2: lock(B), lock(A), work

The deadlock can happen like this:

• Thread 1 locks A: It now owns the first lock.

• Thread 2 locks B: It now owns the second lock.

• Thread 1 waits for B: But B is already held by Thread 2.

• Thread 2 waits for A: But A is already held by Thread 1.

The code may work many times if the timing is different. That is what makes this kind of deadlock difficult to catch: the bug depends on the order in which the threads actually run.

Deadlock vs Slow Execution

Deadlock and slow execution may both look like delay from the outside, but they are not the same problem. The main difference is whether useful progress is still happening.

A useful debugging question is: are the blocked threads waiting on each other? If yes, deadlock is possible. If the threads are still running but delayed, the problem is more likely a performance bottleneck.

Deadlock in Real Systems

Deadlock is not limited to textbook examples. The same circular waiting pattern can appear in databases, backend services, file systems, and kernel code whenever exclusive resources are acquired in conflicting order.

In a database, one transaction may lock row A and then wait for row B, while another transaction locks row B and waits for row A. Both transactions now hold something the other one needs.

In file systems and kernel code, similar problems can occur with file locks, metadata locks, or internal kernel locks. If different execution paths acquire these locks in inconsistent orders, the system can block important operations.

Summary

Deadlock occurs when a set of processes or threads are stuck because each one is waiting for a resource held by another member of the same set. The central pattern is circular waiting, where no member can continue far enough to release what it already holds.

A two-lock deadlock is a simple example: one thread holds A and waits for B, while another holds B and waits for A. Real systems can face the same issue in databases, services, file systems, and kernel code when shared resources are acquired in conflicting orders.