死锁

这个概念是操作系统里面很重要的内容，前阵子面试字节被问到了，太久没复习，面经变凉经。

死锁（Deadlock），又被翻译为死结。是操作系统或软件运行的一种状态，在多任务系统下，当一个或多个进程等待系统资源、而资源又被进程本事或其他进程占用，就形成了死锁。现如今的操作系统都是多任务执行，只有可以协调好不同的进程，才可以让系统运行流畅不卡顿。

插入图片

起因

如果系统只有一个进程在运行，当然不会产生死锁，就像独生子女在家似的。不过这是理想状态，在现实中可遇不可求。

死锁的四个条件：

• 禁止抢占 (No preemption) ： 系统资源不能被强制从一个进程中退出
• 持有和等待 (Hold and wait) : 一个进程可以在等待时有系统资源
• 互斥 (Mutual exclusion) : 资源只能同时分配给一进程，无法多个进程共享，比如驱动器、打印机等
• 循环等待 (Circular waiting) ：一系列进程互相持有其他进程所需要的资源

死锁只有在四个条件（必要条件）同时发生，防止死锁发生只需要破坏其中一项。一般的，解决死锁的方法分为死锁的预防、避免、检测与恢复三种。

死锁的预防

死锁的预防是保证系统不进入死锁状态的一种策略。方法就是要求进程在创建时服从某种协议，从而打破产生死锁的四个必要条件。

1. 　打破禁止抢占条件：允许进程强行从占有者那里夺取资源。
2. 打破持有和等待条件：实行资源预先分配的策略。
3. 打破互斥条件：允许进程同时访问某些资源。但是某些资源（如打印机）不可以被同时访问，这是由于资源本身的属性所决定的，所以该方法价值不大
4. 打破循环等待条件：实行资源有序分配策略。即把资源事先分类编号，按号分配，这样不会因为资源分配形成环路

死锁的避免

该策略不限制进程有关申请资源的命令，而是对进程所发出的每一个申请资源命令加以动态检查，并根据检查结果决定是否进行资源分配。

该策略用到一个著名的避免死锁的算法--银行家算法，由Dijstra提出并加以解决的。具体分析这里不展开了，简要概括下该算法：银行家算法允许死锁必要条件重的互斥条件、占有且申请条件、不可抢占条件的存在，这样它与预防死锁的方法相比限制较少，资源利用程度高了。

算法的缺点如下：

1. 算法要求客户数保持不变，这在实际使用操作系统中很难实现。
2. 这个算法保证客户在有限时间内得到满足。但是实时客户要求快速响应，所以要考虑这个因素。
3. 寻找安全序列的过程中，实际上增加了系统开销。

检测与恢复

死锁检测：

if 每种资源类型只有一个实例：{

　　构建资源分配图，采用DFS确定是否由环路

} else if {

　　每种资源类型还有多个实例的情况：

　　构建向量矩阵

}

最简单的消除死锁的办法是重启～没有重启解决不了的事情，如果有，就重买台机器。

逃）

死锁恢复：

1. 抢占：不通知原进程的情况下，将某一资源从一个进程强行取走给另一个进程使用，然后将资源再送回。
2. 回滚：周期性对进程进行检查点检查，即将进程的状态写入一个文件以备以后重启，包括存储映像、资源状态。新的检查点不覆盖原有文件，而是写到新文件中。
3. 杀死进程：杀死环中的一个或多个进程；

附加：

如果一个进程被多次回滚，迟迟不能占用必须的系统资源，可能会导致资源匮乏 (resource starvation)。

Resource starvation is a problem encounterd in concurrent computing where a process is perpetually denied necessary resources to process its work. Starvation may be caused by errors in a scheduling or mutual exclusion algorithm. Also, it can be caused by resource leaks.

Then what is resorce leaks? Resource leaks are particular type of resource consumption by a computer program where the program does not release resources it has acquired. Also, resource leaks are particularly a problem for resources avaliable in very low quantities. Leaking a unique resource, such as a lock, is pretty serious, as this causes immediate resource starvation and cause deadlock.

活锁

活锁（livelock），与死锁相似，死锁是进程都在等待对方先释放资源，而活锁则是进程彼此释放资源后同时占用对方释放的资源。当此情况持续发生时，尽管资源的状态不断改变，但每个形成都无法获取所需资源，使得事情没有任何进展。