Created
December 31, 2018 08:53
-
-
Save LeeReindeer/a0a78d29d2940dd5a958da67f0db30e8 to your computer and use it in GitHub Desktop.
Banker's Algorithm 银行家算法的简单实现
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment