1.死锁问题

---

  先讲一个生活中的例子，比如说单向通行桥梁。

 

  死锁在操作系统中会频繁出现，一组阻塞的线程持有一种资源，却等待获取另一个线程占有的一个资源。比如，系统有两个磁盘驱动器，P1和P2各有一个，都需要另外一个。

  可以看出死锁问题是，由于竞争资源或者通信关系，两个或更多线程在执行中出现，永远相互等待只能由其他进程引发的事件。

  出现死锁的原因：进程的并发执行。

2.系统模型

---

  死锁中有两类，一类是需求方，一类是资源。

  资源分为两种类型：

  可重用资源(Reusable Resource)：

•     在一个时间只能被一个进程使用，且资源不能被删除
•     进程释放资源后，其他进程可重用
•     可重用资源示例：处理器，I/O通道，主和副存储器，设备和数据结构，文件，数据库和信号量
•     如果每个进程拥有一个资源并请求其他资源，死锁可能发生

  消耗资源(Consumable Resource)：

•     消耗资源会涉及到资源的创建和销毁
•     消耗资源示例：在I/O缓冲区的中断，信号，消息，信息
•     可能出现死锁：进程间互相等待接收对方的消息

资源分配图

  资源分配的情况可以通过图的形式来表示，即一组定点V和边E的集合：

资源分配图示例

  例子1：

 

  上图可以看出以下关系 ：

•   P1占有R2一个资源，它需要R1一个资源，而这个资源被P2所占有；
•   P2占有R1一个资源以及R2一个资源，它需要R3一个资源，而这个资源被P3所占有；
•   P3占有R3一个资源。

  我们会发现有的进程在占有资源的同时，还需要被其他进程占有的资源，那这种情况下会产生死锁吗？

  不会，因为只要等P3执行完，P2就可获得需要的R3资源继续执行，等P2执行完，P1就可获得需要的R1资源继续执行。

  例子2：

  上图可以看出以下关系 ：

•   P1占有R2一个资源，它需要R1一个资源，而这个资源被P2所占有；
•   P2占有R1一个资源以及R2一个资源，它需要R3一个资源，而这个资源被P3所占有；
•   P3占有R3一个资源，它需要R2一个资源，而这个资源被P1和P2占有。

  那这种情况下会产生死锁吗？看起来图是成环的。

  会，不同于例子1中刚开始P3会正常执行，此时三个进程都需要等待资源释放而停止，又因都停止没有一个会真正释放资源。

 

  例子3：

  上图可以看出以下关系 ：

•   P1占有R2一个资源，它需要R1一个资源，而这个资源被P2、P3所占有；
•   P2占有R1一个资源；
•   P3占有R1一个资源，它需要R2一个资源，而这个资源被P1和P4占有；
•   P4占有R2一个资源。

  那这种情况下会产生死锁吗？看起来图是成环的。

  不会，虽然是有循环的资源分配图，但不会造成死锁。因为刚开始P2,P4都能正常执行，执行完毕后释放R1,R2资源，此时P1，P3也能正常执行结束。所以资源分配图成环并不意味着死锁。

总结

  对于用图来表示的资源分配，我们可以总结出以下两条：

  如果图中不包含循环 ===> 没有死锁

  如果途中包括循环 ===> 如果每个资源类只有一个实例，那么死锁；如果每个资源类有几个实例，可能死锁。  

 

3.死锁特征

---

  死锁的出现是有迹可循的，死锁可能出现如果四个条件同时成立：

•   互斥：在一个时间只能有一个进程使用资源。
•   持有并等待：进程保持至少一个资源，且正在等待获取其他进程持有的额外资源。
•   无抢占：一个资源只能被进程自愿释放，在进程完成任务之后。
•   循环等待：存在等待进程集合{ P0, P1 , ... , PN}，P0正在等待P1占用的资源，P1正在等待P2占用的资源，… ，PN-1正在等待PN占用的资源，PN正在等待P0占用的资源。

  需要注意，这四个条件是死锁出现的必要条件，而不是死锁出现的充分条件，因为即使满足四个条件，也有可能遇到可解的情况，比如说前一节的例子3。

4.死锁处理办法

---

  死锁有以下处理办法：

•   Deadlock Prevention       （死锁预防）
•   Deadlock Avoidance        （死锁避免）
•   Deadlock Detection          （死锁检测）
•   Recovery from Deadlock  （死锁恢复）

  其中死锁的处理办法约束一个比一个弱，死锁预防的约束最强，死锁恢复的约束最弱。

  遇到死锁的处理方法主要分为以下几种：

