现代操作系统第六章死锁PPT

1、1第六章 死锁n资源n死锁简介n鸵鸟算法 n死锁检测和恢复n死锁避免n死锁预防 n其他问题 2n当进程获得对设备、文件等对象的独占访问权独占访问权时，有可能会发生死锁死锁。为了尽可能地使死锁的讨论一般化，我们把已授权已授权的对象称为资源资源(resource)。资源可以是硬件(如磁带驱动器)，或者是一些信息(如数据库中加锁的记录)。n对于某些资源可能会有几个相同的实例几个相同的实例。n当某个资源有几个拷贝几个拷贝时，其中任何一个任何一个都可以用于满足对该资源的请求。n简单的说，资源就是在任何时候都只能被一个只能被一个进程使用进程使用的任何对象。资源(resource)3n资源分为两类：可剥夺的

2、可剥夺的和不可剥夺的不可剥夺的。n可剥夺资源可剥夺资源(preemptable resource)可以从拥有它的进程中剥夺剥夺而不会产生不会产生任何副作用。副作用。n存储器存储器就是一类可剥夺的资源。n不可剥夺资源不可剥夺资源(nonpreemptable resource)是无法无法在不导致计算失败的情况下从其拥有者中剥剥夺夺的。n如果一个进程已经开始烧制CD，突然从该进程夺走CD刻录机，并把它交给另一个进程将会造成CD错码。nCD刻录机在任何时刻都是不可剥夺的。和死锁有关可剥夺和不可剥夺资源 4n使用资源的必须步骤必须步骤：n请求资源请求资源n使用资源使用资源n释放资源释放资源n如果请求被

3、拒绝被拒绝，必须等待等待n请求进程可能被阻塞被阻塞n也可能由于错误代码而失败错误代码而失败可剥夺和不可剥夺资源 5资源获得 n对于某些类型的资源，完全是由用户进由用户进程来管理程来管理其自身的使用。由用户管理资用户管理资源源的一种可能方法是给每个资源赋予一个信号量信号量。这些信号量的初值均为初值均为1。n其执行过的三步为：获取获取资源时对信号对信号量量执行down操作，然后使用资源，最后释放释放资源时执行up操作。6资源获得一个用户n使用信号量保护资源 n(a) 一个资源 n(b) 两个资源 typedef int semaphore; semaphore resource_1;semapho

4、re resource_2;void process_A(void) down(&resource _1); down(&resource _2); use_both_resources( ); up(&resource _2); up(&resource _1);(b)typedef int semaphore; semaphore resource_1; void process_A(void) down(&resource _1); use_resource_1( ); up(&resource _1); (a)7资源获得两个用户n在下图

5、(a)中，某个进程将先于另一个获得第一个资源。接着，该进程将成功地获得第二个资源，并且完成其工作。如果另一个进程试图在其释放前获取资源1，该进程将被简单地阻塞，直到资源可用。n在下图 (b)中，情况就不同了。可能会发生一个进程获取两个资源，并且有效地阻塞另一个进程直到它结束。但是，同样也可能发生：进程A获得资源1，请求资源2进程B获得资源2，请求资源1。每个进程都会在它试图获取另一个资源时被阻塞。两个进程都无法继续运行两个进程都无法继续运行。这种情形就是一种死锁死锁。 8资源获得两个用户n(a) 无死锁代码 n(b) 具有潜在死锁的代码 semaphore resource_1;semapho

6、re resource_2;void process_A(void) down(&resource _1);down(&resource _2);use_both_resources( );up(&resource _2);up(&resource _1);void process_B(void) down(&resource _2);down(&resource _1);use_both_resources( );up(&resource _1);up(&resource _2);(b)typedef int semaphore

7、;semaphore resource_1; semaphore resource_2; void process_A(void) down(&resource _1); down(&resource _2); use_both_resources( ); up(&resource _2); up(&resource _1); void process_B(void) down(&resource _1); down(&resource _2); use_both_resources( ); up(&resource _2); up(&a

8、mp;resource _1); (a)9死锁简介n死锁可以正式地定义定义如下：n如果在一个进程集合中进程集合中的每个进程每个进程都在等待只能由该集合中的另一个进程引发另一个进程引发的事件，该组进程就被死锁被死锁。 n在大多数情形下，进程都是在等待等待该集合中另一个成员将目前占有的资源释放释放。n死锁的进程都不能不能n运行运行n释放资源释放资源n被唤醒被唤醒10产生死锁的条件1.互斥条件互斥条件n每个资源每次只允许一个进程一个进程使用或者空闲2.占有和等待条件占有和等待条件n已占有某些资源的进程可以请求新请求新的资源3.非剥夺条件非剥夺条件n先前授予的资源无法强制无法强制地剥夺4.循环等待条件

