操作系统原理第六章

1/19第6章并发性:死锁6.1死锁的概念6.2产生死锁的条件和处理6.3死锁的预防6.4死锁的避免6.5死锁的检测与解除6.6死锁的综合处理策略2/196.1死锁的概念死锁:

指多个进程因竞争共享资源而造成的一种僵局，若无外力作用，这些进程都将永远不能再向前推进。即：一组进程中，每个进程都无限等待被该组进程中另一进程所占有的资源，因而永远无法得到的资源，这种现象称为进程死锁，这一组进程就称为死锁进程。3/196.1死锁的概念死锁例子：有一台打印机R1和一台卡片阅读机R2，进程P1占用打印机R1，进程P2占用卡片阅读机R2。如果Pl要求阅读机，P2要求打印机，则P1，P2便处于死锁状态。4/196.1死锁的概念产生死锁的原因：1．竞争系统资源：如上例所示2．进程的推进顺序不当5/192．进程的推进顺序不当在进程P1和P2并发执行时，按照左图曲线①②③所示顺序推进时，两进程会顺利完成，我们称这种推进顺序是合法的。若按曲线④的顺序推进时，进入不安全区D内，两进程再推进会产生死锁。6/196.2产生死锁的条件和处理互斥条件（资源独占）请求和保持条件（部分分配，占有申请）非剥夺条件（不可强占）循环等待条件6.2.1必要条件

7/191)互斥使用（资源独占）一个资源每次只能给一个进程使用2)不可强占（不可剥夺）

资源申请者不能强行的从资源占有者手中夺取资源，资源只能由占有者自愿释放6.2.1必要条件

6.2产生死锁的条件和处理8/19

3)请求和保持

（部分分配，占有申请）一个进程在申请新的资源的同时保持对原有资源的占有（只有这样才是动态申请，动态分配）6.2.1必要条件

6.2产生死锁的条件和处理9/19

4)循环等待

存在一个进程等待队列

{P1,P2,…,Pn},

其中P1等待P2占有的资源，P2等待P3占有的资源，…，Pn等待P1占有的资源，形成一个进程等待环路6.2.1必要条件

6.2产生死锁的条件和处理10/196.2产生死锁的条件和处理6.2.2处理死锁的基本方法不让死锁发生预防死锁（静态策略）避免死锁（动态策略）让死锁发生检测死锁解除死锁11/196.3死锁的预防通过破坏死锁的四个必要条件中的一个或多个以确保系统绝不会产生死锁。1．互斥条件：无法破环2．破坏请求和保持条件：采用预先分配的策略，详见6.3.1。3．破坏循环等待条件：采用有序分配的策略，详见6.3.2。12/196.3死锁的预防4．破坏非剥夺条件：可以收回已分给进程且尚未使用完毕的资源。2个方案：方案1：进程在申请新的资源不能得到满足，必须释放已占有的全部资源，进入等待队列。13/196.3死锁的预防方案2：进程在请求资源得不到满足，则检查这些资源是否分给了某个进程，如果此进程正在等待更多资源，则剥夺等待进程的这些资源以满足请求进程的需要；否则请求进程等待。在等待过程中，它的某些资源也有可能被剥夺。适用资源：状态容易保存和恢复的，例如CPU寄存器、存储器空间等。14/196.3死锁的预防方法有两种：一种是要求每个进程在运行之前便申请它所需的全部资源另一种是，规定每个进程在请求新的资源之前必须释放其已占用的全部资源。6.3.1预先分配策略15/196.3死锁的预防缺点：一是资源利用率较低；二是有可能产生“饥饿”现象，即如果一个进程需要几种竞争较激烈的资源，而总不能完全得到满足的话，则该进程将无限期地等待。所以，这种方法在实际中用得较少。6.3.1预先分配策略16/196.3死锁的预防把系统中所有资源编号，进程在申请资源时必须按资源编号的递增次序进行，否则操作系统不予分配6.3.2有序分配策略

--破坏“循环等待”条件17/196.3死锁的预防6.3.2有序分配策略例如：资源编号－1，2，3，…，10P1：申请1申请3申请9…P2：申请1申请2申请5…P3……P1018/196.4死锁的避免定义:系统运行过程中，允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次资源分配的安全性。若此次分配不会导致系统进入不安全状态，则将资源分配给进程；否则，令进程等待。最具有代表性的避免死锁算法是银行家算法。19/196.4.1系统安全状态安全状态：如果系统能按某种顺序（如P4，P1，…,Pn,称为安全序列）为每个进程分配其所需的资源，直至每个进程都能顺利地完成，称系统处于安全状态。若不存在这样一个安全序列称系统处于不安全状态。安全状态一定是没有死锁发生的。20/196.4.1系统安全状态

