Autocoder

Deadlock Interview Questions with Banker's Algorithm Worked Example

Last updated 2026-11-19

Deadlock questions come in two forms: theory (the four conditions, prevention versus avoidance) and a Banker's algorithm numerical where you must find a safe sequence. The second form is mechanical once you know the procedure, and it is easy marks if you keep the Need matrix correct. This page works one full Banker's example, a resource request check, and the formula for the minimum resources that make deadlock impossible.

Deadlock also appears outside the OS course: databases abort transactions that wait on each other, and Java interviews ask you to write a deadlock and fix it. Those are covered here too. For the rest of the subject see operating systems interview questions, and for locking and semaphores see process synchronization.

Core ideaFour conditions must all hold; break one to prevent deadlock
NumericalsBanker's algorithm, request check, minimum resources formula
CodeJava two-lock deadlock and the lock-ordering fix

Banker's algorithm in four lines

Deadlock Interview Questions with Banker's Algorithm Worked Example: questions with worked answers

  1. 1

    What is deadlock? Give a real-life analogy.

    easy

    Deadlock is a state in which a set of processes are each waiting for a resource held by another process in the set, so none can ever proceed. The analogy is four cars arriving at a crossing from four sides, each blocking the car to its right and waiting for the road ahead to clear. In software it is typically two threads, each holding one lock and asking for the other.

  2. 2

    State the four Coffman conditions necessary for deadlock.

    easy

    Mutual exclusion: at least one resource can be used by only one process at a time. Hold and wait: a process holds one resource while requesting another. No preemption: a resource can be released only voluntarily by its holder. Circular wait: there is a cycle P0 waits for P1, P1 waits for P2, and so on back to P0. Deadlock needs all four; the conditions are necessary but not individually sufficient.

  3. 3

    How can each of the four conditions be broken in prevention?

    medium

    Mutual exclusion: make resources sharable (read-only files), though printers cannot be. Hold and wait: require a process to request all resources at once before starting, or release everything before asking again; this lowers utilisation and may cause starvation. No preemption: if a process requesting a resource must wait, take away what it holds. Circular wait: assign every resource type a number and require requests in increasing order. Resource ordering is the most practical approach.

  4. 4

    What is the difference between deadlock prevention and deadlock avoidance?

    medium

    Prevention designs the system so that at least one of the four conditions can never hold, regardless of what processes do. Avoidance allows all four conditions in principle but inspects each request using advance information (maximum needs) and grants it only if the system stays in a safe state, as the Banker's algorithm does. Avoidance gives better utilisation than prevention but needs the maximum claims in advance and has a run-time cost.

  5. 5

    What is a safe state? Is every unsafe state a deadlock?

    medium

    A state is safe if there exists at least one ordering of the processes (a safe sequence) such that each can obtain its remaining maximum need from the available resources plus those released by earlier processes in the order. No deadlock can occur in a safe state. An unsafe state is not necessarily deadlocked, but it may lead to deadlock depending on future requests, so avoidance refuses to enter it.

  6. 6

    Numerical: Find the safe sequence. Resources A, B, C total 10, 5, 7. Allocation / Max for P0..P4 are P0: 010 / 753, P1: 200 / 322, P2: 302 / 902, P3: 211 / 222, P4: 002 / 433.

    medium

    Total allocated: A = 0+2+3+2+0 = 7, B = 1+0+0+1+0 = 2, C = 0+0+2+1+2 = 5, so Available = (10-7, 5-2, 7-5) = (3, 3, 2). Need = Max - Allocation: P0 (7,4,3), P1 (1,2,2), P2 (6,0,0), P3 (0,1,1), P4 (4,3,1). Work = (3,3,2). P0 needs 743 > 332, skip. P1 needs 122 <= 332: run, Work = 332 + 200 = 532. P2 needs 600 > 532, skip. P3 needs 011: run, Work = 532 + 211 = 743. P4 needs 431 <= 743: run, Work = 743 + 002 = 745. P0 needs 743 <= 745: run, Work = 745 + 010 = 755. P2 needs 600: run, Work = 755 + 302 = 1057. All five finish, so the state is safe with sequence P1, P3, P4, P0, P2.

  7. 7

    Numerical: In the state above, process P1 requests (1, 0, 2). Can it be granted?

    hard

    Step 1: Request (1,0,2) <= Need of P1 (1,2,2): yes. Step 2: Request <= Available (3,3,2): yes. Step 3: pretend to grant it. Available becomes (2,3,0), P1's Allocation becomes (3,0,2) and its Need becomes (0,2,0). Run the safety check. P1 needs 020 <= 230: run, Work = 230 + 302 = 532. P3 needs 011: Work = 743. P4 needs 431: Work = 745. P0 needs 743: Work = 755. P2 needs 600: Work = 1057. A safe sequence P1, P3, P4, P0, P2 exists, so the request is granted. If the check had failed, the request would be refused and the old state restored.

  8. 8

    Numerical: A system has R identical units of a resource shared by n processes, each needing at most m units. What is the minimum R that guarantees no deadlock? Evaluate for n = 3, m = 4.

    medium

    The worst case is every process holding m - 1 units and waiting for one more: that uses n(m - 1) units and deadlocks. One extra unit lets at least one process finish and release resources. So R >= n(m - 1) + 1. For n = 3, m = 4: 3 x 3 + 1 = 10 units guarantee no deadlock, while 9 units can deadlock with each process holding 3.

  9. 9

    Explain the resource allocation graph. When does a cycle imply deadlock?

    medium

    Processes are circles, resource types are rectangles with a dot per instance. A request edge goes from process to resource, an assignment edge from resource instance to process. If every resource type has a single instance, a cycle means deadlock. If a type has multiple instances, a cycle is necessary but not sufficient: another process outside the cycle might release a unit. For multiple instances use the matrix-based detection algorithm.

  10. 10

    How is deadlock detected and what are the recovery options?

    medium

    Detection runs periodically: build a wait-for graph (single instances) and search for a cycle, or run a Banker's-style algorithm over Allocation, Request and Available (multiple instances). Recovery options are process termination (abort all deadlocked processes, or abort one at a time choosing a victim by priority, work done and resources held) and resource preemption (roll a process back to a checkpoint and take its resources, taking care to avoid starving the same victim repeatedly).

  11. 11

    What is the Ostrich algorithm?

    medium

    It means ignoring the problem: assume deadlocks are rare and let the user restart the system if one occurs. Unix and Windows take this approach for many kernel resources because prevention and detection are expensive relative to how often deadlock happens. It is acceptable when the cost of occasional manual recovery is lower than the cost of constant checking.

  12. 12

    Differentiate deadlock, starvation and livelock.

    medium

    In deadlock, processes are blocked forever and use no CPU. In starvation, a process is ready but never chosen because others always take precedence, as with a low-priority process under priority scheduling; aging fixes it. In livelock, processes keep running and changing state in response to each other but make no progress, like two people repeatedly stepping aside in the same direction in a corridor. Adding random back-off usually fixes livelock.

  13. 13

    Explain the dining philosophers problem and one deadlock-free solution.

    medium

    Five philosophers sit around a table with five forks, one between each pair, and each needs both adjacent forks to eat. If every philosopher picks up the left fork at the same time, all wait forever for the right one: circular wait. Solutions include allowing at most four philosophers at the table (a semaphore of 4), numbering forks and always picking the lower-numbered one first (resource ordering), or picking up both forks only if both are free inside a critical section.

  14. 14

    Write Java code that deadlocks, then fix it.

    medium

    Two threads take the same two locks in opposite orders. If each gets its first lock before the other gets its second, both block forever. The fix is a global lock order: every thread takes lockA before lockB, which removes the circular wait.

    java
    Object a = new Object(), b = new Object();
    
    // Deadlock-prone: opposite order
    new Thread(() -> { synchronized (a) { sleep(50); synchronized (b) { work(); } } }).start();
    new Thread(() -> { synchronized (b) { sleep(50); synchronized (a) { work(); } } }).start();
    
    // Fixed: both threads lock a first, then b
    new Thread(() -> { synchronized (a) { synchronized (b) { work(); } } }).start();
    new Thread(() -> { synchronized (a) { synchronized (b) { work(); } } }).start();
  15. 15

    How do databases deal with deadlock, and how does it relate to the OS concept?

    hard

    Two transactions that each hold a row lock the other needs form a cycle in the wait-for graph. The database detects it, usually by finding the cycle in that graph at intervals or when a lock wait exceeds a timeout, picks a victim (often the transaction with the least work done), rolls it back and lets the others continue. Applications should retry the victim. Reducing deadlocks means acquiring locks in a consistent order and keeping transactions short. See DBMS interview questions.

  16. 16

    Why is the Banker's algorithm rarely used in real operating systems?

    hard

    It needs each process to declare its maximum resource demand in advance, which general programs cannot do. It assumes a fixed number of processes and resources and that processes eventually release everything, and its cost grows as O(m x n^2) per request check for n processes and m resource types. Real systems prefer lock ordering, timeouts, or simply ignoring the problem.

Frequently asked questions

What is the time complexity of the safety algorithm?

With n processes and m resource types the safety check is O(m x n^2), because up to n passes each scan up to n processes and compare m values.

Can deadlock happen with a single process?

Not in the classic sense, since circular wait needs at least two processes. A single thread can still block forever on a non-reentrant lock it already holds, which is a self-deadlock.

Is a cycle in the resource allocation graph always a deadlock?

Only when every resource has a single instance. With several instances per resource type a cycle only shows a possible deadlock and the detection algorithm must decide.

How do I find a safe sequence if several processes qualify?

Any process whose Need fits in Work can be picked next. Different choices can give different valid sequences, so an exam question normally accepts any correct one, but a safe sequence always exists or does not regardless of the order you try.

Related guides

More in CS Fundamentals Interview Questions

See all in this section