【操作系统】进程管理——死锁(个人笔记)

学习日期:2024.7.13

内容摘要:死锁的概念和三大处理策略


目录

死锁

死锁的概念

死锁、饥饿和死循环的区别

死锁产生的必要条件

死锁的处理策略:预防、避免和解除

预防死锁

破坏互斥条件

破坏不剥夺条件

破坏请求和保持条件

破坏循环等待条件

避免死锁

模型引入

解题方法

死锁的检测和解除


死锁

死锁的概念

在《利用信号量机制解决问题》的哲学家进餐问题模型中,我们提到了死锁现象。在那个问题中,每个哲学家拿着一根筷子,每个哲学家都无法完成进餐。在这个模型中,每个人都占有一个资源,同时都在等待别人手上的资源,等到天荒地老也不会等到,这样就是发生了死锁

死锁,就是在并发环境下,各个进程因为争抢资源而导致的一种互相等待对方手里的资源,而所有进程都阻塞,无法向前推进的现象。

发生死锁后,如果没有外力(操作系统)干涉,所有的进程都无法推进。

死锁、饥饿和死循环的区别

死锁:各进程互相等待对方手里的资源,导致所有进程都阻塞的现象。

饥饿:由于长期得不到想要的资源,某进程无法向前推进的现象。

死循环:某进程执行过程中一直跳不出某个循环的现象。有时是因为程序逻辑bug,有时是程序员故意设计的(比如之前介绍的PV操作当中的自旋锁)。

死锁一定是等待对方手里的资源,且发生死锁的进程全部都推进不了。而饥饿,比如说短作业优先算法中,长作业可能会饥饿,但是短作业是一直在推进的。

死锁产生的必要条件

互斥条件:只有对必须互斥使用的资源的争抢才会导致死锁。(如果可以共用筷子就不会死锁了)

不剥夺条件:进程所获得的条件在未使用完之前,不能由其它进程夺走,只能主动释放。(如果哲学家可以抢别人的筷子,就不会死锁了)

请求和保持条件:进程已经保持了至少一个资源,但又提出了新的资源请求,而该资源又被其它进程所占有,此时请求进程被阻塞,但又会对自己已有的资源保持不放。(如果哲学家会在阻塞时放下筷子,就不会死锁了)

循环等待条件:存在一种进程资源的循环等待,链中的每一个进程已经获得的资源同时被下一个进程所请求。(如果最后等待资源的请求没有连成圈,就不会死锁了)

以上四个条件必须全部满足,缺一不可,就会发生死锁。

发生死锁时一定有循环等待,但是发生循环等待时未必死锁!比如说,此时发生了循环等待,但是如果3号哲学家有个朋友进程,正在给他送筷子,他在循环等待的同时也在等待朋友送来筷子,这样在一定的等待时间后,3号哲学家就可以开始进食,就不会死锁。

对不可剥夺资源的不合理分配,可能会导致死锁


死锁的处理策略:预防、避免和解除

预防死锁

预防死锁主要是破坏死锁产生的四个必要条件

破坏互斥条件

如果把只能互斥使用的资源改造为允许共享使用,则系统不会进入死锁状态。

比如SPOOLing技术,操作系统可以把进程对临界资源(如打印机)的请求装进一个输出进程队列里,然后输出进程再依次调用打印机,这样对进程来说,对打印机的访问就不互斥了。

破坏不剥夺条件

①当某个进程请求新资源得不到满足时,它必须立即释放保持的所有资源,待以后需要时再申请。

②当某个进程需要的资源被其它进程所占用的时候,可以由操作系统协助,将想要的资源强行剥夺(从其它进程那里抢过来)。这种方式一般需要考虑各进程的优先级。

缺点:

1.实现比较复杂。

2.释放已经获得的资源可能导致前一阶段工作的失效,因此这种方法一般只适用于易保存和恢复状态的资源。

3.反复地申请和释放资源会增加系统开销,降低系统吞吐量。

4.若采用方案①,意味着只要暂时得不到某个资源,之前获得的那些资源就都需要放弃,以后再重新申请。如果一直发生这样的情况,就会导致进程饥饿。

破坏请求和保持条件

可以采用静态分配方法,即进程在运行前一次申请完它所需要的全部资源,在它的资源未满足前,不让它运行。一旦投入运行后,这些资源就一直归它所有,该进程就不会请求其它资源了。

即哲学家一次申请左右两根筷子,不会拿着筷子等待,这样就不会死锁了。

缺点:有的资源可能只需要使用极短的时间,但是在进程运行时一直占用,会造成资源浪费。

破坏循环等待条件

可采用顺序资源分配法,首先给系统中的资源编号,规定每个进程必须按编号递增的顺序请求资源,编号相同的资源一次申请完。

