银行家算法简易实现

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。

相关文章

C++使用栈实现括号匹配的代码详解

C++使用栈实现括号匹配的代码详解

《C++使用栈实现括号匹配的代码详解》在编程中,括号匹配是一个常见问题,尤其是在处理数学表达式、编译器解析等任务时,栈是一种非常适合处理此类问题的数据结构,能够精确地管理括号的匹配问题,本文将通过C+... 目录引言问题描述代码讲解代码解析栈的状态表示测试总结引言在编程中，括号匹配是一个常见问题，尤其是在
阅读更多...
Java实现检查多个时间段是否有重合

Java实现检查多个时间段是否有重合

《Java实现检查多个时间段是否有重合》这篇文章主要为大家详细介绍了如何使用Java实现检查多个时间段是否有重合,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录流程概述步骤详解China编程步骤1：定义时间段类步骤2：添加时间段步骤3：检查时间段是否有重合步骤4：输出结果示例代码结语作
阅读更多...
使用C++实现链表元素的反转

使用C++实现链表元素的反转

《使用C++实现链表元素的反转》反转链表是链表操作中一个经典的问题,也是面试中常见的考题,本文将从思路到实现一步步地讲解如何实现链表的反转,帮助初学者理解这一操作,我们将使用C++代码演示具体实现,同... 目录问题定义思路分析代码实现带头节点的链表代码讲解其他实现方式时间和空间复杂度分析总结问题定义给定
阅读更多...
Java覆盖第三方jar包中的某一个类的实现方法

Java覆盖第三方jar包中的某一个类的实现方法

《Java覆盖第三方jar包中的某一个类的实现方法》在我们日常的开发中,经常需要使用第三方的jar包,有时候我们会发现第三方的jar包中的某一个类有问题,或者我们需要定制化修改其中的逻辑,那么应该如何... 目录一、需求描述二、示例描述三、操作步骤四、验证结果五、实现原理一、需求描述需求描述如下：需要在
阅读更多...
如何使用Java实现请求deepseek

如何使用Java实现请求deepseek

《如何使用Java实现请求deepseek》这篇文章主要为大家详细介绍了如何使用Java实现请求deepseek功能,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录1.deepseek的api创建2.Java实现请求deepseek2.1 pom文件2.2 json转化文件2.2
阅读更多...
python使用fastapi实现多语言国际化的操作指南

python使用fastapi实现多语言国际化的操作指南

《python使用fastapi实现多语言国际化的操作指南》本文介绍了使用Python和FastAPI实现多语言国际化的操作指南,包括多语言架构技术栈、翻译管理、前端本地化、语言切换机制以及常见陷阱和... 目录多语言国际化实现指南项目多语言架构技术栈目录结构翻译工作流1. 翻译数据存储2. 翻译生成脚本
阅读更多...
如何通过Python实现一个消息队列

如何通过Python实现一个消息队列

《如何通过Python实现一个消息队列》这篇文章主要为大家详细介绍了如何通过Python实现一个简单的消息队列,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录如何通过 python 实现消息队列如何把 http 请求放在队列中执行1. 使用 queue.Queue 和 reque
阅读更多...
Python如何实现PDF隐私信息检测

Python如何实现PDF隐私信息检测

《Python如何实现PDF隐私信息检测》随着越来越多的个人信息以电子形式存储和传输,确保这些信息的安全至关重要,本文将介绍如何使用Python检测PDF文件中的隐私信息,需要的可以参考下... 目录项目背景技术栈代码解析功能说明运行结php果在当今，数据隐私保护变得尤为重要。随着越来越多的个人信息以电子形
阅读更多...
使用 sql-research-assistant进行 SQL 数据库研究的实战指南(代码实现演示)

使用 sql-research-assistant进行 SQL 数据库研究的实战指南(代码实现演示)

《使用sql-research-assistant进行SQL数据库研究的实战指南(代码实现演示)》本文介绍了sql-research-assistant工具,该工具基于LangChain框架,集... 目录技术背景介绍核心原理解析代码实现演示安装和配置项目集成LangSmith 配置（可选）启动服务应用场景
阅读更多...
使用Python快速实现链接转word文档

使用Python快速实现链接转word文档

《使用Python快速实现链接转word文档》这篇文章主要为大家详细介绍了如何使用Python快速实现链接转word文档功能,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 演示代码展示from newspaper import Articlefrom docx import
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2