程序员经验分享-hwhale

死锁预防、死锁避免、死锁检测

2023-05-16

死锁

1.死锁的概念

1.1死锁的定义

多个进程并发执行，由于竞争资源而造成的一种僵局（互相等待），若无外力作用，这些进程都将无法推进，这就是死锁现象。

例如：系统中只有一台打印机和一台输入设备，若进程p1正在占用输入设备，同时又提出使用打印机的请求；而进程p2正在占用打印机，同时又提出请求输入设备的请求。这样两个进程相互无休止地互相等待，均无法继续执行，此时这两个进程进入死锁状态。

1.2死锁产生的原因

①系统资源的竞争

只有对不可剥夺资源的竞争（如打印机） 才可能产生死锁，对可剥夺资源的竞争是不会产生死锁的。

②进程推进顺序非法

进程在运行过程中，请求和释放资源的顺序不当，同样会导致死锁。如1.1的例子。

③死锁产生的必要条件： 死锁产生必须同时满足以下四个条件，任意一条不成立，便不会产生死锁：

  • 互斥条件： 各个进程必须互斥的对系统分配的资源（临界资源）进行排他性使用。
  • 不可剥夺条件： 进程使用完临界资源之前，不能被其他资源强行夺走，只能自行释放。
  • 请求并保持条件：进程已经保持了一个临界资源，但又提出了新的申请临界资源要求，而该临界资源被其他进程占有，此时，请求进程被阻塞，但又保持对自己占有的临界资源保持不放。
  • 循环等待条件: 存在一种进程资源的循环等待链条，每个进程已获得的临界资源同时被下一个资源所请求。

2.死锁的预防

预防死锁只需要破坏死锁的四个必要条件之一即可：

①破坏互斥条件

②破坏不可剥夺条件： 当进程的新资源不可取得时，释放自己已有的资源，待以后需要时重新申请。 但这种方法可能导致迁移阶段工作的失效，反复地申请和释放资源会增加系统开销，降低系统吞吐量。

③破坏请求并保持条件：进程在运行前一次申请完它所需要的全部资源，在它的资源为满足前，不把它投入运行。一旦投入运行，这些资源都归它所有，不能被剥夺。但这种方法系统资源被严重浪费，而且可能导致饥饿现象，由于个别进程长时间占用某个资源，导致等待该资源的进程迟迟无法运行。

④破坏循环等待条件： 给资源编号，规定每个进程必须按编号递增地顺序请求资源，同类资源一次性申请完。这种方法存在问题是发生作业使用资源地顺序与系统规定的顺序不同，造成系统地浪费，并且给编程带来麻烦。

这四种方法都有各自的缺陷，我们一般不采用。

3.死锁的避免

避免死锁同样属于事先预防地策略，但不是破坏死锁地必要条件，而是在资源动态分配过程中，防止系统进入不安全状态，以避免发生死锁。

3.1系统安全状态

允许进程动态地申请资源，但系统在进行资源分配之前，先计算此次分配的安全性。若此次分配不会导致系统进入不安全状态，则允许分配；否则让进程等待。

安全状态：系统能按照某种进程推进顺序为每个进程分配其所需地资源，直至满足每个进程对资源地最大需求，使每个进程可顺序完成。

并非所有不安全状态都是死锁状态，但当系统进入不安全状态后便可能进入死锁状态；只要处于死锁状态，则一定处于不安全序列状态。

如：进程p1,p2,p3，共有12台磁带机。在t时刻，p1，p2，p3所需要资源和已分配资源如下表：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-YAFyZT1g-1657637911433)(C:\Users\ThinkStation K\AppData\Roaming\Typora\typora-user-images\1657634524716.png)]

在t时刻是安全的，因为存在一个安全序列p2、p1、p3，按照这个顺序分配资源，每个进程都能顺利完成。

3.2银行家算法

银行家算法是著名的死锁避免算法，核心思想是：把操作系统视为银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。 规定：

  • 进程运行前先声明对各种资源的最大需求量
  • 若银行家资金能够达到进程声明的最大需求量便能将所有资金收回，否则一分钱受不了，产生坏账。

例:某时刻进程的资源使用情况如下表，此时的安全序列为：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-OjiDex36-1657637911434)(C:\Users\ThinkStation K\AppData\Roaming\Typora\typora-user-images\1657637524207.png)]

安全序列不存在，此时已经处于不安全序列状态。

判断过程如下：

  • 可用资源(0, 2, 1)大于p1进程所需，可以成功完成p1进程回收p1资源后，可用资源为(0, 2, 1) + (2, 0, 0) = (2, 2, 1)。
  • 可用资源(2, 1, 1)大于p4进程所需，可以成功完成p4资源，回收p4资源后，可用资源为(2, 2, 1) + (0, 0, 1) = (2, 2, 2)。
  • 可用资源(2, ,2 , 2)既无法完成p2进程所需，又不够p3进程所需，为不安全序列状态。

