【操作系统概念】 第7章:死锁

文章目录

  • 0.前言
  • 7.1 系统模型
  • 7.2 死锁特征
    • 7.2.1 必要条件
    • 7.2.2 资源分配图
  • 7.3 死锁处理方法
  • 7.4 死锁预防(deadlock prevention)
    • 7.4.1 互斥
    • 7.4.2 占有并等待
    • 7.4.3 非抢占
    • 7.4.4 循环等待
  • 7.5 死锁避免(deadlock-avoidance)
    • 7.5.1 安全状态
    • 7.5.2 资源分配图算法
    • 7.5.3 银行家算法
  • 7.6 死锁检测
    • 7.6.1 每种资源类型只有单个实例
    • 7.6.2 每种资源类型可有多个实例
    • 7.6.3 应用检测算法
  • 7.7 死锁恢复

0.前言

在多道程序环境中,多个进程可以竞争有限数量的资源。当一个进程申请资源时,如果这时没有可用资源,那么这个进程进入等待状态。又是,如果所申请资源被其他等待进程占有,那么该等待进程有可能再也无法改变状态。这种情况称为死锁(deadlock)
死锁最好的例证时Kansas立法机构在20世纪初通过的一项法律,其中说到 ”当两辆列车在十字路口逼近时,它们应完全停下来,并且在一列列车开走之前另一列列车不能再次启动”。

本章目标:

  1. 解释死锁,即一组并发进程不能完成执行任务。
  2. 提出一些方法,以便预防或避免计算机系统内的死锁。

7.1 系统模型

进程在使用资源之前必须先申请资源,在使用资源之后要释放资源。进程所申请的资源数量不能超过系统所有资源的总量。

某系统拥有一定数量的资源,分布在若干竞争进程之间。这些资源可以分成多种类型,每种类型有一定数量的实例。

在正常操作模式下,进程只能按如下顺序使用资源:

  1. 申请:如果申请不能立即被允许,那么申请进程必须等待,直到它获得该资源为止。
  2. 使用:进程对资源进行操作。
  3. 释放:进程释放资源

资源的申请与释放为系统调用。其他资源的申请与释放可以通过信号量的wait与signal操作或通过互斥锁的获取与释放来完成。因此对于进程和线程的每次使用,操作系统会检查以确保使用进程已经申请并获得了资源。

系统表记录了每个资源是否空闲或已被分配,分配给了哪个进程。如果进程正在申请的资源正在为其他进程所使用,那么该进程会增加到该资源的等待队列。

当一组进程的每个进程都在等待一个事件,而这个事件只能由这一组进程的另一个进程所引起,那么这组进程就处于死锁状态。

死锁也可设计不同的资源类型。多线程可能因为竞争共享资源而容易产生死锁。

7.2 死锁特征

当出现死锁时,进程永远不能完成,并且系统资源被阻碍使用,阻止了其他作业开始执行。

7.2.1 必要条件

如果在一个系统中下面四个条件同时满足,那么会引起死锁

  1. 互斥(mutual exclusion): 至少有一个资源必须处于非共享模式,即一次只有一个进程使用,如果另一个进程申请该资源,那么申请进程必须等到该资源被释放为止。

  2. 占有并等待(hold and wait): 一个进程必须占有至少一个资源,并等待另一资源,而该资源为其他进程所占有。

  3. 非抢占(no preemption): 资源不能被抢占,即资源只能在进程完成任务后自动释放。

  4. 循环等待(circular wait): 有一组等待进程{P0,P1,P2,P3…,Pn},P0等待的资源被P1等待,P1等待的资源被P2所占有,……,Pn−1等待的资源为Pn所占有,Pn所等待的资源被P0所占有。

4个条件必须同时满足才会出现死锁,循环等待条件意味着占有并等待条件,这样四个条件并不完全独立。

7.2.2 资源分配图

