文章目录

• 前言
• 一、预防死锁
• • 知识总览
  • 破坏互斥条件
  • 破坏不剥夺条件
  • 破坏请求和保持条件
  • 破坏循环等待条件
  • 知识回顾与重要考点
• 二、避免死锁
• • 知识总览
  • 什么是安全序列
  • 安全序列、不安全状态、死锁的联系
  • 银行家算法
  • 找得到安全序列（安全状态）
  • 快速找到安全序列
  • 找不到安全序列（不安全状态、可能死锁）
  • 代码表示
  • 知识回顾与重要考点
• 三、死锁的检测和解除
• • 知识总览
  • 死锁的检测
  • 死锁的解除
  • 知识回顾与重要考点

前言

此篇文章是我在B站学习时所做的笔记，大部分图片都是课件老师的PPT，方便复习用。此篇文章仅供学习参考。

---

提示：以下是本篇文章正文内容

一、预防死锁

知识总览

知识回顾：死锁的产生必须满足四个必要条件，只要其中一个或者几个条件不满足，死锁就不会发生。

破坏互斥条件

• 互斥条件：只有对必须互斥使用的资源的争抢才会导致死锁。
• 如果把只能互斥使用的资源改造为允许共享使用，则系统不会进入死锁状态。比如：SPOOLing技术。操作系统可以采用SPOOLing 技术把独占设备在逻辑上改造成共享设备。比如，用SPOOLing技术将打印机改造为共享设备…
  
  该策略的缺点：并不是所有的资源都可以改造成可共享使用的资源。并且为了系统安全，很多地方还必须保护这种互斥性。因此，很多时候都无法破坏互斥条件。

破坏不剥夺条件

破坏请求和保持条件

破坏循环等待条件

知识回顾与重要考点

二、避免死锁

知识总览

什么是安全序列

安全序列、不安全状态、死锁的联系

• 所谓安全序列，就是指如果系统按照这种序列分配资源，则每个进程都能顺利完成。只要能找出一个安全序列，系统就是安全状态。当然，安全序列可能有多个。
• 如果分配了资源之后，系统中找不出任何一个安全序列，系统就进入了不安全状态。这就意味着之后可能所有进程都无法顺利的执行下去。当然，如果有进程提前归还了一些资源，那系统也有可能重新回到安全状态，不过我们在分配资源之前总是要考虑到最坏的情况。

考点： 如果系统处于安全状态，就一定不会发生死锁。如果系统进入不安全状态（找不到任何一个安全序列），就可能发生死锁（如左边案例不提出BAT请求时暂时不会发生死锁）（处于不安全状态未必就是发生了死锁，但发生死锁时一定是在不安全状态)

因此可以在资源分配之前预先判断这次分配是否会导致系统进入不安全状态，以此决定是否答应资源分配请求。这也是“银行家算法”的核心思想。

银行家算法

银行家算法是荷兰学者Dijkstra为银行系统设计的，以确保银行在发放现金贷款时，不会发生不能满足所有客户需要的情况。后来该算法被用在操作系统中，用于避免死锁。
核心思想：在进程提出资源申请时，先预判此次分配是否会导致系统进入不安全状态。如果会进入不安全状态，就暂时不答应这次请求，让该进程先阻塞等待。

找得到安全序列（安全状态）

即使用剩余可用资源（3，3，2）与最多还需要的资源进行对比
（7，4，3）>(3，3，2)发现剩下的资源满足不了P0的最大需求
（1，2，2）<(3，3，2)可满足P1需求，将P1加入安全序列，并更新剩余可用资源值为(5,3,2)

快速找到安全序列

找不到安全序列（不安全状态、可能死锁）

要(8,4,3)、(6,5,0)和(4,3,4)中的括号里每个值都小于（7,4,3）才算满足

代码表示

知识回顾与重要考点

• 数据结构：
  ①长度为m的一维数组Available表示还有多少可用资源n*m矩阵Max表示各进程对资源的最大需求数
  ②n *m矩阵Allocation表示已经给各进程分配了多少资源
  ③Max- Allocation = Need矩阵表示各进程最多还需要多少资源
  ④用长度为m的一位数组Request表示进程此次申请的各种资源数
• 银行家算法步骤:
  ①检查此次申请是否超过了之前声明的最大需求数
  ②检查此时系统剩余的可用资源是否还能满足这次请求
  ③试探着分配，更改各数据结构
  ④用安全性算法检查此次分配是否会导致系统进入不安全状态
• 安全性算法步骤:
  ①检查当前的剩余可用资源是否能满足某个进程的最大需求，如果可以，就把该进程加入安全序列，并把该进程持有的资源全部回收。
  ②不断重复上述过程，看最终是否能让所有进程都加入安全序列。入
• 系统处于不安全状态未必死锁，但死锁时一定处于不安全状态。系统处于安全状态一定不会死锁。

三、死锁的检测和解除

知识总览

如果系统中既不采取预防死锁的措施，也不采取避免死锁的措施，系统就很可能发生死锁。在这种情况下，系统应当提供两个算法:
①死锁检测算法：用于检测系统状态，以确定系统中是否发生了死锁。
②死锁解除算法：当认定系统中已经发生了死锁，利用该算法可将系统从死锁状态中解脱出来。

死锁的检测

为了能对系统是否已发生了死锁进行检测，必须：
①用某种数据结构来保存资源的请求和分配信息;
②提供一种算法，利用上述信息来检测系统是否已进入死锁状态。

• 如果系统中剩余的可用资源数足够满足进程的需求，那么这个进程暂时是不会阻塞的，可以顺利地执行下去。
• 如果这个进程执行结束了把资源归还系统，就可能使某些正在等待资源的进程被激活，并顺利地执行下去。
• 相应的，这些被激活的进程执行完了之后又会归还一些资源，这样可能又会激活另外一些阻塞的进程。

如果按上述过程分析，最终能消除所有边，就称这个图是可完全简化的。此时一定没有发生死锁（相当于能找到一个安全序列)

如果最终不能消除所有边，那么此时就是发生了死锁

解说：
用刚才的方法来分析，P1进程此时请求两个R2资源，而R2资源已经全部分配出去了，没有空闲了，所以P1进程应该被阻塞，而P2进程此时请求R1资源，而R1资源也全部分为出去了，也没有空闲的，所以P2进程也需要被阻塞，此时可以顺利执行下去的只有P3进程，那么当P3执行结束之后，会归还它所拥有的全部资源（意思是口语划掉与P3相连的所有边），接下来R2资源已经有一个空闲（P3归还的），但是由于P1进程需要的是两个R2资源，所以此时R2这种资源的数量依然不够满足P1的需求，所以P1依然会被阻塞。P2进程也一样，此时没有空闲的R1资源，所以P2进程也会继续阻塞，所以我们就不能像刚才那样，把P1,P2相连的这些边给干掉，那么到这一步为止，我们就不能继续化简下去了，所以这种情况就是不能消除所有边的情况，那这种情况下系统就发生了死锁。大家可以结合这个图来分析一下此时是否满足此所发生的四个必要条件，四个必要条件，分别又是什么呢？

最终还连着边的那些进程就是处于死锁状态的进程。
即只有P3不是死锁状态的进程，P1和P2都是死锁状态的进程。

检测死锁的算法：
1）在资源分配图中，找出既不阻塞又不是孤点的进程Pi(即找出一条有向边与它相连，且该有向边对应资源的申请数量小于等于系统中已有空闲资源数量。如下图中，R1没有空闲资源，R2有一个空闲资源。若所有的连接该进程的边均满足上述条件，则这个进程能继续运行直至完成，然后释放它所占有的所有资源)。消去它所有的请求边和分配变，使之称为孤立的结点。在下图中，P1是满足这一条件的进程结点，于是将P1的所有边消去。
2）进程Pi所释放的资源，可以唤醒某些因等待这些资源而阻塞的进程，原来的阻塞进程可能变为非阻塞进程。在下图中，P2就满足这样的条件。根据1）中的方法进行一系列简化后,
若能消去途中所有的边，则称该图是可完全简化的。

解说：
不阻塞的意思是说，这个进程申请的这些资源的数量足够满足他的需求，比如说像P1进程就是不阻塞的进程，而P2进程申请的R1资源已经没有足够的剩余资源可以分配给它了，所以P2进程是一个阻塞的进程。另外，不是孤点这个条件指的是与这个进程至少有一个边相连，那么P1和P2显然都不是孤点，所以在这个状态下，满足既不阻塞，又不是孤点的进程就只有P1这个进程。

接下来我们可以消去它所有的请求边和分配边，也就是把和P1相连的所有的边都干掉，使之成为孤立的节点，那由于此时已经没有边和它相连，所以此时P1就变成了之前所提到的所谓的孤点。

那么当P1释放了之前持有的资源之后，P2这个进程就可以被唤醒，于是P2也变成了既不阻塞又不是孤点的进程，所以接下来我们就需要把P2相连的所有的这些边给干掉，那么由于我们可以用这种方式干掉所有的边，所以这个图是可完全简化的。

死锁定理：如果某时刻系统的资源分配图是不可完全简化的，那么此时系统死锁。

死锁的解除

一旦检测出死锁的发生，就应该立即解除死锁。
补充：并不是系统中所有的进程都是死锁状态，用死锁检测算法化简资源分配图后，还连着边的那些进程就是死锁进程
解除死锁的主要方法有:
1. 资源剥夺法。挂起（暂时放到外存上）某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。但是应防止被挂起的进程长时间得不到资源而饥饿。
2. 撤销进程法（或称终止进程法）。强制撤销部分、甚至全部死锁进程，并剥夺这些进程的资源。这种方式的优点是实现简单，但所付出的代价可能会很大。因为有些进程可能已经运行了很长时间，已经接近结束了，一旦被终止可谓功亏一篑，以后还得从头再来。
3. 进程回退法。让一个或多个死锁进程回退到足以避免死锁的地步。这就要求系统要记录进程的历史信息，设置还原点。

知识回顾与重要考点