CSE Roadmap

Common tier · about 5 hours · 7 parts

Part 6 of 7 · 5 min read

Code and cost

The algorithm in C, and its limits

In plain words: The safety algorithm is short in C. This version stores the tables in global arrays, and it returns 1 and fills seq if the state is safe:

#define N 4
#define M 2
int total[M] = {10, 6};
int alloc[N][M] = {{2,1},{3,2},{2,1},{1,0}};
int maxc[N][M]  = {{6,3},{5,3},{4,2},{3,3}};

int is_safe(int seq[]) {
  int work[M], done[N] = {0}, count = 0;
  for (int j = 0; j < M; j++) {
    work[j] = total[j];
    for (int i = 0; i < N; i++) work[j] -= alloc[i][j];     /* Available */
  }
  while (count < N) {
    int found = 0;
    for (int i = 0; i < N && !found; i++) {
      if (done[i]) continue;
      int ok = 1;
      for (int j = 0; j < M; j++) if (maxc[i][j] - alloc[i][j] > work[j]) ok = 0;
      if (!ok) continue;
      for (int j = 0; j < M; j++) work[j] += alloc[i][j];    /* thread i finishes */
      done[i] = 1; seq[count++] = i; found = 1;
    }
    if (!found) return 0;                                    /* nobody can finish */
  }
  return 1;
}

The request function adds the request to alloc, calls is_safe, and subtracts the request again if the result is 0. Running six requests on the original state printed:

start: safe, sequence T1 T0 T2 T3
T1 asks (1,0): granted (state stays safe)
T3 asks (1,0): refused: would be unsafe, thread waits
T0 asks (1,1): refused: would be unsafe, thread waits
T2 asks (2,0): granted (state stays safe)
T3 asks (0,1): granted (state stays safe)
T2 asks (1,1): granted (state stays safe)

(The program prints T0 to T3 for the threads that this page calls P0 to P3, counting from 0.) The results equal the table of section 4.

The cost is the loop count. Each safety check looks at up to n threads, n times over, and compares m numbers each time. OSC gives this as an order of m × n² operations. For 4 threads and 2 types, that is about 32 steps, which is nothing. For thousands of threads or locks, running it at every request would cost too much.

The deeper limits are about the information:

  • Every thread must know its maximum claim in advance. A program rarely does.
  • The number of threads must be fixed, but threads appear and exit all the time.
  • Resources must not vanish: a tape drive or a network link that fails breaks the safety argument.

MOS says that for these reasons the algorithm is useful in theory but almost never used in general systems. The idea survives in smaller forms: reserving all the memory or connections a job will need before it starts, refusing new work when a pool is nearly full, and sizing a pool so that waiting jobs cannot hold every slot. These are admission rules in the spirit of avoidance.

Maximum claim

A maximum claim is the largest number of units of a resource type that a thread declares it may hold at one time; the banker's algorithm refuses any request that would take the thread above it.

Example: a thread with a maximum claim of 3 database connections that asks for a fourth is refused, whatever is free.

Interview angle

"What is the banker's algorithm, and why is it not used much?" Say that it avoids deadlock by granting a request only if a safe sequence exists, that it needs maximum claims in advance, and that its cost grows quickly with the number of threads. Then say that the practical form of the idea is admission control: limit work before resources run out.

Check yourself: 1. What does is_safe return when no thread fits the work vector? 2. For n = 4 and m = 2, about how many steps does one safety check need? 3. Give one reason why a normal program cannot be run under the banker's algorithm.

Words you will meet

Word Meaning
Avoidance Granting a request only if the next state is safe
Maximum claim The most a thread says it will ever hold
Available The free units of each resource type
Need Max minus Allocation: what a thread may still ask for
Safe state A state with at least one safe sequence
Safe sequence An order in which every thread can finish
Unsafe state A state with no safe sequence; not necessarily a deadlock
Pretend grant Testing a request by changing the tables, then undoing the change

Quick notes

  • Deadlock avoidance is a method in which every thread declares its maximum claim in advance, and the system grants a request only if the state after the grant is safe.
  • A safe state is a state of the system in which there is some order of the threads, called a safe sequence, such that each thread can get all it.
  • The banker's algorithm is a deadlock-avoidance method that keeps the tables Available, Max, Allocation and Need, runs the safety algorithm on a pretended state, and grants a request only if that state is safe.
  • A pretend grant is the step in which the system changes its tables as if a request had been granted, tests the new state for safety, and keeps the change only if the state is safe.
  • A maximum claim is the largest number of units of a resource type that a thread declares it may hold at one time; the banker's algorithm refuses any request that would take the thread above it.