死锁相关算法设计报告

1、操作系统课程设计报告题目： 死锁相关算法院系：信息学院班级：信管11-2姓名：王裕辰学号：1101051024指导教师： 赵 华 一、 概述本次设计的程序主要功能是实现银行家算法、安全性算法、死锁检测算法，并根据输入的数据和相应的调度算法计算每个进程的调度结果，根据输入的数据，判断系统安全状态，判断进程的资源请求是否可以被满足，判定系统是否为死锁状态，然后输出各种判定结果（是否安全、安全序列、是否死锁、是否允许分配）。本程序根据当前进程对资源的占用和未分配资源的数量，判断当前系统是否处于安全状态，判定当前状态下进程对资源的请求是否能够被满足，然后判断当前系统是否产生死锁，这给进程的运行提供了较

2、宽松的环境，有利于进程的并发执行。通过对银行家算法，安全性算法和死锁检测算法的模拟，加深了对这三种算法的理解，更好地掌握了死锁预防和检测的方法。二、设计的基本概念和原理（1）安全性算法安全状态：指系统能按某种进程顺序（P1，P2，Pn）（称< P1，P2，Pn >序列为安全序列），来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。如果系统无法找到这样一个安全序列，则称系统处于不安全状态。（2）银行家算法银行家算法把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。为保证资金的安

3、全，银行家规定： 当一个顾客对资金的最大需求量不超过银行家现有的资金时就可接纳该顾客； 顾客可以分期贷款，但贷款的总数不能超过最大需求量； 当银行家现有的资金不能满足顾客尚需的贷款数额时，对顾客的贷款可推迟支付，但总能使顾客在有限的时间里得到贷款； 当顾客得到所需的全部资金后，一定能在有限的时间里归还所有的资金.操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程本次申请的资源数是否超过了该资源所剩余的总量。若超过则拒绝分配资

4、源，若能满足则按当前的申请量分配资源，否则也要推迟分配。（3）死锁检测算法 在资源分配图中，找出一个既不阻塞又非独立的进程结点Pi。在顺利地情况下，Pi可获得所需资源而继续运行，直至运行完毕，再释放其所占有的全部资源，这相当于消去Pi所有的请求边和分配边，使之成为孤立的结点。 重复上述过程，在进行一系列的简化后，若能消去图中所有的边，使所有的进程结点都成为孤立结点，则称该图是可简化的；若不能通过任何进程使该图完全简化，则称该图是不可完全简化的。 当且仅当某状态的资源分配图是不可完全简化时，此状态为死锁状态。三、总体设计本程序才用了结构化程序设计方法，将程序进行了模块化划分。首先定义几种算法中的

5、数据结构，用数组来存放资源。用用户输入的数据来初始化相关数组，以此来表示不同种类、不同进程请求的资源数量。首先调用安全性算法检测当前系统是否处于安全状态。然后用户输入请求向量，调用银行家算法判断是否允许分配。本程序包括以下三个模块：（1） 预定义模块定义程序所用到的头文件并定义了进程数量和临界资源的种类。（2） 主程序模块包括以下五个步骤 输入当前系统状态 调用安全性算法检测系统是否处于安全状态。若安全执行步骤，否则退出程序。 输入请求向量 调用银行家算法对资源矩阵进行假定修改 调用安全性算法判断上述假定修改后系统是否安全，若安全系统允许分配，否则不允许。（3） 其他函数模块定义安全性算法、银

6、行家算法和死锁检测算法。程序流程图：四、详细设计每个模块的代码及分析如下：1、 预定义模块#include "stdafx.h"#include <iostream>#define m 3 /资源类数#define n 5 /进程个数2、 主程序模块int main(int argc, char* argv)int Availablem,Maxnm,Allocationnm,Neednm,Requestnm;/Available可用资源向量 Max最大需求矩阵 Allocation分配矩阵 Need需求矩阵 Requestij 进程i请求资源j的数量int i,

7、j,P,flag,bank;/bank表示调用银行家算法的返回值，为1表示分配完成，为0表示未分配;flag=1;/输入相关数据 cout<<" 死锁相关算法 "<<endl;cout<<" 请输入数据："<<endl; cout<<endl<<"输入最大需求矩阵："<<endl;for(i=0;i<n;i+)for(j=0;j<m;j+)cin>>Maxij; cout<<"输入分配矩阵："&l

8、t;<endl; for(i=0;i<n;i+)for(j=0;j<m;j+)cin>>Allocationij;cout<<"输入需求矩阵："<<endl; for(i=0;i<n;i+)for(j=0;j<m;j+)cin>>Needij; cout<<"输入可利用资源向量："<<endl;for(i=0;i<m;i+)cin>>Availablei;/判断当前系统是否安全Safealg(Available,Max,Allocati

9、on,Need,flag); if(flag=1)/如果当前系统安全可以输入请求向量cout<<"输入请求向量："<<endl;cout<<"进程："<<endl;cin>>P;cout<<"输入"<<"P"<<P<<"进程"<<"请求资源的数量"<<endl;for(j=0;j<m;j+) cin>>RequestPj;els

