實驗要求

程序可以針對不同進程的請求進行判斷，并決定是否滿足其需求。算法程序需要設計合理的數據結構，對資源情況、進程相關數據進行存儲。

內容

隨機生成數據, 并校驗數據是否會產生死鎖問題

實現銀行家算法的核心: 安全性算法, 銀行家算法的請求判斷

打印每個線程的合法請求向量序列

打印銀行家算法一次接受的請求向量序列

代碼

main.cpp

#include <iostream>
#include <pthread.h>
#include <stdlib.h>
#include <unistd.h>
#include <assert.h>
#include <stdbool.h>
#include <set>
#include <vector>
#include "myfunc.h"// 5 個進程, 3類資源
#define NUM_RESOURCES 3
#define NUM_PROCESSES 5
#define MAX_RES_NUM 10#define Lock(x) pthread_mutex_lock(x)
#define UnLock(x) pthread_mutex_unlock(x)// 因為只有一個資源分配處理器, 所以各線程需要互斥地申請資源
pthread_mutex_t mutex;
// 銀行家算法需要用到的數據結構
std::vector<int> available(NUM_RESOURCES);
std::vector<std::vector<int>>maximum(NUM_PROCESSES, std::vector<int>(NUM_RESOURCES));
std::vector<std::vector<int>>need(NUM_PROCESSES, std::vector<int>(NUM_RESOURCES));
std::vector<std::vector<int>>allocation(NUM_PROCESSES, std::vector<int>(NUM_RESOURCES));
/*** 初始化可用資源
*/
void init_resources() {for (int i = 0; i < NUM_RESOURCES; i++) {// [0, MAX_RES_NUM]available[i] = rand() % MAX_RES_NUM + 1;}
}
/*** 初始化每個線程對每個資源的最大需求, 不超過available* (雖然本人絕對這個maximum和need沒多大區別)
*/
void init_maximum() {for (int i = 0; i < NUM_PROCESSES; i++) {for (int j = 0; j < NUM_RESOURCES; j++) {// [0, available[j]]maximum[i][j] = rand() % (available[j] + 1);}}
}/*** 初始化分配矩陣* 初值為0 
*/ 
void init_allocation() {for (int i = 0; i < NUM_PROCESSES; i++) {for (int j = 0; j < NUM_RESOURCES; j++) {allocation[i][j] = 0;}}
}// 初始化需求矩陣
void init_need() {for (int i = 0; i < NUM_PROCESSES; i++) {for (int j = 0; j < NUM_RESOURCES; j++) {need[i][j] = maximum[i][j] - allocation[i][j];}}
}/*** 安全性算法:* 在某時刻, 查看當前可用資源向量面對, need矩陣是否處于安全狀態* 即是否可以找到一個安全序列, 安全序列并不是唯一的, * 能找出一個安全序列即可證明當前的available處于安全狀態
*/
std::vector<int> process_ids(NUM_PROCESSES);
bool check_safe() {// work是當前可分配的資源向量std::vector<int> work(available);// 保存安全序列(有必要可以打印調試)std::vector<int> safe_seq;std::set<int> pids(process_ids.begin(), process_ids.end());for (int i = 0; i < process_ids.size(); i++) {// 檢查need矩陣的每一行, 如果該行對應的需求向量 <= workfor (auto pid : pids) {if (need[pid] <= work) {safe_seq.push_back(pid);work += allocation[pid];pids.erase(pid);break;}}}// 如果能找到一個包含所有線程的安全序列if (safe_seq.size() == process_ids.size()) {return true;}return false;
}
// path保存每個線程的請求向量
std::vector<std::vector<std::vector<int>>> path(NUM_PROCESSES);
// schedule保存處理器調度請求向量的順序和對應的線程編號
std::vector<std::pair<int, std::vector<int>>> schedule;
/*** 向處理器發起資源分配請求* 利用銀行家算法處理請求與分配
*/
void* request_banker(void *arg) {int process_id = *((int *)arg);while (true) {Lock(&mutex);// 隨機為當前進程構造請求向量std::vector<int> request(NUM_RESOURCES);for (int i = 0; i < NUM_RESOURCES; i++) {request[i] = rand() % (need[process_id][i] + 1);}// 請求的資源 > 當前剩余的資源, // 則讓出cpu, 重新生成一個合理的reqif (request > available) {UnLock(&mutex);continue;}// 如果隨機生成的req=0, 則重新生成if (request == std::vector<int>(NUM_RESOURCES, 0)) {UnLock(&mutex);continue;}// 給當前線程分配資源for (int i = 0; i < NUM_RESOURCES; i++) {available[i] -= request[i];allocation[process_id][i] += request[i];need[process_id][i] -= request[i];}// 如果給當前進程分配了它所請求的資源// 但是進入了不安全的狀態, 則撤銷此次分配資源if (!check_safe()) {for (int i = 0; i < NUM_RESOURCES; i++) {available[i] += request[i];allocation[process_id][i] -= request[i];need[process_id][i] += request[i];}// 如果該請求向量, 會使得當前狀態進入不安全的狀態// 則該請求非法, 讓其它線程請求printf("Process %d is Waiting\n", process_id);print_vector(need[process_id]);UnLock(&mutex);continue;} // 調試信息保存path[process_id].push_back(request);schedule.push_back(std::make_pair(process_id, request));if (need[process_id] == std::vector<int>(NUM_RESOURCES, 0)) {printf("Process %d have completed.\n", process_id);// 一個線程完成他的操作后要釋放占用的資源????available += allocation[process_id];for (auto p : path[process_id]) {print_vector(p);}UnLock(&mutex);// break使得該線程結束break;} UnLock(&mutex);}
}
/*** 檢查是否滿足銀行家算法的先決條件* 假設有n個線程, m種資源, 每種資源k[i](i=0, ..., m-1)個* 使得不產生死鎖的充分條件為: 每種資源的總需求和 <= n + m[i] - 1* 即滿足該條件一定不會發生死鎖, 但是不滿足只是可能會產生死鎖* 這里所謂死鎖為: * 當前未完成的線程集合中的任意一個線程的任意一個請求都不能被銀行家算法接受* 從而導致每個線程都在持續的做無用的請求* 例如: 當前有n=3個線程, m=1種資源, 數量為3* 每個線程的需求need如下*   alloc need avail* A:  0    1    3* B:  0    1* C:  0    4* 線程A最多請求1個資源, 如果滿足線程A, 則剩余2個資源, 不能滿足其余的線程, 進入不安全狀態, 拒絕此請求* 線程B最多請求1個資源, 如果滿足線程B, 則剩余2個資源, 不能滿足其余的線程, 進入不安全狀態, 拒絕此請求* 線程C最少請求一個資源, 如果滿足線程C, 則剩余2個資源, * 如果接受C的下限請求, 下一個狀態也為不安全狀態*   alloc need avail* A:  0    1    2* B:  0    1* C:  1    3* 最終會不會發生死鎖, 取決于調度, 如果敲好串行的調度這些線程的請求, * 則肯定不會發生死鎖, 否則有可能發生
*/
bool check_prerequisite() {std::vector<int> colsum(NUM_RESOURCES);for (int i = 0; i < NUM_PROCESSES; i++) {int rowsum = 0;for (int j = 0; j < NUM_RESOURCES; j++) {if (maximum[i] == std::vector<int>(NUM_PROCESSES, 0)) {return false;}colsum[j] += maximum[i][j];rowsum += maximum[i][j];}if (rowsum == 0) return false;}for (int i = 0; i < NUM_RESOURCES; i++) {if (NUM_PROCESSES + available[i] - 1 > colsum[i]) {return false;}}return true;
}
void init() {init_resources();init_maximum();init_allocation();init_need();
}int main() {std::vector<pthread_t> threads(NUM_PROCESSES);srand(time(NULL));// 初始化互斥鎖pthread_mutex_init(&mutex, nullptr);// 隨機生成可用資源// 直到生成的數據不會發生死鎖init_resources();printf("prerequisite[] => ");for (int i = 0; i < NUM_RESOURCES; i++) {printf("%d ", NUM_PROCESSES + available[i]);}printf("\n");// 保證生成的數據不會有死鎖問題do {init_maximum();} while (check_prerequisite());init_allocation();init_need();printf("available[] => ");print_vector(available);printf("need[][] => \n");for (int i = 0; i < NUM_PROCESSES; i++) {print_vector(need[i]);}// 創建進程線程for (int i = 0; i < NUM_PROCESSES; i++) {process_ids[i] = i;pthread_create(&threads[i], nullptr, request_banker, &process_ids[i]);}// 等待所有線程結束for (int i = 0; i < NUM_PROCESSES; i++) {pthread_join(threads[i], nullptr);}printf("A safe cpu schedule: \n");for (auto [pid, req] : schedule) {printf("Process %d : ", pid);print_vector(req);}// 銷毀互斥鎖pthread_mutex_destroy(&mutex);return 0;
}

myfunc.h

#ifndef MYFUNC_H
#define MYFUNC_H#include <vector>
#include <stdio.h>
// 聲明一個函數，用于比較兩個 vector<int> 是否相等
void print_vector(std::vector<int> v);
bool operator==(const std::vector<int>& v1, const std::vector<int>& v2);
bool operator<=(const std::vector<int>& v1, const std::vector<int>& v2);
bool operator<(const std::vector<int>& v1, const std::vector<int>& v2);
bool operator>(const std::vector<int>& v1, const std::vector<int>& v2);
std::vector<int>& operator+=(std::vector<int>& v1, const std::vector<int>& v2);
std::vector<int>& operator-=(std::vector<int>& v1, const std::vector<int>& v2);
std::vector<int> operator+(const std::vector<int>& v1, const std::vector<int>& v2);
#endif

myfunc.cpp

#include "myfunc.h"
void print_vector(std::vector<int> v) {if (v.empty()) return;printf("[");for (int i = 0; i < v.size(); i++) {if (i != v.size() - 1) {printf("%d, ", v[i]);} else {printf("%d]\n", v[i]);}}
}
bool operator==(const std::vector<int>& v1, const std::vector<int>& v2) {// 檢查向量的大小是否相等if (v1.size() != v2.size()) {return false;}// 逐個比較向量的元素for (std::size_t i = 0; i < v1.size(); ++i) {if (v1[i] != v2[i]) {return false;}}return true;
}
bool operator<=(const std::vector<int>& v1, const std::vector<int>& v2) {// 檢查向量的大小是否相等if (v1.size() != v2.size()) {return false;}// 逐個比較向量的元素for (std::size_t i = 0; i < v1.size(); ++i) {if (v1[i] > v2[i]) {return false;}}return true;
}
bool operator>(const std::vector<int>& v1, const std::vector<int>& v2) {return !(v1 <=v2);
}
bool operator<(const std::vector<int>& v1, const std::vector<int>& v2) {// 檢查向量的大小是否相等if (v1.size() != v2.size()) {return false;}// 逐個比較向量的元素for (std::size_t i = 0; i < v1.size(); ++i) {if (v1[i] >= v2[i]) {return false;}}return true;
}
std::vector<int>& operator+=(std::vector<int>& v1, const std::vector<int>& v2) {if (v1.size() != v2.size()) {throw nullptr;}for (std::size_t i = 0; i < v1.size(); ++i) {v1[i] += v2[i];}return v1;
}
std::vector<int>& operator-=(std::vector<int>& v1, const std::vector<int>& v2) {if (v1.size() != v2.size()) {throw nullptr;}for (std::size_t i = 0; i < v1.size(); ++i) {v1[i] -= v2[i];}return v1;
}
std::vector<int> operator+(const std::vector<int>& v1, const std::vector<int>& v2) {if (v1.size() != v2.size()) {return std::vector<int>();}std::vector<int> result;result.reserve(v1.size());for (std::size_t i = 0; i < v1.size(); ++i) {result.push_back(v1[i] + v2[i]);}return result;
}

運行結果與分析

保證沒有死鎖的數據, 運行結果

available[] => [2, 7, 1]
need[][] =>
[0, 3, 1]
[1, 3, 0]
[0, 0, 1]
[0, 5, 1]
[1, 0, 1]
Process 0 have completed.
[0, 3, 0]
[0, 0, 1]
Process 1 have completed.
[1, 3, 0]
Process 2 have completed.
[0, 0, 1]
Process 4 have completed.
[1, 0, 0]
[0, 0, 1]
Process 3 have completed.
[0, 5, 0]
[0, 0, 1]
A safe cpu schedule: 
Process 0 : [0, 3, 0]
Process 0 : [0, 0, 1]
Process 1 : [1, 3, 0]
Process 2 : [0, 0, 1]
Process 4 : [1, 0, 0]
Process 4 : [0, 0, 1]
Process 3 : [0, 5, 0]
Process 3 : [0, 0, 1]

修改程序片段為

do {init_maximum();} while (!check_prerequisite());

生成可能會產生死鎖的數據, 但是沒有調度出死鎖的情況

available[] => [9, 8, 7]
need[][] =>
[2, 3, 6]
[6, 2, 2]
[7, 7, 2]
[4, 0, 0]
[2, 5, 7]
Process 0 is Waiting
[2, 3, 6]
Process 0 have completed.
[1, 1, 2]
[0, 0, 2]
[0, 2, 2]
[1, 0, 0]
Process 1 have completed.
[6, 2, 1]
[0, 0, 1]
Process 3 have completed.
[1, 0, 0]
[2, 0, 0]
[1, 0, 0]
Process 4 have completed.
[2, 5, 6]
[0, 0, 1]
Process 2 have completed.
[1, 3, 1]
[5, 4, 0]
[0, 0, 1]
[1, 0, 0]
A safe cpu schedule:
Process 0 : [1, 1, 2]
Process 0 : [0, 0, 2]
Process 0 : [0, 2, 2]
Process 0 : [1, 0, 0]
Process 1 : [6, 2, 1]
Process 1 : [0, 0, 1]
Process 3 : [1, 0, 0]
Process 3 : [2, 0, 0]
Process 3 : [1, 0, 0]
Process 4 : [2, 5, 6]
Process 4 : [0, 0, 1]
Process 2 : [1, 3, 1]
Process 2 : [5, 4, 0]
Process 2 : [0, 0, 1]
Process 2 : [1, 0, 0]

生成可能會產生死鎖的數據, 調度出死鎖的情況

available[] => [10, 6, 8]
need[][] => 
[2, 0, 5]
[4, 6, 3]
[6, 2, 1]
[5, 3, 2]
[4, 4, 8]
Process 0 is Waiting
[2, 0, 5]
Process 4 is Waiting
[4, 4, 8]
Process 4 is Waiting
[2, 4, 8]
Process 0 have completed.
[1, 0, 4]
[0, 0, 1]
[1, 0, 0]
.....
此后程序阻塞...