操作系统 2 进程管理

本文最后更新于：2023年12月10日 晚上

B站王道考研视频内容，结合《计算机操作系统（第四版）——汤小丹》课本做的笔记

王道的有些图做的确实很好，比较容易看懂

2.1 进程与线程

image-20231127224148425

2.1.1 进程的概念、组成、特征、组织

进程的概念

在多道程序环境下，程序的执行属于并发执行，此时它们将失去其封闭性，并具有间断性，以及其运行结果不可再现性的特征。由此，决定了通常的程序是不能参与并发执行的，否则，程序的运行也就失去了意义。为了能使程序并发执行，并且可以对并发执行的程序加以描述和控制，人们引入了“进程”的概念。

为了使参与并发执行的每个程序(含数据)都能独立地运行，在操作系统中必须为之配置一个专门的数据结构，称为进程控制块(Process Control Block，PCB)。系统利用PCB来描述进程的基本情况和活动过程，进而控制和管理进程。

进程的概念
进程的概念

进程和程序的区别和联系：

区别：

  1. 进程是动态的;程序是静态的。
  2. 进程有独立性，能并发执行；程序不能并发执行。
  3. 二者无一一对应关系。
  4. 进程异步运行，会相互制约；程序不具备此特征。
  5. 组成不同。进程包含PCB、程序段、数据段。程序包含数据和指令代码。程序是一个包含了所有指令和数据的静态实体。本身除占用磁盘的存储空间外，并不占用系统如CPU、内存等运行资源。进程由程序段、数据段和PCB构成，会占用系统如CPU、内存等运行资源。

但是，进程与程序又有密切的联系： 进程不能脱离具体程序而虚设， 程序规定了相应进程所要完成的动作。

进程的组成

进程的组成

进程控制块PCB的作用

  1. 作为独立运行基本单位的标志

  2. 能实现间断性运行方式。

  3. 提供进程管理所需要的信息

  4. 提供进程调度所需要的信息

  5. 实现与其它进程的同步与通信

进程控制块（PCB）中的信息

进程控制块中主要包括下述四个方面的信息。

1.进程标识符：

用于唯一地标识一个进程；通常有两种标识符：

  1. 外部标识符(显示名称)，(2) 内部标识符(PID)

2.处理机状态：

处理机的各种寄存器中的内容组成

3.进程调度信息：

① 进程状态：进程的当前状态，作为进程调度和对换时的依据；

② 进程优先级：描述进程使用处理机的优先程度的一个整数，优先级高的进程应优先获得处理机；

③ 进程调度所需的其它信息：例如，进程已等待CPU的时间总和、进程已执行的时间总和等；

④ 事件：是指进程由执行状态变为阻塞状态所等待发生的事件，即阻塞原因。

4.进程控制信息

① 程序和数据的地址：进程实体中的程序和数据的内存或外存地(首)址；

② 进程同步和通信机制：如消息队列指针、信号量等，它们可能全部或部分地放在PCB中；

③ 资源清单：进程在运行期间所需的全部资源(除CPU以外)；另外还有一张已分配到该进程的资源的清单；

④ 链接指针：给出本进程(PCB)所在队列中的下一进程的PCB首地址。

进程的组成-PCB

进程的特征

image-20231127130059069

进程的组织

在一个操作系统中，通常可拥有数十个、数百个乃至数千个PCB，为了能对它们加以有效的管理，应该用适当的方式将这些 PCB 组织起来。目前常用的组织方式有以下三种。

(1)线性方式，即将系统中所有的 PCB 都组织在一张线性表中，将该表的首址存放在内存的一个专用区域中。该方式实现简单、开销小，但每次查找时都需要扫描整张表，因此适合进程数目不多的系统。图2-10示出了线性表的PCB组织方式。

进程的组织方式-线性方式

(2) 链接方式，即把具有相同状态进程的 PCB 分别通过PCB中的链接字链接成一个队列。这样，可以形成就绪队列、若干个阻塞队列和空白队列等。

对就绪队列而言，往往按进程的优先级将 PCB 从高到低进行排列，将优先级高的进程PCB 排在队列的前面。同样也可把处于阻塞状态进程的 PCB 根据其阻塞原因的不同，排成多个阻塞队列，如等待I/O操作完成的队列和等待分配内存的队列等。图2-11示出了一种链接队列的组织方式

进程的组织-链接方式

(3) 索引方式：即系统根据所有进程状态的不同，建立几张索引表，例如，就绪索引表、阻塞索引表等，并把各索引表在内存的首地址记录在内存的一些专用单元中。在每个索引表的表目中，记录具有相应状态的某个PCB在PCB 表中的地址。图2-12示出了索引方式的PCB组织。

进程组织方式-索引方式

2.1.2 进程的状态及转换

进程的状态

三种基本状态
另外两种状态

创建状态

  • 首先：由进程申请一个空白PCB，并向PCB中填写用于控制和管理进程的信息；
  • 然后：为该进程分配运行时所必须的资源；
  • 最后：把该进程转入就绪状态并插入就绪队列之中。

如果进程所需的资源不能得到满足，比如无足够的内存使进程无法装入其中，此时创建工作尚未完成，进程不能被调度运行，于是把此时进程所处的状态称为创建状态。

终止状态

  • 首先：等待操作系统进行善后处理
  • 最后：将其PCB清零，并将PCB空间返还操作系统

当一个进程到达了自然结束点，或是出现了无法克服的错误，或是被操作系统所终结，或是被其他有终止权的进程所终结，它将进入终止状态。进入终止态的进程以后不能再执行，但在操作系统中依然保留一个记录，其中保存状态码和一些计时统计数据，供其他进程收集。一旦其他进程完成了对其信息的提取之后，操作系统将删除该进程，即将其PCB清零，将空白PCB返还系统。

进程状态间的转换

五状态转换图

2.1.3 进程控制

进程控制概念

进程控制是进程管理中最基本的功能，主要包括创建新进程、终止已完成的进程、将因发生异常情况而无法继续运行的进程置于阻塞状态、负责进程运行中的状态转换等功能。如当一个正在执行的进程因等待某事件而暂时不能继续执行时，将其转变为阻塞状态，而在该进程所期待的事件出现后，又将该进程转换为就绪状态等。进程控制一般是由 OS 的内核中的原语来实现的。

简单说：进程控制就是要实现进程状态转换

原语实现对进程的控制

原语实现对进程的控制
如何实现原语的“原子性”

思考：如果这两个特权指令允许用户程序使用的话，会发生什么情况？

------流氓程序，必须执行完它，才能执行其他的程序，这种是不被允许的

进程控制的五种原语

进程的创建原语

进程的创建原语

进程的终止原语

进程的终止原语

进程的唤醒和阻塞原语

