导航菜单

挑战408

回顾之前提到的死锁的解决方式:预防,检测,避免。避免死锁的方式中最著名的就是银行家算法了。不过在介绍之前,先引入一段介绍。

死锁的避免 安全序列

产生死锁的原因有很多,资源不足还有进程推进次序非法,都是原因。但是系统有不可能一下子满足所有进程的资源请求,才会产生死锁的危险。我们知道,进程结束以后是会释放资源的,释放的资源也是可以给后面的进程使用的。我们可以回顾一下哲学问题,我们的那种作法其实就是,当他们同时饿的时候,我们强制选出其中一位来先吃,吃完后释放筷子,这样也就不会有饿死的危险。如果按吃饭的优先级标号,那么按照优先级来排序,最后一定是可以所有的哲学家都有饭吃。(虽然这道题的序列是任意的)。于是我们定义这样一个概念: 如果一组进程,按照的次序执行,并为它们分配资源,如果都每个进程都能顺利执行,那么就称这个序列为一个安全序列。否则就是一个不安全序列。, 注意,这里说的是 “一个“ 而不是说 就是,因为安全序列有可能不止一个。 安全序列一定不会产生死锁,但是不安全序列只是有产生死锁的危险,并不是一定就会死锁。但是如果死锁了,那么一定是在不安全的序列下执行的。

银行家算法

银行家算法主要分为两部分,安全检测和资源请求部分。该算法主要有四大数据结构: 在这里插入图片描述 下面简要介绍一下: Resource:系统中的资源总量 Available:系统中尚未分配的,可以使用的资源量 Need:每个进程对每种资源的最大需求量。(一行代表某个进程,一列代表某种资源) Allocation:目前已经分配的情况

安全检测

若在资源请求的时候,本次的请求超过了它最初的资源要求总量,那么该进程就会因为总资源数不足而挂起。如果满足那么继续判断: 如果申请的资源数,大于可以使用的资源数,那么该进程就会因为可用资源数不足而挂起。否则继续分配。

资源分配算法

下面用一个实例来说明银行家算法的实现:

如图,系统中有三种资源R1,R2,R3,总量分别是9,3,6。当前已经将他们分配给了4个进程,问是否存在一个安全序列P,使得这组进程在执行期间处于安全状态?

在这里插入图片描述 由前面的两个矩阵和总资源数,很容易算出可供分配的资源数为(0,1,1).于是我们就可以分析一下该算法的过程了:

首先我们先按顺序,将所有的可分配资源分配给P1,得出此时P1的资源数(左边),和P1的最大资源需求数(右边的need)。发现此时p1的资源不足以让运行,于是不分配给p1,让它暂时挂起,继续判断: 在这里插入图片描述接着我们按顺序,把所有的资源分配给P2,这个时候分配的资源数已经足够满足need矩阵了,程序顺利运行,然后退出的时候将所占有的资源全部释放,此时Available(可用资源数)增加,增加的量就是原P2所占有的量,从解题步骤来看,Available的数值就是我们之前假设的把所有资源都加在P2那时候的状态。 在这里插入图片描述此时因为资源增加了,可以将之前的P1再分配资源看看够不够,或者直接向下给P3分配。都可以,不过推荐第一种方式,因为怕遗漏。 在这里插入图片描述然后重复上面的操作,如果始终有某个进程不能满足,那么就不存在安全状态,否则全部程序能按此顺序完成,这就是安全状态。 在这里插入图片描述

我们发现,按照刚刚执行的顺序, P1->P3 ->P4>,那么这组进程一定不会发生死锁,也就是我们说的安全序列。当然上面的P3和P1的顺序调换,也是安全序列。所以,安全序列有可能不止一个。 到了最后的进程退出的时候,注意到Available的值一定等于总资源数。

死锁的解除

那么如果死锁一旦发生了呢?那就得解除这个状态。我们一般有一下方式:

撤销死锁进程剥夺死锁进程的资源,直到不存在死锁鸵鸟算法(即直接忽略,当做什么都没发生,绝大多数的操作系统选择这个方法)。

相关推荐: