Скачать или смотреть OPERATING SYSTEMS - LECTURE -16- DEADLOCK AVOIDANCE (BANKER’S ALGORITHM – DATA STRUCTURES)BCA- S3.

Banker’s Algorithm

The resource-allocation-graph algorithm is not applicable to a resource allocation system with multiple instances of each resource type. The deadlock avoidance algorithm for system with multiple instances of each resource type we use the banker’s algorithm.
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.
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 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. Note that Need[i][j] equals Max[i][j] − Allocation[i][j].
These data structures vary over time in both size and value.

We can treat each row in the matrices Allocation and Need as vectors and refer to them as Allocationi and Needi . The vector Allocationi specifies the resources currently allocated to process Pi ; the vector Needi specifies the additional resources that process Pi may still request to complete its task.