Bankers Algorithm - aryanjoshi0823/5143-Operating-System GitHub Wiki

• For multiple-instance resource categories, the resource-allocation graph is ineffective, requiring more complex methods.
• The algorithm ensures resources are allocated safely, akin to a banker lending only if they can fulfill future commitments.
• Processes declare their maximum resource needs upfront.
• Requests are granted only if they leave the system in a safe state; otherwise, the process waits.

• The banker's algorithm relies on several key data structures: ( where n is the number of processes and m is the number of resource categories. )
• Available[ m ] indicates how many resources are currently available of each type.
• Max[ n ][ m ] indicates the maximum demand of each process of each resource.
• Allocation[ n ][ m ] indicates the number of each resource category allocated to each process.
• Need[ n ][ m ] indicates the remaining resources needed of each type for each process. ( Note that Need[ i ][ j ] = Max[ i ][ j ] -Allocation[ i ][ j ] for all i, j. )
• For simplification of discussions, we make the following notations / observations:
• One row of the Need vector, Need[ i ], can be treated as a vector corresponding to the needs of process i, and similarly for Allocation and Max.
• A vector X is considered to be <= a vector Y if X[ i ] <= Y[ i ] for all i.

---

The safety algorithm determines whether a system state is safe by following these steps:

1. Initialization:

   • Let Work be a copy of the available resources (Available).
   • Let Finish be a boolean array of size n (number of processes), initialized to false.

2. Find a Process:

   • Look for a process i such that:
     • Finish[i] == false (process not completed), and
     • Need[i] <= Work (its needs can be satisfied with available resources).
   • If no such i exists, proceed to step 4.

3. Simulate Completion:

   • Set Work = Work + Allocation[i] (simulate releasing resources by process i).
   • Mark Finish[i] = true (indicating the process has completed).
   • Repeat step 2.

4. Safe State Check:

   • If all Finish[i] == true for all i, the state is safe (a safe sequence exists).

---

The Resource-Request Algorithm determines if a new resource request can be granted safely within the framework of the Banker's Algorithm.

1. Verify Request Validity:

   • If Request[i] > Need[i] for any process i, raise an error (invalid request).
   • If Request[i] > Available for any process i, the process must wait for resources to become available.

2. Safety Check:

   • Temporarily simulate granting the request by modifying resource allocations:
     • Available = Available - Request
     • Allocation = Allocation + Request
     • Need = Need - Request
   • Use the Safety Algorithm to verify if the system remains in a safe state.

3. Grant or Deny Request:

   • If the resulting state is safe, grant the request.
   • If the state is not safe, deny the request, and the process must wait.

This ensures that resource allocation never leads to an unsafe state.