实验四 死锁避免的算法

操作系统实验报告-死锁的避免操作系统实验（二）死锁的避免1.实验内容使用C++实现模拟随机算法和银行家算法2.实验目的（1）了解死锁的产生原因（随机算法）（2）理解死锁的解决办法（银行家算法）3.实验题目使用随机算法和银行家算法设计程序4.程序流程图主要过程流程图银行家算法流程图安全性算法流程图5.程序代码和运行结果#include <stdio.h>#include<stdlib.h> typedef struct{int A;int B;int C;}RES;#define false 0#define true 1//系统中所有进程数量#define PNUMBER 3//最大需求矩阵RES Max[PNUMBER];//已分配资源数矩阵RES Allocation[PNUMBER];//需求矩阵RES Need[PNUMBER];//可用资源向量RES Available={0,0,0};//安全序列int safe[PNUMBER];void setConfig(){int i=0,j=0;printf("================开始手动配置资源==================\n");//可分配资源printf("输入可分配资源\n");scanf("%d%d%d",&Available.A,&Available.B,&Available.C);//最大需求矩阵MAXprintf("输入最大需求矩阵%dx%d\n",PNUMBER,PNUMBER );for (i=0;i<PNUMBER;i++){scanf("%d%d%d",&Max[i].A,&Max[i].B,&Max[i].C);}//已分配矩阵Allocprintf("输入已分配矩阵%dx%d\n",PNUMBER,PNUMBER);for (i=0;i<PNUMBER;i++){scanf("%d%d%d",&Allocation[i].A,&Allocation[i].B,&Allocation[i].C);}//需求矩阵printf("输入需求矩阵%dx%d\n",PNUMBER,PNUMBER);for (i=0;i<PNUMBER;i++){scanf("%d%d%d",&Need[i].A,&Need[i].B,&Need[i].C);}printf("================结束配置资源==================\n");}void loadConfig(){FILE *fp1;if ((fp1=fopen("config.txt","r"))==NULL){printf("没有发现配置文件,请手动输入\n");setConfig();}else{int i=0;printf("发现配置文件,开始导入..\n");//可分配资源fscanf(fp1,"%d%d%d",&Available.A,&Available.B,&Available.C);//最大需求矩阵MAXfor (i=0;i<PNUMBER;i++){fscanf(fp1,"%d%d%d",&Max[i].A,&Max[i].B,&Max[i].C);}//已分配矩阵Allocfor (i=0;i<PNUMBER;i++){fscanf(fp1,"%d%d%d",&Allocation[i].A,&Allocation[i].B,&Allocation[i].C);}//需求矩阵for (i=0;i<PNUMBER;i++){fscanf(fp1,"%d%d%d",&Need[i].A,&Need[i].B,&Need[i].C);}}}//试探分配void ProbeAlloc(int process,RES *res){Available.A -= res->A;Available.B -= res->B;Available.C -= res->C;Allocation[process].A += res->A;Allocation[process].B += res->B;Allocation[process].C += res->C;Need[process].A -= res->A;Need[process].B -= res->B;Need[process].C -= res->C;}//若试探分配后进入不安全状态，将分配回滚void RollBack(int process,RES *res){Available.A += res->A;Available.B += res->B;Available.C += res->C;Allocation[process].A -= res->A;Allocation[process].B -= res->B;Allocation[process].C -= res->C;Need[process].A += res->A;Need[process].B += res->B;Need[process].C += res->C;}//安全性检查bool SafeCheck(){RES Work;Work.A = Available.A;Work.B = Available.B;Work.C = Available.C;bool Finish[PNUMBER] = {false,false,false};int i;int j = 0;for (i = 0; i < PNUMBER; i++){//是否已检查过if(Finish[i] == false){//是否有足够的资源分配给该进程if(Need[i].A <= Work.A && Need[i].B <= Work.B && Need[i].C <= Work.C){//有则使其执行完成，并将已分配给该进程的资源全部回收Work.A += Allocation[i].A;Work.B += Allocation[i].B;Work.C += Allocation[i].C;Finish[i] = true;safe[j++] = i;i = -1; //重新进行遍历}}}//如果所有进程的Finish向量都为true则处于安全状态，否则为不安全状态for (i = 0; i < PNUMBER; i++){if (Finish[i] == false){return false;}}return true;}//资源分配请求bool request(int process,RES *res){//request向量需小于Need矩阵中对应的向量if(res->A <= Need[process].A && res->B <= Need[process].B && res->C <=Need[process].C){//request向量需小于Available向量if(res->A <= Available.A && res->B <= Available.B && res->C <= Available.C){//试探分配ProbeAlloc(process,res);//如果安全检查成立，则请求成功，否则将分配回滚并返回失败if(SafeCheck()){return true;}else{printf("安全性检查失败。

