Deadlocks

9.1 Deadlocks: The Basic Picture

9.1.1 Holding and Waiting

A deadlock is a state in which a set of processes is blocked because each process holds a resource and waits for another resource that is held by some other process in the set. The simple setup goes like this: take a list of processes, each holding a resource, each in need of another resource that is not free because some other process holds it. For example, if P1 is holding R1 and is in need of R2, while P2 is holding R2 and is in need of another resource held by P1, then every participant is stuck: each is holding a resource and each is waiting to acquire a resource. The two phrases holding a resource and waiting to acquire a resource are the heart of the topic — they were emphasized as very, very, very important, because a deadlock is exactly the combination of these two actions across a closed circle of processes.

The block diagram of the idea shows a set of processes with two resources, resource one and resource two. Resource one is assigned to process one, but process one is waiting for resource two; resource two is assigned to process two, which is waiting for resource one. Each process is holding a resource and waiting to acquire a resource — the same two actions as before. Draw the picture the way the arrows go: R1 → P1 (P1 holds R1), P1 → R2 (P1 wants R2), R2 → P2 (P2 holds R2), P2 → R1 (P2 wants R1). Follow the arrows from any point and you come back to where you started: the arrows form a closed loop, a cycle, and that cycle is the signature of a deadlock. This cycle can form with any number of processes and any number of resources. The classic small example is a system with two disk drives: P1 is holding one disk drive, P2 is holding the other, and both need one more drive. Only two drives exist, each is held, and there is no way forward — that is one concrete deadlock.

9.1.2 A Real-World Picture: The Traffic Jam

Real-world: the famous everyday example is a traffic jam near a railway track. Vehicles are coming from this side and also from the other side, and both streams have occupied the same stretch of track, so no one can go either this way, that way, or the other way. Every vehicle is stuck at a particular point because every path is held by some other vehicle. We can treat the road as a resource that is held by the vehicles, and each vehicle as one of the processes, each in need of the resource — the road. The system is in a deadlock, and whatever we do to prevent or avoid the deadlock in traffic applies to our set of processes as well.

9.1.3 Finite Resources, Resource Types, and Instances

A deadlock can only occur with finite resources — this is why the discussion is confined to them. Infinite resources would never run out, so no process would ever have to wait, and no deadlock could form. Wait, in this course, is always about a scarce resource: the resource is there in limited supply, everyone wants it, and someone holds it. Finite resources include: the memory space (how many processes have occupied space, and whether enough free space remains for another process), the number of CPUs, the number of files, and the number of devices such as printers. Say three printers exist and more than three processes want one: each process may hold one printer now, and later may need another instance of the same resource type — but it cannot get it because the fourth process holds it, and so on. We can imagine any arrangement in which a process is holding and waiting to acquire a resource.

A distinction must be kept straight: the resource type is the name of the category (printer, CPU), while the number of instances is how many copies of that type exist. "Three printers" means the resource type is printer and the number of instances is three. "CPU is three" means the resource type is CPU and the number of instances is three. Getting the two levels separate makes the later graphs and tables readable — every resource type is one square in the graph, and every instance is one dot inside that square.

9.1.4 The Request–Use–Release Cycle

Whenever a process has to use a resource, it has to request it, then use it, and then release it. Those three steps are the only way to use a resource safely, and they were stated as things to remember. The same three steps appear in every kind of resource, with different vocabulary: for a device, request the device, use it, release it; for a file, open it in order to use it, then close it; for memory, free space is allocated, the space is used, and then the space is freed.

9.1.5 The Same Problem in Synchronization

The dining philosophers problem is the same problem wearing a different costume. The chopsticks are finite, and each philosopher needs two chopsticks — one from the left hand side and one from the right hand side — in order to eat. A philosopher may fail to acquire both because the left chopstick is already held by a neighbor, in which case the philosopher has to wait. In that situation a deadlock may occur, exactly as it can with any finite number of resources: if every philosopher picks up the left chopstick first and then waits for the right one, each is holding one chopstick and waiting for a chopstick held by a neighbor — a perfect circle of holding and waiting. The producer-consumer problem and the reader-writer problem share the same underlying worry: when a limited resource is shared, processes can end up waiting on each other forever. The connection to synchronization also shows up again when the four conditions are explained — mutual exclusion, the first condition, is the very guarantee that the critical section problem fought for.

