操作系统之进程管理(下)，同步互斥死锁问题，看看操作系统怎么解决的

目录：

• 进程同步，进程互斥
  • 进程同步
  • 进程互斥
  • 临界区的互斥访问
  • 进程互斥的软件实现方法（很多，可跳过）
  • 进程互斥的硬件实现-中断屏蔽方法
  • 进程互斥的硬件实现-TestAndSet指令
  • 进程互斥的硬件实现-Swap指令
  • JAVA 并发包 CAS 实现
  • 信号量机制
  • 管程
  • synchronized 底层原理-管程
• 死锁
  • 什么是死锁
  • 死锁、饥饿、死循环的区别
  • 死锁产生的必要条件
• 死锁的处理策略
  • 预防死锁
  • 避免死锁-银行家算法
  • 死锁的检测和恢复

进程同步，进程互斥

进程同步

进程具有异步性的特征。异步性是指，各并发执行的进程以各自独立的、不可预知的速度向前推进。

看一个例子:进程通信——管道通信。

进程通信-管道通信

读进程和写进程并发地运行，由于并发必然导致异步性，因此“写数据”和“读数据”两个操作执行的先后顺序是不确定的。而实际应用中，又必须按照“写数据->读数据”的顺序来执行的。如何解决这种异步问题，就是 “进程同步”所讨论的内容。

同步亦称直接制约关系，它是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而产生的制约关系。进程间的直接制约关系就是源于它们之间的相互合作。

进程互斥

进程的“并发”需要“共享”的支持。各个并发执行的进程不可避免的需要共享一些系统资源(比如内存，又比如打印机、摄像头这样的I/O设备)。

有两种共享方式：

1. 互斥共享方式： 系统中的某些资源，虽然可以提供给多个进程使用，但一个时间段内只允许一个进程访问该资源；
2. 同时共享方式：系统中的某些资源，允许一个时间段内由多个进程“同时”对它们进行访问.

我们把一个时间段内只允许一个进程使用的资源称为临界资源。许多物理设备(比如摄像头、打印机)都属于临界资源。此外还有许多变量、数据、内存缓冲区等都属于临界资源。

对临界资源的访问，必须互斥地进行。互斥，亦称间接制约关系。进程互斥指当一个进程访问某临界资源时，另一个想要访问该临界资源的进程必须等待。当前访问临界资源的进程访问结束，释放该资源之后，另一个进程才能去访问临界资源。

临界区的互斥访问

对临界资源的互斥访问，可以在逻辑上分为如下四个部分:

临界区的互斥访问

临界区是进程中访问临界资源的代码段。进入区和退出区是负责实现互斥的代码段。临界区也可称为“临界段”。

有个问题：如果一个进程暂时不能进入临界区，那么该进程是否应该一直占着处理机?该进程有没有可能一直进不了临界区?

为了实现对临界资源的互斥访问，同时保证系统整体性能，需要遵循以下原则:

1. 空闲让进。临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区;
2. 忙则等待。当已有进程进入临界区时，其他试图进入临界区的进程必须等待;
3. 有限等待。对请求访问的进程，应保证能在有限时间内进入临界区(保证不会饥饿);
4. 让权等待。当进程不能进入临界区时，应立即释放处理机，防止进程忙等待。

小结

进程互斥的软件实现方法（很多，可跳过）

进程互斥的软件实现

「单标志法」

算法思想:两个进程在访问完临界区后会把使用临界区的权限转交给另一个进程。也就是说每个进程进入临界区的权限只能被另一个进程赋予。

单标志法

解释：turn 的初值为 0，即刚开始只允许 0 号进程进入临界区。若 P1 先上处理机运行，则会一直卡在 5。直到 P1 的时间片用完，发生调度，切换 P0 上处理机运行。代码 1 不会卡住 P0，P0 可以正常访问临界区，在 P0 访问临界区期间即时切换回 P1，P1依然会卡在 5。只有 P0 在退出区将 turn 改为 1 后，P1才能进入临界区。

缺点：只能按 P0 -〉 P1 -〉 P0 -〉 P1 -〉......这样轮流访问。这种必须“轮流访问”带来的问题是，如果此时允许进 入临界区的进程是 P0，而 P0 一直不访问临界区，那么虽然此时临界区空闲，但是并不允许 P1 访问。

因此，单标志法存在的主要问题是:违背“空闲让进”原则。

「双标志检查法」

