Skip to main content

Banker's Algorithm


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:
  1. 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.
  2. 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.
  3. 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.
  4. 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.
Need[i][j] = Max[i][j] - Allocation [i][j]

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:
  1. If number of requested instances of each resource is less than the need (which was declared previously by the process), go to step 2.
  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.
  3. 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
    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.
  1. 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.
  2. 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.
  3. 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.
Example:
Considering a system with five processes P0 through P4 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 t0 following snapshot of the system has been taken:
safety
Need [i, j] = Max [i, j] – Allocation [i, j]
So, the content of Need Matrix is:
unnamed

Try implementing the same in C/Python

Comments

Popular posts from this blog

Server/Client Communication-python

The basic mechanisms of client-server setup are:

A client app send a request to a server app. The server app returns a reply.  Some of the basic data communications between client and server are:
File transfer - sends name and gets a file. Web page - sends url and gets a page. Echo - sends a message and gets it back.  Client server communication uses socket.
             To connect to another machine, we need a socket connection. What's a connection?  A relationship between two machines, where two pieces of software know about each other. Those two pieces of software know how to communicate with each other. In other words, they know how to send bits to each other. A socket connection means the two machines have information about each other, including network location (IP address) and TCP port. (If we can use anology, IP address is the phone number and the TCP port is the extension).  A socket is an object similar to a file that allows a program to accept incoming connections, make o…

Inter Process Communication(IPC)- Pipes

Interprocess communication (IPC) is a set of programming interfaces that allow a programmer to coordinate activities among different program processes that can run concurrently in an operating system. This allows a program to handle many user requests at the same time. Since even a single user request may result in multiple processes running in the operating system on the user's behalf, the processes need to communicate with each other. The IPC interfaces make this possible. Each IPC method has its own advantages and limitations so it is not unusual for a single program to use all of the IPC methods. pipe In computer programming, especially in UNIX operating systems, a pipe is a technique for passing information from one program process to another. Unlike other forms of interprocess communication (IPC), a pipe is one-way communication only. Basically, a pipe passes a parameter such as the output of one process to another process which accepts it as input. The system temporarily ho…

Inter Process Communication-Message Queue

Interprocess communication (IPC) is a set of programming interfaces that allow a programmer to coordinate activities among different program processes that can run concurrently in an operating system. This allows a program to handle many user requests at the same time. Since even a single user request may result in multiple processes running in the operating system on the user's behalf, the processes need to communicate with each other. The IPC interfaces make this possible. Each IPC method has its own advantages and limitations so it is not unusual for a single program to use all of the IPC methods. Message Based Communication Messages are a very general form of communication. Messages can be used to send and receive formatted data streams between arbitrary processes. Messages may have types. This helps in message interpretation. The type may specify appropriate permissions for processes. Usually at the receiver end, messages are put in a queue. Messages may also be formatted in …