死锁

死锁是什么

死锁：各个进程互相等待对方手里的资源，导致各进程都阻塞，无法向前推进
饥饿：由于长期等不到想要的资源，某进程无法向前推进
死循环：某进程执行过程中一直跳不出某个循环的现象

共同点：进程都无法向前推进，估计设计的死循环除外

区别

1. 死锁一定是循环等待对方手里的资源，如果发生死锁，那么至少有两个及以上进程同时发生死锁，发生死锁的进程一定处于阻塞态
2. 饥饿可能只有一个进程，发生饥饿的进程既可能处于阻塞态（比如等不到IO），有可能处于就绪态（比如等不到CPU）
3. 死循环的进程可以上CPU运行
4. 死锁饥饿是操作系统分配资源不当造成，死循环是代码逻辑导致的

四个必要条件

1. 互斥条件：对必须互斥使用的资源进行争抢
2. 不可剥夺条件：进程所获得的资源未使用完之前，不能由其他进程剥夺，只能主动释放
3. 请求和保持条件：进程已经拥有了至少一个资源，并提出新的资源申请，新资源被其他进程占有，该进程被阻塞，但是不释放自己已有的资源
4. 循环等待：存在一种进程的循环等待链，链中每一个进程已获得的资源同时被下一个进程请求

如果同类资源数大于1，即使有循环等待，也不一定发生死锁，如果每类资源只有1个，循环等待就是死锁的充分必要条件

什么时候会发生死锁

对不可剥夺的资源分配不合理

1. 对系统资源的竞争
   对不可剥夺的资源竞争可能引起死锁，可剥夺的不会引起死锁（CPU）
2. 进程推进顺序非法
   p1、p2分别占有了资源r1、r2，又分别申请r2、r1
3. 信号量的使用不当
   生产者消费者问题中，将互斥P操作放在同步P操作之前，就可能导致死锁

预防死锁

1. 破坏互斥条件：将互斥使用的资源改造为允许共享使用的资源。SPOOLing技术
   缺点：并不是所有资源都可以改造成互斥资源，为了系统安全，需要保护互斥性
2. 破坏不可剥夺条件
   2.1. 但某个进程请求的新资源得不到满足时，必须立即释放保持的所有资源，待以后需要时重新申请，也即是资源尚未使用完也需要主动释放
   2.2. 当某个进程需要的资源被其他进程所占有的时候，可以由操作系统协助强行剥夺，这种方式一般需要考虑各进程的优先级
   缺点：实现复杂；释放已获得资源可能造成前一阶段工作失效，一般只适用于易保存易恢复状态的资源；反复申请释放资源会增加系统开销；对方案1只要暂时得不到某个资源，之前获得的资源就需要放弃，之后重新申请，可能导致进程饥饿
3. 破坏请求和保持条件
   在进程运行前一次性申请他所需要的全部资源，在他的资源未满足前，不让他投入运行，一旦运行后，资源就一直归他所有
   优点：实现简单
   缺点：有的资源可能只需要使用很短的时间，如果整个进程运行期间都一直保持所有资源，可能造成严重浪费；也有可能造成某些进程饥饿
4. 破坏循环等待条件
   采用顺序资源分配法，首先给系统中的资源编号，规定进程只能按照编号递增的顺序申请资源，同类资源（编号相同的）一次性申请
   原理分析：一个进程只有已经占有小编号资源才能申请大编号资源，已经有大编号资源就不能返回申请小编号资源，不会产生循环等待的现象
   在任何一个时刻，总有一个进程拥有的资源编号是最大的，这个进程申请之后的资源必然畅通无阻，因此不可能出现所有进程都阻塞的死锁现象
   缺点：不方便增加新的设备，可能需要重新分配所有的编号；进程实际使用资源的顺序可能和编号递增顺序不一致，导致资源浪费；需要按照规定次序申请，用户编程麻烦

避免死锁--银行家算法

安全序列：如果系统按照这种序列分配资源，每个进程都能顺利完成。只要能找到一个安全序列，系统就是安全状态。安全序列可能有多个
如果分配了资源之后，系统中找不出任何一个安全序列，系统就进入了不安全状态，这就意味着之后可能所有进程都无法顺利执行。当然，如果有进程提前归还了一些资源，系统可能重新回到安全状态，但是我们在分配资源之前总是要考虑到最坏的情况
如果系统处于安全状态，就一定不会发生死锁，如果系统进入不安全状态，就可能发生死锁
因此可以在分配资源之前先判断这次分配是否会导致系统进入不安全状态就，以此决定是否答应资源分配请求

银行家算法
假设有n个进程，m个进程
max[i,j] = K表示Pi最多需要K个Rj
allocation[i,j]表示分配
need[i,j]表示还需要最多几个资源
此外还需要一个长度为m的available表示当前系统还有多少可用资源

1. if request_i[j] ≤ need[i,j] for 0≤j≤m, goto 2; else error
2. if request_i[j] ≤ available[j] for 0≤j≤m, goto 3; else Pi has to block and wait
3. try to allocate the resources to Pi, and modify datas
   available, allocation[i], need[I]
4. judge whether the system is in a safe state; if it is safe, allocate the resources formally; else restore datas, let Pi block and wait

总结

1. 检查此次申请是否超过了之前的最大剩余需求数
2. 检查系统当前可用资源是否可以满足此次申请
3. 试探分配，更改数据
4. 用安全性算法检查此次分配是否会导致系统进入不安全状态

安全性算法

1. 检查当前剩余可用资源是否能满足某个进程的最大需求，如果可以，就把该进程加入安全序列，并把该进程持有的资源全部回收
2. 不断重复1，看最后能否将所有进程都加入安全序列

系统处于不安全状态未必死锁，但死锁一定处于不安全状态，处于安全状态一定不会死锁

死锁的检测和解除

死锁的检测
数据结构

如果系统中剩余的可用资源足够满足进程的需求，那么这个进程暂时不会阻塞，可以顺利进行下去
如果这个进程执行结束了把资源归还系统，就可能使某些正在等待资源的进程被激活，并顺利执行
能够消除所有边，就成这个图可完全简化，此时一定没有发生死锁
否则一定发生死锁，最终还连着边的是处于死锁的进程

检测死锁的算法

1. 在资源分配图里，找出既不阻塞又不是孤点的进程Pi，消除它的所有边，使它成为孤点
2. 根据1继续简化，若能消除所有边，就是可完全简化的

死锁定理：如果某时刻系统的资源分配图是不可完全简化的，那么此时系统死锁

死锁的解除

并不是系统中所有的进程都是死锁状态，用死锁检测算法化简资源分配图后，还连着有向边的那些进程就是死锁进程

解除死锁的方法

1. 资源剥夺法：挂起（暂时挂到外存上）某些死锁进程，并抢占他的资源，将这些资源分配给其他死锁进程，但是应防止被挂起的进程长时间等不到资源而饥饿
2. 撤销进程法：强制撤销部分或全部死锁进程，剥夺资源。实现简单，但代价大，有些进程可能已经接近结束，就功亏一篑，还得从头再来
3. 进程回退法：让一个或多个死锁进程回退到足以避免死锁的地步。这要求操作系统记录进程的历史信息，设置还原点

对谁动手

1. 进程优先级低的被搞
2. 已执行时间短的被搞
3. 剩余执行时间长的被搞
4. 已使用资源多的被搞
5. 后台的被搞