10、e/ 否则提示用户，退出程序 cout<<"无法分配资源"<<endl;return 0;/调用银行家算法,对当前请求进行假定修改bank=Banker(Available,Allocation,Need,Request,P); if(bank=0)return 0;/判断是否安全，flag=1表示分配后系统处于安全状态，flag=0表示分配后系统不安全 Safealg(Available,Max,Allocation,Need,flag); if(flag=0)cout<<"系统不分配资源"<<endl;

11、else cout<<"系统允许分配资源"<<endl;3、 其它函数模块void Safealg(int avail,int maxm,int allocm,int needm,int &Flag)/安全性算法/avail可用资源向量 max最大需求矩阵 alloc分配矩阵 need需求矩阵 Flag引用用于标记是否安全 int i,j,k,flagSafe,flagNeed,count;int Workm,Finishn,safen;/Work工作向量 Finish表示系统是否有足够资源是进程执行完成 safe存放安全序列count=0;

12、 for(j=0;j<m;j+)/ 将avail赋值给WorkWorkj=availj;for(i=0;i<n;i+)/ 将所有Finish全部置为0Finishi=0;for(k=0;k<n;k+)for(i=0;i<n;i+) flagNeed=1; for(j=0;j<m;j+) / 找到Need小于等于Work的进程 flagNeed=1 表示找到 flagNeed=0表示未找到 if(needij>Workj) flagNeed=0; break; if(flagNeed=1&&Finishi=0)/ 找到Need小于等于Work的

13、进程后 若此进程的Finish为0，则分配资源，进程执行结束回收资源。 Finishi=1; safecount+=i; /将进程放入安全序列数组中 for(j=0;j<m;j+) Workj+=allocij; flagSafe=1; /判断是否为安全状态 flagsafe为1表示安全，为0表示不安全for(i=0;i<n;i+) if(Finishi=0) flagSafe=0;cout<<"当前系统处于不安全状态"<<endl;break; if(flagSafe=1)cout<<"安全序列为： "&

14、lt;<endl; for(i=0;i<count;i+) cout<<"P"<<safei<<" " cout<<endl<<"系统处于安全状态"<<endl;Flag=flagSafe;int Banker(int avail,int allocm,int needm,int reqm,int p)/ 银行家算法 / avail可用资源数 alloc分配矩阵 need需求矩阵 req请求向量 p第p个进程请求分配资源 int j; for(j=0;

15、j<m;j+) /判断请求向量是否大于第p个进程的需求矩阵if(reqpj>needpj) cout<<"请求资源数已经超过最大值"<<endl; return 0; for(j=0;j<m;j+)/判断请求向量是否大于可用资源数 if(reqpj>availj) cout<<"没有足够资源，进程需等待"<<endl;return 0;for(j=0;j<m;j+) /进行修改 availj-=reqpj; /可用资源数减去请求数量allocpj+=reqpj;/已分配资源数量

16、加上请求数量needpj-=reqpj;/需求数量减少请求数量 cout<<endl<<endl<<"若满足请求，" return 1；五、测试与数据分析假定系统中有五个进程P0，P1,P2，P3,P4和三类资源A，B，C，各种资源的数量分别为10、5、7，在T0时刻的资源分配情况如下图所示资源情况进程 MaxAllocationNeedAvailableA B CA B CA B CA B CP07 5 30 1 07 4 33 3 2P13 2 22 0 01 2 2P29 0 23 0 26 0 0P32 2 22 1 10 1 1

17、P44 3 30 0 24 3 1（1） 将上述矩阵中的数据输入进程，调用安全性算法判断T0时刻系统是否安全，若安全，输出安全序列，执行（2）步；否则，退出程序。（2） P1请求资源：P1发出请求向量Reques1（1,0,2），系统调用银行家算法进行检查和修改，然后调用安全性算法，判断此时系统是否安全。若安全，输出安全序列，允许分配资源；否则，不允许分配，退出程序。（3） P4请求资源：P4发出请求向量Request4（3,3,0），统调用银行家算法进行检查和修改，然后调用安全性算法，判断此时系统是否安全。若安全，输出安全序列，允许分配资源；否则，不允许分配，退出程序。六、完成的情况、简要的

18、使用说明本程序经过了调试，能够正常运行，并能够得到正确的结果。但使用时应注意以下几个问题：1、 程序运行开始是必须按照规定的形式输入Max，Allocation，Need，和Available矩阵。2、 程序中的进程数和资源数被定义为常量，用户无法在程序中设定当前系统中的进程数和资源数，但可以在代码中进行修改。3、 只要用户输入某时刻的资源分配情况，程序都会自动检查当前系统是否安全。进程请求资源时，需要先输入进程号在输入请求向量。七、结果分析运行程序时出现下图，提示用户输入相关数据按照五测试与数据分析中的数据输入程序，程序自动调用安全性算法判断当前是否安全，输出结果如下图所示输入进程1，请求向量（1,0,2）调用银行家算法对数据进行修改，再次调用安全性算法检查，判断是否分配资源。输入进程4，请求向量（3,3,0）调用银行家算法对数据进行修改，再次