Visual intuition. Picture the two-disk-drive example as a diagram: two circle nodes (P1, P2) and two square nodes (D1, D2). Edges: D1 → P1, P1 → D2, D2 → P2, P2 → D1. The four arrows form a closed loop — start anywhere, follow arrows, and return to the start. The takeaway: a closed loop of holding and waiting arrows is the picture of a deadlock; this is exactly the cycle that the resource allocation graph of Section 9.3 will look for, on a much larger scale.

Real-world connection: deadlocks are not a classroom fiction. Database engines like MySQL (InnoDB), PostgreSQL, and Oracle detect lock-wait circles between transactions and resolve them by rolling one transaction back — a real deployment of the detection-and-recovery idea met in Section 9.4. Distributed file systems and cloud schedulers face the same circle when two nodes each hold a lock the other node needs. The same structure also appears far from computing: two ships crossing a narrow channel, or two processes on a factory line each waiting for the other's finished part. Wherever a finite resource is shared, the holding-and-waiting circle can appear, and the algorithms of this module are how systems break it.

9.2 The Four Necessary Conditions of a Deadlock

A deadlock has four characterizations (also called necessary conditions). These are the features that must all be present for a deadlock to occur, and each one gets a careful definition. Think of them as the ingredients of a recipe: the dish (deadlock) is only on the table when every single ingredient is in the pot at the same time.

9.2.1 Mutual Exclusion

Mutual exclusion is the condition that only one process at a time can use a resource. This is the same idea used when processes are synchronized: the resource is mutually exclusive, so any other process that arrives must wait for the resource. Without mutual exclusion, several processes could use the same resource at once, and the data they share would become inconsistent. If all the processes try to access a particular resource at the same time, a race condition occurs and the data is no longer consistent. This is the situation seen earlier in the critical section problem, the producer-consumer problem, and the reader-writer problem, and it is condition number one for a deadlock.

9.2.2 Hold and Wait

Hold and wait means a process is holding at least one resource and is in need of additional resources, so it is waiting to acquire another resource that is held by other processes. The process is doing both things at once: holding something it already has, and waiting for something it still needs. This is the second characterization of a deadlock.

9.2.3 No Preemption

No preemption means a resource held by a process can be taken away only voluntarily — the process itself must release it, and normally it releases only after completing its task. If there is no preemption, a process keeps on holding its resource, no other process can use that resource, and a deadlock can occur. The condition to watch for is the absence of preemption: the resource cannot be forcibly reclaimed while the holder still needs it.

9.2.4 Circular Wait

Circular wait is the situation in which the waiting processes form a ring. Starting from P0, P1, and so on up to Pn, the next process is again P0. Concretely: P0 is waiting for a resource held by P1, P1 is waiting for a resource held by P2, and so on until the last one, Pn, which is waiting for a resource held by P0. The waiting goes around in a circle, and when that happens a deadlock will occur. This is the fourth characterization.

9.2.5 All Four Must Hold at the Same Time

These four are necessary conditions, and the rule to remember is that all four must occur simultaneously before we can say a deadlock has occurred. Even if one of them is not present, we cannot say for sure that a deadlock will occur — there may be chances of a deadlock, but it is not the deadlock yet. The simultaneity was stressed twice: not one condition now and another later or thereafter — no, all four at the same time. This is the kind of statement you should not forget. In real time, if the number of resources is limited and the number of processes that want to use them is larger, the chances for a deadlock exist — but again, only mutual exclusion alone is not enough; all four conditions must occur simultaneously.

Visual intuition. Picture the four conditions as four locked doors on a corridor. Any one door open lets you walk through (no deadlock); all four shut at the same moment and you are trapped. In graph terms, mutual exclusion makes edges, hold and wait plus no preemption keep the edges alive, and circular wait closes the edges into a loop — the "closed loop" of arrows from Section 9.1.1 is precisely circular wait in picture form.

9.2.6 Student Questions and Answers