1.   确保系统永远不会进入死锁状态
2.   运行系统进入了死锁状态，想办法恢复
3.   忽略这个问题，假装系统从来没有发生死锁，这种方法用于大多数操作系统，包括UNIX

  为什么会有最后一种方法，出现死锁假装没有出现？因为判断死锁的开销比较大，同时设置一些约束让操作系统不进入死锁页大大限制了操作系统的功能，所以现在的操作系统只能寄希望于程序员写的代码不会出现死锁，真出现死锁了操作系统只能提供调试的手段帮助程序员解决问题。

Deadlock Prevention       （死锁预防）

  死锁预防是不让死锁出现，思路是打破死锁的四个条件。

  预防是采用某种策略，限制并发进程对资源的请求，使系统在任何时刻都不满足死锁的必要条件。我们看看怎么分别确保死锁的必要条件不满足：

•   针对互斥：把互斥的共享资源封装成可同时访问，但有可能引起不确定性的错误。
•   针对占用并等待：进程请求资源的时候，要求它不持有任何其他资源，但有时候进程需要同时持有多个资源才能继续执行；那能不能刚开始进程拿的时候请求整个执行过程所有的资源，比如进程A在t1、t2、t3时刻需要不同资源，但在开始时全部持有并指导执行结束才释放，这样就不用等待，这是一种解决办法，但使得资源利用率极低，可能会发生饥饿。
•   针对无抢占：有了互斥其实就不能抢占，执行抢占其实就是把另一个进程正在执行的状态打破，拥有互斥的另一个进程就没法正常工作了。所以实现抢占一种可行方式就是，如果进程请求不能立即分配资源，则释放已有的资源，只有在能够获得所有需要资源时，才执行分配操作。
•   针对循环等待：循环等待其实就是状态分配图存在环，打破循环等待就是想办法打破环，可以对所有资源类型进行排序，并要求每个进程按照资源的顺序进行申请。

  针对以上四种情况，只要打破一个条件，就可以合理预防死锁。

  Deadlock Avoidance        （死锁避免）

  第二种情况是死锁避免，比死锁预防的约束要宽松一点，思想是在进程进行资源申请的时候判断合不合理，所谓合不合理就是资源的申请有没有可能导致死锁，如果有可能导致死锁，即使有资源也不予分配。死锁避免是一种很有效的方法，但是需要系统具有一些额外的先验信息提供。死锁避免主要包括以下几步：

•   每个进程声明它可能需要的每个类型资源的最大数目
•   限定提供与分配的资源数量，确保满足进程的最大需求
•   死锁避免算法动态检查资源分配状态，以确保永远不会有一个环形等待状态 

  死锁避免简单来说就是针对最后一个必要条件，不让系统出现环形等待。方法是确保系统资源分配处于安全状态，安全状态就是说有一个执行序列，系统按照这个序列分配资源并执行肯定能执行完，这就是一个安全执行死锁

  安全状态是没有环形等待的状态，反推不安全状态就是有环形等待的状态。前面提到有环形等待不一定有死锁，所以死锁是不安全状态的一个子集。

银行家算法（Banker's Algorithm）

  银行家算法是一个死锁避免的著名算法，它是以银行借贷系统的分配策略为基础，判断并保证系统的安全运行。

背景

  在银行系统中，客户完成项目需要申请贷款的数量是有限的，每个客户在洗一次申请贷款时要声明完成该项目所需的最大资金量，在满足所有贷款要求并完成项目时，客户应及时归还。

  银行家在客户申请的贷款数量不超过自己拥有的最大值时，都应尽量满足客户的需要。

  在这样的描述中，银行家就好比操作系统，资金就是资源，客户就相当于要申请资源的进程。

  银行家算法的前提条件：

•   有多个进程，有多个资源的实例
•   每个进程都必须能最大限度地利用资源
•   当一个进程请求一个资源，就不得不等待
•   当一个进程获得所有的资源，就必须在一段有限的时间释放它们

  基于上述前提条件，银行家算法通过尝试寻找允许每个进程获得的最大资源并结束（把资源返还给系统）的进程请求的一个理想执行时序，来决定一个状态是否安全。不满足要求的执行时序的状态是不安全的。

数据结构

  

算法设计

寻找能正常结束的线程（Finish[i] = false && Need[i] <= work），执行完成回收资源(work = work + Allocation[i])，知道所有线程满足Finish[i] == true,则系统处于安全状态，否则不安全。

  有了安全状态判断，就比较好设计算法。

 

示例

  银行家算法的大致思路就是构建出最大需求矩阵C和已分配资源矩阵A，用C-A算出当前资源请求矩阵，通过系统资源总向量R减去现在已用的资源得到当前可用资源向量V，看V的一行数据能满足C-A哪一行（V>C-A[i]）运行完就先让它（i）运行结束，并把资源归还给V，继续循环查找。