操作系统实验预防进程死锁的银行家算法一、需求分析：1、实验目的：通过这次实验，加深对进程死锁的理解，进一步掌握进程资源的分配、死锁的检测和安全序列的生成方法。

2、问题描述：设计程序模拟预防进程死锁的银行家算法的工作过程。

假设系统中有n个进程P1, … ,P n，有m类可分配的资源R1, … ,R m，在T0时刻，进程P i分配到的j类资源为Allocation ij个，它还需要j类资源Need ij个，系统目前剩余j类资源Work j个，现采用银行家算法进行进程资源分配预防死锁的发生。

3、程序要求：1）判断当前状态是否安全，如果安全给出安全序列；如果不安全给出理由。

2）对于下一个时刻T1，某个进程P k会提出请求Request(R1, … ,R m)，判断分配给P k进程请求的资源之后系统是否安全。

3）输入：进程个数n，资源种类m，T0时刻各个进程的资源分配情况（可以运行输入，也可以在程序中设置）；4）输出：如果安全，输出安全的进程序列，不安全则提示信息。

二、概要设计：1、进程调度的实现过程2、程序中的变量及数据结构struct ResItem{string Name;int Number;}; //资源项typedef vector<ResItem> Resource;struct Progress{string Name;Resource Max; //最大需求Resource Allocation; //分配Resource Need; //需求}; //进程vector <Progress> Progresses; //所有进程vector <ResItem> Available; //可利用资源向量vector <Progress> SafeOrder; //安全序列3、主要函数//初始化数据void InitData(int &n);//判断rs1是否小于等于rs2，是返回true，否则返回falseinline bool LessThan(Resource rs1,Resource rs2);//安全性算法bool SafeAlg();//银行家算法bool BankerAlg(Resource request,Progress &pro);4、主函数int main(){int n;InitData(n);cout<<"\n\n=============================================\n ";if(SafeAlg()){cout<<"由安全性检查可知：可以找到一个安全序列为：{";for(int i = 0 ; i < SafeOrder.size(); i++)cout<<SafeOrder[i].Name<<",";cout<<"}。

避免死锁银行家算法的模拟实现实验题目：机时：4实验一避免死锁银行家算法的模拟实现目的与任务银行家算法是避免死锁的一种重要方法，本实验要求用高级语言编写和调试一个简单的银行家算法程序。

加深了解有关资源申请、避免死锁等概念，并体会和了解死锁和避免死锁的具体实施方法。

内容和要求在了解和掌握银行家算法的基础上，能熟练的处理课本例题中所给状态的安全性问题，能编制银行家算法通用程序，将调试结果显示在计算机屏幕上，再检测和笔算的一致性。

具体程序的功能要求：1.设定进程对各类资源最大申请表示及初值确定。

2.设定系统提供资源初始状况(已分配资源、可用资源)。

3.设定每次某个进程对各类资源的申请表示。

4.编制程序，依据银行家算法，决定其申请是否得到满足。

设计内容(原理图以及相关说明、调试过程、结果设requesti为进程p[i]的请求向量，如果requesti[j]=K，表示进程p[i]需要K 个Rj资源。

当系统发出请求后，系统按下述步骤开始检查：(1)、如果requesti[j]=need[i][j],转向步骤2；否则报告出错，申请的资源已经大于它需要的最大值。

(2)、如果requesti[j]=available[j],转向步骤3；否则报告出错，尚无足够的资源。

(3)、系统试探着把资源分配给p[i]，并修改下列数据结构中的值：available[j]=available[j]-request[j]allocation[i][j]=allocation[i][j]+request[j]need[i][j]=need[i] [j]-request[j](4)、系统进行安全性算法，检查此次分配后，系统是否还处于安全状态，若安全，把资源分配给进程p[i]；否则，恢复原来的资源分配状态，让进程p[i]等待。

安全性算法1.为实现银行家算法，系统中需要设置若干数据结构，用来表示系统中各进程的资源分配及需求情况。

假定系统中有m个进程，n类资源进程数和资源数由程序中直接定义，#define m5//总进程数#define n4//总资源数对于不同规模的进程和资源数，在程序中直接修改m和n值即可。

“死锁避免”实验报告实验思路：先定义进程控制块的数据结构pcb，确定进程并发数目SIZE，在初始化进程时，保证各进程最大资源申请量不大于系统的资源总量，如果大于，则重新输入。

初始化完成之后，选择相应的死锁避免的算法，或随机分配算法，或银行家算法。

随机分配方法：运用取余的方法，轮询各个进程，选择处于就绪状态的进程之一，然后输入该进程的当前资源申请量apply，判断该申请量是否大于系统当前资源剩余量，若大于，将就绪进程状态设置为阻塞态，然后查找就绪队列中是否还有就绪进程，若有，则选择一个就绪进程，继续执行，若没有就绪进程，则表示发生死锁。

若不大于，则给满足该进程的申请量，并将其自愿申请量的变量设为0。

接着再进行判断该进程是否得到全部所需资源，若没有，则选择就绪队列中一个就绪进程，若全部得到，归还该进程所占有的全部资源给系统，并将该进程设置为完成态。

此时，再进行检查有无等待态的进程，若没有，则选择就绪队列中一个就绪进程，若有，则顺序检查等待进程，判断系统现有资源能满足某一等待进程，若能，则将该等待进程状态设置为就绪态，若没有，查找就绪队列中是否还有就绪进程，若有，则选择一个就绪进程，继续执行，若没有就绪进程，则表示发生死锁。

银行家算法：运用取余的方法，轮询各个进程，选择处于就绪状态的进程之一，然后输入该进程的当前资源申请量apply，判断该申请量是否大于系统当前资源剩余量，若大于，将就绪进程状态设置为阻塞态，然后查找就绪队列中是否还有就绪进程，若有，则选择一个就绪进程，继续执行，若没有就绪进程，则表示发生死锁。

若不大于，则假定满足该进程的申请量，并将其资源申请量的变量设为0，表示系统资源的变量减少相应的该进程的资源申请量，然后系统资源暂时用一个变量current保存起来。

将分配后系统剩余的资源数量与各进程的剩余需求量比较寻找一个系统能满足其需求的进程，每找一次，都要计数，用num变量，若找到，在标记数组a[SIZE]中进行相应标记，同时没找到一个都要进行一次对标记数组的循环测试，若测试到所有项都进行了标记，则退出循环，说明此次分配是安全的，若找不到，测试num的值，（对于确定数目的并发进程，其最大分配安全的循环次数<=SIZE!）。

实验四 死锁一. 死锁的避免（一）实验目的当系统的总资源数m 小于或等于所有进程对资源的最大需求n S n i i −∑=1时，就可能产生死锁。

死锁会引起计算机系统的瘫痪。

银行家算法是在实现资源分配时避免死锁的一个著名算法，该算法是在能确保系统处于安全状态时才把资源分配给申请者。

通过本实验使学生能进一步理解死锁的概念，并能选择一个算法来避免死锁。

（二）实验题目系统中有m 个同类资源被n 个进程共享，每个进程对资源的最大需求数分别为S 1, S 2,…,S n ，且Max(S i )<=m, (i=1,2,…n)。

进程可以动态地申请资源和释放资源。

编写一个程序，实现银行家算法，当系统将资源分配给某一进程而不会死锁时，就分配之。

否则，推迟分配，并显示适当的信息。

（三）数据结构和操作说明参照教材上有关银行家算法的资源分配表，设计适当的数据结构。

进程要分配的资源数可由随机数决定或命令行输入，但要注意数据的有效范围。

（四）实验报告要求画出实现银行家算法的程序框图，说明数据结构。

在每当进程要分配资源时以及释放资源后，打印输出资源分配或释放后的分配情况表，如可能产生死锁，显示适当信息；如不会产生死锁，更新系统的资源分配状态表。

二． 死锁的检测（一）实验目的采用银行家算法来预防死锁是可靠的，但也是非常保守的，因为它限制了进程对资源的存取，从而降低了进程的并发运行程度。

死锁检测并不限制进程对资源的申请，只要有，就分配，但这也可能造成死锁。

但由于死锁并不是经常发生的，故大大提高了系统运行的效率。

通过本实验，可使学生进一步加深理解和掌握死锁的检测算法。

（二）实验题目分别使用检测“进程—资源循环等待链”的方法和Coffman 的算法来检测进程的死锁状态。

对于相同的进程资源分配、占用次序，比较两个算法的结果。

（三）数据结构Coffman 的死锁检测算法的数据结构参考书本4.7节图4-13的资源占用矩阵、进程等待资源矩阵Q 、资源总数向量和可用资源向量W 。

什么是死锁？如何避免死锁的算法所谓死锁：是指两个或两个以上的进程在执⾏过程中，因争夺资源⽽造成的⼀种互相等待的现象，若⽆外⼒作⽤，它们都将⽆法推进下去。

此时称系统处于死锁状态或系统产⽣了死锁，这些永远在互相等待的进程称为死锁进程。

由于资源占⽤是互斥的，当某个进程提出申请资源后，使得有关进程在⽆外⼒协助下，永远分配不到必需的资源⽽⽆法继续运⾏，这就产⽣了⼀种特殊现象死锁。

虽然进程在运⾏过程中，可能发⽣死锁，但死锁的发⽣也必须具备⼀定的条件，死锁的发⽣必须具备以下四个必要条件。

1）互斥条件：指进程对所分配到的资源进⾏排它性使⽤，即在⼀段时间内某资源只由⼀个进程占⽤。

如果此时还有其它进程请求资源，则请求者只能等待，直⾄占有资源的进程⽤毕释放。

2）请求和保持条件：指进程已经保持⾄少⼀个资源，但⼜提出了新的资源请求，⽽该资源已被其它进程占有，此时请求进程阻塞，但⼜对⾃⼰已获得的其它资源保持不放。

3）不剥夺条件：指进程已获得的资源，在未使⽤完之前，不能被剥夺，只能在使⽤完时由⾃⼰释放。

4）环路等待条件：指在发⽣死锁时，必然存在⼀个进程——资源的环形链，即进程集合{P0，P1，P2，···，Pn}中的P0正在等待⼀个P1占⽤的资源；P1正在等待P2占⽤的资源，……，Pn正在等待已被P0占⽤的资源。

1) 预防死锁。

