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 idea | Four conditions must all hold; break one to prevent deadlock |
|---|---|
| Numericals | Banker's algorithm, request check, minimum resources formula |
| Code | Java two-lock deadlock and the lock-ordering fix |
Banker's algorithm in four lines
- Need = Max - Allocation, computed for every process and every resource type.
- Work = Available. Find an unfinished process whose Need is less than or equal to Work in every column.
- Pretend it runs to completion: Work = Work + its Allocation, and mark it finished.
- If every process can be marked, the state is safe and the order you found is a safe sequence. If you get stuck, the state is unsafe.
Deadlock Interview Questions with Banker's Algorithm Worked Example: questions with worked answers
1 What is deadlock? Give a real-life analogy.
easyDeadlock 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 State the four Coffman conditions necessary for deadlock.
easyMutual 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 How can each of the four conditions be broken in prevention?
mediumMutual 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 What is the difference between deadlock prevention and deadlock avoidance?
mediumPrevention 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 What is a safe state? Is every unsafe state a deadlock?
mediumA 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 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.
mediumTotal 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 Numerical: In the state above, process P1 requests (1, 0, 2). Can it be granted?
hardStep 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 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.
mediumThe 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 Explain the resource allocation graph. When does a cycle imply deadlock?
mediumProcesses 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 How is deadlock detected and what are the recovery options?
mediumDetection 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 What is the Ostrich algorithm?
mediumIt 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 Differentiate deadlock, starvation and livelock.
mediumIn 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 Explain the dining philosophers problem and one deadlock-free solution.
mediumFive 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 Write Java code that deadlocks, then fix it.
mediumTwo 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.
javaObject 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 How do databases deal with deadlock, and how does it relate to the OS concept?
hardTwo 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 Why is the Banker's algorithm rarely used in real operating systems?
hardIt 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
- Operating Systems Interview Questions with Worked Answers
- Process Synchronization Interview Questions: Semaphores, Mutex and Classic Problems
- CPU Scheduling Interview Questions with Gantt Chart Numericals
- Process and Thread Interview Questions with fork() Output Problems
- Memory Management Interview Questions with Numericals
- DBMS Interview Questions and Answers
More in CS Fundamentals Interview Questions
- Design Patterns Interview Questions with Code
- Distributed Systems Interview Questions
- DNS Interview Questions: Resolution, Record Types, Caching and Troubleshooting
- ER Model Interview Questions
- File System Interview Questions: Inodes, Allocation and Disk Scheduling
- Git Interview Questions and Answers with Commands
- HTTP and HTTPS Interview Questions: Methods, Status Codes, TLS and Caching
- Inheritance and Polymorphism Interview Questions
- IP Addressing and Subnetting Interview Questions with Worked Solutions
- Linux Commands Interview Questions with Examples
- Linux Interview Questions and Answers: Concepts, Permissions and Processes
- Load Balancing Interview Questions and Answers