Real-world connection: the four conditions are the checklist engineers actually use. MySQL's InnoDB storage engine builds a "wait-for" picture of transactions holding row locks and prints the exact circular chain when it aborts a transaction — that chain is condition four made visible. Deadlock monitors in database engines and in the Java virtual machine's lock manager work by watching for the ring while the other three conditions are taken for granted. If you can name which condition a real system violated, you can name the mechanism that fixed it.

9.3 Resource Allocation Graphs

The processes and resources of a system can be pictured with the resource allocation graph (RAG), which makes deadlock questions much easier to see. By drawing the graph and looking for cycles, we can say whether a deadlock exists.

9.3.1 Vertices and Edges: Request Edges and Assignment Edges

The graph has a set of vertices, call it V, and a set of edges, call it E. V consists of two kinds of vertices: every process P1, P2, up to Pn, and every resource type R1 up to Rm present in the system. There are two named edges:

• A request edge: if process P1 is requesting resource R1, the arrow starts from the process and ends at the resource — process → resource.
• An assignment edge: if a process has already been assigned (holds) a resource, the arrow goes the reverse way, from the resource to the process — resource → process.

The direction of the arrow is the key difference: a process that is in need of a resource points to the resource; a process that already holds a resource is pointed at by the resource. Every graph in this topic is drawn with only these two kinds of edges.

9.3.2 Drawing Conventions: Circles, Squares, and Dots

The drawing rules are simple. A process is drawn as a circle. A resource is drawn as a square. If a resource has several instances, the instances are shown as dots inside the square; for example, a printer with four instances is drawn with four dots, and the four dots alone are enough to tell you the resource has four instances. A request edge starts from the process circle and ends by touching the border of the resource square. An assignment edge starts from a particular dot (a particular instance) inside the square and ends at the process circle, because the process holds one specific instance of the resource. With four instances, each instance may be allocated to one or another process.

9.3.3 Worked Example: Three Processes and Four Resources

9.3.4 Cycles, Deadlock, and the Number of Instances

Some basic facts govern the whole method, and they were marked very, very important:

1. If the graph contains no cycle, there is no deadlock. The procedure: draw the resources and processes, draw the request and assignment edges, then check for a cycle. No cycle → no deadlock.
2. If the graph contains a cycle and there is only one instance of each resource type, then the cycle is both a necessary and sufficient condition for the existence of a deadlock. With a single instance per type, a cycle means deadlock, for sure.
3. If the graph contains a cycle but the resources have multiple instances, then the cycle is a necessary but not sufficient condition. There may be a deadlock, or there may not. Why? Because if one of the processes holding an instance releases it, that instance may then be allocated to a process that had already requested it, and the waiting chain unwinds. The chances are better than not, but we cannot say for sure.

The example graph from the previous section has a cycle, and here the number of instances decides the story. P3 is in need of R2, and R2's two instances are currently held by P1 and P2 (the lecture's slip mentioning a process "P4" was a slip indeed — this example defines only three processes, and R2's two instances are allocated to P1 and P2). At some later point P1 or P2 may release its instance, and the freed instance may be allocated to P3; anything can happen once a holder finishes using the resource. Even though a cycle exists, there may be no deadlock. This is why, for multiple instances, we need another method — that is what the banker's algorithm in Section 9.6 is for.

Visual intuition. Picture the two cycles from the worked example as two nested loops of arrows: one loop P1 → R1 → P2 → R3 → P3 → R2 → P1, and inside it the shorter loop P2 → R3 → P3 → R2 → P2. Both loops pass through the pair (R2 → P1 / P2). Since R2 has two instances, one held by each process, the "two loops" share the same bottleneck resource; if either P1 or P2 were to finish and release, both loops would snap open at once. That is why a single release can dissolve a cycle when instances are multiple — and why the same graph with all single-instance resources would be an unrecoverable deadlock.

9.3.5 Worked Example: Six Resources and Three Processes

The class worked a second example together. Suppose there are six resources — resource types R1, R2, R3, each with two instances — and three processes, each process needing three resources (one instance of each type).

