↓Skip to main content
A cup of beer
  1. Posts/

操作系统学习笔记-ch7

·255 words·2 mins
笔记
Table of Contents

死锁概念 #

死锁 #

  • 一组处于阻塞状态，并将永远处于阻塞状态的进程。
  • 该组进程中，每个进程都占有一定的资源，且等待其他进程占有的资源。造成了彼此无效占有资源的情况。
    • 如果某些进程发扬雷锋精神就好了。
  • 该组进程中，每一个进程都得等待对方继续执行，从而发出信号把自己唤醒。造成了彼此等待信号的情况。

饥饿和死锁的区别与联系 #

  • 饥饿和死锁都是无限等待。饥饿包括无限处于阻塞或无限处于就绪队列；死锁只包括无限处于阻塞。
  • 饥饿不一定死锁。饥饿包含死锁。因为死锁相比于饥饿还多一个条件，那就是相互等待。

死锁产生的两个先决条件 #

  • 有临界资源
  • 不当的执行顺序

死锁产生的四个必要条件 #

  • 互斥
    • 有临界资源。
  • 环状等待
    • 不当的执行顺序。
    • 设一个有向图，其节点是进程，边由等待方指向被等待方。那么这个图中存在环。
  • hold-and-wait
    • 哲学家拿着一只筷子等待另一只筷子。
  • 不剥夺
    • 进程只会主动让出资源。没有人发扬雷锋精神。
  • 注：如果资源是单实例资源，那么上述这些是充要条件。
    • 因为如果是多实例资源，且某些这种资源中的一些资源实例并不被这个死锁进程组中的任何一个进程占有，而是为其他不相干的进程占有，那么那些进程就存在主动释放资源的可能（因为这些其他进程并不在阻塞状态）。也就是说有不需要永久等待的可能。因为不会永久等待下去，自然不属于死锁。
    • 也就是，如果成环了，对于多实例资源的情况，存在死锁的可能性；对于单实例资源的情况，必然死锁。

逻辑设备 #

  • 在进程的视角，所有外部设备都属于逻辑设备。它可以向系统申请外部资源。但是它不能指定具体要哪个资源实例，因为进程也不知道具体有哪些资源实例，因为它被OS封装了。
  • 具体把哪个资源实例分配给你，那是OS该干的事情。
  • 就好比双十一淘宝的服务器集群，你只知道输入 taobao.com，但是你不能主动指定要访问其背后的哪个服务器。实际上是分布式OS给你分配了一个服务器实例。这不能由你决定。

RAG,Resource-Allocation-Graph图 #

  • 分配边：从多实例资源的具体实例或单实例资源指向进程节点。
  • 申请边：从进程节点指向多实例资源或单实例资源，无具体实例可分。

LUT,Logic-U-Table逻辑设备表 #

  • 系统把物理设备通过LUT映射为逻辑设备。
  • 能实现统一当作文件进行IO的方式。
  • 设备分配更加灵活。从硬件变成了软件。

死锁避免情况4:避免环状等待 #

  • 情况1、2、3略。见课件。
  • 给系统中的资源编号。进程可以在任意时刻提出资源申请，但是只允许申请比当前此进程占用的资源编号更大的资源。即必须以编号递增的方式提出资源申请。
    • 如果当前此进程占用了编号较大的资源，但是其想申请编号比他小的资源，那就需要先对那个大编号资源予以释放。
  • 例：哲学家就餐
    • 如果顺时针给资源（筷子）编号，那么每个哲学家只能先申请左手边筷子，再申请右手边筷子。
    • 对于顺时针的最后一个哲学家，其左边是7号筷子，右边是0号筷子，那么他是先申请右手边筷子，再申请左手边筷子。
  • 缺点
    • hard-coded。难以增加或删除设备。
    • 例如内存地址空间就没法这么编号：它太多了。
    • 程序员编程带来很多麻烦。

预防死锁问题的正向思维和逆向思维 #

  • 正向：避免产生四个必要条件
  • 逆向：设法打破四个条件

为什么进程不会等待CPU、memory等这类资源而进入死锁？ #

  • 因为它们不满足“不剥夺”。

不死锁不等式：n(x-1)+1≤m #

  • 系统中有n个进程，每个进程最多申请x个资源，系统中共有m个资源。
  • 只要满足上述不等式，就不会死锁。
  • 原因：n(x-1)指出了让每个进程都互相进入等待的数量条件。如果此时没有其他资源了，那么就死锁了。因为大家都差一个。注意，这种分配的情况也是在这种特定的不合理的执行顺序下才会出现的。
  • +1的意思是存在另一个资源，它能让其中一个阻塞进程获得资源并解放，释放其全部资源。其他进程也就跟着解放了。

