操作系统学习（七）—— 死锁

死锁的定义

进程之间互相等待资源又都不能向前推进的情况，即造成进程相互死等的局面。即每个进程“抓住”一些为其他进程所等待的资源不放。其结果是谁也得不到它所申请的全部资源，导致这些进程都无法继续运行。

产生死锁的原因

• 根本原因：系统能够提供的资源个数比请求该资源的进程数要少。
• 死锁是在并发进程在竞争资源的过程中产生的。

死锁产生的必要条件：

• 互斥：多进程共享的资源具有互斥特性，一次只能由一个进程使用。如果另一个进程申请资源，那么申请进程必须等待，直到该资源被释放。
• 不剥夺：进程所获得资源在未使用完毕之前，不能被强行夺走，只能由进程自己释放。
• 占有并等待（部分分配）：进程每次申请它所需要的一部分资源，在等待新资源的同时，进程继续占用已分配到的资源。
• 环路条件（循环等待）：有一种循环链，链中每一个进程已获得的资源同时被链中下一个进程所请求。

死锁的预防（静态策略）

上面说了死锁产生的必要条件，那么只要打破其中一个，死锁就不会发生。

• 打破互斥条件。即允许进程同时访问某些资源。但是，有的资源是不允许被同时访问的，像打印机等等，这是由资源本身的属性所决定的。所以，这种办法并无实用价值。
• 打破不可抢占条件。即允许进程强行从占有者那里夺取某些资源。就是说，当一个进程已占有了某些资源，它又申请新的资源，但不能立即被满足时，它必须释放所占有的全部资源，以后再重新申请。它所释放的资源可以分配给其它进程。这就相当于该进程占有的资源被隐蔽地强占了。这种预防死锁的方法实现起来困难，会降低系统性能。
• 打破占有且申请条件。可以实行资源预先分配策略。即进程在运行前一次性地向系统申请它所需要的全部资源。如果某个进程所需的全部资源得不到满足，则不分配任何资源，此进程暂不运行。只有当系统能够满足当前进程的全部资源需求时，才一次性地将所申请的资源全部分配给该进程。由于运行的进程已占有了它所需的全部资源，所以不会发生占有资源又申请资源的现象，因此不会发生死锁。但是，这种策略也有如下缺点：
  1）在许多情况下，一个进程在执行之前不可能知道它所需要的全部资源。这是由于进程在执行时是动态的，不可预测的；
  2）资源利用率低。无论所分资源何时用到，一个进程只有在占有所需的全部资源后才能执行。即使有些资源最后才被该进程用到一次，但该进程在生存期间却一直占有它们，造成长期占着不用的状况。这显然是一种极大的资源浪费；
  3）降低了进程的并发性。因为资源有限，又加上存在浪费，能分配到所需全部资源的进程个数就必然少了。
• 打破循环等待条件，实行资源有序分配策略。采用这种策略，即把资源事先分类编号，按号分配，使进程在申请，占用资源时不会形成环路。所有进程对资源的请求必须严格按资源序号递增的顺序提出。进程占用了小号资源，才能申请大号资源，就不会产生环路，从而预防了死锁。这种策略与前面的策略相比，资源的利用率和系统吞吐量都有很大提高，但是也存在以下缺点：
  （1）限制了进程对资源的请求，同时给系统中所有资源合理编号也是件困难事，并增加了系统开销；
  （2）为了遵循按编号申请的次序，暂不使用的资源也需要提前申请，从而增加了进程对资源的占用时间。

银行家算法（死锁的动态策略）