Real-world connection: resource allocation graphs are the basis of real deadlock detection tools. Databases and hypervisors track lock ownership as directed edges and run cycle-detection algorithms ($O(n^2)$ on $n$ processes) at intervals — the same "follow the arrows" procedure done by software. The graph is also the natural language for explaining incidents: a database deadlock report that prints "transaction A holds row 5, waits for row 9; transaction B holds row 9, waits for row 5" is a resource allocation graph in text form.

9.4 Three Ways to Handle a Deadlock

9.4.1 Prevention, Detection and Recovery, or Ignoring

Once we understand that deadlocks are possible, we have to decide how to handle them. There are two serious strategies, and a third lazy one. First, prevention: ensure that the system will never enter the deadlock state at all. Second, detection and recovery: allow the system to enter the deadlock state, detect that it has done so, and then recover from it. Third, ignoring: pretend everything is fine and act as if the deadlock never happened — that is the last resort, used by many systems in practice because deadlocks are rare. The aim, stated simply, is to prevent, avoid, detect, or recover.

9.4.2 Prevention versus Avoidance

Prevention and avoidance are different approaches, and the difference is the information each one needs. Prevention works by making sure that at least one of the four necessary conditions can never hold. If one of the four conditions — mutual exclusion, hold and wait, no preemption, circular wait — cannot occur, then the deadlock has been prevented. Prevention needs no a priori information: the system never needs to know in advance how many resources each process will use overall.

Avoidance has a different goal: keep the system in a safe state and make sure it never enters an unsafe state, so that it never reaches the deadlock state. For this, the system needs additional a priori information about the overall use of each resource by each process. Each process must declare, up front, things like: P1 needs three instances of R1, two instances of R2, and one instance of R3. Only with that declared information can the system decide whether granting a request is safe. What a safe state and an unsafe state are is explained in Section 9.6.

Real-world connection: database engines combine the strategies. MySQL InnoDB and Oracle run in detection-and-recovery mode: they allow lock waits, detect the cycle, and roll back the smallest transaction in it — a real "recover from the deadlock" implementation. Systems that cannot tolerate rollback (some real-time controllers) instead forbid the conditions by construction. And the "ignoring" strategy is everywhere: everyday desktop and server operating systems ship without deadlock avoidance, betting on rarity — which is why database transactions were invented to bring the safety guarantee back at the application layer.

9.5 Deadlock Prevention: Break One of the Four Conditions

The aim of prevention is to make at least one of the four necessary conditions never occur. We go through the conditions one by one and see how each can be attacked.

9.5.1 Mutual Exclusion Cannot Be Prevented for Non-Shareable Resources

For mutual exclusion, we first separate shareable resources from non-shareable resources. A non-shareable resource, such as a printer, can be used by only one process at a time; a read-only file is a shareable resource, usable by many readers at once. If a resource is shareable, mutual exclusion is not required for it — but then it is not the source of a deadlock either, because no one waits for it. We are always dealing with non-shareable resources when deadlocks matter. If a non-shareable resource has a single instance, then mutual exclusion definitely happens — the resource cannot be shared. So we cannot prevent a deadlock by attacking mutual exclusion for non-shareable resources; we must check whether the next condition can be prevented instead.

9.5.2 Breaking Hold and Wait: Two Protocols

To make hold and wait impossible, we guarantee that whenever a process requests a resource, it does not hold any other resource. If P1 needs R1, it should not also hold R2 or R3 — there must be no assignment edge from those resources to P1 while it is requesting R1. Two protocols achieve this:

• Protocol 1 — request everything up front: a process requests and is allocated all the resources it will ever need before it starts execution. There is no partial allocation: if P1 needs R1, R2, and R3, all three are given at once, P1 uses everything, and only after P1 releases them does P2 receive whatever it needs.
• Protocol 2 — request only when holding nothing: a process may request a resource only when it holds no other resource. If P1 wants R1, it must first release every resource it already holds, and only then ask for R1. So a process uses a resource, releases it, and then requests the next one.

One caution: if resource utilization is very low, there is a possibility of starvation. Suppose only R1 is in demand and no process ever requests R2, even though R2 exists and is free — utilization of R2 is zero, every process fights over R1, and some processes may wait forever. The requests should be balanced so every process requests and acquires each of the resources it needs.

9.5.3 Breaking No Preemption: Two Protocols