死锁问题可用称为系统资源分配图的有向图进行更为精确地描述。
这种图由一个节点集合V和一个边集合E组成。节点集合V可以分成两种类型的节点:
P={P1,P2,…,Pn}(系统活动进程的集合)
R={R1,R2,…,Rn}(系统所有资源的集合)
Pi→Rj :表示进程Pi已经申请了资源类型为Rj的一个实例,称为申请边
Rj→Pi : 表示资源类型Rj已经分配给进程Pi,称为分配边
在这里插入图片描述
可以证明:

  • 如果分配图没有环,那么系统就没有进程死锁。如果分配图有环,那么可能存在死锁。
  • 如果每个类型只有一个实例,环是死锁存在的充分必要条件。不过每个类型不止一个实例,环是死锁的必要条件。

存在死锁的资源分配图:
在这里插入图片描述
存在环但是没有死锁的资源分配图:
在这里插入图片描述

7.3 死锁处理方法

有三种方法:

  1. 可使用协议以预防或避免死锁,确保系统不会进入死锁状态。
  2. 可允许系统进入死锁状态,然后检测它,并加以修复
  3. 可忽略这个问题,认为死锁不可能在系统内发生。
    第三种方法为绝大多数操作系统所用,因此应用程序开发人员需要自己来处理死锁。

为了确保死锁不会发生,系统可以采用死锁预防或死锁避免方案:

  1. 死锁预防(deadlock prevention) 是一组方法,以确保至少一个必要条件不成立。这些方法通过限制如何申请资源的方法来预防死锁。

  2. 死锁避免(deadlock avoidance) 要求操作系统事先得到有关进程申请资源和使用资源的额外信息。有了这些额外信息,系统可以确定:对于一个申请,进程是否应等待。为了确定当前申请是允许还是延迟,系统必须考虑可用资源,已经分配给每个进程的资源,每个进程将来申请和释放的资源。

除此之外,系统还可以提供一个算法来检查系统状态来确定死锁是否发生,并提供另一个算法来从死锁中恢复。

预防死锁的副作用是降低设备的使用率和系统的吞吐率。

缺点是低设备使用率和系统吞吐率。

7.4 死锁预防(deadlock prevention)

出现死锁有四个必要条件,只要保证至少一个条件不成立,就能预防死锁的发生。

7.4.1 互斥

对于非共享资源,必须要有互斥条件(如打印机)。另一方面,共享资源不要求互斥访问,因此不会涉及死锁(如只读文件)。

故通常不能通过否定互斥条件来预防死锁,有的资源本身就是非共享的。

7.4.2 占有并等待

为了确保占有并等待条件不会在系统内出现,必须保证:当一个进程申请一个资源时,就不能占有其他资源。

  1. 方法一:可以通过要求申请资源的系统调用在所有其使用的协议是每个进程在执行前申请并获得所有资源。他系统调用之前进行。

  2. 方法二:允许进程在没有资源时才可申请资源,一个进程可申请一些资源并使用它们,然而,在它申请更多其他资源之前,它必须释放其现已分配的所有资源。

这两种协议有两个主要缺点:

  1. 第一,资源利用率(resource utilization)可能比较低,因为很多资源可能已分配,但长时间没有被使用。

  2. 第二,可能发生饥饿。一个进程如需要多个常用资源,可能会永久等待,比如因为其所需要的资源中至少一个总是分配给其他的进程。

7.4.3 非抢占

为确保这一条件不成立,可使用如下协议:

即可以抢占,如果一个进程占用资源并申请另一个不能立即分配的资源,那么其现已分配的资源都可被抢占,即这些资源被隐式地释放了。只有当进程获得其原有资源和所申请的新资源时,进程才可以重新执行。

或者说,如果一个进程申请一些资源,首先检查是否可用,如果可用就分配它们,如果不可用,那么检查这些资源是否已分配给其他等待额外资源的进程。如果是就抢占这些资源,并分配给申请进程。如果资源不可用且也不可被其他等待进程占有,那么申请进程必须等待。当一个进程处于等待时,如果其他进程申请其拥有的资源,那么该进程部分资源可以被抢占。一个进程要重新执行,他必须分配到其所申请的资源,并恢复其在等待时被抢占的资源。

这个协议通常用于状态可以保存和恢复的资源,如CPU寄存器和内存,一般不适用其他资源,如打印机和磁带驱动器。

7.4.4 循环等待

一个确保此条件不成立的方法是:对所有资源类型进行完全排序,且要求每个进程按递增顺序来申请资源。

