When Should We Invoke the Deadlock Detection Algorithm

 

When Should We Invoke the Deadlock Detection Algorithm?

The timing of running the detection algorithm depends mainly on:

1️⃣ How often deadlocks occur

  • If deadlocks are frequent, detection should run frequently.

  • Otherwise, resources held by deadlocked threads remain idle for a long time.

  • The longer we wait, the more threads may become involved in the deadlock.

2️⃣ How many threads are affected

  • A deadlock may involve only a few threads initially.

  • If not detected early, the waiting chain may grow.

  • More threads → more resource wastage → worse system performance.

Extreme Approach: Run Detection on Every Failed Request

Deadlocks happen when a thread makes a request that cannot be granted immediately.

So in theory, we could:

Run the detection algorithm every time a resource request is denied.

Advantages

  • Detects deadlock immediately.

  • Identifies:

    • the set of deadlocked threads

    • the thread whose request completed the cycle

Reality Check

  • Every thread in the cycle contributes to the deadlock.

  • If there are many resource types, a single request may create multiple cycles.

  • Running detection this often causes high computational overhead.

Practical Approach: Run Detection Periodically

Instead of checking every request, systems often:

  • Run detection at fixed intervals

    • e.g., once per hour

  • Or based on system conditions

    • e.g., when CPU utilization drops below 40%

Why CPU drop?

  • Deadlocks reduce system throughput.

  • Waiting threads don’t use CPU.

  • So CPU usage falls — a sign something is wrong.

Problem with Periodic Detection

If detection runs only occasionally:

  • The resource graph may already contain many cycles

  • It becomes hard to determine:

    • which thread originally caused the deadlock

Real-World Example: Database Systems

Databases frequently face deadlocks because:

  • Transactions require multiple locks

  • Many transactions run concurrently

Most database systems include:

✔ Deadlock detection
✔ Deadlock recovery

They typically:

  1. Periodically search for cycles in the wait-for graph

  2. If deadlock is found:

    • Select a victim transaction

    • Abort and roll it back

    • Release its locks

  3. Resume other transactions

  4. Restart the aborted transaction later

For example, MySQL often chooses the victim transaction that minimizes the number of affected rows (insert/update/delete).

Simple Summary

  • Detection frequency depends on:

    • likelihood of deadlock

    • number of affected threads

  • Options:

    • Every failed request → accurate but expensive

    • Periodic checks → cheaper but less precise

  • Real systems (like databases) use periodic detection + rollback recovery.

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