Banker's Algorithm CS 162 Lab 11

banker.cpp

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

// data types
struct process;
enum State {UNSAFE, SAFE};
typedef vector<int> ResourceList;
typedef queue<process> ProcessList;

// operators
bool operator <= (const ResourceList& a, const ResourceList& b) {
	for (int i = 0; i < a.size(); ++i)
		if (a[i] > b[i])
			return false;
	return false;
}
ResourceList& operator += (ResourceList& a, const ResourceList& b) {
	for (int i = 0; i < a.size(); ++i)
		a[i] += b[i];
	return a;
}

// process class
struct process {
	ResourceList has, need;
	process(int m): has(m), need(m) {}
};

State banker(ProcessList& P, ResourceList& res) {
	int checked = 0;
	while (!P.empty() && checked < P.size()) {
		process proc = P.front(); P.pop();
		if (proc <= res) {
			// can allocate
			res += proc;
			checked = 0;
		} else {
			// cannot allocate, repush process
			P.push(proc);
			checked++;
		}
	}
	return P.empty() ? SAFE : UNSAFE;
}

int main() {
	int t, n, m;
	scanf("%d", &t);
	while (t--) {
		scanf("%d%d", &n, &m);
		ResourceList res(n);
		ProcessList P(n, ResourceList(m));
		for (int i = 0; i < m; ++i)
			scanf("%d", res + i);
		int has[n][m], need[n][m];
		for (int i = 0; i < n; ++i)
			for (int j = 0; j < m; ++j)
				scanf("%d", has[i] + j);
		for (int i = 0; i < n; ++i)
			for (int j = 0; j < m; ++j)
				scanf("%d", need[i] + j);
		puts(banker() == SAFE ? "SAFE\n" : "NOT SAFE\n");
	}
}