Category Archives: Operating systems

Banker’s algo for deadlock avoidance

What is deadlock?

From wikipedia- A deadlock is a situation where in two or more competing actions are each waiting for the other to finish, and thus neither ever does. It is often seen in a paradox like the “chicken or the egg“. The concept of a Catch-22 is similar.

So what is a deadlock in terms of operating system job scheduling. It is same, there are multiple jobs which are trying to gain control of resources and end up in a situation where each process is waiting for some resiurce which is being held by another process.

How to avoid such situations? Banker’s algoirthm is the answer. As the name suggest, the algorithm uses intellegence shown by a banker in order to maintain safe amount of cash in the bank, so that bank never runs into a situation where it has no money to fulfill its customer needs.

A very simple example will be, say the bank has 60K amount. There are 3 customers A, B and C. A needs 30K for its project, B needs 25K, and C needs 40K. Now we know that bank can fulfill need of all three customers, but not at once. So ideally the bank will fulfill one customer’s need at a time, wait for the customer to return the money (we will ignore interest for simplicity, and we will assume money will be returned by cistomer as soon as project is finished though in real workd cstomer might need some time), and then move on to next. Which is not effective use of money as customers will need to wait while others finish. In practical world, not all the money will be needed for projects in one go, so the bank can ask customers how much amount they will need at what stage, and at what time they can return the money, and try to organize the finances in a way that all customers can finish there projects in best possible time. The same kind of logic is used by job-scheduler of on operating system to make sure all jobs gets finished in best possible time, avoiding deadlock.

Lets say customers provide this data to bank

Customer A: Need 10K at start

Customer B: Need 10K at start

Customer C: Need 10K at start

The bank sees it can afford to give this money to all the customers as it will still have enough money to fulfill needs of all the customers.

In stage 2, all customers again come up with a demand of 10K. Now the bank sees if it will allocate all the money, it will run out of money with none of the projects being successfully completed, hence no point of recovery. So it must deny some of the customer. Safest bet will be to refuse the amount to C and tell it to wait till bank has enoght fund. Allocate the money to A and B, as it will still have enough money to give to these customer to finish the project.

So C is put on hold and A and B moves on with the project. Now say A comes up with demand of 10K, which bank will fulfill and A will be able to finish project successfully and return 30K. Now bank can provide money to C, as it knows it will have sufficient funds for other customers.

The same intellegence is used by an OS to make sure the system never runs out of resources.