safe sequence、safe state和unsafe state #

  • safe sequence即一个能使得当前各个进程在其所需资源、系统剩余可用资源条件下继续执行的拓扑序列。该拓扑序列的每个节点的意思都是“此进程完全执行完毕并释放所有资源”。因此拓扑序列得已正常进行的原理就是，每走一步，就有新的资源补充进来。
  • safe state是能找出safe sequence的程序执行状态。
  • unsafe state就是找不出safe sequence的情况了。也就是不存在一种执行顺序，能够使这组进程不进入死锁。
    • 换言之，unsafe state虽然像safe state一样，当前都不处于死锁状态，但是unsafe state继续执行若干步骤，必然会直接陷入死锁。因为它不存在能不死锁的执行顺序。
    • 就像射雕英雄传里面，你就在悬崖边上，一只脚在空中。这样就是unsafe state，但是还没dead。但是你再走一步就dead了。
  • safe state可向unsafe state转化，因为进程的执行是动态的。如果在safe state按其safe sequence执行，那么不会进入unsafe state。否则就有进入unsafe state的可能性。就好比你走错了路，往悬崖边走。
  • safe state和unsafe state无交集；unsafe state包含dead lock。

死锁避免的本质 #

  • 避免程序向unsafe state转化。
  • 当给进程分配资源，应当考虑本次分配是否会将程序置于unsafe state。
    • 因此，提出“假分配”的概念。即假设如果分配了，看一看RAG图是否出现成环的现象。
    • 摸着石头过河。如果假分配不会出现unsafe state，那么就进行同样的真分配。

死锁避免算法 #

  • 对于单实例资源，使用带Claim的RAG图判断；对于多实例资源，使用银行家算法。

带Claim的RAG图算法 #

  • 在原有RAG图的基础上，加上一种新边，即Claim边。
    • Claim边用虚线箭头表示，Request边和Assignment边用实线箭头表示。它们之间可以混搭构成环。（即环的构成是无视边的类型的。）
    • 由于该算法是单实例下的算法，所以边一定都是从资源指入或指出。不存在和其中的实例交互的情况，因为一个资源只有一个实例。
  • 关于三种边和在该算法下的互相转化
    • 当进程被装入内存开始执行：
      • Claim边在进程开始运行时就全部显示在图上了。
      • 表示该进程在执行的全过程中可能会进行申请的资源情况（但是现在还没提出request）
    • 当进程提出某一资源的申请：
      • OS把这个Claim边变成Request边，也就是虚线变实线；
    • 当进行假分配：
      • 先进行资源可用性检查：如果申请的资源被占用，那么OS让这个申请进程阻塞，否则进入下一步：
      • 再看假分配是否出现环：先把Request边换成Assignment边，也就是反向；
        • 如果出现环（可以由各种类型的边混搭而成），那么系统进入unsafe state，把Assignment边恢复成Claim边；（也就是驳回Request，不让他申请，以防止其进入阻塞。（因为一旦进入阻塞就有死锁的可能，而Request边一旦出现就说明它正在阻塞等待资源。））
        • 如果没有环，那就真分配了。那个边保持Assignment边不变。
    • 当资源被释放：
      • 把Assignment边换成Claim边。

当系统处于安全状态时，系统中一定无死锁进程. #

  • 因为在safe state下，不存在阻塞的进程，因此必然不存在死锁的进程。

银行家算法数据结构 #

全局数据结构（用于表示系统状态和假分配） #

假设当前有N个进程和M种多实例资源：

  • Need[N][M] 可以类比RAG算法中，第N个进程对每个资源类型目前还有多少条Claim边。
    • 如果适配到RAG算法中，这是一个0-1矩阵。
    • 由于银行家算法适用于多实例资源情况，所以这个矩阵非0-1。
    • 由N个M维行向量构成。每个行向量代表该资源向这M个多实例资源分别伸出的Claim边数量。
  • MAX[N][M]
    • 矩阵形式和Need相同，只不过其意义不是当前的Claim边的情况，而是进程刚装入时Claim边的情况。
    • 因为它描述了最多需要Claim多少。
  • Allocation[N][M]
    • 矩阵形式和Need相同，只不过其意义是当前Assignment边的情况。
    • 关系：MAX-Allocation=Need.
  • Avaliable[M]
    • 是一个M维向量，每一维度表示第M种多实例资源目前的剩余可用实例数。
局部数据结构（用于Safety Check算法） #
  • Finish[N]
    • 是一个N维Boolean向量，每一维度表示第N个进程是否执行完毕并释放资源。
  • Work[M]
    • 是一个M维向量，每一维度表示第M种多实例资源目前的剩余可用实例数（在Safety Check推演过程中）。
    • 和Avaliable[M]的区别是：Work[M]所表示的是推演出来的数据，并不是真实发生的。因为它只是在推演一种可能的Safe Sequence，以进行安全检查，查看如果这样假分配，是否会处于安全状态。

银行家算法流程 #

假设当前第i个进程提出了申请，其申请向量是Request[M].

  • 合法性检查：检查向量 Request中是否有某一维度大于行向量 Need[i] 中的对应维度。如果存在，那么报错（即不让其等待，而是直接驳回）。
    • 因为你申请了超过所需的资源，出现浪费。
  • 可用性检查：检查向量 Request中是否有某一维度大于行向量 Avaliable[i] 中的对应维度。如果存在，那么让该进程进入等待。
    • 因为当前不可用，需等待。
    • State:Pending. Reason:Resources.
  • 假分配：根据向量Request来重新设置行向量 Need[i]、Avaliable、Allocation[i] 的值，构成一个如果分配了，出现的假想的系统状态。
  • 运行安全检查算法：根据假分配的系统状态进行推演，看在这种状态下，是否存在一个Safe Sequence，能让大家正常执行结束而不陷入死锁。
    • 如果是安全状态，就允许该请求；
    • 否则让进程进入等待。

