Bankers Algorithm in Operating System (OS)
Operating System – Bankers Algorithm
The Banker’s Algorithm in Operating System is a method used in operating systems to ensure that a system does not experience deadlock or starvation. The algorithm is used to determine the maximum number of resources that can be allocated to each process while still ensuring that the system remains in a safe state. The algorithm keeps track of the maximum number of resources that each process may need and the number of resources that are currently available.
What is Bankers Algorithm?
If a process requests a resource, the algorithm checks to see if the resources are available and, if so, allocates them to the process. If the resources are not available, the algorithm checks to see if they can be freed up by other processes and, if so, allocates them. The algorithm continues to check and allocate resources until the system is in a safe state or until all processes have been allocated the resources they need.
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]
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.
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-
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment