操作系统笔记 CH7 Deadlocks

deadlock characteristics

4个条件同时满足，引起死锁：

request edge : Pi->Rj

assignment edge : Rj->Pi

申请边只用指向矩形，但分配边必须从某个原点开始

资源分配图有环是死锁的必要条件。若每类资源只有一个实例，含环是充分必要条件。若同类资源数>1,不一定有死锁。

1.预防或避免死锁

2.允许进入死锁，检测并恢复

3.忽视这个问题(为多数OS所用)

deadlock prevention: 确保至少一个必要条件不成立，通过限制如何申请资源

deadlock avoidance: 事先得到进程申请和使用资源的额外信息，系统可确定对于一个申请，进程是否等待(申请允许还是延迟)，考虑可用、已分配、进程将来申请和释放的资源

确保4个必要条件至少1个不成立

mutual exclusion

通常不通过这个条件…
hold and wait
- 每个进程在执行前申请并获得所有资源
- 进程在没有资源时才可申请资源(申请更多资源前，先释放已分配的资源)
缺点:1.资源利用率低 2.starvation
no preemption

如果一个进程占有资源并申请另一个不能立即分配的资源，其现在已分配的资源都可被抢占(被隐式释放)。

进程申请资源时，不可用也不被其他等待进程占有时，等待

常应用于状态可以保存恢复的资源，如CPU寄存器和内存，不适用于打印机和磁带驱动器等。
circular wait

对所有资源类型进行完全排序。每个进程只按递增顺序申请资源。(只能申请编号比它大的)

死锁避免比死锁预防要求低

deadlock prevention 低设备使用率和吞吐率

a system is in a safe state only if there exists a safe sequence

增加claim edge(需求边)，虚线

当进程Pi开始执行时，所有需求边必须先处于资源分配图。(可放宽为只要与Pi有关的需求边)

只有在申请边Pi->Rj变成分配边Rj->Pi，而不会出现环时，才允许申请。环存在是unsafe state

cycle-detection algorithm

自己看书做题去 P247

不采用prevention和avoidance，应提供检查是否出现死锁&恢复算法。

wait-for graph: Pi等待Pj释放一个Pi需要的资源

Pi->Pj iff 资源分配图中 Pi->Rq, Rq->Pj

图中有环 <-> 死锁

detection algorithm

PPT P45 + 看橘

不管哪种进程终止方法，系统都会收回分配给终止进程的所有资源

select a victim: which resources and which processes are to be preempted 代价因素 cost factors

rollback: 抢占资源后对进程做什么安排 roll back to some safe state. simplest: total rollback

starvation: 如何保证资源总是从一个进程抢占在代价因素中加上回滚次数

最后修改于 2020-02-28