9、循环等待条件n至少有2个或以上进程构成循环链循环链n每个每个进程都在等待等待由循环链中下一个成员占有的资源11死锁模型n圆形节点圆形节点表示进程，方形节点方形节点表示资源。n由资源节点(方形节点)到进程节点(圆形节点)的弧线代表该资源已被进程申请、申请、获准并占用获准并占用。在下图 (a)中，资源资源R当前当前被指派给进程被指派给进程A。n由进程到资源的弧线表示该进程当前正正在申请在申请该资源，并且处于阻塞等待状态处于阻塞等待状态。在下图 (b)中，进程进程B正等待着资源正等待着资源S。 12n资源分配图n(a) 资源R被指派给进程An(b) 进程B请求/等待资源Sn(c) 进程C和D死锁死锁

10、模型13n死锁的产生死锁模型14n死锁的避免死锁模型15总而言之，处理死锁处理死锁有以下四种策略四种策略：1.忽略该问题忽略该问题。n也许你忽视它，它也会忽视你。2.检测并恢复检测并恢复。n允许死锁发生允许死锁发生，然后检测它们，再采取行动。3.通过仔细地资源分配仔细地资源分配来动态地避免死锁避免死锁。4.通过在结构上破坏死锁结构上破坏死锁的四个必要条件必要条件之一来预防死锁预防死锁。 死锁模型16鸵鸟算法(Ostrich Algorithm)n视而不见视而不见n理由理由： n死锁极少极少发生n预防预防死锁的代价太高代价太高nUNIX和Windows采用这方法n这是方便性与正确性的平衡平衡17

11、死锁检测和恢复n当使用该技术时，系统并不试图阻止并不试图阻止死锁的发生，相反，它允许死锁发生允许死锁发生，当死锁发生时尝试去检测尝试去检测它，然后采取某些行动来进行恢复恢复。 18单资源类型的死锁检测n从最简单的例子开始：即每种类型每种类型只存在一个资源一个资源。n对于这样的系统，可以构造一个资源图资源图，如果这张图包含包含了一个或多个的环路环路，那么就存在死锁存在死锁。该环路中任何进程都被死锁。如果不存在环路不存在环路，系统就不会不会死锁死锁。 19单资源类型的死锁检测n单资源类型的死锁检测n(a) 资源图 n(b) 从(a)中抽取的环路 n如果图中有环，说明系统中有死锁20单资源类型的死锁

12、检测n该算法的执行步骤执行步骤如下：1.对于图中的每个节点N，以N作为起点执行下面5个步骤。2.初始化L为空表，并清除所有弧线的标记。3.LL+N，并检测N是否在L中已出现2次。如果是，那么该图包含了一个环路(在L中)，算法结束。4.从N为始点的有向边，是否有未被标记的。如果有，执行步骤5；如果没有，转到步骤6。5.随机选取一条有向边，标记它。N此边的另一个节点，转到步骤3。6.NN的前一节点，即当前节点的前面一个节点，如果该节点为起始节点，则表明该图不存在任何环路，算法结束。否则转步骤3。21单资源类型的死锁检测n该算法的原理：将图中每个节点作为一棵树的根节点根节点，作深度优先遍历深度优先遍

13、历，如果返回到已遍历的节点，说明有环存在。22多资源类型的死锁检测n使用基于矩阵的算法来检测n个进程(从P1到Pn)中的死锁。假设资源类为m，E1表示资源类1，E2表示资源类2，Ei表示资源类i (1im)。nE为现有资源向量现有资源向量(existing resource vector)，它表示每类资源的总数。n例如，如果类1为磁带驱动器，则El = 2表示系统有两台磁带驱动器。 23多资源类型的死锁检测n在任一时刻，某些资源已被指派而不可用。n令A为可用资源向量可用资源向量(available resource vector)，Ai表示资源类i当前可供使用的(即尚未分配的)实例数目。n如果

