06并发性死锁和饥饿

计算机科学系操作系统课程组李才伟&凌应标制作@2016年4月1第6章并发性：死锁和饥饿（资源管理）主要内容死锁的原理、预防、避免和检测管理资源的策略和方法死锁的综合策略哲学家就餐问题Unix、Linux、Solaris、Windows等主流操作系统的并发机制计算机科学系操作系统课程组李才伟&凌应标制作@2016年4月2第一讲死锁死锁原理死锁（deadlock）概念资源、资源分配图与死锁定理死锁的条件死锁预防死锁避免进程启动拒绝资源分配拒绝(银行家算法)死锁检测与恢复综合策略6.1死锁原理计算机科学系操作系统课程组李才伟&凌应标制作@2016年4月46.1.1死锁的概念死锁(deadlock)：一个进程集合中的每个进程都在等待只能由该集合中的其他一个进程才能引发的事件（释放占有资源/进行某项操作）死锁是多个进程因竞争资源且推进顺序不合理而造成的一种僵局，若无外力作用，这些进程将永远不能再向前推进计算机科学系操作系统课程组李才伟&凌应标制作@2016年4月5联合进程图联合进程图(jointprogressdiagram)是一种记录进程共享资源的历史和分析死锁的工具二个进程的联合进程图是一个二维网格，三个进程的联合进程图是一个三维网格，如此类推四种区域安全区域（白色）敏感区域（fatalregion，致命区域）（黑色）死锁区域（黑色）不可达区域（彩色）计算机科学系操作系统课程组李才伟&凌应标制作@2016年4月6可能死锁的进程举例进程P：…获得A…获得B…释放A…释放B…进程Q：…获得B…获得A…释放B…释放A…计算机科学系操作系统课程组李才伟&凌应标制作@2016年4月7联合进程图—死锁的例子P与Q想要AP与Q想要B死锁释放A获得A获得B释放B获得A获得B释放A释放BP的进展Q的进展123465P与Q想要A&B请求A请求B请求A请求B计算机科学系操作系统课程组李才伟&凌应标制作@2016年4月8不会死锁的进程举例进程P：…获得A…释放A…获得B…释放B…进程Q：…获得B…获得A…释放B…释放A…计算机科学系操作系统课程组李才伟&凌应标制作@2016年4月9联合进程图—无死锁的例子释放A获得A获得B释放B获得A获得B释放A释放BP的进展Q的进展123465请求A请求B请求A请求BP与Q想要BP与Q想要A计算机科学系操作系统课程组李才伟&凌应标制作@2016年4月106.1.1可重用资源资源分类可重用资源（如图书）与可消费资源（如食物）可剥夺资源（如处理机、内存等）与不可剥夺资源（如打印机、表、队列、信号量等）永久性资源与临时性资源可重用资源（reusableresource）一次只能供一个进程安全地使用，且不会由于使用而耗尽（消失）的资源可以获得、使用和释放，能够再次被使用例子：处理器、I/O通道、主存和辅存、设备，文件、数据库、信号量等数据结构计算机科学系操作系统课程组李才伟&凌应标制作@2016年4月11涉及可重用资源死锁的例子破坏环路等待条件计算机科学系操作系统课程组李才伟&凌应标制作@2016年4月126.1.2可消费资源可消费/消耗资源（consumableresource）可以创建(生产)并且可以销毁(消费)的资源数目没有限制，当一个进程得到一个可消费资源时，这个资源就不再存在了例子：中断、信号、消息、I/O缓冲区中的信息计算机科学系操作系统课程组李才伟&凌应标制作@2016年4月13涉及消耗性资源死锁的例子（消息）P1:…receive(P2);…send(P2,M1);…P2:…receive(P1);…send(P1,M2);…计算机科学系操作系统课程组李才伟&凌应标制作@2016年4月操作系统检测、预防和避免死锁的方法原则资源分配策略不同的方案主要优点主要缺点预防保守，预提交(undercommits)资源一次性请求所有资源对执行单一突发行为的进程有效不需抢占低效延时进程的初始化进程必须知道未来的资源请求抢占便于用于状态易保存和恢复的资源过多的不必要抢占资源排序通过编译时检测可实施由于问题已在系统设计时解决，不需运行时再计算不允许增加资源请求避免位于检测和预防中间操纵以发现至少一条安全路径不需抢占OS必须知道未来的资源请求进程可能被长期阻塞检测非常自由；尽可能地准许请求的资源周期性地调用以测试死锁不会延时进程的初始化易于在线处理丢失固有抢占计算机科学系操作系统课程组李才伟&凌应标制作@2016年4月156.1.3资源分配图resourceallocationgraph用有向图描述的进程死锁模型表示法资源类（资源的不同类型）：方框资源实例（存在于每个资源类中）：黑圆点进程：圆圈中加进程名分配边：资源实例指向进程的一条有向边申请边：进程指向资源类的一条有向边计算机科学系操作系统课程组李才伟&凌应标制作@2016年4月16死锁定理如果资源分配图中没有环路，则系统中没有死锁，如果图中存在环路则系统中可能存在死锁如果每个资源类中只包含一个资源实例，则环路是死锁存在的充分必要条件计算机科学系操作系统课程组李才伟&凌应标制作@2016年4月资源分配图例计算机科学系操作系统课程组李才伟&凌应标制作@2016年4月186.1.4死锁的条件死锁的三个必要条件互斥条件指进程对所分配到的资源进行排他性使用，即在一段时间内某资源只由一个进程占有如果此时还有其他进程要求该资源，要求者只能阻塞，直至占有该资源的进程用毕释放占有且等待条件进程已经占有至少一个资源，但可以提出新的资源要求若该资源已被其它进程占有，则请求进程阻塞，同时对已经获得的其它资源保持不放不可剥夺/抢占（preemption）条件进程已获得的资源在未使用完之前不能被剥夺，只能在使用完时由自己释放计算机科学系操作系统课程组李才伟&凌应标制作@2016年4月19死锁的条件(续)环路等待条件资源分配图中存在环路，即进程集合{P0,P1,P2,…,Pn}(n=2)中的P0正在等待一个P1占用的资源；P1正在等待P2占用的资源，……，Pn正在等待已被P0占用的资源死锁的充分必要条件互斥占有且等待不可抢占循环等待计算机科学系操作系统课程组李才伟&凌应标制作@2016年4月206.2死锁预防四类方法鸵鸟算法：对死锁视而不见预防死锁避免死锁检测死锁死锁预防(deadlockprevention)通过破坏产生死锁的四个条件中的一个或多个条件，保证不会发生死锁计算机科学系操作系统课程组李才伟&凌应标制作@2016年4月216.2.1破坏互斥条件方法允许多个进程同时使用资源适用条件资源的固有特性允许多个进程同时使用（如文件允许多个进程同时读）借助特殊技术允许多个进程同时使用（如打印机借助Spooling技术）缺点不适用于绝大多数资源计算机科学系操作系统课程组李才伟&凌应标制作@2016年4月226.2.2破坏占有且等待条件方法禁止已拥有资源的进程再申请其他资源，如要求所有进程在开始时一次性地申请在整个运行过程所需的全部资源；或申请资源时要先释放其占有资源后，再一次性申请所需全部资源优点简单、易于实现、安全缺点进程延迟运行资源严重浪费计算机科学系操作系统课程组李才伟&凌应标制作@2016年4月236.2.3破坏不可剥夺条件方法一个已经占有了某些资源的进程，当它再提出新的资源请求而不能立即得到满足时，必须释放它已经占有的所有资源，待以后需要时再重新申请OS可以剥夺一个进程占有的资源，分配给其他进程适用条件资源的状态可以很容易地保存和恢复(如CPU)缺点实现复杂、代价大，反复申请/释放资源、系统开销大、降低系统吞吐量6.2.4破坏环路等待条件方法要求每个进程任何时刻只能占有一个资源，如果要申请第二个则必须先释放第一个（不现实）对所有资源按类型进行线性排队，进程申请资源必须严格按资源序号递增的顺序（可避免循环等待）缺点很难找到令每个人都满意的编号次序，类型序号的安排只能考虑一般作业的情况,限制了用户简单、自主地编程易造成资源的浪费（会不必要地拒绝对资源的访问）可能低效（会使进程的执行速度变慢）计算机科学系操作系统课程组李才伟&凌应标制作@2016年4月25第二讲死锁避免拒绝启动进程策略拒绝资源请求策略——银行家算法死锁检测和恢复综合策略计算机科学系操作系统课程组李才伟&凌应标制作@2016年4月266.3死锁避免deadlockavoidance不需事先采取限制措施破坏产生死锁的必要条件，而是在资源的动态分配过程中，采用某种策略防止系统进入不安全状态，从而避免发生死锁两种死锁避免的方法：不启动其资源请求会导致死锁的进程不允许会导致死锁的进程资源请求计算机科学系操作系统课程组李才伟&凌应标制作@2016年4月276.3.1进程启动拒绝模型n个进程和m种资源系统资源(Resource)总量向量R=(R1,R2,…,Rm)，Rj为第j种资源的总数系统当前可用(aVailable)资源总量向量V=(V1,V2,…,Vm)，Vj为第j种资源的剩余数进程-资源需求(Claim)矩阵C，Cij=进程i对资源j的请求数进程-资源分配(Allocation)矩阵A，Aij=当前已经分配给进程i的资源j数C11,C12,…,C1mC21,C22,…,C2m…Cn1,Cn2,…,CnmA11,A12,…,A1mA21,A22,…,A2m…An1,An2,…,Anm计算机科学系操作系统课程组李才伟&凌应标制作@2016年4月28进程启动拒绝系统正常状态下，模型有如下性质：Rj=Vj+(A1j+A2j+…+Anj)，对所有的j=1,2,…,mCij≤Rj，对所有的i=1,2,…,n，j=1,2,…,mAij≤Cij，对所有的i=1,2,…,n，j=1,2,…,m进程启动拒绝策略若Rj≥Cn+1,j+(C1j+C2j+…+Cnj)，j=1,2,…,m，则允许启动进程Pn+1否则系统不启动进程Pn+1本策略不能保证资源的最优使用率，但可以保证系统现有进程不会发生死锁计算机科学系操作系统课程组李才伟&凌应标制作@2016年4月296.3.2资源分配拒绝资源分配拒绝策略是Dijkstra受银行资金借贷管理的启发于1965年提出的模型系统状态：由资源总量向量R=(R1,R2,…,Rm)、系统可用资源总量向量V=(V1,V2,…,Vm)、进程-资源需求矩阵C和进程-资源分配矩阵A表示安全状态：至少存在一个执行时序，使当前所有进程都能运行到结束状态不安全状态：不存在一个执行时序，使当前所有进程都能运行到结束状态计算机科学系操作系统课程组李才伟&凌应标制作@2016年4月30安全状态举例R1R2R3R1R2R3R1R2R3R1R2R3R1R2R3P1P2P3P4P1P2P3P4P1P2P3P4需求矩阵C分配矩阵A矩阵C-A(a)初始状态资源向量R可用向量V322613314422100612211002222001103420936011计算机科学系操作系统课程组李才伟&凌应标制作@2016年4月31安全状态举例（续）R1R2R3R1R2R3R1R2R3R1R2R3R1R2R3P1P2P3P4P1P2P3P4P1P2P3P4需求矩阵C分配矩阵A矩阵C-A(b)P2运行到完成+322000314422100000211002222000103420936623613010资源向量R可用向量V计算机科学系操作系统课程组李才伟&凌应标制作@2016年4月32安全状态举例（续）R1R2R3R1R2R3R1R2R3P1P2P3P4P1P2P3P4P1P2P3P4需求矩阵C分配矩阵A矩阵C-A(c)P1运行到完成资源向量R可用向量V00000031442200