What is the difference between deadlock prevention and deadlock avoidance, and how does the banker's algorithm decide whether to grant a resource request?

## Three strategies, not two The classic taxonomy has four responses to deadlock: - **Prevention** - design so one of the four necessary conditions can never hold. - **Avoidance** - allow the conditions, but use advance knowledge of future requests to refuse grants that could lead to trouble. - **Detection and recovery** - let it happen, find it, break it by aborting a victim. - **Ignore it** - accept the risk and restart when it bites (the "ostrich" approach, which most general-purpose operating systems take for user-level locks). Prevention and avoidance are frequently confused in interviews, and the distinction is exactly *when* the decision is made. Prevention decides at design time and needs no runtime state: a lock order either exists in the code or it does not. Avoidance decides at request time and needs runtime accounting plus a declaration of future intent. ## The state model behind the banker's algorithm The algorithm treats the system like a bank lending identical units of several currencies: - **Available[j]** - free instances of resource type j. - **Max[i][j]** - the most of type j that participant i will *ever* need at once, declared before it starts. - **Allocation[i][j]** - what i currently holds. - **Need[i][j] = Max[i][j] - Allocation[i][j]** - what i may still ask for. A state is **safe** if there exists an ordering of all participants - a *safe sequence* - such that each in turn can have its entire remaining need satisfied from what is currently available plus everything released by those before it. If such a sequence exists, the system can always drive every participant to completion, so deadlock is impossible from that state. ## The two procedures **Safety check.** Start with `work = Available` and everyone unfinished. Repeatedly look for an unfinished participant whose `Need` is componentwise less than or equal to `work`; pretend it runs to completion and add its `Allocation` back into `work`; mark it finished. If every participant can be finished this way, the state is safe; if you get stuck with unfinished participants, it is unsafe. **Request handling.** When participant i requests a vector R: 1. If R exceeds `Need[i]`, it broke its declared maximum - an error. 2. If R exceeds `Available`, i simply waits for resources. 3. Otherwise tentatively apply the grant (`Available -= R`, `Allocation[i] += R`, `Need[i] -= R`) and run the safety check. If the resulting state is safe, keep the grant; if unsafe, roll the grant back and make i wait. ## Safe, unsafe, deadlocked These are three distinct states, and mixing them up is the standard mistake. Safe means deadlock cannot occur from here regardless of what participants do next. **Unsafe does not mean deadlocked** - it means that if everyone requested up to their declared maximum, the system might not be able to finish anyone. Many unsafe states never deadlock, because participants do not actually claim their maximum. Avoidance is therefore deliberately **conservative**: it refuses grants that would have been fine, trading utilization for a guarantee. ## Why it is not used in real systems The assumptions are severe: - Every participant must declare its **maximum claim in advance**. Real programs discover what they need as they run. - The set of participants and resources must be **fixed and known**. Threads are created dynamically, and locks are created per object. - Resources must be **countable interchangeable instances**. A mutex protecting a specific object is not interchangeable with any other mutex. - The safety check runs on **every request**, at roughly O(n squared times m) for n participants and m resource types. - A refused request means the participant **waits**, so a poor claim declaration wrecks throughput. So it stays a teaching device that makes the safe-state concept precise. That concept, however, does survive in practice. ## Where the idea does show up - **Admission control**: refuse a new job unless the resources it declares are available, so accepted work is guaranteed to complete. - **Reserve-the-whole-set up front**: acquire every permit or lock an operation needs before starting it, and take nothing if the full set is unavailable - the hold-and-wait prevention that avoidance's claim declaration hints at. - **Capacity guards and quotas** in schedulers and cluster managers, which will not place work unless a feasible completion plan exists. - **Bounded borrow depth**: capping how many pool permits a single unit of work may hold is a crude but effective safe-state rule.