引起进程阻塞和唤醒的事件

  1. 向系统请求共享资源失败。

  2. 等待某种操作的完成。

  3. 新数据尚未到达。

  4. 等待新任务的到达。

image-20231128000426318
进程的唤醒和阻塞原语

进程的切换原语

进程的切换原语

无论哪个进程控制原语，要做的无非三类事情：

  1. 更新PCB中的信息
  2. 将PCB插入合适的队列
  3. 分配/回收资源

2.1.4 进程通信

为什么进程通信需要操作系统支持？

进程通信是指进程之间的信息交换。进程的互斥与同步也归为进程通信；互斥与同步称为低级进程通信。

以信号量机制为例，它们之所以低级的原因在于：

① 效率低，生产者每次只能向缓冲池投放一个产品(消息)，消费者每次只能从缓冲区中取得一个消息；

② 通信对用户不透明，OS只为进程之间的通信提供了共享存储器。

在进程之间要传送大量数据时，应当利用OS提供的高级通信工具，这些工具最主要的特点是：

  1. 使用方便：OS隐藏了实现进程通信的具体细节，向用户提供一组用于实现高级通信的命令(原语)；通信过程对用户是透明的， 大大减少了通信程序编制上的复杂性。

  2. 高效地传送大量数据：用户可直接利用高级通信命令(原语)高效地传送大量的数据。

共享存储系统

共享一块大家都可以访问的空间，一次只能有一个进程进行读或写操作

共享存储

消息传递系统

发送信息的进程将消息头写好，接受信息进程根据消息头读取信息或寻找信封是哪一个

image-20231128001938441
消息传递（直接）

直接通信方式：点名道姓的消息传递

消息传递（间接）

管道通信系统

共享通信方式是写哪都可以，管道通信相当于一个队列（FIFO）

管道通信系统

2.1.5 线程概念与多线程模型

1. 线程概念

为什么要引入线程？

为什么要引入线程？

什么是线程？

img

引入线程带来的变化

引入线程带来的变化

2. 线程的属性

线程的属性

3. 线程的实现方式

  • 线程的实现分为两类：用户级线程(User-Level Thread,UTL)和内核级线程(Kernel-Level Thread, KTL)。内核级线程又称内核支持的线程。
  • 内核级线程 KLT (Kernel-Level Thread) 又称“内核支持的线程”：内核支持线程 KST (Kernel Supported Threads)

历史背景：早期的操作系统 (如：早期Unix) 只支持进程不支持线程。当时的“线程”是由线程库实现的

用户级线程

用户级线程（ULT）

ULT线程方式的优点：

  1. 线程切换不需要转换到内核空间，线程管理的系统开销小，效率高

  2. 调度算法可以是进程专用的

  3. ULT线程的实现与OS平台无关，因为对于线程管理的代码是属于用户程序的一部分，所有的应用程序都可以对之进行共享。

ULT线程方式的主要缺点：

  1. 系统调用的阻塞问题

在基于进程机制的OS中，当线程执行一个系统调用时，不仅该线程被阻塞，该进程内的所有线程会被阻塞。并发度不高。

  1. 不能充分利用多处理机

OS每次分配给一个进程的仅有一个CPU，因此，进程中仅有一个线程能执行，在该线程放弃CPU之前，进程中其它线程只能等待，即多个线程不可在多核处理机上并行运行

内核级线程

在内核空间为每一个内核线程设置了一个TCB，OS内核根据TCB来感知某线程的存在，并对其加以控制和管理

内核级线程

KST线程方式的四个主要优点：

  1. 在多处理器系统中，内核能够同时调度同一进程中的多个线程并行执行；
  2. 如果进程中的某个线程被阻塞，内核可以调度该进程中的其它线程运行，也可以运行其它进程中的线程；
  3. KLT（KST）线程具有很小的数据结构和堆栈，线程的切换比较快，切换开销小；
  4. 内核本身也可以采用多线程技术，可以提高系统的执行速度和效率。

内核支持线程的主要缺点是：

对于用户的线程切换而言，其模式切换的开销较大，在同一个进程中，从一个线程切换到另一个线程时，需要从用户态转到核心态进行，这是因为用户进程的线程在用户态运行，而线程调度和管理是在内核实现的，系统开销较大。

这里的两个切换，一个开销大，一个开销小，这里解释一下：优点说的是内核级线程之间的切换，缺点说的是用户级线程之间的切换

特殊的组合方式

上面两种方式结合的组合方式

4. 多线程模型

  • 前面我们提到了线程的实现方式，有用户级和内核级。那么这两种模式的交叉组合就会产生几种不一样的组织结构，即不一样的模型。

一对一模型

一对一模型

多对一模型

多对一模型

多对多模型

多对多模型

2.1.6 线程的状态与转换

线程的状态与转换

线程的状态与转换与进程的完全一致

  1. 执行状态（或者叫运行状态）：表示线程已获得处理机而正在运行；

  2. 就绪状态：指线程已具备了各种执行条件，只须再获得CPU便可立即执行；

  3. 阻塞状态：指线程在执行中因某事件受阻而处于暂停状态，例如，当一个线程执行从键盘读入数据的系统调用时，该线程就被阻塞

线程的状态与转换

线程控制块TCB

如同每个进程有一个进程控制块一样，系统也为每个线程配置了一个线程控制块Thread Control Block(TCB)，将所有用于控制和管理线程的信息记录在线程控制块中

线程控制块TCB

2.2 处理机的调度

2.2.1 处理机调度的概念及层次

1. 调度的基本概念

调度的基本概念

2. 调度的三个层次

高级调度（作业调度）

作业后备队列：

作业：一个具体的任务，用户向系统提交一个作业 ≈ 用户让操作系统启动一个程序（来处理一个具体的任务）

高级调度（作业调度）

高级调度主要用于多道批处理系统中，在分时和实时系统中不设置高级调度。

高级调度简化理解：好几个程序需要启动，到底先启动哪个

低级调度（进程调度）

低级调度所调度的对象是进程（或内核级线程）。

进程调度是最基本的一种调度，在多道批处理、分时和实时二种类型的OS中，都必须配置这级调度。

低级调度（进程调度）

中级调度（内存调度）

中级调度（内存调度）

进程的七状态模型

进程的七状态模型

3. 三层调度的联系和对比

三层调度的联系和对比

2.2.2 进程调度的时机、切换与过程、方式

进程调度的时机

（1）什么时候进行进程调度？

什么时候进行进程调度？

（2）什么时候不能进行进程调度？

什么时候不能进行进程调度？

（3）OS内核程序临界区与普通临界区的进程调度情况

OS内核程序临界区与普通临界区的进程调度情况

内核程序临界区是会上一个🔒，然后独自占用资源，并且其他的进程是无法进去就绪队列的

OS内核程序临界区与普通临界区的进程调度情况

