现代操作系统：第六章死锁

谁借莪１个温暖的怀抱￠ 2022-04-17 03:22 306阅读 0赞

在计算机系统中有很多独占性的资源，在任意时刻中都只能被一个进程所占有。

# 6.1 资源 #

在进程对设备、文件等取得了排他性访问权的时候，有可能会产生死锁。为了尽可能使关于死锁的讨论通用，我们把这类需要排他性使用的对象称为**资源**。

## 6.1.1 可抢占性资源和不可抢占性资源 ##

*  可抢占性资源：可以从拥有它的进程中抢占而不产生任何副作用，存储器就是一种可抢占性的资源。
 *  不可抢占性资源：不引起相关的计算失败的情况下，无法从占有它的进程中抢占过来，这种资源就称为不可抢占性资源。

使用一个资源所需要的事件顺序可以用抽象的形式表现出来：

1.  请求资源。
2.  使用资源。
3.  释放资源。

## 6.1.2 资源获取 ##

一种允许用户管理资源的方法就是为每一个资源配置一个信号量。这个信号量初始化为1。互斥信号量也能起到相同的作用。上述的三个步骤可以实现为信号量的down操作来获取资源、使用资源、最后使用up操作来释放资源。

# 6.2 死锁定义 #

如果一个进程集合中的每个进程都在等待只能由该进程集合中的其他进程才能引发的事件，那么该进程集合就是死锁的。

细节解释：在大多数情况下，每个进程所等待的时间是释放进程集合中其他进程所占有的资源。换言之，这一个死锁进程集合中的每一个进程都在等待另一个死锁进程已经占有的资源。但是由于所有进程都不能运行，他们中的任何一个进程都无法释放资源，所以没有一个进程可以被唤醒。这种死锁称为资源死锁。

## 6.2.1 死锁发生的条件 ##

1） 互斥条件：每个资源要么已经分配给了一个进程，要么就是可用的

2） 占有和等待条件：已经得到了某个资源的进程可以再请求新的资源，如果该资源被其他进程占有，则当前进程进入等待状态

3） 不可抢占条件：已经分配的资源不能被抢占，只能由占有它的进程显式释放

4） 环路等待条件：系统中有两个或两个以上进程形成环路，环路中每个进程都在等待下一个进程所占有的资源

# 6.2.2 死锁建模 #

Holt指出如何用有向图建立上述四个条件的模型。在有向图中有两类节点：用圆形表示的进程，用方形表示的资源。从资源节点到进程节点的有向边代表该资源已被请求，授权并被进程所占用。从进程节点到资源节点的有向边表示当前进程正在请求资源，并且该进程已经被阻塞，处于等待该资源的状态。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMTI1MTgz_size_16_color_FFFFFF_t_70]

总而言之，有四种处理死锁的策略：

1） 忽略该问题（鸵鸟算法）

2） 检测死锁并恢复

3） 仔细对资源进行分配，动态地避免死锁

4） 通过破坏引起死锁的四个必要条件之一，防止死锁发生

# 6.3 鸵鸟算法 #

忽略该问题（鸵鸟算法）

# 6.4 死锁检查并恢复 #

系统并不试图到死锁产生，而是允许死锁发送，当检测到死锁后，采取措施进行恢复。

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

建模检测是否有环

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

当前分配矩阵C，请求矩阵R

步骤：

（1）寻找一个没有标记的进程Pi，对它而言R矩阵的第i行向量小于等于A。

（2）如果找到了这样一个进程，那么将C矩阵的第i行向量加到A中，标记该进程，并转到第一步。

（3）如果没找到，算法终止。

如果算法结束，存在没有标记的进程，则为死锁进程。

## 6.4.3 从死锁中恢复 ##

### 1.利用抢占恢复（要求资源本身允许抢占） ###

在某些情况下，可能会临时将某个资源从它的当前所有者那里转移给另一个进程。许多情况下，尤其对于运行在大型主机上的批处理操作系统来说，需要进行人工干预。

### 2.利用回滚恢复（将状态写入文件以备重启） ###

