Banker's algorithm is a deadlock avoidance
algorithm. It is named so because this algorithm is used in banking
systems to determine whether a loan can be granted or not.

Consider there are n account holders in a bank and
the sum of the money in all of their accounts is S. Everytime a loan
has to be granted by the bank, it subtracts the loan amount from the
total money the bank has. Then it checks if that difference is
greater than S. It is done because, only then, the bank would have
enough money even if all the n account holders draw all their money
at once.

Banker's algorithm works in a similar way in
computers. Whenever a new process is created, it must exactly specify
the maximum instances of each resource type that it needs.

Let us assume that there are

**n**processes and**m**resource types. Some data structures are used to implement the banker's algorithm. They are:`Available:`

It is an array of length**m**. It represents the number of available resources of each type. If`Available[j] = k`

, then there are**k**instances available, of resource type**Rj**.`Max:`

It is an**n x m**matrix which represents the maximum number of instances of each resource that a process can request. If`Max[i][j] = k`

, then the process**Pi**can request atmost**k**instances of resource type**Rj**.`Allocation:`

It is an**n x m**matrix which represents the number of resources of each type currently allocated to each process. If`Allocation[i][j] = k`

, then process**Pi**is currently allocated**k**instances of resource type**Rj**.`Need:`

It is an**n x m**matrix which indicates the remaining resource needs of each process. If`Need[i][j] = k`

, then process**Pi**may need**k**more instances of resource type**Rj**to complete its task.

#### Resource Request Algorithm:

This describes the
behavior of the system when a process makes a resource request in the
form of a request matrix. The steps are:

- If number of requested instances of each resource is less than the need (which was declared previously by the process), go to step 2.
- If number of requested instances of each resource type is less than the available resources of each type, go to step 3. If not, the process has to wait because sufficient resources are not available yet.
- Now, assume that the resources have been allocated.
Accordingly do,

Available = Available - Requesti

Allocationi = Allocationi + Requesti

Needi = Needi - Requesti

This step is done because the system needs to
assume that resources have been allocated. So there will be less
resources available after allocation. The number of allocated
instances will increase. The need of the resources by the process
will reduce. That's what is represented by the above three
operations.

After completing the above three steps, check if
the system is in safe state by applying the safety algorithm. If it
is in safe state, proceed to allocate the requested resources. Else,
the process has to wait longer.

#### Safety Algorithm:

Let
Work and Finish be vectors of length

**m**and**n**, respectively. Initially,- Work = Available
- Find an index
**i**such that both

Finish[i] ==false

Needi <= Work

If there is no such i present, then proceed to step 4.

It means, we need to find an unfinished process whose need can be satisfied by the available resources. If no such process exists, just go to step 4.

- Perform the following:

Work = Work + Allocation;

Finish[i] = true;

Go to step 2.

When an unfinished process is found, then the resources are allocated and the process is marked finished. And then, the loop is repeated to check the same for all other processes.

- If
`Finish[i] == true`

for all i, then the system is in a safe state.

That means if all processes are finished, then the system is in safe state.

Finish[i] =false for i = 0, 1, ... , n - 1.

This means, initially, no process has finished and the number of available resources is represented by the

**Available**array.

**Example:**

**Considering a system with five processes P**

_{0}**through P**

_{4}**and three resources types A, B, C. Resource type A has 10 instances, B has 5 instances and type C has 7 instances. Suppose at time t**

_{0}**following snapshot of the system has been taken:**

Need
[i, j] = Max [i, j] – Allocation [i, j]

So, the content of Need Matrix is:`Try implementing the same in C/Python`

## Comments

## Post a Comment