什么是死锁

典型：哲学家进餐问题
在并发环境下，各进程竞争资源而造成的一种互相等待对方手里的资源，导致各个进程都阻塞，都无法向前推进的现象，就是死锁。
如果没有操作系统干涉将会一直处于死锁状态，无法向前推进。

进程死锁、饥饿、死循环区别

相同点：都是进程无法顺利的向前推进的现象（故意设计的死循环除外）

区别

死锁：
死锁一定是“互相等待对方手里的资源”导致的，一次如果发生死锁现象，至少要两个及两个以上的进程循环等待才能死锁。另外，发生死锁的过程一定处于阻塞态。

饥饿：
发生饥饿是由于长期得不到想要的资源，某些进程无法向前推进导致的现象。可能只有一个进程饥饿。发生饥饿的进程既可能是阻塞态（如长期得不到处I/O设备）；也可能是就绪态（长期得不到处理机）。

死循环：
可能只有一个进程发生死循环。死循环是可以上处理机运行的。死锁和饥饿问题都是由操作系统分配资源不合理导致的。死循环是逻辑错误或故意为之。

死锁产生必要条件

  • 互斥条件：对必须互斥访问的资源的争抢才会导致死锁（打印设备）
  • 不可剥夺条件：进程所获得的资源没有使用完之前，不能由其他进程强行夺走，只能主动释放。
  • 循环等待条件：存在循环等待链，链上的每一个进程已获得的资源被下一个进程请求。
  • 请求和保持条件：进程已经获取了一项资源，但是又提出了其他请求，此时请求被阻塞，但又对自己的资源保持不放。

注意：
发生死锁的时候一定有循环等待，但是发生循环等待未必死锁。循环等待是死锁的必要不充分条件。
例如：同类资源数量大于1，即使有循环等待，也未必死锁。如果每一类资源只有一个，那循环等待就是自锁的充分必要条件了。

什么时候会发生死锁

  • 对系统资源的竞争。各进程对不可剥夺资源（IO设备）的竞争。对可剥夺资源的竞争是不会发生死锁的如（cpu）
  • 进程间推进顺序非法。请求和释放资源的顺序不当。例如，并发进程P1、P2分别分别申请了R1、R2，之后又分别申请R2、R1。
  • 信号量的使用不当也会发生死锁。例如：生产者-消费者问题，如果互斥的P操作在同步的P操作之前就有可能死锁。（可以把互斥信号量、同步信号量看做一种抽象得系统资源）

    死锁的处理策略

避免死锁：银行家算法
解除死锁：消进程法
预防死锁资源：静态分配法
检测死锁资源：分配图简化法

预防死锁

破坏死锁的四个必要条件中的一个或几个

破坏互斥条件：把互斥的资源改造成共享使用，则系统不会进入死锁状态。比如SPOOLing技术，把独占设备改造成共享设备。在使用之后，各个请求被处理，进程不需要阻塞等待。
缺点：但并不是所有的资源都可以使用这一项技术改造成共享资源

破坏不可剥夺条件：方式一：当某一个进程请求的资源得不到满足的时候，立即释放保持的所有条件，待以后需要的时候在申请。方式二：当进程需要的资源被其他进程所占有的时候，由操作系统协助把需要的资源剥夺（涉及优先级）。
缺点：复杂、反复申请释放资源增加开销，可能使以前的一些工作失效。因此这种方法只适用于易保存易恢复状态的资源。

破坏请求和保持条件：采用静态分配法，进程运行前一次性申请完它所需要的所有资源。
缺点：资源利用率低，可能会导致饥饿。

破坏循环等待条件：顺序资源分配法。给系统中的资源编号，规定进程按照递增的顺序请求资源。一个进程已经占有小编号资源才有资格申请大编号资源。
缺点：不方便新增资源，进程使用资源的顺序可能不是递增的。会导致资源浪费

避免死锁

用某种方法防止系统进入不安全状态，如银行家算法。

安全序列，指系统按照一个序列分配资源，每个进程都能顺利的完成。安全序列可以有很多个。

如果系统找不出任何一个安全序列，系统就进入了不安全状态。这就意味着之后可能所有的进程都无法继续进行下去。当然如果一些进程归还了一些资源，系统可能也有可能重新回到安全状态，不过我们要考虑最坏的情况。

处于安全状态，一定不会死锁；处于不安全状态，就可能发生死锁。因此在资源分配之前预先判断这次分配是否会导致系统进入不安全状态。**未雨绸缪，这也是银行家算法的核心思想

**
image.png

死锁的检测和解除

允许死锁发生，不过操作系统会检测死锁的发生，然后才去某种措施解决。

目前处理死锁的方法可以归纳为如下：
(1)不考虑此问题（鸵鸟算法）：把头埋在沙子里，假装根本没发生问题。因为解决死锁问题的代价很高，因此鸵鸟策略这种不采取任务措施的方案会获得更高的性能。当发生死锁时不会对用户造成多大影响，或发生死锁的概率很低，可以采用鸵鸟策略。大多数操作系统，包括 Unix，Linux 和 Windows，处理死锁问题的办法仅仅是忽略它。
(2)不让死锁发生，分为以下两种：

  • 死锁预防：不让死锁发生的静态策略，通过设计合适的资源分配算法，由资源分配策略保证不让死锁发生
  • 死锁避免：不让死锁发生的动态策略，以不让死锁发生为目标，跟踪并评估资源分配过程，根据评估结果决策是否分配

(3)让死锁发生
通过死锁的检测判断死锁是否真的发生，然后采用一些方法来解除死锁的问题。
总体解决锁死发生的方法可以分为四类：鸵鸟算法、死锁预防、死锁避免以及死锁检测与解除。