操作系统课件5_2.ppt

1、第五章 死锁与饥饿,5.1 死锁的概念 5.2 死锁的类型 5.3 死锁的条件 5.4 死锁的处理 5.5 资源分配图 5.6 死锁的预防 5.7 死锁的避免 5.8 死锁的发现 5.9 死锁的恢复 5.10 鸵鸟的算法 5.11 有关问题的讨论 5.12 饥饿与活锁 5.13 死锁与饥饿的例子,1,5.7 死锁避免,预防死锁的方法施加一些较强的限制条件使之在系统中不出现死锁 为提高系统资源的利用率，万一死锁有可能出现时，应避免发生，著名的算法为银行家算法 避免死锁的方法，施加的条件较弱，有可能获得较满意的系统性能 该方法把系统分为安全和不安全状态 只要系统始终处于安全状态便可避免死锁的发生,

2、2,5.7 死锁避免,5.7.1 安全状态与安全进程序列 5.7.2 银行家算法(bankers Algorithm),3,5.7.1 安全状态与安全进程序列,安全状态 系统处于安全状态是指系统中的所有进程能够按照某一种次序依次地进行完 安全状态形式化定义 ： 如果存在一个由系统中所有进程构成的安全进程序列，则称系统处于安全状态。 进程序列 是安全的, 则对每个进程pi(1in), 它尚需要的资源数不超过系统当前剩余资源数与所有进程pj(ji)当前占有资源数之和. 若系统中不存在这样一个安全序列，则称系统处于不安全状态。,4,5.7.1 安全状态与安全进程序列,图5-4给出了安全状态、不安全状

3、态、死锁状态之间的关系：,5,安全状态之例,设系统有三个进程P1、P2、P3，共有12台磁带机。在T0时刻资源状况如下表： 经分析，在T0时刻系统是安全的，存在一个序列，按此顺序每个进程可以顺利完成,6,由安全状态向不安全状态的转换,如不按照安全序列分配资源，系统可能会由安全状态向不安全状态转换，如在T0时刻后，P3请求1台，系统分配给P3，则系统进入不安全状态,7,银行家算法思想,将一定数量的资金供多个用户周转使用 当用户对资金的最大申请量不超过现存资金时可接纳一个新客户 客户可以分期借款，但借款总数不能超过最大的申请量。 银行家对客户的借款可推迟支付，但是能够使客户在有限的时间内得到借款

4、客户得到所有的借款后能在有限的时间内归还,8,银行家算法思想,有三个客户A、B、C, 共享10个现金单元（设一个现金单元为一万元），它们共需20个现金单元 括号外为已借款数，括号内为要求数,9,银行家算法思想,优点： 保证至少有一个进程得到所需的全部资源下进行资源分配，避免进程共享资源时可能产生的死锁 允许资源独占、不剥夺条件、请求和保持条件存在，比预防死锁的限制条件放松了，资源利用率提高。 系统可满足、也可拒绝进程提出的资源请求 当一个进程的资源请求将导致不安全状态时，系统拒绝其要求，直到该资源要求不会导致不安全状态时才满足此进程的资源要求（这主要由于其它进程释放了资源） 这样的系统总是处于

5、安全状态。,10,银行家算法思想,缺点： 要求被分配的每类资源的总数固定不变，难以做到。 要求用户数保持不变，在多道程序设计中难以做到 保证所有用户的要求在有限的时间内得到满足，但是实时用户要求更好的响应 要求用户说明最大资源要求，对用户来说不方便且困难,11,银行家算法,Bankers algorithm, E.W. Dijkstra. 进程：事先申明所需资源最大量（并不分配） 系统：对每个可满足的资源申请命令进行安全性检查。,12,银行家算法,设n为进程总数, m为资源类总数 数据结构: int Availablem; 当前各类资源中可用资源实例的个数 Availablej=k, 资源类r

6、j当前有k个资源实例可用，初始时Available为系统资源总量 int Claimn,m; 每个进程所需各类资源的资源实例最大量 int Allocationn,m; 记录每个进程占有各资源类中资源实例个数 初始时Allocationi,j= 0,13,银行家算法,数据结构: int Needn,m; 记录每个进程尚需各资源类中资源实例个数 Needi, j=k, 进程pi尚需资源类rj中k个资源实例 初始时Need=Claim int Requestn,m; 记录每个进程当前申请各资源类中资源实例个数 Requesti,j= k, 进程pi申请资源类rj中k个资源实例,14,银行家算法,为

7、了方便, 引入下述记法: 设X,Y为下标1到L的一维数组,C为常量 定义 XY 当且仅当 j，1jL, XjYj X=Y 当且仅当j，1jL, Xj = Yj X=C 当且仅当j，1jL, Xj = C,15,资源分配算法,Pi请求资源,RequestINeedI,请求超量，错返,RequestIAvailable,不满足，等待,Available:=Available-RequestI AllocationI:=AllocationI+RequestI NeedI:=NeedI-RequestI,安全,确认，pi继续,Available:=Available+RequestI Allocat

8、ionI:=AllocationI-RequestI NeedI:=NeedI+RequestI pi等待,F,T,F,T,T,F,16,安全性检测算法,为进行安全性检查, 需定义数据结构 int Workm; 记录可用资源 int Finishn; 记录进程是否可进行完,17,安全性检测算法,F,18,银行家算法例子5-4,R=A(10),B(5),C(7) P=p0,p1,p2,p3,p4 某时刻状态,19,银行家算法例子5-4,存在安全序列，处于安全状态,20,银行家算法例子5-4,设p1发出新申请, Request1=(1,0,2) 检查Request1Available是否满足, 由

9、于(1,0,2)(3,3,2), 假定分配资源, 系统状态变化为,21,银行家算法例子5-4,可找到一个进程安全序列, 系统实施资源分配 在新状态下 p4发出Request4=(3,3,0)，不能实施资源分配, 因为它超过了系统当前的资源数量 p0发出Request0=(0,2,0)，亦不能实施资源分配 虽然未超过系统当前的资源数量, 但资源分配将导制一个不安全的状态,22,银行家算法的保守性例5-5,考虑R=A(1),B(1)，P=p1,p2 进程p1和p2的活动序列分别为： p1：a, b, a, b p2：b, b, b, a, b, a p1和p2的资源最大需求量均为A(1)，B(1)

10、 假定某时刻系统状态如下：,23,银行家算法的保守性例5-5,此时p1的a被接受 其后可能：p1请求b, 或p2请求b 假定p2请求b, 因Request2=(0,1)Need2=(1,1)，该请求是合法的 又Request2=(0,1)Available=(0,1)，该请求系统能够满足,24,银行家算法的保守性例5-5,假定分配系统状态变化如下 运行安全性检测算法发现系统处于不安全状态，取消分配，p2等待,25,银行家算法的保守性例5-5,p1：a, b, a, b p2：b, b, b, a, b, a 实际上真正实施分配系统并不进入死锁状态，因为分配后按照 p2(b),p1(b),p1(

11、a),p1(b)p2 (b),p2(a),p2(b),p2(a)的次序两个进程可以执行完 这是一个p1和p2交叉执行的次序，不是一个顺序执行的次序 银行家算法不能判断 该例验证了前面的论断：死锁状态是不安全状态的真子集,26,5.8 死锁的检测,数据结构： Available: array1.mof integer; Allocation: array1.n,1.mof integer; Request: array1.n,1.mof integer; 临时变量： Work: array1.mof integer; Finish: array1.nof boolean;,27,5.8.1 死锁

