Applied Operating System Concepts
8.11
Silberschatz ,Galvin, and Gagne1999
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.
•
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.（循环等待：等待资源的进程之间存在环）
•
• •
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.
• •
request edge – directed edge P1 Rj（请求边：直接P1 Rj ） assignment edge – directed edge Rj Pi（分配边：P1 Rj ）
Applied Operating System Concepts
8.6
Silberschatz ,Galvin, and Gagn不返回）
Starvation is possible.（有可能产生饥饿）
8.3 Silberschatz ,Galvin, and Gagne1999
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（释放）
8.2 Silberschatz ,Galvin, and Gagne1999
Applied Operating System Concepts
Bridge Crossing Example（过桥的例子）
• •
Traffic only in one direction.（只有一个方向） Each section of a bridge can be viewed as a resource. （桥的每一个部分都可以看成资源）
Applied Operating System Concepts
8.4
Silberschatz ,Galvin, and Gagne1999
Deadlock Characterization（死锁的特性）
Deadlock can arise if four conditions hold simultaneously. （四个条件同时出现，死锁将会发生）
•
Applied Operating System Concepts
8.5
Silberschatz ,Galvin, and Gagne1999
Resource-Allocation Graph（资源分配图）
A set of vertices V and a set of edges E.（一个顶点的集合V和边的集合E）
8.1
Silberschatz ,Galvin, and Gagne1999
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. （一组等待的进程，其中每一个进程都持有资源，并且等待着由 这个组中其他进程所持有的资源）
Module 8: Deadlocks（死锁）
• • • • • • • •
System Model（系统模型） Deadlock Characterization（死锁特征） Methods for Handling Deadlocks（处理死锁的方法）
Deadlock Prevention（预防死锁）
•
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：含有系统中全部的资源）
• • •
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. （如果一种资源类型有多个实例，可能死锁）
• •
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. （利用率低，可能出现饥饿）
•
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 wait (A); wait (B); P1 wait(B) wait(A)
（允许系统进入死锁状态，然后恢复系统）
Ignore the problem and pretend that deadlocks never occur in the system; used by most operating systems, including UNIX.（忽略这个问题，假装系统中从未出现过死锁。这个方法被 大部分的操作系统采用，包括UNIX）
• •
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. （占有并等待：一个至少持有一个资源的进程等待获得额外的由其他进程 所持有的资源）
Applied Operating System Concepts