这是⼀种较简单和直观的事先预防的⽅法。

⽅法是通过设置某些限制条件，去破坏产⽣死锁的四个必要条件中的⼀个或者⼏个，来预防发⽣死锁。

预防死锁是⼀种较易实现的⽅法，已被⼴泛使⽤。

但是由于所施加的限制条件往往太严格，可能会导致系统资源利⽤率和系统吞吐量降低。

a 破坏互斥条件 如果允许系统资源都能共享使⽤，则系统不会进⼊死锁状态。

但有些资源根本不能同时访问，如打印机等临界资源只能互斥使⽤。

所以，破坏互斥条件⽽预防死锁的⽅法不太可⾏，⽽且在有的场合应该保护这种互斥性。

b 破坏不剥夺条件 当⼀个已保持了某些不可剥夺资源的进程，请求新的资源⽽得不到满⾜时，它必须释放已经保持的所有资源，待以后需要时再重新申请。

实验四银行家算法一、实验学时2 学时二、实验目的与要求（1）了解多道程序系统中，多个进程并发执行的资源分配。

（2）掌握死锁产生的原因、产生死锁的必要条件和处理死锁的基本方法。

（3）掌握预防死锁的方法，系统安全状态的基本概念。

（4）掌握银行家算法，了解资源在进程并发执行中的资源分配策略。

（5）理解避免死锁在当前计算机系统中不常使用的原因。

三、实验内容在多道程序系统中，虽可借助于多个进程的并发执行来改善系统的资源利用率，提高系统的吞吐量，但可能发生一种危险——死锁。

