#死锁 在多道程序环境下，多个进程可能竞争一定数量的资源。而当某个进程申请资源时，而如果这是该资源不可用，那么该进程便进入等待状态。而如果所申请的资源是被其他等待进程占有，那么该等待进程有可能再也无法改变其状态。这种状况就叫做死锁。即在无外力作用下，两个互相等待的进程将永远无法执行完成，只能保持互相等待的状态。
##系统模型
- 资源：资源可分为多种类型，每种类型具有一定数量的实例。比如，内存空间、cpu周期、文件、I/O设备（打印机或DVD驱动器）
-
使用模型：“申请–分配–使用–释放”模式
进程在使用资源前必须申请资源，在使用完毕前必须释放资源。申请不被允许（申请的资源被其他进程所使用）时，申请进程必须等待，直到它获得该资源位置。
##必要条件
- 互斥：至少有一种资源必须处于非共享模式。即一个资源在被一个进程使用时，另一个进程是无法使用该资源的。除非正在使用的进程执行完毕，释放了该资源。
- 占有并等待：一个进程必须占有至少一个资源，并等待一被另外进程资源占有的资源。
- 非抢占：资源不能被抢占
- 循环等待：在资源分配图中，存在环。比如，P0等待P1占有的资源，P1等待P2占有的资源，而且P2等待P0占有的资源。
##死锁处理方法
- 使用协议来预防或避免死锁
- 忽略死锁，再通过周期检测。检测到死锁，对此加以恢复。
- 忽略死锁问题，认为死锁不会发生。（让程序开发者，写程序时，自己处理，保证不会有死锁产生）
###死锁预防 死锁预防是一组方法，以确保至少一个必要条件不成立。（缺点：导致低设备利用率和系统吞吐率)
- 破坏“互斥” 保证所有资源都是共享资源。比如 多次读取文件
- 破坏“占有并等待”：
- 要求每个进程在运行前必须一次性申请它所要求的所有资源，且仅当该进程所要资源均可满足时才给予一次性分配。
- 允许进程在没有资源时，才可申请资源。
-
破坏“非抢占” 在允许进程动态申请资源前提下规定，一个进程在申请新的资源不能立即得到满足而变为等待状态之前，必须隐式释放已占有的全部资源，若需要再重新申请
-
破坏“循环等待”条件
采用资源有序分配法： 把系统中所有资源编号，进程在申请资源时必须严格按资源编号的递增次序进行，否则操作系统不予分配。
###死锁避免
通过一些额外的信息，来衡量某些进程申请的资源是否分配。
####安全状态####
（概念补充）：
- 存在一个安全的序列，使进程能按该序列不死锁的运行，则说明系统处于安全状态。
- 安全状态不是死锁状态。相反，死锁状态是不安全状态。然而，不是所有不安全状态都能导致死锁状态。不安全状态，主要表明的是 操作系统不能阻止进程以会导致死锁的方式申请资源。关系图，如图所示：
-
资源分配图算法
针对的是每种资源只有一个实例的情况。其主要就是保证在资源分配图中不存在环即可。
-
银行家算法 针对的是每种资源类型有多个实例的资源分配系统。这个具体细节 下篇博文发^v^.
###死锁检测
通过一个算法周期检测当前状态下是否存在死锁。若有，则纠正死锁状态。
1.每种资源只有单个实例情况 从资源分配图中，删除所有资源类型节点，合并适当边，就可以得到等待图。如图所示：
接下来只需要维护等待图，保证其不出现环即可。（若出现，则通过一定策略，消去）
###死锁恢复 ####1.进程终止
- 终止所有死锁进程
- 一次终止一个进程直到取消死锁循环为止。 （最好选择一个“代价最小”的进程先终止）
####2.资源抢占 通过资源抢占来取消死锁，逐步从进程中抢占资源给其他进程使用，直到死锁环被打破为止。 问题：
- 如何选择牺牲品（代价最小）
- 如何回滚：即执行完毕后，必须将进程回滚到某个安全状态，以便从该状态重启进程。
- 如何确保不会发生饥饿
典型习题
####7.2
考虑如下的死锁可能发生在哲学家进餐中，哲学家在同个时间获得筷子。讨论此种情况下死锁的四个必要条件的设置。讨论如何在消除其中任一条件来避免死锁的发生。
死锁是可能的，因为哲学家进餐问题是以以下的方式满足四个必要条件：
1）互斥 所需的筷子互斥，一个哲学家两边只有两只筷子
2）持有并等待：哲学家手里拿着一只筷子，并等待另一只筷子
3）非抢占：一只筷子分配给一个哲学家后不能被强行拿走
4）循环并等待：可能出现一种情况，每个哲学家都有一双筷子并等待另一只筷子的到来。
死锁可避免克服的条件方式如下：
1）破坏互斥：允许同时分享筷子
2）破坏持有并等待：若哲学家无法获得第二双筷子，则立即放弃第一双筷子
3）允许抢占：如果另一哲学家已等待这一哲学家筷子很久，则允许筷子被另一哲学家强行拿走
4）破坏循环等待：实施筷子编号，总是获得较低编号的筷子，之后才能获得较高的编号的筷子。
####7.5 在一个真实的计算机系统中，可用的资源和进程命令对资源的要求都不会持续很久是一致的长期（几个月）。资源会损坏或被替换，新的进程会进入和离开系统，新的资源会被购买和添加到系统中。如果用银行家算法控制死锁，下面哪些变化是安全的（不会导致可能的死锁） ，并且在什么情况下发生？
a. 增加可用资源（新的资源被添加到系统）
b. 减少可用资源（资源被从系统中永久性地移出）
c. 增加一个进程的Max（进程需要更多的资源，超过所允许给予的资源） d. 减少一个进程的Max（进程不再需要那么多资源）
e. 增加进程的数量
f. 减少进程的数量
解答：
a. 增加可用资源（新的资源被添加到系统）：这个可以在没有任何问题的情况下安全地改变 b. 减少可用资源（资源被从系统中永久性地移出）：这可能会影响到系统，并导致可能性死锁，因为系统的安全性假定其拥有一定数量的可用资源 c. 增加一个进程的Max（进程需要更多的资源，超过所允许给予的资源）：这可能会影响到系统，并可能导致死锁 d. 减少一个进程的Max（进程不再需要那么多资源）：这个可以在没有任何问题的情况下安全地改变 e. 增加进程的数量：如果允许分配资源给新进程，那么该系统可能进入一个不安全的状态。 f. 减少进程的数量：这个可以在没有任何问题的情况下安全地改变
####7.6
假设系统中有四个相同类型的资源被三个进程共享。每个进程最多需要两个资源。证明这个系统不会死锁。
证明：假设该系统陷入死锁。这意味着，每一个进程持有一个资源，并且正等待另一个资源。因为有三个进程和四个资源，一个进程就必须获取两个资源。这一进程并不需要更多的资源，它可以立即执行，不需等待。因此当其完成时会返回其资源。
####7.7 假设一个系统有 m 个资源被 n 个进程共享，进程每次只请求和释放一个资源。证明只要系统符合下面两个条件，就不会发生死锁： a.每个进程需要资源的最大值在 1 到 m 之间 b.所有进程需要资源的最大值的和小于 m+n
证明： 假设n个进程的MAXi＝｛x1，x2，…xn} x1+x2+…xn<m+n 1<Max{x1,x2,..xn}<m 如果存在死锁，那么发生死锁时，所有资源都被分配，即Allocationi的累加和应为m。而Allocation与Need的累加和等于MAXi的累加和，即累加和Allocation＋Need＝MAX<m+n => m+Need<m+n =»Need<n 得到Need的累加和小于n。那么，对于n个进程必有一个进程其仍需的资源为0.而所需资源为0的进程，可直接执行，执行完后释放资源。即不可能存在死锁
