Top 28 OS Deadlock Interview Questions & Answers (2026)

Last Updated: June 2026 | Level: Beginner to Advanced | Format: Q&A with Resource Graphs and Algorithm Walkthroughs

Deadlock is one of the most consistently tested OS topics at product companies (Google, Microsoft, Amazon) and service companies (TCS, Infosys, Wipro). Candidates report that questions range from "name the four conditions" to full Banker's Algorithm walkthroughs and system design scenarios. Based on public preparation resources and candidate-reported interview threads, the Banker's Algorithm calculation appears in written rounds at TCS NQT and Infosys InfyTQ regularly. This guide covers 28 deadlock questions with diagrams described in text, algorithm traces, and comparison tables.

---

Table of Contents

1. Deadlock Fundamentals (Q1-Q8)
2. Prevention and Avoidance (Q9-Q16)
3. Detection and Recovery (Q17-Q22)
4. Advanced and Design (Q23-Q28)

---

Deadlock Fundamentals

Q1. What is a deadlock? Give a real-world analogy. Easy

A deadlock is a situation where two or more processes are permanently blocked, each waiting for a resource held by another process in the same set. No process can proceed.

Real-world analogy: Two single-lane roads merge at a narrow bridge. Car A enters from the left, Car B enters from the right. Neither can reverse (no preemption). Both hold their lane and wait for the other. Neither moves. This is a deadlock.

CS example:

Process P1 holds Resource R1, needs R2.
Process P2 holds Resource R2, needs R1.

P1 waits for P2 to release R2.
P2 waits for P1 to release R1.
Neither ever releases. Both are blocked forever.

---

Q2. What are the four necessary conditions for deadlock? Easy

All four conditions must hold simultaneously for deadlock to occur. These are Coffman conditions (1971).

Condition	Description	Example
Mutual Exclusion	At least one resource must be non-shareable; only one process can use it at a time	A printer: only one process can print at a time
Hold and Wait	A process holds at least one resource and waits to acquire more	P1 holds mutex_A, waits for mutex_B
No Preemption	Resources cannot be forcibly taken from a process; only voluntary release	OS cannot snatch the printer mid-job
Circular Wait	There exists a circular chain of processes P1->P2->...->Pn->P1, each waiting for a resource held by the next	P1 waits for P2, P2 waits for P3, P3 waits for P1

Interview trick: If any one condition is broken, deadlock cannot occur.

---

Q3. What is a Resource Allocation Graph (RAG)? How do you detect deadlock from it? Medium

A Resource Allocation Graph visually represents processes and resources:

• Circle = Process (P1, P2, ...)
• Rectangle = Resource type (R1, R2, ...)
• Dot inside rectangle = Instance of the resource
• Request edge (P -> R): Process P requests resource R
• Assignment edge (R -> P): Resource R is assigned to process P

Deadlock detection rules:

Resource instances	Deadlock condition
Single instance per resource	Deadlock if and only if the RAG contains a cycle
Multiple instances per resource	Cycle is necessary but not sufficient; must run detection algorithm

RAG with cycle - single instance (deadlock):

P1 --> R1 --> P2 --> R2 --> P1
(P1 waits for R1 held by P2; P2 waits for R2 held by P1 -- cycle = deadlock)

RAG with cycle - multiple instances (NOT necessarily deadlock):

R1 has 2 instances.
P1 holds one instance of R1, requests R2.
P2 holds R2, requests R1.
P3 holds one instance of R1 (not in cycle).

Cycle exists: P1->R2->P2->R1->P1
But P3 will eventually release R1, allowing P2 to proceed.
Not a deadlock.

---

Q4. What is the difference between deadlock, starvation, and livelock? Medium

Condition	Processes blocked?	Progress?	Cause
Deadlock	Yes, permanently	None	Circular resource dependency
Starvation	One process indefinitely delayed	Others make progress	Priority or fairness failure
Livelock	No (processes run)	None	Processes keep changing state in response to each other, never completing

Livelock example: Two people meet in a corridor, both step aside in the same direction simultaneously. Each moves repeatedly but never passes. They are active but making no progress.

CS livelock example:

# Thread T1                    # Thread T2
while True:                    while True:
    if trylock(R1):                if trylock(R2):
        if trylock(R2):                if trylock(R1):
            work(); break                  work(); break
        else:                      else:
            release(R1)                release(R2)
            sleep(random)              sleep(random)

Both threads keep acquiring one lock, failing to get the second, releasing, and retrying. They move but never progress.

---

Q5. How does deadlock differ from a race condition? Medium

Aspect	Deadlock	Race Condition
Nature	Synchronization problem (too much locking)	Synchronization problem (too little locking)
Symptom	Processes blocked forever	Non-deterministic, wrong output
Root cause	Circular resource hold-and-wait	Unsynchronized access to shared data
Fix	Break one Coffman condition	Add proper synchronization (mutex, semaphore)

A system can have both simultaneously: improper locking causing race conditions, and over-locking causing deadlock.

---

Q6. What are the strategies for handling deadlock? Easy

Four strategies exist:

Strategy	Approach	When used
Prevention	Eliminate one of four Coffman conditions structurally	System design time
Avoidance	Dynamically track resource state; never enter unsafe state	Runtime, with advance knowledge of max resource needs
Detection + Recovery	Allow deadlocks; detect them; break them	When deadlocks are rare and cost of prevention is high
Ignore (Ostrich Algorithm)	Pretend deadlocks don't happen	When deadlocks are very rare and cost of handling exceeds benefit

Real-world: Most general-purpose OSes (Linux, Windows) use the ostrich approach for deadlocks between user processes. Databases (MySQL, PostgreSQL) use detection + recovery (deadlock detection + transaction rollback).

---

Q7. What is a safe state and unsafe state? Medium

A safe state is a system state in which there exists at least one safe sequence of process execution such that every process can eventually obtain all the resources it needs, complete, and release resources for the next process.

A unsafe state does not guarantee a safe sequence exists and may lead to deadlock, but is not itself a deadlock.

Safe:    All processes can complete in SOME order.
Unsafe:  No such order guarantees all can complete.
Deadlock: At least one process is blocked and cannot make progress.

Relationship:
Safe -> No deadlock guaranteed
Unsafe -> Deadlock POSSIBLE (not certain)
Deadlock -> Definitely unsafe

Avoidance goal: Keep the system always in a safe state. Refuse any resource request that would move the system to an unsafe state.

---

Q8. What is circular wait? How does it differ from a simple cycle in a RAG? Medium

Circular wait is one of the four Coffman conditions. It means: there exists a set of processes {P1, P2, ..., Pn} such that P1 is waiting for a resource held by P2, P2 is waiting for a resource held by P3, ..., and Pn is waiting for a resource held by P1.

In a single-instance RAG: Circular wait is equivalent to a cycle in the graph. If a cycle exists, deadlock exists.

In a multi-instance RAG: A cycle in the graph is necessary for deadlock (no cycle = no deadlock), but not sufficient (cycle may exist without deadlock if instances are available from non-cycle processes). Must run the full detection algorithm to confirm.

---

Prevention and Avoidance

Q9. How does deadlock prevention work? Explain each condition's prevention. Medium

Mutual Exclusion: Make resources shareable where possible. Read-only files can be shared. Printers cannot (inherently exclusive). This condition cannot always be eliminated.

Hold and Wait - two approaches:

