操作系统之死锁
三、死锁
3.1、关于死锁
死锁就是在并发环境下，各进程因竞争资源而造成的一种互相等待对方手里的资源，导致各进程都阻塞，都无法向前推进的现象，发生死锁后若无外力干涉，这些进程都将无法向前推进。
- 死锁产生的必要条件
产生死锁必须同时满足以下四个条件，只要其中任一条件不成立，死锁就不会发生。
①互斥条件：只有对必须互斥使用的资源的争抢才会导致死锁。( 如哲学家用餐问题)，像内存、扬声器这样可以同时让多个进程使用的资源是不会导致死锁的(因为进程不用阻塞等待这种资源)。
②不剥夺条件：进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放。
③请求和保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程被阻塞，但又对自己已有的资源保持不放。
④循环等待条件：存在一种进程资源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程所请求。
注意，发生死锁时一定有循环等待，但是发生循环等待时未必死锁。
如果同类资源数大于1,则即使有循环等待，也未必发生死锁。但如果系统中每类资源都只有一个，那循环等待就是死锁的充分必要条件了。
- 什么时候发生死锁？
①对系统资源的竞争。各进程对不可剥夺的资源( 如打印机)的竞争可能引起死锁，对可剥夺的资源(CPU)的竞争是不会引起死锁的。
②进程推进顺序非法。请求和释放资源的顺序不当，也同样会导致死锁。例如，并发执行的进程P1、P2分别申请并占有了资源R1、R2，之后进程P1又紧接着申请资源R2，而进程P2又申请资源R1,两者会因为申请的资源被对方占有而阻塞，从而发生死锁。
③信号量的使用不当也会造成死锁。如生产者–消费者问题中，如果实现互斥的P操作在实现同步的P操作之前，就有可能导致死锁。(可以把互斥信号量、同步信号量也看做是一种抽象的系统资源)
总之，对不可剥夺资源的不合理分配，可能导致死锁。
3.2、死锁的处理策略
死锁的处理策略通常情况是分为允许死锁发生和不允许死锁的发生，不允许死锁发生又分为静态策略和动态策略，其中静态策略就是预防死锁，动态策略就是避免死锁。允许死锁发生包括死锁的检测和死锁的解除。下面分别讨论预防死锁、避免死锁、检测死锁和解除死锁。
- 预防死锁：通过设置某些限制条件，去破坏产生死锁的四个必要条件中的一个或几个条件，来防止死锁的发生。
- 避免死锁：在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免死锁的发生。
- 检测死锁：允许系统在运行过程中发生死锁，但可设置检测机构及时检测死锁的发生，并采取适当措施加以清除。
- 解除死锁：当检测出死锁后，便采取适当措施将进程从死锁状态中解脱出来。
（1）预防死锁
- 破坏互斥条件
就是在系统里取消互斥。若资源不被一个进程独占使用，那么死锁是肯定不会发生的。但一般来说在所列的四个条件中，“互斥”条件是无法破坏的。因此，在死锁预防里主要是破坏其他几个必要条件，而不去涉及破坏“互斥”条件。比如SPOOLing技术，操作系统可以采用SPOOLing技术把独占设备在逻辑上改造成共享设备，比如用SPOOLing技术将打印机改成共享设备，但是通常破坏互斥条件时比较困难的，因为为了安全系统的保证，很多地方不虚保护这种互斥性。
- 破坏不可剥夺条件
不可剥夺条件：进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放。
方案1：即使某些资源尚未使用完，也需要主动释放，从而破坏了不可剥夺条件。
方案2：当某个进程需要的资源被其他进程所占有的时候，可以由操作系统协助，将想要的资源强行剥夺。
该策略的缺点:
①实现起来比较复杂；
②释放已获得的资源可能造成前一阶段工作的失效。因此这种方法一般只适用于易保存和恢复状态的资源，如CPU；
③反复地申请和释放资源会增加系统开销，降低系统吞吐量；
④若采用方案一，意味着只要暂时得不到某个资源，之前获得的那些资源就都需要放弃，以后再重新申请。如果一直发生这样的情况，就会导致进程饥饿。
- 破坏请求和保持条件
请求和保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程被阻塞，但又对自己已有的资源保持不放。
可以采用静态分配方法，即进程在运行前一次申请完它所需要的全部资源，在它的资源未满足前，不让它投入运行。一旦投入运行后，这些资源就一直归它所有， 该进程就不会再请求别的任何资源了。
该策略实现起来简单，但也有明显的缺点:
有些资源可能只需要用很短的时间，因此如果进程的整个运行期间都一直保持着所有资源，就会造成严重的资源浪费，资源利用率极低。另外，该策略也有可能导致某些进程饥饿。
- 破坏循环等待条件
循环等待条件：存在一种进程资源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程所请求。
可采用顺序资源分配法。首先给系统中的资源编号，规定每个进程必须按编号递增的顺序请求资源，同类资源(即编号相同的资源) 一次申请完。
原理分析:一个进程只有已占有小编号的资源时，才有资格申请更大编号的资源。按此规则，已持有大编号资源的进程不可能逆向地回来申请小编号的资源，从而就不会产生循环等待的现象。
在任何一个时刻，总有一个进程拥有的资源编号是最大的，那这个进程申请之后的资源必然畅通无阻。因此，不可能出现所有进程都阻塞的死锁现象。
该策略的缺点:
①不方便增加新的设备，因为可能需要重新分配所有的编号:
②进程实际使用资源的顺序可能和编号递增顺序不一致，会导致资源浪费:
③必须按规定次序申请资源，用户编程麻烦。
（2）避免死锁
安全序列、不安全状态、死锁的联系？
安全序列，就是指如果系统按照这种序列分配资源，则每个进程都能顺利完成。只要能找出一个安全序列，系统就是安全状态。当然，安全序列可能有多个。
不安全状态可能会产生死锁，死锁一定是系统处于不安全的状态。
- 避免死锁的方法：银行家算法
银行家算法核心思想：可以在资源分配之前预先判断这次分配是否会导致系统进入不安全状态，以此来决定是否答应资源的分配的请求。如果会发生不安全状态，就暂时不答应这次请求，让该进程先阻塞等待。
（1）算法所需要的数据结构：
长度为m的一维数组Avilable表示还有多少可用资源nxm矩阵Max表示各进程对资源的最大需求数nxm矩阵Alocation表示已经给各进程分配了多少资源Max - Alocation= Need矩阵表示各进程最多还需要多少资源
用长度为m的一维数组Request表示进程此次申请的各种资源数[ j ]
（2）银行家算法步骤：
①检查此次申请是否超过了之前声明的最大需求数；
②检查此时系统剩余的可用资源是否还能满足这次请求；
③试探着分配，更改各数据结构的值；
④用安全性算法检查此次分配是否会导致系统进入不安全状态。
安全性算法步骤：
检查当前的剩余可用资源是否能满足某个进程的最大需求，如果可以，就把该进程加入安全序列，并把该进程持有的资源全部回收。不断重复上述过程，看最终是否能让所有进程都加入安全序列。
（3）死锁的检测
死锁检测算法:用于检测系统状态，以确定系统中是否发生了死锁。
为了能对系统是否已发生了死锁进行检测，必须：
①用某种数据结构来保存资源的请求和分配信息；
②提供一种算法， 利用上述信息来检测系统是否已进入死锁状态。
死锁定理：如果某时刻系统的资源分配图是不可完全简化的，那么此时系统死锁。
检测死锁的算法：
①在资源分配图中，找到既不阻塞又不是孤点的进程 Pi（即找出一条有向边与它相连，且该有向边对应资源的申请数量小于等于系统中已有空闲资源数量）。消去它所有的请求边和分配边，使之成为孤立的结点。
在这里要注意一个问题，判断某种资源是否有空闲，应该用它的资源数量减去它在资源分配图中的出度。
②进程 Pi 所释放的资源，可以唤醒某些因等待这些资源而阻塞的进程，原来的阻塞进程可以变为非阻塞进程。根据①中的方法进行一系列简化后，若能消去图中所有的边，则称该图是可完全简化的。
（4）死锁的解除
死锁解除算法:当认定系统中已经发生了死锁，利用该算法可将系统从死锁状态中解脱出来。
但是也并不是系统中所有的进程都是死锁状态，用死锁检测算法化简资源分配图后，还连着边的那些进程就是死锁进程。
一旦检测出死锁，就应立即釆取相应的措施，以解除死锁，死锁解除的主要方法有：
- 资源剥夺法。挂起某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。但应防止被挂起的进程长时间得不到资源，而处于资源匮乏的状态。
- 撤销进程法。强制撤销部分、甚至全部死锁进程并剥夺这些进程的资源。撤销的原则可以按进程优先级和撤销进程代价的高低进行。
- 进程回退法。让一（多）个进程回退到足以回避死锁的地步，进程回退时自愿释放资源而不是被剥夺。要求系统保持进程的历史信息，设置还原点。