还是以哲学家进餐问题为例。0号哲学家需要0,1筷子,1号需要1,2...但4号哲学家需要的是4号筷子和0号筷子。

极端情况下,0号哲学家拿0号筷子,1号哲学家拿1号筷子......但是,4号哲学家不会拿起4号筷子然后使所有进程循环等待。因为在使用顺序资源分配法后,4号哲学家在拿起4号筷子前要先拿起0号筷子,但此时0号筷子已经被0号哲学家占用,所以4号筷子会在不占用资源的情况下阻塞,避免了死锁。

这是因为,如果要发生死锁,就必然会有循环等待,而只要循环等待,这个“圈”就有个“头尾接口”,我们只需要按编号大小顺序分配资源,就可以破坏“接口”处的循环等待条件。

缺点:

1.不方便新增设备,因为可能需要重新编号。

2.进程实际使用资源的顺序可能和资源编号递增的顺序不一致,导致资源浪费。

3.必须按规定顺序申请资源,用户编程麻烦。

避免死锁
模型引入

避免死锁的核心是避免系统进入不安全状态,以银行家算法为例。

你是一个银行家,手里有100亿资金,然后有B、A、T三个企业想找你贷款,B最多贷70亿,A最多贷40亿,T最多贷50亿。但是你们这个贷款很奇特,如果你借给企业的钱的总数达不到企业提出的最大要求,那么不管你之前借了多少钱,企业都不用还了。(什么慈善家)

一开始,BAT三个企业分别从你这里借了20,10,30亿,掰手指可得你还剩40亿

企业最大需求已借走最多还会借
B702050
A401030
T503020

 此时,如果B还想借30亿,你借不借呢?

企业最大需求已借走最多还会借
B7020+30=5050-30=20
A401030
T503020

 掰手指可得,如果借出去,我们手里还剩10亿,但剩下三个公司都可能借更多的钱,无法满足需求,我们会破产,这样不安全。所以不能答应B的请求。

如果A还想借20亿,你借不借呢?

企业最大需求已借走最多还会借
B702050
A4010+20=3030-20=10
T503020

 我们现在手上还剩20亿,可以满足A或T的需求,可以先全部借给T,等T还回来了,我们手上就有50亿了,再借给B,满足他的需求,最后借给A就行。这个顺序无所谓,也可以先全部借给A。所以是可以借的,我们不会破产,是安全的。

在这种情况下,我们把形如A->T->B或者T->B->A这种的序列叫做安全序列。

所谓安全序列,就是如果系统按照这种序列分配资源,则每个进程都能顺利完成,只要能找出一个安全序列,系统就是安全状态,反之则是不安全状态,安全序列可能有多个。

如果系统处于不安全状态,就可能发生死锁。(不安全状态是死锁的必要不充分条件)

因此,我们可以在资源分配之前预先判断这次分配是否会导致系统进入不安全状态,以此决定是否答应资源分配请求,这也是“银行家算法”的核心思想。

在这个模型中,我们手上的钱就是临界资源,三个企业是三个进程,在第二种情况,我们手上的钱一个进程都满足不了的时候,就发生了死锁。

银行家算法是荷兰学者Dijkstra为银行系统设计的(没错又是这个人),一开始真的是用来在银行发放贷款时避免不会满足所有用户需要的情况,后来用于操作系统避免死锁。

所需资源可能不止一种,在这种情况下,我们用形如(3,1,1)这样的格式记录进程所需的资源和所缺的资源。

解题方法

例:资源总数(10,5,7),问此时系统是否处于安全状态。

用资源总数做减法运算得,剩余资源(3,3,2),最多还需要的资源,用最大需求资源减已分配即可。

然后检查剩余资源能满足哪个最多还需要的资源。比如说满足P1,那就分给P1,P1运行完成后释放(2,0,0),剩余资源变为(5,3,2),能满足P3,P3释放资源,变为(7,4,3)...以此类推,每次满足可以满足的进程,释放资源即可。

好比带兵打仗,一开始兵(资源)少,就先满足容易满足的进程,打败它们后“招降”他们,解放更多的兵力,然后用更多的兵力“打败”更多的进程,最后就能满足最难的需求。如果在某个情况下全都满足不了,系统就是处于不安全状态。

银行家算法就是把最大需求、已分配、最多还需要的资源,分别用矩阵保存,然后在分配资源之前,系统会先在数据结构中尝试分配,然后用安全性算法检查此次分配是否会导致系统进入不安全状态。

所谓安全性算法,就是在做我们刚刚做的事,检查当前的可用资源能否满足某个进程的最大需求,如果可以,就把该进程加入安全序列,并模拟回收该进程的资源,然后重复,直到判断最后能否让所有进程加入安全队列。

