操作系统进程死锁详解

学习前福利-牛肉丸子面

1 - 死锁概念

操作系统中有若干进程并发执行，它们不断申请、使用、释放系统资源，虽然系统的进程协调、通信机构会对它们进行控制，但也可能出现若干进程都相互等待对方释放资源才能继续运行，否则就阻塞的情况。此时，若不借助外界因素，谁也不能释放资源，谁也不能解除阻塞状态。根据这样的情况，操作系统中的死锁被定义为系统中两个或者多个进程无限期地等待永远不会发生的条件，系统处于停滞状态，这就是死锁。

2 - 产生死锁的必要条件

(1)互斥使用(资源独占)：一个资源每次只能给一个进程使用

(2)占有且等待(请求和保持，部分分配)：进程在申请新的资源的同时保持对原有资源的占有

(3)不可抢占(不可剥夺)：资源申请者不能强行的从资源占有者手中夺取资源，资源只能由占有者自愿释放

(4)循环等待：存在一个进程等待队列 {P1 , P2 , … , Pn}，其中P1等待P2占有的资源，P2等待P3占有的资源，…，Pn等待P1占有的资源，形成一个进程等待环路。

当死锁产生的时候一定会有这四个条件，有一个条件不成立都不会造成死锁。

3 - 处理死锁的方法

目前处理死锁的方法可以归纳为如下：

(1)不考虑此问题（鸵鸟算法）：把头埋在沙子里，假装根本没发生问题。因为解决死锁问题的代价很高，因此鸵鸟策略这种不采取任务措施的方案会获得更高的性能。当发生死锁时不会对用户造成多大影响，或发生死锁的概率很低，可以采用鸵鸟策略。大多数操作系统，包括 Unix，Linux 和 Windows，处理死锁问题的办法仅仅是忽略它。

(2)不让死锁发生，分为以下两种：

死锁预防：不让死锁发生的静态策略，通过设计合适的资源分配算法，由资源分配策略保证不让死锁发生

死锁避免：不让死锁发生的动态策略，以不让死锁发生为目标，跟踪并评估资源分配过程，根据评估结果决策是否分配

(3)让死锁发生

通过死锁的检测判断死锁是否真的发生，然后采用一些方法来解除死锁的问题。

总体解决锁死发生的方法可以分为四类：鸵鸟算法、死锁预防、死锁避免以及死锁检测与解除。

4 - 死锁预防

在设计系统时，通过确定资源分配算法，排除发生死锁的可能性。具体做法是防止产生死锁的四个必要条件中任何一个条件发生即破坏产生死锁的四个条件之一。

(1)破坏“互斥使用/资源独占”条件

资源本身的特性是独占的，是排他性使用的，所以要使用一种资源转换技术，把独占资源变为共享资源。例如针对于打印机，SPOOLing技术的引入解决不允许任何进程直接占有打印机的问题。设计一个“守护进程/线程”负责管理打印机，进程需要打印时，将请求发给该daemon，由它完成打印任务。

(2)破坏“占有且等待”条件

指一个进程占有了一部分资源，在申请其他资源的时候由于得不到满足而进入等待状态。有下面两种方案实现：

实现方案1：要求每个进程在运行前必须一次性申请它所要求的所有资源，且仅当该进程所要资源均可满足时才给予一次性分配。这种实现会使得资源的利用率很低，当一个进程所需要的资源不能同时满足的情况下可能一直处于等待状态，会产生饥饿现象。

实现方案2：在允许进程动态申请资源前提下规定，一个进程在申请新的资源不能立即得到满足而变为等待状态之前，必须释放已占有的全部资源，若需要再重新申请。

(3)破坏“不可抢占”条件

实现方案是当一个进程申请的资源被其他进程占用时，可以通过操作系统抢占这一资源(两个进程优先级不同)。这种方法具有局限性，适用于状态易于保存和恢复的资源，如CPU、内存资源。

(4)破坏“循环等待”条件

主要思想是通过定义资源类型的线性顺序实现，实现方案是资源有序分配法，把系统中所有资源编号，进程在申请资源时必须严格按资源编号的递增次序进行，否则操作系统不予分配。实现资源的有序分配时需要考虑如何对资源进行编号，通常可以利用资源使用的频繁性进行排序。

假如有P1,P2…Pn共n个进程，每个进程都需要一定的资源，一定可以找到某个进程所需要申请的资源的序号是最大的这个进程，从这个进程开始执行；这个进程执行完之后再继续找下一个所需要资源序号最大的进程，以此类推，因此使用资源的有序分配法一定可以解决死锁问题。

5 - 利用银行家算法避免死锁

银行家算法是仿照银行发放贷款时采取的控制方式而设计的一种死锁避免算法，起这样的名字是因为该算法原本是为银行系统设计的，以确保银行在发放贷款时，不会发生不满足客户需要的情况，在操作系统中也可以用它来避免死锁。

为实现银行家算法，每一个进程进入系统时，他它须申明在运行过程中，可能需要每种资源类型的最大数目，其数目不能超过系统所拥有的资源总量。当进程请求一组资源时，系统必须首先确定是否有足够的资源分配给该进程。若有，再进一步计算在将这资源分配给进程后，是否会使系统处于不安全状态。如果不会，才将资源分配给它，否则让进程等待。

应用条件如下：

在固定数量的进程中共享数量固定的资源

每个进程预先指定完成工作所需的最大资源数量

进程不能申请比系统中可用资源总数还多的资源

进程等待资源的时间是有限的

如果系统满足了进程对资源的最大需求，那么，进程应该在有限的时间内使用资源，然后归还给系统

6 - 死锁检测与解除：

允许死锁发生，但是操作系统会不断监视系统进展情况，判断死锁是否真的发生；一旦死锁发生则采取专门的措施，解除死锁并以最小的代价恢复操作系统运行。

检测死锁是否发生有三个典型的检测时机：(1)当进程由于资源请求不满足而等待时检测死锁，缺点是系统开销大；(2)定时检测；(3)系统资源利用率下降时检测死锁。

一个简单的死锁检测算法

给每个进程、每个资源指定唯一编号；设置一张资源分配表记录各进程与其占用资源之间的关系；设置一张进程等待表记录各进程与要申请资源之间的关系。从资源等待表出发，看有没有形成等待的环路。即可以利用资源分配图的思想来检测是否有死锁发生。

死锁避免

死锁避免的重要是以最小的代价恢复系统的运行，具体的死锁解除的方法有几个：(1)撤消所有死锁进程，代价较大；(2)进程回退（Roll back）再启动，进程在执行过程中，系统会为进程记录一些中间节点，当出现死锁的时候进行回退再一起重新运行，由于需要记录每个进程的现场，所以系统代价也比较大；(3)按照某种原则逐一撤消死锁进程，直到没有死锁；(4)按照某种原则逐一抢占资源（资源被抢占的进程必须回退到之前的对应状态），直到没有死锁。