一、死锁的概念

1.1 死锁、饥饿、死循环对比

1.1.1 死锁（Deadlock）

教科书解释：
死锁是操作系统中的一种状态，指两个或多个进程在执行过程中，因争夺资源而造成的一种相互等待的现象。每个进程都占用着一些资源而又等待着其它进程所占有的资源，导致所有进程都无法向前推进，整个系统因此陷入停滞。（至少有两个及以上的进程同时发生死锁）。

通俗易懂的解释：
想象几个小朋友围坐一圈，每个人手里拿着一个玩具，同时又想要隔壁小朋友的玩具。没有一个小朋友愿意先放弃手中的玩具，大家都等着别人先给，结果就是所有人都没法得到新玩具，大家都不玩了。这就是死锁，每个人都卡住了，啥事也干不了。

1.1.2 饥饿（Starvation）

教科书解释：
饥饿是指一个或多个进程由于系统资源分配策略的原因，无法获得足够的资源来完成其任务，尽管这些资源是可用的。长时间下来，这些进程无法取得进展，就像人长时间不吃东西会饿一样。（可能只有一个进程会发生饥饿）

通俗易懂的解释：
想象排队买冰淇淋的小朋友队伍，但是每次轮到比较高大的孩子时，他们不仅给自己买，还帮后面的朋友买，导致队伍前面的小朋友总也轮不到。那些个小一点、不够强壮的孩子就一直排在后面，可能到冰淇淋卖完都还没轮到。这些小朋友就像是“饥饿”的进程，一直得不到他们需要的资源（冰淇淋）。

1.1.3 死循环（Infinite Loop）

教科书解释：
死循环是一种编程错误，指的是程序中的一个循环结构设计不当，导致循环条件始终满足，使得程序无法自行跳出循环，一直在循环体内执行，无法继续执行后续的代码。

注意：死锁和饥饿是操作系统的问题，死循环是被管理者的问题

1.2 死锁产生的条件

互斥条件：临界资源是独占资源，只能在同一时间被同一进程独占，不能同时被多个进程共享。

想象你和朋友去图书馆借书，一本书一次只能借给一个人，不能两个人同时看同一本。

占有和等待条件：已经持有一个资源的进程可以继续请求别的资源，等待过程中不释放已有资源。

就像一些小朋友各自拿着自己的玩具，同时又想玩别人手里的玩具，他们不愿意放下手中的玩具，就在那里等待。

不剥夺条件：已获得的资源只能由进程自愿释放，不允许被其他进程剥夺。

你借到的书除非你看完了或者主动归还，管理员不能从你手上抢走给其他人，哪怕那个人急需这本书。

循环等待条件：每个进程都在等待链中等待下一个人的资源。

你等着A的书，A等着B的书，B等着C的书，而C正好等着你手里的书。这样形成了一个等待的圈，每个人都卡在那儿了。

注意：1. 死锁一定处于循环等待，循环等待不一定处于死锁
2. 对不可剥夺资源的不合理分配，可能导致死锁

二、预防死锁

破坏互斥条件：允许资源可以同时访问而非互斥使用，但在大多数情况下无法实现（写文件、键盘、磁带机……）

缺点：
①实现困难②设计复杂度增加

破坏占有和等待条件： 要求进程在启动前声明它将需要的所有资源，仅当系统能够满足所有这些资源请求时才分配资源，否则进程等待直到资源齐全。

缺点：
①资源利用率降低：进程可能因为一两个资源未到位就长时间等待，导致其他资源也被闲置。
②可能导致饥饿：长期等待某些资源的进程可能永远无法获取所有资源，从而饥饿。

破坏不剥夺条件：
法Ⅰ：占有资源进程若要申请新资源，必须主动释放已占用资源（剥夺式），若仍需要占用此资源，应当重新提出申请，从而破坏不剥夺条件，可能会造成进程重复地申请和释放资源。

法Ⅱ：当操作系统为某个新进程分配资源时，如果有则分配，如果没有，则将剥夺占有此资源进程的全部资源，让该进程进入等待状态。（需要考虑进程的优先级）

缺点：
①实现较复杂
②释放已有的资源可能导致前一段工作失效
③反复申请释放资源增加系统开销

破坏循环等待条件：
采用层次分配策略：

1. 资源排序与分类
   首先，对系统中的所有资源进行分类和排序，给予每个类型的资源一个唯一的标识符或编号。这个编号不一定反映资源的实际价值或重要性，而是为了确保在请求资源时有一个固定的顺序。比如，可以将资源标记为R1、R2、R3…等，按照某种逻辑（比如资源的使用频率、重要性等）排序。

2. 进程请求资源遵循顺序
   接下来，要求每个进程在请求资源时，必须按照资源的编号顺序进行。也就是说，一个进程在已经持有R1资源的情况下，只能请求R2或编号更高的资源，而不能反向请求R0或更低编号的资源。这样做的目的是，确保进程间不会因为资源请求的交叉而导致循环等待的链条形成。

3. 预防循环的检查机制
   在进程请求资源时，系统需要有一个检查机制，验证此次请求是否符合上述的顺序规则。如果进程试图违反顺序请求资源（比如持有R3却请求R2），请求会被拒绝，直到进程释放其持有的资源并按照正确的顺序重新发起请求。

4. 资源分配策略
   在资源分配时，系统还需要确保资源是按照编号顺序逐步分配给进程的。一旦进程获得了某个编号的资源，它只能继续申请编号更高的资源，这在逻辑上断绝了形成闭环的可能性。

举例说明：
假设我们有三个资源类型：打印机（R1）、扫描仪（R2）、复印机（R3），并且已经按照某种逻辑进行了排序。

1.进程A首先请求并获得了打印机（R1）。

2.接着，A想要使用扫描仪（R2），此时因为它已经拥有比R2编号低的资源，所以可以顺利获取。

3.假设此时进程B正在等待打印机（R1），它不能直接跳过去请求扫描仪（R2），因为这将违反顺序原则，必须等待A释放R1。

4.这样，即使有多个进程同时运行，也不会形成如A等待B的扫描仪，B等待A的打印机这样的循环等待情况。

m个资源被n个进程共享，每个进程都要求K个资源 m > n x (k-1）一定不会发生死锁

三、避免死锁

银行家算法

四、死锁的检测和解除

4.1 资源分配图和死锁定理

资源类用方框（口）
此资源类中的各种资源用黑圈点（●）
进程用圆圈（⚪）
有向边表示进程申请和分配资源

死锁定理：如果一个系统的进程-资源分配图（进程与资源之间的关系图）是不可完全简化的，那么该系统中存在死锁

4.2 死锁的检测和恢复

资源剥夺法、进程回退法、进程撤销法、系统重启法

1. 结束所有进程的执行并重启操作系统。（损失很大）
2. 撤销陷于死锁的进程，解除死锁，继续运行
3. 逐个撤销陷于死锁的进程，回收其资源并重新分派，直至死锁解除
4. 剥夺陷于死锁的进程所占用的资源，并不撤销此进程，直至死锁解除（可能导致饥饿）
5. 根据系统保存检查点让所有进程回退，直至死锁解除

---

欢迎添加我的微信公众号：Q1Hang的AI学习小屋，分享AIGC学习笔记与文章