4.死锁的检测和解除

若系统在分配资源是不采取任何措施，应该提供死锁检测和避免手段。

4.1资源分配图

用圆圈代表一个进程，用框代表一类资源。从进程到资源的有向边称为请求边，表示该进程从该类资源申请一个资源；从从资源到进程的边称为分配边，表示该类资源已有一个资源分配给该进程。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-jag9w1UC-1657637911434)(C:\Users\ThinkStation K\AppData\Roaming\Typora\typora-user-images\1657635287017.png)]

如：进程p1已经分配了2个R1资源，并请求了一个R2资源；进程p2分配了一个R1，一个R2资源，并申请了一个R1资源。

4.2死锁定理

简化资源分配图可检测系统状态S是否为死锁状态。简化方法如下：

  • 找出既不阻塞又不孤点的进程Pi(找出一条有向边与它相连，且该有向边对应资源的申请数量小于等于系统中已有的空闲资源数量)。
  • 消除与Pi所有相邻的请求边和分配边，使之成为孤立的节点。
  • 循环以上两条。

总结来说就是：依次消除与不阻塞进程相邻的边，直到无边可消除。

如果能消除所有的边，则没有产生死锁；否则产生死锁。

S为死锁的条件是当且仅当S状态的资源分配图是不可完全简化的，该条件为死锁定理。

例如：p1是既不阻塞又不孤点的进程，消去与它相邻的所有边。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Apa24oHi-1657637911435)(C:\Users\ThinkStation K\AppData\Roaming\Typora\typora-user-images\1657636278786.png)]

p2既不阻塞又不孤点，消去与它相邻的所有边。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-0FfxZXYJ-1657637911435)(C:\Users\ThinkStation K\AppData\Roaming\Typora\typora-user-images\1657636288968.png)]

消去了所有边，不是死锁状态。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-lHBLxHAO-1657637911435)(C:\Users\ThinkStation K\AppData\Roaming\Typora\typora-user-images\1657636297852.png)]

4.3死锁解除

一旦检测出死锁，就应该立即采取措施来接触死锁。死锁解除的主要方法有：

  • 资源剥夺法。 挂起某些死锁进程，抢占它的资源，分配给其他死锁进程。
  • 撤销进程法。 强制撤销部分进程并剥夺这些进程的资源，让其他进程顺利执行。
  • 进程回退法。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

死锁预防

死锁避免

死锁检测