银行家算法的安全检查算法 #

该算法的意义 #
  • 根据假分配的系统状态进行推演，看在这种状态下，是否存在一个Safe Sequence，能让大家正常执行结束而不陷入死锁。即假分配后，是否是一个安全状态。因为根据之前的定义，存在Safe Sequence的状态就是安全状态。
  • 这是在为分配后的情况进行考虑。即“走一步，看百步”。
  • 只要保证每次分配后，都是安全状态，那么系统就能一直处于安全状态。于是大家都能执行完成且不死锁。
算法流程 #
  1. 先初始化Work[M]为Avaliable[M]。表示在初始状态下，可用的资源就是这么多。初始化Finish[N]都为false。表示初始状态下，大家都还没有完成执行。
  2. 查看当前是否存在这样的i，满足 Finish [i]==false(未执行完成)且 Need[i]<=Work(可以分配给他资源)。如果当前还存在这样的i，进入3；否则进入4.
  3. Work = Work + Allocation[i], Finish[i] = true(分配资源，让他完成并释放资源)
  4. 检查对于所有i，Finish [i]==true。如果成立，那么存在Safe Sequence，当前处于安全状态；否则不存在Safe Sequence，当前不是安全状态。

死锁检测算法 #

  • 死锁检测算法包括wait-for图法和Detection算法。前者用于单实例资源，后者用于多实例资源情况。
  • 死锁检测算法中不存在Claim的概念，因为我们没有先验知识。
    • 与死锁避免不同的是，我们没有Claim这个先验知识！

Wait-for图法 #

  • 把RAG图（因为没有Claim先验知识，所以其中只有Request和Assignment两种边）中的资源节点都省略，纳入边中，就变成了wait-for图。
    • 这样做没有问题，因为每个资源节点都只有一个实例，不会产生二义性。
  • wait-for图中的边的含义：例如由A指向B，那就是A在等待B。
  • 如果存在环，那么说明死锁了。
  • **算法的思想就是定期对wait-for图进行环路检测。**如果存在环，那么就探测到了死锁。

Detection算法 #

  • 类似于银行家算法，假设有N个进程和M种多实例资源，则定义数据结构Allocation[N][M]、Avaliable[M]、Finish[N]、Work[M]。
    • 但是，我们由于没有Claim先验知识，所以Need[N][M] 和MAX[N][M] 不再适用。因为它们都是基于Claim的。
    • 我们只是对当前的状态进行检测，所以只有Request[N][M] 是知道的。在算法中，Request[N][M] 可以起到代替Need[N][M] 的效果，只不过一共是后验一个是先验。
      • 银行家中，表格的三列分别是Allocation、Need和Available。在Detection算法中，自然变成了Allocation、Request和Available。
      • Need是根据Max-Allocation算出的，是还未发生的，即这个申请仍然没有提出；但是这里Request是已经发生的，是已经提出了申请。因此前者没有进入阻塞，但是后者进入了阻塞。
  • 如果某一行向量Request[i]为零向量，那么这第i个进程可以说是finish了，因此finish[i]=true。Detection算法根据这个思想去判断哪些进程finish了，并释放资源去满足其他的request。
  • 如果到最后还存在一些没有finish的进程，那么它们互相等待了。（因为它们都不能把已经占用的资源拿出来供其他进程继续执行，且它们由于request向量非零，在阻塞状态呢。）
    • 因此，最后如果还存在一组finish==false的进程，那么这些进程就是阻塞进程组，且它们互相等待。

解题步骤 #

  • 如果题目给出了RAG图，让你判断是否阻塞
    • 对于单实例资源的情况，转化为Wait-for图，判环；
    • 对于多实例资源的情况，转化为Detection算法思想，列出其表格（由Allocation、Request和Available列构成的表格），跑一遍。

死锁检测和死锁避免的区别 #

  • 后者Need、Max这种基于先验Claim的方法；前者只有后验Request可用。
  • 前者是判断当前是否已经出现死锁；后者是根据先验去判断是否要满足本次资源请求，以避免死锁可能性。
    • 前者是资源已经分配出去了，申请已经是提出来了，且没能满足申请的进程已经阻塞了。
    • 后者是资源还没分配，正在运行算法决定是否分配。当前系统正在处于安全状态，不存在因资源分配的阻塞。
  • 采用前者，那就是有资源就立马分配，没资源就等待，出问题再说；采用后者，那就是申请超额直接回绝，如果没有资源**或可能导致死锁（进入unsafe state）**就等待，没问题就分配。
  • 前者用于批处理等系统，例如实验室的slurm；后者用于分时系统。
↑