1. Require all-at-once: Process must request ALL resources it will ever need before starting. Low resource utilization (holds resources it won't need for hours).
2. Release before requesting: Process must release all held resources before requesting new ones. Risk: must restart if it cannot get all new resources.

No Preemption: Allow the OS to preempt resources from waiting processes:

• If P1 holds R1 and requests R2, and R2 is unavailable, release R1 from P1.
• Works for resources whose state can be saved/restored (CPU registers, memory pages).
• Does NOT work for printers or tape drives (job state is lost).

Circular Wait - resource ordering: Impose a global ordering on all resource types. Processes must always request resources in increasing order number.

R1 < R2 < R3 (ordering)
Process must acquire R1 before R2, R2 before R3.
If P1 holds R2 and wants R1, it must release R2 first.
This eliminates circular chains.

Most practical prevention: Resource ordering (eliminates circular wait) is the most commonly used approach in practice (e.g., lock ordering conventions in kernel code).

---

Q10. Explain the Banker's Algorithm for deadlock avoidance. Hard

The Banker's Algorithm (Dijkstra, 1965) is named after a bank that only lends money if it can still satisfy all other customers' maximum loan requests.

Data structures:

n = number of processes, m = number of resource types

Available[m]      : available instances of each resource type
Max[n][m]         : maximum demand of each process for each resource
Allocation[n][m]  : currently allocated to each process
Need[n][m]        : remaining need = Max - Allocation

Safety Algorithm (determines if current state is safe):

1. Work = Available (copy)
   Finish[i] = false for all i

2. Find process i where:
   - Finish[i] == false
   - Need[i] <= Work (all resource types)

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

4. If Finish[i] == true for all i: SAFE STATE
   Otherwise: UNSAFE STATE

Resource Request Algorithm (for process Pi requesting Request[m]):

1. If Request[i] > Need[i]: error (exceeded declared max)
2. If Request[i] > Available: wait (resources unavailable)
3. Pretend to allocate:
   Available -= Request[i]
   Allocation[i] += Request[i]
   Need[i] -= Request[i]
4. Run Safety Algorithm on new state
5. If SAFE: commit allocation
   If UNSAFE: rollback (restore old values), Pi must wait

---

Q11. Work through a complete Banker's Algorithm example. Hard

5 processes (P0-P4), 3 resource types (A, B, C)

Available = [3, 3, 2]

         Allocation    Max        Need (Max-Allocation)
         A  B  C      A  B  C    A  B  C
P0       0  1  0      7  5  3    7  4  3
P1       2  0  0      3  2  2    1  2  2
P2       3  0  2      9  0  2    6  0  0
P3       2  1  1      2  2  2    0  1  1
P4       0  0  2      4  3  3    4  3  1

Safety check:
Work = [3,3,2]

Round 1: Find Need[i] <= Work
  P0: Need=[7,4,3] > Work=[3,3,2]? Yes, skip.
  P1: Need=[1,2,2] <= Work=[3,3,2]? Yes. Finish P1.
      Work = [3,3,2] + [2,0,0] = [5,3,2]
  
Round 2: Work = [5,3,2]
  P3: Need=[0,1,1] <= [5,3,2]? Yes. Finish P3.
      Work = [5,3,2] + [2,1,1] = [7,4,3]

Round 3: Work = [7,4,3]
  P0: Need=[7,4,3] <= [7,4,3]? Yes. Finish P0.
      Work = [7,4,3] + [0,1,0] = [7,5,3]
  P2: Need=[6,0,0] <= [7,5,3]? Yes. Finish P2.
      Work = [7,5,3] + [3,0,2] = [10,5,5]
  P4: Need=[4,3,1] <= [10,5,5]? Yes. Finish P4.

Safe sequence: P1 -> P3 -> P0 -> P2 -> P4

Request from P1: [1,0,2]
  Check: [1,0,2] <= Need[1]=[1,2,2] YES
  Check: [1,0,2] <= Available=[3,3,2] YES
  Pretend: Available=[2,3,0], Allocation[1]=[3,0,2], Need[1]=[0,2,0]
  Run safety: find safe sequence -> YES (safe)
  Grant request.

---

Q12. What is the difference between deadlock prevention and deadlock avoidance? Easy

Aspect	Prevention	Avoidance
When	System design time (structural rules)	Runtime (per-request decision)
Information needed	None beyond policy	Max resource needs of each process
Method	Eliminate one Coffman condition	Keep system in safe state
Overhead	Low (policy enforced, no runtime check)	High (Safety Algorithm O(n^2 * m) per request)
Utilization	Lower (conservative allocation)	Higher than prevention, but still conservative
Examples	Lock ordering, request-all-at-once	Banker's Algorithm

Prevention = structural rules that make deadlock impossible. Avoidance = runtime intelligence that steers around deadlock.

---

Q13. Why is the Banker's Algorithm impractical for general-purpose OSes? Medium

The Banker's Algorithm requires:

1. Known maximum resource needs in advance. In a general-purpose OS, a process cannot predict how many files it will open, how much memory it will allocate, or which devices it will use.
2. Fixed number of processes and resources. Dynamic process creation/deletion and hotplugging hardware violate this.
3. Single resource unit granularity. Real systems have thousands of resource types (file descriptors, socket handles, memory pages) making the algorithm too expensive.
4. O(n^2 * m) per request. With thousands of processes and resource types, each request triggers a costly check.

Where it IS used: Specialized embedded systems with fixed process sets and known resource profiles. Also conceptually in database transaction managers (optimistic vs. pessimistic locking).

---

Q14. How does lock ordering prevent deadlock? Show an example. Medium

Lock ordering is a deadlock prevention technique: all threads must acquire locks in a globally agreed order.

Without ordering (deadlock possible):

// Thread T1
pthread_mutex_lock(&A);
pthread_mutex_lock(&B);
work();

// Thread T2
pthread_mutex_lock(&B);   // Opposite order!
pthread_mutex_lock(&A);
work();

If T1 acquires A and T2 acquires B simultaneously, both block. Deadlock.

With ordering (lock A before B, always):

// Thread T1
pthread_mutex_lock(&A);
pthread_mutex_lock(&B);
work();

// Thread T2
pthread_mutex_lock(&A);   // Same order
pthread_mutex_lock(&B);
work();

Now if T1 holds A, T2 cannot proceed past the first lock. T1 finishes and releases both. No deadlock.

Challenge: Lock ordering becomes complex in large codebases. Static analysis tools (like Linux's lockdep) verify lock ordering at runtime.

---

Q15. What is the Wait-For Graph and when is it used? Medium

A Wait-For Graph (WFG) is a simplified version of the Resource Allocation Graph used when each resource has exactly one instance.

Construction: Remove resource nodes from the RAG. If process Pi is waiting for a resource held by Pj, draw a direct edge Pi -> Pj.

Deadlock detection: Invoke a cycle-detection algorithm on the WFG. A cycle means deadlock.

Example:

RAG:  P1->R1->P2->R2->P1
WFG:  P1->P2->P1  (cycle -- deadlock confirmed)

RAG:  P1->R1->P2, P3->R1 (P3 also requests R1, held by P2)
WFG:  P1->P2, P3->P2 (no cycle -- no deadlock, P3 and P1 both wait for P2)

Overhead: WFG cycle detection can be O(n + e) with DFS. Run periodically or triggered when CPU utilization drops unexpectedly (a heuristic that a deadlock may have occurred).

---

Q16. How does avoiding hold-and-wait reduce deadlock? What is the cost? Easy

Approach 1: Request all resources at start. Process declares ALL needed resources before beginning. OS grants all or none (atomic allocation).

• Eliminates Hold and Wait.
• Cost: Low resource utilization (process holds resources it won't need for hours). Poor for long-running processes with evolving needs.

Approach 2: Release before requesting. Process must release ALL currently held resources before requesting new ones.

• Also eliminates Hold and Wait.
• Cost: Process may have to restart its work (e.g., release partially-processed data, re-read from scratch). Risk of starvation if popular resources are never all available simultaneously.

In practice: Databases implement Approach 2 implicitly: a transaction that cannot acquire a lock in 2-phase locking is aborted and restarted. The rollback is the "release all" step.

---

Detection and Recovery

Q17. Explain the deadlock detection algorithm for multiple resource instances. Hard

Similar to the Banker's Safety Algorithm but without the Need matrix (since we are not checking future safety, just current state).

Data structures:

Available[m]      : currently available instances
Allocation[n][m]  : currently allocated
Request[n][m]     : current outstanding requests

Algorithm:

1. Work = Available
   Finish[i] = (Allocation[i] == 0) ? true : false
   (Processes with no allocation cannot be in deadlock)

2. Find process i where:
   - Finish[i] == false
   - Request[i] <= Work

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

4. Any process where Finish[i] == false is deadlocked.

Example:

Available = [0,0,0]
         Allocation    Request
         A  B  C       A  B  C
P0       0  1  0       0  0  0
P1       2  0  0       2  0  2
P2       3  0  3       0  0  0
P3       0  1  0       1  0  0
P4       0  0  2       0  0  2

Finish initially: P0=true (no alloc? No, has 0,1,0 -> false), P2=true? No (3,0,3)
Actually: Finish[i] = (Allocation[i] all zero). P0 Alloc=(0,1,0) -> not all zero -> Finish=false.

Work=[0,0,0]
Find Request[i] <= Work=[0,0,0]:
  P0: Request=[0,0,0] <= [0,0,0] YES. Work=[0,1,0]. Finish[0]=true.
  P2: Request=[0,0,0] <= [0,1,0] YES. Work=[3,1,3]. Finish[2]=true.
  P3: Request=[1,0,0] <= [3,1,3] YES. Work=[3,2,3]. Finish[3]=true.
  P1: Request=[2,0,2] <= [3,2,3] YES. Work=[5,2,3]. Finish[1]=true.
  P4: Request=[0,0,2] <= [5,2,3] YES. Finish[4]=true.

All Finish=true. No deadlock.

---

Q18. How often should deadlock detection run? Medium

Trade-off: Detection has O(n^2 * m) cost. Running it on every resource request is expensive. Running it rarely means deadlock persists longer.

Strategies:

Frequency	Pros	Cons
Every resource request	Immediate detection	High overhead
Periodic (every 1 hour)	Low overhead	Deadlock persists longer; hard to identify which request caused it
On CPU utilization drop	Heuristic: deadlock often causes idle CPUs	May false-trigger; may also miss deadlock
On explicit trigger	Admin/application-controlled	Requires app cooperation

Common practice: Most databases run detection every few seconds and recover via transaction rollback. General-purpose OS kernels rarely run detection; they rely on application-level timeouts and retry logic.

---

Q19. What are the deadlock recovery techniques? Medium

Two broad approaches:

1. Process Termination

Sub-approach	Description	Cost
Abort all deadlocked processes	Guaranteed to break deadlock	Highest: all work lost
Abort one at a time	Kill cheapest process, re-run detection	Lower cost; may require multiple kills

Selection criteria for which process to kill:

• Process priority (kill lowest)
• Time consumed so far (kill shortest-lived, less work lost)
• Resources held (kill process holding most contested resources)
• Interactive vs. batch (prefer to kill batch)

2. Resource Preemption

Forcibly take a resource from a process and give it to another.

Three sub-problems:

1. Selecting victim: Which process loses its resource? (Minimize cost.)
2. Rollback: Return the preempted process to a safe prior state (checkpoint-based).
3. Starvation prevention: Avoid always preempting the same process. Include number of rollbacks in cost calculation.

Works for: Resources with checkpointable state (memory pages, partially computed values with saves). Does not work for: Printers mid-job, network connections.

---

Q20. What is the Ostrich Algorithm? When is it acceptable? Easy

The Ostrich Algorithm is the strategy of ignoring deadlocks entirely (head in the sand). When a deadlock occurs, the user or administrator manually kills processes or reboots.

Justification:

• Prevention/avoidance reduce system efficiency and throughput.
• Deadlocks in general-purpose systems are rare (probabilistically unlikely for typical workloads).
• Cost of handling deadlock (complex OS code, reduced utilization) exceeds cost of occasional manual intervention.

Used by: Linux, Windows, macOS for user-process deadlocks. These OSes do NOT run system-wide deadlock detection.

Not acceptable for: Safety-critical systems (avionics, medical devices), databases (where deadlock between transactions must be handled automatically).

---

Q21. How does MySQL/PostgreSQL handle deadlocks? Medium

MySQL (InnoDB): Runs deadlock detection after every lock wait. Uses a wait-for graph. When a cycle is detected, it kills the transaction with the lowest "weight" (fewest locks held, smallest undo log). The killed transaction gets an error and is rolled back. The surviving transaction proceeds.

-- Session 1:
BEGIN;
UPDATE accounts SET balance = balance - 100 WHERE id = 1;  -- locks row 1
UPDATE accounts SET balance = balance + 100 WHERE id = 2;  -- waits for row 2

-- Session 2 (concurrent):
BEGIN;
UPDATE accounts SET balance = balance - 50 WHERE id = 2;   -- locks row 2
UPDATE accounts SET balance = balance + 50 WHERE id = 1;   -- waits for row 1 -> DEADLOCK

InnoDB detects cycle, rolls back Session 2:
ERROR 1213 (40001): Deadlock found when trying to get lock; try restarting transaction

PostgreSQL: Similar wait-for graph detection. deadlock_timeout (default: 1 second) sets how long a lock wait runs before deadlock detection is triggered.

Best practice: Applications must catch deadlock errors and retry the transaction.

---

Q22. How can developers avoid deadlocks in application code? Medium

1. Lock ordering: Always acquire multiple locks in a consistent global order. Document the ordering.

2. Lock timeouts: Use timed lock attempts instead of blocking indefinitely.

if (lockA.tryLock(100, TimeUnit.MILLISECONDS)) {
    try {
        if (lockB.tryLock(100, TimeUnit.MILLISECONDS)) {
            // critical section
        }
    } finally {
        lockA.unlock();
    }
}

3. Single global lock: For simple cases, replace multiple fine-grained locks with one coarse-grained lock (lower concurrency but eliminates multi-lock deadlock).

4. Lock-free data structures: Use atomic operations (compare-and-swap) where possible. Java's java.util.concurrent.atomic, C++ std::atomic.

5. Try-lock with backoff: On failure, release all locks, wait random time (exponential backoff), retry. Prevents livelock.

6. Deadlock-free design patterns: Producer-consumer with bounded queues eliminates complex lock interactions. Message passing (actors) avoids shared mutable state.

---

Advanced and Design

Q23. What is the difference between resource deadlock and communication deadlock? Hard

Type	Resources involved	Example
Resource deadlock	Physical resources (locks, files, memory)	P1 holds mutex A waits for B; P2 holds B waits for A
Communication deadlock	Message buffers / network buffers	P1 waits for a message from P2; P2 waits for a message from P1 before sending

Communication deadlock example in distributed systems:

Process A: send(B, "request") then wait receive(B, "ack")
Process B: send(A, "request") then wait receive(A, "ack")

If both send buffers are full (or the sends are synchronous),
A waits for B to receive; B waits for A to receive.
Neither receives. Deadlock.

Solution: Non-blocking sends (async message passing) or using timeouts with retry logic in distributed protocols.

---

Q24. How do distributed systems handle deadlocks differently from single-machine systems? Hard

Distributed deadlock is harder because:

• No global state is visible to any single node.
• Network delays make RAG construction expensive and unreliable.
• Node failures look like deadlocks (process appears to be waiting forever).

Approaches:

Approach	Description
Global deadlock detection	A coordinator collects local wait-for graphs from all nodes, merges them, and detects cycles. Expensive; requires all nodes to be up.
Distributed detection (probe-based)	A blocked process sends a probe message along wait-for edges. If the probe returns to its origin, deadlock is detected. (Chandy-Misra-Haas algorithm)
Timeout-based recovery	Process waits for at most T seconds. If no response, assume deadlock (or failure), abort and retry. Simple but may abort non-deadlocked transactions during slow nodes.
Avoidance via 2PC	Two-Phase Commit coordinator can detect and abort participants that are causing global deadlock.

Most practical distributed approach: Timeout + retry, with exponential backoff. Used in Google Spanner, Cassandra, and most distributed databases.

---

Q25. What is a spinlock and can it cause deadlock? Hard

A spinlock is a lock where the waiting process busy-waits (spins in a loop) instead of blocking/sleeping.

// Spinlock in pseudo-code
while (test_and_set(&lock) == 1) { /* spin */ }
// critical section
lock = 0;

Can spinlocks cause deadlock? Yes, in these scenarios:

1. Preemption deadlock: On a single-CPU system, if a thread holding a spinlock is preempted, the thread waiting for the spinlock spins forever (the lock holder cannot run to release it). Solution: disable preemption while holding a spinlock (done in Linux kernel).

2. Classic circular wait: Thread T1 holds spinlock A, spins on B. Thread T2 holds B, spins on A. Both spin forever. Same four conditions apply.

3. Priority inversion with spinlocks: High-priority thread spins waiting for a spinlock held by a low-priority thread that the scheduler won't run.

Appropriate use: Short critical sections on multi-CPU systems where the expected wait time is less than the cost of a context switch. Never hold a spinlock across I/O or long computations.

---

Q26. How does the Linux kernel avoid deadlock internally? Hard

The Linux kernel uses several strategies to avoid deadlock in its own code:

1. Lock ordering + lockdep:

• The kernel uses a global lock-ordering validator called lockdep (CONFIG_PROVE_LOCKING).
• lockdep tracks every lock acquisition sequence at runtime.
• If a new acquisition violates the established ordering, it prints a warning immediately (even if a deadlock hasn't occurred yet).
• This catches potential deadlocks in testing before they appear in production.

2. Spinlock rules:

• Spinlocks must be held for short durations.
• Preemption is disabled while holding a spinlock.
• IRQ handlers cannot be interrupted by other IRQ handlers that would try to acquire the same lock (use spin_lock_irqsave).

3. Mutex design:

• Mutexes (sleeping locks) cannot be held in interrupt context.
• If a mutex is needed in interrupt context, a spinlock must be used instead.

4. RCU (Read-Copy-Update):

• A lock-free synchronization mechanism for read-heavy data structures.
• Readers never block. Writers create a new copy, update it, then atomically swap. Old copies are reclaimed after all readers leave the critical section.
• Eliminates read-side locking entirely for many kernel data structures (routing tables, file system path cache).

---

Q27. Design a thread-safe stack that avoids deadlock. Hard

import java.util.concurrent.locks.ReentrantLock;
import java.util.Stack;

public class DeadlockFreeStack<T> {
    private final Stack<T> stack = new Stack<>();
    private final ReentrantLock lock = new ReentrantLock();
    // Single lock: no multi-lock acquisition, no deadlock possible.

    public void push(T item) {
        lock.lock();
        try {
            stack.push(item);
        } finally {
            lock.unlock();  // Always release in finally block
        }
    }

    public T pop() throws Exception {
        lock.lock();
        try {
            if (stack.isEmpty()) throw new Exception("Stack is empty");
            return stack.pop();
        } finally {
            lock.unlock();
        }
    }

    public T peek() throws Exception {
        lock.lock();
        try {
            if (stack.isEmpty()) throw new Exception("Stack is empty");
            return stack.peek();
        } finally {
            lock.unlock();
        }
    }
}

Design decisions that prevent deadlock:

1. Single lock eliminates circular wait (no two locks to acquire).
2. try/finally ensures lock is ALWAYS released even on exception (prevents permanent lock hold).
3. ReentrantLock is reentrant: same thread can call push() inside a lock without deadlocking itself.
4. No callbacks or external methods are called while holding the lock (avoids alien calls that could acquire other locks).

---

Q28. What interview questions on deadlock appear at top product companies? Medium

Conceptual (any SDE-1 interview):

• Name and explain the four Coffman conditions.
• What is the difference between deadlock prevention and avoidance?
• Can Round Robin scheduling cause deadlock?

Computational (written test / coding rounds):

• Given a RAG, identify if deadlock exists.
• Given allocation/max/available tables, run Banker's Algorithm and find safe sequence.
• Calculate whether a resource request is safe using Banker's Resource Request Algorithm.

Code-based (SDE-2 or senior):

• Write a thread-safe class that avoids deadlock.
• Find the bug in a multithreaded code snippet (lock ordering violation).

Design-based (system design or senior SDE):

• How does your database handle deadlocks? Design the detection mechanism.
• How would you detect deadlock in a distributed microservices system?

PapersAdda tip: Practice computing Banker's Algorithm on paper until you can do it in under 5 minutes. It appears in written rounds at Infosys, TCS, Wipro, and Accenture regularly.

---

FAQ

Q: Can deadlock occur with a single process? No. Deadlock requires at least two processes in a circular wait. A single process can self-deadlock (try to acquire a non-reentrant lock it already holds), which is a related but distinct problem.

Q: Is deadlock detection expensive? The basic single-instance detection (cycle in WFG) is O(n + e). Multi-instance detection runs in O(n^2 * m). For large systems, it is expensive to run on every operation; most systems run it periodically.

Q: What is the real-time risk of deadlock in production? In well-written server software, deadlock is rare but catastrophic when it occurs (service hangs, requires restart). Most production systems detect it via health-check timeouts and restart the affected service rather than implement OS-level detection.

---

Related PapersAdda guides:

• OS Interview Questions 2026
• OS Process Scheduling Questions 2026
• OS Threads and Concurrency Questions 2026
• OS Memory Management Questions 2026
• DBMS ACID Transactions Questions 2026