银行家算法简易实现

2024-05-12 00:20
文章标签 算法 实现 简易 银行家

本文主要是介绍银行家算法简易实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这里写目录标题

  • 实验要求
  • 内容
  • 代码
    • main.cpp
    • myfunc.h
    • myfunc.cpp
  • 运行结果与分析

实验要求

程序可以针对不同进程的请求进行判断，并决定是否满足其需求。算法程序需要设计合理的数据结构，对资源情况、进程相关数据进行存储。

内容

随机生成数据, 并校验数据是否会产生死锁问题

实现银行家算法的核心: 安全性算法, 银行家算法的请求判断

打印每个线程的合法请求向量序列

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

代码

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]
.....
此后程序阻塞...

这篇关于银行家算法简易实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/981073。

相关文章

不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

利用康拓展开将一个排列映射成一个自然数，然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
【C++】_list常用方法解析及模拟实现

【C++】_list常用方法解析及模拟实现

相信自己的力量，只要对自己始终保持信心，尽自己最大努力去完成任何事，就算事情最终结果是失败了，努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一：什么是list？ •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二：list常用接口 •🌰1.默认成员函数 🔥构造函数（⭐） 🔥析构函数 •🌰2.list对象
阅读更多...
【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯，先赞后看哦~🎈🎈 🏆 作者简介：景天科技苑 🏆《头衔》：大厂架构师，华为云开发者社区专家博主，阿里云开发者社区专家博主，CSDN全栈领域优质创作者，掘金优秀博主，51CTO博客专家等。 🏆《博客》：Python全栈，前后端开发，小程序开发，人工智能，js逆向，App逆向，网络系统安全，数据分析，Django，fastapi
阅读更多...
让树莓派智能语音助手实现定时提醒功能

让树莓派智能语音助手实现定时提醒功能

最初的时候是想直接在rasa 的chatbot上实现，因为rasa本身是带有remindschedule模块的。不过经过一番折腾后，忽然发现，chatbot上实现的定时，语音助手不一定会有响应。因为，我目前语音助手的代码设置了长时间无应答会结束对话，这样一来，chatbot定时提醒的触发就不会被语音助手获悉。那怎么让语音助手也具有定时提醒功能呢？ 我最后选择的方法是用threading.Time
阅读更多...
Android实现任意版本设置默认的锁屏壁纸和桌面壁纸（两张壁纸可不一致）

Android实现任意版本设置默认的锁屏壁纸和桌面壁纸（两张壁纸可不一致）

客户有些需求需要设置默认壁纸和锁屏壁纸  在默认情况下 这两个壁纸是相同的  如果需要默认的锁屏壁纸和桌面壁纸不一样 需要额外修改 Android13实现 替换默认桌面壁纸： 将图片文件替换frameworks/base/core/res/res/drawable-nodpi/default_wallpaper.*  （注意不能是bmp格式） 替换默认锁屏壁纸： 将图片资源放入vendo
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2