Deadlock Detection

 

Deadlock Detection

If a system does not use:

  • Deadlock Prevention, or

  • Deadlock Avoidance

then a deadlock may occur.

In such systems, the OS must provide:

  1. A deadlock-detection algorithm

  2. A recovery algorithm

However, detection and recovery introduce overhead:

  • Runtime cost of maintaining information

  • Cost of executing detection algorithm

  • Losses during recovery (e.g., terminating processes, rollback)

Single Instance of Each Resource Type

If each resource type has only one instance, deadlock detection is simpler.

In this case, we use a special graph called a:

Wait-For Graph

What is a Wait-For Graph?

It is derived from the Resource-Allocation Graph by:

  • Removing all resource nodes

  • Collapsing the edges

Meaning of Edges

In a wait-for graph:

An edge

Ti → Tj

means:

Thread Ti is waiting for thread Tj to release a resource.

More precisely:

An edge Ti → Tj exists in the wait-for graph
if and only if the resource-allocation graph contains:

Ti → Rq   and   Rq → Tj

for some resource Rq.

That means:

  • Ti is requesting resource Rq

  • Rq is currently allocated to Tj

  • Therefore, Ti is waiting for Tj




Deadlock Condition

A deadlock exists:

If and only if the wait-for graph contains a cycle.

So detection becomes:

✔ Construct wait-for graph
✔ Check if there is a cycle

If cycle exists → Deadlock
If no cycle → No deadlock

Cycle Detection Complexity

Detecting a cycle in a graph requires:

O(n2)O(n^2)

Where:

  • n = number of threads (vertices)

Practical Example (Linux – BCC Toolkit)

The BCC toolkit (mentioned in the text) provides a deadlock detection tool for:

  • Pthreads mutex locks

  • Linux systems

How it works:

  • Inserts probes into:

    • pthread_mutex_lock()

    • pthread_mutex_unlock()

  • Builds a wait-for graph dynamically

  • Reports possible deadlock if a cycle is detected

Summary (Single Instance Case)

FeatureDescription
Resource instances        One per type
Graph used        Wait-for graph
Deadlock condition        Cycle in graph
Time complexity        O(n²)
Used in practice        Mutex deadlock detection

Deadlock Detection: Several Instances of a Resource Type

When a system has multiple instances of each resource type, the wait-for graph method cannot be used.

Instead, we use a detection algorithm that is similar to the Banker’s Algorithm, but it is used for detection, not avoidance.

Data Structures Used

Let:

  • n = number of threads

  • m = number of resource types

The algorithm uses the following time-varying data structures:

Available (Vector of size m)

Available[j] = number of available instances of resource type Rj

Allocation (n × m Matrix)

Allocation[i][j] = number of instances of resource type Rj currently allocated to thread Ti

Request (n × m Matrix)

Request[i][j] = number of additional instances of resource type Rj that thread Ti is requesting

Idea of the Algorithm

The detection algorithm:

Tries to find a possible completion sequence for all threads.

If such a sequence exists → No deadlock

If some threads cannot complete → Deadlock exists

This is similar to the Safety Algorithm in Banker’s Algorithm, but here we check current requests instead of maximum needs.

Deadlock Detection Algorithm

  1. Let Work and Finish be vectors of length m and n, respectively. Initialize
    Work = Available. For i = 0, 1, ..., n − 1, if Allocationᵢ ≠ 0, then Finish[i] = false. Otherwise, Finish[i] = true.

  2. Find an index i such that both
    a. Finish[i] == false
    b. Requestᵢ ≤ Work
    If no such i exists, go to step 4.

  3. Work = Work + Allocationᵢ
    Finish[i] = true
    Go to step 2.

  4. If Finish[i] == false for some i, 0 ≤ i < n, then the system is in a deadlocked state. Moreover, if Finish[i] == false, then thread Tᵢ is deadlocked.

Explanation

Step 1: Initialization

Let:

  • Work = Available

  • Finish[i] =

    • false, if Allocationᵢ ≠ 0

    • true, if Allocationᵢ = 0

This means:

  • Threads holding no resources are not part of a deadlock.

Step 2: Find a Thread That Can Finish

Find an index i such that:

  • Finish[i] == false

  • Requestᵢ ≤ Work

If no such i exists → go to Step 4.

Step 3: Assume Thread i Finishes

Work = Work + Allocationᵢ
Finish[i] = true

Then go back to Step 2.

Step 4: Deadlock Check

If:

Finish[i] == false for some i

Then:

The system is in a deadlocked state.
Those threads with Finish[i] == false are deadlocked.

Time Complexity

The algorithm requires:

O(m×n2)O(m \times n^2)

Where:

  • m = number of resource types

  • n = number of threads

Why Do We Reclaim Resources in Step 3?

When:

Requestᵢ ≤ Work

We assume optimistically that:

  • Thread Ti will complete

  • It will release its resources

  • Those resources can be used by others

If this assumption is wrong, the next execution of the detection algorithm will detect the deadlock.

Example 

Initial State:

System:

  • 5 threads (T0–T4)

  • 3 resource types (A, B, C)

  • Resource type A has seven instances, resource type B has two instances, and resource type C has six instances. The following snapshot represents the current state of the system:

We claim that the system is not in a deadlocked state. Indeed, if we execute our algorithm, we will find that the sequence <T0, T2, T3, T1, T4> results in Finish[i] == true for all i.

Suppose now that thread T2 makes one additional request for an instance of type C. The Request matrix is modified as follows:


We claim that the system is now deadlocked. Although we can reclaim the resources held by thread T0, the number of available resources is not sufficient to fulfill the requests of the other threads. Thus, a deadlock exists, consisting of threads T1, T2, T3, and T4.

Key Difference from Banker’s Algorithm

Banker’s AlgorithmDetection Algorithm
Used for avoidance        Used after deadlock may occur
Uses Need matrix        Uses Request matrix
Ensures safe state        Detects deadlocked threads
Prevents deadlock        Identifies deadlock

Final Summary

When multiple instances exist:

  • Wait-for graph cannot be used.

  • Use matrix-based detection algorithm.

  • Try to simulate completion.

  • If some threads cannot finish → deadlock exists.

  • Time complexity: O(m × n²)

Comments

Post a Comment

Popular posts from this blog

Operating Systems OS PCCST403 Semester 4 BTech KTU CS 2024 Scheme

 About Me Scheme and Syllabus Module-1 Introduction and CPU Scheduling Introduction to OS - 3 important pieces- virtualization, concurrency, persistence Operating System Services Operating System and Kernel Linux Versus Classic Unix Kernels Difference between Linux and Unix Kernels Process and Process Creation- overview Process States in Operating System Data Structures in Operating Systems Key Aspects of a Program and Process in an Operating System-Summary Sharing the Processor Among Processes System Boot Sequence Threads and Concurrency Case Study: Linux Kernel Process management Case Study: Linux Implementation of Threads CPU Scheduling Multi-level feedback Queue ( MLFQ) Scheduler How MLFQ Approximates Shortest Job First (SJF) I/O in MLFQ Problems With the Basic MLFQ Scheduler Solving the Issues with MLFQ Scheduler Case Study: Linux Completely Fair Scheduler (CFS) Module-2 Concurrency and Synchronization Tools Concurrency and Synchronization- Basic principles Critical secti...
Read more

Introduction to Operating System -Virtualization, Concurrency, and Persistence

  How Operating Systems Really Work: Virtualization, Concurrency, and Persistence Have you ever wondered how your laptop can play music, run a web browser, download files, and open a Word document—all at the same time—without melting down? It might look simple, but beneath the surface, your operating system (OS) is doing incredibly sophisticated work. In this , we’ll break down the three most important ideas that make modern operating systems possible: Virtualization Concurrency Persistence These concepts are the foundation of how computers manage programs(applications), memory, and data.  1. Virtualization: Making One Computer Look Like Many Virtualization is all about creating useful illusions . You might have Spotify playing, Instagram open, and a browser loading—all on one phone. It feels like all apps run simultaneously, but the phone is rapidly switching between them so smoothly you don’t notice. Virtualization = making one CPU appear like many. Ev...
Read more

Differences Between Linux and Classic UNIX Kernels

  Differences Between Linux and Classic UNIX Kernels Although Linux and classic UNIX kernels share a common heritage and a similar system-call interface, Linux introduces several important design improvements that distinguish it from traditional UNIX systems. 1. Dynamic Kernel Modules Linux supports dynamic loading and unloading of kernel modules at runtime. Even though Linux is a monolithic kernel , new functionality (such as device drivers) can be added without rebooting. Classic UNIX kernels are mostly static , requiring recompilation and reboot for changes. 2. Symmetric Multiprocessing (SMP) Support Linux has strong SMP support , allowing efficient use of multiple CPUs. Traditional UNIX implementations had limited or no SMP support. Many modern UNIX variants added SMP later, but Linux was designed with scalability in mind. 3. Kernel Preemption The Linux kernel is fully preemptive , meaning a running kernel task can be interrupted to improve r...
Read more