Geekerstar

计算机操作系统核心知识总结(三)死锁
目录计算机操作系统核心知识总结(一)概述计算机操作系统核心知识总结(二)进程管理计算机操作系统核心知识总结(三)死...
扫描右侧二维码阅读全文
02
2018/03

计算机操作系统核心知识总结(三)死锁

目录

计算机操作系统核心知识总结(一)概述

计算机操作系统核心知识总结(二)进程管理

计算机操作系统核心知识总结(三)死锁

计算机操作系统核心知识总结(四)存储器管理

计算机操作系统核心知识总结(五)设备管理


死锁的条件

u=895005534,600679372&fm=27&gp=0.jpg

  1. 互斥
  2. 请求与保持
  3. 不可抢占
  4. 环路等待

死锁的条件.jpg

其中,请求与保持是指一个进程因请求资源而阻塞时,对已获得的资源保持不放。

死锁的处理方法

1. 鸵鸟策略

把头埋在沙子里,假装根本没发生问题。

这种策略不可取。

2. 死锁预防

在程序运行之前预防发生死锁。

2.1 破坏互斥条件

例如假脱机打印机技术允许若干个进程同时输出,唯一真正请求物理打印机的进程是打印机守护进程。

2.2 破坏请求与保持条件

一种实现方式是规定所有进程在开始执行前请求所需要的全部资源。

2.3 破坏不可抢占条件

2.4 破坏环路等待

给资源统一编号,进程只能按编号顺序来请求资源。

3. 死锁避免

在程序运行时避免发生死锁。

3.1 安全状态

安全状态.jpg

图 a 的第二列 has 表示已拥有的资源数,第三列 max 表示总共需要的资源数,free 表示还有可以使用的资源数。从图 a 开始出发,先让 B 拥有所需的所有资源,运行结束后释放 B,此时 free 变为 4;接着以同样的方式运行 C 和 A,使得所有进程都能成功运行,因此可以称图 a 所示的状态时安全的。

定义:如果没有死锁发生,并且即使所有进程突然请求对资源的最大需求,也仍然存在某种调度次序能够使得每一个进程运行完毕,则称该状态是安全的。

3.2 单个资源的银行家算法

一个小城镇的银行家,他向一群客户分别承诺了一定的贷款额度,算法要做的是判断对请求的满足是否会进入不安全状态,如果是,就拒绝请求;否则予以分配。

单个资源的银行家算法

上图 c 为不安全状态,因此算法会拒绝之前的请求,从而避免进入图 c 中的状态。

3.3 多个资源的银行家算法

多个资源的银行家算法.jpg

上图中有五个进程,四个资源。左边的图表示已经分配的资源,右边的图表示还需要分配的资源。最右边的 E、P 以及 A 分别表示:总资源、已分配资源以及可用资源,注意这三个为向量,而不是具体数值,例如 A=(1020),表示 4 个资源分别还剩下 1/0/2/0。

检查一个状态是否安全的算法如下:

  • 查找右边的矩阵是否存在一行小于等于向量 A。如果不存在这样的行,那么系统将会发生死锁,状态是不安全的。
  • 假若找到这样一行,将该进程标记为终止,并将其已分配资源加到 A 中。
  • 重复以上两步,直到所有进程都标记为终止,则状态时安全的。

4. 死锁检测与死锁恢复

不试图阻止死锁,而是当检测到死锁发生时,采取措施进行恢复。

4.1 死锁检测算法

死锁检测的基本思想是,如果一个进程所请求的资源能够被满足,那么就让它执行,释放它拥有的所有资源,然后让其它能满足条件的进程执行。

死锁检测算法.jpg

上图中,有三个进程四个资源,每个数据代表的含义如下:

  • E 向量:资源总量
  • A 向量:资源剩余量
  • C 矩阵:每个进程所拥有的资源数量,每一行都代表一个进程拥有资源的数量
  • R 矩阵:每个进程请求的资源数量

进程 P1 和 P2 所请求的资源都得不到满足,只有进程 P3 可以,让 P3 执行,之后释放 P3 拥有的资源,此时 A = (2 2 2 0)。P1 可以执行,执行后释放 P1 拥有的资源,A = (4 2 2 2) ,P2 也可以执行。所有进程都可以顺利执行,没有死锁。

算法总结如下:

每个进程最开始时都不被标记,执行过程有可能被标记。当算法结束时,任何没有被标记的进程都是死锁进程。

  1. 寻找一个没有标记的进程 Pi,它所请求的资源小于等于 A。
  2. 如果找到了这样一个进程,那么将 C 矩阵的第 i 行向量加到 A 中,标记该进程,并转回 1。
  3. 如果有没有这样一个进程,算法终止。

4.2 死锁恢复

  • 利用抢占恢复
  • 杀死进程

上一章:计算机操作系统核心知识总结(二)进程管理
下一章:计算机操作系统核心知识总结(四)存储器管理


最后修改:2018 年 03 月 03 日 11 : 23 AM
如果觉得我的文章对你有用,请随意赞赏

发表评论