The Banker's Algorithm is a critical deadlock avoidance method in operating…
2024
The Banker's Algorithm is a critical deadlock avoidance method in operating systems, designed to facilitate resource allocation without causing deadlock. It operates by maintaining information about the maximum resources Each process may require, the current allocated resources and the available resources in the system. The algorithm checks each resource request to determine, if granting it would leave the system in a safe state, meaning that there is always a sequence in which all processes can complete their execution without getting stuck due to resource unavailability. Each process must specify its maximum demand for each resource type before it starts execution. When a process requests additional resources, the algorithm checks if granting the request will keep the system in a safe state. If so, the resources are allocated otherwise the process must wait until its request can be safely fulfilled.
Which data structure does the Banker's Algorithm use to maintain the state of available, maximum and allocated resources?
- A.
Priority Queue
- B.
Hash table
- C.
Wait-for-Graph
- D.
Matrices and Vectors.
Attempted by 159 students.
Show answer & explanation
Correct answer: D
Answer: The Banker's Algorithm uses matrices and vectors to maintain resource state and perform safety checks.
Available vector: a vector of length m (number of resource types) that shows how many units of each resource are currently available.
Max matrix: an n × m matrix (n processes, m resource types) where each row gives the maximum demand of a process for each resource.
Allocation matrix: an n × m matrix showing the currently allocated resources to each process.
Need matrix: computed as Need = Max − Allocation; it represents remaining resource requirements for each process.
How these structures are used (safety check and request handling):
When a process makes a request, first verify the request does not exceed its Need and does not exceed Available. If it exceeds either, the request is denied or the process must wait.
If the request is potentially valid, pretend to allocate the resources: Available := Available − Request, Allocation := Allocation + Request, Need := Need − Request.
Perform the safety algorithm: set Work := Available and Finish[i] := false for all processes. Find a process whose Need ≤ Work and Finish is false; if found, set Work := Work + Allocation of that process and mark Finish true; repeat until no such process exists.
If all Finish[i] become true in the simulation, the state is safe and the request can be granted; otherwise roll back and the process must wait.
Key formula: Need = Max − Allocation
A video solution is available for this question — log in and enroll to watch it.