本文章将主要解释死锁的消除方法
一、死锁的概念
这是《操作系统》对于死锁的定义:
有并发进程P1,P2,…Pn,它们共享资源R1,R2,…Rm (n>0,m>0, n>=m)。其中,每个Pi(1≤i≤n)拥有资源Rj(1≤j ≤m),直到不再有剩余资源。同时,各Pi又在不释放Rj的前提下要求Rk(k≠j,1≤k ≤m),从而造成资源的互相占有和互相等待。在没有外力驱动的情况下,该组并发进程停止往前推进,陷入永久等待状态。
说人话就是,我自己的资源不给别人,别人的资源不给我,导致两个人都因为凑不齐资源而不能执行相关操作而一直等待,这就是死锁。结构图如下所示:
二、死锁产生的必要条件
如果产生死锁则一定会满足以下条件:
1、互斥条件。一个资源不能同时被两个或两个以上的进程所拥有。
2、不剥夺条件。一个进程未结束前,任何进程都不能得到该进程的资源。
3、部分分配。进程每次申请所需要的一部分资源,在等待申请其他资源的时间里,不会释放它已经拥有的资源。
4、环路条件。如下图所示:
而只要上述的条件被破坏就不会产生死锁,这就是我们解决死锁问题的思路。
三、死锁的消除方法
1、死锁预防
死锁预防是一种静态的消除死锁的方法。它是采用某种策略,限制并发进程对资源的请求,从而使得死锁的必要条件在系统执行的任何时间都不满足。
方法:
①、互斥条件是资源固有属性,不能避免
②、破坏“部分分配(请求和保持)”条件。预先全分配,等待释放。缺点:资源严重浪费(不使用也被占用)、降低进程并发性
③、破坏“不剥夺”条件。缺点:增加系统开销,且进程前段工作可能失效。
④、破坏“环路等待”条件。将资源分类并按顺利排列,规定按递增顺序请求资源;如果需要多个资源,必须同时请求(先低后高),如果占用了高的资源而请求低的资源时,必须先释放高的资源。如此可以避免形成环路。缺点:限制进程对资源的请求,系统开销大。具体操作如下图所示,P3占有s3资源,当它想申请s2资源时必须释放s3资源。
2、死锁避免
死锁避免可被称为动态预防,因为系统采用动态分配资源,在分配过程中预测出死锁发生的可能性并加以避免的方法。
方法:
- 进程启动拒绝:如果进程对资源的申请可能导致死锁,就不启动这个进程
- 资源分配拒绝:如果进程对资源的申请可能导致死锁,就不给进程分配该资源
详解:
进程启动拒绝
该表说明表达的意思如下:
(j=1…m)
由公式知道,只有当申请的资源小于剩余的资源,就会分配给进程资源,否则就不分配进程资源。
仅当满足以上条件时,才启动一个新进程Pn+1(即:只有满足新进程的请求及所有当前进程的最大请求量时,才启动该进程) 这个策略不是最优的,因为它假设了最坏的情况:所有进程同时发出它们的最大请求
资源分配拒绝
避免死锁的著名算法——银行家算法(Dijkstra)
类比的问题:
客户向银行申请贷款的数量是有限的 每个客户在第一次申请贷款时要声明完成该项目所需的最大资金量 在满足所有贷款要求时,客户应及时归还贷款 银行家在客户申请的贷款数量不超过自己拥有的最大值时,都应尽量满足客户的需要
例子:
设银行家有10万元资金,有三个客户A、B、C,分别需要8、3、9万元贷款完成项目 客户要求分期贷款,目前A已贷到4万 此时,B要申请2万,C要申请4万 银行家需要评估贷款请求的安全性,避免出现坏账 B借2万,C借4万,能借吗?在这个例子中银行家是操作系统, 资金是资源 ,客户是要申请资源的进程。
允许进程动态申请资源,在系统分配资源之前,先计算此次分配是否安全
本次分配不会导致系统进入不安全状态,则分配, 否则,本次请求资源的进程等待
安全状态
本次分配之后,存在一个进程安全序列{P1, …, Pn},对其中每一个Pi来说,它还需要的资源量不超过系统当前剩余的资源量与所有Pj (j<i)占有的资源量之和
不安全状态
不存在安全序列
算法中用到的数据结构
Available可用资源数组
Available[j] = k 目前资源j有k个
Max最大需求矩阵
Max[i,j] = l 进程Pi对资源j的最大需求数量是l个
Allocation分配矩阵
Allocation[i, j] = m 进程Pi已分配到资源j的数量是m个
Need需求矩阵
Need[i, j] = n 进程Pi还需要资源j的数量是n个
Request[i]资源请求
若Request[i, j] = q, 进程Pi请求资源j的数量是q个
流程图如下:
分配资源流程图
文章来源地址https://www.toymoban.com/news/detail-555509.html
释放资源流程图:
Work:系统运行过程中可用资源数量,初值=Available
Finish[i]:系统是否有足够资源分配给进程Pi,使其运行结束,初始为false
文章来源:https://www.toymoban.com/news/detail-555509.html
到了这里,关于【操作系统】死锁问题---死锁的消除方法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!