第六章并发：死锁与饥饿

一、死锁

定义：一组相互竞争系统资源或进行通信的进程由于某种原因处于“永久”阻塞状态，不可解的循环等待。
一组进程中，每个进程都无限等待被该组进程中另一进程所占有的资源，因而永远无法得到的资源，这种现象称为进程死锁，这一组进程就称为死锁进程。

这里写图片描述

资源的使用方式：
“申请–分配–使用–释放”模式

可重用资源：可被多个进程多次使用
可抢占资源与不可抢占资源
处理器、I/O部件、内存、文件、数据库、信号量

可消耗资源：只可使用一次、可创建和销毁的资源
信号、中断、消息

活锁 :
 先加锁
 再轮询 → 既无进展也没有阻塞(处于忙等待）

饥饿：资源分配策略决定，使用进程得不到资源

死锁存在的三个必要条件：
1、互斥：一次只有一个进程可以使用一个资源
2、占有且等待：当一个进程等待其他资源时，继续占有已经分配的资源
3、不可抢占：不能强行抢占进程已占有的资源
这三个条件都只是死锁存在的必要条件，但不是充分条件。对死锁的产生，还需要第四个条件：
4、循环等待：存在一个封闭的进程链，使得每个进程至少占有此链中下一个进程所需要的一个资源。

资源分配图：

资源类：用方框表示
资源实例：用方框中的黑圆点表示
进程：用圆圈中加进程名表示

分配边：
资源实例 ->进程
申请边：
进程 -> 资源类

死锁定理：
如果资源分配图中没有环路，则系统中没有死锁，如果图中存在环路则系统中可能存在死锁
如果每个资源类中只包含一个资源实例，则环路是死锁存在的充分必要条件

资源分配图化简步骤
1）找一个非孤立、且只有分配边的进程结点去掉分配边，将其变为孤立结点
2）再把相应的资源分配给一个等待该资源的进程即将该进程的申请边变为分配边
重复1）、2）

四种方法处理死锁：鸵鸟算法（不考虑此问题）、死锁预防、死锁避免、死锁检测

二、死锁预防：

试图设计一种系统来排除发生死锁的可能性，设计合适的资源分配算法，不让死锁发生。分成两类：一种是间接死锁预防方法，即防止前面列出的三个必要条件（互斥、占有且等待、非抢占）中任何一个的发生；一种是直接死锁预防方法，防止循环等待的发生。

破坏“占有且等待”条件：
实现方案1：要求每个进程在运行前必须一次性申请它所要求的所有资源，且仅当该进程所要资源均可满足时才给予一次性分配
问题：资源利用率低；“饥饿”现象
实现方案2：在允许进程动态申请资源前提下规定，一个进程在申请新的资源不能立即得到满足而变为等待状态之前，必须释放已占有的全部资源，若需要再重新申请

资源有序分配法防止循环等待：给每种资源类型指定一个下标，当i小于j时，资源Ri排在Rj前面，在进行资源分配是先分配下标小的资源再分配下标大的资源。假设两个进程PA与PB死锁，原因是A获得Ri并请求Rj，而B获得Rj并请求Ri，则这个条件是不可能的，因为这意味着i小于j且j小于i。

三、死锁避免：

是否允许当前的资源分配请求是通过判断该请求是否可能导致死锁来决定的，因此死锁避免要知道将来的进程资源请求的情况。
（1）如果一个进程的请求会导致死锁，则不启动进程
（2）如果一个进程增加的资源请求会导致死锁，则不允许此分配请求

安全状态：如果系统中存在一个由所有进程构成的安全序列P1，…，Pn，则称系统处于安全状态
安全序列：一个进程序列{P1，…，Pn}是安全的，如果对于每一个进程Pi(1≤i≤n）：它以后还需要的资源量不超过系统当前剩余资源量与所有进程Pj (j < i )当前占有资源量之和，则称系统处于安全状态

银行家算法（资源分配拒绝策略）

应用条件：
1. 在固定数量的进程中共享数量固定的资源
2. 每个进程预先指定完成工作所需的最大资源数量
3. 进程不能申请比系统中可用资源总数还多的资源
4. 进程等待资源的时间是有限的
5. 如果系统满足了进程对资源的最大需求，那么，进程应该在有限的时间内使用资源，然后归还给系统

n：系统中进程数量 
m：资源类数量 
Available: ARRAY[1..m] of integer; 
Max: ARRAY[1..n,1..m] of integer; 
Allocation: ARRAY[1..n,1..m] of integer; 
Need: ARRAY[1..n,1..m] of integer; 
Request: ARRAY[1..n,1..m] of integer;

当进程Pi提出资源申请时，系统执行下列步骤：
（1）若Request[i] ≤ Need[i]，转（2）；否则，报错返回；
（2）若Request[i] ≤ Available，转（3）；否则，进程等待；
（3）假设系统分配了资源，则有：
Available = Available - Request[i];
Allocation[i] = Allocation[i] + Request[i];
Need[i] = Need[i] - Request[i];
若系统新状态是安全的，则分配完成；若系统新状态是不安全的，则恢复原来状态，进程等待

为进行安全性检查，定义数据结构：
Work: ARRAY[1..m] of integer;
Finish: ARRAY[1..n] of Boolean;
安全性检查的步骤：
1) Work = Available; Finish = false;
2) 寻找满足条件的i：
a. Finish[i]==false;
b. Need[i]≤Work;
如果不存在，则转(4)
(3) Work = Work + Allocation[i]; Finish[i] = true; 转(2)
(4) 若对所有i，Finish[i]==true，则系统处于安全状态，否则系统处于不安全状态