算法思想:设置一个布尔型数组 flag[]，数组中各个元素用来标记各进程想进入临界区的意愿，比如 “flag[0] = ture”意味着 0 号进程 P0 现在想要进入临界区。每个进程在进入临界区之前先检查当前有 没有别的进程想进入临界区，如果没有，则把自身对应的标志 flag[i] 设为 true，之后开始访问临界区。

双标志法

缺点：若按照 152637....的顺序执行，P0 和 P1 将会同时访问临界区。因此，双标志先检查法的主要问题是:违反“忙则等待”原则。原因在于，进入区的“检查”和“上锁” 两个处理不是一气呵成的。“检查”后，“上锁”前可能发生进程切换。

「双标志后检查法」

算法思想:双标志先检查法的改版。前一个算法的问题是先“检查”后“上锁”，但是这两个操作又无法一气呵成，因此导致了两个进程同时进入临界区的问题。因此，人们又想到先“上锁”后“检查”的方法，来避免上述问题。

双标志后检查法

若按照 1526....的顺序执行，P0 和 P1 将都无法进入临界区 因此，双标志后检查法虽然解决了“忙则等待”的问题，但是又违背了“空闲让进”和“有限等待” 原则，会因各进程都长期无法访问临界资源而产生“饥饿”现象。两个进程都争着想进入临界区，但是谁也不让谁，最后谁都无法进入临界区。

「Peterson 算法」算法思想:结合双标志法、单标志法的思想。如果双方都争着想进入临界区，那可以让进程尝试“孔融让梨”(谦让)。做一个有礼貌的进程。

Peterson算法

❝谁最后说了“客气话”，谁就失去了行动的优先权。 Eg: 过年了，某阿姨给你发压岁钱。阿姨: 乖，收下阿姨的心意~ 你: 不用了阿姨，您的心意我领 阿姨:对阿姨来说你还是个孩子，你就收下吧 结局... ❞

Peterson 算法用软件方法解决了进 程互斥问题，遵循了空闲让进、忙 则等待、有限等待 三个原则，但是 依然未遵循让权等待的原则。

Peterson 算法相较于之前三种软件 解决方案来说，是最好的，但依然 不够好。

进程互斥软件实现小结

进程互斥的硬件实现-中断屏蔽方法

进程互斥的硬件实现方法

「中断屏蔽方法」

中断屏蔽方法

优点:简单、高效

缺点:不适用于多处理机;只适用于操作系统内核进程，不适用于用户进程(因为开/关中断指令只能运行在内核态，这组指令如果能让用户随意使用会很危险)

进程互斥的硬件实现-TestAndSet指令

「TestAndSet指令」

简称 TS 指令，也有地方称为 TestAndSetLock 指令，或 TSL 指令 TSL 指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成。以下是用C语言描述的逻辑：

TestAndSet指令

解释：若刚开始 lock 是 false，则 TSL 返回的 old 值为 false，while 循环条件不满足，直接跳过循环，进入临界区。若刚开始 lock 是 true，则执行 TLS 后 old 返回的值为 true，while 循环条件满足，会一直 循环，直到当前访问临界区的进程在退出区进行“解锁”。

相比软件实现方法，TSL 指令把“上锁”和“检查”操作用硬件的方式变成了一气呵成的原子操作。

优点:实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞;适用于多处理机环境

缺点:不满足“让权等待”原则，暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从 而导致“忙等”。

进程互斥的硬件实现-Swap指令

「Swap指令」有的地方也叫 Exchange 指令，或简称 XCHG 指令。Swap 指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成。以下是用C语言􏰀述的逻辑：

Swap指令

逻辑上来看 Swap 和 TSL 并无太大区别，都是先记录下此时临界区是否已经被上锁(记录在 old 变 量上)，再将上锁标记 lock 设置为 true，最后检查 old，如果 old 为 false 则说明之前没有别的进程 对临界区上锁，则可跳出循环，进入临界区。

优点:实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞;适用于多处理机环境

缺点:不满足“让权等待”原则，暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从 而导致“忙等”。

进程互斥的硬件实现

JAVA 并发包 CAS 实现

「JAVA 并发包CAS实现，对Swap指令的利用」

java.util.concurrent.atomic 包下有个原子类 AtomicInteger，其中的 compareAndSet 方法即 CAS。CAS 全称是 compare and swap，是一种用于在多线程环境下实现同步功能的机制。代码如下：