12、检测算法,FinishI=true for allocationI=0,28,Remarks,1. 上述算法可以检测到参与死锁的全部进程，包括占有资 源和不占有资源的进程。 如果存在i，1=i=n，finishi=false，则系统处于死锁状态，且pi参与了死锁。 对当前不占有资源的进程直接将finish置为true 定理5-2：令p是系统中所有的进程集合，p是p的子集且为系统中占有资源的进程集合，则p中存在死锁的充要条件是p中存在死锁。,29,死锁例子,例子：R=A(7),B(2),C(6); P=p0,p1,p2,p3,p4,Allocation Request Available Wor

13、k Finish A B C A B C A B C A B C p0: 0 1 0 0 0 0 0 0 0 p1: 2 0 0 2 0 2 p2: 3 0 3 0 0 0 p3: 2 1 1 1 0 0 p4: 0 0 2 0 0 2,未死锁。 此时，Request2=(0,0,1), 死锁，参与死锁进程p1,p2,p3,p4,30,5.8.2 死锁检测时刻,何时进行死锁检测主要取决于两个因素 死锁发生的频率； 死锁所涉及的进程个数 通常在如下时刻进行死锁检测 进程等待时检测 定时检测 资源利用率降低时检测,31,5.9 死锁的恢复,重新启动(system restart) 简单，代价大，涉

14、及未参与死锁的进程 终止进程(terminating processes) 终止参与死锁的进程并收回所占资源, 死锁得以解除 两种处理策略: 一次性撤销所有参与死锁的全部进程, 方法简单, 代价较高 逐一撤销参与死锁的进程 按照某种算法选择一个参与死锁的进程 将其撤销并收回其占有的全部资源 判断是否还存在死锁, 如果是选择下一个将被淘汰的进程 重复直至死锁解除,32,5.9 死锁的恢复,剥夺资源(preempting resources) 剥夺死锁进程所占有的全部或部分资源 实现时分为两种情形: 逐步剥夺: 一次剥夺死锁进程所占有的一个或一组资源, 如死锁尚未解除继续剥夺, 直至死锁解除 一次

15、剥夺: 一次性地剥夺参与死锁进程所占有的全部资源 进程回退(process rollback) 让参与死锁的进程回退到以前没有发生死锁的某个点处, 并由此点开始继续, 希望进程交叉执行时不再发生死锁,33,5.10 鸵鸟算法(ostrich algorithm),仿鸵鸟遇到危险时将头埋在沙子里的传说而得名 对死锁采取视而不见的处理方法 是目前实际系统采用最多的策略 当死锁真正发生且影响系统正常运行时，手工干预重新启动,34,5.10 鸵鸟算法,视而不见 工程师观点(考虑死锁发生的频率,危害,处理代价) 死锁发生频率 危害 数学家观点 必须处理，无论代价如何,35,5.11 有关问题的讨论,关于

16、充要性算法 是一个复杂的问题, 不存在完美的死锁处理方法 关于两阶段封锁 在数据库管理系统中，一个原子事务可能涉及多个数据项 为保证数据完整性，在访问数据项之前需要对其加锁(共享锁或排它锁) 当多个事务同时运行时，加锁冲突可能会导致死锁,36,5.11 有关问题的讨论,关于可剥夺资源问题 进程不会因为处理机而死锁 当内存和虚存均不能满足时会发生死锁，如果有足够大的虚存，则不会死锁,37,5.11 有关问题的讨论,关于消耗型资源问题 前面有关死锁的讨论基本针对可重用资源(reusable resource) 这类资源一次只能分给一个进程，使用完后资源仍存在，可分配给其它进程使用，这是操作系统管理

17、的主要资源 另一类资源称为消耗型资源(consumable resource)，亦称生灭资源，指在系统运行过程中动态产生、动态消亡的资源 对消耗型资源死锁的处理比较困难,38,5.12 饥饿与饿死,当等待时间给进程推进和响应带来明显影响时，称发生了进程饥饿(starvation)，当饥饿到一定程度的进程所赋予的任务即使完成也不再具有实际意义时称该进程被饿死(starve to death). 活锁(live lock)： 在忙式等待条件下发生的饥饿，称为活锁,39,5.12 饥饿与饿死,饥饿：没有时间上界的等待，如： 排队等待 忙式等待 饿死：等待时间超过极限(deadline) 饿死 vs

18、死锁 死锁进程处于等待状态，饿死不然 死锁可以检测，饿死不然 饥饿和饿死与资源分配策略(policy)有关 防止饥饿与饿死从公平性考虑，确保所有进程不被忽视，如FCFS分配算法,40,5.12 饥饿与饿死,饿死与死锁有一定联系：都是竞争资源而引起，有明显差别，主要表现在： 从进程状态考虑，死锁进程都处于等待状态 死锁进程等待永远不会被释放的资源，饿死进程等待会被释放但却不会分配给自己的资源 死锁一定发生循环等待，饿死则不然，通过资源分配图可检测死锁，不能检测饿死 死锁一定涉及多个进程，饥饿或被饿死的进程可能只有一个,41,5.13 可复用资源死锁的静态分析,定义5-7 一次只能分配给一个进程使

19、用的资源称为可复用资源 如打印机、磁带机，释放后可分配给其它进程 定义5-8 由相对独立的若干资源构成的资源集合称为组合资源，其中每个相对独立的资源成为子资源 如：lp(2)，tape(3)，mouse(1)构成的资源集合lp(2)，tape(3)，mouse(1) lp(2)，tape(3)，mouse(1)为子资源 定义5-9 由相同类型的子资源构成的组合资源，称为同种组合资源,42,可复用资源死锁的静态分析算法(子资源仅含一个实例),条件：已知各个进程有关资源的活动序列； 判断：有无死锁可能性。 步骤1：以每个进程占有资源，申请资源作为一个状态， 记作：(pi：aj：ak1,akn)=(

20、进程：请求：占有); 步骤2：以每个状态为一个节点； 步骤3：如s1所申请资源为s2所占有，则由s1向s2画一有向 弧（相同进程间不画，因为一个进程不会等待自己 占有的资源）； 步骤4：找出所有环路；,可复用资源死锁的静态分析算法(子资源仅含一个实例),44,步骤5：判断环路上状态是否能同时到达，如是有死锁可能 性，否则无死锁可能性。 (1)环路中有相同进程，不能到达(一个进程不可以 处于两种状态)； (2)环路中有相同被占有资源，不能到达(一个简单 资源不可以分配给两个进程)。 如果发现环路，且环路无相同的进程，也没有相同的进程，不能判断是否发生死锁，需要进一步分析,死锁分析例子,死锁分析例

21、子,步骤3：如s1所申请资源为s2所占有，则由s1向s2画一有向弧,死锁分析例子,p1：c d c a b d a b p2：d e d b f e b f p3：c e e f a e f a,1,2,证明：线1不可达； 反证：假定线1可达，则线2可达。 p2先于p1; p3先于p2; p1先于p3, 矛盾。,p1:,p2:,pn:,a,5.14 同种组合资源死锁的必要条件,M：资源数量 N：使用该类资源进程的数量 ：所有进程所需要该类资源的总量 假定死锁，n个进程参与了死锁(2nN) 参与死锁的进程所需资源的总量M+n 未参与死锁进程所需资源的总量N-n 所有进程所需资源的总量M+n+N-

22、n=M+N 当M+N时，一定没有死锁； 当M+N时，至少有一个交叉有死锁。,例子,例1. M=15； N=4；P1(4); P2(6); P3(1); P4(7) =4+6+1+7=18M+N=19 无死锁可能性。 例2. M=15; N=4；P1(5); P2(6); P3(1); P4(7) =5+6+1+7=19M+N=19 有死锁可能性。死锁情况： P1：a a a a a P2：a a a a a a P3：a P4：a a a a a a a,5.15 死锁的例子,过河问题 有南北走向的河流如图5-6所示, 河中用石块搭成便桥，每个石块最多容纳一个过河者，两个相邻石块的间距恰好为一步. 西岸过河者经过石块