死锁基本概念

定义：多个进程由于竞争资源而造成阻塞现象，若无外力作用，这些进程将无法继续前进
相似概念：饥饿：等待时间过长以至于给进程推进和响应带来明显影响，但”饿而不死”
死锁产生原因：1.系统资源的竞争 2. 推进顺序非法
产生的必要条件：

互斥条件：共享资源排他性访问
不剥夺条件：访问时该共享资源不会被剥夺
请求并保持条件：保持当前资源时请求另一资源
循环等待条件：存在共享资源的循环等待链

死锁的预防

1.破坏互斥条件：
- 将只能互斥访问的资源改为同时共享访问
- 将独占锁改为共享锁
- 不是所有资源都能改成共享的

2.破坏剥夺条件：
- 请求新资源无法满足时必须释放已有资源
- 由os协助强制剥夺某进程的资源
- 实现复杂代价高，此操作过多可能导致原进程无法推进

3.破坏请求等待条件：
- 3.1 进程开始时一次性申请所需要的所有资源：资源浪费，进程饥饿
- 3.2 阶段性请求和释放资源：

4.破坏循环等等：
- 对所有资源进行排序，按序号请求资源，请求时先低后高，释放时先高后低
- 对资源的编号相对稳定，限制了新设备增加
- 进程使用资源的顺序可能与系统编号的顺序不同,限制了用户编程

核心：安全性算法
系统安全状态：

安全状态不一定会出现死锁
不安全状态可能会出现死锁

银行家算法：

系统预判进程是否导致不安全状态
是则拒绝请求，否则答应请求

1.需要一种数据结构，保存相关资源请求和分配信息-资源分配图(G=(N,E))
2.需要一种算法，利用这些信息检测是否形成死锁-死锁定理（死锁状态充分条件)

资源分配图：

两种资源
两种节点

死锁定理：

当且仅当此状态下资源分配图是不可完全简化的
简化的过程类似于拓扑排序算法

1.资源剥夺

挂起死锁进程
剥夺其资源
将资源分配给其他（死锁）进程

2.撤销进程
3.进程回退

回退到避免死锁的地点
需要记录进程历史信息，设置回退点