14、两台磁带驱动器都被指派了，则A1 = 0。 24多资源类型的死锁检测n另外还有两个数组。C为当前分配矩阵当前分配矩阵(current allocation matrix)，R为请求矩请求矩阵阵(request matrix)。nC的第i行表示进程Pi当前占有每一类资源占有每一类资源的数目的数目。因此，Cij表示进程i所占有的资源j的数量。类似的，Rij代表Pi申请的资源j的数量。 25死锁检测所需的数据结构(a) 所有资源 (E1, E2, E3, , Em)(b) 可用资源 (A1, A2, A3, , Am)(c) 当前分配矩阵 (d) 请求矩阵多资源类型的死锁检测111213121222

15、32123mmnnnnmCCCCCCCCCCCC11121312122232123mmnnnnmRRRRRRRRRRRR26多资源类型的死锁检测n这四种数据结构之间有一个重要的恒等式。 nijjijEAC127多资源类型的死锁检测n死锁检测算法可以按下列步骤进行：n寻找一个尚未标记尚未标记的进程Pi，且(Ri1, Ri2, ., Rim) 小于等于小于等于A。nAA+ (Ci1, Ci2, ., Cim) ， 并标记Pi，转步骤1。n如果没有这样的进程存在，则算法终止。n算法结束时，所有尚未标记尚未标记的进程(如果有的话)都已死锁死锁。 28n死锁检测算法范例多资源类型的死锁检测29n解法：n

16、找到P3满足R3=(2 1 0 0)=A，标记P3并释放其资源：A=A+C3=(2 1 0 0)+(0 1 2 0)=(2 2 2 0)n找到P2满足R2=(1 0 1 0)=A，标记P2并释放其资源：A=A+C2=(2 0 0 1)+(2 2 2 0)=(4 2 2 1)n找到P1满足R1=(2 0 0 1)=A，标记P1并释放其资源：A=A+C1=(0 0 1 0)+(4 2 2 1)=(4 2 3 1)结果： P1、 P2 、P3均被标记，不存在死锁多资源类型的死锁检测30从死锁中恢复n剥夺法恢复剥夺法恢复n在某些情况下，临时临时将资源从其占有者拿走拿走，并转交转交给另一个进程是可能的。

17、很多情况下，需要人工干预，尤其是对大型主机上运行的批处理操作系统。n将资源从一个进程拿走，给另一个进程使用，并在不不影响原进程的情况下返回影响原进程的情况下返回，这种作法取决于该资源的特性。n回退法恢复回退法恢复n周期性地对进程设置检测点检测点(checkpoint)，即将进程状态写入文件以备稍后重启以备稍后重启。n检测点中不仅包括内存映像内存映像，还包括资源状态资源状态，即哪些资源已经被指派给进程。n一旦检测到死锁，恢复时，进程回退到较早的检测点回退到较早的检测点。31从死锁中恢复n杀死进程来恢复杀死进程来恢复n最粗鲁也是最简单的解决死锁的方法就是杀杀死一个或多个进程死一个或多个进程。n杀掉

18、环路中环路中的一个进程。n另外，也可以是将环路外的进程作为牺牲品，以释放资源。n最好杀死可以从头再运行而不会产生副作用的进程。32死锁避免n在讨论死锁检测时，我们假设，当进程申请资源时，它一次性申请所有一次性申请所有的资源。n不过，在大多数系统中一次只申请一个一次只申请一个资源资源。系统必须能够判断授权某个资源是否安全，并且只在安全的情况下分配资源。n这就引出了一个问题：是否存在一种算法总能作出正确的选择从而避免死锁？答案是肯定的，但是必须预知某些特定必须预知某些特定的信息的信息。33资源轨迹图n避免死锁的主要算法基于安全状态的概念。在描述该算法之前，先了解安全的概念。通过图示的方式，更容易理

19、解。尽管该图的方法不能直接转换成可用的算法，但它给出了一个解决问题的直觉。 n在下图中，可以看到处理两个进程和两种资源(打印机和绘图仪)的模型。 34n两个进程的资源轨迹资源轨迹图35安全和不安全状态n在任何时刻，当前状态都包括E, A, C和R。如果没有死锁，而且存在某种调度次序能够满足所有进程最大的资源请求并且完成它们，那么此状态就是安全(safe)的。n不安全状态没有任何序列可以保证完成工作。n安全状态和不安全状态的区别是：从安全状态出发，系统能够确保所有进程都能完成；而从不安全状态出发，不存在这样的保证。 36安全和不安全状态n上图中状态(a)是安全的从状态(a)出发，存在一个分配序列

