第7讲死锁与银行家算法

操作系统华软软件学院软件工程系P1第七讲死锁与银行家算法华软软件工程系操作系统华软软件学院软件工程系P2►内容回顾操作系统概述进程及进程间的通信►软中断、管道通信►IPC机制、消息缓冲通信、共享内存通信、信号量集(PV操作)►本次课内容资源分配、死锁（银行家算法）主要内容操作系统华软软件学院软件工程系P3第一部分内容回顾•OS概述•用户界面•进程•进程间通信主要内容操作系统华软软件学院软件工程系P4内容回顾►操作系统概述从概念上讲述了操作系统的内涵从类型上介绍了操作系统的分类从技术上了解了操作系统的基础►用户界面介绍了各种操作界面(interface)程序界面：系统提供给编程人员的接口，也称系统调用界面。操作系统华软软件学院软件工程系P5内容回顾(2)►进程重点理解进程的概念：程序的一次运行过程理解进程控制块PCB的结构（Unix、Linux）以及作用掌握进程的三种基本状态及其转换，以及进程的创建、撤销、睡眠、唤醒掌握进程的同步与互斥，包括临界资源的概念►进程间通信软中断信号机制、管道通信（分类）IPC机制（消息缓冲、共享内存、信号量集）►掌握这些对象的创建、使用、撤销等操作►针对信号量集，需掌握信号量的PV操作操作系统华软软件学院软件工程系P6第二部分死锁与银行家算法•资源分配•死锁•处理机的多级调度•作业调度•进程调度主要内容操作系统华软软件学院软件工程系P7资源分配►资源分配的基本概念系统中所有进程共享并竞争系统中的所有资源操作系统对其所有的资源进行统一管理和分配用户进程提出资源需求申请，系统采用某种合理的规则分配资源目的：满足所有进程对资源的需求，并使系统资源的利用率达到最高►资源竞争的结果提高资源的利用率导致系统死锁操作系统华软软件学院软件工程系P8资源分配(2)►资源管理和分配的目标保证资源有高的利用率在合理的时间内,使各进程有获取所需资源的机会对“不可共享”的资源实行互斥使用防止因资源的不合理分配引起系统死锁►资源分配的基本方法静态资源分配：指作业级的资源分配。作业开始分配资源，作业结束释放资源。利用率低。动态资源分配：指进程级的资源分配。请求时分配，使用完释放。利用率高。操作系统华软软件学院软件工程系P9死锁►死锁的基本概念一组进程中，每个进程都无限等待被该组进程中另一进程所占有的资源,因而永远无法得到的资源,这种现象称为进程死锁,这一组进程称为死锁进程产生死锁的原因►系统资源不足►进程推进的顺序不合理进程死锁举例打印机摄像头进程A进程B占有占有等待等待操作系统华软软件学院软件工程系P10死锁(2)►产生死锁的必要条件：互斥:临界资源为互斥使用不可剥夺(非抢占)：一旦占有就直到使用完毕,由进程释放部分分配：允许部分申请，系统可部分分配环路（循环等待）：各进程对资源的占有和请求形成环路►解决死锁：破坏4个必要条件中的任何一个“互斥”条件一般是资源本身的特性，很难破坏一般从破坏其他三个条件考虑解决方案操作系统华软软件学院软件工程系P11死锁的处理方法►（1）预防死锁：通过某些限制条件的设置，去破坏产生死锁的四个必要条件；►（2）避免死锁：在资源的动态分配过程中，用某种方法去防止系统进入不安全状态；►（3）检测死锁：及时检测死锁的发生，并确定与之相关的进程、资源，从而采取措施清除死锁；►（4）解除死锁：撤消或挂起某些进程以回收一些资源，用于解脱另一些处于死锁的进程。操作系统华软软件学院软件工程系P12预防死锁破坏环路条件（静态资源分配）►有序资源分配法：要求将资源编号，资源请求只能按编号递增进行。►举例：有资源R1、R2、R3，比如有A、B两进程都请求R1、R2资源，必须先申请R1，成功后才可申请R2►缺点：不方便使用、资源利用率低操作系统华软软件学院软件工程系P13因此采用静态预防的方式来解决死锁问题牺牲了资源的利用率，而资源利用率的降低直接导致并发度的降低。为了保证资源的利用率，操作系统往往采用动态分配方式来避免死锁。死锁避免是指操作系统在动态分配过程中对每一次的分配都要采取某种策略去判断一下当前的分配有没有导致死锁的可能性，没有则实施分配，有则拒绝分配，从而动态地避免死锁的产生。操作系统华软软件学院软件工程系P14避免死锁—银行家算法设银行家有10万周转资金，P,Q,R分别需要8,3,9万元搞项目，如果P已申请到了4万，Q要申请2万，R要申请4万.Q1：客户要求分期贷款，一旦得到每期贷款，就能够归还贷款Q2：银行家应谨慎的贷款，防止出现坏帐什么是银行家问题？银行家-操作系统周转资金-系统资源贷款客户-进程当某进程请求分配资源时，系统假定先分配给它，之后若能找到一个进程完成序列（安全序列），说明系统是安全的，可进行实际分配；否则，让申请者等待。银行家算法的实现思想操作系统华软软件学院软件工程系P15算法原理►我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。►为保证资金的安全，银行家规定：(1)当一个顾客对资金的最大需求量不超过银行家现有的资金时就可接纳该顾客；(2)顾客可以分期贷款，但贷款的总数不能超过最大需求量；(3)当银行家现有的资金不能满足顾客尚需的贷款数额时，对顾客的贷款可推迟支付，但总能使顾客在有限的时间里得到贷款；(4)当顾客得到所需的全部资金后，一定能在有限的时间里归还所有的资金.操作系统华软软件学院软件工程系P16表示形式含义Available（可用资源数组）Available[j]＝k现有资源j的数目为kMax（最大需求矩阵）Max[i,j]＝k进程i对资源j的最大需求数目为kAllocation（分配矩阵）Allocation[i,j]＝k进程i当前已分得的资源j的数目为kNeed（需求矩阵）Need[i,j]＝k进程i尚需分配的资源j的数目为k银行家算法中的数据结构操作系统华软软件学院软件工程系P17►银行家算法当Pi发出资源请求，分配一个Request向量然后系统按下述流程进行执行：Requesti：是进程Pi的请求向量如果Requesti[j]=K，表示进程i需要K个Rj类型的资源。银行家算法实现过程操作系统华软软件学院软件工程系P18操作系统华软软件学院软件工程系P19安全性算法实现过程►安全性算法两个向量：Work和FinishWork表示系统可提供给进程继续运行所需的各类资源数目（即在分配过程中，系统的可用资源数）。初始值Work∶=Available;Finish表示系统是否有足够的资源分配给进程i，使之运行完成。初始值Finish[i]:=false当有足够资源分配给进程时Finish[i]:=true操作系统华软软件学院软件工程系P20操作系统华软软件学院软件工程系P21假定系统中有五个进程｛P0,P1,P2,P3,P4｝和三类资源｛A,B,C｝，各种资源的数量分别为10、5、7，在T0时刻的资源分配情况如下图所示。P4P3P2P1P0AvailableA,B,CNeedA,B,CAllocationA,B,CMaxA,B,C进程资源情况7,5,33,2,29,0,22,2,24,3,30,1,02,0,03,0,22,1,10,0,27,4,31,2,26,0,00,1,14,3,13,3,2银行家算法实例操作系统华软软件学院软件工程系P22（1）T0时刻系统是否安全？执行安全性算法进行检查：①向量初值Work:＝Available＝(3,3,2)；Finish[i]:＝false；（i＝0,1,…,4）②在进程集合中找到Need1＝(1,2,2)≤Work且Finish[1]＝false；③则设P1顺利执行完成，从而有：Work:＝Work＋Allocation1＝(3,3,2)＋(2,0,0)＝(5,3,2)Finish[1]:＝true银行家算法实例操作系统华软软件学院软件工程系P23Chapter3处理机调度与死锁FinishWork+AllocationAllocationNeedWorktrue532200122332P1AllocationNeedP0010743P1200122P2302600P3211011P4002431操作系统华软软件学院软件工程系P24Chapter3处理机调度与死锁FinishWork+AllocationAllocationNeedWorktrue743532211011P3true532200122332P1AllocationNeedP0010743P1200122P2302600P3211011P4002431操作系统华软软件学院软件工程系P25Chapter3处理机调度与死锁FinishWork+AllocationAllocationNeedWorktrue753743010743true743211011532true532200122332P0P3P1AllocationNeedP0010743P1200122P2302600P3211011P4002431操作系统华软软件学院软件工程系P26Chapter3处理机调度与死锁FinishWork+AllocationAllocationNeedWorktrue1055753true753010743743302600true743211011532true532200122332P0P2P3P1AllocationNeedP0010743P1200122P2302600P3211011P4002431操作系统华软软件学院软件工程系P27Chapter3处理机调度与死锁AllocationNeedP0010743P1200122P2302600P3211011P4002431true10570024311055P4FinishWork+AllocationAllocationNeedWorktrue1055753true753010743743302600true743211011532true532200122332P0P2P3P1操作系统华软软件学院软件工程系P28④发现：目前可执行的所有资源分配工作完成之后，各个进程对应的状态向量Finish[i]＝true；且对应于该向量置为“true”的进程编号依次为：1→3→0→2→4，故：系统存在安全序列{P1，P3，P0，P2，P4}所以，T0时刻系统处于安全状态！银行家算法实例操作系统华软软件学院软件工程系P29Chapter3处理机调度与死锁由分析知：执行完P1、P3的资源分配请求之后，系统可用的资源数量可以满足其它3个进程的资源请求，则此时的资源分配顺序已无关紧要。所以：安全序列可以不唯一！true10570024311055P4FinishWork+AllocationAllocationNeedWorktrue1055753true753010743743302600true743211011532true532200122332P0P2P3P1操作系统华软软件学院软件工程系P30（2）P1发出请求Request(1,0,2)，系统能分配资源吗？执行银行家算法：①Request1(1,0,2)≤Need1(1,2,2)；②Request1(1,0,2)≤Available(3,3,2)；③系统为P1进行预分配，并修改Available，Allocation1和Need1向量：银行家算法实例Request1(1,0,2)，Need1，Available操作系统华软软件学院软件工程系P31Available:＝Available－Request1＝(3,3,2)－(1,0,2)＝(2,3,0)Allocation1:＝Allocation1＋Request1＝(2,0,0)＋(1,0,2)＝(3,0,2)Need1:＝Need1－Request1＝(1,2,2)－(1,0,2)＝(0,2,0)银行家算法实例操作系统华软软件学