死锁预防、死锁避免、死锁检测 的相关文章

  • 报错：CommandNotFoundError: Your shell has not been properly configured to use ‘conda activate‘.

    新安装anaconda xff0c 输入 conda activate 报错 终端输入 xff1a source activate source deactivate conda activate

  • Windows下C++调用Http接口

    1 WininetHttp h span class token macro property span class token directive keyword pragma span once span span class toke

  • ubuntu系统 PyImport_ImportModule 返回 NULL

    原因 xff1a 1 python文件出错 2 python文件路径出错 在PyImport ImportModule命令前添加语句 PyRun SimpleString 34 import sys 34 PyRun SimpleStrin

  • ModuleNotFoundError:No module named

    经典报错 xff1a ModuleNotFoundError No module named XXX 但通过conda list 可以发现相关第三方包 在程序中添加路径 import sys sys path append 39 三方包路径

  • Iterator迭代器

    1 迭代器的概述 迭代器 是一种通用的遍历集合 取出集合中元素的方式 迭代器由来 集合有很多种 每种集合的数据结构是不同的 数组 链表 哈希表 集合取出元素的方式也不同 我们不可能为每种集合都定义一种取出元素的方式 浪费 所以我们就可以使用

  • strcat函数将两个字符串拼接在一起

    span class token macro property span class token directive keyword include span span class token string 34 pch h 34 span

  • 4、C语言结构体使用---链表

    结构体 1 掌握结构体的概念和用法 2 掌握结构体数组和结构体指针 3 掌握包含结构体的结构体 4 掌握结构体搭建链表方法 5 掌握结构体及链表在产品应用场景 结构体的概念 比如说学生的信息 xff0c 包含了学生名称 学号 性别 年龄等信

  • 爬虫之爬取百度贴吧

    爬虫之爬取百度贴吧 直接示例代码 xff1a import requests from lxml import html etree 61 html etree from lxml import etree class Tieba obje

  • 正则表达式匹配开头和结尾（^、$、[^指定字符]）

    1 匹配开头和结尾 代码功能 匹配字符串开头 匹配字符串结尾 示例1 xff1a 需求 xff1a 匹配以数字开头的数据 import re 匹配以数字开头的数据 match obj 61 re match 34 d 34 34 1hell

  • re.sub()用法详解

    源代码 参数及其意义 xff1a def sub pattern repl string count 61 0 flags 61 0 34 34 34 Return the string obtained by replacing the

  • BERT模型的详细介绍

    1 BERT 的基本原理是什么 xff1f BERT 来自 Google 的论文Pre training of Deep Bidirectional Transformers for Language Understanding xff0c

  • 自然语言处理(NLP)之使用TF-IDF模型计算文本相似度

    自然语言处理 NLP 之使用TF IDF模型计算文本相似度 所用数据集 xff1a ChnSentiCorp htl all csv 语料库即存放稀疏向量的列表 要注意的是 xff0c 搜索文本text与被检索的文档共用一个特征词词典 NL

  • C++中关于类重复定义的分析和解决方法

    在C 43 43 中将类以及类中的成员函数的声明放在 h的头文件中 xff0c 而将类中成员函数的定义 xff08 即实现代码 xff09 放在 cpp的源文件中 xff0c 这样我们的程序设计起来更加的模块化 xff0c 但是 xff0c

  • re.search()用法详解

    re search xff1a 匹配整个字符串 xff0c 并返回第一个成功的匹配 如果匹配失败 xff0c 则返回None pattern 匹配的规则 string 要匹配的内容 flags 标志位 这个是可选的 就是可以不写 可以写 比

  • re.findall()用法详解

    re findall xff1a 函数返回包含所有匹配项的列表 返回string中所有与pattern相匹配的全部字串 xff0c 返回形式为数组 示例代码1 xff1a 打印所有的匹配项 import re s 61 34 Long li

  • Linux系统中创建虚拟环境详解

    1 方法一 1 1 安装虚拟环境的命令 xff1a sudo pip install virtualenv sudo pip install virtualenvwrapper 1 2 安装完虚拟环境后 xff0c 如果提示找不到mkvir

  • 使用python将图片改为灰度图或黑白图

    使用python将图片改为灰度图或黑白图有三种方式 xff0c 分别是是使用cv2库和PIL库来实现 xff0c 详细过程如下所示 1 使用cv2库将图片改为灰度图 在使用cv2进行读取原彩色图片时 xff0c 在里面添加一个参数cv2 I

  • 虚拟机中windows镜像下载与安装

    镜像文件下载 xff1a 链接 xff1a https pan baidu com s 1VKWMHHCGRwWXk2GpxyUp0A 提取码 xff1a shlg 注意 xff1a 虚拟机中的镜像和本地电脑系统安装的镜像是一样的 安装教程

  • mongo数据库中字符串型正负数值比较大小

    数据库中数据展示 xff1a 使用python代码实现 xff1a Requires pymongo 3 6 0 43 from pymongo import MongoClient client 61 MongoClient 34 mon

