[Solved]: Bankers algorithm - How does it work?

Problem Detail: 

I'm currently studying deadlocks and I'm trying to learn myself the bankers algorithm.

In this example my teacher goes to B first, then C and finally A.

He adds (I think) 2 (row b, Has) with 3 (free) and then gets the new Free value 5. After that he proceeds to row C where he adds 2 (row c, Has) with the free value 5 which gives us a new free value of 7.

After this he goes to the last row A and adds 3 to seven which gives him the free value of 10.

This does not cause a dead lock and I'm wondering why, Isn't he over the Max value of row A?

Here is another example in which the first image is included, but there is also one scenario when we get a dead lock. I don't really understand why since we still get 10 free like the rest of the examples.

Sorry if this is a bit confusing. I can simplify if its needed.

Asked By : saturn

Answered By : Ryan Smith

To understand this problem you have to understand the rules for the safety checks. I am not going to give a detailed explanation of these but you can go here to read more about it. I will try to give an explanation of why C request 1 is safe but A request 1 is not.

There is a value associated with a process and a resource called need. The need is an n-tuple where n is the number of different resources. In this case n is just 1. Calculating the need is just taking the max and subtracting the has for each resource. And there is a safety check that if no process has a need less than or equal to the n-tuple of available resources after a request then that request should be denied.

For C requests 1 it appears that the previous state is after B requests 1. In this C request 1 step we see A has a need (6), B has a need (1) and C has a need (4). Since there is only one resource the n-tuple of available resources is just (1) so this can be granted as B has a need of (1).

For A requests 1 the previous state is the initial state. We then calculate the need of A is (5), B is (2) and C is (5). And the resulting n-tuple of available resources is (1). There is no need which is less than or equal to this so we should reject it.

Be careful when reading more about the subject. The notation is often different, the letters A,B and C are often used to represent resources and p's will be used for processes. You will also be dealing with n-tuples of greater values.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/22877