死锁的检测和解除

死锁的检测和解除允许死锁发生,由系统负责检测出死锁并解除。

为了能实现这一功能,必须

①用某种数据结构保存资源的请求和分配信息,这种数据结构叫资源分配图。

②提供一种算法,利用信息检测系统是否已经进入死锁状态。

如图,P2进程此时请求1个R1资源(一个指向R1的蓝箭头),但是3个R1资源都分配出去了(三个出去的绿箭头)所以P2会阻塞。而P1正在请求R2资源,R2资源还剩下一个,是可以分配给P1的,所以P1能够执行完。在P1执行完之后,释放所有资源,删去连着P1的箭头,此时就可以将R1资源分配给R2了。

所以根据这样一幅图,我们能看出进程的运行顺序,和系统是否死锁,如果最终能消除所有边,就说图是完全可简化的,此时一定不会死锁。

如图,此时P2请求1个R1资源,但R1资源已经全部分配完了。P1请求2个R2资源,但是R2资源已经分配了一个给P2,数量不够,无法完全简化,这样就发生了死锁。

 一旦检测出死锁的发生,就应该立刻解除死锁。并不是系统中所有的进程都是死锁状态,用死锁检测算法化简资源分配图后,还连着边的进程就是死锁进程。

解决死锁的主要方法有:

1.资源剥夺法。挂起(暂时放到外存上)某些死锁进程,并抢占其资源,将这些资源分配给其它的死锁进程。但是应防止挂起的进程长时间得不到资源而饥饿。

2.撤销进程法。强制撤销部分甚至全部死锁进程,剥夺它们占用的资源。实现简单但是过于粗暴,可能导致很多即将完成的进程“功亏一篑”。

3.进程回退法。让部分死锁的进程回退到足以避免死锁的地步,但这要求系统要记录进程的历史信息,设置还原点。

抢谁的资源?如何决定“对谁动手”——欺负软柿子

进程优先级高的、执行时间长的、快要完成的、交互式的(重视即时反馈的)少动手。

欺负优先级低的、批处理的、占用资源多的。


感谢您看到这里,如果满意的话麻烦您点个赞支持一下,个人主页还有更多内容分享。

个人能力不足,如有错漏还请指出,我会尽快修改。

内容总结自王道计算机考研《操作系统》 和 人民邮电出版社《操作系统导论》

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/798575.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【从0到1进阶Redis】主从复制 — 主从机宕机测试

上一篇:【从0到1进阶Redis】主从复制 测试:主机断开连接,从机依旧连接到主机的,但是没有写操作,这个时候,主机如果回来了,从机依旧可以直接获取到主机写的信息。 如果是使用命令行,来…

STM32MP135裸机编程:唯一ID(UID)、设备标识号、设备版本

0 资料准备 1.STM32MP13xx参考手册1 唯一ID(UID)、设备标识号、设备版本 1.1 寄存器说明 (1)唯一ID 唯一ID可以用于生成USB序列号或者为其它应用所使用(例如程序加密)。 (2)设备…

笔记 1 : 课本前 2 章

现在开始跟着彭老师学习 arm 。把重要的知识点归拢一下,便于复习。早日学有所成,为国为家为己,更幸福些。 (1)冯诺依曼架构与哈弗架构,与混合架构: 以及: (2&#xff0…

php反序列化--2--PHP反序列化漏洞基础知识

一、什么是反序列化? 反序列化是将序列化的字符串还原为PHP的值的过程。 二、如何反序列化 使用unserialize()函数来执行反序列化操作 代码1: $serializedStr O:8:"stdClass":1:{s:4:"data";s:6:"sample";}; $origina…

03-Charles实战

一、抓包分析问题示例 1)问题描述 2)抓包分析 这是后台响应回来的错误信息,说明问题一是后台的原因;但是后台只响应了一条信息,而前端页面却显示两条错误信息,说明前端页面处理异常的时候逻辑有问题&#…

Android-- 集成谷歌地图

引言 项目需求需要在谷歌地图: 地图展示,设备点聚合,设备站点,绘制点和区域等功能。 我只针对我涉及到的技术做一下总结,希望能帮到开始接触谷歌地图的伙伴们。 集成步骤 1、在项目的modle的build.gradle中添加依赖如…

深层神经网络示例

维度说明: A[L]、Z[L]:(本层神经元个数、样本数) W[L]:(本层神经元个数、上层神经元个数) b[L]:(本层神经元个数、1) dZ[L]:dA[L] * g’A&#xf…

leetcode 513. 找树左下角的值

