Banker’s algorith

Question

Allocation. MAX

R1 R2 R3 R4. R1 R2 R3 R4

T1. 3. 0. 1. 4. 3. 1. 1. 7

T2. 2. 2. 1. 0. 3. 2. 1. 1

T3. 3. 1. 2 1. 3 3. 2. 1

T4. 0. 5. 1. 0. 4. 6 1. 2

T5. 4. 2. 1. 2. 6. 3. 2. 5

Using the banker's algorithm, determine whether or not each of the following states is unsafe. If the state is safe, illustrate the order in which the threads may complete. Otherwise, illustrate why the state is unsafe. Show details for either scenario. (a) Available = (0, 3, 0, 1)

(b) Available = (1, 0, 0, 2)

For A others say that it’s unsafe because it doesn’t work for T1 and T5but it works for me. So could you explain why it won’t work.

to solve this question I get the need first getting	R1 R2 R3 R4
T1	2   1    0    3
T2	1   0    0    1
T3	0   2    0    0
T4	4   1    0    2
T5	2   1    1    3

then I check using T1<= 0,3,0,1 which is false but is true for T3 which is (3,4,2,2) the rest are false then I check T1 with the new available which is true no?

Answer 1

The others are right about (a), and I can show you exactly where your version goes off. But first there is a small arithmetic slip in your Need table that is worth fixing even though it is not what causes the disagreement.

Need is Max minus Allocation, row by row:

        R1  R2  R3  R4
  T1     0   1   0   3        max 3,1,1,7  minus  alloc 3,0,1,4
  T2     1   0   0   1
  T3     0   2   0   0
  T4     4   1   0   2
  T5     2   1   1   3

You had T1 as 2, 1, 0, 3. For R1, T1's max is 3 and it already holds 3, so its remaining need there is 0, not 2. Everything else in your table matches.

Now for part (a) with Available = (0, 3, 0, 1). Your first two steps are exactly right. T1 cannot go, and T3 can, and when T3 finishes it releases its (3, 1, 2, 1) so Available becomes (3, 4, 2, 2). You got all of that. The step after is where it breaks. You checked T1 against (3, 4, 2, 2) and read it as true, but look only at the R4 column. T1 still needs 3 of R4 and there are only 2 available. Three is not less than or equal to two, so T1 is still blocked. Remember, the comparison has to hold in every column at once, and a single column failing is enough to stop the whole thread. R4 is the column that decides this entire problem, and it is easy to lose track of because it is the last one.

If you keep going past T3 you can get two more threads out, but not the last two:

T3 runs  ->  available (0,3,0,1) + (3,1,2,1) = (3,4,2,2)
T2 runs  ->  needs (1,0,0,1), fits  ->  (3,4,2,2) + (2,2,1,0) = (5,6,3,2)
T4 runs  ->  needs (4,1,0,2), fits  ->  (5,6,3,2) + (0,5,1,0) = (5,11,4,2)
now stuck: T1 needs R4 = 3, T5 needs R4 = 3, only 2 are free

So three threads finish and then T1 and T5 sit there forever, each waiting on an R4 that only the other one could release. That is the definition of an unsafe state, and it is why your classmates named T1 and T5 specifically.

The reason R4 is so tight is worth seeing. There are only 8 R4 in the whole system, 1 free plus 7 already handed out. T1 and T5 between them still want 6 more, and the three threads that can finish only give back 1 of them. I also had a program try all 120 possible orderings of the five threads, and not a single one gets all five to finish. So (a) is unsafe no matter what order the scheduler picks, which is a stronger statement than just finding one order that fails.

Part (b), Available = (1, 0, 0, 2), is safe:

T2 runs  ->  needs (1,0,0,1), fits  ->  (1,0,0,2) + (2,2,1,0) = (3,2,1,2)
T3 runs  ->  needs (0,2,0,0), fits  ->  (3,2,1,2) + (3,1,2,1) = (6,3,3,3)
T1 runs  ->  needs (0,1,0,3), fits  ->  (6,3,3,3) + (3,0,1,4) = (9,3,4,7)
T4 runs  ->  needs (4,1,0,2), fits  ->  (9,3,4,7) + (0,5,1,0) = (9,8,5,7)
T5 runs  ->  needs (2,1,1,3), fits  ->  all five complete

Notice the one extra R4 is what makes the difference. It lets T2 go first, and once T2 and T3 both release, R4 climbs to 3 and T1 finally fits. Out of the 120 orderings, 6 of them work and every one of those begins T2 then T3, so that opening is forced.

If you want to check work like this quickly, the whole safety test is about fifteen lines:

bool fits(const int need[], const int work[], int m) {
    for (int i = 0; i < m; i++)
        if (need[i] > work[i]) return false;   // one column is enough to fail
    return true;
}

// repeatedly scan for any unfinished thread that fits,
// run it, add its allocation back into work, repeat.
// if you get through all n threads the state is safe.

That inner loop is the part worth remembering, because it is the same mistake in code form: you have to check every resource column before you let a thread through.