转载声明：文章来源https://zhuanlan.zhihu.com/p/367061930

先给大家回忆一下上周的讲的死锁避免涉及到的一些数据结构和算法。

数据结构

1. Available向量，它的含义是可利用的资源数。
2. Max矩阵，代表每个进程需要k个资源最多需要多少个。
3. 需求矩阵Need，代表每个进程接下来还需要多少个资源。
4. 分配矩阵Allocation，记录当前系统中每个进程已经获得的资源量。
5. Request(i)是代表进程i的请求向量，Request(i)[j]代表进程i需要j类资源的数目为k。

算法

银行家算法：
1. 如果Request(i)[j]<=Need[i][j],说明提出的要求是合理的，进行下一步，否则，视为出错。
2. 若Request(i)[j]<=Available[j],说明系统中还有相应的资源可以分配，则进行下一步，否则，出错。
3. 系统将资源分配给进程i，并对系统中的资源数据结构进行修改

Available=Available-Request(i)
Allocation[i][j]=Allocation[i][j]+Request(i)[j]
Need[i][j]=Need[i][j]-Request(i)[j]

4. 系统执行安全性算法，检查本次资源分配后，系统是否处于安全状态，若安全，才正式将资源分配给进程i。否则，此次分配无效。

安全性算法：
1. 设置两个向量：在执行安全算法开始时，Work∶=Available; Finish［i］:= False;
2. 从进程集合中找到一个能满足下述条件的进程：① Finish［i］= False; ② Need[i][j]≤Work[j]；
若找到， 执行步骤(3)， 否则，执行步骤(4)。
3. 当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：

Work[j]∶= Work[i]+ Allocation[i][j];
Finish［i］∶= true; go to step (2);

4. 如果所有进程的Finish[i]=true都满足， 则表示系统处于安全状态；否则，系统处于不安全状态。

题目一
某系统有R1，R2，R3共三种资源，在T0时刻P1，P2，P3和P4这四个进程对资源的占用和需求情况见下表，此时系统的可用资源向量为（2，1，2）。试问：
1）用向量或矩阵表示系统中各种资源的总数和此刻各进程对各资源的需求数目。
2）若此时进程P1和进程P2均发出资源请求向量Request(0,1,0)，为了保证系统的安全性，应如何分配资源给这两个进程？说明所采用策略的原因。

3）若2）中两个请求立即得到满足后，系统此刻是否处于死锁状态？

解析：
1）系统中当前资源总量为各进程已分配资源的总和，故系统中资源总量为：
(4,1,1)+(2,1,1)+(4,1,1)+(2,1,1)+(0,0,2)=(9,3,6)
各进程对资源的需求量为：
P1对资源的需求向量为(3,2,2)-(1,0,0)=(2,2,2)
P2对资源的需求向量为(6,1 3)-(4,1,1 )=(2,0,2)
P3对资源的需求向量为(3,1,4)-(2,1,1)=(1,0,3)
P4对需求的需求向量为(4,2,2)-(0,0,2)=(4,2,0)

2）若此时P1发出资源请求Request(1,0,1),此时按照银行家算法进行检查：

Work[j]∶= Work[i]+ Allocation[i][j];
Finish［i］∶= true; go to step (2);

尝试将资源进行分配，分配之后的资源分布表如下：

再利用安全性算法检查系统是否安全，可得到如下表所示的安全性检测情况。注意表中各个进程对应的Work+Allocation向量表示在该进程释放资源之后更新的Work向量。

从表中可用看到，此时存在一个安全序列{P2,P3,P4,P1},因此该状态是安全的，可以立即将进程P2所申请的资源分配给它。

3）若2）中的两个请求立即得到满足，这个时候系统没有立即进入死锁状态，因为这时，所有的进程未提出新的资源申请，全部进程均为因资源请求没有得到满足而进入阻塞态。只有当进程提出资源申请且全部进程都进入阻塞态时，系统才处于死锁状态。

题目二：

假设具有5个进程的进程集合P={P0，P1，P2，P3，P4}，系统中有三类资源A，B，C，假设在某时刻有如下状态：

请问当前系统是否处于安全状态？若系统中的可利用资源Avaliable为(0,6,2)系统是否安全？若系统处在安全状态，请给出安全序列；若系统处在非安全状态，简要说明原因。

解析：
1）首先看到此时的Avaliable为（1，4，0），可以满足进程P2的需求，当P2结束后释放资源，此时Avaliable为（2，7，5），此时可以满足P0，P1，P3，P4中任一进程的需求，所以系统不会出现死锁，当前处于安全状态。

2）若初始Work=Available为（0，6，2），可以满足P0，P3的需求，这两个进程结束后释放资源，Work为(0,6,7)，仅可以满足进程P4，的需求；P4结束后释放资源，Work为（0，6，8），此时不能满足余下任一进程的需求，系统出现死锁，因此当前系统处在非安全状态。