资源

资源:需要排他性使用的对象,硬件设备或者一组信息

可抢占资源和不可抢占资源

  • 可抢占:可以从拥有它的进程中抢占而不会产生副作用,比如存储器
  • 不可抢占:在不引起相关计算失败的情况下,无法把它从占有它的进程处抢占过来,如刻录机

死锁和不可抢占资源有关

  • 请求资源
  • 使用资源
  • 释放资源

请求资源不可用,请求进程将会被迫等待,或者阻塞

资源获取

数据库系统记录这种资源,应该由用户进程来管理使用。使用信号量或者互斥信号量,down和up操作。

死锁概述

如果一个进程集合中的每个进程都在等待只能由该进程集合中的其他进程才能引发的事件,那么,该进程集合就是死锁的。被称为资源死锁,因为进程数量以及占有或者请求的资源数量和种类都是无关紧要的。

资源死锁的条件

  • 互斥条件:每个资源要么已经分配给一个进程,要么就是可用的
  • 占有和等待条件:已经得到了某个资源的进程可以请求新的资源
  • 不可抢占条件:已经分配给一个进程的资源不能强制性的被抢占,只能由占有的进程显式释放
  • 环路等待条件:死锁发生的时候,一定有两个或者两个以上的进程组成环路

死锁发生的时候,上面四个条件一定是同时满足的。

死锁建模

需要做出不会引起死锁的资源分配决策,如果资源分配图出现环路,则有死锁。

处理死锁:

  • 忽略问题
  • 检测死锁并且恢复
  • 仔细对资源进行分配,动态避免死锁
  • 破环死锁四个必要条件,防止死锁的发生

鸵鸟算法

把头埋到沙子里,假装根本没有问题发生。这也是算法= =!

死锁检测和死锁恢复

每种类型一个资源的死锁检测

如果有了资源分配图,就可以通过检测有向图环路的方法来检测是否有环,即是否死锁。

就是将每个节点作为起始节点,然后进行深度优先搜索,如果再次碰到已经碰到的节点,就是找到了一个环。

参考: Golang 实现有向图

每种类型多个资源的死锁检测

使用基于矩阵的算法来检测死锁。

  • E表示现有资源向量,即资源总数
  • A表示可用资源向量,即剩余资源总数
  • C表示当前分配矩阵,即给进程分配的资源情况
  • R表示当前请求矩阵,即进程还需要的资源情况

算法:

  • 找到可以运行完的进程,即可以A剩余资源可以满足该进程请求的资源
  • 然后标记该进程并完成运行,继续找
  • 直到结束

最后没有标记的进程都是死锁进程

从死锁中恢复

  1. 利用抢占恢复
    • 临时将某个资源从它的当前所有者那里转移到另一个进程
  2. 利用回滚恢复
    • 周期性地对进程进行检查点检查,将进程的状态写入一个文件以备以后重启。
  3. 通过杀死进程恢复

死锁避免

资源轨迹图

避免死锁的主要算法是基于安全状态的概念。

非阴影部分才是安全的,阴影部分是不安全的,阴影部分是同时要占用某个资源。

安全状态和不安全状态

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

不安全状态并不是死锁,因为还有可能通过一些措施进入安全状态,比如某些进程释放了资源。两者的区别是,从安全状态出发,系统能够保证所有进程都能完成,从不安全状态出发,就没有这样的保证。

单个资源的银行家算法

当银行家的剩余空闲资源不足以满足任何一个人,让其先完成并且释放资源的时候就进入了不安全状态。那么银行家算法就要对每一个请求进行检查,检查如果满足这一请求是否会达到安全状态,如果可以,则满足,否则,推迟这一请求的满足。

多个资源的银行家算法

和上面多个资源的死锁检测差不多。

  • 查找R中矩阵,看是否有一行,其没有被满足的资源数均小于或者等于A,如果不存在,则死锁。
  • 如果存在,假设其获得资源并且结束,标记该进程,然后释放资源
  • 重复以上

如果所有进程都被标记,说明初始状态是安全的。

但是该算法缺乏使用价值,因为最大资源没法确定,进程数也没法确定。

死锁预防

破坏互斥条件

如果资源不被一个进程独占,那么死锁肯定不会发生。避免分配那些不是绝对必需的资源,尽量做到尽可能少的进程可以真正请求资源。假脱机技术。

破坏占有和等待条件

禁止已经持有资源的进程再等待其他资源即可消除死锁。

  • 规定所有进程在开始执行前请求所需要的全部资源。
  • 当一个进程请求资源的时候,先暂时释放其当前占用的所有资源,然后再尝试一次获得所需要的全部资源。

破坏不可抢占条件

一些资源可以通过虚拟化的方式来避免独占。比如打印机的假脱机打印机。

破坏环路等待条件

  • 保证每一个进程在任何时刻只能占用一个资源,要请求另一个资源,需要释放第一个资源。
  • 所有资源统一编号,请求时候必须按照资源编号升序提出。(如果没有更高序号的资源怎么办)