第8章死锁.ppt

实用操作系统概念 内容框架 概述 体系结构 进程管理 内存管理 文件管理 外设管理 内容 Ch4: 进程 Ch5: 线程 Ch6: CPU调度 Ch7：进程同步 Ch8：死锁 Ch 8: Deadlocks Deadlock Problem System Model Deadlock Characterization Resource-Allocation Graph Methods for Handling Deadlocks The Deadlock Problem Reason Example The Deadlock Problem Reason A set of blocked processes each holding a resource and waiting to acquire a resource held by another process in the set. 资源竞争，是进程对资源要求在时间上的冲突。 竞争可能产生死锁，但不一定会死锁。取决于各个进程推进的速度和对资源请求的顺序。 The Deadlock Problem Example Example1 System has 2 tape drives. P1 and P2 each hold one tape drive and each needs another one. The Deadlock Problem Example 2 semaphores A and B, initialized to 1 P0 P1 wait (A); wait(B) wait (B); wait(A) The Deadlock Problem Example 3 ：Bridge Crossing Example System Model Resource types R1, R2, . . ., Rm CPU cycles, memory space, I/O devices Each resource type Ri has Wi instances. Each process utilizes a resource as follows: request use release 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. Deadlock Characterization 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 With A Deadlock Resource Allocation Graph With A Cycle But No Deadlock Resource-Allocation Graph If graph contains no cycles ? no deadlock. If graph contains a cycle ? if only one instance per resource type, then deadlock. if several instances pe