银行家算法课程设计报告
银行家算法
一．需求分析
1. 在多道程序系统中，多个进程的并发执行来改善系统的资源利用率，提高系统的吞吐量，但可能发生一种危险——死锁。所谓死锁(Deadlock)，是指多个进程在运行过程中因争夺资源而造成的一种僵局（DeadlyEmbrace），当进程处于这种状态时，若无外力作用，他们都无法在向前推进。
要预防死锁，有摒弃“请求和保持”条件，摒弃“不剥夺”条件，摒弃“环路等待”条件等方法。
但是，在预防死锁的几种方法之中，都施加了较强的限制条件；而在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。在该方法中把系统状态分为安全状态和不安全状态，便可避免死锁的发生。
而最具代表性的避免死锁的算法，便是Dijkstra的银行家算法。
利用银行家算法，我们可以来检测CPU为进程分配资源的情况，决定CPU是否响应某进程的的请求并为其分配资源，从而很好避免了死锁的产生。
2. 银行家算法是一种最有代表性的避免死锁的算法。
要解释银行家算法，必须先解释操作系统安全状态和不安全状态。安全状态：如果存在一个由系统中所有进程构成的安全序列P1，…，Pn，则系统处于安全状态。安全状态一定是没有死锁发
生。
不安全状态:不存在一个安全序列。不安全状态不一定导致死锁。那么什么是安全序列呢
安全序列：一个进程序列{P1，…，Pn}是安全的，如果对于每一个进程Pi(1≤i≤n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j < i )当前占有资源量之和。
银行家算法：
我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。
3.设计要求：
设计一n个并发进程共享m个系统资源的程序实现银行家算法。要求包括：
（1）简单的初始化界面；
（2）系统资源的占用和剩余情况；
（3）为进程分配资源，用银行家算法对其进行检测，分为以下三种情况：
A. 所申请的资源大于其所需资源，提示分配不合理不予分配并返回；
B. 所申请的资源未大于其所需资源，但大于系统此时的可利用资源，提示分配不合理不予分配并返回；
C. 所申请的资源未大于其所需资源，亦未大于系统此时的可利用资源，预分配并进行安全性检查：
a. 预分配后系统是安全的，将该进程所申请的资源予以实际分配并打印后返回；
b. 与分配后系统进入不安全状态，提示系统不安全并返回；
（4）对输入进行检查，即若输入不符合条件，应当报错并返回重新输入；
（5）撤销作业，释放资源。
二．概要设计
（一）算法思路：
先对用户提出的请求进行合法性检查，即检查请求是否大于需要的，是否大于可利用的。若请求合法，则进行预分配，对分配后的状态调用安全性算法进行检查。若安全，则分配；若不安全，则拒绝申请，恢复到原来的状态，拒绝申请。
(二)算法步骤：
（1）如果Requesti＜or =Need,则转向步骤(2)；否则，认为出错，因为它所需要的资源数已超过它所宣布的最大值。
（2）如果Request＜or=Available,则转向步骤（3）；否则，表示系统中尚无足够的资源，进程必须等待。
（3）系统试探把要求的资源分配给进程Pi,并修改下面数据结构中的值：Available=Available-Request[i];
Allocation=Allocation+Request;
Need=Need-Request;
(4)系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。
三．详细设计
#define SIZE 11
int available[SIZE];
int claim[SIZE][SIZE];
int allocation[SIZE][SIZE];
int need[SIZE][SIZE];
int request[SIZE][SIZE] = { 0 };n\n");
return;
如果安全检测时安全的，则程序就会找出一个安全的序列，例如：
p0,p1,p2,p3,p4。此程序在找安全序列的时候每次都是从头开始找的for (i = 0; i < process; i++)
{
for (j = 0; j < ava; j++)
n\n");
}
showdate();
return 1;
}
void allot()
{
int i, j, k;
printf("\n请输入当前要申请资源的进程的序号(0--%d):", process - 1);
while (1)
{
scanf("%d", &r);
if ((r <= process - 1) && (r >= 0))
{
break;
}
printf("输入错误，请重新输入：");
}
printf("请输入要申请的各个资源实例的数量：\n");
ava_xh();
for (j = 0; j < ava; j++)
{
scanf("%d", &request[r][j]);
}
for (i = 0; i < ava; i++)
{
if (request[r][i] > need[r][i])
{
printf("\n申请资源量超过所声明的最大资源需求量Max\n");
return;
}
}
for (i = 0; i < ava; i++)
{
if (request[r][i] > available[i])
{
printf("剩余资源实例不足，需要等待,重来一次.\n");
return;
}
}
for (i = 0; i < ava; i++)n\n");
return;
}
int check()
{
int i, j, k, l = 0;
int work[SIZE] = { 0 };//工作数组
for (i = 0; i < ava; i++)//初始化
{
work[i] = available[i];
}
for (i = 0; i < process; i++) //初始化
{
finish[i] = 0;
}
for (i = 0; i < process; i++)
{
for (j = 0; j < ava; j++)////寻找条件 Need[i]<=Work[i]
{
if (need[i][j] > work[j])
{
break;
}
}
if ((j == ava) && (finish[i] == 0))///寻找条件Finish[i]=false ，每次从头开始找安全序列
finish[i] = 1;
for (k = 0; k < ava; k++)
{
work[k] = work[k] + allocation[i][k];
}
p[l] = i;//记录安全序列
l++;
//i = -1;///重置i，为了寻找安全序列
}
else
{
continue;
}
if (l == process)//可以找到安全序列，输出并结束{
printf("\n系统安全!\n");
printf("安全序列为：");
for (k = 0; k < l; k++)
{
printf("P(%d)", p[k]);
if (k != l - 1)
{
printf("-->");
}
}
return 1;
}
printf("\n系统不安全，不能满足你的要求！\n");
return 0;
}
void showdate()//显示现在所有数据
{
int i, j, k;
printf("当前所有数据！\n");
printf("\nMax\n");
printf(" ");
ava_xh();
for (i = 0; i < process; i++)
{
printf("P(%d) ", i);
for (j = 0; j < ava; j++)
{
printf("%d ", claim[i][j]);
}
printf("\n");
}
printf("\nAllocation\n");
printf(" ");
ava_xh();
for (i = 0; i < process; i++)
{
printf("P(%d) ", i);
for (j = 0; j < ava; j++)
{
printf("%d ", allocation[i][j]);
}
printf("\n");
}
printf("\nNeed\n");
printf(" ");
ava_xh();
for (i = 0; i < process; i++)
{
printf("P(%d) ", i);
for (j = 0; j < ava; j++)
{
printf("%d ", need[i][j]);
}
printf("\n");
}
printf("\nAvailable\n");
ava_xh();
for (i = 0; i < ava; i++)
{
printf("%d ", available[i]);
}
printf("\n==================================================== ===========\n");
printf("\n\n\n");
return;
}