For Multiple Instances of Each Resource Type

Introduction & Overview

Read summaries of the section's main ideas at different levels of detail.

Audio Book

Dive deep into the subject with an immersive audiobook experience.

  * **Algorithm Basis: Adaptation of Banker's Safety Algorithm:** The detection algorithm for multiple instances is fundamentally similar to the Banker's Safety Algorithm we discussed for deadlock avoidance. However, instead of using a `Max` matrix (which represents the *maximum* resources a process *might* need), it uses a `Request` matrix.
      * `Request[i][j]` tells us how many instances of resource type `j` process `i` is *currently* requesting.
  * **Key Data Structures (similar to Banker's):**
      * `Available`: A vector representing the number of currently free instances of each resource type. (This is initialized to the system's `Available` resources).
      * `Allocation`: An `n×m` matrix showing how many instances of each resource type are currently allocated to each process.
      * `Request`: An `n×m` matrix showing how many instances of each resource type each process is *currently requesting*. (This is key to detection, replacing `Need` or `Max` from avoidance).
      * `Work`: A temporary vector, initially equal to `Available`. This represents the resources that are currently available for allocation.
      * `Finish`: A boolean array of size `n` (number of processes), initially set to `false` for all processes. `Finish[i] = true` will mean that process `Pi` has been determined to be able to complete.
  * **The Detection Algorithm Steps:**
    1.  **Initialization:** Set `Work = Available`. Set all `Finish[i]` to `false`.
    2.  **Iterative Search:** The algorithm enters a loop, searching for a process `Pi` that meets two conditions:
          * `Finish[i]` is `false` (meaning we haven't yet determined if `Pi` can complete).
          * `Request[i]` \\<= `Work` (meaning `Pi`'s current outstanding request can be satisfied by the currently available `Work` resources).
    3.  **Process Completion Simulation:** If such a process `Pi` is found:
          * We assume `Pi` runs to completion.
          * Its currently allocated resources are "released" back to the system: `Work = Work + Allocation[i]`.
          * Mark `Pi` as complete: `Finish[i] = true`.
          * The search then **repeats from step 2** (it goes back and tries to find *any* process that can now complete, potentially including ones that couldn't before due to new resources in `Work`).
    4.  **Deadlock Identification:** After the loop (when no more processes can be found that satisfy the conditions in step 2):
          * Any process `Pi` for which `Finish[i]` is still `false` is part of a **deadlocked set**. These processes are permanently blocked because their current requests cannot be satisfied, even if all other processes (those for which `Finish[i]` became `true`) eventually complete and release their resources.

Key Concepts

• Cycle ≠ Deadlock: For multiple instance resource types, a cycle in the RAG is only a possibility of deadlock, not a guarantee.

• Banker's Adaptation: The detection algorithm is an adaptation of the Banker's Safety Algorithm.

• Request Matrix: Used instead of Max to represent current outstanding requests.

• Iterative Check: The algorithm simulates processes completing and releasing resources to see if all processes can eventually finish.

• Finish[i] = false: The definitive indicator that process Pi is part of a deadlocked set.

• ---

• Examples

• Given State:

• Available Resources: [1, 2, 0] (e.g., 1 instance of R1, 2 of R2, 0 of R3)

• Allocation Matrix:

• Process | R1 | R2 | R3

• --------|----|----|----

• P0 | 0 | 1 | 0

• P1 | 2 | 0 | 0

• P2 | 3 | 0 | 3

• P3 | 2 | 1 | 1

• P4 | 0 | 0 | 2

• Request Matrix: (What each process is currently waiting for)

• Process | R1 | R2 | R3

• --------|----|----|----

• P0 | 0 | 0 | 0 (P0 is not requesting anything currently)

• P1 | 2 | 0 | 2

• P2 | 0 | 0 | 0 (P2 is not requesting anything currently)

• P3 | 1 | 0 | 0

• P4 | 0 | 0 | 2

• Detection Algorithm Steps:

• Initialization:

• Work = [1, 2, 0] (copy of Available)

• Finish = [false, false, false, false, false] (for P0 to P4)

• Iterative Search:

• Iteration 1:

• Can P0 run? Finish[0] is false. Request[0] = [0, 0, 0]. [0, 0, 0] <= [1, 2, 0] (Work). YES.

• Work = Work + Allocation[0] = [1, 2, 0] + [0, 1, 0] = [1, 3, 0]

• Finish[0] = true

• Can P1 run? Finish[1] is false. Request[1] = [2, 0, 2]. [2, 0, 2] <= [1, 3, 0] (Work)? No, R1 and R3 request too high.

• Can P2 run? Finish[2] is false. Request[2] = [0, 0, 0]. [0, 0, 0] <= [1, 3, 0] (Work). YES.

• Work = Work + Allocation[2] = [1, 3, 0] + [3, 0, 3] = [4, 3, 3]

• Finish[2] = true

• Can P3 run? Finish[3] is false. Request[3] = [1, 0, 0]. [1, 0, 0] <= [4, 3, 3] (Work). YES.

• Work = Work + Allocation[3] = [4, 3, 3] + [2, 1, 1] = [6, 4, 4]

• Finish[3] = true

• Can P4 run? Finish[4] is false. Request[4] = [0, 0, 2]. [0, 0, 2] <= [6, 4, 4] (Work). YES.

• Work = Work + Allocation[4] = [6, 4, 4] + [0, 0, 2] = [6, 4, 6]

• Finish[4] = true

• Iteration 2 (restart search for Finish[i] = false processes):

• Only P1 remains with Finish[1] = false.

• Can P1 run? Request[1] = [2, 0, 2]. [2, 0, 2] <= [6, 4, 6] (current Work)? YES\!

• Work = Work + Allocation[1] = [6, 4, 6] + [2, 0, 0] = [8, 4, 6]

• Finish[1] = true

• Final Check: All Finish are now true.

• Conclusion: In this example, no deadlock exists. All processes can eventually run to completion. If, however, P1's request could not have been satisfied even after all other processes conceptually released their resources, then P1 would have been identified as deadlocked.

• ---

• Flashcards

• Term: Multiple Instance Resource Type

• Definition: Resource type with more than one available unit.

• Term: Request Matrix

• Definition: Matrix showing resources currently requested by each process.

• Term: Work Vector (Detection)

• Definition: Temporary vector representing available resources during detection algorithm, updated by released resources.

• Term: Finish Array (Detection)

• Definition: Boolean array; false indicates process is potentially deadlocked, true means it can complete.

• Term: Deadlocked Process (Multiple Instances)

• Definition: A process Pi for which Finish[i] remains false after the detection algorithm runs, indicating it's permanently blocked.

• ---

• Memory Aids

• Analogy: The Bus Depot Manager: Imagine a bus depot with multiple buses (R1, R2, R3) and many drivers (P0-P4). The manager (OS) needs to see if all drivers can eventually complete their routes, given the currently available buses and the drivers' current outstanding requests for specific buses.

• "Check if Driver Can Go": The manager goes driver by driver. If a driver Pi is not yet on their way (Finish[i] is false) AND they can get the specific buses they currently need (Request[i] <= Work), the manager assumes they leave.

• "Buses Come Back": When a driver leaves, their currently held buses are returned to the depot (Work = Work + Allocation[i]).

• "Re-check Others": The manager then re-checks ALL drivers (even those previously passed over) with the newly available buses (Work).

• "Stuck Drivers": After exhaustively checking everyone, any driver still marked false (Finish[i] is false) is stuck. They can't get the buses they need, even if everyone else who could leave has already left and returned their buses. These are your deadlocked drivers.

• Key Difference from Banker's Avoidance: Remember, in Avoidance, the Banker's algorithm uses MAX to prevent an unsafe state. In Detection, it uses REQUEST to identify if a deadlock already exists by checking if processes can currently complete their requests.

Examples & Applications

Memory Aids

Interactive tools to help you remember key concepts

  * "Check if Driver Can Go"

Glossary