7 Deadlock
1. Deadlock 定义
*需要有单独的线程来检测是否死锁
Deadlock ：A set of blocked processes each holding a resource and waiting to acquire a resource held by another process in the set.
死锁：指多个进程因竞争共享资源而造成的一种僵局，若无外力作用，这些进程都将永远不能再向前推进。
2. Deadlock Characterization
产生死锁的四个必要条件：
– 互斥（Mutual exclusion）：同一时间只能有一个进程访问该资源。
– 占有并等待、请求和保持（Hold and wait）：进程已经保持了至少一个资源，但又提出了新的资源要求，而该资源又已被其它进程占有，此时请求进程阻塞，但又对已经获得的其它资源保持不放。
– 不可抢占（No preemption）：资源只能自愿释放在该进程完成其任务之后，由持有它的进程执行。
– 循环等待（Circular wait）：存在一组等待过程{P0，P1，…，Pn}，这样P0正在等待P1保留的资源，P1正在等待P2保留的资源，…，Pn-1正在等待 Pn保留的资源，而Pn正在等待P0保留的资源。
资源分配图（Resource-Allocation Graph）
request edge – 请求边（P->R）
assignment edge – 分配边 （R->P）
vertices P – 进程节点（圆形）
vertices R – 资源节点（正方形）
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.
– 死锁定理：S为死锁状态的充分条件是：尚且仅当S状态的资源分配图是不可完全简化的。（有环）
– 资源分配图（有向图）的简化。–离散数学算法
3. Handing methods
– Ensure that the system will never enter a deadlock state.
（分配资源以前）Prevention死锁预防、 Avoidance死锁避免
– Allow the system to enter a deadlock state and then recover.
（分配资源以后）Detection死锁检测、 Recovery死锁解除
– Ignore the problem （不做任何的处理）and pretend that deadlocks never occur in the system; used by most operating systems, including UNIX、Linux、Windows. —鸵鸟方法
4. Prevention 死锁预防
使4个必要条件中有一个不符合即可：
– Mutual Exclusion
not required for sharable resources; must hold for nonsharable resources.
虚拟化 Restrain the ways request can be made.
– 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.（产生饥饿）
– 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.施加所有资源类型的总顺序，并要求每个进程以递增的顺序请求资源。（资源有序申请）
F(tape drive)=1, F(disk drive)=5, F(printer)=12
资源的有序申请破坏了循环等待条件。
5. Avoidance 死锁避免
如果产生死锁，则不分配资源。
1.Safe State 安全状态：安全状态是指系统的一种状态，在此状态开始系统能按某种顺序（如P1、 P2……Pn）来为各个进程分配其所需资源，直至最大需求，使每个进程都可顺序地一个个地完成。这个序列（P1、P2…….Pn）称为安全序列。若系统此状态不存在一个安全序列，则称系统处于不安全状态。
Basic Facts:
– If a system is in safe state -> no deadlocks.
– If a system is in unsafe state -> possibility of deadlock.
– Avoidance -> ensure that a system will never enter an unsafe state.
即：deadlock包含unsafe state。
2.资源分配图算法：假设进程Pi申请资源Rj。只有在需求边Pi ->Rj 变成分配边 Rj-> Pi 而不会导致资源分配图形成环时，才允许申请。 用算法循环检测，如果没有环存在，那么资源分配会使系统处于安全状态。如果存在环，资源分配会使系统不安全。进程Pi必须等待。
3.Banker’s Algorithm（银行家算法）
Multiple instances
最具代表的避免死锁算法是Dijkstra的银行家算法，这是由于该算法用于银行系统现金贷款的发放而得名。
例：设银行家有10万贷款，P、Q、R分别需要8,3,9万元搞项目，如果P已申请到了4万，Q 要申请2万，显然，如果满足Q的申请，有安全序列<p,q,r>/<q,p,r>。但如果R要申请4 万，若满足R的申请，显然不存在安全序列。
Each process must a prior claim maximum use. When a process requests a resource it may have to wait. When a process gets all its resources it must return them in a finite amount of time.</q,p,r></p,q,r>
0 条评论