一旦检测到死锁，就很容易发现需要哪些资源。为了进行恢复，要从一个较早的检查点开始，这样所拥有的所需要资源的进程会回滚到一个时间点。实际上，是将该进程回滚一个更早的状态，那时它还没有取得所需要的资源，接着就把这个资源分配给另一个死锁进程。如果复位后的进程试图重新获取对该资源的控制，它就必须等待该资源可用为止。

### 3.通过杀死进程恢复（数据库可能不允许这样） ###

最直接也是最简单的解决死锁的方法是杀死一个或者若干个进程。一种方法是杀掉环中的一个进程。如果走运的话，其他进程将也可以继续。如果这样行不通的话，就需要继续杀死别的进程知道打破死锁破坏。

# 6.5 死锁避免 #

安全状态和不安全状态的区别：从安全状态出发，系统能够保证所有进程都能完成， 而不安全状态则没有这样的保证

不安全状态不是死锁，死锁意味着进程进程都锁死不能执行，而不安全状态则可以运行一段时间。

不安全状态不一定会引起死锁，但是不安全状态可能会导致死锁。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMTI1MTgz_size_16_color_FFFFFF_t_70 1]

银行家算法

# 6.6 死锁预防 #

## 6.6.1 破坏互斥条件 ##

如果资源不被一个进程所独占，那么死锁肯定不会发生。当然，允许两个进程同时使用打印机会造成混乱，通过采用假脱机技术可以运行若干个进程同时占有资源。

## 6.6.2 破坏占有并等待资源 ##

只要禁止已经持有资源的进程再等待其他资源就可以消除死锁。一种实现方法就是规定所有进程再开始执行前请求所需要的全部资源。如果所需要的全部资源可用，那么久将他分配给这个进程，于是该进程肯定能运行结束。如果有一个或者多个资源正在被使用，那么就不进行分配，进程等待。

## 6.6.3 破坏不可抢占条件 ##

通过虚拟化方式进行抢占，并只允许假脱机打印机向磁盘输出，并只允许守护进程访问真正的物理打印机。

## 6.6.4 破坏环路等待条件 ##

消除环路等待条件有几种方法：

*  保证每一进程都只能在任何时刻都只能还在纳雍一个进程，如果要请求其他另外一个资源，它必须释放第一个资源。
 *  将所有资源进行编号。现在的规则是：进程可以在任何时刻提出资源请求，但是所有请求必须按照资源编号的顺序(升序)提出。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMTI1MTgz_size_16_color_FFFFFF_t_70 2]

# 6.7 其他问题 #

## 6.7.1 两阶段锁 ##

在数据库系统中，一个经常发生的操作就是请求锁住一些记录，然后更新所有锁住的记录。

第一阶段：试图对所有所需记录加锁，如某个进程已被加锁，释放该进程的所有加锁记录，重新开始第一阶段。

第二阶段：第一阶段加锁成功后，完成更新然后释放锁。

该算法只适用于程序员可以安排程序停下和重新开始而不会产生错误的情况（如数据库系统）。

## 6.7.2 通信死锁 ##

在一系列进程中，每个进程因为等待另外一个进程引发的事件而产生阻塞，可采用超时机制解决。

在大多数网络通信系统中，只要有一个消息被发送到一个特定的地方，并等待其返回一个预期的回复，发送者就同时启动计时器。若计时器在回复到达前计时就停止了，则消息的发送者可以认定消息已经丢失，并重新发送。

## 6.7.3 活锁 ##

没有阻塞但也没有进展。通过轮询代替阻塞，只是没有阻塞而已。

## 6.7.4 饥饿 ##

进程无限制地推后，得不到执行，可采用先来先服务资源分配策略避免。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMTI1MTgz_size_16_color_FFFFFF_t_70]: /images/20220417/7305ac4bd5644299837a0b9029fc4f3e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMTI1MTgz_size_16_color_FFFFFF_t_70 1]: /images/20220417/5c97f3550cce4bb0ba092bc08b80e0fe.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMTI1MTgz_size_16_color_FFFFFF_t_70 2]: /images/20220417/4f94fdcef84d4de080c4986c19678056.png