操作系统——死锁（学习笔记）

死锁产生的四个必要条件
死锁是因为多个进程争夺资源而导致无限的循环等待的一个现象，出现主要是因为系统资源不足，或者是程序的运行顺序不对。

**互斥条件：**某个资源只允许同时有一个资源访问。
占有且等待： 一个进程已经占有资源，又申请资源但未被满足，不放弃资源且进行等待。
不可抢占： 在别的程序已经占有的情况下，你不能因为你需要这种资源就抢过来。
循环等待： 存在一个进程环路，每个进程都占有下一个进程所需的至少一个资源。
这四个条件是死锁产生的必要条件，只要其中有一个条件被破坏，死锁就无法产生，而解决死锁的方法，就从这个条件出发。

解决死锁的方法

鸵鸟算法

认为死锁产生只是一种低概率事件，或者说，认为系统中几乎不存在死锁，如果真的出现了会影响系统正常运行的死锁，就重启系统。

死锁预防

一种静态分配方式

破坏互斥条件： 改变资源特性，将独享资源变为共享，将互斥设备改为共享设备。（难度过高，费力不讨好）
破坏占有且等待条件： 为了防止出现占着资源又拿不到下一个资源的情况，在程序开始运行时就将所有需要的资源分配给程序，不能满足就等待。（资源利用率过低，有可能产生饥饿问题，但是简单）
破坏不可抢占条件： 当进程已经占有资源并且提出新资源的申请请求时，如果不能被满足，则释放所有的资源，待之后再重新申请，并不等待至进程运行结束后释放资源。（需要保存进程状态以及恢复“现场”，代价高昂）
破坏循环等待条件： 无序的随机申请可能会产生环路，所以将资源编号，只能按照递增/递减顺序申请资源。（需要计算程序需要的所有资源的编号，较难添加新资源）

死锁避免

一种动态的分配方式，允许系统占有一部分资源运行，但在系统申请资源时，先计算，如果进行分配，系统是否还是安全状态，如果是就分配，不是则相反。

安全状态

在安全状态中，系统中不会产生死锁，可以找到某一个安全序列（P1，P2，…,Pn）使系统正常的分配资源，并且使所有程序顺利结束；非安全状态下可能产生死锁。
安全序列的算法较为简单，在此不做赘述。

死锁检测

为了降低开销，一般选择隔一段时间进行一次检测而不是每次分配都进行检测。检测的目的是为了确认系统的资源分配图中是否存在环路，如果有的话，则是存在死锁。
这种检测方法类似于图的遍历(图中的字母代表资源和进程)
操作系统——死锁（学习笔记）拿这个图(有向图)举例子，使用DFS（深度优先）进行遍历，假设从B开始，
B入栈，[B],
B连接T,T入栈,[B,T]，
T连接E,E入栈,[B,T,E]，
E连接V,V入栈,[B,T,E,V]，
V连接G,G入栈,[B,T,E,V,G]，
G连接U,U入栈,[B,T,E,V,G,U]，
U连接D,D入栈,[B,T,E,V,G,U,D]，
D连接T,T入栈,[B,T,E,V,G,U,D,T]，
栈内有两个T，所以存在环路。

另一种方法是简化资源分配图
1、如果资源只有射出箭头（即全部分配出去，没有未满足的，表示方法同上图），则擦去所有箭头。
2、如果进程只有射入箭头（即全部得到了，没有未申请到的，表示方法同上图），则擦去所有箭头。
3、如果进程有射出箭头，而且对于每个箭头指向的资源都有一个可用资源，则擦去相关箭头。
4、重复步骤，直到没有箭头可以擦，如果没有箭头，则不存在死锁。

死锁恢复

剥夺资源
剥夺一些进程的资源或者将进程滚回，代价不大，但可能让某些进程一直无法顺利执行，可能有饥饿问题。
撤销进程
最直接，直接撤销死锁相关进程，断开死锁。