关于银行家调度算法预防死锁
本帖最后由 沉默的菜鸟 于 2019-5-17 23:03 编辑今天上机的实习题是实现银行家算法，上次有个老哥写了一个C语言版的银行家算法，我介绍一个C++版本的。（本人菜鸟，代码是自己原创的，未能很好的简化代码，如有错误麻烦指出，谢谢）
一、银行家算法与死锁
在银行中，客户申请贷款的数量是有限的，每个客户在第一次申请贷款时要声明完成该项目所需的最大资金量，在满足所有贷款要求时，客户应及时归还。银行家在客户申请的贷款数量不超过自己拥有的最大值时，都应尽量满足客户的需要。在这样的描述中，银行家就好比操作系统，资金就是资源，客户就相当于要申请资源的进程。
银行家算法是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次分配资源的安全性，若分配不会导致系统进入不安全状态，则分配，否则等待。为实现银行家算法，系统必须设置若干数据结构。
线程死锁是指由于两个或者多个线程互相持有对方所需要的资源，导致这些线程处于等待状态，无法前往执行。当线程进入对象的synchronized代码块时，便占有了资源，直到它退出该代码块或者调用wait方法，才释放资源，在此期间，其他线程将不能进入该代码块。当线程互相持有对方所需要的资源时，会互相等待对方释放资源，如果线程都不主动释放所占有的资源，将产生死锁
二、银行家算法的核心步骤
核心步骤就是检查序列是否是安全序列，若是安全序列这将调度顺序记录下来，否则返回死锁提示。
安全序列是指一个进程序列{P1，…，Pn}是安全的，即对于每一个进程Pi(1≤i≤n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j < i )当前占有资源量之和。
三、talk is cheap,show your code
// BankerAlgorithm.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#include "pch.h"
#include <iostream>
#include <array>
#include <queue>
#include <vector>
using namespace std;
struct Client
{
array<int, 4> own;
array<int, 4> need;
Client(array<int,4>a, array<int,4>b) //有参的构造函数
{
unsigned int i;
for (i=0;i<a.size();i++)
{
own = a;
need = b;
}
}
Client()
{
own.fill(0);
need.fill(0);
}
};
struct Resource
{
array<int, 4>my_resource;
Resource(array<int, 4>a) //带参数的构造函数
{
unsigned int i;
for (i = 0; i < my_resource.size(); i++)
{
my_resource = a;
}
}
Resource()//无参数的构造函数
{
my_resource.fill(0);
}
};
bool lower_than(array<int,4> a, array<int, 4>b)
{
return (a <= b && a <= b && a <= b && a <= b);
}
bool is_safe(Client *my_client, int nums, Resource remained_resources, queue<int>&dispatch_array)
{
vector<bool>finish(nums, false);
bool temp1 = true;
bool temp2 = false;
while (true)
{
for (int i = 0; i < nums; i++)
{
if (finish)
{
continue;
}
if (lower_than(my_client.need,remained_resources.my_resource))//剩余的资源大于某一进程需要的资源
{
finish = true;
dispatch_array.push(i);
for (unsigned int j = 0; j < my_client.own.size(); j++)
{
remained_resources.my_resource.at(j) += my_client.own.at(j);//回收资源
}
}
}
for (int i = 0; i < nums; i++)
{
temp1 = temp1 && finish;//全为true
temp2 = temp2 || finish;//全为false
}
if (temp1)
{
goto label;
}
if (!temp2)
{
temp1 = temp2;
goto label;
}
temp1 = true;
temp2 = false;
}
label: return temp1;
}
//调度函数
void dispatch(Client *my_client,int nums, Resource &all_resources, Resource &allocated_resources, Resource &remained_resources)
{
queue<int>dispatch_array;
if (!is_safe(my_client,nums,remained_resources,dispatch_array))
{
cout << "无法完成调度，系统加死锁！！！";
return;
}
cout << "所有资源总表为：";
for (unsigned int i = 0; i < all_resources.my_resource.size(); i++)
{
cout << all_resources.my_resource.at(i)<<" ";
}
cout << endl << endl;
cout << "未调度前已分配的资源总表为：";
for (unsigned int i = 0; i < allocated_resources.my_resource.size(); i++)
{
cout << allocated_resources.my_resource.at(i) << " ";
}
cout << endl << endl;
cout << "未调度前剩余资源总表为：";
for (unsigned int i = 0; i < remained_resources.my_resource.size(); i++)
{
cout << remained_resources.my_resource.at(i) << " ";
}
cout << endl << endl;
for (int i = 0; i < nums; i++)
{
cout << "第 " << i + 1 << " 次调度：" << endl;
cout << "当前各个进程所占资源的表为：" << endl;
for (int j = 0; j < nums; j++)
{
cout << "进程 " << j<<": ";
for (unsigned int k = 0; k < my_client.own.size(); k++)
{
cout << my_client.own.at(k)<<" ";
}
cout << endl;
}
int cur_dispatch_num = dispatch_array.front();//当前调度的进程号
dispatch_array.pop();
for (unsigned int k = 0; k < my_client.own.size(); k++)
{
remained_resources.my_resource.at(k) += my_client.own.at(k);
my_client.own.at(k) = 0;
}
cout << "调度完后各个资源剩余的表为：" << endl;
for (auto a:remained_resources.my_resource)
{
cout << a << " ";
}
cout << endl<<endl;
}
};
void Init(Client *my_client, int nums,Resource &all_resources, Resource &allocated_resources, Resource &remained_resources)
{
for (int i = 0; i < nums; i++)//从分配给各个客户(进程)的资源数组中统计已分配的资源
{
for (unsigned int j = 0; j < my_client.own.size(); j++)
{
allocated_resources.my_resource += my_client.own.at(j);
}
}
for (unsigned int i = 0; i < all_resources.my_resource.size(); i++)//用总共的资源减去已分配的资源得到剩余的资源
{
remained_resources.my_resource.at(i) = all_resources.my_resource.at(i) - allocated_resources.my_resource.at(i);
}
}
int main()
{
Client my_client =
{
{{3,0,1,1},{1,1,0,0}},
{{0,1,0,0},{0,1,1,2}},
{{1,1,1,0},{3,1,0,0}},
{{1,1,0,1},{0,0,1,0}},
{{0,0,0,0},{2,1,1,0}}
};
Resource all_resources, allocated_resources, remained_resources;
all_resources.my_resource.at(0) = 6;
all_resources.my_resource.at(1) = 3;
all_resources.my_resource.at(2) = 4;
all_resources.my_resource.at(3) = 2;
Init(my_client,5,all_resources, allocated_resources, remained_resources);
dispatch(my_client, 5, all_resources, allocated_resources, remained_resources);
}
这张图是原课本的题目和算法思路：
这张图是运行结果：
我们也学了 支持。{:1_921:}
代码的过程参数如果大于3，那么建议使用一个对象或结构来封装。 下次我们还实现一哈书中别的算法。嘿嘿嘿 看不懂 还得继续学习 s02lk 发表于 2019-5-18 19:41
下次我们还实现一哈书中别的算法。嘿嘿嘿
can't agree more,嘿嘿嘿
页:
[1]