安全状态之例：有三个进程p1,p2,p3，有12台磁带机。P1共要求10台，P2共要求4台，P3共要求9台。在T0时刻，p1,p2,p3分别获得5、2、2台，尚有3台空闲。进程最大需求已分配可用P1P2P310495223经分析，在T0时刻，系统是安全的。因为存在一个安全序列p2、p1、p3。21/196.4.1系统安全状态

由安全状态向不安全状态的转换：如在T0以后，P3要求1台磁带机，若系统分给它一台，则系统进入不安全状态。进程最大需求已分配还需可用p110552p2422p3936因为其余2台分给P2，P2完成后，只能释放4台，这既不能满足P1（5台），也不能满足P3（6台），将导致死锁。22/196.4.2银行家算法

1.银行家算法中的数据结构

（1）可利用资源向量Available。它是一个含有m个元素的数组，其中每个元素代表一类可利用资源的数目。如：

ABC52323/196.4.2银行家算法

1.银行家算法中的数据结构

（2）最大需求矩阵Max。n*m矩阵，表示n个进程的每一个对m类资源的最大需求。ABCP1562P2331P3425P433224/196.4.2银行家算法

1.银行家算法中的数据结构

（3）分配矩阵Allocation。n*m矩阵，表示每个进程分配的资源数。ABCP1212P2121P3222P413225/196.4.2银行家算法

1.银行家算法中的数据结构

（4）需求矩阵Need。n*m矩阵，表示每个进程还需要各类资源数。ABCP1352P2211P3223P423226/196.4.2银行家算法

2.银行家算法

当进程pi提出资源申请时，系统执行下列步骤：（1）若Request[i]≤Need[i],转（2）；

否则错误返回(需要资源数超过最大值)（2）若Request[i]≤Available,

转（3）；否则进程等待(无足够资源)27/196.4.2银行家算法

2.银行家算法

（3）系统试分配资源，则有：Available:=Available-Request[i];Allocation[i]:=Allocation[i]+Request[i];Need[i]:=Need[i]–Request[i]（4）执行安全性算法，若系统新状态是安全的，则分配完成，若系统新状态是不安全的，则恢复原状态，进程等待28/196.4.2银行家算法

3.安全性算法为进行安全性检查，定义数据结构：Work:ARRAY[1..m]ofinteger;Finish:ARRAY[1..n]ofBoolean;m代表资源的数量，n代表进程的数量29/196.4.2银行家算法

3.安全性算法(1)Work:=Available;Finish:=false;(2)

寻找满足条件的i：

a.Finish[i]=false;b.Need[i]≤Work;如果不存在，则转(4)30/196.4.2银行家算法

3.安全性算法(3)Work:=Work+Allocation[i];Finish[i]:=true;

转(2)(4)若对所有i,Finish[i]=true,则系统处于安全状态，否则处于不安全状态31/194.银行家算法举例：

设系统有五个进程和三类资源，每类资源分别有10、5、7。在T0时刻资源分配情况如图:资源情况进程MaxABCAllocationABCNeedABCAvailableABCP0753010743332P1322200122P2902302600P3222211011P4433002431(1)

T0时刻可以找到一个安全序列{p1,p3,p4,p2,p0},

系统是安全的32/194.银行家算法举例：

(2)P1发出请求Request(1,0,2)，执行银行家算法:资源情况进程MaxABCAllocationABCNeedABCAvailableABCP0753010743332230P13222003021220

20P2902302600P3222211011P4433002431可以找到一个安全序列{p1,p3,p4,p0,p2}，系统是安全的，可以将P1的请求分配给它。33/194.银行家算法举例：

(３)P4发出请求Request(3,3,0),执行银行家算法:资源情况进程MaxABCAllocationABCNeedABCAvailableABCP0753010743230P13223020

20P2902302600P3222211011P4433002431Available=（2,3,0），Request[i]≤Available

），所以P4等待。34/194.银行家算法举例：

(4)P0请求资源Request（0，2，0），执行银行家算法，试分配后:资源情况进程MaxABCAllocationABCNeedABCAvailableABCP0753030723210P13223020

20P2902302600P3222211011P4433002431Available＝(2,1,0)不能满足任何进程需要，所以系统进入不安全状态，P0的请求不能分配3