设R={R1,R2,R3,…,Rn}为资源类型的的集合。为每个资源类型分配一个唯一整数来允许比较两个资源以确定其先后顺序。可定义一个函数F:R→N ,其中N是自然数集合,例如:F(tapedrive)=1 F(diskdrive)=5 F(printer)=12

每个进程只按照递增顺序申请资源,即一个进程开始可以申请任意数量的资源类型为Ri的实例。之后,当且仅当F(Rj)>F(Ri)时,该进程可以申请资源Rj的实例。如果需要同一资源类型的多个实例,那么对它们必须一起申请。

例如,对于以上给定函数,一个进程如果同时需要打印机和磁带驱动器,那么就必须先申请磁带驱动器,再申请打印机。换句话说,要求当一个进程申请资源类型Rj时,必须先释放所有Ri[F(Ri)>F(Rj)]

可以使用反证法证明,使用这两个协议,那么循环等待就不可能成立。

设计一个完全排序或层析并不能防止死锁,而是要靠应用程序员来按顺序编写程序。另外函数F应该根据系统内资源使用的正常顺序来定义。例如,由于磁带通常在打印机之前使用,所以定义F(tapedrive)<F(printer)较为合理。

7.5 死锁避免(deadlock-avoidance)

避免死锁的另外一种方法是获得以后如何申请资源的附加信息。

不同的算法所要求的信息量和信息的类型上有所不同,最为简单和最为常用的模型要求每个进程说明可能需要的每种资源类型实例的最大需求。根据每个进程可能申请的每种资源类型实例的最大需求的事先信息,可以构造一个算法以确保系统绝不会进入死锁状态。这种算法定义了死锁避免(deadlock-avoidance)方法。

死锁避免算法动态地检测资源分配状态以确保循环等待条件不可能成立。资源分配状态是由可用资源和已分配资源,以及进程最大需求所决定的。

7.5.1 安全状态

如果系统能按某个顺序为每个进程分配资源(不超过其最大值)并能避免死锁,那么系统状态就是安全的即如果存在一个安全序列,那么系统处于安全状态。如果没有这样的顺序存在,那么系统处于不安全状态。

进程顺序{P1,P2,…,Pn},如果对于每个Pi,Pi仍然可以申请的资源数小于当前可用资源加上所有进程Pj(其中j小于i)所占用资源,那么这一顺序称为安全序列。

在这种情况下,进程Pi所需要的资源即使不能立即使用,那么Pi等待直到所有Pj释放其资源,当它们完成时,Pi可得到其所需要的所有资源,完成其给定任务。

安全状态不是死锁状态,相反,死锁状态是不安全状态。然而,不是所有不安全状态都能够导致死锁状态。

只要状态为安全,操作系统就能避免不安全(和死锁)状态。在不安全情况下,操作系统不能阻止进程以会导致死锁的方式申请资源。进程行为控制了不安全状态。
在这里插入图片描述
有了安全状态的概念,可定义避免算法确保系统不会死锁,即确保系统处于安全状态,开始,系统处于安全状态,当进程申请一个可用资源时,系统必须确定这一资源申请是可以立即分配还是要等待,即便现在资源可用,也只有分配后系统仍处于安全状态,才允许申请。

也因此采用这种方法和没有采用死锁避免算法相比资源使用率可能更低。

7.5.2 资源分配图算法

利用资源分配图,引入需求边Pi→Rj
表示进程Pi可能在将来某个时候申请资源Rj。只有申请边变为分配边而不会导致资源分配图形成环时,才允许申请。

如果没有环存在,那么会使得系统处于安全状态,如果有环存在则分配会导致系统处于不安全状态。
在这里插入图片描述

7.5.3 银行家算法

银行家算法: 对于每种资源类型有多个实例的资源分配系统,资源分配图就不再适用。使用银行家算法,但是效率比资源分配图方案低。

当新进程进入系统时,它必须说明其可能需要的各种类型资源实例的最大数量,这一数量不能超过当前系统资源的总和。当用户申请一组资源时,系统必须确定这些资源的分配是否仍会使系统出于安全状态,如果是,就分配资源;否则,进程必须等待直到某个其他进程释放足够资源为止。