public class AtomicInteger extends Number implements java.io.Serializable {

    // setup to use Unsafe.compareAndSwapInt for updates
    private static final Unsafe unsafe = Unsafe.getUnsafe();
    private static final long valueOffset;

    static {
        try {
            // 计算变量 value 在类对象中的偏移
            valueOffset = unsafe.objectFieldOffset
                (AtomicInteger.class.getDeclaredField("value"));
        } catch (Exception ex) { throw new Error(ex); }
    }

    private volatile int value;
    
    public final boolean compareAndSet(int expect, int update) {
        /*
         * compareAndSet 实际上只是一个壳子，主要的逻辑封装在 Unsafe 的 
         * compareAndSwapInt 方法中
         */
        return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
    }
    
    // ......
}

public final class Unsafe {
    // compareAndSwapInt 是 native 类型的方法，继续往下看
    public final native boolean compareAndSwapInt(Object o, long offset,
                                                  int expected,
                                                  int x);
    // ......
}

在 Java 中，Java 并没有直接实现 CAS，CAS 相关的实现是通过 C++ 内联汇编的形式实现的。Java 代码需通过 JNI 才能调用，compareAndSwapInt 是 native 类型的方法。

CAS 底层的实现离不开处理器的支持。C++底层代码，其实核心代码就是一条带 lock 前缀的 cmpxchg 指令，即lock cmpxchg dword ptr [edx], ecx.

交换指令：CMPXCHG、XCHG

1. CPMXCHG

用于比较并交换操作数，CPU对CAS的原语支持 非原子性，最早用于单核CPU

1. XCHG

用于交换两个操作数 具备原子性，CPU会自动加LOCK前缀

LOCK前缀:

1. 作用 CPU保证被其修饰的指令的原子性。
2. 实现方式

• 依赖内存有序模型，来保证读取指令有序；
• 通过总线锁或缓存一致性，保证被修饰指令操作的数据一致性：

当访问的数据在系统内存时，通过在总线锁实现原子性；当访问的数据在处理器的缓存时，通过缓存一致性协议实现原子性；

举个栗子:

volatile 关键字有两个作用，一个是保证线程可见性，一个是禁止指令重排。Java的DCL中若返回的变量不加volatile修饰，则可能会由于指令重排导致另一个线程获取到一个非完全初始化的对象。

当volatile修饰的变量所在的代码段成为热点，被JIT编译为汇编代码后，会增加LOCK前缀来禁止指令重排和来保证数据一致；具体的详细的，可以移步一篇博客文“https://www.cnblogs.com/ITPower/p/13580691.html”

信号量机制

这个信号量，非常的抽象，他到底是什么？

「什么是信号量」

❝信号量就是在一个叫做互斥区的门口放一个盒子，盒子里面装着固定数量的小球，每个线程过来的时候，都从盒子里面摸走一个小球，然后去互斥区里面浪，浪开心了出来的时候，再把小球放回盒子里。如果一个线程走过来一摸盒子，得，一个球都没了，不拿球不让进啊，那就只能站在门口等一个线程出来放回来一个球，再进去。这样由于小球的数量是固定的，那么互斥区里面的最大线程数量就是固定的，不会出现一下进去太多线程把互斥区给挤爆了的情况。这是用信号量做并发量限制。 另外一些情况下，小球是一次性的，线程拿走一个进了门，就把小球扔掉了，这样用着用着小球就没了，不过有另外一些线程（一般叫做生产者）会时不时过来往盒子里再放几个球，这样就可以有新的线程（一般叫做消费者）进去了，放一个球进一个线程，这是信号量做同步功能。这种就是生产者消费者模型。 ❞

信号量其实就是一个变量 (可以是一个整数，也可以是一个结构体)，可以用一个信号量 来表示系统中某种资源的数量，比如:系统中只有一台打印机，就可以设置一个初值为 1 的信号量。

「信号量实现」

我们前面说到进程控制的时候，花了大篇的篇幅来讲原语，信号量机制就是利用了原语操作。前面看进程互斥的软件实现方式的时候，各种的编码方式，各种的名称，其实主要是因为读和写操作不是一个原子操作，即然原语可以保证原子操作，利用在这里再好不过了。

一对原语:wait(S) 原语和 signal(S) 原语，可以把原语理解为我们自己写的函数，函数名分别为 wait 和 signal，括号里的信号量 S 其实就是函数调用时传入的一个参数。

wait、signal 原语常简称为 P、V操作(来自荷兰语 proberen 和 verhogen)。信号量（Semaphore）也称为信号灯，典故来源于荷兰：火车根据旗标来决定是否通行。其实就是红绿灯的作用。

「信号量作用」

1. 信号量可以实现进行互斥，进程同步，进程的前驱关系

一个信号量对应一种资源

• 信号量的值 = 这种资源的剩余数量(信号量的值如果小于0，说明此时有进程在等待这种资源);
• P( S ) —— 申请一个资源S，如果资源不够就阻塞等待;
• V( S ) —— 释放一个资源S，如果有进程在等待该资源，则唤醒一个进程;

信号量可以实现进行互斥，进程同步，进程的前驱关系。以实现前驱关系举例：

进程 P1 中有句代码 S1，P2 中有句代码 S2 ，P3中有句代码S3 ...... P6 中有句代码 S6。这些代码要求 按如下前驱图所示的顺序来执行:

信号量控制进程的前驱关系

代码实现如下图：

信号量控制进程的前驱关系代码实现

每个进程都需要申请和释放自己对应的资源。

1. 信号量解决 生产者-消费者 问题
2. 信号量解决 多生产者-多消费者 问题
3. 信号量解决 哲学家进餐 问题
4. 信号量解决 读者-写这 问题

管程

「为什么要引入管程」

信号量机制存在的问题: 编写程序困难、易出错；进程自备同步操作，P(S)和V(S)操作大量分散在各个进程中，不易管理，易发生死锁。.

能不能设计一种机制，让程序员写程序时不需要再关注复杂的PV操作，让写代码更轻松呢?

1973年，Brinch Hansen 首次在程序设计语言 (Pascal) 中引入了“管程”成分：一种高级同步机制。

「管程定义和基本特征」

❝引用一段专业书里对管程的介绍: 在利用管程实现进程同步时，当某进程通过管程请求获得临界资源而未能满足时，管程便调用wait原语使该进程等待，并将其排在等待队列上。仅当另一个进程访问完成并释放该资源后，管程才又调用signal原语，唤醒等待队列中的队首进程。但是，考虑这样一种情况：当一个进程调用了管程后，在管程中时被阻塞或挂起，直到阻塞或挂起的原因解除；在此期间，如果该进程不释放管程，则其它进程就无法进入管程，被迫长时间等待。 为了解决这个问题，引入条件变量condition。通常，一个进程被被阻塞或挂起的条件（原因）可有多个，因此在管程中设置了多个条件变量，对这些条件变量的访问智能在管程中进行。 ❞

❝wiki百科的简单定义: 管程 (英语：Monitors，也称为监视器) 是一种程序结构，结构内的多个子程序（对象或模块）形成的多个工作线程互斥访问共享资源。 这些共享资源一般是硬件或一群变量。管程实现了在一个时间点，最多只有一个线程在执行管程的某个子程序。 与那些通过修改数据结构实现互斥访问的并发程序设计相比，管程实现很大程度上简化了程序设计。 ❞

管程提供了一种机制，线程可以临时放弃互斥访问，等待某些条件得到满足后，重新获得执行权恢复它的互斥访问。

管程(monitor)只是保证了同一时刻只有一个进程在管程内活动,即管程内定义的操作在同一时刻只被一个进程调用(由编译器实现).但是这样并不能保证进程以设计的顺序执行,因此需要设置condition变量,让进入管程而无法继续执行的进程阻塞自己.

管程是一种特殊的软件模块，有这些部分组成:

1. 局部于管程的共享数据结构说明;
2. 对该数据结构进行操作的一组过程;
3. 对局部于管程的共享数据设置初始值的语句;
4. 管程有一个名字。

管程的基本特征:

1. 局部于管程的数据只能被局部于管程的过程所访问;
2. 一个进程只有通过调用管程内的过程才能进入管程访问共享数据;
3. 每次仅允许一个进程在管程内执行某个内部过程。

「管程如何解决互斥和同步问题」

管程如何解决互斥和同步问题：

互斥问题：

1. 管程是互斥进入，管程提供了入口等待队列：存储等待进入同步代码块的线程;
2. 管程的互斥性是由编译器负责保证的。

同步问题:管程中设置条件变量，等待/唤醒操作，以解决同步问题。

