Banker's Algorithm 银行家算法的简单实现

banker.cc

#include <cstring>
#include <iostream>
#include <set>
using namespace std;
/**
 * Banker's Algorithm by Dijkstra
 *
 * @author LeeR
 */
/*
test input:
3 5
10 5 7
0 1 0
2 0 0
3 0 2
2 1 1
0 0 2
7 5 3
3 2 2
9 0 2
2 2 2
4 3 3
1
1 0 2
4
3 3 0
0
0 2 0
*/
const int MAX_RESOURCE = 10;
int RESOURCE_NUM, THREAD_NUM;

bool print_sequence(int *a, int size) {
  for (int i = 0; i < size; i++) {
    if (i != 0) printf(" ");
    printf("%d", *(a + i));
  }
  printf("\n");
}

/** Wether current state is safe.
 * return true if safe, else return false.
 * if return true, the safe_seq will be filled with the sequence that thread
 * process
 */
bool is_safe(int *available, int need[][MAX_RESOURCE],
             int alloction[][MAX_RESOURCE], int *safe_seq) {
  int work[RESOURCE_NUM];
  memcpy(work, available, sizeof(int) * RESOURCE_NUM);

  set<int> rest;
  set<int>::iterator it;

  for (int i = 0; i < THREAD_NUM; i++) {
    rest.insert(i);
  }

  int size = 0;
  while (rest.size() != 0) {
    // find a thread that its need < available
    int id = -1;
    bool no_possible = true;

    for (it = rest.begin(); it != rest.end(); it++) {
      bool ok = true;
      for (int j = 0; j < RESOURCE_NUM; j++) {
        if (need[*it][j] > work[j]) {
          ok = false;
          // break inner loop
          j = RESOURCE_NUM;
        }
      }
      if (ok) {
        no_possible = false;
        id = *it;
        safe_seq[size++] = id;
        // remove from set
        rest.erase(it);
        for (int k = 0; k < RESOURCE_NUM; k++) {
          // assume we release this thread's resource
          work[k] += alloction[*it][k];
        }
        break;
      }
    }
    // no thread satisfied, stop search
    if (no_possible) break;
  }
  return rest.size() == 0;
}

int main() {
  cin >> RESOURCE_NUM >> THREAD_NUM;
  int resource[MAX_RESOURCE], available[MAX_RESOURCE];
  int allocation[THREAD_NUM][MAX_RESOURCE];
  int claim[THREAD_NUM][MAX_RESOURCE], need[THREAD_NUM][MAX_RESOURCE];

  for (int i = 0; i < RESOURCE_NUM; i++) scanf("%d", &resource[i]);

  // input alloction table
  for (int i = 0; i < THREAD_NUM; i++)
    for (int j = 0; j < RESOURCE_NUM; j++) scanf("%d", &allocation[i][j]);

  // input claim table
  for (int i = 0; i < THREAD_NUM; i++)
    for (int j = 0; j < RESOURCE_NUM; j++) scanf("%d", &claim[i][j]);

  int all_alloced[RESOURCE_NUM] = {0};
  // calculate need table
  for (int i = 0; i < THREAD_NUM; i++)
    for (int j = 0; j < RESOURCE_NUM; j++) {
      all_alloced[j] += allocation[i][j];
      need[i][j] = claim[i][j] - allocation[i][j];
    }

  // calculate available table
  for (int j = 0; j < RESOURCE_NUM; j++)
    available[j] = resource[j] - all_alloced[j];

  int safe_sequence[THREAD_NUM];

  if (is_safe(available, need, allocation, safe_sequence)) {
    printf("state is safe, the safe squence is:\n");
    print_sequence(safe_sequence, THREAD_NUM);
    printf("now available:\n");
    print_sequence(available, RESOURCE_NUM);
  } else {
    printf("state not safe, exiting...");
    exit(1);
  }

  int thread_id;
  int request[RESOURCE_NUM];
  // input request thread id, index start from 0
  while (scanf("%d", &thread_id) == 1) {
    // input request
    bool overflow = false;
    for (int i = 0; i < RESOURCE_NUM; i++) {
      scanf("%d", &request[i]);
      if (request[i] > need[thread_id][i] || request[i] > available[i]) {
        overflow = true;
        printf("request rejected: request too much resource\n");
      }
    }
    if (overflow) continue;

    // try to satisfy request
    for (int i = 0; i < RESOURCE_NUM; i++) {
      allocation[thread_id][i] += request[i];
      available[i] -= request[i];
      need[thread_id][i] -= request[i];
    }
    printf("try to satisfy request, now available:\n");
    print_sequence(available, RESOURCE_NUM);
    if (is_safe(available, need, allocation, safe_sequence)) {
      printf("request accepted\n");
    } else {
      printf("request rejected: state not safe\n");
      // restore previous state
      for (int i = 0; i < RESOURCE_NUM; i++) {
        allocation[thread_id][i] -= request[i];
        available[i] += request[i];
        need[thread_id][i] += request[i];
      }
    }
  }
  return 0;
}