银行家算法简易实现

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。

相关文章

Python使用Tenacity一行代码实现自动重试详解

Python使用Tenacity一行代码实现自动重试详解

《Python使用Tenacity一行代码实现自动重试详解》tenacity是一个专为Python设计的通用重试库,它的核心理念就是用简单、清晰的方式,为任何可能失败的操作添加重试能力,下面我们就来看... 目录一切始于一个简单的 API 调用Tenacity 入门：一行代码实现优雅重试精细控制：让重试按我
阅读更多...
Redis客户端连接机制的实现方案

Redis客户端连接机制的实现方案

《Redis客户端连接机制的实现方案》本文主要介绍了Redis客户端连接机制的实现方案,包括事件驱动模型、非阻塞I/O处理、连接池应用及配置优化,具有一定的参考价值,感兴趣的可以了解一下... 目录1. Redis连接模型概述2. 连接建立过程详解2.1 连php接初始化流程2.2 关键配置参数3. 最大连
阅读更多...
Python实现网格交易策略的过程

Python实现网格交易策略的过程

《Python实现网格交易策略的过程》本文讲解Python网格交易策略,利用ccxt获取加密货币数据及backtrader回测,通过设定网格节点,低买高卖获利,适合震荡行情,下面跟我一起看看我们的第一... 网格交易是一种经典的量化交易策略，其核心思想是在价格上下预设多个“网格”，当价格触发特定网格时执行买
阅读更多...
python设置环境变量路径实现过程

python设置环境变量路径实现过程

《python设置环境变量路径实现过程》本文介绍设置Python路径的多种方法：临时设置（Windows用`set`,Linux/macOS用`export`）、永久设置（系统属性或shell配置文件... 目录设置python路径的方法临时设置环境变量（适用于当前会话）永久设置环境变量（Windows系统
阅读更多...
Python对接支付宝支付之使用AliPay实现的详细操作指南

Python对接支付宝支付之使用AliPay实现的详细操作指南

《Python对接支付宝支付之使用AliPay实现的详细操作指南》支付宝没有提供PythonSDK,但是强大的github就有提供python-alipay-sdk,封装里很多复杂操作,使用这个我们就... 目录一、引言二、准备工作2.1 支付宝开放平台入驻与应用创建2.2 密钥生成与配置2.3 安装ali
阅读更多...
Spring Security 单点登录与自动登录机制的实现原理

Spring Security 单点登录与自动登录机制的实现原理

《SpringSecurity单点登录与自动登录机制的实现原理》本文探讨SpringSecurity实现单点登录（SSO）与自动登录机制,涵盖JWT跨系统认证、RememberMe持久化Token... 目录一、核心概念解析1.1 单点登录（SSO）1.2 自动登录（Remember Me）二、代码分析三、
阅读更多...
PyCharm中配置PyQt的实现步骤

PyCharm中配置PyQt的实现步骤

《PyCharm中配置PyQt的实现步骤》PyCharm是JetBrains推出的一款强大的PythonIDE,结合PyQt可以进行pythion高效开发桌面GUI应用程序,本文就来介绍一下PyCha... 目录1. 安装China编程PyQt1.PyQt 核心组件2. 基础 PyQt 应用程序结构3. 使用 Q
阅读更多...
Python实现批量提取BLF文件时间戳

Python实现批量提取BLF文件时间戳

《Python实现批量提取BLF文件时间戳》BLF（BinaryLoggingFormat）作为Vector公司推出的CAN总线数据记录格式,被广泛用于存储车辆通信数据,本文将使用Python轻松提取... 目录一、为什么需要批量处理 BLF 文件二、核心代码解析：从文件遍历到数据导出1. 环境准备与依赖库
阅读更多...
linux下shell脚本启动jar包实现过程

linux下shell脚本启动jar包实现过程

《linux下shell脚本启动jar包实现过程》确保APP_NAME和LOG_FILE位于目录内,首次启动前需手动创建log文件夹,否则报错,此为个人经验,供参考,欢迎支持脚本之家... 目录linux下shell脚本启动jar包样例1样例2总结linux下shell脚本启动jar包样例1#!/bin
阅读更多...
go动态限制并发数量的实现示例

go动态限制并发数量的实现示例

《go动态限制并发数量的实现示例》本文主要介绍了Go并发控制方法,通过带缓冲通道和第三方库实现并发数量限制,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面... 目录带有缓冲大小的通道使用第三方库其他控制并发的方法因为go从语言层面支持并发，所以面试百分百会问到
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2