Deadlock_BankersAlgo

Banker's Algorithm

Banker's Algorithm

• The Banker's algorithm is a resource allocation and deadlock avoidance algorithm used in operating systems.

• It was developed by Edsger Dijkstra in 1965.

• The algorithm helps prevent deadlock in a system by allowing processes to request resources while ensuring that resources are allocated in a safe and non-blocking manner.

• It is commonly used in multi-process, multi-resource systems, such as computer systems and operating systems.

Banker's Algorithm

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 Rj are available.

• Max. An n × m matrix defines the maximum demand of each process.

  If Max[i][j] equals k, then process Pi may request at most k instances of resource type Rj .

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

• Need. An n × m matrix indicates the remaining resource need of each process. If Need[i][j] equals k, then process Pi may need k more instances of resource type Rj to complete its task.

  Need[i][j] = Max[i][j] − Allocation[i][j].

Safety Algorithm

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 i such that both

a. Finish[i] == false

b. Needi ≤ Work

If no such i exists, go to step 4.

3. Work = Work + Allocation_i

Finish[i] = true

Go to step 2.

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


Note: This algorithm may require an order of m × n² operations to determine whether

a state is safe.

Resource-Request Algorithm

Let Request_i be the request vector for process P_i .
If Requesti [j] == k, then process P_i wants k instances of resource type R_j . When a request for resources is made by process P_i, the following actions are taken:

1. If Request_i ≤ Need_i , go to step 2. Otherwise, raise an error condition, since the process has exceeded its maximum claim.

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

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

   1. Available = Available–Request_i ;

   2. Allocation_i = Allocation_i + Request_i ;

   3. Need_i = Need_i –Request_i ;

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

Example

Consider a system with five processes P₀ through P₄ and three resource types A, B, and C. Resource type A has ten instances, resource type B has five instances, and resource type C has seven instances. Suppose that, at time T₀, the following snapshot of the system has been taken:









The system is currently in a safe state or not?

Multiple Choice

In the Banker's algorithm, which data structures are used to keep track of available, maximum, and allocated resources?

• Stacks

• Linked lists

• Queues

• Arrays

Multiple Choice

What is the purpose of the safety check in the Banker's algorithm?

• To allocate resources to a process

• To check if a process has enough resources

• To ensure that resource allocation won't lead to deadlock

• To terminate processes

Multiple Choice

When a process makes a resource request in the Banker's algorithm, what must be checked before granting the request?

• If the process has enough money

• If the process has the highest priority

• If the process is the only one running

• If the requested resources are available and the state remains safe

Multiple Choice

What happens if a resource request in the Banker's algorithm cannot be satisfied without violating safety?

• The process is terminated

• The request is granted anyway

• The process is paused until the resources become available

• The request is denied