利用银行家算法避免死锁
【注】本代码数据及思路方法参考自《计算机操作系统（第四版）》汤小丹等 编著的教材。
#include <iostream>
#define m 3 // 资源数
#define n 5 // 进程数
#define p 3 // 请求资源的进程数
// 可利用资源向量 Available (含有m个元素的数组，每个元素代表一类课利用的资源数目)
int Available[m];
// 最大需求矩阵 Max (n×m的矩阵，n个教程，每个进程对m类资源的最大需求)
int Max[n][m];
// 分配矩阵 Allocation (n×m的矩阵，每类资源当前已分配给每个进程的资源数)
int Allocation[n][m];
// 需求矩阵 Need (n×m的矩阵，每个进程尚需的各类资源数)
int Need[n][m]; // Need[i][j] = Max[i][j] - Allocation[i][j]
// 请求向量
int Request[n];
// 安全序列
int securitySequence[n];
// 初始化函数
void Init()
{
// 三类资源：A,B,C；资源数量分别为：10, 5, 7
// 初始时刻资源分配情况
int a = 0;
int temp[m * n*3] = {7,5,3,0,1,0,7,4,3,3,2,2,2,0,0,1,2,2,9,0,2,3,0,2,6,0,0,2,2,2,2,1,1,0,1,1,4,3,3,0,0,2,4,3,1};
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
Max[i][j] = temp[a];
a++;
//printf("%d", Max[i][j]);
}
//printf("\t");
for (int j = 0; j < m; j++)
{
Allocation[i][j] = temp[a];
a++;
//printf("%d", Allocation[i][j]);
}
//printf("\t");
for (int j = 0; j < m; j++)
{
Need[i][j] = temp[a];
a++;
//printf("%d", Need[i][j]);
}
//printf("\n");
}
Available[0] = 3;
Available[1] = 3;
Available[2] = 2;
}
// 安全性检测
bool SafetyCheck()
{
int index = 0;
// 1. 设置两个向量，初始化两个向量
int Work[m]; // 工作向量
bool Finish[n] = { false }; // 系统是否有足够的资源分配给进程，使之运行完成，默认为没有足够资源
for (int i = 0; i < m; i++)
Work[i] = Available[i];
// 2. 从进程集合中找到一个满足条件的进程(Finish[i] = false; Need[i][j] <= Work[j])，若找到：执行3；否则：执行4
// 这个循环是错的，应该循环查找，记得改一下！！（可能的问题还是在循环判断这！！！）
// 安全性检查也有问题，后面的Work有问题，后面的进程判断也有问题！！！
/*
（已改）注：在用循环查找到满足两个条件的进程后，继续往后查找，在后面的进程中，找到最后一个也不满足就会产生找不到的假象
*/
bool findFlag = true; // 用来标识在一次的for循环中，是否找到了一个满足条件的进程，默认为能找到
while (findFlag)
{
int i; // 第i个进程
findFlag = false; // 在每次的for循环前，设定为找不到满足条件的进程，
// 当找到进程后，再修改成true，作为判断是否再进行一次for查找和判断是否安全的条件
for (i = 0; i < n; i++)
{
if (Finish[i] == false)
{
bool flag = true; // 用来标识是否满足Need[i][j] <= Work[j]，默认为满足
for (int j = 0; j < m; j++)
{
if (Need[i][j] > Work[j]) // 不满足Need[i][j] <= Work[j]
{
flag = false;
break;
}
}
if (flag) // 该进程满足两个条件
{
// 3. 当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源
// 输出安全序列的表格（类似于书上的表格）便于检查程序是否正确
// if语句没有含义，就是为了在集成开发环境中将输出语句收起来，方便看代码
/*if (true)
{
printf("P%d\t", i);
for (int j = 0; j < m; j++)
printf("%d", Work[j]);
printf("\t");
for (int j = 0; j < m; j++)
printf("%d", Need[i][j]);
printf("\t");
for (int j = 0; j < m; j++)
printf("%d", Allocation[i][j]);
printf("\t");
for (int j = 0; j < m; j++)
printf("%d", Work[j] + Allocation[i][j]);
printf("\n");
}*/
for (int j = 0; j < m; j++)
Work[j] = Work[j] + Allocation[i][j];
Finish[i] = true;
findFlag = true;
securitySequence[index++] = i;
}
}
}
}
// 4. 如果所有进程的Finish[i] = true都满足，则系统处于安全状态
bool safety = true; // 标识系统是否处于安全状态，默认为安全状态
for (int i = 0; i < n; i++)
{
if (Finish[i]==false) // 存在Finish!=true的进程
{
safety = false; // 系统处于不安全状态
break;
}
}
if (safety)
return true; // true代表安全
else
return false; // false代表不安全
}
// 输出安全序列
void PrintResult()
{
printf("安全序列为：{");
for (int i = 0; i < n; i++)
{
printf("P%d ",securitySequence[i]);
}
printf("}\n");
}
// 银行家算法
int Bankers(int index)
{// index代表：第index个进程请求资源
// 1. 如果Request[j]≤Need[i, j] 转向步骤2；否则认为出错：所需资源超过所宣称的最大值
for (int i = 0; i < m; i++)
{
if (Request[i] > Need[index][i])
return 0; // 返回0代表：所需资源超过所宣称的最大值
}
// 2. 如果Request[j]≤Available[j] 转向步骤3；否则：尚无足够的资源，第index个进程需等待
for (int i = 0; i < m; i++)
{
if (Request[i] > Available[i])
return 1; // 返回1代表：尚无足够的资源，进程需等待
}
// 3. 系统试着将资源分配给第index个进程，并修改下面数据结构中的数值
for (int i = 0; i < m; i++)
{
Available[i] = Available[i] - Request[i];
Allocation[index][i] = Allocation[index][i] + Request[i];
Need[index][i] = Need[index][i] - Request[i];
}
// 4. 系统执行安全性算法，检查此次资源分配后系统是否处于安全状态。若安全：完成分配；否则：取消分配
if (SafetyCheck()) // 当SafetyCheck()返回true时：表明安全
{
return 2; // 返回2代表：完成分配
}
else
{
for (int i = 0; i < m; i++) // 取消分配，恢复原来的资源分配状态
{
Available[i] = Available[i] + Request[i];
Allocation[index][i] = Allocation[index][i] - Request[i];
Need[index][i] = Need[index][i] + Request[i];
}
return 3; // 返回3代表：完成分配后，系统将处于不安全的状态
}
}
int main()
{
Init();
int tempRequest[p][m] = { { 1, 0, 2 }, {3,3,0}, {0, 2, 0} }; // 各进程的对应请求资源数
int process[p] = { 1, 4, 0 }; // 请求资源的进程号：P1 -> P4 -> P0
for (int i = 0; i < p; i++)
{
for (int j = 0; j < m; j++) // 赋值资源请求数目
{
Request[j] = tempRequest[i][j];
}
int result = Bankers(process[i]);
if (result == 0)
{
printf("所需资源超过所宣称的最大值\n");
}
else if (result == 1)
{
printf("尚无足够的资源，进程需等待\n");
}
else if (result == 2)
{
PrintResult();
}
else if (result == 3)
{
printf("完成分配后，系统将处于不安全的状态（取消分配）");
}
}
}
利用银行家算法避免死锁
【注】本代码数据及思路方法参考自《计算机操作系统（第四版）》汤小丹等 编著的教材。
#include <iostream>
#define m 3 // 资源数
#define n 5 // 进程数
#define p 3 // 请求资源的进程数
// 可利用资源向量 Available (含有m个元素的数组，每个元素代表一类课利用的资源数目)
int Available[m];
// 最大需求矩阵 Max (n×m的矩阵，n个教程，每个进程对m类资源的最大需求)
int Max[n][m];
// 分配矩阵 Allocation (n×m的矩阵，每类资源当前已分配给每个进程的资源数)
int Allocation[n][m];
// 需求矩阵 Need (n×m的矩阵，每个进程尚需的各类资源数)
int Need[n][m]; // Need[i][j] = Max[i][j] - Allocation[i][j]
// 请求向量
int Request[n];
// 安全序列
int securitySequence[n];
// 初始化函数
void Init()
{
// 三类资源：A,B,C；资源数量分别为：10, 5, 7
// 初始时刻资源分配情况
int a = 0;
int temp[m * n*3] = {7,5,3,0,1,0,7,4,3,3,2,2,2,0,0,1,2,2,9,0,2,3,0,2,6,0,0,2,2,2,2,1,1,0,1,1,4,3,3,0,0,2,4,3,1};
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
Max[i][j] = temp[a];
a++;
//printf("%d", Max[i][j]);
}
//printf("\t");
for (int j = 0; j < m; j++)
{
Allocation[i][j] = temp[a];
a++;
//printf("%d", Allocation[i][j]);
}
//printf("\t");
for (int j = 0; j < m; j++)
{
Need[i][j] = temp[a];
a++;
//printf("%d", Need[i][j]);
}
//printf("\n");
}
Available[0] = 3;
Available[1] = 3;
Available[2] = 2;
}
// 安全性检测
bool SafetyCheck()
{
int index = 0;
// 1. 设置两个向量，初始化两个向量
int Work[m]; // 工作向量
bool Finish[n] = { false }; // 系统是否有足够的资源分配给进程，使之运行完成，默认为没有足够资源
for (int i = 0; i < m; i++)
Work[i] = Available[i];
// 2. 从进程集合中找到一个满足条件的进程(Finish[i] = false; Need[i][j] <= Work[j])，若找到：执行3；否则：执行4
// 这个循环是错的，应该循环查找，记得改一下！！（可能的问题还是在循环判断这！！！）
// 安全性检查也有问题，后面的Work有问题，后面的进程判断也有问题！！！
/*
（已改）注：在用循环查找到满足两个条件的进程后，继续往后查找，在后面的进程中，找到最后一个也不满足就会产生找不到的假象
*/
bool findFlag = true; // 用来标识在一次的for循环中，是否找到了一个满足条件的进程，默认为能找到
while (findFlag)
{
int i; // 第i个进程
findFlag = false; // 在每次的for循环前，设定为找不到满足条件的进程，
// 当找到进程后，再修改成true，作为判断是否再进行一次for查找和判断是否安全的条件
for (i = 0; i < n; i++)
{
if (Finish[i] == false)
{
bool flag = true; // 用来标识是否满足Need[i][j] <= Work[j]，默认为满足
for (int j = 0; j < m; j++)
{
if (Need[i][j] > Work[j]) // 不满足Need[i][j] <= Work[j]
{
flag = false;
break;
}
}
if (flag) // 该进程满足两个条件
{
// 3. 当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源
// 输出安全序列的表格（类似于书上的表格）便于检查程序是否正确
// if语句没有含义，就是为了在集成开发环境中将输出语句收起来，方便看代码
/*if (true)
{
printf("P%d\t", i);
for (int j = 0; j < m; j++)
printf("%d", Work[j]);
printf("\t");
for (int j = 0; j < m; j++)
printf("%d", Need[i][j]);
printf("\t");
for (int j = 0; j < m; j++)
printf("%d", Allocation[i][j]);
printf("\t");
for (int j = 0; j < m; j++)
printf("%d", Work[j] + Allocation[i][j]);
printf("\n");
}*/
for (int j = 0; j < m; j++)
Work[j] = Work[j] + Allocation[i][j];
Finish[i] = true;
findFlag = true;
securitySequence[index++] = i;
}
}
}
}
// 4. 如果所有进程的Finish[i] = true都满足，则系统处于安全状态
bool safety = true; // 标识系统是否处于安全状态，默认为安全状态
for (int i = 0; i < n; i++)
{
if (Finish[i]==false) // 存在Finish!=true的进程
{
safety = false; // 系统处于不安全状态
break;
}
}
if (safety)
return true; // true代表安全
else
return false; // false代表不安全
}
// 输出安全序列
void PrintResult()
{
printf("安全序列为：{");
for (int i = 0; i < n; i++)
{
printf("P%d ",securitySequence[i]);
}
printf("}\n");
}
// 银行家算法
int Bankers(int index)
{// index代表：第index个进程请求资源
// 1. 如果Request[j]≤Need[i, j] 转向步骤2；否则认为出错：所需资源超过所宣称的最大值
for (int i = 0; i < m; i++)
{
if (Request[i] > Need[index][i])
return 0; // 返回0代表：所需资源超过所宣称的最大值
}
// 2. 如果Request[j]≤Available[j] 转向步骤3；否则：尚无足够的资源，第index个进程需等待
for (int i = 0; i < m; i++)
{
if (Request[i] > Available[i])
return 1; // 返回1代表：尚无足够的资源，进程需等待
}
// 3. 系统试着将资源分配给第index个进程，并修改下面数据结构中的数值
for (int i = 0; i < m; i++)
{
Available[i] = Available[i] - Request[i];
Allocation[index][i] = Allocation[index][i] + Request[i];
Need[index][i] = Need[index][i] - Request[i];
}
// 4. 系统执行安全性算法，检查此次资源分配后系统是否处于安全状态。若安全：完成分配；否则：取消分配
if (SafetyCheck()) // 当SafetyCheck()返回true时：表明安全
{
return 2; // 返回2代表：完成分配
}
else
{
for (int i = 0; i < m; i++) // 取消分配，恢复原来的资源分配状态
{
Available[i] = Available[i] + Request[i];
Allocation[index][i] = Allocation[index][i] - Request[i];
Need[index][i] = Need[index][i] + Request[i];
}
return 3; // 返回3代表：完成分配后，系统将处于不安全的状态
}
}
int main()
{
Init();
int tempRequest[p][m] = { { 1, 0, 2 }, {3,3,0}, {0, 2, 0} }; // 各进程的对应请求资源数
int process[p] = { 1, 4, 0 }; // 请求资源的进程号：P1 -> P4 -> P0
for (int i = 0; i < p; i++)
{
for (int j = 0; j < m; j++) // 赋值资源请求数目
{
Request[j] = tempRequest[i][j];
}
int result = Bankers(process[i]);
if (result == 0)
{
printf("所需资源超过所宣称的最大值\n");
}
else if (result == 1)
{
printf("尚无足够的资源，进程需等待\n");
}
else if (result == 2)
{
PrintResult();
}
else if (result == 3)
{
printf("完成分配后，系统将处于不安全的状态（取消分配）");
}
}
}