实现银行家算法,必须有几个数据结构:Available,Max,Allocation,Need。
这些数据结构对资源分配系统的状态进行了记录。设n为系统的进程的个数,m为资源类型的种类:
Available: 长度为m的向量,表示每种资源类型的现有实例的数量。如果Available[j] = k,则说明资源类型Rj有现有k个实例。
Max: n×m矩阵,定义每个进程的最大需求,如果Max[i][j] = k,那么进程Pi最多申请k个资源类型Rj的实例。
Allocation: n×m矩阵,定义每个进程现在所分配的各种资源类型的实例数量,例如Allocation[i][j] = k,那么进程Pi现在已经分配了k个资源类型Rj的实例。
Need: n×m矩阵,表示每个进程还需要的剩余的资源。如果Need[i][j] = k,那么进程Pi还需要申请k个资源类型Rj的实例。并且Need[i][j] = Max[i][j] - Allocation[i][j]
这些数据结构的大小和值会随着时间而改变。

为了简化银行家算法的描述:

设X,Y为长度为n的向量,那么X≤Y 当且仅当对所有的i=1,2,3…,n,X[i]≤Y[i],如果X≤Y 并且X!=Y,那么Y小于X。

可以将矩阵Allocation 和Need的每行作为向量,并分别用Allocationi 和Needi来表示。
向量Allocationi表示分配给进程Pi的资源,Needi表示进程Pi
为完成其任务可能仍然需要申请的额外资源。

  1. 安全性算法
    确定计算机是否处于安全状态需要以下几步:
    1. 创建Work 和 Finish 向量,长度分别为m,n,并且Work = Avallable,将Finish的每一项置为false
    2. 查找是否存在这样的i使得满足:
      Finish[i] = false
      Needi <= Work

如果不存在则跳到第四步。
Work = Work + Allocationi
Finish[i] = true
跳回第二步
如果对所有的i,Finish[i] = true,那么系统处于安全状态。
2. 资源请求算法
设Requesti为进程Pi的请求向量。即如果Requesti[j]==k ,那么Pi所需要资源类型Rj的实例数量为k。

当进程Pi做出资源申请时,采取如下动作:

  1. 如果Requesti<Needi,那么进行下一步,否则产生出错条件,因为已经超过了其最大请求。
  2. 如果Requesti<Available,那么进行下一步,否则Pi必须等待,因为没有可用的资源。
  3. 假定系统可以分配给进程Pi所需的资源,并按如下方式修改状态:
    Available=Available−Requesti
    Allocationi=Allocationi+Requesti
    Needi=Needi−Requesti

如果所产生的资源分配状态是安全的,那么交易完成且进程Pi可分配到其所需要的资源。

然而,如果新状态不安全,那么进程Pi必须等待Requesti并回复到原资源分配状态。

7.6 死锁检测

如果一个系统既不采用死锁预防算法也不采用死锁避免算法,那么死锁可能出现。在这种情况下,系统可以提供:

  1. 一个用来检查系统状态从而确定是否出现死锁的算法
  2. 一个用来从死锁状态恢复的算法

7.6.1 每种资源类型只有单个实例

如果所有资源类型只有单个实例,我们可以定义这样一个死锁检测算法,该算法使用了资源分配图的一个变形,称为等待图(wait-for)
在这里插入图片描述

7.6.2 每种资源类型可有多个实例

在这里插入图片描述

7.6.3 应用检测算法

在这里插入图片描述

7.7 死锁恢复

一种措施是通知操作员死锁已发生,以便操作人员人工处理死锁。

另一种措施是让系统从死锁状态中自动恢复过来。

打破死锁有两种方法:
一个方法是简单地终止或多个进程以打破循环等待。
另一个方法是从一个或多个死锁进程那里抢占一个或多个资源。

进程终止:

一是,终止所有死锁进程,这种方式虽然终止了死锁循环,代价太大。
二是,一次只终止一个进程直到取消死锁循环为止,这种方法的开销会很大,因为每次终止一个进程,就需要调用死锁检测算法以确定进程是否仍处于死锁。
资源抢占:

这里有三个问题需要处理:

①选择一个牺牲品:抢占哪些资源和哪个进程?必须确定抢占顺序以使代价最小化。

