操作系统之银行家算法检测死锁.doc

操作系统实验 利用银行家算法避免死锁 实验报告 实验题目：利用银行家算法避免死锁 实验内容：编程实现银行家算法，要求能够输入资源数和作业数，输出进程的安全状况。若进程安全，输出安全序列。 实验目的：通过实验加强对银行家算法避免死锁的理解和掌握。 实验过程： 基本思想：银行家算法的基本思想是分配资源之前,判断系统是否是安全的;若是,才分配。详细如下： 设进程i提出请求Request [j]，则银行家算法按如下规则进行判断。 如果Request [i][j]= Need[i][j]，则转(2)；否则出错。　 (2)如果Request [i] [j]= Available[j]，则转(3)；否则出错。 (3)系统试分配资源，修改相关数据： Available[j]=Available[j]-Request[i][j]; Allocation[i][j]=Allocation[j]+Request[i][j]; 系统执行安全性检查，如安全，则分配成立；否则试分配作废，系统恢复原状，进程等待。 安全性检查算法 (1)设置两个工作向量Work=Available;Finish[i]=false　 (2)从进程集合中找到一个满足下述条件的进程，　　Finish==false;　　Need=Work;　　如找到，执行(3)；否则，执行(4)　　 (3)设进程获得资源，可顺利执行，直至完成，从而释放资源。　　Work+=Allocation　　Finish=true;　　GOTO step2　　 (4)如所有的进程Finish= true，则表示安全；否则系统不安全。 主要数据结构： 可利用资源向量Available。定义为一个一元数组，Available[j]=K表示系统中有j类资源K个。 最大需求Max。定义为一个n*m的矩阵，Max[i][j]=K表示进程i需要j资源的最大数目为K个。 分配矩阵Allocation。定义为一个n*m的矩阵，Allocation[i][j]=K表示进程i已经得到j资源K个。 需求矩阵Need。定义为一个n*m的矩阵，Need[i][j]=K表示进程i还需要j资源K个来完成任务。 输入、输出： 成功分配的例子：输入资源数2(各3)，进程数2，最大需求1 1，已分配 0 1。输出： 1 1 1 0 Max Allocation Need 进程名 A B A B A B 0 1 1 0 1 1 0 1 1 1 1 0 0 1 不安全，会出现死锁的：输入资源数2（各2），进程数2，最大需求3 3，已分配 0 0。输出： 3 3 0 0 Max Allocation Need 进程名 A B A B A B 0 3 3 0 0 3 3 1 3 3 0 0 3 3 没有安全序列 若输入时已分配大于最大需求：输入资源数1（5个资源），进程数1，Max=3 ，Allocation=5，则会产生提示，发生错误，申请的大于最大需求量。需要重新输入。 输入资源种数程序流程图 输入资源种数 输入资源名称 输入资源名称 输入资源数量 输入资源数量 输入进程数 输入进程数 输入最大需求矩阵 输入最大需求矩阵 输入已分配矩阵 输入已分配矩阵 判断已分配是否大于最大需求大于最大需求 判断已分配是否大于最大需求 小于最大需求 进行预分配 进行预分配 预分配失败，资源不分配安全性算法 预分配失败，资源不分配 安全性算法 未通过