一些IO设备，如打印机，因为这类的设备处理会很慢很慢，总不可能一直等待打印机工作结束

一个是临界区，一个是内核临界区，临界区是大范围，内核临界区是小范围

进程调度的方式

在进程调度的时机“（1）什么时候进行进程调度？”中，有的系统中，只允许进程主动放弃处理机，而有的系统中，进程可以主动放弃处理机，当有更紧急的任务需要处理时，也会强行剥夺处理机（被动放弃）

这就引出了进程调度的两种方式——非剥夺与剥夺

进程调度的方式

进程的切换和过程

进程的切换和过程

2.2.3 调度程序和闲逛程序

调度程序

调度器/调度程序
image-20231210103451666

闲逛进程

调度程序永远的备胎，没有其他就绪进程时，运行闲逛进程 (idle)

闲逛进程的特性：

  • 优先级最低
  • 可以是0地址指令，占一个完整的指令周期(指令周期末尾例行检查中断)
  • 能耗低

2.2.4 调度算法的评价指标

1. CPU利用率

CPU利用率

2. 系统吞吐量

系统吞吐量

3. 周转时间

周转时间-平均周转时间
带权周转时间

带权周转时间其实表示的是进程的周转时间比运行时间大多少倍的这样一个指标

4. 等待时间

等待时间

5. 响应时间

响应时间

2.2.5 作业/进程调度算法1

0. 思维导图

调度算法学习思路

1. 先来先服务--FCFS

  • First Come First Serve
先来先服务--FCFS
先来先服务(FCFS)例题

2. 短作业优先--SJF

  • Shortest Job First
短作业优先--SJF

非抢占式—SJF：

其实这里应该叫短进程优先---SPF，但是很多时候题目也不区分这两个了

非抢占式—SJF例题

抢占式—SJF（SRTN）：

抢占式—SJF（SRTN）
抢占式—SJF（SRTN）各种时间计算

注意几个细节：

image-20231210111022273

3. 高响应比优先--HRRN

  • Highest Response Ratio Next
思考中……

byd看一个多小时qing有点小累了🥱🥱🥱，2023.12.10 11:15

高响应比优先--HRRN
高响应比优先--HRRN例题

4. 三种算法的对比和总结

三种算法的对比和总结

2.2.6 作业/进程调度算法2

0.思维导图

作业/进程调度算法2

1. 时间片轮转--RR

  • Round-Robin
时间片轮转--RR

时间片大小为2举例

1
2
3

时间片大小为5举例

1

可能出现的问题，与FCFS对比

RR与FCFS对比

如果时间片太大，使得每个进程都可以在一个时间片内就完成，则时间片轮转调度算法退化为先来先服务调度算法，并且会增大进程响应时间。因此时间片不能太大。

  • 比如：系统中有10个进程在并发执行，如果时间片为1秒，则一个进程被响应可能需要等9秒...也就是说，如果用户在自己进程的时间片外通过键盘发出调试命令，可能需要等待9秒才能被系统响应

另一方面，进程调度、切换是有时间代价的(保存、恢复运行环境)，因此如果时间片太小，会导致进程切换过于频繁，系统会花大量的时间来处理进程切换，从而导致实际用于进程执行的时间比例减少。可见时间片也不能太小。

一般来说，设计时间片时要让切换进程的开销占比不超过1%

2. 优先级调度算法

优先级调度算法

用于作业调度的时候，选择一个处于外存后备队列当中的作业，进入内存

用于进程调度的时候，选择一个在内存的就绪队列当中的进程，为它分配处理机

非抢占式例子：

这里的优先数越大，优先级越高只是本题规定的

优先级调度算法-非抢占式例子

抢占式例子：

优先级调度算法-抢占式例子
补充一点点喵

3. 多级反馈队列调度算法

思考🤔
  • Multileveled Feedback Queue
多级反馈队列调度算法
多级反馈队列调度算法例题
多级反馈队列调度算法调度过程

4. 三种算法的对比总结

三种算法的对比总结

5. 补充：多队列调度算法

  • Multilevel queue scheduling

单个就绪队列无法满足用户对进程调度策略的不同要求；将就绪队列分成多个队列，提出多级队列调度算法

多队列调度算法

固定优先级：一般不用固定优先级，比如你打字打着打着有个系统进程要运行，那你就不能打字了

时间片划分，比如100ms，那么在这100ms每个优先级的进程都会被至少响应一次

2.3 进程的同步与互斥

2.3.1 进程的同步与互斥

1. 进程同步

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

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

一个简单的例子来理解这个概念。 例如，让系统计算1 + 2 * 3，假设系统产生两个进程:一个是加法进程，一个是乘法进程。要让计算结果是正确的，一定要让加法进程发生在乘法进程之后，但实际上操作系统具有异步性，若不加以制约，加法进程发生在乘法进程之前是绝对有可能的，因此要制定一定的机制去约束加法进程，让它在乘法进程完成之后才发生。

2. 进程互斥

  • 互斥，亦称间接制约关系。
  • 进程互斥指当一个进程访问某临界资源时，另一个想要访问该临界资源的进程必须等待。当前访问临界资源的进程访问结束，释放该资源之后，另一个进程才能去访问临界资源。
进程互斥
  • 临界资源(Critical Resouce)
    • 许多硬件资源如打印机、 磁带机等，都属于临界资源
    • 进程间应采取互斥方式，实现对这类资源的共享。
    • 软件资源如信号量，共享变量等
  • 临界区(critical section)
    • 不论是硬件临界资源还是软件临界资源，多个进程必须互斥地对它进行访问；每个进程中访问临界资源的那段代码称为临界区。
image-20231210204357574

为了禁止两个进程同时进入临界区，实现对临界资源的互斥访问，同时保证系统整体性能，需要遵循以下原则：

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

2.3.2 进程互斥的软件实现方法

这部分书上其实就一句话：软件方法能解决诸如进程互斥进入临界区的问题，但有一定难度，并且存在很大的局限性，因而现在已很少采用。

所以期末考试是不会考的，但王道讲了的话说明在408的范围内🧐🧐

进程互斥的软件实现方法

1. 单标志法

单标志法
单标志法

2. 双标志先检查法

双标志先检查法

如果能让 “检查” 和 “上锁”一气呵成，那其实这个算法就没啥问题了，下一小节的硬件实现方法就实现了

3. 双标志后检查法

双标志后检查法

4. Peterson算法

Peterson算法

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

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

2.3.3 进程互斥的硬件实现方法

1. 中断屏蔽方法

中断屏蔽方法

关中断方法的缺点：

① 滥用关中断权力可能导致严重后果；

② 关中断时间过长，会影响系统效率，限制了处理器交叉执行程序的能力；

③ 不适用于多CPU系统，因为在一个处理器上关中断并不能防止进程在其它处理器上执行相同的临界段代码。

