Bankers Algorithm in Operating System (OS)
What is Bankers Algorithm in Operating System?
Banker’s Algorithm is a resource allocation and deadlock avoidance algorithm. This name has been given since it is one of most problem in Banking Systems these days.
- In this, as a new process P1 enters, it declares the maximum number of resource it needs.
- The system looks at those and checks if allocating those resources to P1 will leave system in safe state or not.
- If after allocation, it will be in safe state , the resources are allocated to process P1.
- Otherwise, P1 should wait till other process release some resource.
This is the basic idea of Banker’s Algorithm.
A state is safe if the system can allocate all resources requested by all processes ( up to their stated maximums ) without entering a deadlock state.(MCQ Question in CoCubes)
Now, Let’s have a look at how these are implemented . They are implemented using 4 data structure.
Let n be the number of process in system.
Let m be no of resources in system.
- 1 D Array of Size m.
- Each element Available[i] indicates the number of resources of i type available. Denoted by Ri
- 2 D Array of size n*m
- Determines maximum demand of each process.
- Maximum[i,j] tells the maximum demand an ith process will request of jth type resource.
- 2 D Array of size n*m
- Defines number of resources of each type currently allocated to each process.
- Allocation[i,j] means i th process has current k instance of j th type resource
- 2D Array of size n*m
- Tells about remaining resources type which are required by each process.
- Need[i,j] means i th process needs k instance of j th resource type.
- Need[i,j] = Maximum[i,j] – Allocation[i,j]
The above data Structures Size and value vary over time. There are 2 Algorithm on which banker’s Algorithm is build upon
- Safety Algorithm : It finds out whether system is in safe state or not.
- Resource Request Algorithm : It finds out if request can be safely granted.
Safety Algorithm –
Time Complexity of Above Algorithm = O(m*n*n)
Resource Request Algorithm
- Tells if Resource can be safely Granted.
- Request i is Request for Process i.
After a process makes a request, The following steps are followed-
- Banker’s Algorithm
- bankers algorithm for deadlock avoidance in c (in above post itself)Resource Allocation Graph (RAG)
- Dining Philosopher’s Problem
- Bounded Buffer Problem / Producer Consumer Problem
- User Level thread Vs Kernel Level thread
- Multithreading models
- Difference between program and process