操作系统死锁处理--09

操作系统死锁处理--09

• 如果信号量这样使用
• 死锁的成因
• 死锁的4个必要条件
• 死锁处理方法概述
• 死锁预防的方法例子
• 死锁避免: 判断此次请求是否引起死锁?
  • 找安全序列的银行家算法(Dijkstra提出)
  • 死锁避免之银行家算法实例
  • 请求出现时: 首先假装分配，然后调用银行家算法
• 死锁检测+恢复: 发现问题再处理
• 死锁忽略的引出

如果信号量这样使用

P代表消费资源,V代表产生资源

• 信号量的定义和初始化

//空闲的资源
semaphore full = 0; 
//生产者还能生产的资源数
semaphore empty = BUFFER_SIZE;
semaphore mutex = 1;

在这里插入图片描述

如果先调用P(mutex)再调用P(empty)和P(full)会有问题吗?

• 先来看看正常的流程是怎么个执行法的

在这里插入图片描述

• 如果先P(mutex)会怎样呢?

在这里插入图片描述

显然，生产者等待mutex锁的释放，而消费者却在等待生产者生产出来资源后,将自己唤醒.

我们将这种多个进程由于互相等待对方持有的 资源而造成的谁都无法执行的情况叫死锁

死锁的成因

在这里插入图片描述

各自占有的资源和互相申请的资源形成了环路等待

死锁的4个必要条件

• 互斥使用(Mutual exclusion)
  • 资源的固有特性，如道口
• 不可抢占(No preemption)
  • 资源只能自愿放弃，如车开走以后
• 请求和保持(Hold and wait)
  • 进程必须占有资源，再去申请
• 循环等待(Circular wait)
  • 在资源分配图中存在一个环路

死锁处理方法概述

在这里插入图片描述

死锁预防的方法例子

• 在进程执行前，一次性申请所有需要的资源，不会占有资源再去申 请其它资源

缺点1: 需要预知未来，编程困难 
缺点2: 许多资源分配后很长时间后才使用，资源利用率低

• 对资源类型进行排序，资源申请必须按 序进行，不会出现环路等待

缺点: 仍然造成资源浪费

死锁避免: 判断此次请求是否引起死锁?

如果系统中的所有进程存在一个可完成的执行序列P1，…Pn，则称 系统处于安全状态

安全序列: 上面的执行序列P1，…Pn。

如何找?

在这里插入图片描述

Allocation表示当前进程已经分配的资源，Need表示当前进程还需要多少资源，Available表示当前剩余资源。

p0—>p4是四个进程，如何安排四个进程的执行序列，能够确保四个进程都能顺利执行完毕，而不会因为互相抢占资源，导致死锁发生呢?

这里答案选A，我们来验证一下:

• P1先执行，他需要两个B，此时剩余资源满足条件，P1执行结束后，释放资源，此时剩余资源为:

A   B   C
5   3   2

• P3再执行,他需要一个B，此时剩余的资源数满足需求，P3执行完后，释放资源，此时剩余资源为:

A   B   C
7   6   3

后面同理，只要确保当前进程需要占用的资源数比剩余资源数多就行，这样当前进程拿到这些资源后，就可以顺序执行，执行完后释放掉自己占有的资源，这样剩余资源数会比一开始增加一些。然后再让需要占用更多资源数的进程去执行，以此往复即可。

找安全序列的银行家算法(Dijkstra提出)

在这里插入图片描述

把上面的推导过程写成算法，就是著名的银行家算法了。

核心在:

Need[i]<=Work---这里的Work就是Avaliable

如果剩余资源数多余当前需要的资源数，说明当前进程可以先执行。

我们可以利用银行家算法求出一个安全序列，但是银行家算法的复杂度比较高，因此系统代价大。

死锁避免之银行家算法实例

在这里插入图片描述

请求出现时: 首先假装分配，然后调用银行家算法

当有进程需要申请资源时，可以先调用银行家算法，计算是否会产生死锁，如果会的话，就阻止这次分配，

在这里插入图片描述

如上图所示: P0要申请(0,2,0)，但是会发现分配后，剩余资源数无法满足任意一个进程的需求，因此无法求出安全序列，所以需要拒绝此次资源分配请求。

死锁检测+恢复: 发现问题再处理

• 基本原因: 每次申请都执行O(mn2)，效率低。发现问题再处理

在这里插入图片描述

进程的回滚涉及很多方面，例如: 某个进程已经将部分数据写入磁盘了，此时你要回滚，这就很麻烦，还有很多其他的点需要考虑

在这里插入图片描述

死锁忽略的引出

在这里插入图片描述