操作系统-4——并发：死锁和饥饿
一、死锁
1、死锁原理
- 当一组进程中的每个进程都在等待某个事件（所请求的资源被释放），而只有在这组进程中的其他阻塞进程才能触发该事件，而只有这组进程中的其他阻塞进程才能触发该事件，称这组进程发生死锁。
- 死锁涉及两个或多个进程之间的资源需求冲突。
- 死锁原因：竞争资源，进程推进顺序不当。
2、资源
- 资源分为两类：可重用资源和可消耗资源。
- 可重用资源：指可重复使用，互斥使用的资源。如CPU，虚拟内存，磁盘等。【打印机，磁带机，文件，数据库，信号量等】（属于不可剥夺资源：如果被剥夺，会引起进程失败。）
- 竞争不可剥夺资源可能导致死锁。
？#为什么死锁不会涉及虚拟内存或磁盘？
2.2 可消耗资源
- 可消耗资源：可被创建（生产）和销毁（消费）的资源。如消息、信号、缓冲数据等。
- 竞争可消耗资源也可能导致死锁。
2.3 资源分配图
有向图，描述资源和进程状态。
- 进程节点：P
- 资源节点：R。 一个圆点表示一个资源实例。
- 请求边：进程->资源。 Pi -> Rj
- 分配边： 资源 ->进程。 Rj -> Pi
- 若死锁、则资源分配图中必有环。
- 但有环路时并不一定死锁，要看是否进程都阻塞而无法运行。
3、死锁的条件
- 互斥：涉及的是需要互斥访问的临界资源。
- 占有并等待：进程申请资源而阻塞（等待）时，不释放（继续占有）已分配资源。
- 不可抢占：进程已占有的资源未使用完前不可强行剥夺（抢占），只能有进程资源释放。
- 循环等待：进程间形成一个等待资源的循环链。
死锁时，以上四个必要条件同时成立。某一个或几个必要条件成立时并未进入死锁状态。
3.1 死锁的三个处理方法
- 死锁预防：破坏四个必要条件之一。
- 死锁避免：不破坏必要条件，允许进程动态申请资源，但检查资源分配状态，以避免可能导致的死锁。
- 死锁检查和恢复：检查系统是否已死锁、那些进程和资源涉及死锁，并撤销死锁进程或剥夺资源以摆脱死锁。
4、死锁预防
破坏四个必要条件的其中一个。
4.1 破坏互斥
互斥条件不可破坏。因为一旦互斥条件破坏，就不存在多道程序设计了。
4.2 破坏占有且等待
①资源静态分配法：程序运行前，一次性分配所有需要的资源。若有某个资源不能满足，则全部不分配。进程等待直至所有资源可用。
- 可能会引起进程饥饿；资源利用率低。
- 进程可能事先不知道所需要的资源列表。
4.3 破坏不可抢占
- 进程申请新资源被阻塞时，必须（主动）释放已占有的资源。本进程需要时再重新申请。
- OS剥夺低优先级进程的资源给高优先级进程。
4.4 破坏循环等待
①资源有序分配法：系统内每个资源一个编号，各进程必须严格按照编号递增的顺序申请资源。
！#死锁≠死机
5、死锁避免
系统运行进程动态申请资源。在分配资源之前，先计算资源分配的安全性。若此次分配可能导致死锁，则暂不分配，该进程等待。
两种死锁避免方法：
①进程启动拒绝：如果一个新进程的资源最大需求总量会导致死锁，则不启动此新进程。
②资源分配拒绝：如果一个进程提出的某次资源请求会导致死锁，则不允许此次分配。（更常用）
5.1 进程启动拒绝
定义以下向量和矩阵：n——进程数；m——资源类型数
- 资源总量Resource = R = (R1,R2,...,Rm)
- 可用资源Available = V = （V1,V2,...,Vm）
- 最大需求矩阵Claim = C = ：n*m 的矩阵 ——C[i,j] = k 表示进程 i 需要第 j 类资源最多为k个。
- 已分配矩阵Allocation = A = n*m的矩阵 ——A[i,j] = k 表示进程 i 已分得第 j 类资源 k 个。
当系统的资源总量能够满足“所有进程的最大需求量加上新进程Pn+1的最大需求量”时，才能启动新进程Pn+1。
（即所有进程申请的资源最大需求量之和不能大于系统的资源总量。）
？#进程启动拒绝和资源静态分配有什么区别？？？
5.2 资源分配拒绝
- 银行家算法：分配资源前，先计算此次分配是否会导致系统处于不安全状态。若安全则分配，否则不分配（事先评估）。
- 安全状态：存在一个由所有进程（P1,P2,...,Pn）构成的安全序列，如果系统安装这个顺序为每个进程分配所需资源，直至该进程声明的最大资源需求量，则可以使每个进程都运行完。
- 不安全状态：系统不存在任何一个安全序列，使得所有进程都能够运行完。
！#不安全状态≠死锁状态
进程提出资源分配请求后，OS先试探性分配，若仍处于“安全状态”才分配，否则暂不分配，进程等待。
- 安全性测试算法（银行家算法）
boolean safe(state S){
int currentavail[m];//系统可用资源数目（临时记录，非真实）
process rest[进程总数];//剩余的，未运行完毕的进程集合
currentavail = available;//开始时，currentavail = 实际的可用资源
rest = {所有进场};//开始时，所有进程都尚未运行完毕
possible = true;
while(possible){
<在rest中（循环）查找一个进程Pk,满足claim[k,*]-alloc[k,*]<= currentavail;>
//其资源需求可被满足
if(found){//如果有这样的进程Pk，则认为它能够运行完毕
currentavail = currentavail+alloc[k,*];//并释放其已分配的资源
rest=rest-{Pk};//从rest集合中去掉“已运行完的”进程Pk
}
else possible = false;//如果没有找到这样的进程Pk，则结束循环
}
return (rest == null);//若rest为空，则为安全状态，否则不安全
}6、死锁检测
只要所请求资源可用，则分配给进程。OS定期运行死锁检测算法，判断是否存在死锁。
死锁检测算法类似于银行家算法。
6.1恢复
解除死锁：代价最小地撤销进程、剥夺资源。
- 终止所有死锁进程。
- 每个死锁进程回滚到某个安全状态的“检查点”（周期性将内存映像、资源状态等写入文件），并重启进程。
- 每次终止一个死锁进程，知道死锁环解除。
- 每次剥夺一个资源，直至死锁环解除。
选择终止进程顺序和剥夺自愿的顺序
- 进程已运行时间最少，预计剩余运行时间最长。
- 进程已产生的输出最少，已用资源总量最少。
- 进程的优先级最低，进程是交互式的还是批处理的。
- 防止饥饿：避免总是选择同一个牺牲者（考虑其回滚的次数）。
？#某系系统中仅有5个并发进程竞争某类资源，且都需要3个该类资源，那么至少有 11 个该类资源，才能保证系统不会发生死锁。
7、哲学家就餐问题
基于信号量解决方案：
- 至多允许4个哲学家同时拿起叉子
semaphore fork[5] = 1;
semaphore room = 4;//至多允许四人同时拿起叉子
void phiosopher(int i){
while(true){
think();
wait(room);
wait(fork[i]);
wait(fork[(i+1) mod 5]);
eat();
signal(fork[i]);
signal(fork[fork(i+1) mod 5]);
signal(room);
}
}- 奇数号人先拿左叉，偶数号人先拿右叉。
semaphore fork[5] = 1;
void phiosopher(int i){
while(true){
think();
if(i % 2 == 1){
wait(fork[i]);
wait(fork[(i+1) mod 5]);
}
else{
wait(fork[(i+1) mod 5]);
wait(fork[i]);
}
eat();
signal(fork[fork(i+1) mod 5]);
signal(fork[i]);
}
}