BlueSky

银行家算法是Dijksta在1965年提出的一种能够避免死锁的调度算法。该模型基于一个小城镇的银行家，他向一群客户分别承诺了一定的贷款额度。算法要做的是判断对请求的满足是否会导致进入不安全状态。

可以把银行家算法进行推广以处理多个资源。下图说明了多个资源的银行家算法如何工作。

我们可以看到两个矩阵。左边的矩阵显示出5个进程分别已分配的各种资源数，右边的矩阵显示了使各进程完成运行所需的各种资源数。最右边的三个向量分别表示现有资源E、已分配资源P和可用资源A。P向量可通过将左边矩阵的各列相加获得，可用资源向量可通过从现胡资源中减去已分配资源获得。

检查一个状态是否安全的算法如下：

1）查找右边矩阵中是否有一行，其没有被满足的资源数均小于或等于A。如果不存在这样的行，那么系统将会死锁，因为任何进程都无法运行结束。

2）假若找到这样一行，那么可以假设它获得所需的资源并运行结束，将该进程标记为终止，并将其资源加到向量A上。

3）重复以上两步，直到所有的进程都被标记为终止，其初始状态是安全的；或者直到死锁发生，此刻的状态是不安全的。

如果在第1步中同时存在若进程均符合条件，那么不管挑选哪一个进程运行都没有关系，因为可用资源或者会增多，或者至少保持不变。

上图所示的状态是安全的，若进程B现在再请求一台打印机，可以满足它的请求，因为所得系统状态仍然是安全的（进程D可以结束，然后是A或E结束，剩下的进程相继结束）。

假设进程B获得两台可用打印机中的一台以后，E试图获得最后的一台打印机，假若分配给E，可用资源向量会减到（1000），这时会引起死锁。显然E的请求不能立即满足，必须延迟一段时间。

银行家算法自从被提出 后很多操作系统的专著都会详细地描述它。不过很少有作者指出该算法或然很有意义但却缺乏实用价值，因为很少有进程能够在运行前就知道其所需资源的最大值。而且进程数也不是固定的，往往在不断地变化，况且原本可用的资源也可能突然间变成不可用（硬盘可能突然坏掉什么的）。因此，在实际中，如果有，也只有极少的系统使用银行家算法来避免死锁（如运用在批处理系统中，有的批处理系统在处理作业时要求程序员明确指出所需要资源）。

附上自己写的源码：

#include <vector>
#include <iostream>
#include <algorithm>
#include <numeric>
using namespace std;