②回滚:如果从一个进程那里抢占一个资源,那么应对该进程做些什么安排?必须将这个进程回滚到某个安全状态,以便以后重启进程。

最简单的方法是完全回滚:终止进程并重新执行。更为有效的方法是将进程回滚到足够打破死锁。另一方面,这种方法要求系统维护有关运行进程状态的更多信息。

③饥饿:如何确保不会发生饥饿?最为常用的方法是在代价因素中加上回滚次数。

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

docker离线搭建仓库

要在Docker中搭建本地仓库&#xff0c;可以按照以下步骤进行操作&#xff1a; 首先安装 Docker。根据不同的操作系统选择合适的版本并完成安装过程。打开命令行工具&#xff08;如Terminal或PowerShell&#xff09;&#xff0c;运行以下命令来创建一个新的容器并将其设置为本地…

牛客网 华为机试 坐标移动

本题是需要将输入的字符串&#xff0c;得到移动位置的信息&#xff0c;同时要判断移动信息的合法性。 所以我们可以考虑先通过正则表达式过滤得到正确的字符串。 正确的字符串应该以ADWS其中一个字母开头&#xff0c;然后后面接着1个或者2个&#xff08;0-9&#xff09;的数字。…

如何在小程序中绑定身份证

在小程序中绑定身份证信息是一项常见的需求&#xff0c;特别是在需要进行实名认证或者身份验证的场景下。通过绑定身份证信息&#xff0c;可以提高用户身份的真实性和安全性&#xff0c;同时也为小程序提供了更多的个性化服务和功能。下面就介绍一下怎么在小程序中绑定居民身份…

LVGL在VScode中安装模拟器运行配置笔记教程

1、LVGL模拟器工程搭建 LVGL(Light and Versatile Graphics Library,轻巧而多功能的图形库)是一个免费的开放源代码图形库,它提供创建具有易于使用的图形元素,精美的视觉效果和低内存占用的嵌入式GUI所需的一切。本文主要讲述如何实现在VScode中实现LVGL模拟器环境的搭建运行。…

element组件使用教程

首先在终端输入 npm i element-ui -S 下载完成后如何使用呢 在main.js文件中导入组件以及需要使用 import Vue from vue import { Button, Form, FormItem, Input, Message, Container, Header, Aside, Main, Menu, Submenu, MenuItem, MenuItemGroup } from element-uiVue.…

如何学习、上手点云算法(三):用VsCode、Visual Studio来debug基于PCL、Open3D的代码

写在前面 本文内容 以PCL 1.14.0&#xff0c;Open3D0.14.1为例&#xff0c;对基于PCL、Open3D开发的代码进行源码debug&#xff1b; 如何学习、上手点云算法系列&#xff1a; 如何学习、上手点云算法(一)&#xff1a;点云基础 如何学习、上手点云算法(二)&#xff1a;点云处理相…

Java项目:41 springboot大学生入学审核系统的设计与实现010

作者主页&#xff1a;源码空间codegym 简介&#xff1a;Java领域优质创作者、Java项目、学习资料、技术互助 文中获取源码 项目介绍 本大学生入学审核系统管理员和学生。 管理员功能有个人中心&#xff0c;学生管理&#xff0c;学籍信息管理&#xff0c;入学办理管理等。 学…

WordPress建站入门教程:如何上传安装WordPress主题?

我们成功搭建WordPress网站后&#xff0c;默认使用的是自带的最新主题&#xff0c;但是这个是国外主题&#xff0c;可能会引用一些国外的资源文件&#xff0c;所以为了让我们的WordPress网站访问速度更快&#xff0c;强烈建议大家使用国产优秀的WordPress主题。 今天boke112百…

【C++】学习记录

一、第一个C程序 #include<iostream> using namespace std;int main() {cout << "Hello World!";return 0; } 二、数据类型、变量与常量、运算符 2.1 数据类型 2.2 变量与常量 2.3 运算符 三 、判断语句&#xff08;if-else、switch-case&#xff09; …

蓝桥杯物联网竞赛_STM32L071_11_知识体系的查漏与补缺

