一、实验目的
(1)进一步理解利用银行家算法避免死锁的问题;
(2)在了解和掌握银行家算法的基础上,编制银行家算法通用程序,将调试结果显示在计算机屏幕上,再检测和笔算的一致性。
(3)理解和掌握安全序列、安全性算法
二、实验环境
1.开发语言:C++/C#
2.开发环境:Microsoft Visual Studio 6.0/ Microsoft Visual Studio .NET 2003/DEV C++
三、实验内容
【实验原理】
一、安全状态
指系统能按照某种顺序如<P1,P2,…,Pn>(称为<P1,P2,…,Pn>序列为安全序列),为每个进程分配所需的资源,直至最大需求,使得每个进程都能顺利完成。
二、银行家算法
假设在进程并发执行时进程i提出请求j类资源k个后,表示为Requesti[j]=k。系统按下述步骤进行安全检查:
(1)如果Requesti≤Needi则继续以下检查,否则显示需求申请超出最大需求值的错误。
(2)如果Requesti≤Available则继续以下检查,否则显示系统无足够资源,Pi阻塞等待。
(3)系统试探着把资源分配给进程Pi,并修改下面数据结构中的数值:
Available[j]∶=Available[j]-Requesti[j];
Allocation[i,j]∶=Allocation[i,j]+Requesti[j];
Need[i,j]∶=Need[i,j]-Requesti[j];
(4)系统执行安全性算法,检查此次资源分配后,系统是否处于安全状态。若安全,才正式将资源分配给进程Pi,以完成本次分配;否则, 将本次的试探分配作废,恢复原来的资源分配状态,让进程Pi等待。
三、安全性算法
(1)设置两个向量:
① 工作向量Work: 它表示系统可提供给进程继续运行所需的各类资源数目,它含有m个元素,在执行安全算法开始时,Work∶=Available;
② Finish: 它表示系统是否有足够的资源分配给进程,使之运行完成。开始时先做Finish[i]∶=false; 当有足够资源分配给进程时, 再令Finish[i]∶=true。
(2)从进程集合中找到一个能满足下述条件的进程:
① Finish[i]=false;
② Need[i,j]≤Work[j]; 若找到, 执行步骤(3), 否则,执行步骤(4)。
(3)当进程Pi获得资源后,可顺利执行,直至完成,并释放出分配给它的资源,故应执行:
- Work[j]∶=Work[i]+Allocation[i,j];
- Finish[i]∶=true;
- go to step 2;
- 如果所有进程的Finish[i]=true都满足, 则表示系统处于安全状态;否则,系统处于不安全状态。
【实验步骤】
- 参考图1-1所示流程图编写安全性算法。
(2)编写统一的输出格式。
每次提出申请之后输出申请成功与否的结果。如果成功还需要输出变化前后的各种数据,并且输出安全序列。
(3)参考图1-2所示流程图编写银行家算法。
(4)编写主函数来循环调用银行家算法。
话不多说上代码!!!
#include <stdio.h>
int main()
{int claim[5][3]={{7,5,3},{3,2,2},{9,0,2},{2,2,2},{4,3,3}};//各线程最大需求量int allocation[5][3]={{0,1,0},{2,0,0},{3,0,2},{2,1,1},{0,0,2}};//各线程已分配资源int i,j,k,l=0,count=0,m=0;int C_A[5][3]={{0,0,0},{0,0,0},{0,0,0},{0,0,0},{0,0,0}};//各进程仍需要的各类资源int result[5]={-1,-1,-1,-1,-1};//存放预分配成功的线程int currentavail[3]={3,3,2};//当前可分配资源printf("银行家总共拥有的各类资源的总数:\n A B C\n 10 5 7\n");printf("银行目前仍剩下的各类资源的数量:\n A B C\n 3 3 2\n");printf("各进程对各类资源的最大需求量:\n A B C\n");for(i=0;i<5;i++){printf("P%d: ",i);for(j=0;j<3;j++){printf(" %d ",claim[i][j]);C_A[i][j]=claim[i][j]-allocation[i][j];}printf("\n");}printf("各进程已分配到的各类资源:\n A B C\n");for(i=0;i<5;i++){printf("P%d: ",i);for(j=0;j<3;j++)printf(" %d ",allocation[i][j]);printf("\n");}printf("各进程仍需的各类资源数量:\n A B C\n");for(i=0;i<5;i++){printf("P%d: ",i);for(j=0;j<3;j++)printf(" %d ",C_A[i][j]);printf("\n");}while(result[l]==-1)//{for(k=0;k<5;k++)if(result[k]==-1){for(j=0;j<3;j++)
//判断各线程对各资源仍需量是否小于当前可分配资源总量,此量为正数才正常if(C_A[k][j]<=currentavail[j]&&C_A[k][j]>=0){
//把满足条件的进程的已分配资源加到当前可分配资源中currentavail[j]=currentavail[j]+allocation[k][j];m++;if(m==3){result[l]=k;//只有ABC三类资源都满足才把相应的线程记入数组result中m=0;}}else break;//否则退出循环,打印"系统不安全"l++;}for(i=0;i<l;i++)if(result[i]!=-1){printf("P%d->",result[i]);//把预分配成功的先打印出来count++;}l=0;//清零,为下一轮的预分配做准备}if(count==5)printf("\n系统安全!上行所示为其中一个进程安全序列\n");elseprintf("\n系统不安全!\n");
}
四、实验结果
五、实验总结
- 问题1:在编程中遇到了哪些问题?你是如何解决的?
1. 注意变量全局定义问题:在实现这份代码的时候陷入了一个误区那就是当你找到了一个安全序列之后,它查找过的Finish必定会被修改为true,而Finish这个数组又是在全局定义的,所以只要找到一次正确的安全序列这个Finish所找到的位就会被置为true会一直出现找到安全序列的,所以在找到安全序列之后一定要将Finish重新赋初值false。
2.死锁问题:在执行过程中出现两个或两个以上的进程由于竞争资源或彼此通信而阻塞,导致无法继续执行的情况。
解决办法:当一个进程申请资源的时候,操作系统通过银行家算法先试探分配给该进程资源,然后通过安全性算法判断分配后的系统是否处于安全状态,若不安全则分配作废,让该进程继续等待,否则分配资源给进程。
- 问题2:在安全性算法中,为什么不用变量Available,而又定义一个临时变量work?
变量Available通常是表示系统、资源或信息当前可用的状态,直接使用Available作为操作依据可能存在风险:
1. 如果Available是一个硬编码的阈值,那么一旦这个阈值被攻击者得知,他们可能会利用它发起针对性攻击。
2. 如果Available被频繁查询,对手可能会通过观察变化模式推断出系统的运行状态,这会暴露潜在的安全漏洞。
因此,定义一个临时变量work,通常用于处理、计算或检查Available的实时状态。这样可以增加一层间接性和动态性,使得攻击者难以直接利用这个值。`work`可能是经过某种加密、哈希或其他安全处理后的结果,或者是在访问Available之前进行安全校验和限制的过程的一部分。
操作work而不是Available,有助于保护系统的稳定性和隐私,同时提高防御策略的复杂性,使得恶意行为更难以预测和实施。
- 关于死锁
系统中资源分为两类:
可剥夺性资源:资源分配给进程后可以被高优先级的进程剥夺,比如cpu,主存等
不可剥夺性资源:资源分配给进程用完才被释放的资源,比如打印机,磁带等
死锁产生原因
1.1资源竞争
一般系统中的不可剥夺性资源,因其数量不足的原因无法满足多数进程的需要而出现的竞争资源而陷入僵局,这是造成死锁问题的原因之一。只有对不可剥夺性资源的竞争才会产生死锁问题,对可剥夺性资源的竞争不会产生死锁问题。
1.2进程推进顺序非法
假设此时P1和P2分别保持了资源R1、R2.此时P1申请资源R2、P2,申请R1那么就会陷入僵局,产生死锁问题。
1.3信号使用不当
A在申请B的资源时等待B给出信号,同时B也在等待A的信号,B也想申请A的资源;此时他们申请的并非是同一种资源,而是都在等待各自的信号,从而造成死锁。
满足死锁的四个必要条件:
互斥性:
某一资源只能为一个进程所占用,若有其他进程要请求该资源,只能进行等待
请求和保持条件:
进程已经保持了至少一个资源,但又提出新的资源请求,但此时该资源被其他进程占用,此时请求进程堵塞,但又对已获得的资源保持不放。
不可剥夺条件:
进程所获得的资源在未使用完毕之前,不能被其他进程强行夺走,即只能 由获得该资源的进程自己来释放(只能是主动释放)。
循环等待:
存在一种进程资源的循环等待链,链中每一个进程已获得的资源同时被 链中下一个进程所请求。
如何避免死锁?
安全状态和不安全状态:
系统处于安全状态时,就可避免死锁;处于不安全状态时,可能发生死锁。
所谓安全状态,是指系统此时能找到一个进程的序列<P1,P2,P3…Pn>,只要按照此顺序为其分配资源,就能使每个进程都能顺利完成。如果存在一个安全序列,那么系统则处于安全状态,否则就处于不安全状态。
在避免死锁方法中,允许进程动态地申请资源,但是系统在分配资源之前,会先计算此次资源分配的安全性,安全的话才分配,不安全的话便令进程等待。