2. Test-and-Set指令

TestAndSet 简称 TS 指令，也有地方称为 TestAndSetLock 指令，或 TSL 指令

TSL 指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成。

以下是用C语言描述的逻辑：

1
2
3
4
5
6
7
8
9
// 布尔型共享变量 lock 表示当前临界区是否被加锁
// true 表示已经加锁， false 表示未加锁
bool TestAndSet(bool *lock)
{
    bool old;            
    old = *lock;          // 用于存放lock 原来的值
    *lock = true;         // 无论之前是否已经加锁，都将lock值设为true
    return old;           // 返回lock原来的值
}

以下是使用TSL指令，实现互斥的算法逻辑：

1
2
3
4
while (TestAndSet(&lock));        // “上锁”并“检查”
临界区代码段...
lock = false;                     // “解锁”
剩余区代码段...

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

简而言之：

假设lock现在为false，代表临界资源A空闲，那么我就可以访问这个资源，同时将lock=true，提醒别的进程，这个临界资源A我正在使用，你先别急，等等，然后用完之后再lock = false; ，解锁，让别人能用

假设lock为true，代表临界资源正在有人使用，所以我必须等待，并且将lock=true，这无所谓，反正已经是true了

lock=true这个语句只是为了让lock为false时可以上锁

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

  • 优点：实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞；适用于多处理机环境
  • 缺点：不满足“让权等待”原则，暂时无法进入临界区的进程会占用CPU并循环执行 TSL 指令，从而导致“忙等”。

3. Swap指令

有的地方也叫 Exchange 指令，或简称 XCHG 指令。 Swap 指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成。

以下是用C语言描述的逻辑：

