并发：死锁和饥饿
死锁原理
死锁定义为一组相互竞争系统资源或进行通信的进程间的“永久”阻塞。当一组进程中的每个进程都在等待某个事件（资源），而仅有这组进程中被阻塞的其他进程才可触发该事件时，称这组进程发生了死锁
- 无通用有效解决方案
- 冲突需要两个及以上的资源
资源可分为：可重用资源和可消耗资源
可重用资源
- 一次仅供一个进程安全使用且不因使用而耗尽的资源
- 释放资源后其他进程可用
- 包括：处理器、I/O通道、内存和外存、设备、数据结构（文件、数据库、信号量）
进程死锁：
内存请求死锁：可用的分配空间为200KB
可消耗资源
- 可被创建（生产）和销毁（消耗）的资源
- 包括：中断、信号、消息、I/O缓冲区中的信息
- 很少的事件组合也可能导致死锁
接收发生死锁：
资源分配图（resource allocation graph）
从进程指向资源的边表示请求资源但还未得到授权；从可重用资源的圆点到一个进程的边表示请求已被授权（占有），从可消耗资源的点到一个进程的边表示进程是资源生产者
（d）无死锁：每个资源有多个实例
死锁的条件
三个必要条件
- 互斥：一次一个进程可以使用资源
- 占有且等待：一个进程等待其他资源同时占有已分配的资源
- 非抢占：不能抢占进程已占有的资源
一个充分条件
- 循环等待：存在闭合的进程链，每个进程至少占有此链中下一个进程所需的一个资源
处理死锁的方法：预防、避免、检测
死锁预防
互斥：操作系统必须支持
占有且等待：一次性请求所有资源，并阻塞这个进程直到所有请求都同时满足
（低效：一个进程可能被阻塞很长时间、分配给进程的资源可能很长时间不会被该进程使用；一个进程可能不知道它需要的所有资源）
不可抢占：
- 被拒绝后释放占有的资源，之后再请求资源
- 被高优先级进程抢占
循环等待：定义资源类型的线性顺序来预防，但低效
死锁避免
死锁预防：可以通过防止三个必要条件中的一个或防止充分条件循环等待实现避免死锁
死锁避免：允许三个必要条件，但明智选择以确保永远不会到达死锁点
法一：进程启动拒绝（Process Initiation Denial）
如果一个进程的请求会导致死锁，则不启动此进程，进程启动拒绝
成立的关系
$$ \begin{align*} & R_{j} = V_{j} + \sum_{i=1}^N A_{ij}\ :\ 所有资源要么可用，要么已被分配\\ & C_{ij}\le R_{i}\ :\ 任何一个进程对任何一种资源的请求都不能超过系统中该资源的总量\\ & A_{ij}\le C_{ij}\ :\ 分配给任何一个进程的任何一种资源都不会超过这个进程最初生命的此资源的最大请求量 \end{align*} $$
定义一个死锁避免策略：若一个新进程的资源需求会导致死锁，则拒绝启动这个新进程，即$R_{j}\ge C_{(n+1)j}+\sum_{i=1}^nC_{ij}$时才启动新进程$P_{n+1}$
eg：无法启动P3进程
$$ \begin{align*} & R=[10,10,9]\\ & Claim=\begin{bmatrix}a & b\\c & d\end{bmatrix}\\ & P_{3}=[2,3,1]（添加的新进程所需资源数）\\ & R_{1}=10>(1+3+2=6)满足\\ & R_{2}=10<(5+4+3=12)不满足\\ & R_{3}=9<(5+4+1=10)不满足 \end{align*} $$
法二：资源分配拒绝（Resource Allocation Denial）
又称银行家算法，系统状态是当前给进程分配的资源情况
- 安全状态：至少有一个资源分配序列不会导致死锁（所有进程都能运行到结束）
- 不安全状态
四个进程三个资源：满足$C_{ij}-A_{ij}\le V_{j}$
通过把一个R3单元分配给进程P2，P2拥有了所需最大资源，从而可以运行到结束，此后资源回到可用资源池
接下来选择P1运行
接下来选择P3运行
最后完成P4，因此（a）中定义的状态是安全的
从开始的（a）出发，P1请求另外一个R1和R3单元，若同意则到下图，此时没有可用的R1单元，P1的请求被拒绝并且它被阻塞
死锁避免逻辑
死锁避免优点：无需死锁预防中的抢占和回滚进程，且与死锁预防相比限制较少
限制：
- 必须事先声明每个进程请求的最大资源
- 所讨论的进程必须无关，执行顺序无同步要求的限制
- 分配资源数目必须固定
- 占有资源时不能退出
死锁检测
死锁预防：策略保守、通过限制访问资源和在进程上加强约束来解决死锁问题
死锁检测：不限制资源访问或约束进程行为，只要有可能就会给进程分配其所请求的资源
方法：
- 退出死锁进程
- 回滚某个检查点，重启（风险：原始死锁再次发生）
- 连续退出进程（基于最小代价原则）
- 连续抢占资源
选择死锁进程原则
- 目前为止消耗的处理器时间最少
- 目前为止产生的输出最少
- 预计剩下的时间最长
- 目前为止分配的资源总量最少
- 优先级最低
一种综合死锁策略
解决死锁在不同情况下使用不同策略
- 资源分类为不同的资源类
- 资源之间采用线性排序
- 资源类中使用最适合的算法
可以分为如下几类及相应的策略：
- 可交换空间：一次请求所有需要的资源
- 进程资源：死锁避免、资源排序
- 内存：抢占
- 内部资源：资源排序
哲学家就餐问题
<div align=center>
<img src="http://xherlock.top/usr/uploads/2022/04/1223743964.png" style='width:300px;height:300px;'>
<div>
一位哲学家相当于一个进程，1根筷子相当于一个临界资源；哲学家要想进餐必须同时获得左右两边的筷子，即同时获得两个临界资源
首先肯定不允许死锁：可以从静态和动态两种方向思考
静态：
- 互斥：可以增加一根筷子或者吃饭时共享筷子不符合）
- 保持占有：要拿就拿两根
- 抢占：不符合哲学家身份
- 设定资源访问顺序
动态：（银行家算法）
每次拿起筷子时进行判断，是否会造成死锁，若会出现死锁就不拿筷子
方案错误：五位哲学家同时拿起左边的筷子后，想要拿起右边的筷子发生死锁
方案：至多允许4位哲学家拿起左边的筷子，此时由鸽笼原理，必有一位哲学家能够拿起一双筷子
方案：一次拿起两根筷子
方案：设定资源的访问顺序