随机推荐

  • flask项目中内部接口调用其他内部接口操作

    1 requests 在 Flask 框架项目中 xff0c 可以通过使用 requests 模块来进行内部接口调用 requests 模块是 Python 中常用的 HTTP 请求库 xff0c 可以用于发送 HTTP 请求和处理响应 示

  • ElasticSearch删除索引中的数据（delete_by_query）

    1 删除两个月以前的数据 在 Elasticsearch 中 xff0c 要删除两个月以前的数据 xff0c 可以通过以下步骤 xff1a 计算当前时间的两个月前的日期 xff0c 可以使用 Python 的 datetime 模块来实现

  • Qt Creator子图绘制

    Qt中在一个窗体文件内画所有图显然是不好维护的 xff0c 我们可以将主窗体拆分为几个子窗体 xff0c 在子窗体中绘制子图 xff0c 这样便于我们去维护我们的代码 1 在工程文件中右键 gt Add New 2 选择Qt 设计师界面 3

  • MessageFilter [target=odom ]: Dropped 100.00% of messages so far.问题解决

    错误提示 WARN 1580994954 426403779 MessageFilter target 61 odom Dropped 100 00 of messages so far Please turn the ros gmappi

  • 电磁循迹智能车基于stm32cubeMX、HAL库—我的第一辆智能车

    我的第一辆智能车 电磁循迹智能车 提示 本文适用于初学 想完成一个基础四轮车练练手者 大佬还请勿喷 不过欢迎提出意见 有纰漏之处我将及时纠正 注 工程代码链接已贴在文末 前言 所用到的硬件平台 stm32f103c8t6 舵机 电机 L29

  • 2022年国赛建模B题思路与程序

    B题 无人机遂行编队飞行中的纯方位无源定位 关键词搜索 xff1a 无人机 xff0c 无源定位 其实这个工作特别多 xff0c 知网一堆 xff0c 如果选这个题一定要想好做的出彩 xff0c 另外网上的场景和本题不是很一样 xff0c

  • 2017全国大学生电子设计竞赛:室内可见光定位装置

  • 基于FreeRTOS下多任务的同时操作

    FreeRTOS移植及多任务的实现 前言 xff1a 一 FreeRTOS移植 xff08 1 xff09 移植准备工作 xff08 2 xff09 FreeRTOS移植到stm32中 xff08 3 xff09 例程验证 二 多任务实现

  • undefined symbol 问题解决记录

    历经一个月 xff0c 昨日完成打印机network部分的编写 c语言 xff0c 编写makefile构建动态库 构建完成后遂进行调用测试 xff0c 出现 xff1a network symbol lookup error usr li

  • 2.O(NlogN)的排序算法

    认识O NlogN 的排序算法 1 剖析递归行为及其时间复杂度的估算 递归过程 xff1a 递归过程是一个多叉树 xff0c 计算所有树的结点的过程就是利用栈进行后序遍历 xff0c 每个结点通过自己的所有子结点给自己汇总信息之后才能继续向

  • 4.二叉树的遍历(C++版)

    二叉树的递归 1 二叉树递归遍历 二叉树的递归序 递归序过程 xff1a 两个注释1之间的代码代表第一次来到一个节点的时候 xff0c 会判断一下这个节点是否为空 xff1b 来到这个节点的左树去遍历 遍历完第二次回到本函数 xff0c 进

  • 6.暴力递归转动态规划

    动态规划 1 什么是动态规划 xff1f 动态规划就是暴力递归 xff08 回溯 xff09 的过程中有重复调用的过程 xff0c 动态规划在算过每次调用后把答案记下来 xff0c 下次再遇到重复过程直接调用这个行为就叫动态规划 动态规划就

  • 8.岛问题

    岛问题 题目 一个矩阵中只有0和1两种值 xff0c 每个位置都可以和自己的上 下 左 右四个位置相连 xff0c 如果有一片1连在一起 xff0c 这个部分叫做一个岛 xff0c 求一个矩阵中有多少个岛 xff1f 例子 0 0 1 0

  • 9.KMP算法

    KMP算法 1 KMP算法解决的问题 字符串str1和str2 xff0c str1是否包含str2 xff0c 如果包含返回str2在str1中开始的位置 xff0c 如果不包含返回 1 如果做到时间复杂度O N 完成 xff1f 测试用

  • 10.Manacher算法（用于解决回文子串问题）

    Manacher算法 1 Manacher算法解决的问题 字符串str中 xff0c 最长回文子串的长度如何求解 xff1f 如何做到时间复杂度O N 完成 xff1f 回文序列是从左往右和从右往左看一样 xff0c 如abba xff0c

  • git push代码到远程仓库，报错解决：fatal: unable to access ‘https://github.com/.......‘: OpenSSL SSL_read: Connec

    报错如下 xff1a 产生原因 xff1a 一般是这是因为服务器的SSL证书没有经过第三方机构的签署 xff0c 所以才报错解除ssl验证后 xff0c 再次git即可 解决办法输入此条git命令 xff1a git config glob

  • 11.滑动窗口的最大值——重要结构双端队列

    滑动窗口最大 xff08 小 xff09 值 1 滑动窗口最大值结构 窗口概念 xff1a 一开始窗口左边界L 有边界R都停留在数组左侧 xff0c 窗口L和R都只能往数组右边移动 xff0c 并且左边界L永远不能超过有边界R 任何时刻都能

  • 12.单调栈——解决接雨水和柱状图中的最大矩形等问题

    单调栈 1 单调栈实现结构 单调栈解决的问题 xff1a 给你一个数组 想要用尽可能低的代价知道数组中每一个元素的左边元素比它大的或者右边元素比他大的信息是什么 如果用暴力方法 xff0c 左边遍历一次右边遍历一次 xff0c 时间复杂度为

  • 12.快速排序

    1荷兰国旗问题 问题1 xff1a 给定一个数组arr和一个数num xff0c 将小于等于num的数放在数组的左边大于num的数放在数组的右边 xff08 不要求有序 xff09 要求额外空间复杂度为O 1 时间复杂度为O N 遍历数组元

  • 死锁预防、死锁避免、死锁检测

    死锁 1 死锁的概念 1 1死锁的定义 多个进程并发执行 xff0c 由于竞争资源而造成的一种僵局 xff08 互相等待 xff09 xff0c 若无外力作用 xff0c 这些进程都将无法推进 xff0c 这就是死锁现象 例如 xff1a

热门标签