Module8: Deadlocks(死锁) System Model(系统模型) Deadlock Characterization(死锁特征) ° Methods for Handling Deadlocks(处理死锁的方法) Deadlock Prevention(预防死锁) Deadlock Avoidance(死锁避免) ● Deadlock Detection(死锁检测) Recovery from Deadlock(死锁恢复) Combined Approach to Deadlock Handling(综合处理方法) Applied Operating System Concepts 8 Silberschatz, GalVin, and Gagne@1999
Silberschatz ,Galvin, and Gagne©1999 8.1 Applied Operating System Concepts Module 8: Deadlocks（死锁） • System Model（系统模型） • Deadlock Characterization（死锁特征） • Methods for Handling Deadlocks（处理死锁的方法） • Deadlock Prevention（预防死锁） • Deadlock Avoidance（死锁避免） • Deadlock Detection （死锁检测） • Recovery from Deadlock （死锁恢复） • Combined Approach to Deadlock Handling（综合处理方法）
The deadlock problem(死锁问题) A set of blocked processes each holding a resource and waiting to acquire a resource held by another process in the set (一组等待的进程,其中每一个进程都持有资源,并且等待着由 这个组中其他进程所持有的资源) ° Example(例如) System has2 tape drives.(系统有两个磁带设备) P, and P2 each hold one tape drive and each needs another one.(进程P1和P2各占有一个磁带设备并且实际需 要两个磁带) Example 为 hores A and B, initialized to1(信号量A,B初始化 sem wait(A); wait(B) wait (B); wait(A) Applied Operating System Concepts 8 Silberschatz, GalVin, and Gagne@1999
Silberschatz ,Galvin, and Gagne©1999 8.2 Applied Operating System Concepts The Deadlock Problem（死锁问题） • A set of blocked processes each holding a resource and waiting to acquire a resource held by another process in the set. （一组等待的进程，其中每一个进程都持有资源，并且等待着由 这个组中其他进程所持有的资源） • Example （例如） – System has 2 tape drives.（系统有两个磁带设备） – P1 and P2 each hold one tape drive and each needs another one.（进程P1和P2各占有一个磁带设备并且实际需 要两个磁带） – Example – semaphores A and B, initialized to 1（信号量A，B初始化 为1） P0 P1 wait (A); wait(B) wait (B); wait(A)
Bridge Crossing Example(过桥的例子) Traffic only in one direction.(只有一个方向) Each section of a bridge can be viewed as a resource (桥的每一个部分都可以看成资源) e If a deadlock occurs, it can be resolved if one car backs up (preempt resources and rollback). (如果死锁发生,它可以由一辆车返回而解决,抢占资源并回退 Several cars may have to be backed upif a deadlock occurs (如果死锁发生,可能很多车都不得不返回) Starvation is possible.(有可能产生饥饿) Applied Operating System Concepts 83 Silberschatz, GalVin, and Gagne@1999
Silberschatz ,Galvin, and Gagne©1999 8.3 Applied Operating System Concepts Bridge Crossing Example（过桥的例子） • Traffic only in one direction.（只有一个方向） • Each section of a bridge can be viewed as a resource. （桥的每一个部分都可以看成资源） • If a deadlock occurs, it can be resolved if one car backs up (preempt resources and rollback). （如果死锁发生，它可以由一辆车返回而解决，抢占资源并回退） • Several cars may have to be backed upif a deadlock occurs. （如果死锁发生，可能很多车都不得不返回） • Starvation is possible.（有可能产生饥饿）
System Model(系统模型) Resource types(资源类型)R1R2,,Rm CPU cycles, memory space, vo devices (cPU周期,内存空间,∥O设备) Each resource type Ri has Wi instances (每一种资源R有W种实例) Each process utilizes a resource as follows (每一个进程如下的利用资源) request(申请) use(使用) Release(释放) Applied Operating System Concepts 8 Silberschatz, GalVin, and Gagne@1999
Silberschatz ,Galvin, and Gagne©1999 8.4 Applied Operating System Concepts System Model（系统模型） • Resource types （资源类型）R1 , R2 , . . ., Rm CPU cycles, memory space, I/O devices （CPU周期，内存空间，I/O设备） • Each resource type Ri has Wi instances. （每一种资源Ri有Wi 种实例） • Each process utilizes a resource as follows （每一个进程如下的利用资源） – request （申请） – use （使用） – Release（释放）
Deadlock characterization(死锁的特性) Deadlock can arise if four conditions hold simultaneously (四个条件同时出现,死锁将会发生 Mutual exclusion: only one process at a time can use a resource. 互斥:一次只有一个进程可以使用一个资源) Hold and wait: a process holding at least one resource is waiting to acquire additional resources held by other processes (占有并等待:一个至少持有一个资源的进程等待获得额外的由其他进程 所持有的资源) No preemption: a resource can be released only voluntarily by the process holding it, after that process has completed its task. (不可抢占:一个资源只有当持有它的进程完成任务后,自由的释放 Circular wait: there exists a set (Po, P1,..., Po] of waiting processes such that Po is waiting for a resource that is held by P1, P, is waiting for a resource that is held by P2,..., Pn-1 is waiting for a resource that is held by Pns and Po is waiting for a resource that is held by p。(循环等待:等待资源的进程之间存在环) Applied Operating System Concepts 8.5 Silberschatz, GalVin, and Gagne@1999
Silberschatz ,Galvin, and Gagne©1999 8.5 Applied Operating System Concepts Deadlock Characterization（死锁的特性） • Mutual exclusion: only one process at a time can use a resource.（ 互斥：一次只有一个进程可以使用一个资源） • Hold and wait: a process holding at least one resource is waiting to acquire additional resources held by other processes. （占有并等待：一个至少持有一个资源的进程等待获得额外的由其他进程 所持有的资源） • No preemption: a resource can be released only voluntarily by the process holding it, after that process has completed its task. （不可抢占：一个资源只有当持有它的进程完成任务后，自由的释放） • Circular wait: there exists a set {P0 , P1 , …, P0} of waiting processes such that P0 is waiting for a resource that is held by P1 , P1 is waiting for a resource that is held by P2 , …, Pn–1 is waiting for a resource that is held by Pn, and P0 is waiting for a resource that is held by P0 .（循环等待：等待资源的进程之间存在环） Deadlock can arise if four conditions hold simultaneously. （四个条件同时出现，死锁将会发生）
Resource-Allocation Graph(资源分配图) A set of vertices V and a set of edges E.(一个顶点的集合Ⅴ和边的集合E) V is partitioned into two types:(V被分为两个部分) P=(P1, P2,., Pn], the set consisting of all the processes in the system.(P:含有系统中全部的进程) R=(R1, R2,..., Rmi, the set consisting of all resource types in the system.(R:含有系统中全部的资源 request edge- directed edge P1→R(请求边:直接P1→R) assignment edge- directed 09e→P(分配边:P1→月) Applied Operating System Concepts 86 Silberschatz, GalVin, and Gagne@1999
Silberschatz ,Galvin, and Gagne©1999 8.6 Applied Operating System Concepts Resource-Allocation Graph（资源分配图） • V is partitioned into two types:（V被分为两个部分） – P = {P1 , P2 , …, Pn }, the set consisting of all the processes in the system.（P：含有系统中全部的进程） – R = {R1 , R2 , …, Rm}, the set consisting of all resource types in the system.（R：含有系统中全部的资源） • request edge – directed edge P1 → Rj（请求边：直接P1 → Rj ） • assignment edge – directed edge Rj → Pi（分配边：P1 → Rj ） A set of vertices V and a set of edges E.（一个顶点的集合V和边的集合E）
Resource-Allocation Graph(Cont 咨源分配 Process进程 ° Resource Type with4 instances有四个实例的资源类型 ° Pi requests instance of R(P请求一个R的实例) R · Pi is holding an instance of R(P并有一个R的实例) P1日 Applied Operating System Concepts 87 Silberschatz, GalVin, and Gagne@1999
Silberschatz ,Galvin, and Gagne©1999 8.7 Applied Operating System Concepts Resource-Allocation Graph (Cont.) 资源分配图续 • Process进程 • Resource Type with 4 instances有四个实例的资源类型 • Pi requests instance of Rj （ Pi 请求一个Rj的实例） • Pi is holding an instance of Rj（ Pi 持有一个Rj的实例） Pi Pi Rj Rj
Example of a Resource Allocation Graph 资源分配图的例子 R R2 Applied Operating System Concepts 88 Silberschatz, GalVin, and Gagne@1999
Silberschatz ,Galvin, and Gagne©1999 8.8 Applied Operating System Concepts Example of a Resource Allocation Graph 资源分配图的例子
Resource Allocation Graph With A Deadlock 死销的瓷源分配图 月1 R Applied Operating System Concepts 8.9 Silberschatz, GalVin, and Gagne@1999
Silberschatz ,Galvin, and Gagne©1999 8.9 Applied Operating System Concepts Resource Allocation Graph With A Deadlock 有死锁的资源分配图
Resource Allocation Graph with a cycle But No deadlock 有环但没有死锁的资源分配图 ( ea Applied Operating System Concepts 8.10 Silberschatz, GalVin, and Gagne@1999
Silberschatz ,Galvin, and Gagne©1999 8.10 Applied Operating System Concepts Resource Allocation Graph With A Cycle But No Deadlock 有环但没有死锁的资源分配图