1. 条件变量（java里理解为锁对象自身）
2. 等待操作:可以让进程、线程在条件变量上等待（此时，应先释放管程的使用权，不然别其它线程、进程拿不到使用权）；将线程存储到条件变量的等待队列中。
3. 发信号操作:也可以通过发送信号将等待在条件变量上的进程、线程唤醒（将等待队列中的线程唤醒）

synchronized 底层原理-管程

synchronized是语法糖，会被编译器编译成：1个monitorenter 和 2个monitorexit（一个用于正常退出，一个用于异常退出）。monitorenter 和 正常退出的monitorexit中间是synchronized包裹的代码.

调用代码

java 对象和 monitor 关联图

synchronized是重量级锁，存储了是指向monitor的指针。monitor(又称管程)，在Java中是ObjectMonitor(JVM源码中C++实现)来实现管程。

synchronized的底层

synchronized 内部实现流程：

1. 想要获取monitor的线程先进入monitor的_EntryList队列阻塞等待。即遇到synchronized关键字时。
2. 如果monitor的_owner为空，则从队列中移出并赋值与_owner。
3. 如果在程序里调用了wait()方法，则该线程进入_WaitSet队列。注意wait方法我们之前讲过，它会释放monitor锁，即将_owner赋值为null并进入_WaitSet队列阻塞等待。这时其他在_EntryList中的线程就可以获取锁了。
4. 当程序里其他线程调用了notify/notifyAll方法时，就会唤醒_WaitSet中的某个线程，这个线程就会再次尝试获取monitor锁。如果成功，则就会成为monitor的owner。
5. 当程序里遇到synchronized关键字的作用范围结束时，就会将monitor的owner设为null，退出。

调用的方法自然也是管程提供的方法，如下图：

管程提供的方法

死锁

什么是死锁

在并发环境下，各进程因竞争资源而造成的一种互相等待对方手里的资源，导致各进程都阻塞，都无法向前推进的现象，就是“死锁”。发生死锁后若无外力干涉，这些进程都将无法向前推进。

死锁、饥饿、死循环的区别

死锁、饥饿、死循环的区别

死锁产生的必要条件

产生死锁必须同时满足一下四个条件，只要其中任一条件不成立，死锁就不会发生。

1. 互斥条件:只有对必须互斥使用的资源的争抢才会导致死锁(如哲学家的筷子、打印机设备)。像内存、扬声器这样可以同时让多个进程使用的资源是不会导致死锁的(因为进程不用阻塞等待这种资源)。
2. 不剥夺条件:进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放。
3. 请求和保持条件:进程已经保持了至少一个资源，但又提 3 出了新的资源请求，而该资源又被其他进程占有，此时请 求进程被阻塞，但又对自己已有的资源保持不放。
4. 循环等待条件:存在一种进程资源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程所请求。

死锁的处理策略

三个策略：

1. 预防死锁。破坏死锁产生的四个必要条件中的一个或几个。
2. 避免死锁。用某种方法防止系统进入不安全状态，从而避免死锁(银行家算法)
3. 死锁的检测和解除。允许死锁的发生，不过操作系统会负责检测出死锁的发生，然后采取某种措 施解除死锁。

预防死锁

预防死锁

用SPOOLing技术将打印机改造为共享设备...

打印机-破坏互斥条件

核心就是破坏死锁产生的四个必要条件中的一个或几个。

避免死锁-银行家算法

先看一个借钱的例子：

❝你是一位成功的银行家，手里掌握着100个亿的资金... 有三个企业想找你贷款，分别是 企业B、企业A、企业T，为􏰀述方便，简称BAT。 B 表示:“大哥，我最多会跟你借70亿...” A 表示:“大哥，我最多会跟你借40亿...” T 表示:“大哥，我最多会跟你借50亿...” 然而...江湖中有个不成文的规矩:如果你借给企业的钱总数达不到企业提出的最大要求，那么不管你之前给企业借了多少钱，那些钱都拿不回来了... 刚开始，BAT三个企业分别从你这儿借了 20、10、30 亿 ... ❞

最开始

第二步，假如，再给B借30亿，这样是不安全的...之后手里只剩10亿，如果BAT都提出再借20亿的请求，那么任何一个企业的需求都得不到满足...如下：

第二步

这样肯定不行，这不是银行家，这是马大哈。

「安全序列」

这种场景，涉及到一个安全序列。

所谓安全序列，就是指如果系统按照这种序列分配资源，则每个进程都能顺利完成。只要能找出一个安全序列，系统就是安全状态。当然，安全序列可能有多个。如下图，借钱就达到了一个安全序列：