"No preemption" means a process keeps using a resource without interruption; to prevent deadlock we want preemption to be possible. Two protocols:

• Protocol 1 — release everything if you cannot get the next resource: if a process holding some resources requests another resource that cannot be allocated immediately, then all the resources currently held by the process are released. Example: P1 holds R1 and R2 and requests R3; if R3 is not immediately available, P1 first releases R1 and R2. The preempted resources are added to the list of resources needed by the process (they are still required later). The process is then restarted — because it had not finished using the resources before they were preempted — and after some time it must regain all the resources it used before, plus the one it was requesting.
• Protocol 2 — preempt from a waiting process: if a process requests a resource, we check whether an instance is free. Suppose P1 asks for R1, but R1 is held by P2, and P2 is itself waiting for some other resource, say R3. Then we preempt the desired resource (R1) from the waiting process P2 and allocate it to P1. That way preemption happens without stopping a process that is actually working.

9.5.4 Breaking Circular Wait: Ordering Resource Types

To prevent circular wait, impose a total ordering on all resource types and make every process request resources in increasing order of enumeration. Assign each resource type a number through a function F, and require that a process never requests a resource with a number lower than (or equal to) one it already holds. If R1 gets the number 2 and R2 gets the number 5, the request order must go 2 → 5, increasing, never the reverse.

Example: three resources — a DVD, a file, and a printer. Suppose P1 needs the DVD and the file, and then a printer to send information to print. We assign numbers in increasing order: DVD gets 2, the file gets 4, and the printer gets the next number. Then P1 must first ask for the DVD, then for the file, and only then for the printer — it may never ask for the file first and the DVD second, and all three should not be held by P1 at the same time. The resource that is already allocated must have a number less than the number of the resource being requested.

Why does this rule kill circular wait? Suppose a circular wait existed. The process holding R1 would be waiting for a resource with a higher number, say R2; holding R2 would wait for R3, and so on, giving $F(R_1)<F(R_2)<F(R_3)$. Going around the circle we end back at R1, which would require $F(R_3)<F(R_1)$ — but the numbers cannot both be increasing and come back down. The ordering makes the circle impossible; the contradiction proves there is no circular wait.

$$\begin{array}{rlrlr}\text{Assume a circular wait: }& P_i\text{ holds }{R}_i\text{ and waits for }{R}_{i+1},\text{ for }i=0,1,\dots ,n(\mathrm{mod}n)\text{The ordering rule forces: }& F(R_i)<F(R_{i+1})\text{for every }i\text{Chaining all steps: }& F(R_0)<F(R_1)<\cdots <F(R_n)<F(R_0)\text{By transitivity: }& F(R_0)<F(R_0),\text{which is impossible.}\end{array}$$

The contradiction means the assumed circular wait cannot exist: with a consistent total ordering, the ring of arrows can never close. In the small example: DVD (2) → file (4) → printer (6) is the only legal direction, so a "waiting ring" would need someone to go from printer (6) back to DVD (2) — forbidden by the rule.

The main problem with this scheme is low device utilization: the printer may not be used for a long time, device utilization falls, and overall system throughput decreases. These costs are the price of prevention.

9.5.5 The Price of Prevention: Low Utilization and Starvation

To summarize the cost side: breaking hold and wait by allocating everything up front wastes resources, because a process may hold resources it will not use for a long time; low utilization can cause starvation, as in the R1-only example; breaking circular wait by ordering can leave some device idle for long stretches; throughput drops. These are the trade-offs, but if we must prevent a deadlock, then at least one of the four conditions must be made impossible — no mutual exclusion, or no hold and wait, or preemption, or no circular wait.

Real-world connection: resource ordering is exactly what real systems use. Database engines teach transactions to acquire locks in a fixed order (for example, always lock account A before account B) to make lock-wait rings impossible, and tools like FreeBSD's witness monitor running kernels, recording the order in which mutexes are acquired and warning on the console the moment a thread violates the ordering. The price is familiar to every database administrator: transactions hold locks longer, contention rises, and throughput falls — the same utilization-versus-safety trade the professor describes.

9.6 Deadlock Avoidance

9.6.1 A Priori Information and the Resource Allocation State