20、B、C、A使得所有进程都可以完成37安全和不安全状态n上图中状态(b)是不安全的从状态(b)出发，不存在任何一个分配序列可以使得所有进程都完成38单资源的银行家算法nDijkstra(1965)提出了一种能够避免死锁的调度算法，称为银行家算法(bankers algorithm)，该算法是死锁检测算法的扩展。n它是一个小镇的银行家为模型设计的，银行家向一群客户分别承诺了一定的贷款额度。n该算法所作的就是检查请求获准是否会导致不安全状态。如果会，请求即被拒绝；否则，批准其请求。39n资源分配状态n(a) 安全n(b) 安全n(c) 不安全单资源的银行家算法40n算法：对每个资源请求检查满足它会否

21、引起不安全状态，如果是不安全状态，则不满足此请求。检测状态是否安全：此状态下是否有足够的资源满足一个距最大需求最近的客户，如果有，将此客户标记，（设客户运行结束）资源释放后，继续检查其他客户，直至所有客户都被标记则是安全状态，否则是不安全状态。单资源的银行家算法41多资源的银行家算法n银行家算法可以进行推广到处理多种资源。 n检查一个状态是否安全的步骤如下：1.查找矩阵R，有没有某行Ri=向量A。如果找不到，那么系统最终将会死锁，因为任何进程都无法运行完成。2.若有,假设被选择的进程i申请其所需的所有资源(已经确保有可能满足)并且完成，将该进程标记为终止，并将其所有资源加到向量A上，即AA+C

22、i。3.重复以上两步，直到所有的进程都标记为终止。如果所有进程都可以终止，那么初始状态是安全的；否则，就会产生死锁。42n多资源的银行家算法范例多资源的银行家算法43银行家算法中，若出现下述的资源分配情况 Allocated Need AvailableP0 0 0 3 2 0 0 1 2 1 6 2 2P1 1 0 0 0 1 7 5 0 P2 1 3 5 4 2 3 5 6P3 0 3 3 2 0 6 5 2P4 0 0 1 4 0 6 5 6问：该状态是否安全,为什么？ 如P2提出资源分配请求（0 0 0 1），系统能否将资源分配给它？多资源的银行家算法实例44解：该状态安全，因为存在分

23、配序列使的所有的进程都可以运行完成：P0 (0 0 1 2)(1 6 2 2)A=(1 6 5 4)P3 (0 6 5 2)(1 6 5 4)A=(1 9 8 6) P1 (1 7 5 0)(1 9 8 6)A=(2 9 8 6)P4 (0 6 5 6)(2 9 8 6)A=(2 9 9 10) P2 (2 3 5 6)(2 9 9 10) A=(3 12 14 14)不能分配，因为如果分配给P2 （0 0 0 1），则系统还剩资源（1 6 2 1），在系统中找不到一个进程可以满足NeedAvailable，进程将处于死锁状态。多资源的银行家算法实例45死锁预防n我们已经知道死锁避免从本质上是

24、不可能的，因为它需要未来需求的信息，而这些需求是不可知的。n那么，真正的系统又是如何避免死锁的呢？让我们回顾Coffman等(1971)所述的四个条件，看是否能发现线索。n如果能够保证四个条件中至少有一个不满足，那么从结构上死锁将不会产生(Havender，1968)。46n某些设备(例如打印机)可以假脱机操作n只有打印机守护程序使用打印机资源n这样就可以消除打印机死锁n不是所有的设备都可以进行假脱机操作n原则:n不到万不得已不要指派资源n使得尽可能少的进程实际上要求资源破坏互斥条件47n要求进程在开始执行前请求所需资源n这样进程在其需要时无需等待n问题n也许在开始运行时无法确知是否需要资源n也许需要的资源其他进程正在使用n变更: n进程必须放弃所有资源n然后在需要时申请全部所需资源破坏占有和等待条件 48n消除不可剥夺条件比前面的方法更困难。n如果一个进程已分配到一台打印机，且正在进行打印，如果由于它需要的绘图仪无法获得而强制性地把它占有的打印机剥夺掉，这会引起一片混乱。n通常，该方法不是有效的。 破坏不可剥夺条件 49破坏循环等待条件n消除循环等待有几种方法。一种是保证每一个进程在任何时刻只能占用一个资源，如果要申请第二个，必须先