【操作系统】进程管理——死锁（个人笔记）
学习日期：2024.7.13
内容摘要：死锁的概念和三大处理策略
目录
死锁
死锁的概念
死锁、饥饿和死循环的区别
死锁产生的必要条件
死锁的处理策略：预防、避免和解除
预防死锁
破坏互斥条件
破坏不剥夺条件
破坏请求和保持条件
破坏循环等待条件
避免死锁
模型引入
解题方法
死锁的检测和解除
死锁
死锁的概念
在《利用信号量机制解决问题》的哲学家进餐问题模型中，我们提到了死锁现象。在那个问题中，每个哲学家拿着一根筷子，每个哲学家都无法完成进餐。在这个模型中，每个人都占有一个资源，同时都在等待别人手上的资源，等到天荒地老也不会等到，这样就是发生了死锁。
死锁，就是在并发环境下，各个进程因为争抢资源而导致的一种互相等待对方手里的资源，而所有进程都阻塞，无法向前推进的现象。
发生死锁后，如果没有外力（操作系统）干涉，所有的进程都无法推进。
死锁、饥饿和死循环的区别
死锁：各进程互相等待对方手里的资源，导致所有进程都阻塞的现象。
饥饿：由于长期得不到想要的资源，某进程无法向前推进的现象。
死循环：某进程执行过程中一直跳不出某个循环的现象。有时是因为程序逻辑bug，有时是程序员故意设计的（比如之前介绍的PV操作当中的自旋锁）。
死锁一定是等待对方手里的资源，且发生死锁的进程全部都推进不了。而饥饿，比如说短作业优先算法中，长作业可能会饥饿，但是短作业是一直在推进的。
死锁产生的必要条件
互斥条件：只有对必须互斥使用的资源的争抢才会导致死锁。（如果可以共用筷子就不会死锁了）
不剥夺条件：进程所获得的条件在未使用完之前，不能由其它进程夺走，只能主动释放。（如果哲学家可以抢别人的筷子，就不会死锁了）
请求和保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其它进程所占有，此时请求进程被阻塞，但又会对自己已有的资源保持不放。（如果哲学家会在阻塞时放下筷子，就不会死锁了）
循环等待条件：存在一种进程资源的循环等待，链中的每一个进程已经获得的资源同时被下一个进程所请求。（如果最后等待资源的请求没有连成圈，就不会死锁了）
以上四个条件必须全部满足，缺一不可，就会发生死锁。
发生死锁时一定有循环等待，但是发生循环等待时未必死锁！比如说，此时发生了循环等待，但是如果3号哲学家有个朋友进程，正在给他送筷子，他在循环等待的同时也在等待朋友送来筷子，这样在一定的等待时间后，3号哲学家就可以开始进食，就不会死锁。
对不可剥夺资源的不合理分配，可能会导致死锁。
死锁的处理策略：预防、避免和解除
预防死锁
预防死锁主要是破坏死锁产生的四个必要条件。
破坏互斥条件
如果把只能互斥使用的资源改造为允许共享使用，则系统不会进入死锁状态。
比如SPOOLing技术，操作系统可以把进程对临界资源（如打印机）的请求装进一个输出进程队列里，然后输出进程再依次调用打印机，这样对进程来说，对打印机的访问就不互斥了。
破坏不剥夺条件
①当某个进程请求新资源得不到满足时，它必须立即释放保持的所有资源，待以后需要时再申请。
②当某个进程需要的资源被其它进程所占用的时候，可以由操作系统协助，将想要的资源强行剥夺（从其它进程那里抢过来）。这种方式一般需要考虑各进程的优先级。
缺点：
1.实现比较复杂。
2.释放已经获得的资源可能导致前一阶段工作的失效，因此这种方法一般只适用于易保存和恢复状态的资源。
3.反复地申请和释放资源会增加系统开销，降低系统吞吐量。
4.若采用方案①，意味着只要暂时得不到某个资源，之前获得的那些资源就都需要放弃，以后再重新申请。如果一直发生这样的情况，就会导致进程饥饿。
破坏请求和保持条件
可以采用静态分配方法，即进程在运行前一次申请完它所需要的全部资源，在它的资源未满足前，不让它运行。一旦投入运行后，这些资源就一直归它所有，该进程就不会请求其它资源了。
即哲学家一次申请左右两根筷子，不会拿着筷子等待，这样就不会死锁了。
缺点：有的资源可能只需要使用极短的时间，但是在进程运行时一直占用，会造成资源浪费。
破坏循环等待条件
可采用顺序资源分配法，首先给系统中的资源编号，规定每个进程必须按编号递增的顺序请求资源，编号相同的资源一次申请完。
还是以哲学家进餐问题为例。0号哲学家需要0，1筷子，1号需要1，2...但4号哲学家需要的是4号筷子和0号筷子。
极端情况下，0号哲学家拿0号筷子，1号哲学家拿1号筷子......但是，4号哲学家不会拿起4号筷子然后使所有进程循环等待。因为在使用顺序资源分配法后，4号哲学家在拿起4号筷子前要先拿起0号筷子，但此时0号筷子已经被0号哲学家占用，所以4号筷子会在不占用资源的情况下阻塞，避免了死锁。
这是因为，如果要发生死锁，就必然会有循环等待，而只要循环等待，这个“圈”就有个“头尾接口”，我们只需要按编号大小顺序分配资源，就可以破坏“接口”处的循环等待条件。
缺点：
1.不方便新增设备，因为可能需要重新编号。
2.进程实际使用资源的顺序可能和资源编号递增的顺序不一致，导致资源浪费。
3.必须按规定顺序申请资源，用户编程麻烦。
避免死锁
模型引入
避免死锁的核心是避免系统进入不安全状态，以银行家算法为例。
你是一个银行家，手里有100亿资金，然后有B、A、T三个企业想找你贷款，B最多贷70亿，A最多贷40亿，T最多贷50亿。但是你们这个贷款很奇特，如果你借给企业的钱的总数达不到企业提出的最大要求，那么不管你之前借了多少钱，企业都不用还了。（什么慈善家）
一开始，BAT三个企业分别从你这里借了20，10，30亿，掰手指可得你还剩40亿
| 企业 | 最大需求 | 已借走 | 最多还会借 |
| B | 70 | 20 | 50 |
| A | 40 | 10 | 30 |
| T | 50 | 30 | 20 |
此时，如果B还想借30亿，你借不借呢？
| 企业 | 最大需求 | 已借走 | 最多还会借 |
| B | 70 | 20+30=50 | 50-30=20 |
| A | 40 | 10 | 30 |
| T | 50 | 30 | 20 |
掰手指可得，如果借出去，我们手里还剩10亿，但剩下三个公司都可能借更多的钱，无法满足需求，我们会破产，这样不安全。所以不能答应B的请求。
如果A还想借20亿，你借不借呢？
| 企业 | 最大需求 | 已借走 | 最多还会借 |
| B | 70 | 20 | 50 |
| A | 40 | 10+20=30 | 30-20=10 |
| T | 50 | 30 | 20 |
我们现在手上还剩20亿，可以满足A或T的需求，可以先全部借给T，等T还回来了，我们手上就有50亿了，再借给B，满足他的需求，最后借给A就行。这个顺序无所谓，也可以先全部借给A。所以是可以借的，我们不会破产，是安全的。
在这种情况下，我们把形如A->T->B或者T->B->A这种的序列叫做安全序列。
所谓安全序列，就是如果系统按照这种序列分配资源，则每个进程都能顺利完成，只要能找出一个安全序列，系统就是安全状态，反之则是不安全状态，安全序列可能有多个。
如果系统处于不安全状态，就可能发生死锁。（不安全状态是死锁的必要不充分条件）
因此，我们可以在资源分配之前预先判断这次分配是否会导致系统进入不安全状态，以此决定是否答应资源分配请求，这也是“银行家算法”的核心思想。
在这个模型中，我们手上的钱就是临界资源，三个企业是三个进程，在第二种情况，我们手上的钱一个进程都满足不了的时候，就发生了死锁。
银行家算法是荷兰学者Dijkstra为银行系统设计的(没错又是这个人)，一开始真的是用来在银行发放贷款时避免不会满足所有用户需要的情况，后来用于操作系统避免死锁。
所需资源可能不止一种，在这种情况下，我们用形如（3，1，1）这样的格式记录进程所需的资源和所缺的资源。
解题方法
例：资源总数(10,5,7)，问此时系统是否处于安全状态。
用资源总数做减法运算得，剩余资源(3,3,2)，最多还需要的资源，用最大需求资源减已分配即可。
然后检查剩余资源能满足哪个最多还需要的资源。比如说满足P1，那就分给P1，P1运行完成后释放(2,0,0)，剩余资源变为(5,3,2)，能满足P3，P3释放资源，变为(7,4,3)...以此类推，每次满足可以满足的进程，释放资源即可。
好比带兵打仗，一开始兵（资源）少，就先满足容易满足的进程，打败它们后“招降”他们，解放更多的兵力，然后用更多的兵力“打败”更多的进程，最后就能满足最难的需求。如果在某个情况下全都满足不了，系统就是处于不安全状态。
银行家算法就是把最大需求、已分配、最多还需要的资源，分别用矩阵保存，然后在分配资源之前，系统会先在数据结构中尝试分配，然后用安全性算法检查此次分配是否会导致系统进入不安全状态。
所谓安全性算法，就是在做我们刚刚做的事，检查当前的可用资源能否满足某个进程的最大需求，如果可以，就把该进程加入安全序列，并模拟回收该进程的资源，然后重复，直到判断最后能否让所有进程加入安全队列。
死锁的检测和解除
死锁的检测和解除允许死锁发生，由系统负责检测出死锁并解除。
为了能实现这一功能，必须
①用某种数据结构保存资源的请求和分配信息，这种数据结构叫资源分配图。
②提供一种算法，利用信息检测系统是否已经进入死锁状态。
如图，P2进程此时请求1个R1资源（一个指向R1的蓝箭头），但是3个R1资源都分配出去了（三个出去的绿箭头）所以P2会阻塞。而P1正在请求R2资源，R2资源还剩下一个，是可以分配给P1的，所以P1能够执行完。在P1执行完之后，释放所有资源，删去连着P1的箭头，此时就可以将R1资源分配给R2了。
所以根据这样一幅图，我们能看出进程的运行顺序，和系统是否死锁，如果最终能消除所有边，就说图是完全可简化的，此时一定不会死锁。
如图，此时P2请求1个R1资源，但R1资源已经全部分配完了。P1请求2个R2资源，但是R2资源已经分配了一个给P2，数量不够，无法完全简化，这样就发生了死锁。
一旦检测出死锁的发生，就应该立刻解除死锁。并不是系统中所有的进程都是死锁状态，用死锁检测算法化简资源分配图后，还连着边的进程就是死锁进程。
解决死锁的主要方法有：
1.资源剥夺法。挂起（暂时放到外存上）某些死锁进程，并抢占其资源，将这些资源分配给其它的死锁进程。但是应防止挂起的进程长时间得不到资源而饥饿。
2.撤销进程法。强制撤销部分甚至全部死锁进程，剥夺它们占用的资源。实现简单但是过于粗暴，可能导致很多即将完成的进程“功亏一篑”。
3.进程回退法。让部分死锁的进程回退到足以避免死锁的地步，但这要求系统要记录进程的历史信息，设置还原点。
抢谁的资源？如何决定“对谁动手”——欺负软柿子
进程优先级高的、执行时间长的、快要完成的、交互式的（重视即时反馈的）少动手。
欺负优先级低的、批处理的、占用资源多的。
感谢您看到这里，如果满意的话麻烦您点个赞支持一下，个人主页还有更多内容分享。
个人能力不足，如有错漏还请指出，我会尽快修改。
内容总结自王道计算机考研《操作系统》 和 人民邮电出版社《操作系统导论》
