Basic Facts(基本事实) ° If graph contains no cycles→ no deadlock °(如果图没有环,那么不会有死锁) ° If graph contains a cycle→(如果图有环) if only one instance per resource type, then deadlock (如果每一种资源类型只有一个实例,那么死锁发生) if several instances per resource type, possibility of deadlock (如果一种资源类型有多个实例,可能死锁) Applied Operating System Concepts Silberschatz, GalVin, and Gagne@1999
Silberschatz ,Galvin, and Gagne©1999 8.11 Applied Operating System Concepts Basic Facts（基本事实） • If graph contains no cycles no deadlock. • （如果图没有环，那么不会有死锁） • If graph contains a cycle （如果图有环） – if only one instance per resource type, then deadlock. （如果每一种资源类型只有一个实例，那么死锁发生） – if several instances per resource type, possibility of deadlock. （如果一种资源类型有多个实例，可能死锁）
Methods for Handling Deadlocks 死销的方法 Ensure that the system will never enter a deadlock state (确保系统永远不会进入死锁状态) Allow the system to enter a deadlock state and then recover. (允许系统进入死锁状态,然后恢复系统) e Ignore the problem and pretend that deadlocks never occur in the system; used by most operating systems, including UNX.(忽略这个问题,假装系统中从未出现过死锁。这个方法被 大部分的操作系统采用,包括UNX) Applied Operating System Concepts 8.12 Silberschatz, GalVin, and Gagne@1999
Silberschatz ,Galvin, and Gagne©1999 8.12 Applied Operating System Concepts Methods for Handling Deadlocks 处理死锁的方法 • Ensure that the system will never enter a deadlock state. （确保系统永远不会进入死锁状态） • Allow the system to enter a deadlock state and then recover. （允许系统进入死锁状态，然后恢复系统） • Ignore the problem and pretend that deadlocks never occur in the system; used by most operating systems, including UNIX.（忽略这个问题，假装系统中从未出现过死锁。这个方法被 大部分的操作系统采用，包括UNIX）
Dead| ock Prevention(死锁的预防) Restrain the ways request can be made.(抑制死锁发生的必要条件) Mutual Exclusion not required for sharable resources; must hold for nonsharable resources (互斥:共享资源不是必须的,必须保持非共享资源 Hold and Wait- must guarantee that whenever a process requests a resource, it does not hold any other resources. (占有并等待:必须保证进程申请资源的时候没有占有其他资源) Require process to request and be allocated all its resources before it begins execution, or allow process to request H resources only when the process has none (要求进程在执行前一次申请全部的资源,只有没有占有资源时才 可以分配资源 Low resource utilization starvation possible (利用率低,可能出现饥饿) Applied Operating System Concepts 8.13 Silberschatz, GalVin, and Gagne@1999
Silberschatz ,Galvin, and Gagne©1999 8.13 Applied Operating System Concepts Deadlock Prevention（ 死锁的预防） • Mutual Exclusion – not required for sharable resources; must hold for nonsharable resources. （互斥：共享资源不是必须的，必须保持非共享资源） • Hold and Wait – must guarantee that whenever a process requests a resource, it does not hold any other resources. （占有并等待：必须保证进程申请资源的时候没有占有其他资源） – Require process to request and be allocated all its resources before it begins execution, or allow process to request resources only when the process has none. （要求进程在执行前一次申请全部的资源，只有没有占有资源时才 可以分配资源） – Low resource utilization; starvation possible. （利用率低，可能出现饥饿） Restrain the ways request can be made.（抑制死锁发生的必要条件）
Deadlock Prevention(Cont 死销的预防 ° No Preemption-(非抢占) If a process that is holding some resources requests late to it, then all resources currently being held are released.(如果一个进程的申请没有实现,它要释放所有占 有的资源) Preempted resources are added to the list of resources for which the process is waiting.(先占的资源放入进程等 待资源列表中) Process will be restarted only when it can regain its old resources, as well as the new ones that it is requesting (进程在重新得到旧的资源的时候可以重新开始) e Circular Wait-impose a total ordering of all resource types, and require that each process requests resources in an increasing order of enumeration.(循环等待:将所有的资源类 型放入资源列表中,并且要求进程按照资源表申请资源) Applied Operating System Concepts Silberschatz, GalVin, and Gagne@1999
Silberschatz ,Galvin, and Gagne©1999 8.14 Applied Operating System Concepts Deadlock Prevention (Cont.) 死锁的预防（续） • No Preemption –（非抢占） – If a process that is holding some resources requests another resource that cannot be immediately allocated to it, then all resources currently being held are released.（如果一个进程的申请没有实现，它要释放所有占 有的资源） – Preempted resources are added to the list of resources for which the process is waiting.（先占的资源放入进程等 待资源列表中） – Process will be restarted only when it can regain its old resources, as well as the new ones that it is requesting. （进程在重新得到旧的资源的时候可以重新开始） • Circular Wait – impose a total ordering of all resource types, and require that each process requests resources in an increasing order of enumeration.（循环等待：将所有的资源类 型放入资源列表中，并且要求进程按照资源表申请资源）