安全借钱

第二步，给A借 20 亿是安全的，因为存在 T-〉B-〉A 这 样的安全序列。

「银行家算法」

银行家算法是荷兰学者 Dijkstra 为银行系统设计的，以确保银行在发放现金贷款时，不会发生不能满足所有客户需要的情况。后来该算法被用在操作系统中，用于避免死锁。

核心思想:在进程对资源申请时，先预判此次分配是否会导致系统进入不安全状态。如果会进 入不安全状态，就暂时不答应这次请求，让该进程先阻塞等待。

BAT 的例子中，只有一种类型的资源——钱，但是在计算机系统中会 有多种多样的资源，应该怎么把算法拓展为多种资源的情况呢?

举例：可以把单维的数字拓展为多维的向量。比如:系统中有5个进程 P0~P4，3 种资源 R0~R2，初始数量为 (10, 5, 7)，则某一时刻的情况可表示如下:

银行家算法

此时总共已分配 (7, 2, 5)，还剩余 (3, 3, 2) 可把最大需求、已分配的数据看作矩阵， 两矩阵相减，就可算出各进程最多还需要多少资源了。

经对比发现，(3, 3, 2)可满足 P1、P3，说明无论如何，这两个进程的资源需求一定是可以依次被 满足的，因此P1、P3 一定可以顺利的执行完，并归还资源。可把 P1、P3 先加入安全序列。

银行家算法-资源需求

(2, 0, 0) + (2, 1, 1) + (3, 3, 2) = (7, 4, 3)， 剩下的 P0、P2、P4 都可被满足。同理，这些进程都可以加入安全序列。于是，5个进程全部加入安全序列，说明此时系统处于安全状态，暂不可能发生死锁。

银行家算法步骤:

1. 检查此次申请是否超过了之前声明的最大需求数
2. 检查此时系统剩余的可用资源是否还能满足这次请求
3. 试探着分配，更改各数据结构
4. 用安全性算法检查此次分配是否会导致系统进入不安全状态

安全性算法步骤:

1. 检查当前的剩余可用资源是否能满足某个进程的最大需求，如果可以，就把该进程加入安全序列，并把该进程持有的资源全部回收。
2. 不断重复上述过程，看最终是否能让所有进程都加入安全序列。

死锁的检测和恢复

不试图阻止死锁，而是当检测到死锁发生时，采取措施进行恢复。

1. 检测

为了能对系统是否已发生了死锁进行检测，必须:

• 用某种数据结构来保存资源的请求和分配信息;
• 提供一种算法，利用上述信息来检测系统是否已进入死锁状态。

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

上图为资源分配图，其中方框表示资源结点，圆圈表示进程结点，进程结点向资源结点请求资源；资源指向进程表示该资源已经分配给该进程，进程指向资源表示进程请求获取该资源。

图 a 可以抽取出环，如图 b，它满足了环路等待条件，因此会发生死锁。

每种类型一个资源的死锁检测算法是通过检测有向图是否存在环来实现，从一个节点出发进行深度优先搜索，对访问过的节点进行标记，如果访问了已经标记的节点，就表示有向图存在环，也就是检测到死锁的发生。

使用类似于这种的算法来进行检测，当然实际实现还会有比这个更加牛的算法来进行检测。

1. 解除

解除死锁的主要方法有:

• 资源剥夺法。挂起(暂时放到外存上)某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。但是应防止被挂起的进程长时间得不到资源而饥饿。
• 撤销进程法(或称终止进程法)。强制撤销部分、甚至全部死锁进程，并剥夺这些进程的资 源。这种方式的优点是实现简单，但所付出的代价可能会很大。因为有些进程可能已经运行了很长时间，已经接近结束了，一旦被终止可谓功亏一篑，以后还得从头再来。
• 进程回退法。让一个或多个死锁进程回退到足以避免死锁的地步。这就要求系统要记录进程的历史信息，设置还原点。

❝往期推荐： 1.操作系统之内存管理，高能预警！！！ 2.操作系统之文件管理，一切皆文件!!! 3.操作系统之进程管理(上)，研究再多高并发，都不如啃一下操作系统进程！！！ ❞

文章参考：王道老师操作系统

先赞后看，养成习惯。有收获的欢迎点赞，分享，在看，喜欢的话可以关注我公主号《小龙飞》，文章首发均在这～～～