1
2
3
4
5
6
7
8
9
// swap原语
// swap指令的作用是交换两个变量的值
void Swap (bool *a, bool *b)
{
    bool temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

以下是使用Swap指令 实现互斥的算法逻辑， lock表示当前临界区是否被加锁

1
2
3
4
5
6
7
8
// true 表示已经加锁， false 表示未加锁
bool old = true;
while (old == true){
    Swap (&lock, &old);
}
临界区代码段...
lock = false;
剩余区代码段...

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

清晰地说：

① old是每个进程都要进行的一步，都必须将old=true

② 因为lock是某一特定临界资源的共享变量，当每一个进程准备访问这个特定的临界资源时，初始化old=true，然后进入while循环进行交换

③ 如果当前lock是false，则交换后old=false，则当前进程可以跳出循环进入临界区代码段，同时因为交换，lock=old=true上锁，不让别的进程来打扰，别的进程会因为lock变为true，一直在while循环等待

④ 当使用完临界资源，则将lock=false，此时别的进程再交换old和lock就能再判断old=false，就又进入了③步骤，可以跳出循环，使用临界资源。

优缺点跟Test-and-Set指令一样，因为他俩逻辑上是基本一样的东西

  • 优点：实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞；适用于多处理机环境
  • 缺点：不满足“让权等待”原则，暂时无法进入临界区的进程会占用CPU并循环执行Swap指令，从而导致“忙等”。

*互斥🔒总结

前面的七种方式其实都是🔒，下面对他们统一总结：

解决临界区最简单的工具就是互斥锁 (mutex lock)。

一个进程在进入临界区时应获得锁，在退出临界区时释放锁。函数 acquire()获得锁，而函数 release()释放锁。

每个互斥锁有一个布尔变量 available，表示锁是否可用。如果锁是可用的，调用 acquire()会成功，且锁不再可用。当一个进程试图获取不可用的锁时，会被阻塞，直到锁被释放。

1
2
3
4
5
6
7
8
9
acquire(){
	while(!available)
           ;          //忙等待              
	available = false;  //获得锁
}
release(){
    available = true;  //释放锁
}

acquire()或 release()的执行必须是原子操作，因此互斥锁通常采用硬件机制来实现。

互斥锁的主要缺点是忙等待，当有一个进程在临界区中，任何其他进程在进入临界区时必须连续循环调用 acquire()。当多个进程共享同一 CPU 时，就浪费了CPU 周期。因此，互斥锁通常用于多处理器系统，一个线程可以在一个处理器上等待，不影响其他线程的执行。

需要连续循环忙等的互斥锁，都可称为自旋锁 (spin lock) ，如TSL指令、swap指令、单标志法

特性:

  • 需忙等，进程时间片用完才下处理机，违反“让权等待“
  • 优点：等待期间不用切换进程上下文，多处理器系统中，若上锁的时间短，则等待代价很低，
  • 常用于多处理器系统，一个核忙等，其他核照常工作，并快速释放临界区
  • 不太适用于单处理机系统，忙等的过程中不可能解锁

怎么感觉上面这部分总结有点不太懂啊，标记一处地点🐕💧

2.3.4 信号量机制

0. 前期总结

知识总览

为什么引入信号量机制？

  • 为了更好的解决进程互斥与同步的问题

1. 信号量机制

用户进程可以通过使用操作系统提供的一对原语来对信号量（Semaphore）进行操作，从而很方便的实现了进程互斥、进程同步。

  • 信号量其实就是一个变量，可以用一个信号量（可以是一个整数，也可以是更复杂的记录型变量）来表示系统中某种资源的数量，比如：系统中只有一台打印机，就可以设置一个初值为 1 的信号量。
  • 原语是一种特殊的程序段，其执行只能一气呵成，不可被中断。原语是由关中断/开中断指令实现的。软件解决方案的主要问题是“进入区的各种操作无法一气呵成”，因此如果能把进入区、退出区的操作都用“原语”实现，使这些操作能“一气呵成”就能避免问题。

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

wait、signal 原语常简称为 P、V操作（来自荷兰语 proberen 和 verhogen）。

常把wait(S)、signal(S) 两个操作分别写为 P(S)、V(S)。

2. 整型信号量

用一个整数型的变量作为信号量，用来表示系统中某种资源的数量。

与普通整数变量的区别：对信号量的操作只有三种，即 初始化、P操作、V操作。

eg：某计算机系统中有一台打印机

1
2
3
4
5
6
7
8
9
10
int S = 1;                // 初始型整型信号量s，表示当前系统中可用的打印机资源数

void wait (int S){         // wait 原语，相当于“进入区”
    while (S <= 0);       // 如果资源数不够，就一直循环等待
    S--;                  // 如果资源数够，则占用一个资源
}

void signal (int S){      // signal 原语，相当于“退出区”
    S++;                // 使用完资源后，在退出区释放资源
}

进程 P0 ：

1
2
3
4
5
// ...
wait (S);                 // 进入区，申请资源
// 使用打印机资源...       // 临界区，访问资源
signal(S);                // 退出区，释放资源
// ...

当P0在访问打印机资源的时候，假如说发生了进程切换，有另外的进程，比如进程 P1，它也想使用打印机这种资源，所以使用之前先执行wait (S); ，但是打印机已经被P0占用了，S是0，就一直循环等待，直到P0进程把打印机资源释放

1
2
3
4
5
// ...
wait (S);                // 进入区，申请资源
// 使用打印机资源...      // 临界区，访问资源
signal(S);               // 退出区，释放资源
// ...

...

进程 Pn （执行过程跟P1一样）：

1
2
3
4
5
// ...
wait (S);                // 进入区，申请资源
// 使用打印机资源...      // 临界区，访问资源
signal(S);               // 退出区，释放资源
// ...

在任何一个进程开始执行的时候，进入程序内部执行检查操作，检查信号量资源是否被完全占据，如果被占据，就一直忙等待，等有空闲信号量资源的时候，再占据这个信号量。“检查”和“上锁”一气呵成，避免了并发、异步导致的问题。（双标志先检查法的改进，用一个原语来实现的）

存在的问题：不满足“让权等待”原则，会发生“忙等”（忙等，busy wait，当一个进程正处在某临界区内，任何试图进入其临界区的进程都必须进入代码连续循环，陷入忙等状态，连续测试一个变量直到某个值出现为止）。

3. 记录型信号量⭐

整型信号量的缺陷是存在“忙等”问题，因此人们又提出了“记录型信号量”，即用记录型数据结构表示的信号量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/* 记录型信号量的定义 */
typedef struct {
    int value;                 // 剩余资源数，S.value 的初值表示系统中某种资源的数目。
    struct process *L;         // 等待队列
} Semaphore;

/* 某进程需要使用资源时，通过wait原语申请 */
void wait(Semaphore S) {
    S.value--;
    if (S.value < 0) {
        block (S.L);  
        //如果剩余资源数不够，使用block原语使进程从运行态进入阻塞态，并挂到信号量S的等待队列（即阻塞队列）中。
    }
}

/*进程使用完资源后，通过signal 原语释放*/
void signal (Semaphore S) {
    s.value++;
    if (S.value <= 0) {
        wakeup(S.L);
        //释放资源后，若还有别的进程在等待这种资源，则使用wakeup原语唤醒等待队列中的一个进程，该进程从阻塞态变为就绪态。
    }
}
  • 一个例子
记录型信号量例子

可以去看原视频，更好理解

最初：

  1. 剩余资源数：2
  2. 等待队列：->null

P0进程申请：

  1. 执行wait(S)原语，value--，剩余资源数：1，等待队列：->null
  2. 把红色打印机分配给P0

P1进程申请：

  1. 执行wait(S)原语，value--，剩余资源数：0，S.value=0，资源恰好分配完，等待队列：->null
  2. 把绿色打印机分配给P1

P2进程申请：

  1. 执行wait(S)原语，value--，剩余资源数：-1，S.value = -1，
  2. 因为S.value < 0，执行block (S.L); ，等待队列：->P2

P3进程申请：

  1. 执行wait(S)原语，value--，剩余资源数：-2，S.value = -2，
  2. 因为S.value < 0，执行block (S.L); ，等待队列：->P2->P3

假设P0进程使用完打印机了，

  1. 执行signal(S)原语，value++，剩余资源数：-1，S.value = -1，还是小于等于0，说明等待队列当中还是有进程等待
  2. 执行signal(S)原语中的 wakeup(S.L);，用于唤醒信号量对应的等待队列当中队头的进程P2，P2由阻塞态变为就绪态，等待队列：->P3
  3. 把红色打印机分配给P2

假设P2进程使用完打印机了，

  1. 执行signal(S)原语，value++，剩余资源数：0，S.value = 0，还是小于等于0，说明等待队列当中还是有进程等待
  2. 执行signal(S)原语中的 wakeup(S.L);，用于唤醒信号量对应的等待队列当中队头的进程P3，等待队列：->null
  3. 把红色打印机分配给P3

如果之后CPU又回到为P1服务，P1也用完了打印机

  1. 执行signal(S)原语，value++，剩余资源数：1，S.value = 1，这时大于0了，说明等待队列当中已经没有进程等待
  2. 所以在执行signal(S)原语时，不需要执行 wakeup(S.L);
  3. P1继续往下执行，结束

之后CPU为P3服务，P3也用完了打印机

  1. 执行signal(S)原语，value++，剩余资源数：2，S.value = 2，这时大于0了，说明等待队列当中已经没有进程等待
  2. 所以在执行signal(S)原语时，不需要执行 wakeup(S.L);
  3. P3继续往下执行，结束

对信号量 S 的一次 P 操作意味着进程请求一个单位的该类资源，因此需要执行 S.value--，表示资源数减1，当S.value < 0 时表示该类资源已分配完毕，因此进程应调用 block 原语进行自我阻塞（当前运行的进程从运行态 -> 阻塞态），主动放弃处理机，并插入到该类资源的等待队列 S.L 中。

可见，该机制遵循了“让权等待”原则，不会出现“忙等”现象。

对信号量 S 的一次 V操作意味着进程释放一个单位的该类资源，因此需要执行S.value++，表示资源数加1，若加1后仍是 S.value <= 0，表示依然有进程在等待该类资源，因此应调用wakeup 原语唤醒等待队列中的第一个进程（被唤醒进程从阻塞态 -> 就绪态）。

注：若考试中出现 P(S)、V(S)的操作，除非特别说明，否则默认S 为记录型信号量

2.3.5 信号量的应用

1. 信号量机制实现进程互斥

实现方法

  • 分析并发进程的关键活动，划定临界区（如：对临界资源打印机的访问就应放在临界区）
  • 设置互斥信号量 mutex，初值为 1
  • 在进入区 P(mutex) —— 申请资源
  • 在退出区 V(mutex) —— 释放资源

信号量 mutex 表示“进入临界区的名额”。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/*记录型信号量的定义*/
typedef struct {
    int value;                // 剩余资源数
    struct process *L;        // 等待队列
} Semaphore;


/* 信号量机制实现互斥 */
Semaphore mutex = 1;   // 初始化信号量
//要会自己定义记录型信号量，但如果题目中没特别说明,可以把信号量的声明简写成这种形式

P1(){
    ...
    P(mutex);                // 使用临界资源前需要加锁
    临界区代码段
    V(mutex);                // 使用临界资源后需要解锁
    ...
}

P2(){
    ...
    P(mutex);
    临界区代码段
    V(mutex);
    ...
}

注意： 对不同的临界资源需要设置不同的互斥信号量。

对不同的临界资源需要设置不同的互斥信号量

P、V操作必须成对出现。缺少P(mutex) 就不能保证临界资源的互斥访问。缺少 V(mutex) 会导致资源永不被释放，等待进程永不被唤醒。

2. 信号量机制实现进程同步

进程同步：要让各并发进程按要求有序地推进。

1
2
3
4
5
6
7
8
9
10
P1(){
    代码 1;
    代码 2; 
    代码 3;
}
P2(){
    代码 4;
    代码 5; 
    代码 6;
}

比如：P1、P2 并发执行，由于存在异步性，因此二者交替推进的次序是不确定的。

若 P2 的“代码4”要基于 P1 的“代码1”和“代码2”的运行结果才能执行，那么我们就必须保证“代码4”一定是在“代码2”之后才会执行。这就是进程同步问题，让本来异步并发的进程互相配合，有序推进。

用信号量实现进程同步：

  • 分析什么地方需要实现“同步关系”，即必须保证“一前一后”执行的两个操作（或两句代码）；

  • 设置同步信号量 S，初始为 0；

  • 在“前操作”之后执行 V(S)；

  • 在“后操作”之前执行 P(S)；

    前V后P

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/* 信号量机制实现同步 */
Semaphore S = 0;

P1(){
    代码 1;
    代码 2; 
    V(S);   
    代码 3;
}

P2(){    // P2 的执行需要依赖一种信号量资源S，而这种资源只能由P1 释放，因此保证必须 P1 后再 P2
    P(S);
    代码 4;
    代码 5; 
    代码 6;
}
  • 若先执行到 V(S) 操作，则 S++ 后 S = 1。之后当执行到 P(S) 操作时，由于 S = 1，表示有可用资源，会执行 S--，S 的值变回 0，P2 进程不会执行 block 原语，而是继续往下执行代码4。

执行顺序 1、2、4、5、6。保证代码4在代码2之后执行

  • 若先执行到 P(S) 操作，由于 S = 0，S-- 后 S = -1，表示此时没有可用资源，因此P操作中会执行 block 原语，主动请求阻塞。
  • 之后当处理机交还处理进程P1，执行完代码2，继而执行 V(S) 操作，S++，使 S 变回 0，由于此时有进程在该信号量对应的阻塞队列中，因此会在 V 操作中执行 wakeup 原语，唤醒 P2 进程。这样 P2 就可以继续执行 代码4 了。

理解：信号量S代表“某种资源”，刚开始是没有这种资源的。P2需要使用这种资源，而又只能由P1产生这种资源。

3. 信号量机制实现前驱关系

其实是用信号量机制实现进程同步的升级版，多级同步问题，记住前V后P

信号量机制实现前驱关系

2.3.6 进程同步与互斥经典问题

1. 生产者-消费者问题

(1) 问题描述

系统中有一组生产者进程和一组消费者进程，生产者进程每次生产一个产品放入缓冲区，消费者进程每次从缓冲区中取出一个产品并使用。(注：这里的“产品”理解为某种数据)

  • 生产者、消费者共享一个初始为空、大小为n的缓冲区。
  • 只有缓冲区没满时，生产者才能把产品放入缓冲区，否则必须等待。
  • 只有缓冲区不空时，消费者才能从中取出产品，否则必须等待。
  • 缓冲区是临界资源，各进程必须互斥地访问。
生产者-消费者问题

(2) 问题分析

常把wait(S)、signal(S) 两个操作分别写为 P(S)、V(S)。

PV操作题目分析步骤：

  1. 关系分析。找出题目中描述的各个进程，分析它们之间的同步、互斥关系。

    生产者和消费者对缓冲区互斥访问是互斥关系，同时生产者和消费者又是一个相互协作的关系，只有生产者生产之后，消费者才能消费，它们也是同步关系。

  2. 整理思路。根据各进程的操作流程确定P、V操作的大致顺序。

    生产者每次要消耗 (P)一个空闲缓冲区，并生产(V)一个产品。

    消费者每次要消耗 (P) 一个产品，并增加一个空闲缓冲区(V)。

    往缓冲区放入/取走产品需要互斥。

  3. 设置信号量。并根据题目条件确定信号量初值。（互斥信号量初值一般为1，同步信号量的初始值要看对应资源的初始值是多少）

在这样的环境下，设置信号量如下：

1
2
3
4
5
semaphore mutex = 1;   // 互斥信号量，实现对缓冲区的互斥访问

semaphore empty = n;   // 同步信号量，表示空闲缓冲区的数量 
semaphore full = 0;    // 同步信号量，表示产品的数量，也即非空缓冲区的数量
//full表示缓冲区有多少产品，empty表示缓冲区有多少空位
前驱图

(3) 代码实现

代码实现

(4) 一些分析

实现互斥的P操作一定要在实现同步的P操作之后

如果是按照（3）中的代码

当缓冲区内已经放满产品时，则empty=0，full=n，

生产者执行P(empty)，由于已经没有空闲缓冲区，因此生产者被阻塞

由于生产者被阻塞，因此切换回消费者进程，消费者进程执行P(full)，消耗一个产品，full = n-1，

然后接着执行P(mutex);从缓冲区取出一个产品;V(mutex);，然后继续V(empty)，增加一个空闲缓冲区，然后就能回到消费者那里执行了……，完美

知识点回顾

2. 多生产者-多消费者问题

(1) 问题描述

多生产者-多消费者问题

多意思是多类

(2) 问题分析

多生产者-多消费者问题

(3) 代码实现

有mutex：

有mutex

无mutex：

无mutex

结论：即使不设置专门的互斥变量mutex，也不会出现多个进程同时访问盘子的现象

为什么有mutex和没有mutex一样呢？

  • 原因在于：本题中的缓冲区大小为1，在任何时刻，apple、 orange、 plate 三个同步信号量中最多只有一个是1。因此在任何时刻，最多只有一个进程的P操作不会被阻塞，并顺利地进入临界区

如果有两个盘子plate

如果有两个盘子plate

(4) 一些总结

总结：在生产者-消费者问题中，如果缓冲区大小为1，那么有可能不需要设置互斥信号量就可以实现互斥访问缓冲区的功能。当然，这不是绝对的，要具体问题具体分析。

建议：在考试中如果来不及仔细分析，可以加上互斥信号量，保证各进程一定会互斥地访问缓冲区。但需要注意的是，实现互斥的P操作一定要在实现同步的P操作之后，否则可能引起“死锁”。

加上互斥信号量就完事了

总结

3. 吸烟者问题

(1) 问题描述

可生产多种产品的单生产者——多消费者问题

吸烟者问题

(2) 问题分析

吸烟者问题
吸烟者问题

(3) 代码实现

吸烟者问题

(4) 一些总结

吸烟者问题可以为我们解决“可以生产多个产品的单生产者”问题提供一个思路。

值得吸取的精华是：“轮流让各个吸烟者吸烟”，必然需要：“轮流的在桌上放上组合一、二、三”，注意体会我们是如何用一个整型变量 i 实现这个“轮流”过程的。

如果题目改为“每次随机地让一个吸烟者吸烟”，我们有应该如何用代码写出这个逻辑呢？random()

若一个生产者要生产多种产品(或者说会引发多种前驱事件)，那么各个V操作应该放在各自对应的“事件”发生之后的位置。

4. 读者写者问题

(1) 问题描述

读进程之间不互斥，写进程和读进程、写进程都互斥

读者写者问题

(2) 问题分析

读者写者问题

(3) 代码实现

① 给count加mutex互斥访问

  • 为什么要加mutex——保证对count变量的互斥访问
  • 潜在的问题：读进程正在读这个文件，count的值是1，如果有一个写进程到达，由于第一个读进程已经对rw进行了P操作，rw的值变成了0，写进程在进行P(rw)，会被阻塞在这个信号量上面，如果这时再有读进程到达，因为count的值是1，读进程可以跳过P操作，执行下面的代码，如果有源源不断的读进程到达的话，都能直接执行，由于最后一个读进程读完之后才会解锁，会导致写进程饿死的现象
读者写者问题

② 加一个w实现“读写公平法”

若希望写进程优先，即当有读进程正在读共享文件时，有写进程请求访问，这时应禁止后续读进程的请求，等到已在共享文件的读进程执行完毕，立即让写进程执行，只有在无写进程执行的情况下才允许读进程再次运行。为此，增加一个信号量并在上面程序的writer()和 reader()函数中各增加一对PV操作，就可以得到写进程优先的解决程序。

读者写者问题

上面的几种情况可以自己分析一下

(4) 一些总结

读者-写者问题为我们解决复杂的互斥问题提供了一个参考思路。

其核心思想在于设置了一个计数器 count 用来记录当前正在访问共享文件的读进程数。我们可以用count 的值来判断当前进入的进程是否是第一个/最后一个读进程，从而做出不同的处理。

另外，对 count 变量的检查和赋值不能一气呵成导致了一些错误，如果需要实现“一气呵成”，自然应该想到用互斥信号量。

最后，还要认真体会我们是如何解决“写进程饥饿”问题的。

绝大多数的考研PV操作大题都可以用之前介绍的几种生产者-消费者问题的思想来解决，如果遇到更复杂的问题，可以想想能否用读者写者问题的这几个思想来解决。

5. 哲学家进餐问题

(1) 问题描述

哲学家进餐问题

(2) 问题分析

每个哲学家吃饭前依次拿起左、右两支筷子：

哲学家进餐问题

(3) 代码实现

如何防止死锁的发生呢?

① 可以对哲学家进程施加一些限制条件，比如最多允许四个哲学家同时进餐。这样可以保证至少有一个哲学家是可以拿到左右两只筷子的

② 要求奇数号哲学家先拿左边的筷子，然后再拿右边的筷子，而偶数号哲学家刚好相反。用这种方法可以保证如果相邻的两个奇偶号哲学家都想吃饭，那么只会有其中一个可以拿起第一只筷子，另一个会直接阻塞。这就避免了占有一支后再等待另一只的情况

思考代码如何实现这两种方案

③ 仅当一个哲学家左右两支筷子都可用时才允许他抓起筷子。

假设0先想吃饭，1再想吃，2再想吃：

哲学家进餐问题

假设0先想吃，4再想吃：

哲学家进餐问题

(4) 一些总结

哲学家进餐问题的关键在于解决进程死锁。

这些进程之间只存在互斥关系，但是与之前接触到的互斥关系不同的是，每个进程都需要同时持有两个临界资源，因此就有“死锁”问题的隐患。

如果在考试中遇到了一个进程需要同时持有多个临界资源的情况，应该参考哲学家问题的思想，分析题中给出的进程之间是否会发生循环等待，是否会发生死锁。

可以参考哲学家就餐问题解决死锁的三种思路。

2.3.7 管程

why

why

管程的定义及基本特征

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

  1. 局部于管程的共享数据结构说明

  2. 对该数据结构进行操作的一组过程

  3. 对局部于管程的共享数据设置初始值的语句

  4. 管程有一个名字

    跨考Tips：“过程”其实就是“函数”，可以类比于面向对象的思想

    管程当做类class

    共享数据结构当做类里面的变量

    一组过程可以看做是类里面的函数

管程的基本特征：

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

拓展

管程
管程
管程

2.4 死锁

2.4.1 死锁的概述

1. 资源竞争问题

系统中有许多不可被抢占的资源，即临界资源；如打印机、数据文件、队列、信号量等

需要采用互斥机制访问临界资源

可重用性资源和消耗性资源

  1. 可重用性资源

    • 只能分配给一个进程使用，不允许多个进程共享

    • 必须按以下顺序使用

      • 请求资源：如果请求失败，请求进程将会被阻塞

      • 使用资源：进程使用该资源

      • 释放资源：当进程使用完后自己释放资源

    • 系统中每一类可重用性资源中的单元数目是相对固定的，进程在运行期间既不能创建也不能删除它

  1. 可消耗性资源

    又称临时性资源；由进程动态创建和消耗，性质如下：

    • ① 每一类可消耗性资源的单元数目在进程运行期间是可以不断变化的
    • ② 进程可以不断创造可消耗性资源的单元，将它们放入该资源类的缓冲区中，以增加该资源类的单元数目
    • ③ 进程在运行过程中，可以请求若干个可消耗性资源单元，用于进程自己的消耗，不再将它们返回给该资源类中

​ 最典型可消耗性资源是进程间传递的消息！

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

  1. 可抢占性资源：某进程在获得这类资源后，该资源可以再被其它进程或系统抢占
  1. 不可抢占性资源：一旦系统把该类资源分配给该进程后，就不能将它强行收回，只能在进程用完后自行释放

2. 计算机系统中的死锁

① 竞争不可抢占性资源引起死锁

系统中不可抢占性资源数量不足以满足多个进程运行需要，使得进程在运行过程中，会因争夺资源而陷入僵局；如下图所示：

共享文件时的死锁情况

② 竞争可消耗资源引起死锁

图3-13示例为三个进程在利用消息通信机制进行通信时(竞争可消耗资源，即消息m)所形成的死锁情况。

进程之间通信时的死锁

③ 进程推进顺序不当引起死锁

除了多个进程对资源的竞争会引发死锁外，进程在运行过程中对资源进行申请和释放的顺序是否合法，也是系统中是否会产生死锁的一个重要因素

进程推进顺序对死锁的影响
进程推进顺序合法
进程推进顺序非法

上面其实就是说了一个问题：什么时候会发生死锁？

什么时候会发生死锁？

3. 死锁的定义

婆婆特里面的：在一组进程发生死锁的情况下，这组死锁进程中的每一个进程，都在等待另一个死锁进程所占有的资源。

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

4. 死锁、饥饿、死循环

死锁、饥饿、死循环

5. 产生死锁的必要条件

产生死锁的必要条件

​

6. 处理死锁的方法

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

2.4.2 预防死锁

  • 预防死锁的方法是通过破坏产生死锁的四个必要条件中的一个或几个，以避免发生死锁
  • 互斥条件是非共享设备所必须的特性；不仅不能改变，还应加以保证
  • 因此，死锁预防主要是破坏产生死锁的后三个条件

1.破坏互斥条件

不建议这样做

破坏互斥条件

2. 破坏不可剥夺条件

不可剥夺条件又称 不可抢占条件

不剥夺条件：进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放。

破坏不剥夺条件：

方案一：当某个进程请求新的资源得不到满足时，它必须立即释放保持的所有资源，待以后需要时再重新申请。也就是说，即使某些资源尚未使用完，也需要主动释放，从而破坏了不可剥夺条件。

方案二：当某个进程需要的资源被其他进程所占有的时候，可以由操作系统协助，将想要的资源强行剥夺。这种方式一般需要考虑各进程的优先级(比如：剥夺调度方式，就是将处理机资源强行剥夺给优先级更高的进程使用)

该策略的缺点：

  1. 实现起来比较复杂。
  2. 释放已获得的资源可能造成前一阶段工作的失效。因此这种方法一般只适用于易保存和恢复状态的资源，如CPU。
  3. 反复地申请和释放资源会增加系统开销，降低系统吞吐量。
  4. 若采用方案一，意味着只要暂时得不到某个资源，之前获得的那些资源就都需要放弃，以后再重新申请。如果一直发生这样的情况，就会导致进程饥饿。

3. 破坏请求和保持条件

破坏请求和保持条件

4. 破坏循环等待条件

破坏循环等待条件

2.4.3 避免死锁

  • 属于事先预防的策略，但并不是事先采取某种限制措施去破坏产生死锁的必要条件
  • 是在资源动态分配过程中，防止系统进入不安全状态，以避免发生死锁
  • 这种方法所施加的限制条件较弱，可能获得较好的系统性能；目前常用此方法来避免发生死锁

1. 系统安全状态

  • 把系统的状态分为安全状态和不安全状态
  • 当系统处于安全状态时，可避免发生死锁；当系统处于不安全状态时，则可能进入到死锁状态

① 安全状态

  • 定义：系统能按某种进程推进顺序为每个进程分配所需资源，使进程都能顺利完成。若存在该顺序，则系统处于安全状态; 否则，处于不安全状态
  • 允许进程动态地申请资源，但系统在进行资源分配之前应先计算此次资源分配的安全性

② 安全状态示例

安全状态示例

P2---P1----P3

总结：

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

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

如果系统处于安全状态，就一定不会发生死锁。如果系统进入不安全状态，就可能发生死锁 (处于不安全状态未必就是发生了死锁，但发生死锁时一定是在不安全状态)

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

2. 银行家算法

Dijkstra在1965年提出的银行家算法是著名的死锁避免算法，这个用于一个银行家给多个顾客贷款的算法可以直接用于操作系统给进程分配资源，这时只要把银行家换成操作系统，把顾客换成进程，把资金换成资源，把银行家决定是否放贷时所用的判断过程（即判断顾客是否有信誉和偿还能力）换成操作系统决定是否分配资源时所用的判断过程（即判断进程是否能及时归还资源）即可。

银行家算法的实质就是要设法保证系统动态分配资源后不进入不安全状态，以避免可能产生的死锁。

例子

银行家算法
银行家算法

银行家算法中的数据结构

为了实现银行家算法，在系统中必须设置这样四个数据结构：

1）Available向量：系统中可利用的资源数目，长度为m的一维数组

2）Max矩阵：每个进程对每种资源的最大需求，n*m的矩阵

3）Allocation矩阵：每个进程已分配的各类资源的数目，n*m的矩阵

4）Need矩阵：每个进程还需要的各类资源数，Need[i,j] = Max[i,j] - allocation[i, j]

5）Request：表示进程此次申请的各种资源数，长度为m的一维数组

银行家算法的描述

初试数据
银行家算法

image-20231107162817252
image-20231107162835370

银行家算法流程图表示

image-20231107162637053

银行家算法的程序实现

数据结构：

  1. 可用资源向量Available,这是一个一维数组Available[j],j=1,…m，表示第j种资源的可用数量，其中m为资源的种类个数
  2. 最大资源需求矩阵Max,这是一个n*m的二维数组，其中n为进程个数。单元Max[i,j]存储的数值表示第i个进程最多需要多少第j种资源
  3. 分配矩阵Allocation，这是一个n*m的二维数组。单元Allocation[i,j]存储的是已经分配给第i个进程的第j种资源的数量
  4. 需求矩阵Need，这也是一个n*m的矩阵，单元Need[i,j]存储的数值表示进程i还需要多少第j种资源的数量才能完成退出。
1
//詹姆斯？

可以看一下b站这个视频，做题是话应该够了：

操作系统-银行家算法_哔哩哔哩_bilibili

2.4.4 死锁的检测和解除

如果在系统中，既不采取死锁预防措施也未配有死锁避免算法，系统很可能会发生死锁；在这种情况下，系统应当提供两个算法：

① 死锁检测算法：用于检测系统状态，以确定系统中是否发生了死锁

② 死锁解除算法：当认定系统中已发生了死锁，利用该算法可将系统从死锁状态中解脱出来

1. 死锁的检测

死锁的检测

如果系统中剩余的可用资源数足够满足进程的需求，那么这个进程暂时是不会阻塞的，可以顺利地执行下去。

如果这个进程执行结束了把资源归还系统，就可能使某些正在等待资源的进程被激活，并顺利地执行下去。相应的，这些被激活的进程执行完了之后又会归还一些资源，这样可能又会激活另外一些阻塞的进程...

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

如果最终不能消除所有边，那么此时就是发生了死锁，最终还连着边的那些进程就是处于死锁状态的进程

  • 举个例子，可以消除所有边，即无死锁发生
死锁的检测
  • 举个例子，不可消除所有边，即产生死锁
死锁的检测
死锁的检测

2. 死锁的解除

死锁的解除

参考：

《王道操作系统》学习笔记总目录+思维导图_王道操作系统思维导图-CSDN博客

详解操作系统之银行家算法（附流程图） (zhihu.com)

2.1_2_进程的状态与转换、进程的组织_哔哩哔哩_bilibili

【OS 操作系统】047 | 进程同步与互斥 - 知乎 (zhihu.com)

操作系统
#操作系统
操作系统 2 进程管理
http://viper2383.github.io/2023/11/07/操作系统 2 进程管理/
作者
w1per3
发布于
2023年11月7日
许可协议