死锁

死锁是指多个并发进程因为竞争资源而互相等待，导致这些进程都被阻塞、都无法继续向前推进的现象。

典型结构是：

如果没有外力干预，两个进程都不会主动离开阻塞状态。

从 Dining-Philosophers-Problem 可以看到同样的结构：每个哲学家都持有一支筷子，又等待另一支筷子，等待关系首尾相接。

死锁、饥饿、死循环

现象	共同点	区别
死锁	都会使进程无法顺利推进	至少两个进程互相等待对方资源；死锁进程一定处于阻塞态
饥饿	都会使进程无法顺利推进	某进程长期得不到资源；可能只有一个进程饥饿；饥饿进程可能是阻塞态，也可能是就绪态
死循环	都会使进程无法顺利推进	进程一直运行但跳不出循环；通常是程序逻辑问题，进程可以处于运行态

死锁和饥饿通常来自资源分配或调度策略；死循环通常来自程序自身逻辑。

死锁产生有四个必要条件：互斥、不可剥夺、请求并保持、循环等待。

900

死锁一旦产生，必须同时满足四个条件。换句话说，只要破坏其中任意一个条件，死锁就不会发生。这也就是死锁预防的思路。

这四个条件只是**必要**条件而不**充分**，即同时满足四个条件不一定会导致死锁。

## 互斥

只有必须互斥使用的资源竞争才可能导致死锁。

打印机、筷子、互斥锁这类资源同一时刻只能被一个进程使用，进程得不到它们时会阻塞等待。内存中的只读数据、扬声器这类可共享资源不会因为同时使用本身导致死锁。

进程已经获得的资源，在未使用完之前不能被其他进程或系统强行夺走，只能由持有进程主动释放。

CPU 是可剥夺资源，调度器可以中断当前进程并把 CPU 分给其他进程。打印机正在打印时通常不能随便剥夺，否则输出结果会被破坏。

进程已经持有至少一个资源，同时又请求新的资源；如果新资源暂时得不到满足，进程阻塞，但仍保持已经持有的资源。

这会把资源“扣住”。其他进程可能正好需要它扣住的资源，于是等待链条变长。

存在一个进程-资源等待环。环中每个进程已经获得的资源，正被下一个进程请求。

例如：

1
2
3

P1 持有 R1，等待 R2
P2 持有 R2，等待 R3
P3 持有 R3，等待 R1

这就是循环等待。

900

发生死锁时一定存在循环等待，但存在循环等待不一定已经死锁。

关键在于资源实例数：

因此不能只看到“有环”就机械判断死锁。要进一步看资源实例数、可用资源数，以及资源分配图是否可以完全化简。

死锁常见于三类情况。

对不可剥夺资源的竞争。

打印机、磁带机、互斥锁等资源一旦被占有，通常不能强行剥夺。多个进程争抢这类资源时更容易出问题。
进程推进顺序非法。

两个进程按相反顺序申请资源，例如 P1 先申请 R1 再申请 R2，P2 先申请 R2 再申请 R1，就可能互相等待。
信号量使用不当。

在生产者-消费者问题中，若把互斥 P 操作放在同步 P 操作之前，进程可能带着互斥锁阻塞，导致另一类进程也无法进入临界区改变条件。

本质上，死锁来自不可剥夺资源的不合理分配。即，进程是否已经持有一部分资源，又在等待其他进程持有的资源。