Loading... ## 进程 ### 进程的基本概念 - **程序**是存放在磁盘内的可执行文件，是**静态的**。 - **进程**是程序的**一次执行过程**，是**动态的**。 #### 进程的组成 - 当进程被创建时，操作系统会为该进程分配一个唯一的、不重复的 “身份证号” —— PID (Process ID，进程 ID ) 。 - 操作系统需要记录 PID ，以及进程所属用户 ID (UID) 。根据这两个进程的基本描述信息，可以让操作系统区分各个进程。 - 除此之外，操作系统还会记录给进程分配了哪些资源 (如分配了多少内存、正在使用哪些 I/O 设备、正在使用哪些文件) ，从而实现操作系统对资源的管理。 - 操作系统还会记录进程的运行情况 (如：CPU 使用时间、磁盘使用情况、网络流量使用情况等) ,可用于实现操作系统对进程的控制和调度。 上述这些信息都被保存在一个数据结构 **PCB (Process Control Block)** 中，即**进程控制块**。操作系统需要对各个并发运行的进程进行管理，但凡管理时所需要的信息，都会被放在 PCB 中。 ![操作系统对进程进行管理工作所需的信息都存在 PCB 中][1] > **PCB 是进程存在的唯一标志**，当进程被创建时，操作系统为其创建 PCB ，当进程结束时，会回收其 PCB 。 除了 PCB ，进程中还有两个成分：程序段和数据段。 ![image-20241016210740575.png][2] > PCB 是给操作系统用的，儿程序段和数据段是给进程自己用的。 一个进程实体（进程映像）由PCB、程序段、数据段组成。 - 进程是动态的，进程实体（进程映像）是静态的。 - 进程实体反应了进程在某一时刻的状态。 > 一般来说认为进程和进程实体是同一个东西。 #### 进程的特征 程序是静态的，进程是动态的，相比于程序，进程拥有以下特征： - **动态性**：进程是程序的一次执行过程，是动态地产生，变化和消亡的。 动态性是进程最基本的特征。 - **并发性**：内存中有多个进程实体，各进程可并发执行。 - **独立性**：进程是能独立运行，独立获得资源，独立接受调度的基本单位。 - **异步性**：各进程按各自独立的，不可预知的速度向前推进，操作系统要提供 "进程同步机制" 来解决异步问题。 异步性会导致并发程序执行结果的不确定性。具体见 "进程同步" 相关小节。 - **结构性**：每个进程都会配置一个 PCB 。结构上看，进程由程序段，数据段，PCB 组成。 #### 小结 ![image-20241016212708060.png][3] ### 进程的状态与转换 #### 进程的状态 - 进程正在被创建时，它的状态是 “**创建态**” ，在这个阶段操作系统会为进程分配资源、初始化 PCB - 当进程创建完成后，便进入 “**就绪态**”，处于就绪态的进程已经具备运行条件，但由于没有空闲 CPU ，就暂时不能运行。 - 如果一个进程此时在CPU上运行，那么这个进程处于 “**运行态**”。CPU 会执行该进程对应的程序（执行指令序列） - 在进程运行的过程中，可能会请求等待某个事件的发生（如等待某种系统资源的分配，或者等待其他进程的响应）。在这个事件发生之前，进程无法继续往下执行，此时操作系统会让这个进程下 CPU ，并让它进入 “**阻塞态**” 。 当 CPU 空闲时，又会选择另一个 “**就绪态**” 进程上 CPU 运行。 - 一个进程可以执行 `exit` 系统调用，请求操作系统终止该进程。此时该进程会进入“**终止态**”，操作系统会让该进程下 CPU ，并回收内存空间等资源，最后还要回收该进程的 PCB 。当终止进程的工作完成之后，这个进程就彻底消失了。 ![image-20241017011633479.png][4] **进程 PCB 中，会有一个变量 `state` 来表示进程的当前状态**。如：1 表示创建态、2 表示就绪态、3 表示运行态等。 #### 进程状态之间的转换 ![image-20241017011323076.png][5] - **阻塞态到就绪态**不是进程本身可以控制的，是一种**被动行为**。 - **运行态到阻塞态**是一种进程自身做出的**主动行为**。 - **不能由阻塞态直接转换为运行态，也不能由就绪态直接转换为阻塞态**。 #### 进程的组织 为了对同一个状态下的各个进程进行统一的管理，操作系统会将各个进程的 PCB 组织起来。常用的组织方法有两种：链接方式和索引方式。 **链接方式**：按照进程状态将 PCB 分为多个队列；操作系统持有指向各个队列的指针。 ![image-20241017012035038.png][6] **索引方式**：根据进程状态的不同，建立几张索引表；操作系统持有指向各个索引表的指针。 ![image-20241017012054690.png][7] #### 小结 ![image-20241017012227269.png][8] ### 进程控制 #### 基本概念 **原语**：原语是一种特殊的程序，它的执行具有**原子性**。也就是说，这段程序的运行必须一气呵成，不可中断。 > 可以用 “关中断指令” 和 “开中断指令” 这两个特权指令实现原子性。 进程控制的过程要 "一气呵成" ，不能被打断。否则就有可能导致操作系统中的某些关键数据结构信息不统一的情况，这会影响操作系统进行别的管理工作。 因此进程控制可以用原语来实现，原语的原子性保证了执行过程中不会被其他进程所打断。 原语所做的事就三类： 1. 更新 PCB 中的信息 - 所有的进程控制原语一定都会修改进程状态标志 - 剥夺当前运行进程的 CPU 使用权必然需要保存其运行环境 - 某进程开始运行前必然要恢复期运行环境 2. 将 PCB 插入合适的队列 3. 分配 / 回收资源 #### 进程控制相关的原语 ##### 进程创建 ![image-20241017130009138.png][9] ##### 进程终止 ![image-20241017130033840.png][10] ##### 进程阻塞和唤醒 ![image-20241017130053842.png][11] ##### 进程切换 ![image-20241017130113758.png][12] #### 小结 ![image-20241017131408249.png][13] ### 进程通信 进程间通信（Inter-Process Communication， IPC）是指两个进程之间产生数据交互。 进程是分配系统资源的单位（包括内存地址空间），因此**各进程拥有的内存地址空间相互独立**。为了保证安全，**一个进程不能直接访问另一个进程的地址空间**。因此进程间通信需要操作系统的支持。 #### 共享存储 **基于数据结构的共享**：比如共享空间里只能放一个长度为 10 的数组。这种共享方式速度慢、限制多，是一种**低级通信**方式。 **基于存储区的共享**：操作系统在内存中划出一块共享存储区，数据的形式、存放位置都由通信进程控制，而不是操作系统。这种共享方式速度很快，是一种**高级通信**方式。 ![image-20241017161143864.png][14] 为避免出错，各个进程对共享空间的**访问**应该是**互斥**的。各个进程可使用操作系统内核提供的同步互斥工具（如P、V操作）。 #### 消息传递 进程间的数据交换以**格式化的消息** (Message) 为单位。进程通过操作系统提供的 “发送消息 / 接收 消息” 两个**原语**进行数据交换。 ![image-20241017162134988.png][15] ##### 直接通信方式 消息发送进程要指明接收进程的 ID 。 ![image-20241017162433588.png][16] 1. 进程 P 执行发送原语 `send(Q, msg)` 。 2. 操作系统内核将该消息挂入进程 Q 的消息队列中。 3. 进程 Q 执行接收原语 `receive(P, &msg)` 。 4. 操作系统从消息队列中找到 P 发来的消息，并将该消息写入`&msg` 中。 ##### 间接通信方式 通过 "信箱" 间接地通信。因此又称 "信箱通信方式" 。 ![image-20241017163320245.png][17] 可以多个进程往同一个信箱 send 消息，也可以多个进程从同一个信箱中 receive 消息。 #### 管道通信 ![image-20241017163534447.png][18] 1. 管道只能采用**半双工通信**，某一时间段内只能实现单向的传输。如果要实现**双向同时通信**，则**需要设置两个管道**。 2. 各进程要**互斥**地访问管道（由操作系统实现） 3. 当**管道写满**时，**写进程将阻塞**，直到读进程将管道中的数据取走，即可唤醒写进程。 4. 当**管道读空**时，**读进程将阻塞**，直到写进程往管道中写入数据，即可唤醒读进程。 5. 管道中的数据一旦被读出，就彻底消失。因此，当多个进程读同一个管道时，可能会错乱。对此，通常有两种解决方案： - 一个管道允许多个写进程，一个读进程。(2014年408真题高教社官方答案) - 允许有多个写进程，多个读进程，但系统会让各个读进程轮流从管道中读数据。(Linux 的方案) > 和共享内存的区别：共享内存是一片内存，可以在该内存内任意一个地方读写；而管道是受限的的空间，类似于一个循环队列。 #### 小结 ![image-20241017164410875.png][19] ## 线程 ### 线程的基本概念 进程是程序的一次执行，有的进程可能需要 “同时” 做很多事，而传统的进程只能串行地执行一系列程序。因此，引入了 “线程” 来增加并发度。 > 传统进程是程序执行流的最小单位，但引入线程后，**线程成为了程序执行流的最小单位**。 **线程**是一个**基本的 CPU 执行单元**，也是**程序执行流的最小单位**。引入线程之后，不仅是进程之间可以并发，**进程内的各线程之间也可以并发**，从而进一步**提升了系统的并发度**，使得一个进程内也可以并发处理各种任务。 引入线程后，**进程**只作为**除 CPU 之外的系统资源的分配单元**（如打印机、内存地址空间等都是分配给进程的），**线程**则作为**处理机的分配单元**。 ![image-20241017170539215.png][20] ### 线程的属性 ![image-20241017170635419.png][21] ### 线程的实现方式 #### 用户级线程 早期的操作系统（如：早期Unix）只支持进程，不支持线程。当时的“线程”是由线程库实现的。 一个简单的例子： ```c++ int main() { int i = 0; while (true) { if (i == 0) { // process first function } if (i == 1) { // process second function } if (i == 3) { // process third function } i = (i + 1) % 3; } } ``` 从代码的角度看，线程其实就是一段代码逻辑。上述三段代码逻辑上可以看作三个 “线程” 。while 循环就是一个最弱智的 “线程库” ，线程库完成了对线程的管理工作（如调度）。很多编程语言提供了强大的线程库，可以实现线程的创建、销毁、调度等功能。 ![image-20241017192741628.png][22] - 用户级线程由应用程序通过线程库实现，所有的**线程管理工作都由应用程序负责**（包括线程切换） - 用户级线程中，**线程切换**可以在**用户态下即可完成**，无需操作系统干预。 - 在用户看来是有多个线程。但是在**操作系统内核**看来，并**意识不到线程的存在**。“用户级线程” 就是 “从用户视角看能看到的线程” 。 - 优缺点： - **优点**：用户级线程的切换在用户空间即可完成，不需要切换到核心态，线程管理的系统开销小，效率高。 - **缺点**：当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高。多个线程不可在多核处理机上并行运行。 #### 内核级线程 内核级线程（Kernel-Level Thread, KLT，又称 “内核支持的线程”）。目前大多数现代操作系统都实现了内核级线程，如 Windows、Linux 。 ![image-20241017192916071.png][23] 1. **内核级线程的管理工作**由**操作系统内核**完成。 2. 线程调度、切换等工作都由内核负责，因此**内核级线程的切换**必然需要在**核心态**下才能完成。 3. 操作系统会为每个内核级线程建立相应的 TCB（Thread Control Block，线程控制块）， 通过 TCB 对线程进行管理。“**内核级线程**” 就是 “**从操作系统内核视角看能看到的线程**” 。 4. 优缺点 - **优点**：当一个线程被阻塞后，别的线程还可以继续执行，并发能力强。多线程可在多核处理机上并行执行。 - **缺点**：一个用户进程会占用多个内核级线程，线程切换由操作系统内核完成，需要切换到核心态，因此线程管理的成本高，开销大。 ### 多线程模型 在支持内核级线程的系统中，根据用户级线程和内核级线程的映射关系，可以划分为几种多线程模型。 #### 一对一模型 一个用户级线程映射到一个内核级线程。每个用户进程有与用户级线程同数量的内核级线程。 **优点**：当一个线程被阻塞后，别的线程还可以继续执行，并发能力强。多线程可在多核处理机上并行执行。 **缺点**：一个用户进程会占用多个内核级线程，线程切换由操作系统内核完成，需要切换到核心态，因此线程管理的成本高，开销大。 #### 多对一模型 多个用户级线程映射到一个内核级线程。且一个进程只被分配一个内核级线程。 **优点**：用户级线程的切换在用户空间即可完成，不需要切换到核心态，线程管理的系统开销小，效率高 **缺点**：当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高。多个线程不可在多核处理机上并行运行 > 操作系统只 “看得见” 内核级线程，因此**只有内核级线程才是处理机分配的单位**。 #### 多对多模型 $n$ 用户级线程映射到 $m$ 个内核级线程 ($n \geq m$) 。每个用户进程对应 $m$ 个内核级线程。 克服了多对一模型并发度不高的缺点（一个阻塞全体阻塞），又克服了一对一模型中一个用户进程占用太多内核级线程，开销太大的缺点。 用户级线程是 “代码逻辑” 的载体，内核级线程是 “运行机会” 的载体。一段“代码逻辑”只有获得了“运行机会”才能被 CPU 执行。 > 内核级线程才是处理机分配的单位。 内核级线程中可以运行任意一个有映射关系的用户级线程代码，只有**所有内核级线程**中正在运行的代码逻辑都**阻塞**时，这个**进程才会阻塞**。 #### 小结 ![image-20241017193902250.png][24] ### 线程的状态与转换 类似进程的状态与转换。 ![image-20241017194016746.png][25] ### 线程的组织与控制 同样也是类似进程的组织与控制。 ![image-20241017194115620.png][26] ## 处理机调度 当有一堆任务要处理，但由于资源有限，这些事情没法同时处理。这就需要确定某种规则来决定处理 这些任务的顺序，这就是 “调度” 研究的问题。 ### 调度的三个层次 - **高级调度 (作业调度)** ：按一定的原则从外存的作业后备队列中挑选一个作业调入内存，并创建进程。每个作业只调入一次，调出一次。作业调入时会建立 PCB ，调出时才撤销 PCB 。 内存空间有限，有时无法将用户提交的作业全部放入内存，因此需要作业调度。 > 多个程序需要启动，应该先启动哪一个。 - **中级调度 (内存调度)** ：按照某种策略决定将哪个处于挂起状态的进程重新调入内存。一个进程可能会被多次调出、调入内存，因此中级调度**发生的频率要比高级调度更高**。 内存不够时，可将某些进程的数据调出外存。等内存空闲或者进程需要运行时再重新调入内存。暂时调到外存等待的进程状态为**挂起状态**。被挂起的进程PCB会被组织成**挂起队列**。 - **低级调度 (进程调度/处理机调度)** ：按照某种策略从就绪队列中选取一个进程，将处理机分配给它。 进程调度是操作系统中**最基本的一种调度**，在一般的操作系统中都必须配置进程调度。进程调度的**频率很高**，一般几十毫秒一次。 **三层调度的联系与对比** | | 要做什么 | 调度发生在哪 | 发生频率 | 对进程状态的影响 | | ------------------- | ------------------------------------------------------------ | ---------------------------------- | -------- | ----------------------------------------------------------- | | 高级调度 (作业调度) | 按照某种规则，从后备队列中选择合适的作业将其调入内存，并为其创建进程。 | 外存 $\rightarrow$ 内存 (面向作业) | 最低 | 无 $\rightarrow$ 创建态 $\rightarrow$ 就绪态 | | 中级调度 (内存调度) | 按照某种规则，从挂起队列中选择合适的进程将其数据调回内存。 | 外存 $\rightarrow$ 内存 (面向进程) | 中等 | 挂起态 $\rightarrow$ 就绪态 (阻塞挂起 $\rightarrow$ 阻塞态) | | 低级调度 (进程调度) | 按照某种规则，从就绪队列中选择一个进程为其分配处理机 | 内存 $\rightarrow$ CPU | 最高 | 就绪态 $\rightarrow$ 运行态 | ### 进程的七状态模型 > 了解即可 暂时调到外存等待的进程状态为挂起状态（挂起态，suspend）。挂起态又可以进一步细分为**就绪挂起、阻塞挂起**两种状态。 ![image-20241017202412430.png][27] 注意 “挂起” 和 “阻塞” 的区别，两种状态都是暂时不能获得 CPU 的服务，但挂起态是将进程映像调到外存去了，而阻塞态下进程映像还在内存中。 ### 小结 ![image-20241017203108082.png][28] ## 进程调度 进程调度（低级调度），就是按照某种算法从就绪队列中选择一个进程为其分配处理机。 ### 进程调度的时机 **需要进行**进程调度与切换的情况： - 当前运行的进程**主动放弃**处理机： - 进程正常终止 - 运行过程中发生异常而终止 - 进程主动请求阻塞 (如等待 I/O) 等。 - 当前运行的进程**被动放弃**处理机： - 分给进程的时间片耗尽 - 有更紧急的事需要处理 (如 I/O 中断) - 有更高优先级的进程进入就绪队列 > 有的系统中，只允许进程主动放弃处理机； > > 有的系统中，进程可以主动放弃处理机，当有更紧急的任务需要处理时，也会强行剥夺处理机（被动放弃） **不能进行**进程调度与切换的情况： 1. **在处理中断的过程中**。中断处理过程复杂，与硬件密切相关，很难做到在中断处理过程中进行进程切换。 2. 进程在**操作系统内核程序临界区**中。 注意是操作系统内核程序的临界区，不是所有的临界区。普通临界区访问的临界资源不会直接影响操作系统内核的管理工作，如打印机。 3. 在**原子操作过程中** (原语) 。原子操作不可中断，要一气呵成 (如之前讲过的修改PCB中进程状态标志，并把PCB放到相应队列) ### 进程调度的方式 - **非剥夺调度方式**，又称**非抢占方式**。 只允许进程主动放弃处理机。在运行过程中即便有更紧迫的任务到达，当前进程依然会继续使用处理机，直到该进程终止或主动要求进入阻塞态。 实现简单，系统开销小但是无法及时处理紧急任务，适合于早期的批处理系统。 - **剥夺调度方式**，又称**抢占方式**。 当一个进程正在处理机上执行时，如果有一个更重要或更紧迫的进程需要使用处理机，则立即暂停正在执行的进程，将处理机分配给更重要紧迫的那个进程。 可以优先处理更紧急的进程，也可实现让各进程按时间片轮流执行的功能（通过时钟中断）。适合于分时操作系统、实时操作系统。 ### 进程的切换与过程 狭义的进程调度与进程切换的区别： - **狭义的进程调度**指的是从就绪队列中**选中一个要运行的进程**。这个进程可以是刚刚被暂停执行的进程，也**可能是另一个进程**，后一种情况就需要**进程切换**。 - **进程切换**是指一个进程让出处理机，由另一个进程占用处理机的过程。 广义的进程调度包含了选择一个进程和进程切换两个步骤。 进程切换的过程主要完成了： 1. 对原来运行进程各种数据的保存； 2. 对新的进程各种数据的恢复。 (如：程序计数器、程序状态字、各种数据寄存器等处理机现场信息，这些信息一般保存在进程控制块) > **进程切换是有代价的**，因此如果**过于频繁**的进行进程调度、切换，必然会**使整个系统的效率降低**，使系统大部分时间都花在了进程切换上，而真正用于执行进程的时间减少。 ### 调度器 / 调度程序 调度程序决定哪些进程需要运行 (调度算法) ，以及运行多长时间 (时间片大小) 。 ![image-20241018131300837.png][29] 触发调度程序的时机： - 创建新进程 - 京城推出 - 运行进程阻塞 - I/O 中断发生 (可能唤醒某些阻塞进程) 非抢占式调度策略，只有运行进程阻塞或退出才触发调度程序工作； 抢占式调度策略，每个**时钟中断**或 k 个时钟中断会触发调度程序工作。 ![image-20241018131557327.png][30] ### 闲逛进程 调度程序永远的备胎，没有其他就绪进程时，运行闲逛进程（idle） 闲逛进程的特性： - 优先级最低 - 可以是0地址指令，占一个完整的指令周期（指令周期末尾例行检查中断） - 能耗低 ### 小结 ![image-20241018125412018.png][31] ## 调度算法 ### 调度算法的评价指标 - **CPU 利用率**：CPU 工作的时间占总时间的比例。 $利用率 = \frac{忙碌的时间}{总时间}$ - **系统吞吐量**：单位时间内完成作业的数量。 $系统吞吐量 = \frac{总共完成了多少道作业}{总共花了多少时间}$ - **周转时间**：指从**作业被提交给系统开始**，到**作业完成为止**的这段时间间隔。 它包括四个部分：作业在外存后备队列上等待作业调度（高级调度）的时间、进程在就绪队列上等待进程调度（低级调度）的时间、进程在CPU上执行的时间、进程等待I/O操作完成的时间。后三项在一个作业的整个处理过程中，可能发生多次。 $周转时间 = 作业完成时间 – 作业提交时间$ $平均周转时间 = \frac{各作业周转时间之和}{作业数}$ $带权周转时间 = \frac{作业周转时间}{作业实际运行的时间} = \frac{作业完成时间–作业提交时间}{作业实际运行的时间}$ ，带权周转时间必然 $\geq 1$ 。 $平均带权周转时间 = \frac{各作业带权周转时间之和}{作业数}$ - **等待时间**：指进程 / 作业处于等待处理机状态时间之和。等待时间越长，用户满意度越低。 对于进程来说，等待时间就是指进程建立后等待被服务的时间之和，在等待I/O完成的期间其实进 程也是在被服务的，所以不计入等待时间。 对于作业来说，不仅要考虑建立进程后的等待时间，还要加上作业在外存后备队列中等待的时间。 一个作业总共需要被 CPU 服务多久，被I/O设备服务多久一般是确定不变的，因此调度算法其实只会影响作业 / 进程的等待时间。 - **响应时间**：指从用户提交请求到首次产生响应所用的时间。 ![image-20241017210216703.png][32] ### 先来先服务 FCFS **算法思想**：先来后到，主要从 “公平” 的角度考虑。 **算法规则**：按照作业 / 进程到达的先后顺序进行服务。 **用于作业还是进程调度**： - 用于作业调度时，考虑的是哪个作业先到达后备队列； - 用于进程调度时，考虑的是哪个进程先到达就绪队列。 **是否可抢占**：非抢占式算法。 **优缺点**： - 优点：公平、算法实现简单。 - 缺点：排在长作业（进程）后面的短作业需要等待很长时间，带权周转时间很大，对短作业来说用户体验不好。即，FCFS算法对长作业有利，对短作业不利。 **是否会导致饥饿**：不会。 > 饥饿：某进程/作业长期得不到服务。 ### 短作业优先 SJF **算法思想**：追求最少的平均等待时间，最少的平均周转时间、最少的平均平均带权周转时间。 **算法规则**：最短的作业 / 进程优先得到服务 (所谓 “最短” ，是指要求服务时间最短) **用于作业还是进程调度**：即可用于作业调度，也可用于进程调度。用于进程调度时称为 “短进程优先 (SPF, Shortest Process First) 算法” 。 **是否可抢占**：SJF 和 SPF 是非抢占式的算法。但是也有抢占式的版本 —— **最短剩余时间优先算法** (SRTN, Shortest Remaining Time Next) 。未特别说明的话默认是非抢占式算法。 > **最短剩余时间优先算法**：每当有进程加入就绪队列改变时就需要调度，如果新到达的进程剩余时间比当前运行的进程剩余时间更短，则由新进程抢占处理机，当前运行进程重新回到就绪队列。另外，当一个进程完成时也需要调度。 **优缺点**： - 优点：“最短的”平均等待时间、平均周转时间。 - 缺点：不公平。对短作业有利，对长作业不利。可能产生饥饿现象。另外，作业/进程的运行时间是由用户提供的，并不一定真实，不一定能做到真正的短作业优先 **是否会导致饥饿**：会。如果源源不断地有短作业/进程到来，可能使长作业/进程长时间得不到服务，产生“饥饿”现象。如果一直得不到服务，则称为 “饿死” 。 在**所有进程同时可运行**时，采用SJF调度算法的平均等待时间、平均周转时间最少。如果不加上述前提条件，则应该说“抢占式的短作业/进程优先调度算法（最短剩余时间优先, SRNT算法）的平均等待时间、平均周转时间最少” 。 ### 高响应比优先 HRRN 高响应比优先算法：**非抢占式**的调度算法，只有当前运行的进程主动放弃 CPU 时（正常 / 异常完成，或主动阻塞），才需要进行调度，调度时计算所有就绪进程的响应比，**选响应比最高的进程上处理机**。 **算法思想**：要综合考虑作业 / 进程的等待时间和要求服务的时间。 **算法规则**：在每次调度时先计算各个作业/进程的响应比，选择响应比最高的作业/进程为其服务。 > $响应比 = \frac{等待时间+要求服务时间}{要求服务时间}$ ，显然响应比 $\geq 1$ 。 **用于作业还是进程调度**：即可用于作业调度，也可用于进程调度 **是否可抢占**：**非抢占式**的算法。因此只有当前运行的作业 / 进程主动放弃处理机时，才需要调度，才需要计算响应比。 **优缺点**： - 综合考虑了等待时间和运行时间。（要求服务时间） - 等待时间相同时，要求服务时间短的优先。（SJF的优点） - 要求服务时间相同时，等待时间长的优先。（FCFS的优点） - 对于长作业来说，随着等待时间越来越久，其响应比也会越来越大，从而避免了长作业饥饿的问题 。 **是否会导致饥饿**：不会。 这几种算法主要关心对用户的公平性、平均周转时间、平均等待时间等评价系统整体性能的指标，但是不关心 “响应时间” ，也并不区分任务的紧急程度，因此对于用户来说，交互性很糟糕。因此这三种算法一般适合用于早期的批处理系统。 ### 时间片轮转调度算法 RR **算法思想**：公平地、轮流地为各个进程服务，让每个进程在一定时间间隔内都可以得到响应。 **算法规则**：按照各进程到达就绪队列的顺序，轮流让各个进程执行一个时间片（如100ms）。若进程未在一个时间片内执行完，则剥夺处理机，将进程重新放到就绪队列队尾重新排队。 **用于作业还是进程调度**：用于进程调度（只有作业放入内存建立了相应的进程后，才能被分配处理机时间片）。 **是否可抢占**：若进程未能在时间片内运行完，将被强行剥夺处理机使用权，因此时间片轮转调度算法属于抢占式的算法。由时钟装置发出时钟中断来通知CPU时间片已到。 **优缺点**： - 优点：公平；响应快，适用于分时操作系统； - 缺点：由于高频率的进程切换，因此有一定开销；不区分任务的紧急程度。 **是否会导致饥饿**：不会。 **时间片大小的影响：** - 如果**时间片太大**，使得每个进程都可以在一个时间片内就完成，则时间片轮转调度算法**退化为先来先服务调度算法**，并且会**增大进程响应时间**。因此时间片不能太大。 - 另一方面，进程调度、切换是有时间代价的（保存、恢复运行环境），因此**如果时间片太小**，会导致进程**切换过于频繁**，系统会花大量的时间来处理进程切换，从而导致**实际用于进程执行的时间比例减少**。可见时间片也不能太小。 ### 优先级调度算法 **算法思想**：随着计算机的发展，特别是实时操作系统的出现，越来越多的应用场景需要根据任务的紧急程度来决定处理顺序。 **算法规则**：每个作业 / 进程有各自的优先级，调度时选择优先级最高的作业 / 进程。 根据优先级是否可以动态改变，可将优先级分为**静态优先级**和**动态优先级**两种： - 静态优先级：创建进程时确定，之后一直不变。 - 动态优先级：创建进程时有一个初始值，之后会根据情况动态地调整优先级。 **用于作业还是进程调度**：既可用于作业调度，也可用于进程调度。甚至，还会用于在之后会学习的 I/O 调度中。 **是否可抢占**：抢占式、非抢占式都有。 做题时的区别在于：非抢占式只需在进程主动放弃处理机时进行调度即可，而抢占式还需在就绪队列变化时，检查是否会发生抢占。 > 就绪队列未必只有一个，可以按照不同优先级来组织。另外，也可以把优先级高的进程排在更靠近队头的位置。 **优缺点**： - 优点：用优先级区分紧急程度、重要程度，适用于实时操作系统。可灵活地调整对各种作业/进程的偏好程度。 - 缺点：若源源不断地有高优先级进程到来，则可能导致饥饿。 **是否会导致饥饿**：会 **各类进程优先级设置的一般规则：** - 系统进程优先级高于用户进程； - 前台进程优先级高于后台进程； - 操作系统更偏好I/O型进程（或称I/O繁忙型进程）； I/O 设备和 CPU 可以并行工作。如果优先让 I/O 繁忙型进程优先运行的话，则越有可能让 I/O 设备尽早地投入工作，则资源利用率、系统吞吐量都会得到提升。 **动态优先级的调整策略**：可以从追求公平、提升资源利用率等角度考虑。 - 如果某进程在就绪队列中等待了很长时间，则可以适当提升其优先级； - 如果某进程占用处理机运行了很长时间，则可适当降低其优先级； - 如果发现一个进程频繁地进行 I/O 操作，则可适当提升其优先级。 ### 多级反馈队列调度算法 **算法思想**：对其他调度算法的折中权衡。 **算法规则**： 1. 设置多级就绪队列，各级队列优先级从高到低，时间片从小到大。 2. 新进程到达时先进入第 1 级队列，按 FCFS 原则排队等待被分配时间片，若用完时间片进程还未结束，则进程进入下一级队列队尾。如果此时已经是在最下级的队列，则重新放回该队列队尾。 3. 只有第 k 级队列为空时，才会为 k+1 级队头的进程分配时间片。 **用于作业还是进程调度**：用于进程调度 **是否可抢占**：抢占式的算法。在k级队列的进程运行过程中，若更上级的队列 (1 ~ k-1级) 中进入了一个新进程，则由于新进程处于优先级更高的队列中，因此新进程会抢占处理机，原来运行的进程放回k级队列队尾。 **优缺点**： - 对各类型进程相对公平（FCFS的优点）； - 每个新到达的进程都可以很快就得到响应（RR的优点）； - 短进程只用较少的时间就可完成（SPF的优点）； - 不必实现估计进程的运行时间（避免用户作假）； - 可灵活地调整对各类进程的偏好程度，比如 CPU 密集型进程、I/O 密集型进程（拓展：可以将因I/O而阻塞的进程重新放回原队列，这样 I/O 型进程就可以保持较高优先级） **是否会导致饥饿**：会 比起早期的批处理操作系统来说，由于计算机造价大幅降低，因此之后出现的交互式操作系统（包括分时操作系统、实时操作系统等）更注重系统的响应时间、公平性、平衡性等指标。而这几种算法恰好也能较好地满足交互式系统的需求。因此这三种算法适合用于交互式系统。（比如UNIX使用的就是多级反馈队列调度算法） ### 多级队列调度算法 系统中按进程类型设置多个队列，进程创建成功后插入某个队列。 ![image-20241019134529895.png][33] 队列之间可采取固定优先级，或时间片划分： - 固定优先级：高优先级空时低优先级进程才能被调度。 - 时间片划分：如三个队列分配时间50%、40%、10%。 各队列可采用不同的调度策略，如： - 系统进程队列采用优先级调度； - 交互式队列采用 RR ； - 批处理队列采用 FCFS 。 ## 同步与互斥 ### 基本概念 #### 进程同步 进程具有异步性 (各并发执行的进程以各自独立的、不可预知的速度向前推进) 的特征，因此操作系统要提供 “进程同步机制” 来解决异步问题。 #### 进程互斥 进程的 “并发” 需要 “共享” 的支持。各个并发执行的进程不可避免的需要共享一些系统资源。比如内存，又比如打印机、摄像头这样的 I/O 设备。 ![image-20241021120508628.png][34] 我们把**一个时间段内只允许一个进程使用的资源**称为**临界资源**。许多物理设备（比如摄像头、打印机）都属于临界资源。此外还有许多变量、数据、内存缓冲区等都属于临界资源。 对临界资源的访问，必须**互斥**地进行。互斥，亦称**间接制约关系**。**进程互斥**指当一个进程访问某临界资源时，另一个想要访问该临界资源的进程必须等待。当前访问临界资源的进程访问结束，释放该资源之后，另一个进程才能去访问临界资源。 对临界资源的互斥访问，可以在逻辑上分为如下四个部分： - **进入区**：负责检查是否可进入临界区，若可进入，则应设置正在访问临界资源的标志（可理解为“上锁”），以阻止其他进程同时进入临界区。 - **临界区**：访问临界资源的那段代码。 - **退出区**：负责解除正在访问临界资源的标志（可理解为“解锁”）。 - **剩余区**：做其他处理。 为了实现对临界资源的互斥访问，同时保证系统整体性能，需要遵循以下原则： 1. 空闲让进。临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区； 2. 忙则等待。当已有进程进入临界区时，其他试图进入临界区的进程必须等待； 3. 有限等待。对请求访问的进程，应保证能在有限时间内进入临界区（保证不会饥饿）； 4. 让权等待。当进程不能进入临界区时，应立即释放处理机，防止进程忙等待。 #### 小结 ![image-20241021121345271.png][35] ### 进程互斥的软件实现 #### 单标志法 **算法思想**：两个进程在访问完临界区后会把使用临界区的权限转交给另一个进程。也就是说**每个进程进入临界区的权限只能被另一个进程赋予**。 ![image-20241021122026077.png][36] 只能按照 $P0 \rightarrow P1 \rightarrow P0 \rightarrow \cdots $ 这样轮流访问。这种必须轮流访问带来的问题是，如果此时允许进入临界区的进程是 P0 ，而 P0 一直不访问临界区，那么虽然此时临界区空闲，但是并不允许 P1 访问。 因此，单标志法存在的主要问题是：违背“空闲让进”原则。 #### 双标志先检查 **算法思想**：设置一个布尔型数组 `flag[]` ，数组中各个元素用来标记各进程想进入临界区的意愿，比如 `flag[0] = ture` 意味着 0 号进程 P0 现在想要进入临界区。每个进程在进入临界区之前先检查当前有没有别的进程想进入临界区，如果没有，则把自身对应的标志 `flag[i]` 设为 `true` ，之后开始访问临界区。 ![image-20241021132359101.png][37] 若按照 $1 \rightarrow 5\rightarrow 2\rightarrow 6\rightarrow 3\rightarrow 7\rightarrow \cdots$ 的顺序执行，则 P0 和 P1 会同时访问临界区。 因此，双标志先检查法的主要问题是：**违反 “忙则等待” 原则**。原因在于，进入区的 “检查” 和 “上锁” **两个处理不是一气呵成的**。“检查” 后，“上锁” 前可能发生进程切换。 #### 双标志后检查 **算法思想**：双标志先检查法的改版。前一个算法的问题是先 “检查” 后 “上锁” ，但是这两个操作又无法一气呵成，因此导致了两个进程同时进入临界区的问题。因此，人们又想到先 “上锁” 后 “检查” 的方法，来避免上述问题。 ![image-20241021132634336.png][38] 若按照 $1 \rightarrow 5\rightarrow 2\rightarrow 6\rightarrow \cdots$ 的顺序执行，则 P0 和 P1 都无法进入临界区。 因此，双标志后检查法虽然解决了 “忙则等待” 的问题，但是又违背了 “空闲让进” 和 “有限等待” 原则，会因各进程都长期无法访问临界资源而产生 “饥饿” 现象。两个进程都争着想进入临界区，但是谁也不让谁，最后谁都无法进入临界区。 #### Peterson 算法 **算法思想**：结合双标志法、单标志法的思想。如果双方都争着想进入临界区，那可以让进程尝试 “孔融让梨”（谦让）。做一个有礼貌的进程。 ![image-20241021135107541.png][39] > Peterson算法相较于之前三种软件解决方案来说，是最好的，但依然不够好。 Peterson 算法用软件方法解决了进程互斥问题，遵循了**空闲让进、忙则等待、有限等待**三个原则，但是依然未遵循**让权等待**的原则。 #### 小结 ![image-20241021135200919.png][40] ### 进程互斥的硬件实现 #### 中断屏蔽方法 利用 “开/关中断指令” 实现。与原语的实现思想相同，即在某进程开始访问临界区到结束访问为止都不允许被中断，也就不能发生进程切换，因此也不可能发生两个同时访问临界区的情况。 ![image-20241021135424296.png][41] **优点**：简单、高效。 **缺点**： - 不适用于多处理机。 - 只适用于操作系统内核进程，不适用于用户进程。 因为开/关中断指令只能运行在内核态，这组指令如果能让用户随意使用会很危险。 #### TestAndSet (TS 指令 / TSL 指令) > 简称 TS 指令，也有地方称为 TestAndSetLock 指令，或 TSL 指令。 TSL 指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成。以下是用 C 语言描述的逻辑： ```c // bool 型共享变量 lock 表示当前临界值是否被加锁 // true 表示已加锁，false 表示未加锁 bool TestAndSet (bool *lock) { bool old; old = *lock; // old 用来存放 lock 原来的值 *lock = true; // 无论之前是否已加锁，都将 lock 设置为 true return old; // 返回 lock 原来的值 } // 以下是使用 TSL 指令实现互斥的算法逻辑 while (TestAndSet (&lock)); // 上锁并检查 ... // 临界代码段 lock = false; // 解锁 ... // 剩余区代码段 ``` - 若刚开始 `lock` 是 `false` ，则 TSL 返回的 `old` 值为 `false` ，`while` 循环条件不满足，直接跳过循环，进入临界区。 - 若刚开始 `lock` 是 `true` ，则执行 TLS 后 `old` 返回的值为 `true` ，`while` 循环条件满足，会一直循环，直到当前访问临界区的进程在退出区进行 “解锁” 。 相比软件实现方法，TSL 指令把 “上锁” 和 “检查” 操作用硬件的方式变成了一气呵成的原子操作。 **优点**： - 实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞。 - 适用于多处理机环境。 **缺点**：不满足 “让权等待” 原则，暂时无法进入临界区的进程会占用 CPU 并循环执行 TSL 指令，从而导致 “忙等” 。 #### Swap 指令 (XCHG 指令) > 有的地方也叫 Exchange 指令，或简称 XCHG 指令。 Swap 指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成。以下是用 C 语言描述的逻辑： ```c // Swap 指令的作用是交换两个变量的值 Swap (bool *a, bool *b) { bool tmp; tmp = *a; *a = *b; *b = tmp; } // 以下是使用 Swap 指令实现互斥的算法逻辑 // lock 表示当前临界区是否被加锁 bool old = true; while (old == true) Swap (&lock, &old); ... // 临界区代码段 lock = false; ... // 剩余区代码段 ``` 逻辑上来看 Swap 和 TSL 并无太大区别，都是先记录下此时临界区是否已经被上锁（记录在 `old` 变量上），再将上锁标记 `lock` 设置为 `true` ，最后检查 `old` 。如果 `old` 为 `false` 则说明之前没有别的进程对临界区上锁，则可跳出循环，进入临界区。 **优点**： - 实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞。 - 适用于多处理机环境。 **缺点**：不满足 “让权等待” 原则，暂时无法进入临界区的进程会占用 CPU 并循环执行 Swap 指令，从而导致 “忙等” 。 #### 小结 ![image-20241021141003409.png][42] ### 互斥锁 解决临界区最简单的工具就是互斤锁 (mutex lock) 。一个进程在进入临界区时应获得锁；在退出临界区时释放锁。函数 `acquire()` 获得锁，而函数 `release()` 释放锁。 每个互斤锁有一个布尔变量available，表示锁是否可用。如果锁是可用的，调用acqiure0会成功，且锁不再可用。当一个进程试图获取不可用的锁时，会被阻塞，直到锁被释放。 ```c acquire() { while (!available) ; // 忙等待 available = false; // 获得锁 } release() { available = true; // 释放锁 } ``` `acquire()` 或 `release()` 的执行必须是原子操作，因此互斤锁通常采用硬件机制来实现。 互压锁的主要缺点是忙等待，当有一个进程在临界区中，任何其他进程在进入临界区时必须连续循环调用 `acquire()`。当多个进程共享同一 CPU 时，就浪费了 CPU 周期。因此，互斤锁通常用于多处理器系统，一个线程可以在一个处理器上等待，不影响其他线程的执行。 > 需要连续循环忙等的互斥锁，都可称为自旋锁（spin lock），如 TSL 指令、swap 指令、单标志法。 **特性**： - 需忙等，进程时间片用完才下处理机，违反 “让权等待” 。 - 优点：等待期间不用切换进程上下文，多处理器系统中，若上锁的时间短，则等待代价很低。 - 常用于多处理器系统，一个核忙等，其他核照常工作，并快速释放临界区。 - 不太适用于单处理机系统，忙等的过程中不可能解锁。 ### 信号量机制 **信号量**其实就是**一个变量**，可以用一个信号量 (<u>可以是一个整数，也可以是更复杂的记录型变量</u>) 来**表示系统中某种资源的数量**，比如：系统中只有一台打印机，就可以设置一个初值为 1 的信号量。 用户进程可以通过使用操作系统提供的**一对原语**来**对信号量进行操作**，从而很方便的实现了进程互 斥、进程同步。 **一对原语**：`wait(S)` 原语和 `signal(S)` 原语，可以把原语理解为我们自己写的函数，函数名分别为 `wait` 和 `signal` ，括号里的信号量 `S` 其实就是函数调用时传入的一个参数。 > `wait`、`signal` 原语常简称为P、V操作 (来自荷兰语 proberen 和 verhogen ) 。因此，做题的时候常把 `wait(S)` 、`signal(S)` 两个操作分别写为 `P(S)` 、 `V(S)` 。 #### 整型信号量 用一个整数型的变量作为信号量，用来表示系统中某种资源的数量。 > 与普通整数变量的区别：对信号量的操作只有三种，即初始化、P 操作、V 操作。 假设某计算机系统中有一台打印机： ![image-20241021170144438.png][43] #### 记录型信号量 整型信号量的缺陷是存在 “忙等” 问题，因此人们又提出了 “记录型信号量” ，即用记录型数据结构表示的信号量。 ![image-20241021172126500.png][44] - 对信号量 S 的一次 P 操作意味着进程请求一个单位的该类资源，因此需要执行 `S.value--`，表示资源数减 1 。当 `S.value < 0` 时表示该类**资源已分配完毕**，因此进程应调用 `block` 原语进行**自我阻塞**（当前运行的进程从运行态 $\rightarrow$ 阻塞态），主动放弃处理机，并插入该类资源的等待队列 `S.L` 中。可见，该机制**遵循了 “让权等待” 原则**，不会出现 “忙等” 现象。 - 对信号量 S 的一次 V 操作意味着进程释放一个单位的该类资源，因此需要执行 `S.value++` ，表示资源数加 1。若加 1 后仍是 `S.value <= 0` ，表示依然有进程在等待该类资源，因此应调用 `wakeup` 原语唤醒等待队列中的第一个进程（被唤醒进程从阻塞态 $\rightarrow$ 就绪态）。 #### 两种信号量小结 ![image-20241021172608577.png][45] > 若考试中出现 `P(S), V(S)` 的操作，除非特别说明，否则默认 S 为记录型信号量。 #### 信号量实现进程互斥 1. 分析并发进程的关键活动，划定临界区。（如：对临界资源打印机的访问就应放在临界区） 2. 设置互斥信号量 `mutex`，初值为1 。 3. 在进入区 `P(mutex)` —— 申请资源。 4. 在退出区 `V(mutex)` —— 释放资源。 ```c // 记录型信号量的定义 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)` 会导致资源永不被释放，等待进程永不被唤醒。 #### 信号量实现进程同步 > 进程同步：要让各并发进程按要求有序地推进。 1. 分析什么地方需要实现 “同步关系” ，即必须保证 “一前一后” 执行的两个操作（或两句代码）； 2. 设置同步信号量 S ，初始为 0 ； 3. 在 “前操作” 之后执行 `V(S)` ； 4. 在 “后操作” 之前执行 `P(S)` ； > 先 V 后 P ![image-20241021190711446.png][46] #### 信号量实现进程的前驱关系 进程 P1 中有句代码 S1，P2 中有句代码 S2，P3 中有句代码 S3 …… P6 中有句代码 S6。这些代码要求按如下前驱图所示的顺序来执行： ![image-20241021203647494.png][47] 其实每一对前驱关系都是一个进程同步问题 (需要保证一前一后的操作) 。因此： 1. 要为每一对前驱关系各设置一个同步信号量； 2. 在 “前操作” 之后对相应的同步信号量执行 V 操作； 3. 在 “后操作” 之前对相应的同步信号量执行 P 操作。 ![image-20241021203915332.png][48] #### 信号量实现小结 ![image-20241021203952731.png][49] ### 经典进程同步问题 #### 生产者消费者问题 系统中有一组生产者进程和一组消费者进程，生产者进程每次生产一个产品放入缓冲区，消费者进程每次从缓冲区中取出一个产品并使用。（注：这里的“产品”理解为某种数据） - 生产者、消费者共享一个初始为空，大小为 n 的缓冲区。 - 只有缓冲区没满时，生产者才能把产品放入缓冲区，否则必须等待。 - 只有缓冲区不空时，消费者才能从中取出产品，否则必须等待。 - 缓冲区是临界资源，各进程必须互斥地访问。 **PV操作题目分析步骤**： 1. 关系分析。找出题目中描述的各个进程，分析它们之间的同步、互斥关系。 ![image-20241022205021281.png][50] 2. 整理思路。根据各进程的操作流程确定 P、V 操作的大致顺序。 ![image-20241022205104605.png][51] 3. 设置信号量。并根据题目条件确定信号量初值。(互斥信号量初值一般为 1，同步信号量的初始值要看对应资源的初始值是多少) ![image-20241022205120711.png][52] > **实现互斥的 P 操作一定要在实现同步的 P 操作之后**，否则可能会发生死锁问题；V 操作不会导致进程阻塞，因此两个 V 操作顺序可以交换。 生产者消费者问题是一个互斥、同步的综合问题。对于初学者来说最难的是发现题目中隐含的两对同步关系。有时候是消费者需要等待生产者生产，有时候是生产者要等待消费者消费，这是两个不同的 “一前一后问题” ，因此也需要设置两个同步信号量。 #### 多生产者多消费者问题 桌子上有一只盘子，每次只能向其中放入一个水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，儿子专等着吃盘子中的橘子，女儿专等着吃盘子中的苹果。只有盘子空时，爸爸或妈妈才可向盘子中放一个水果。仅当盘子中有自己需要的水果时，儿子或女儿可以从盘子中取出水果。用PV操作实现上述过程。 1. 关系分析。找出题目中描述的各个进程，分析它们之间的同步、互斥关系。 互斥关系：对缓冲区（盘子）的访问要互斥地进行。 同步关系： - 父亲将苹果放入盘子后，女儿才能取苹果； - 母亲将橘子放入盘子后，儿子才能取橘子； - 只有盘子为空时，父亲或母亲才能放入水果。 2. 整理思路。根据各进程的操作流程确定 P、V 操作的大致顺序。 ![image-20241022210555802.png][53] 3. 设置信号量。并根据题目条件确定信号量初值。(互斥信号量初值一般为 1，同步信号量的初始值要看对应资源的初始值是多少) ![image-20241022210739221.png][54] 本题中的缓冲区大小为 1 ，在任何时刻，apple、orange、plate 三个同步信号量中最多只有一个是 1 。因此在任何时刻，最多只有一个进程的P操作不会被阻塞，并顺利地进入临界区。因此此题条件下即使不设置专门的互斥变量 mutex ，也不会出现多个进程同时访问盘子的现象。 > 如果来不及分析就直接加上，不会判错。 解决“多生产者-多消费者问题”的关键在于理清复杂的同步关系。在分析同步问题（一前一后问题）的时候不能从单个进程行为的角度来分析，要把“一前一后”发生的事看做是两种“事件”的前后关系。 #### 吸烟者问题 假设一个系统有三个抽烟者进程和一个供应者进程。每个抽烟者不停地卷烟并抽掉它，但是要卷起并抽掉一支烟，抽烟者需要有三种材料：烟草、纸和胶水。三个抽烟者中，第一个拥有烟草、第二个拥有纸、第三个拥有胶水。供应者进程无限地提供三种材料，供应者每次将两种材料放桌子上，拥有剩下那种材料的抽烟者卷一根烟并抽掉它，并给供应者进程一个信号告诉完成了，供应者就会放另外两种材料再桌上，这个过程一直重复（让三个抽烟者轮流地抽烟）。 1. 关系分析。找出题目中描述的各个进程，分析它们之间的同步、互斥关系。 ![image-20241022212659575.png][55] 2. 整理思路。根据各进程的操作流程确定 P、V 操作的大致顺序。 ![image-20241022212727058.png][56] 3. 设置信号量。并根据题目条件确定信号量初值。(互斥信号量初值一般为 1，同步信号量的初始值要看对应资源的初始值是多少) ![image-20241022212800962.png][57] 吸烟者问题可以为我们解决“可以生产多个产品的单生产者”问题提供一个思路。 值得吸取的精华是：“轮流让各个吸烟者吸烟”必然需要“轮流的在桌上放上组合一、二、三”，注意体会我们是如何用一个整型变量i 实现这个“轮流”过程的。 #### 读者写者问题 有读者和写者两组并发进程，共享一个文件，当两个或两个以上的读进程同时访问共享数据时不会产生副作用，但若某个写进程和其他进程（读进程或写进程）同时访问共享数据时则可能导致数据不一致的错误。因此要求： - 允许多个读者可以同时对文件执行读操作； - 只允许一个写者往文件中写信息； - 任一写者在完成写操作之前不允许其他读者或写者工作； - 写者执行写操作前，应让已有的读者和写者全部退出。 1. 关系分析。找出题目中描述的各个进程，分析它们之间的同步、互斥关系。 两类进程：写进程、读进程。 互斥关系：写进程—写进程、写进程—读进程。读进程与读进程不存在互斥问题。 2. 整理思路。根据各进程的操作流程确定 P、V 操作的大致顺序。 3. 设置信号量。并根据题目条件确定信号量初值。(互斥信号量初值一般为 1，同步信号量的初始值要看对应资源的初始值是多少) ![image-20241022220830511.png][58] 针对写进程饿死的情况，可以使用一个信号量来实现 "写优先" ： ![image-20241022221050630.png][59] 读者-写者问题为我们解决复杂的互斥问题提供了一个参考思路。 其核心思想在于设置了一个计数器 count 用来记录当前正在访问共享文件的读进程数。我们可以用 count 的值来判断当前进入的进程是否是第一个/最后一个读进程，从而做出不同的处理。 另外，对 count 变量的检查和赋值不能一气呵成导致了一些错误，如果需要实现 “一气呵成” ，自 然应该想到用互斥信号量。 最后，还要认真体会我们是如何解决 “写进程饥饿” 问题的。 #### 哲学家进餐问题 一张圆桌上坐着5名哲学家，每两个哲学家之间的桌上摆一根筷子，桌子的中间是一碗米饭。哲学家们倾注毕生的精力用于思考和进餐，哲学家在思考时，并不影响他人。只有当哲学家饥饿时，才试图拿起左、右两根筷子（一根一根地拿起）。如果筷子已在他人手上，则需等待。饥饿的哲学家只有同时拿起两根筷子才可以开始进餐，当进餐完毕后，放下筷子继续思考。 1. 关系分析。找出题目中描述的各个进程，分析它们之间的同步、互斥关系。 系统中有 5 个哲学家进程，5位哲学家与左右邻居对其中间筷子的访问是互斥关系。 2. 整理思路。根据各进程的操作流程确定 P、V 操作的大致顺序。 这个问题中只有互斥关系，但与之前遇到的问题不同的事，每个哲学家进程需要同时持有两个临界资源才能开始吃饭。如何避免临界资源分配不当造成的死锁现象，是哲学家问题的精髓。 3. 设置信号量。并根据题目条件确定信号量初值。(互斥信号量初值一般为 1，同步信号量的初始值要看对应资源的初始值是多少) 定义互斥信号量数组 `chopstick[5]={1,1,1,1,1}` 用于实现对 5 个筷子的互斥访问。并对哲学家按 0~4 编号，哲学家i左边的筷子编号为 `i`，右边的筷子编号为 `(i + 1) % 5` 。 最容易想到的实现方法： ```c semaphore chopstick[5] = {1, 1, 1, 1, 1}; Pi (){ // i 号哲学家的进程 while(1){ P(chopstick[i]); // 拿左 P(chopstick[(i + 1) % 5]); // 拿右 吃饭… V(chopstick[i]); // 放左 V(chopstick[(i + 1) % 5]); // 放右 思考… } } ``` 显然，当每个哲学家都拿起自己左边的筷子的时候，每个人都在等待右边的人放下筷子，从而造成了死锁。 **如何防止死锁的发生**？ 1. 可以对哲学家进程施加一些限制条件，比如最多允许四个哲学家同时进餐。这样可以保证至少有一个哲学家是可以拿到左右两只筷子的。 2. 要求奇数号哲学家先拿左边的筷子，然后再拿右边的筷子，而偶数号哲学家刚好相反。用这种方法可以保证如果相邻的两个奇偶号哲学家都想吃饭，那么只会有其中一个可以拿起第一只筷子，另一个会直接阻塞。这就避免了占有一支后再等待另一只的情况。 3. 仅当一个哲学家左右两支筷子都可用时才允许他抓起筷子。 ```c semaphore chopstick[5] = {1, 1, 1, 1, 1}; semaphore mutex = 1; // 互斥地取筷子 Pi (){ // i 号哲学家的进程 while(1){ P(mutex); P(chopstick[i]); //拿左 P(chopstick[(i + 1) % 5]); //拿右 V(mutex); 吃饭… V(chopstick[i]); //放左 V(chopstick[(i + 1) % 5]); //放右 思考… } } ``` 哲学家进餐问题的关键在于解决进程死锁。 这些进程之间只存在互斥关系，但是与之前接触到的互斥关系不同的是，每个进程都需要同时持有两个临界资源，因此就有“死锁”问题的隐患。 如果在考试中遇到了一个进程需要同时持有多个临界资源的情况，应该参考哲学家问题的思想，分析题中给出的进程之间是否会发生循环等待，是否会发生死锁。可以参考哲学家就餐问题解决死锁的三种思路。 ### 管程 信号量机制存在的问题：编写程序困难、易出错。能不能设计一种机制，让程序员写程序时不需要再关注复杂的 PV 操作，让写代码更轻松呢？ 1973年，Brinch Hansen 首次在程序设计语言 Pascal 中引入了 “管程” 成分 —— 一种高级同步机制。 #### 定义 管程是一种特殊的软件模块，有这些部分组成： 1. 局部于管程的共享数据结构说明； 2. 对该数据结构进行操作的一组过程； 3. 对局部于管程的共享数据设置初始值的语句； 4. 管程有一个名字。 > 类似于面向对象语言中的类 #### 基本特征 - 局部于管程的数据只能被局部于管程的过程所访问； - 一个进程只有通过调用管程内的过程才能进入管程访问共享数据； - **每次仅允许一个进程在管程内执行某个内部过程**。 #### 使用 引入管程的目的无非就是要更方便地实现进程互斥和同步。 1. 需要在管程中定义共享数据（如生产者消费者问题的缓冲区） 2. 需要在管程中定义用于访问这些共享数据的 “入口” ，其实就是一些函数。（如生产者消费者问题中，可以定义一个函数用于将产品放入缓冲区，再定义一个函数用于从缓冲区取出产品） 3. 只有**通过这些特定的 “入口” 才能访问共享数据**。 4. 管程中有很多 “入口” ，但是每次只能开放其中一个 “入口” ，并且**只能让一个进程或线程进入**。（如生产者消费者问题中，各进程需要互斥地访问共享缓冲区。管程的这种特性即可保证一个时间段内最多只会有一个进程在访问缓冲区） > 这种互斥特性是**由编译器负责实现**的，程序员不用关心。 5. 可在管程中设置条件变量及等待 / 唤醒操作以解决同步问题。可以让一个进程或线程在条件变量上等待（此时，该进程应先释放管程的使用权，也就是让出 “入口” ）；也可以通过唤醒操作将等待在条件变量上的进程或线程唤醒。 程序员可以用某种特殊的语法定义一个管程，之后其他程序员就可以使用这个管程提供的特定 “入口” 很方便地使用实现进程同步 / 互斥了。比如 Java 中的关键字 `synchronized` 。 #### 小结 ![image-20241025200009453.png][60] ## 死锁 ### 相关概念 在并发环境下，各进程因竞争资源而造成的一种互相等待对方手里的资源，导致各进程都阻塞，都无法向前推进的现象，就是 “**死锁**” 。发生死锁后若无外力干涉，这些进程都将无法向前推进。 ![image-20241024001151830.png][61] #### 死锁产生的条件 产生死锁必须同时满足一下四个条件，只要其中任一条件不成立，死锁就不会发生。 - **互斥条件**：只有对必须互斥使用的资源的争抢才会导致死锁（如哲学家的筷子、打印机设备）。像内存、扬声器这样可以同时让多个进程使用的资源是不会导致死锁的（因为进程不用阻塞等待这种资源）。 - **不剥夺条件**：进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放。 - **请求和保持条件**：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程被阻塞，但又对自己已有的资源保持不放。 - **循环等待条件**：存在一种进程资源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程所请求。 > 发生死锁时一定有循环等待，但是发生循环等待时未必死锁（循环等待是死锁的必要不充分条件） #### 什么时候会发生死锁 1. 对系统资源的竞争。各进程对不可剥夺的资源（如打印机）的竞争可能引起死锁，对可剥夺的资源（CPU）的竞争是不会引起死锁的。 2. 进程推进顺序非法。请求和释放资源的顺序不当，也同样会导致死锁。例如，并发执行的进程 P1、P2 分别申请并占有了资源 R1、R2 ，之后进程 P1 又紧接着申请资源 R2 ，而进程 P2 又申请资源 R1 ，两者会因为申请的资源被对方占有而阻塞，从而发生死锁。 3. 信号量的使用不当也会造成死锁。如生产者 - 消费者问题中，如果实现互斥的P操作在实现同步的 P 操作之前，就有可能导致死锁。（可以把互斥信号量、同步信号量也看做是一种抽象的系统资源） 总之，对不可剥夺资源的不合理分配，可能导致死锁。 #### 死锁的处理策略 - 预防死锁。破坏死锁产生的四个必要条件中的一个或几个。 - 避免死锁。用某种方法防止系统进入不安全状态，从而避免死锁。（银行家算法） - 死锁的检测和解除。允许死锁的发生，不过操作系统会负责检测出死锁的发生，然后采取某种措 施解除死锁。 #### 小结 ![image-20241024002514046.png][62] ### 预防死锁 #### 破坏互斥条件 > 互斥条件：只有对必须互斥使用的资源的争抢才会导致死锁。 如果把只能互斥使用的资源改造为允许共享使用，则系统不会进入死锁状态。比如: `SPOOLing `技术。 操作系统可以采用 `SPOOLing `技术把独占设备在逻辑上改造成共享设备。比如，用 `SPOOLing `技术将打印机改造为共享设备。 **该策略的缺点**：并不是所有的资源都可以改造成可共享使用的资源。并且为了系统安全，很多地方还必须保护这种互斥性。因此，很多时候都无法破坏互斥条件。 #### 破坏不剥夺条件 > 不剥夺条件：进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放。 破坏不剥夺条件： 1. 当某个进程请求新的资源得不到满足时，它必须立即释放保持的所有资源，待以后需要时再重新申请。也就是说，即使某些资源尚未使用完，也需要主动释放，从而破坏了不可剥夺条件。 2. 当某个进程需要的资源被其他进程所占有的时候，可以由操作系统协助，将想要的资源强行剥夺。这种方式一般需要考虑各进程的优先级（比如：剥夺调度方式，就是将处理机资源强行剥夺给优先级更高的进程使用） **该策略的缺点**： 1. 实现起来比较复杂。 2. 释放已获得的资源可能造成前一阶段工作的失效。因此这种方法一般只适用于易保存和恢复状态的资源，如 CPU 。 3. 反复地申请和释放资源会增加系统开销，降低系统吞吐量。 4. 若采用方案一，意味着只要暂时得不到某个资源，之前获得的那些资源就都需要放弃，以后再重新申请。如果一直发生这样的情况，就会导致进程饥饿。 #### 破坏请求和保持条件 > 请求和保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程被阻塞，但又对自己已有的资源保持不放。 可以采用静态分配方法，即进程在运行前一次申请完它所需要的全部资源，在它的资源未满足前，不让它投入运行。一旦投入运行后，这些资源就一直归它所有，该进程就不会再请求别的任何资源了。 该策略实现起来简单，但也有明显的**缺点**： 有些资源可能只需要用很短的时间，因此如果进程的整个运行期间都一直保持着所有资源，就会造成严重的资源浪费，资源利用率极低。另外，该策略也有可能导致某些进程饥饿。 #### 破坏循环等待条件 > 循环等待条件：存在一种进程资源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程所请求。 可采用**顺序资源分配法**。首先给系统中的资源编号，规定每个进程**必须按编号递增的顺序请求资源**，同类资源（即编号相同的资源）一次申请完。 原理分析：一个进程只有已占有小编号的资源时，才有资格申请更大编号的资源。按此规则，已持有大编号资源的进程不可能逆向地回来申请小编号的资源，从而就不会产生循环等待的现象。 ![image-20241024010425559.png][63] 该策略的缺点： 1. 不方便增加新的设备，因为可能需要重新分配所有的编号； 2. 进程实际使用资源的顺序可能和编号递增顺序不一致，会导致资源浪费； 3. 必须按规定次序申请资源，用户编程麻烦。 #### 小结 ![image-20241024011604786.png][64] ### 避免死锁 #### 安全序列 所谓**安全序列**，就是指如果系统按照这种序列分配资源，则每个进程都能顺利完成。只要能找出一个安全序列，系统就是**安全状态**。当然，**安全序列可能有多个**。 如果分配了资源之后，系统中找不出任何一个安全序列，系统就进入了**不安全状态**。这就意味着之后**可能**所有进程都无法顺利的执行下去。当然，如果有进程提前归还了一些资源，那**系统也有可能重新回到安全状态**，不过我们在分配资源之前总是要考虑到最坏的情况。 如果系统处于**安全状态**，就**一定不会发生死锁**。如果系统进入**不安全状态**，就**可能发生死锁**。（处于不安全状态未必就是发生了死锁，但发生死锁时一定是在不安全状态） 因此可以**在资源分配之前预先判断这次分配是否会导致系统进入不安全状态**，以此决定是否答应资源分配请求。这也是 “银行家算法” 的核心思想。 #### 银行家算法 银行家算法是荷兰学者 Dijkstra 为银行系统设计的，以确保银行在发放现金贷款时，不会发生不能满足所有客户需要的情况。后来该算法被用在操作系统中，用于避免死锁。 **核心思想**：在进程提出资源申请时，先预判此次分配是否会导致系统进入不安全状态。如果会进入不安全状态，就暂时不答应这次请求，让该进程先阻塞等待。 ![image-20241024022426382.png][65] **数据结构**： - 长度为 `m` 的一维数组 `Available` 表示还有多少可用资源； - `n * m` 矩阵 `Max` 表示各进程对资源的最大需求数； - `n * m` 矩阵 `Allocation` 表示已经给各进程分配了多少资源； - `Max – Allocation = Need` 矩阵表示各进程最多还需要多少资源； - 用长度为 `m` 的一位数组 `Request` 表示进程此次申请的各种资源数； **算法步骤**： 1. 检查此次申请是否超过了之前声明的最大需求数。 2. 检查此时系统剩余的可用资源是否还能满足这次请求。 3. 试探着分配，更改各数据结构。 4. 用安全性算法检查此次分配是否会导致系统进入不安全状态。 **安全性算法步骤**： - 检查当前的剩余可用资源是否能满足某个进程的最大需求，如果可以，就把该进程加入安全序列，并把该进程持有的资源全部回收。 - 不断重复上述过程，看最终是否能让所有进程都加入安全序列。 ### 死锁的检测与解除 如果系统中既不采取预防死锁的措施，也不采取避免死锁的措施，系统就很可能发生死锁。在这种情况下，系统应当提供两个算法： 1. 死锁检测算法：用于检测系统状态，以确定系统中是否发生了死锁。 2. 死锁解除算法：当认定系统中已经发生了死锁，利用该算法可将系统从死锁状态中解脱出来。 #### 死锁的检测 为了能对系统是否已发生了死锁进行检测，必须： - 用某种数据结构来保存资源的请求和分配信息； - 提供一种算法，利用上述信息来检测系统是否已进入死锁状态。 ![image-20241024023306974.png][66] **分析过程**： - 如果系统中剩余的可用资源数足够满足进程的需求，那么这个进程暂时是不会阻塞的，可以顺利地执行下去。 - 如果这个进程执行结束了把资源归还系统，就可能使某些正在等待资源的进程被激活，并顺利地执行下去。 - 相应的，这些被激活的进程执行完了之后又会归还一些资源，这样可能又会激活另外一些阻塞的进程。 如果按上述过程分析，最终**能消除所有边**，就称这个图是**可完全简化的**。此时**一定没有发生死锁**（相当于能找到一个安全序列） 如果最终**不能消除所有边**，那么此时就是**发生了死锁**。最终还连着边的那些进程就是处于死锁状态的进程。 **检测死锁的算法**： 1. 在资源分配图中，找出既不阻塞又不是孤点的进程 Pi（即找出一条有向边与它相连，且该有向边对应资源的申请数量小于等于系统中已有空闲资源数量。如下图中，R1 没有空闲资源，R2 有一个空闲资源。若所有的连接该进程的边均满足上述条件，则这个进程能继续运行直至完成，然后释放它所占有的所有资源）。消去它所有的请求边和分配变，使之称为孤立的结点。在下图中， P1 是满足这一条件的进程结点，于是将P1的所有边消去。 2. 进程 Pi 所释放的资源，可以唤醒某些因等待这些资源而阻塞的进程，原来的阻塞进程可能变为非阻塞进程。在下图中，P2 就满足这样的条件。根据 1 中的方法进行一系列简化后，若能消去途中所有的边，则称该图是可完全简化的。 ![image-20241024023855812.png][67] > 死锁定理：如果某时刻系统的资源分配图是不可完全简化的，那么此时系统死锁 #### 死锁的解除 一旦检测出死锁的发生，就应该立即解除死锁。 > 并不是系统中所有的进程都是死锁状态，用死锁检测算法化简资源分配图后，还连着边的那些进程就是死锁进程。 **解除死锁的主要方法**有： 1. **资源剥夺法**。挂起（暂时放到外存上）某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。但是应防止被挂起的进程长时间得不到资源而饥饿。 2. **撤销进程法**（或称终止进程法）。强制撤销部分、甚至全部死锁进程，并剥夺这些进程的资源。这种方式的优点是实现简单，但所付出的代价可能会很大。因为有些进程可能已经运行了很长时间，已经接近结束了，一旦被终止可谓功亏一篑，以后还得从头再来。 3. **进程回退法**。让一个或多个死锁进程回退到足以避免死锁的地步。这就要求系统要记录进程的历史信息，设置还原点。 **处理对象的选择**： 1. 进程优先级； 2. 已执行多长时间； 3. 还要多久能完成； 4. 进程已经使用了多少资源； 5. 进程是交互式的还是批处理式的。 #### 小结 ![image-20241024024047587.png][68] [1]: https://blog.domineto.top/usr/uploads/2024/10/422854037.png [2]: https://blog.domineto.top/usr/uploads/2024/10/2971456453.png [3]: https://blog.domineto.top/usr/uploads/2024/10/596643381.png [4]: https://blog.domineto.top/usr/uploads/2024/10/3828853364.png [5]: https://blog.domineto.top/usr/uploads/2024/10/2823782884.png [6]: https://blog.domineto.top/usr/uploads/2024/10/1426657552.png [7]: https://blog.domineto.top/usr/uploads/2024/10/1574346267.png [8]: https://blog.domineto.top/usr/uploads/2024/10/3351417341.png [9]: https://blog.domineto.top/usr/uploads/2024/10/477915265.png [10]: https://blog.domineto.top/usr/uploads/2024/10/2623930408.png [11]: https://blog.domineto.top/usr/uploads/2024/10/1492480163.png [12]: https://blog.domineto.top/usr/uploads/2024/10/3765399294.png [13]: https://blog.domineto.top/usr/uploads/2024/10/1287635761.png [14]: https://blog.domineto.top/usr/uploads/2024/10/1880695892.png [15]: https://blog.domineto.top/usr/uploads/2024/10/2156567021.png [16]: https://blog.domineto.top/usr/uploads/2024/10/2853174092.png [17]: https://blog.domineto.top/usr/uploads/2024/10/2828214811.png [18]: https://blog.domineto.top/usr/uploads/2024/10/4098717663.png [19]: https://blog.domineto.top/usr/uploads/2024/10/1780526574.png [20]: https://blog.domineto.top/usr/uploads/2024/10/2423558633.png [21]: https://blog.domineto.top/usr/uploads/2024/10/1823631725.png [22]: https://blog.domineto.top/usr/uploads/2024/10/3417261884.png [23]: https://blog.domineto.top/usr/uploads/2024/10/1083869887.png [24]: https://blog.domineto.top/usr/uploads/2024/10/2348146796.png [25]: https://blog.domineto.top/usr/uploads/2024/10/4068779391.png [26]: https://blog.domineto.top/usr/uploads/2024/10/1991100954.png [27]: https://blog.domineto.top/usr/uploads/2024/10/328445470.png [28]: https://blog.domineto.top/usr/uploads/2024/10/507980185.png [29]: https://blog.domineto.top/usr/uploads/2024/10/3351359645.png [30]: https://blog.domineto.top/usr/uploads/2024/10/202884049.png [31]: https://blog.domineto.top/usr/uploads/2024/10/3145577890.png [32]: https://blog.domineto.top/usr/uploads/2024/10/3200487154.png [33]: https://blog.domineto.top/usr/uploads/2024/10/1082409805.png [34]: https://blog.domineto.top/usr/uploads/2024/10/3634786617.png [35]: https://blog.domineto.top/usr/uploads/2024/10/4175057457.png [36]: https://blog.domineto.top/usr/uploads/2024/10/1239014534.png [37]: https://blog.domineto.top/usr/uploads/2024/10/100817304.png [38]: https://blog.domineto.top/usr/uploads/2024/10/1638145759.png [39]: https://blog.domineto.top/usr/uploads/2024/10/2801727872.png [40]: https://blog.domineto.top/usr/uploads/2024/10/111172476.png [41]: https://blog.domineto.top/usr/uploads/2024/10/660827615.png [42]: https://blog.domineto.top/usr/uploads/2024/10/1879812627.png [43]: https://blog.domineto.top/usr/uploads/2024/10/2484006073.png [44]: https://blog.domineto.top/usr/uploads/2024/10/3772111682.png [45]: https://blog.domineto.top/usr/uploads/2024/10/4211405725.png [46]: https://blog.domineto.top/usr/uploads/2024/10/1162633537.png [47]: https://blog.domineto.top/usr/uploads/2024/10/734508769.png [48]: https://blog.domineto.top/usr/uploads/2024/10/3533477446.png [49]: https://blog.domineto.top/usr/uploads/2024/10/1851891997.png [50]: https://blog.domineto.top/usr/uploads/2024/10/2108821113.png [51]: https://blog.domineto.top/usr/uploads/2024/10/2028584282.png [52]: https://blog.domineto.top/usr/uploads/2024/10/1247385223.png [53]: https://blog.domineto.top/usr/uploads/2024/10/4170790058.png [54]: https://blog.domineto.top/usr/uploads/2024/10/3355531768.png [55]: https://blog.domineto.top/usr/uploads/2024/10/2798395825.png [56]: https://blog.domineto.top/usr/uploads/2024/10/2024380285.png [57]: https://blog.domineto.top/usr/uploads/2024/10/3589660186.png [58]: https://blog.domineto.top/usr/uploads/2024/10/1571227863.png [59]: https://blog.domineto.top/usr/uploads/2024/10/2536611869.png [60]: https://blog.domineto.top/usr/uploads/2024/10/1302196046.png [61]: https://blog.domineto.top/usr/uploads/2024/10/3448360389.png [62]: https://blog.domineto.top/usr/uploads/2024/10/3559255747.png [63]: https://blog.domineto.top/usr/uploads/2024/10/3829747586.png [64]: https://blog.domineto.top/usr/uploads/2024/10/2430574995.png [65]: https://blog.domineto.top/usr/uploads/2024/10/378596513.png [66]: https://blog.domineto.top/usr/uploads/2024/10/2523524160.png [67]: https://blog.domineto.top/usr/uploads/2024/10/230500655.png [68]: https://blog.domineto.top/usr/uploads/2024/10/1885441537.png 最后修改：2024 年 12 月 01 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