安全状态：指至少有一个资源分配序列不会导致死锁。
不安全状态：相反，所有的资源分配序列都会导致死锁

四、死锁检测

死锁检测：
允许死锁发生，但是操作系统会不断监视系统进展情况，判断死锁是否真的发生
 一旦死锁发生则采取专门的措施，解除死锁并以最小的代价恢复操作系统运行
检测时机：
 当进程由于资源请求不满足而等待时检测死锁缺点：系统开销大
 定时检测
 系统资源利用率下降时检测死锁

死锁解除：
方法如下：
撤消所有死锁进程
进程回退（Roll back）再启动
按照某种原则逐一撤消死锁进程，直到…
按照某种原则逐一抢占资源（资源被抢占的进程必须回退到之前的对应状态），直到…

哲学家就餐问题：
解决方法：
（1）最多允许4个哲学家同时坐在桌子周围

semaphore fork[5] = {1}; 
semaphore room = {4}; 
int i; 
void philosopher (int i) 
{ 
    while (true) { 
      think(); 
      P (room); 
      P (fork[i]); 
      P (fork [(i+1) mod 5]); 
      eat(); 
      V (fork [(i+1) mod 5]); 
      V (fork[i]); 
      V (room); 
    } 
} 
void main() 
{ 
     parbegin ( philosopher (0), philosopher (1),philosopher (2), 
     philosopher(3),philosopher (4) ); 
}

（2）仅当一个哲学家左右两边的筷子都可用时，才允许他拿筷子（管程）

#define  N  5 
#define  THINKING  0 
#define  HUNGRY    1 
#define  EATING    2 
#typedef  int semaphore; 
int state[N]; 
semaphore mutex=1; 
semaphore s[N]; 
//为了避免死锁，把哲学家分为三种状态，思考，饥饿，进食，并且一次拿到两只筷子，否则不拿
void  philosopher (int i)  
{   while (true)   
     { 
      思考; 
       P(&mutex); 
       state[i] = HUNGRY; 
       test(i); 
       V(&mutex); 
       P(&s[i]); 
       拿左筷子； 
       拿右筷子； 
       进食； 
       放左筷子； 
        放右筷子； 
        P(&mutex) 
        state[ i ] = THINKING； 
        test([i-1] % 5); 
        test([i+1] % 5); 
        V(&mutex); 
    } 
} 
state[ i ] = THINKING; 
s[ i ] = 0;

void test(int i) 
{ 
      if (state[ i ] == HUNGRY)  
          && (state [(i-1) % 5] != EATING)  
          && (state [(i+1) % 5] != EATING) 
          { 
               state[ i ] = EATING; 
               V(&s[ i ]); 
           } 
 }

（3）给所有哲学家编号，奇数号的哲学家必须首先拿左边的筷子，偶数号的哲学家则反之

第六章 并发：死锁与饥饿

第六章并发：死锁与饥饿