太久没学单片机了&#xff0c;再重新过一遍查漏补缺&#xff0c;对其中之前没怎么在意的&#xff0c;而现在又发觉的问题进行再分析与补充 1. debug serial wire是干什么用的 这个东西我勾选不勾选都对我的程序没有什么影响&#xff0c;我很好奇是干什么用的&#xff0c;网上查…

《Ubuntu20.04环境下的ROS进阶学习1》

一、vscode和超级终端Terminator 在上节我们已经逛了逛ROS官方应用商店和全球最大开源平台github。为了方便阅读代码和启动程序&#xff0c;本节我们来下载两个好用的app&#xff0c;当然是在Ubuntu上。 二、下载安装并运行vscode 1、下载vscode安装包 这里为了方便我们直接打…

职工医疗报销管理系统

目录 1 系统目标与范围说明... 0 1.1项目名称... 0 1.2问题说明... 0 1.3项目目标... 0 1.4项目范围... 0 1.5初步想法... 0 1.6可行性研究计划... 0 2 可行性分析报告... 1 2.1系统概述... 1 2.2可行性分析... 2 2.3结论意见... 2 3 项目开发计划... 2 3.1系统…

【电路笔记】-NPN晶体管

NPN晶体管 文章目录 NPN晶体管1、概述2、双极NPN晶体管配置3、NPN晶体管中的α和β关系4、示例5、共发射极配置1、概述 NPN 晶体管是三端三层器件,可用作放大器或电子开关。 在前面的文章中,我们看到标准双极晶体管或 BJT 有两种基本形式。 NPN(负-正-负)配置和PNP(正-负…

代码随想录 二叉树第四周

目录 617.合并二叉树 700.二叉搜索树中的搜索 98.验证二叉搜索树 530.二叉搜索树的最小绝对差 501.二叉搜索树中的众树 236.二叉树的最近公共祖先 617.合并二叉树 617. 合并二叉树 简单 给你两棵二叉树&#xff1a; root1 和 root2 。 想象一下&#xff0c;当你将其…

程序员未来发展之路-从入门到高手的成长轨迹

作为程序员&#xff0c;每个人的职业发展路径都是独特而富有挑战性的。从新手到专家&#xff0c;需要不断学习和实践&#xff0c;积累经验和技能。本文将带你探讨程序员职业发展的各个阶段以及关键要素&#xff0c;帮助你规划自己的职业发展之路。 一、新手阶段&#xff1a;夯…

fasta文件与fastq文件相互转化Python脚本

fa文件与fq文件互相转换 今天分享的内容是fasta文件与fastq文件的基本知识&#xff0c;以及通过Python实现两者互相转换的方法。 测序数据公司给的格式通常是fq.gz&#xff0c;也就是fastq文件&#xff0c;计算机的角度来说&#xff0c;生物的序列属于一种字符串&#xff0c;就…

2024/3/7—2575. 找出字符串的可整除数组

代码实现&#xff1a; int* divisibilityArray(char *word, int m, int *returnSize) {int n strlen(word);int *res (int*)malloc(sizeof(int) * n);long cur 0;for (int i 0; i < n; i) {cur (cur * 10 (word[i] - 0)) % m;res[i] (cur 0) ? 1 : 0;}*returnSize …

windows重装系统后如何恢复自带的正版office

前言 重装系统后&#xff0c;正版office如何安装 登录微软官网 https://www.microsoft.com 下载office&#xff0c;在已购买的产品中找到Office产品&#xff0c;点击安装,选择默认即可 https://account.microsoft.com/services

基于UDP实现直播间聊天的功能

需求&#xff1a;软件划分为用户客户端和主播服务端两个软件client.c和server.c 用户客户端负责&#xff1a;1.接收用户的昵称2.接收用户输入的信息&#xff0c;能够将信息发送给服务端3.接收服务端回复的数据信息,并完成显示主播服务端负责&#xff1a;1.对所有加入直播间的用…

pytorch(四、五)用pytorch实现线性回归和逻辑斯蒂回归(分类)

文章目录 线性回归代码过程准备数据设计模型设计构造函数与优化器训练过程训练代码和结果pytorch中的Linear层的底层原理&#xff08;个人喜欢&#xff0c;不用看&#xff09;普通矩阵乘法实现Linear层实现 回调机制 逻辑斯蒂回归模型损失函数代码和结果 线性回归 代码过程 训…