(操作系统)银行家算法.docx

(操作系统)银行家算法
D
则肯定不会陷入死锁。否则，一个时刻的安全状态是毫无意义的，而且可能从安全状态转变成不安全状态。
(2)安全状态与不安全状态两个概念的引入使许多人产生误解，容易认为安全状态意味着系统刁i会陷入死锁，不安全状态意味着系统肯定会陷入死锁。其实，安全状态与不安全状态基于安全序列而定义，其实质是指是否存在一个安全序列。安全序列的意义不在于从某时刻起系统按安全序列的顺序分配资源使各进程依次执行完毕。在某时刻确定的一个安全序列预示着，从此刻起，一定可以找到一种避免死锁的资源分配方案。一种特殊方案就是按照安全序列的顺序依次满足各进程的后续资源需求，使各进程依次顺序执行完毕。银行家算法基于这样一个原理：如果在系统运行的整个过程中，始终存在一种避免死锁的资源分配方案，则系统肯定能顺利推进直至所有进程都运行完毕。可以反证法来证明这一结论：如果系统陷入死锁，则肯定不存在一种避免死锁的资源分配方案。银行家算法的作用就是使系统始终存在一个安全序列，即始终存在一种资源分配方案。存在一种资源分配方案不意味着一定按此方案进行实际的资源分配。
(3)如果所有进程的最大资源需求都小于或等于系统资源总额，则在银行家算法的作用下，系统能始终保持安全状态(即时刻都有一个安全序列)。深入分析可知：系统的初始状态肯定是安全的。如果在某时刻存在着一个安全序列Sl，则意味着在银行家算法的作用下以后系统不会拒绝所有进程的资源请求而陷入死锁，总会有一个进程的资源请求能得到满足而继续推进，至少安全序列Sl中的第一个进程的资源请求能得到满足(这点很容易证明)，且该次资源分配后系统仍然保持安全状态(即存在一个安全序列S2，S2可能不同予上一个安全序列
S1)：依次递推，则系统会一赢处于安全状态。
(4)如果在某时刻系统处于不安全状态，即不存在一个安全序列，则意味着到最后可能(不一定)有一些进程的资源请求永远得不到满足，相互之间循环等待而产生死锁。一个特例就是从当前时刻起，进程一次性申请全部剩余资源，而且一直保持当时已经占有的资源直至运行完毕才释放其占有的全部资源。在这种情况下，如果不存在一个安全序列，则最后肯定会有些进程陷入死锁。
((5)银行家算法是一种比较谨慎的资源分配方法。在银行家算法的作用下，如果满足当前进程P的资源请求后系统处于安全状态(即存在一个安全序列)，那么就为P分配资源，否则拒绝P的资源请求。安全序列意味着一种资源分配方案，但不一定是唯一的资源分配方案，可能有另外的资源分配方案，只不过很难寻找。不存在安全序列并不意味着不存在一种可以避免死锁的资源分配方案。那么按银行家算法实施资源分配，就有可能拒绝一些不会导致死锁的资源请求，从而阻滞了某些进程的执行，而且降低了资源利用率。其他的资源分配方案难找是因为无法预知各进程以后申请资源的情况：分多少次申请，每次申清备类资源的数量是多少。
说完银行家算法的原理之后，很自然的就说到了银行家算法的数据结构：
设有n个进程Pl、P2、⋯⋯、Pn，共享m类资源R1、R2、⋯⋯、Rm。
(1)可利用资源向量Available=(al，a2，⋯，啪禽有m个元素，每个元素表示某类资源可利
用的单位数，初值为系统中所配置的该类资源全部单位数，其值随该类资源的分配和回收而动态改变。
(2)最大需求矩阵Max
Max(i,j)=k，表示进程Pi总共需要k个单位的Rj类资源
(3)分配矩阵AIlocation
Allocation(ij)=k，表示进程Pi已占有k个单位的Ri类资源。
(4)需求矩阵Need
Need(i，i)=k，表示进程Pi要完成T作还需要k个单位的Ri类资源，即剩余资源需求。上述三个矩阵之问存在下述关系：(见图1)Need(ij)=Max(iJ)一Allocation(iJ)Rl R2⋯⋯Rm
然后，银行家算法的流程。
设Reques乜是当前运行的进程Pi的请求向量，若Requesth[j]=k，表示进程Pi当前请求k个单位的Rj类资源。当进程Pi发出资源请求后，系统按下述步骤进行检套：
(1)若Request,>；一Need[i】，则为非法清求，进行相应处理，因为它需要的资源数超过它开始宣布的最大值：否则进行下一步。
(2)若Requesti>／Available，则表示系统现在可利用资源不能满足进程需求，阻塞进程；否则进行下一步。
(3)系统试探地把要求的资源分配给进程Pi，即不进行实际的资源分配，而八是修改有关数据结构：
Available2Available-Requesti
Allocation[i]2Allocation[i]+Requesti
Need[i]2