Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Module 7: Deadlocks.• System Model.• Deadlock Characterization.• Methods for Handling Deadlocks.• Deadlock Prevention.• Deadlock Avoidance.• Deadlock Detection.• Recovery from Deadlock.• Combined Approach to Deadlock Handling. 7.1 Silberschatz and Galvin 1999 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• Example. – semaphores A and B, initialized to 1 P0 P1. wait (A); wait(B). wait (B); wait(A). 7.2 Silberschatz and Galvin 1999 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 7.3 Silberschatz and Galvin 1999 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. 7.4 Silberschatz and Galvin 1999 Deadlock CharacterizationDeadlock 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 {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 7.5 Silberschatz and Galvin 1999 Resource-Allocation Graph.A set of vertices V and a set of edges E. • V is partitioned into two types:. – P = {P1, P2, , Pn}, the set consisting of all the processes in. the system. – R = {R1, R2, , Rm}, the set consisting of all resource types. in the system • request edge – directed edge P1 Rj • assignment edge – directed edge Rj Pi. 7.6 Silberschatz and Galvin 1999 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. 7.7 Silberschatz and Galvin 1999 Example of a Resource Allocation Graph. 7.8 Silberschatz and Galvin 1999 Resource Allocation Graph With A Deadlock. 7.9 Silberschatz and Galvin 1999 Resource Allocation Graph With A Cycle But No Deadlock. 7.10 Silberschatz and Galvin 1999 Basic Facts.• If graph contains no cycles no deadlock• If graph contains a cycle. – if only one instance per re