If the operating system is given complete information about each process — how much it has requested and how much it will release — then a deadlock can be avoided. This sounds simple and useful, but there is a catch: we would need to know the future requests and releases of each resource. When P1 needs R1 we do not know at present — it may be holding R2 right now, and it may need R1 or R3 later. Those future needs cannot be predicted in general. What we do know is captured in the resource allocation state: the number of available resources, how many instances have been allocated to each process, and the maximum demand of each process.

The resource allocation state is the complete picture the system reasons with: (1) how many instances of each resource type are currently available, (2) how many instances of each type are currently allocated to each process, and (3) the maximum demand each process declared. Every request, grant, and release moves the system from one state to the next; avoidance is the policy of only ever moving to safe states.

9.6.2 Safe States and Unsafe States

A state is safe if there exists a sequence of processes such that there are enough resources for the first process to finish, and as each process finishes and releases its resources, there are enough for the next one to finish. If we write some sequence P1, P2, P3 — any sequence, not necessarily the order of creation — then P1 finishes first, releases its resources, P2 gets what it needs and finishes, and so on to P3. More carefully: if a process Pi needs a resource that is not immediately available, Pi has to wait until some Pj completes; when Pj completes, Pi can take the needed resource, execute, return the allocated resource, and terminate; then Pi+1 can obtain the resource, and the sequence goes on.

From this comes the central link: if a system is in a safe state there is no deadlock. If a system is in an unsafe state there is a possibility of deadlock. Avoidance means ensuring the system never enters an unsafe state; then the deadlock is avoided. Two statements to keep straight, and they are easy to confuse:

• All deadlocks are unsafe states.
• Not all unsafe states are deadlocks.

Picture the whole space of states: inside it there is a safe region where no deadlock can occur; outside the safe region lies the unsafe region, where a deadlock is possible but not certain; and inside the unsafe region there is a smaller portion that actually is the deadlocked state. A deadlock, when it occurs, is always within the unsafe region — but being unsafe does not mean being deadlocked.

9.6.3 Single-Instance Systems: The Claim Edge

For a system where each resource type has a single instance, avoidance uses the resource allocation graph with one extra kind of edge. Alongside the request edge and the assignment edge, there is a third edge called the claim edge. A claim edge indicates that the process may request this particular resource at some point in the future. It is drawn as a dashed line from the process to the resource (the other edges are solid, and the assignment arrow points the reverse way). The life cycle of an edge:

• A claim edge may be converted into a request edge when the process actually requests the resource — but we do not know when that will happen.
• A request edge is converted into an assignment edge when the resource is allocated.
• When the resource is released, the assignment edge is converted back into a claim edge, because after some time the same process may use the resource again.

All claim edges must be declared a priori — mentioned before the process starts. Consider a graph where R1 is assigned to P1, and P1 may need R2 in the future (dashed claim edge P1 → R2). P2 is requesting R1, which is held by P1, and P2 may also claim R2. If, later, P1's claim converts to a request and P1 is allocated R2, there is no cycle. But if P2's claim converts to a request and the resource is allocated to P2, the request edge creates a cycle, and a deadlock may follow. In a single-instance system, seeing the cycle tells us a deadlock may occur — the claim is not yet a request, so the cycle is only possible, but the moment the claim becomes a request the deadlock risk is real.

9.6.4 Multiple-Instance Systems: The Banker's Algorithm

When resource types have multiple instances, the graph method is not enough, and we use the banker's algorithm. The algorithm handles multiple instances, and while it was not claimed to be very powerful, it does help to avoid a deadlock.

The assumptions behind it: every process has to claim the maximum use of each and every resource; a process has to request a resource, and sometimes it may need to wait; only when a process gets all its resources will it return them, and it must return them within a finite amount of time — if it acquires a resource at time t1, then at t2 or t3 it has to give it back after completing its work; it cannot hold a resource for a longer time.

9.6.5 The Four Data Structures

Let n be the number of processes and m the number of resource types. The algorithm needs four data structures:

• Available: a vector of length m. $\text{Available}[j]=k$ means there are k instances of resource type Rj currently available. For example, if we call the printer resource type one, then $\text{Available}[1]=3$ says three printer instances are free right now.
• Max: an n × m matrix. $\text{Max}[i][j]=k$ means process Pi may request at most k instances of resource type Rj over its whole life.
• Allocation: an n × m matrix. $\text{Allocation}[i][j]=k$ means process Pi is currently allocated k instances of Rj.
• Need: an n × m matrix. $\text{Need}[i][j]=k$ means process Pi may need k more instances of Rj to complete its task.

The need of a process is what is left after what it already has. The formula — stated in class as one to remember and use:

$$\text{Need}[i][j]=\text{Max}[i][j]-\text{Allocation}[i][j]$$

9.6.6 The Safety Algorithm

The safety algorithm decides whether the current state is safe. It uses two more variables, each a vector: Work of length m and Finish of length n.

1. Initialize: $\text{Work}=\text{Available}$ and $\text{Finish}[i]=\text{false}$ for every process $i=0,1,\dots ,n-1$. Setting Finish to false means: as of now, no process has completed its task.
2. Find an index i such that $\text{Finish}[i]=\text{false}$ and the need satisfies $\text{Need}[i][j]\le \text{Work}[j]$ for every resource type j. If no such i exists, go to step 4.
3. Assume the process finishes: $\text{Work}[j]=\text{Work}[j]+\text{Allocation}[i][j]$ for all j (the process is allocated what it needs, does its work, and returns everything, so the pool grows), set $\text{Finish}[i]=\text{true}$, and go back to step 2.
4. If $\text{Finish}[i]=\text{true}$ for all i, the system is in a safe state; otherwise the system is unsafe. The loop continues until no other process can be satisfied, and only then do we declare the outcome.

9.6.7 Worked Example: Five Processes and Three Resource Types

9.6.8 The Resource-Request Algorithm

Any process may request any resource at any time, and the system must decide whether the request can be granted. The request is recorded in a fifth data structure: $\text{Request}[i][j]=k$ means process Pi wants k more instances of resource type Rj. The resource-request algorithm checks the request in steps:

1. Check against Need: if $\text{Request}[i]\le \text{Need}[i]$ (component by component), go to step 2; otherwise raise an error — the process has exceeded its maximum claim. A process may request only up to its declared need.
2. Check against Available: if $\text{Request}[i]\le \text{Available}$, go to step 3; otherwise the process must wait until the resource is available.
3. Pretend to allocate: modify the state as if the request were granted:

$$\begin{array}{rl}\text{Available}& =\text{Available}-\text{Request}[i]\\ \text{Allocation}[i]& =\text{Allocation}[i]+\text{Request}[i]\\ \text{Need}[i]& =\text{Need}[i]-\text{Request}[i]\end{array}$$

Then run the safety algorithm on this pretend state. If the pretend state is safe, the request is granted for real. If it is unsafe, the process waits, and the older resource-allocation state is restored.

9.6.9 Checking a Request: 1 0 2 by P1

The general idea was summarized in class: if we can allocate the resource to a process and the system stays safe, we say the system is safe; if the process waits with the older state restored, the system may be in an unsafe state — but again, unsafe does not mean deadlock.

9.6.10 Practice Problem: Requests by P4 and P0

As practice for the same rules, check whether a request by P4 and a request by P0 can be granted in the worked example's state. Apply the resource-request algorithm: check each request against the process's Need, check against Available, and run the safety algorithm on the pretend state. The example and this practice set will be continued in the next session, along with another example drawn from the exercises. Here is the method applied now, so the checks are ready:

• P4 requests (3 3 0). Step 1: 3 3 0 ≤ Need P4 = 4 3 1 — yes. Step 2: 3 3 0 ≤ Available 3 3 2 — yes (3 ≤ 3, 3 ≤ 3, 0 ≤ 2). Step 3: pretend — Available becomes 0 0 2, Allocation[P4] becomes 3 3 2, Need[P4] becomes 1 0 1. Run safety on this pretend state with Work = 0 0 2: no process fits — P1 needs 1 2 2, P2 needs 6 0 0, P3 needs 0 1 1, P4 needs 1 0 1, P0 needs 7 4 3 — none are component-wise ≤ 0 0 2. The pretend state is unsafe, so P4's request is denied: P4 waits and the old state is restored.
• P0 requests (0 2 0). Step 1: 0 2 0 ≤ Need P0 = 7 4 3 — yes. Step 2: 0 2 0 ≤ Available 3 3 2 — yes. Step 3: pretend — Available becomes 3 1 2, Allocation[P0] becomes 0 3 0, Need[P0] becomes 7 2 3. Run safety with Work = 3 1 2: P3 fits (0 1 1 ≤ 3 1 2) → Work = 3 1 2 + 2 1 1 = 5 2 3; P1 fits (1 2 2 ≤ 5 2 3) → Work = 7 2 3; P2 fits (6 0 0 ≤ 7 2 3) → Work = 10 2 5; P0 fits (7 2 3 ≤ 10 2 5) → Work = 10 5 5; P4 fits (4 3 1 ≤ 10 5 5) → Work = 10 5 7. All finish, so the pretend state is safe, and P0's request is granted.

A useful cross-check from the prescribed book: the same two requests, evaluated in the state that results after P1's request (1 0 2) is granted (Available 2 3 0), reach different verdicts — P4's (3 3 0) is refused because the resources are not available, and P0's (0 2 0) is refused because that pretend state is unsafe. The verdict depends on the state the system is in, which is why every request must be re-checked against the current Available, Allocation, and Need.

Real-world connection: avoidance is the philosophy behind resource managers that must never lose a job — batch schedulers, mainframe resource managers, and database deadlock avoidance layers all declare maximums or run pretend-state checks. The banker's algorithm itself is rarely the scheduler of a general-purpose operating system today (real processes cannot truthfully declare future maximums, and the $m\times n^2$ safety scan on every request is costly), but its safe-state idea survives everywhere: "never make a change you cannot complete" is the same guarantee behind two-phase locking in databases and behind transaction managers that refuse to commit a state that cannot be rolled forward.

Exam Guidance Summary

Exam note: the coverage plan for the course is that up to module 4 the topics are process synchronization, and this session starts the next module, deadlocks. The plan is to cover the first half of the deadlock module — up through deadlock avoidance — before the mid-semester examination, and the remaining topics after the mid-semester. For the comprehensive exam, all topics are included. The banker's algorithm worked example was explicitly stated as not being part of the mid-semester, so it can be set aside for the mid-semester — "no need to worry" — but it does belong to the full topic set.

Exam note: for process scheduling problems, answers may be typed or written by hand and scanned/uploaded — both facilities are available, and for scheduling you have to solve the problems regardless: draw the table and the Gantt chart, work the computation in the notebook, and submit. For whichever question, choose whichever method is feasible for that particular question. The prescribed book is the book to follow, and the class example for the banker's algorithm is even in the book; the next session takes another example from the exercises at the end of the chapter.

Exam note: the four necessary conditions and their simultaneity rule are the kind of statement to expect — "you can master" it, and the "necessary and sufficient" versus "necessary but not sufficient" distinction for cycles in a resource allocation graph was repeated as very, very important. The formula Need = Max − Allocation was also emphasized as one to remember and use.

Exam note: the mid-semester examination is next week, with a makeup examination on the last day of the makeup period; the advice is to concentrate on the examination — all the best.

Key Industry Applications

Real-world: the traffic jam near a railway track is the everyday picture of a deadlock — vehicles from both directions occupy the same stretch of road, the road is the resource, the vehicles are the processes, and no one can move. Prevention or avoidance techniques for deadlock apply to the traffic situation in the same way they apply to a set of processes.

Real-world: printers, DVD drives, and other I/O devices are the concrete example of non-shareable, limited resources. If more processes want the resource than there are instances, chances of a deadlock exist; mutual exclusion keeps the data consistent and avoids race conditions in the critical section, producer-consumer, and reader-writer settings.

Real-world: files are used through open, use, and close — the file-world version of request, use, and release — and memory is used through allocation of free space, use, and freeing the space. A system with two disk drives, where two processes each hold one drive and both need one more, is the classic small deadlock.

Real-world: the banker's algorithm — named for its banking analogy and developed by Edsger Dijkstra (1965) — is the standard method for deadlock avoidance with multiple instances, and its worked example is the one found in the prescribed book.