死锁是指多个进程在运行中因争夺资源而造成的一种僵局，当进程处于这种僵持状态时，若无外力作用，他们都将无法再向前推进。

银行家算法是最具代表性的避免死锁的算法，它的基本思想是分配资源之前，判断系统是否是安全的，若是才分配资源。

设计一个n个并发进程共享m个系统资源的程序实现银行家算法。

要求包含：1、一个简单的界面。

2、显示或修改当前系统资源情况。

3、添加进程对资源的需求。

4、判断是否存在死锁，若无死锁则显示其安全序列。

5、若产生死锁，制定策略，以最小的代价解决死锁问题。

四、实验重点、难点银行家算法的实现、解除死锁的策略。

五、实验教学方法集中讲授，讨论需求，由学生独立完成六、运行结果分析1、给出一组初始数据。

2、根据给出的数据得出运行结果。

3、分析结果是否符合原理。

4、产生死锁时你采用的策略是什么？为什么？5、分析所写程序还有什么可以改进的地方。

七、关键数据结构及源代码1、带注释的源代码。

实验四银行家算法模拟【实验目的】（1）进一步理解利用银行家算法避免死锁的问题；（2）在了解和掌握银行家算法的基础上，编制银行家算法通用程序，将调试结果显示在计算机屏幕上，再检测和笔算的一致性。

（3）理解和掌握安全序列、安全性算法【实验要求】（1）了解和理解死锁；（2）理解利用银行家算法避免死锁的原理；（3）会使用某种编程语言。

【实验原理】一、安全状态指系统能按照某种顺序如<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。

死锁产⽣条件以及预防和处理算法 ⼀、死锁的概念 在多道程序系统中，虽可借助于多个进程的并发执⾏，来改善系统的资源利⽤率，提⾼系统的吞吐量，但可能发⽣⼀种危险━━死锁。

所谓死锁(Deadlock),是指多个进程在运⾏中因争夺资源⽽造成的⼀种僵局(Deadly_Embrace),当进程处于这种僵持状态时，若⽆外⼒作⽤，它们都将⽆法再向前推进。

⼀组进程中，每个进程都⽆限等待被该组进程中另⼀进程所占有的资源，因⽽永远⽆法得到的资源，这种现象称为进程死锁，这⼀组进程就称为死锁进程。

⼆、死锁产⽣的原因 产⽣死锁的原因主要是： （1）因为系统资源不⾜。

（2）进程运⾏推进的顺序不合适。

（3）资源分配不当等。

如果系统资源充⾜，进程的资源请求都能够得到满⾜，死锁出现的可能性就很低，否则就会因争夺有限的资源⽽陷⼊死锁。

其次，进程运⾏推进顺序与速度不同，也可能产⽣死锁。

产⽣死锁的四个必要条件： （1）互斥条件：⼀个资源每次只能被⼀个进程使⽤。

（2）请求与保持条件：⼀个进程因请求资源⽽阻塞时，对已获得的资源保持不放。

（3）⾮抢占:进程已获得的资源，在末使⽤完之前，不能强⾏抢占。

（4）循环等待条件:若⼲进程之间形成⼀种头尾相接的循环等待资源关系。

三、死锁处理⽅法： （1）可使⽤协议以预防或者避免死锁，确保系统不会进⼊死锁状态； （2）可允许系统进⼊死锁状态，然后检测他，并加以恢复； （3）可忽视这个问题，认为死锁不可能发⽣在系统内部。

四、死锁预防 1、互斥：对于⾮共享资源，必须要有互斥条件； 2、占有并等待： 为了确保占有并等待条件不会出现在系统中，必须保证：当⼀个进程申请⼀个资源时，它不能占有其他资源。

⼀种可以使⽤的协议是每个进程在执⾏前申请并获得所有资源，可以实现通过要求申请资源的系统调⽤在所有的其他系统调⽤之前执⾏。

3、⾮抢占： 为了确保第三个条件不成⽴，可以使⽤如下协议：如果⼀个进程占有资源并申请另⼀个不能⽴即分配的资源，那么其现已分配资源都可被抢占； 4、循环等待： 为了确保循环等待条件不成⽴，⼀种可⾏的算法是：对所有资源进程排序，且要求每个进程按照递增顺序来申请进程。