回顾之前提到的死锁的解决方式:预防,检测,避免。避免死锁的方式中最著名的就是银行家算法了。不过在介绍之前,先引入一段介绍。
死锁的避免 安全序列产生死锁的原因有很多,资源不足还有进程推进次序非法,都是原因。但是系统有不可能一下子满足所有进程的资源请求,才会产生死锁的危险。我们知道,进程结束以后是会释放资源的,释放的资源也是可以给后面的进程使用的。我们可以回顾一下哲学问题,我们的那种作法其实就是,当他们同时饿的时候,我们强制选出其中一位来先吃,吃完后释放筷子,这样也就不会有饿死的危险。如果按吃饭的优先级标号,那么按照优先级来排序,最后一定是可以所有的哲学家都有饭吃。(虽然这道题的序列是任意的)。于是我们定义这样一个概念: 如果一组进程,按照的次序执行,并为它们分配资源,如果都每个进程都能顺利执行,那么就称这个序列为一个安全序列。否则就是一个不安全序列。, 注意,这里说的是 “一个“ 而不是说 就是,因为安全序列有可能不止一个。 安全序列一定不会产生死锁,但是不安全序列只是有产生死锁的危险,并不是一定就会死锁。但是如果死锁了,那么一定是在不安全的序列下执行的。
银行家算法银行家算法主要分为两部分,安全检测和资源请求部分。该算法主要有四大数据结构: 下面简要介绍一下: Resource:系统中的资源总量 Available:系统中尚未分配的,可以使用的资源量 Need:每个进程对每种资源的最大需求量。(一行代表某个进程,一列代表某种资源) Allocation:目前已经分配的情况
若在资源请求的时候,本次的请求超过了它最初的资源要求总量,那么该进程就会因为总资源数不足而挂起。如果满足那么继续判断: 如果申请的资源数,大于可以使用的资源数,那么该进程就会因为可用资源数不足而挂起。否则继续分配。
资源分配算法下面用一个实例来说明银行家算法的实现:
如图,系统中有三种资源R1,R2,R3,总量分别是9,3,6。当前已经将他们分配给了4个进程,问是否存在一个安全序列P,使得这组进程在执行期间处于安全状态?
由前面的两个矩阵和总资源数,很容易算出可供分配的资源数为(0,1,1).于是我们就可以分析一下该算法的过程了:
![在这里插入图片描述](https://i-blog.csdnimg.cn/blog_migrate/09139f9f4001ddaabdbe966864ca9da7.png)
![在这里插入图片描述](https://i-blog.csdnimg.cn/blog_migrate/091b308510183bd3a0d77147108716d4.png)
![在这里插入图片描述](https://i-blog.csdnimg.cn/blog_migrate/53d60f50712870beb6a4ec1e0683ee29.png)
![在这里插入图片描述](https://i-blog.csdnimg.cn/blog_migrate/d3cdf1ddca3dc6be43ed7fa49e478d79.png)
我们发现,按照刚刚执行的顺序, P1->P3 ->P4>,那么这组进程一定不会发生死锁,也就是我们说的安全序列。当然上面的P3和P1的顺序调换,也是安全序列。所以,安全序列有可能不止一个。 到了最后的进程退出的时候,注意到Available的值一定等于总资源数。
死锁的解除那么如果死锁一旦发生了呢?那就得解除这个状态。我们一般有一下方式:
撤销死锁进程剥夺死锁进程的资源,直到不存在死锁鸵鸟算法(即直接忽略,当做什么都没发生,绝大多数的操作系统选择这个方法)。