Version: Next
死锁
死锁、饥饿、死循环
死锁：各进程互相等待对方手里的资源，导致各进程都阻塞，无法向前推进的现象
饥饿：由于长期得不到想要的资源，某进程无法向前推进的现象。例如在短进程优先 SPF 算法中，若有源源不断的短进程到来，则长进程将一直得不到处理机，发生饥饿
死循环：某进程执行过程中一直跳不出某个循环的现象，有时是因为 BUG，有时是程序员故意设计
| 共同点 | 区别 | |
|---|---|---|
| 死锁 | 进程无法继续推进 | 死锁一定是循环等待对方手里的资源导致的，因此发生死锁，至少有两个或两个以上的进程同时发生死锁。另外，发生死锁的进程一定处于阻塞态 |
| 饥饿 | 进程无法继续推进 | 可能只有一个进程发生饥饿。发生饥饿的进程既可能是阻塞态（如长期得不到需要的IO设备），也可能是就绪态（长期得不到处理机） |
| 死循环 | 进程无法继续推进 | 可能只有一个进程发生死循环。死循环可能发生在运行态，只是无法像预期一样顺利推进。可能是代码逻辑有问题，不一定是得不到资源。死锁和饥饿是管理者（操作系统）的问题，死循环是被管理者的问题 |
死锁产生的四个必要条件
必须同时满足四个条件，任意一条不成立，死锁就不会产生
- 互斥条件：只有对必须互斥使用的资源的争抢才会导致死锁（如打印机）而扬声器这样可以同时被多个进程使用的资源不会导致死锁
- 不可剥夺条件：进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放
- 请求和保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程被阻塞，但又对自己已经持有的资源保持不放
- 循环等待条件：存在一种进程资源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程所请求
注意
发生死锁时一定发生循环等待，但发生循环等待时不一定产生死锁
死锁的处理策略
- 预防死锁：破坏产生死锁的四个必要条件中的一个或者多个
- 避免死锁：用某种方法防止系统进入不完全状态，从而避免死锁（银行家算法）
- 死锁的检测和解除：允许死锁发生，不过操作系统会负责检测出死锁的发生，然后才去某种措施解除死锁
预防死锁
破坏互斥条件
- 把只能互斥使用的资源改造成允许共享使用的资源（SPOOLing 技术）
- 缺点：并不是所有的资源都可以改造成可共享使用的资源，并且为了系统安全，很多地方还必须保留互斥性，因此很多时候无法破坏互斥条件
破坏不可剥夺条件
- 方案一：当某个进程请求新的资源得不到满足时，它必须立即释放保持的所有资源，待以后需要时再重新申请。即使某些资源尚未使用完，也需要主动释放，从而破坏了不可剥夺条件
- 方案二：当某个进程需要的资源被其他进程所占有的时候，可以由操作系统协助，将想要的资源强行剥夺。这种方式一般需要考虑各进程的优先级
- 缺点：
- 实现复杂
- 释放已获得的资源可能造成前一阶段工作实效。因此这种方法一般只适用于易保存和恢复状态的资源，如 CPU
- 反复地申请和释放资源会增加系统开销，降低系统吞吐量
- 若采用方案一，意味着只要暂时得不到资源，之前得到的资源都要放弃，以后重新申请。如果一直这样，就产生了饥饿
破坏请求和保持条件
- 静态分配法：进程在运行前一次申请完它所需要的全部资源，在它的资源未满足前，不让它投入运行，一旦投入运行后，这些资源就一直归他所有，该进程就不会再请求别的任何资源
- 缺点：
- 有些资源只需要使用很短的时间，因此如果进程的整个运行期都一直保持着所有资源，就会造成严重的资源浪费，资源利用率极低，另外该策略也可能导致饥饿
破坏循环等待条件
- 顺序资源分配法：首先给系统中的资源编号，规定每个进程必须按编号递增的顺序请求资源，同类资源（即编号相同的资源）一次申请完
- 一个进程只有占有小编号的资源时，才有资格申请更大编号的资源，按此规则，已持有大编号资源的进程不可能逆向地回来申请小编号资源，就不会发生循环等待
- 缺点
- 不方便增加新设备，因为可能需要重新分配所有编号
- 进程实际使用资源的顺序可能和编号递增顺序不一致，导致资源浪费
- 用户编程麻烦
避免死锁
安全序列
- 指如果系统按照这种序列分配资源，则每个进程都能顺利完成，只要找出一个安全序列，系统就是
安全状态，安全序列可能不唯一 - 如果找不到任何一个安全序列，系统就进入
不安全状态。意味着之后可能所有进程都无法顺利执行下去，但如果有进程提前归还了一些资源，则系统也可能重新回到安全状态
安全序列、不安全状态、死锁的联系
- 如果系统处于
安全状态，一定不会发生死锁 - 如果系统处于
不安全状态，可能发生死锁 - 可以再资源分配前预先判断这次分配是否会导致系统进入不安全状态，以决定是否答应资源分配，这就是
银行家算法的核心思想
银行家算法
荷兰学者 Dijkstra 为银行系统设计，以确保银行在发放现金贷款时，不会发生不能满足所有客户需要的情况。后被应用于操作系统中，用于避免死锁
死锁的检测与解除
检测
- 用某种数据结构来保存资源的请求和分配信息
- 提供一种算法，利用上述信息来检测系统是否进入死锁状态
资源分配图：
- 两种节点
- 进程节点：对应一个进程
- 资源节点：对应一类资源，一类资源可能有多个
- 两种边
- 进程节点 → 资源节点：表示进程想申请几个资源（每条边代表一个）
- 资源节点 → 进程节点：表示已经为进程分配了几个资源（每条边代表一个）
- 如果系统中剩余的可用资源足够满足进程的需求，那么这个进程暂时不会阻塞，可以顺利执行下去
- 如果这个进程执行结束了把资源归还给系统，就可以使某些正在等待资源的进程被激活，并顺利执行下去
- 以此类推
- 如果可以消除所有边，称图是可以
完全简化的，说明未发生死锁，相当于找到安全序列- 如果最终不能消除所有边，那么就发生了死锁，最终还连着边的进程就是处于死锁状态的进程
解除
资源剥夺法
- 挂起（暂时存到外存上）某些死锁进程，并抢占它的资源，将这些资源分配给其他死锁的进程，但是应防止被挂起的进程长时间得不到资源发生饥饿
撤销进程法
终止进程法，强制撤销部分、甚至全部死锁进程，并剥夺资源。非常简单粗暴进程回退法
- 让一个或多个死锁进程回退到足以避免死锁的地步，这就要求系统记录进程的历史信息，设置还原点
对谁动手？
- 根据线程优先级
- 根据线程运行时间
- 根据线程还有多久执行完毕
- 根据进程已经使用的资源
- 根据进程是交互式的还是批处理式的