Deadlock

tags: IT铁人

介绍

Deadlock是Multi-process常产生的问题，如果多个process同时在运作，那麽会产生争夺Resource的行为，而这样的行为可能就会导致Deadlock。

以下图来说，每台车子都在等另一台开走，最终导致4台车都无法往前，这就是简单的Deadlock概念。

原因

产生Deadlock有四个必要条件，只有满足下面四个条件，Deadlock才可能发生，反之四个条件成立不一定会发生Deadlock。

条件	叙述	范例
Mutual Exclusion	如果Resource在任何时间点，最多只允许一个process持有(使用)。	大多数Resource : CPU, Memory, I/O Device, etc
Hold & Wait	Process持有部分Resource且等待其他process有的Resource。
No Preemption	Process不可任意抢夺其他process持有的Resource，必须等待对方自愿释放後才有机会取得。
Circular Waiting	一组process形成循环等待的关系。

与Starvation比较

Deadlock跟Starvation同样导致process无法执行，不过两者有不小的区别，以下做出比较：

解决方法

要解决Deadlock有四种方针，以下依序讨论：

Prevention

我们可以想办法破除必需的四个条件以确保Deadlock不会发生，不过有的条件破除的难度太高，以下把每一个条件各讨论一次。

Avoidance

不是破除Deadlock条件，而是在申请Resource时，OS会判断有没有可能发生Deadlock，假如有可能择否决申请。

至於判断的方式，是执行一个称为Banker's Algorithm，这个做法先对process定义5个参数，Request代表申请的各式Resource数量，MAX代表完成工作所需之最大各式Resource数量，Allocation代表目前持有的各式Resource数量，Need代表尚需的各式Resource数量，Available代表OS目前可用的Resource数量。

如果Request的数量小於Need数量，则代表申请合理，反之直接无情拒绝；再判断Request是否小於Available，可以才会进行下一步计算，反之则要求process等待。

前面的流程大概是这样，至於下一步的计算因为较为麻烦，就不在这边说明了，概念上是计算如果给予process申请的Resource，如果是safe state才可以执行，反之可能造成Deadlock的unsafe state则暂时拒绝之。

Deadlock Detection & Recovery

这种做法就是不多加限制，让Process任意取得Resource，不过OS要能够侦测目前是否有Deadlock存在，如果发现有则执行Recovery破除Deadlock，恢复正常状况。

不过侦测的方式牵涉到比较麻烦的演算法，就不特别说明了。而复原的方式则是一个一个终止process直到破除Deadlock，或是把某个process的Resource抢过来，并将她回复到拿到Resource之前。

Ignore

这个就是完全不理会Deadlock，发生卡住的状况OS就直接介入终止程序之类的。

虽然这个做法听起来超不负责任，不过UNIX系统基本上都采用这种方式，毕竟Deadlock发生的频率少之又少，忽视的影响也很小，也可以省去其他方法耗费的大量成本。

Deadlock的内容就到这边为止了，因为程序执行的时间很迅速，以至於现实生活中很少发生Deadlock，但还是要讨论一下啦><，剩下的下篇见罗。