操作系统 | 银行家算法举例

数据结构:

长度为m的一维数组Available表示还有多少可用资源n*m矩阵Max表示各进程对资源的最大需求数

n*m矩阵Allocation表示已经给各进程分配了多少资源

Max - Allocation = Need矩阵表示各进程最多还需要多少资源用长度为m的一位数组

Request表示进程此次申请的各种资源数

银行家算法步骤:

• ①检查此次申请是否超过了之前声明的最大需求数
• ②检查此时系统剩余的可用资源是否还能满足这次请求
• ③试探着分配，更改各数据结构
• ④用安全性算法检查此次分配是否会导致系统进入不安全状态

安全性算法步骤:

检查当前的剩余可用资源是否能满足某个进程的最大需求，如果可以，就把该进程加入安全序列，并把该进程持有的资源全部回收。

不断重复上述过程，看最终是否能让所有进程都加入安全序列。

举例说明：“若系统状态目前是安全的，若对某个申请评估时 在假定分配状态中，只要找到一个可满足线程就可断定系统是安全的”结论是错的。请构造一个例子进行证明。

例：在银行家算法中，若出现下述分配情况，试问：

若进程P2提出请求Request（1，2，2，2）后，系统能否将资源分配给它？

答：不能，按照银行家算法，首先检查Requesti [j] 是否小于等于 Need[i,j]，在这里（1，2，2，2） < （2，3，5，6）满足条件，则再判断Requesti [j] 是否小于等于 Available[j]，这里（1，2，2，2） <（1，6，2，2）满足！此时找到了一个可满足进程。

然后便试探性的将资源分配给P2，此时P2的Allocation项变为（2，5，7，6），Need项变为（1，1，3，4），Available项变为（0，4，0，0）必须执行安全性算法，第一步就发现找不到一个进程使得Need[i,j] <= Work[j]；所以安全性检查失败，这个Request请求会造成死锁，系统将处于不安全状态，故本次试探分配作废，恢复原来的资源分配状态，让进程P2等待。故“只要找到一个可满足线程就可断定系统是安全的”是错误的。

笔记：

1.多个进程： { P0，P1，P2，P4 } 代表1，2，3，4四个需要临界资源的进程

2.几种资源：{ A, B ,C } 代表A，B，C三种临界资源

3.Claim：最大需求矩阵（进程完成执行需要的各资源总量）

Allocation：分配矩阵（某个进程现在已经拥有的各资源量）

Need：需求矩阵（某个进程仍需要的各资源量）

Available：可利用资源向量 （系统保有的供分配的资源量）

其中：Need = Max - Allocation ，仍然需要的量等于总需求量减去拥有的量

当进程请求一组资源时，假设同意该请求，从而改变了系统的状态，然后确定其结果是否还处于安全状态。如果是，同意这个请求；如果不是，阻塞该进程知道同意该请求后系统状态仍然是安全的。