deadlock detection
Instead of preventing accidents by banning fast driving (prevention) or vetting every trip in advance (avoidance), some systems take the relaxed view: let cars drive freely, but keep a tow truck and periodically check whether anyone has crashed and frozen traffic. Deadlock detection is that approach — the OS allows deadlocks to happen, then runs an algorithm now and then to discover whether a set of processes has actually become deadlocked, so it can be cleaned up.
How does it find a deadlock? In the single-instance case the OS builds a WAIT-FOR GRAPH (processes as nodes, an edge from Pi to Pj meaning Pi is waiting for a resource Pj holds) and looks for a CYCLE; a cycle is a deadlock. With multiple instances, a cycle is not enough, so a more careful algorithm is used — essentially the banker's safety check run on the CURRENT state with no MAX needed: mark a process 'finishable' if its outstanding request can be met from currently available instances, pretend it finishes and releases, and repeat; any process that can never be marked finishable is part of a deadlock. The OS chooses how OFTEN to run this: every request (expensive, finds deadlocks instantly) or periodically / only when CPU utilization drops and many processes are blocked (cheaper, but a deadlock may sit undetected for a while).
Detection pairs with recovery — finding the deadlock is useless unless you then break it by killing or rolling back processes. The honest trade-off is timing and cost. Running detection constantly is precise but burns CPU; running it rarely is cheap but lets deadlocked processes (and the resources they freeze) sit idle longer, and makes recovery harder because more work may be lost. Detection makes sense when deadlocks are rare enough that paying the prevention/avoidance overhead all the time would be wasteful, but common enough that ignoring them entirely is unacceptable.
Single-instance detection: build the wait-for graph and search for a cycle. If P1 -> P2 -> P3 -> P1 appears, those three are deadlocked. Multiple-instance detection: repeatedly mark any process whose request fits in AVAILABLE as finished and reclaim its resources; whatever stays unmarked is deadlocked.
Single-instance detection looks for a cycle; multiple-instance detection runs a finish-and-reclaim sweep.
Detection only finds deadlocks; it does nothing without a recovery step. Running it often is precise but costly; running it rarely is cheap but lets deadlocks linger and waste resources.