Difficulty: Advanced
How does an OS detect deadlocks with single and multiple resource instances, and what recovery options exist?
If the system neither prevents nor avoids deadlock, it must be able to notice when one has occurred and then repair it. This is the detect-and-recover strategy, used in databases far more than in general-purpose operating systems, because database engines take many locks in unpredictable orders and can roll back transactions cleanly. Think of a city traffic control room: it does not stop gridlock from forming, but it watches the cameras, spots a jam where every road is blocked by another, and sends a tow truck to remove a car.
For resources with a single instance, detection reduces to finding a cycle in a wait-for graph. This is derived from the resource allocation graph by removing the resource nodes: there is an edge from Pi to Pj if Pi is waiting for a resource held by Pj. A cycle in this directed graph means a deadlock, and every process on the cycle is deadlocked. Cycle detection with depth-first search costs O(n squared) in the number of processes, and the system runs it periodically or when a request cannot be granted immediately.
For resources with multiple instances, a cycle is not sufficient, so we use an algorithm similar to Banker's but based on current requests instead of maximum needs. We keep Available, Allocation and Request matrices. Set Work = Available. Mark processes with zero allocation as finished, since they hold nothing that can block others. Then find an unfinished process whose current Request is less than or equal to Work. Assume it finishes and reclaims its allocation, adding it to Work. Repeat. If some processes remain unfinished at the end, they are deadlocked. The optimistic assumption is that a process that can currently proceed will eventually release everything, so we are not predicting the future, just testing whether the present requests can be satisfied.
Now, when do you run detection? Running it on every request gives immediate detection but costs CPU. Running it at fixed intervals or when CPU utilization drops below a threshold, since deadlocked processes leave the CPU idle, is a compromise.
Once deadlock is found, there are two recovery families. Process termination either aborts all deadlocked processes (simple, but wastes all the computation), or aborts them one at a time until the cycle is broken, re-running detection after each abort. Choosing the victim uses criteria like priority, computation time done and remaining, resources held, whether the process is interactive or batch, and how many processes need to be terminated. Resource preemption takes resources away from some processes and gives them to others until the deadlock breaks. This needs three decisions: victim selection (minimize cost), rollback (return the victim to a safe state, ideally a checkpoint, or restart from scratch), and starvation prevention (make sure the same process is not repeatedly chosen as the victim, for example by counting rollbacks in the cost factor).
Databases like PostgreSQL and MySQL InnoDB do exactly this: they maintain a wait-for graph, detect cycles, and abort one transaction, reporting a deadlock error that the application should retry. In an interview, mentioning that transactions make rollback cheap is a great practical link.
To finish, remind the interviewer that detection algorithms have overhead, recovery has a cost, and prevention through lock ordering is usually cheaper if you control the code.
deadlock detection, wait-for graph, recovery, process termination, rollback