class Resource
{
public:
Resource(int n, int *init=NULL):num(n)
{
resArray = new int[n];
if (init==NULL)
{
memset(resArray, 0, n);
}
else
copy(init, init+n, resArray);
}
Resource(Resource &res)
{
num = res.getNum();
resArray = new int[num];
copy(res.getArray(), res.getArray()+num, resArray);
}
~Resource()
{
delete []resArray;
}
//获得数组元素个数
int getNum()
{
return num;
}
//获得数组的const指针
const int* getArray()
{
return resArray;
}
//左边数组的元素全部大于右边数组时才返回真
bool operator>=(Resource &right)
{
if (num!=right.getNum())
{
cout << "资源种类不一样，无法比较。。。" << endl;
return false;
}
for (int loop=0; loop!=num; ++loop)
{
if (resArray[loop]<right.getArray()[loop])
{
return false;
}
}
return true;
}
//假如数组中有一个小于零，则返回真
bool operator<(int)
{
for (int loop=0; loop!=num; ++loop)
{
if (resArray[loop]<0)
{
return true;
}
}
return false;
}
void operator=(Resource &right)
{
if (num!=right.getNum())
{
cout << "资源种类不一样，无法赋值。。。" << endl;
return;//表示赋值失败
}
copy(right.getArray(), right.getArray()+num, resArray);
}
Resource operator+(Resource &right)
{
if (num!=right.getNum())
{
cout << "资源种类不一样，无法相加。。。" << endl;
return 0;//表示相加失败
}
Resource temp(num);
for (int loop=0; loop!=num; ++loop)
{
temp.resArray[loop] = resArray[loop] + right.getArray()[loop];
}
return temp;
}
Resource operator-(Resource &right)
{
{
if (num!=right.getNum())
{
cout << "资源种类不一样，无法相减。。。" << endl;
return 0;//表示相减失败
}
Resource temp(num);
for (int loop=0; loop!=num; ++loop)
{
temp.resArray[loop] = resArray[loop] - right.getArray()[loop];
}
return temp;
}
}
private:
int num;//记录可用资源种数
int *resArray;//指向资源数组
};
//用来释放掉智能指针范围的指针指向的内存空间
template <class Iter>
void DelProxy(Iter begin, Iter end)
{
for (Iter loop=begin; loop!=end; ++loop)
{
delete *loop;
}
}
//将vector容器的元素指向的对象全部相加，并返回相加后的结果
Resource Additive(vector<Resource*>::iterator begin, vector<Resource*>::iterator end)
{
Resource temp((*begin)->getNum());
for (vector<Resource*>::iterator it=begin; it!=end; ++it)
{
temp = temp + **it;
}
return temp;
}
int main()
{
int num, cProCount;
cout << "输入资源种数：";
cin >> num;
cout << "输入进程个数：";
cin >> cProCount;
int *resArray = new int[num];
bool fSafe = false;

bool fState = true;
vector<bool> state(cProCount, true);
vector<Resource*> ownRes(cProCount);
vector<Resource*> neededRes(cProCount);

cout << "请分别输入各个进程原先拥有各个资源的数量：" << endl;
for (int loop1=0; loop1!=cProCount; ++loop1)
{
for (int loop2=0; loop2!=num; ++loop2)
{
cin >> resArray[loop2];
}
ownRes[loop1] = new Resource(num, resArray);
}

cout << "请分别输入各个进程仍需各个资源的数量：" << endl;
for (int loop1=0; loop1!=cProCount; ++loop1)
{
for (int loop2=0; loop2!=num; ++loop2)
{
cin >> resArray[loop2];
}
neededRes[loop1] = new Resource(num, resArray);
}

cout << "请分别输入各个资源的原有数量：" << endl;
for (int loop=0; loop!=num; ++loop)
{
cin >> resArray[loop];
}
Resource intrinsicRes(num, resArray);
Resource assignedRes(num);
//将各个进程拥有的资源数进行相加，则可得到每种资源已分配的数量
assignedRes = Additive(ownRes.begin(), ownRes.end());
//这时原有资源数比已分配资源数少，肯定是错误的
if (intrinsicRes-assignedRes<0)
{
cout << "原有资源数比已分配资源数少，错误。。。" << endl;
//膳后工作
delete []resArray;
DelProxy(ownRes.begin(), ownRes.end());
DelProxy(neededRes.begin(), neededRes.end());
return 1;
}
Resource availRes(num);
//得到每种资源仍可使用的数量
availRes = intrinsicRes - assignedRes;
for (int loop=0, index=0; loop!=num; ++loop, index=0)
{
fSafe = false;
for (vector<Resource*>::iterator it=neededRes.begin(); it!=neededRes.end(); ++it, ++index)
{
//state[index]为false的话则表明对应的进程已经获得所要的资源并结束退出了
if (state[index]&&availRes>=**it)
{
availRes = availRes + *(ownRes[index]);
state[index] = false;
fSafe = true;
break;
}
}
//fSafe此时为false的话表明没有一个进程能获得想要的资源数量
if (!fSafe)
{
cout << "此状态不太妙，会引起死锁。。。" << endl;
fState = false;
break;
}
}
if (fState)
{
cout << "此状态安全。。。" << endl;
}
//膳后工作
delete []resArray;
DelProxy(ownRes.begin(), ownRes.end());
DelProxy(neededRes.begin(), neededRes.end());
return 0;
}