银行家算法实现——找出所有安全序列
一 .死锁概述
所谓死锁： 是指两个或两个以上的进程在执行过程中，由于竞争资源或者由于彼此通信而造成的一种阻塞的现象，若无外力作用，它们都将无法推进下去。此时称系统处于死锁状态或系统产生了死锁，这些永远在互相等待的进程称为死锁进程。——百度百科
通俗的说，A进程持有资源a，还需要资源b，B进程持有资源b，还需要资源a，在无其他外界条件下，A进程需要B进程资源，B进程需要A进程资源，谁也不肯放手，我们就说这时出现死锁。
解决死锁问题主要通过预防死锁，避免死锁，检测死锁，解除死锁四个方面。
二. 银行家算法
银行家算法是从避免死锁来解决死锁问题。
1. 数据结构
available[m] //m种资源，每种资源可用数目
max[i][j] //第i个进程第j种资源最大需求量
allocation[i][j] //第i个进程第j种资源已经分配的量
need[i][j] //第i个进程第j种资源还需要的量
由上可以看出 max[i][j] = allocation[i][j] + need[i][j]
2. 算法步骤
设requesti是Pi的请求向量
若request[j]>need[i][j]，程序报错
若request[j]>available[i][j]，系统资源数不够，进程陷入等待
系统尝试着把资源分配给进程i，修改如下数据
available[j] -= request[j]
allocation[i][j] += request[j]
need[i][j] -= request[j]
接下来运行安全性算法
设置工作向量work[m]，表示系统目前的各类资源数，初始work=available
finish[n]，表示该进程是否在安全性队列中，初始finish[i] = false
从进程集合中找出一个满足下列条件的进程：
finish[i] = false，need[i][j] <= work[j]
若找到，修改下列值：
finish[i] = true
work[i] += allocation[i][j]
继续寻找下一个满足的进程
若所有的finish[i] = true，表示系统处于安全性状态，之前提出的请求可以满足。
3. 程序实现
我们先看一下安全性算法的c++代码
void isSafe()
{
int i, j, k;
for(i=1; i<=n; i++) //安全性序列要选n个进程
{
for(j=0; j<n; j++) //每次选择从n个进程里选一个
{
bool pd = true;
if(finish[j]){
continue;
}
for(k=0; k<m; k++) //每次选择要判断m个资源
{
if(work[k] < need[j][k]) //若有一个资源不满足，则break，寻找下一个进程
{
pd = false;
break;
}
}
if(pd){
ans.push_back(j);
finish[j] = true;
for(k=0; k<m; k++){ //选完j进程后，把已分给j进程的资源收回
work[k] += allow[j][k];
}
break;
}
}
if(j >= n){
break;
}
}
if(i > n){
for(j=0; j<ans.size(); j++)
{
cout << "P" << ans[j] << ",";
}
cout << endl;
sum++;
}
}主体为三重循环，时间复杂度为O(n*n*m)，第一层循环代表安全序列里要有n个，第二层循环代表每次要从n个进程里选出一个，第三层循环代表判断该进程是否可选（其m个资源是否满足要求），因为安全序列只要找到一个，且每个进程选定后，后一个进程不会对前一个进程产生影响，也就是不会产生回溯现象（为什么？）。
完整代码如下（为了便于测试，没有提示输入说明代码）
#include<cstring>
#include<vector>
#include<iostream>
using namespace std;
int resource[4] = {10, 5, 7};
int available[4] = {3, 3, 2};
int work[4];
int allow[6][4] = {{0, 1, 0}, {2, 0, 0}, {3, 0, 2}, {2, 1, 1}, {0, 0, 2}};
int need[6][4] = {{7, 4, 3}, {1, 2, 2}, {6, 0, 0}, {0, 1, 1}, {4, 3, 1}};
int maxx[6][4] = {{7, 5, 3}, {3, 2, 2}, {9, 0, 2}, {2, 2, 3}, {4, 3, 3}};
int n = 5; //进程数
int m = 3; //资源数
bool finish[6];
vector<int> ans;
int sum = 0;
void isSafe()
{
int i, j, k;
for(i=1; i<=n; i++) //安全性序列要选n个进程
{
for(j=0; j<n; j++) //每次选择从n个进程里选一个
{
bool pd = true;
if(finish[j]){
continue;
}
for(k=0; k<m; k++) //每次选择要判断m个资源
{
if(work[k] < need[j][k]) //若有一个资源不满足，则break，寻找下一个进程
{
pd = false;
break;
}
}
if(pd){
ans.push_back(j);
finish[j] = true;
for(k=0; k<m; k++){ //选完j进程后，把已分给j进程的资源收回
work[k] += allow[j][k];
}
break;
}
}
if(j >= n){
break;
}
}
if(i > n){
for(j=0; j<ans.size(); j++)
{
cout << "P" << ans[j] << ",";
}
cout << endl;
sum++;
}
}
void request(int p, int req[])
{
int i;
bool pd = true;
for(i=0; i<m; i++){
if(need[p][i] < req[i])
{
pd = false;
break;
}
}
if(!pd){
cout << "请求资源数错误\n";
return;
}
pd = true;
for(i=0; i<m; i++){
if(available[i] < req[i])
{
pd = false;
break;
}
}
if(!pd){
cout << "资源数不足,陷入等待\n";
return;
}
sum = 0;
for(i=0; i<m; i++)
{
work[i] = available[i] - req[i];
need[p][i] -= req[i];
allow[p][i] += req[i];
}
memset(finish, false, sizeof(finish));
isSafe();
if(sum > 0){
cout << "可以分配资源\n";
}
else{
cout << "不可分配资源\n";
for(i=0; i<m; i++)
{
need[p][i] += req[i];
allow[p][i] -= req[i];
}
}
}
int main()
{
//二进程请求资源 0，0，0
int req[] = {0, 0, 0};
request(2, req);
return 0;
} 4. 运行结果
三. 找出所有安全序列
以上的程序找出了一种安全性序列，从银行家算法的角度上完成了任务，如何找出所有的安全性序列呢？
1. DFS
找出所有解，一般这种问题都是由深度优先搜索来完成。程序很简单，一般熟悉深搜框架的都能很快写完。
void dfs(int k)
{
if(k == n){ //找到了一种安全性序列，打印输出
cout << sum++ << ":";
int i;
for(i=0; i<ans.size(); i++)
{
cout << "P" << ans[i] << ",";
}
cout << endl;
return;
}
int i;
for(i=0; i<n; i++){
if(!finish[i])
{
int j;
bool pd = true;
for(j=0; j<m; j++)
{
if(need[i][j] > work[j])
{
pd = false;
}
}
if(pd){ //第i个进程满足要求，暂时放入安全性队列
for(j=0; j<m; j++)
{
work[j] += allow[i][j];
}
finish[i] = true;
ans.push_back(i);
dfs(k+1); //搜索下一层
ans.pop_back(); //回溯，将第i个进程所做的改变恢复
for(j=0; j<m; j++)
{
work[j] -= allow[i][j];
}
finish[i] = false;
}
}
}
}时间复杂度为O((n * m) ^ n),可以看出，为了找出所有序列，时间复杂度较第一种大大提升，变成了指数级。
2. BFS
其实广度优先搜索也可以解决这个问题，上面的深搜借用了递归的思想，而广搜则是队列的思想，因为没有了递归，所以我们需要把每个点定义为一个状态，存下当前需要记录的信息，易于后面的回溯。
struct state
{
int work[5]; //当前每种资源可用量
bool finish[5]; //当前状态每个进程选择情况
int cur; //当前安全性序列已选中几个
vector<int> ans; //记录直到当前状态的安全性队列
state()
{
memset(finish, false, sizeof(finish));
}
};接下来先将资源数满足的进程先入队，然后进行bfs，每次队列首节点出队，由此节点扩展之后的子节点
queue<state> q;
int sum = 0;
void bfs()
{
int i, j, k;
for(i=0; i<n; i++)
{
bool pd = true;
for(j=0; j<m; j++)
{
if(need[i][j] > work[j]){
pd = false;
break;
}
}
if(pd){
state s;
for(j=0; j<m; j++)
{
s.work[j] = work[j] + allow[i][j];
}
s.ans.push_back(i);
s.finish[i] = true;
s.cur = 1;
q.push(s);
}
}
while(!q.empty())
{
state p = q.front();
q.pop();
if(p.cur == n){
cout << sum++ << ":";
int i;
for(i=0; i<p.ans.size(); i++)
{
cout << "P" << p.ans[i] << ",";
}
cout << endl;
}
for(i=0; i<n; i++)
{
if(!p.finish[i])
{
bool pd = true;
for(j=0; j<m; j++)
{
if(p.work[j] < need[i][j])
{
pd = false;
break;
}
}
if(pd){
for(j=0; j<m; j++)
{
p.work[j] += allow[i][j];
}
p.cur++;
p.finish[i] = true;
p.ans.push_back(i);
q.push(p);
for(j=0; j<m; j++)
{
p.work[j] -= allow[i][j];
}
p.cur--;
p.finish[i] = false;
p.ans.pop_back();
}
}
}
}
}时间复杂度同样为O((n * m) ^ n)
