死锁

资源

排他性使用的对象

  • 可抢占资源
  • 不可抢占起源

1)请求资源 2)使用资源 3)释放资源

资源获取

可能产生死锁的编码

void fa(){
    down(r1);
    down(r2);
    up(r1);
    up(r2);
}

void fb(){
    down(r2);
    down(r1);
    up(r1);
    up(r2);
}

死锁简介

集合中的每一个进程都在等待只能由本集合中的其他进程才能引发的事件,那么该组进程是死锁的

  • 资源死锁的条件

    • 互斥:每个资源要么已经分配给了一个进程,要么就是可用的
    • 占有和等待:已经得到了某个资源的进程可以再请求新的资源
    • 不可抢占:已经分配给一个进程的资源不能强制性地被抢占,它只能被占有它的进程显式地释放
    • 环路等待:有两个或者两个以上的进程组成一条环路,该环路中的每个进程都在等待下一个进程所占有的资源

死锁建模

圆形表示进程,方形表示资源

屏幕截图 2020-08-06 103700

如果产生环路,则产生死锁

处理死锁的策略

  • 忽略问题
  • 检测并恢复
  • 仔细分配资源
  • 破坏引起死锁的四个必要条件

鸵鸟策略

解决死锁问题的代价很高,因此鸵鸟策略这种不采取任务措施的方案会获得更高的性能

死锁检测和死锁恢复

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

202032182320

方框代表资源,圆圈表示进程,资源指向进程表示该资源已经分配给该进程,进程指向资源表示进程请求获取该资源,这样当一个图中出现了环,就代表出现了死锁

可以通过检测有向图环路的算法,进行深度优先搜索,对访问过的节点进行标记,如果发现重复的节点,则代表出现了死锁

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

202032182611

基于向量检测

  • 从死锁中恢复

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

死锁避免

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

资源轨迹图

安全状态和不安全状态

20203218352

第二列 Has 表示已拥有的资源数,第三列 Max 表示总共需要的资源数,Free 表示还有可以使用的资源数 从图 a 开始出发,先让 B 拥有所需的所有资源(图 b),运行结束后释放 B,此时 Free 变为 5(图 c);接着以同样的方式运行 C 和 A,使得所有进程都能成功运行,因此可以称图 a 所示的状态时安全的 从安全状态出发,系统能保证所有进程都能完成

单个资源的银行家算法

多个资源的银行家算法

死锁预防

在程序运行之前避免发生死锁

  • 破坏互斥条件
    • 使资源可以同时被多个进程共享
  • 破坏占有和等待条件
    • 规定进程在开始执行前请求所需要的资源
  • 破坏不可抢占条件
    • 一个进程使用某个资源时,这个资源可以被其他需要的进程抢夺
  • 破坏环路等待
    • 给资源进行编号,规定资源的获取顺序
条件 处理方式
互斥 一切都使用假脱机技术
占有和等待 在开始就请求全部资源
不可抢占 抢占资源
环路等待 对资源按序编号

其他问题

  • 两阶段加锁
  • 通信死锁
  • 活锁
  • 饥饿

results matching " "

No results matching " "

results matching " "

No results matching " "