Bankers Algorithm in OS

Bankers Algorithm in OS:- This algorithm is commonly known as the banker’s algorithm. The name was chosen because the algorithm could be used in a banking system to ensure that the bank never allocated its available cash in such a way that it could no longer satisfy the needs of all its customers. Here we provided Bankers Algorithm in OS.

 

Bankers Algorithm in OS

 

When a new process enters the system, it must declare the maximum number of instances of each resource type that it may need. This number may not exceed the total number of resources in the system. When a user requests a set of resources, the system must determine whether the allocation of these resources will leave the system in a safe state. If it will, the resources are allocated; otherwise, the process must wait until some other process releases enough resources. File Access Methods in OS

Several data structures must be maintained to implement the banker’s algorithm. These data structures encode the state of the resource-allocation system. We need the following data structures, where n is the number of processes in the system and m is the number of resource types:

Available:- A vector of length m indicates the number of available resources of each type. If Available[j] equals k, then k instances of resource type R are available.

Max:- An n x m matrix defines the maximum demand of each process. If Max[i][j] equals k, then process P, may request at most k instances of resource type R₁.

Allocation:- An n x m matrix defines the number of resources of each type currently allocated to each process. If Allocation[i][j] equals k, then process P, is currently allocated k instances of resource type Rj.

Need:- An n x m matrix indicates the remaining resource need of each process. If Need[i][j] equals k, then process P, may need k more instances of resource type R to complete its task. Note that Need[i][j] equals Max[i][j] Allocation[i][j].

These data structures vary over time in both size and value. To simplify the presentation of the banker’s algorithm, we next establish some notations. Let X and Y be vectors of length n. We say that X ≤ Y if and only if X[i]≤Y[i] for all i = 1, 2,…, n. For example, if X = (1,7,3,2) and Y (0,3,2,1), then Y≤ X. In addition, Y< X if Y < X and Y# X.

We can treat each row in the matrices Allocation and Need as vectors and refer to them as Allocation, and Need. The vector Allocation specifies the resources currently allocated to process P the vector Need, specifies the additional resources that process P, may still request to complete its task. NOTE:- IN THIS ARTICLE [, = i]

 

Safety Algorithm

We can now present the algorithm for finding out whether or not a system is in a safe state. This algorithm can be described as follows:

1. Let Work and Finish be vectors of length m and n, respectively. Initialize Work= Available and Finish[i]=false for i=0,1…n-1.

 

2. Find an index í such that both

a. Finish[i] = false

b. Need, ≤ Work

 

If no such i exists, go to step 4.

3. Work = Work + Allocation,

Finish[i]=true

Go to step 2.

 

4. If Finish[i]==true for all i, then the system is in a safe state.

 

This algorithm may require an order of m x n² operations to determine whether a state is safe.

 

Resource-Request Algorithm

Next, we describe the algorithm for determining whether requests can be safely granted. Let Request; be the request vector for process P₁. If Request, [j] == k, then process P, wants k instances of resource type R₁. When a request for resources is made by process P₁, the following actions are taken:

1. It Request, ≤ Need, go to step 2. Otherwise, raise an error condition, since the process has exceeded its maximum claim.

2. If Request, ≤ Available, go to step 3. Otherwise, P, must wait, since the resources are not available.

3. Have the system pretend to have allocated the requested resources to process P, by modifying the state as follows:

Available = Available – Request,

Allocation, = Allocation, + Request,

Need, = Need, – Request,

If the resulting resource-allocation state is safe, the transaction is completed, and process P, is allocated its resources. However, if the new state is unsafe, then P, must wait for Request, and the old resource-allocation state is restored.

Leave a Reply

Your email address will not be published.