1）安全序列
我们首先引入安全序列的定义：所谓系统是安全的，是指系统中的所有进程能够按照某一种次序分配资源，并且依次地运行完毕，这种进程序列{P1，P2，...，Pn}就是安全序列。如果存在这样一个安全序列，则系统是安全的；如果系统不存在这样一个安全序列，则系统是不安全的。
安全序列{P1，P2，...，Pn}是这样组成的：若对于每一个进程Pi，它需要的附加资源可以被系统中当前可用资源加上所有进程Pj当前占有资源之和所满足，则{P1，P2，...，Pn}为一个安全序列，这时系统处于安全状态，不会进入死锁状态。 　
虽然存在安全序列时一定不会有死锁发生，但是系统进入不安全状态（四个死锁的必要条件同时发生）也未必会产生死锁。当然，产生死锁后，系统一定处于不安全状态。
这是一个著名的避免死锁的算法，是由Dijstra首先提出来并加以解决的。

[背景知识]
一个银行家如何将一定数目的资金安全地借给若干个客户，使这些客户既能借到钱完成要干的事，同时银行家又能收回全部资金而不至于破产，这就是银行家问题。这个问题同操作系统中资源分配问题十分相似：银行家就像一个操作系统，客户就像运行的进程，银行家的资金就是系统的资源。

[问题的描述]
一个银行家拥有一定数量的资金，有若干个客户要贷款。每个客户须在一开始就声明他所需贷款的总额。若该客户贷款总额不超过银行家的资金总数，银行家可以接收客户的要求。客户贷款是以每次一个资金单位（如1万RMB等）的方式进行的，客户在借满所需的全部单位款额之前可能会等待，但银行家须保证这种等待是有限的，可完成的。

例如：有三个客户C1，C2，C3，向银行家借款，该银行家的资金总额为10个资金单位，其中C1客户要借9各资金单位，C2客户要借3个资金单位，C3客户要借8个资金单位，总计20个资金单位。某一时刻的状态如图所示。

银行家算法实例.png

解答：
1）选取客户C2，银行家手上资源大于C2请求的资源，C2借款完毕，返还3个资源。
2）选取客户C3，银行家手上资源等于C3请求的资源，C3借款完毕，返还4个资源。
3）选取客户C1，银行家手上资源大于C1请求的资源，C1借款完毕，返还9个资源。
最后返还10个资源，银行家保本。

综上所述，银行家算法是从当前状态出发，逐个按安全序列检查各客户谁能完成其工作，然后假定其完成工作且归还全部贷款，再进而检查下一个能完成工作的客户，......。如果所有客户都能完成工作，则找到一个安全序列，银行家才是安全的。

银行家算法允许死锁必要条件中的：
1）互斥条件（资源被一个人申请其他人无法申请）
2）占有且申请条件（进程占有一部分资源，完成之前继续占有并申请资源）
3）不可抢占条件（占有资源后不能强制解除，只能自己完成后释放）
这样，它与预防死锁的几种方法相比较，限制条件少了，资源利用程度提高了。

死锁的恢复

2.死锁的恢复

一旦在死锁检测时发现了死锁，就要消除死锁，使系统从死锁状态中恢复过来。

• 最简单，最常用的方法就是进行系统的重新启动，不过这种方法代价很大，它意味着在这之前所有的进程已经完成的计算工作都将付之东流，包括参与死锁的那些进程，以及未参与死锁的进程。

• 撤消进程，剥夺资源。终止参与死锁的进程，收回它们占有的资源，从而解除死锁。这时又分两种情况：一次性撤消参与死锁的全部进程，剥夺全部资源；或者逐步撤消参与死锁的进程，逐步收回死锁进程占有的资源。一般来说，选择逐步撤消的进程时要按照一定的原则进行，目的是撤消那些代价最小的进程，比如按进程的优先级确定进程的代价；考虑进程运行时的代价和与此进程相关的外部作业的代价等因素。

• 此外，还有进程回退策略，即让参与死锁的进程回退到没有发生死锁前某一点处，并由此点处继续执行，以求再次执行时不再发生死锁。虽然这是个较理想的办法，但是操作起来系统开销极大，要有堆栈这样的机构记录进程的每一步变化，以便今后的回退，有时这是无法做到的。