给定一个二叉树的 根节点 root&#xff0c;请找出该二叉树的 最底层 最左边 节点的值。 假设二叉树中至少有一个节点。 示例 1: 输入: root [2,1,3] 输出: 1示例 2: 输入: [1,2,3,4,null,5,6,null,null,7] 输出: 7提示: 二叉树的节点个数的范围是 [1,104]-231 < Node.val &…

python的字符串

字符串 简单操作 创建 利用 ‘ ’ 或 “ ” 将字符或数字包裹起来的都为字符串 a"你好" 格式化字符串 元组的字符格式化 字符串格式化函数 srt.format() f格式化 方法 split()//指定分割符经行分割 strip()//指定移除字符头尾的字符 join()//指定序列中的字符连接成新…

Java 设计模式系列:外观模式

简介 外观模式&#xff08;Facade Pattern&#xff09;是一种设计模式&#xff0c;又名门面模式&#xff0c;是一种通过为多个复杂的子系统提供一个一致的接口&#xff0c;而使这些子系统更加容易被访问的模式。该模式对外有一个统一接口&#xff0c;外部应用程序不用关心内部…

Redis系列命令更新--Redis哈希命令

一、设置密码验证&#xff1a; 使用文本编辑器&#xff0c;这里使用Notepad&#xff0c;打开Redis服务配置文件。 注意&#xff1a;不要找错了&#xff0c;通常为redis.windows-service.conf&#xff0c;而不是redis.windows.conf。后者是以非系统服务方式启动程序使用的配置…

2-33 基于matlab的用于计算无故障的斜齿轮对啮合时接触线长度随时间的变化

基于matlab的用于计算无故障的斜齿轮对啮合时接触线长度随时间的变化&#xff0c;根据需求设置斜齿轮对的相应参数&#xff0c;得到结果。程序已调通&#xff0c;可直接运行。 2-33 斜齿轮对啮合时接触线长度 齿轮参数 - 小红书 (xiaohongshu.com)

【日常记录】【CSS】display:inline 的样式截断

文章目录 1. 案例2. css属性&#xff1a;box-decoration-break参考地址 1. 案例 现在有一篇文章&#xff0c;某些句子&#xff0c;是要被标记的&#xff0c;加一些css 让他突出一下 可以看到&#xff0c;在最后&#xff0c;断开了&#xff0c;那如若要让 断开哪里的样式 和 开始…

《C专家编程》杂谈

库函数调用和系统调用的区别 系统调用比函数调用要慢很多&#xff0c;因为还要切换到内核模式。

时域分析----移动平均滤波器介绍及其在金融应用示例

介绍 移动平均滤波器&#xff08;Moving Average Filter&#xff09;是一种基本但功能强大的信号处理技术&#xff0c;广泛应用于各种数据平滑和去噪任务中。其主要目的是通过对数据进行平均处理&#xff0c;减少随机波动和噪声&#xff0c;从而突出数据中的趋势和规律。移动平…

二进制成分分析软件(组件漏洞扫描)

免费试用软件 华为云腾讯云 华为云 进入二进制成分分析页面 二进制扫描地址 一个账号免费扫描5次 腾讯云 进入二进制成分分析页面 二进制扫描地址 免费300M流量 其他二进制分析软件 推荐使用悬镜、墨菲安全&#xff0c;支持IDEA插件&#xff0c;在线分析maven依赖。 …

操作系统真象还原:文件描述符简介

14.3 文件描述符简介 14.3.1 文件描述符原理 inode 是操作系统为自己的文件系统准备的数据结构&#xff0c;它用于文件存储的管理&#xff0c;与用户关系不大&#xff0c;咱们要介绍的文件描述符才是与用户息息相关的。 文件描述符即 file descriptor&#xff0c;但凡叫“描…

【周末闲谈】Stable Diffusion会魔法的绘画师

个人主页&#xff1a;【&#x1f60a;个人主页】 系列专栏&#xff1a;【❤️Python】 文章目录 前言Stable Diffusion介绍 使用ComfyUI 和 WebUIComfyUIWebUI 配置需求 Stable Diffusion资源分享吐司AiAUTOMATIC1111Civitai绘世整合包Nenly同学stability.ai 前言 在很早之前&…

【前端项目笔记】10 项目优化上线

项目优化上线 目标&#xff1a;优化Vue项目部署Vue项目&#xff08;上线提供使用&#xff09; 项目优化 项目优化策略&#xff1a; 生成打包报告&#xff1a;根据生成的报告发现问题并解决第三方库启用CDN&#xff1a;提高首屏页面的加载效率Element-UI组件按需加载路由懒加…

Django 删除所有数据

1&#xff0c;添加模型 Test/app11/models.py from django.db import modelsclass Post(models.Model):title models.CharField(max_length200)content models.TextField()pub_date models.DateTimeField(date published)class Book(models.Model):title models.CharFiel…