操作系统-进程与线程(2)

4FGR2026-10-142026-10-14

2.1 进程与线程

2.1.1 程序与进程

程序：是静态的，存放在磁盘里的可执行文件，是一系列指令集合。
进程（Process）：是动态的，是程序的一次执行过程。

同一个程序多次执行会对应多个进程。

2.1.2 进程的组成

更确切的说，应该是进程实体(进程映像)的组成。
进程实体由 $PCB$、程序段、数据段三部分组成。

$PCB$：进程控制块，是给操作系统用的，$PCB$ 是进程存在的唯一标志。当进程被创建时，操作系统为其创建 $PCB$，当进程结束时，会回收其 $PCB$。操作系统对进程进行管理工作所需的信息都存放在 $PCB$ 中。
1. 进程描述信息
  - 进程标识符 $PID$
  - 用户标识符 $UID$
2. 进程控制和管理信息
  - $CPU$、磁盘、网络流量使用情况统计
  - 进程当前状态：就绪态/阻塞态/运行态
3. 资源分配清单
  - 正在使用哪些文件
  - 正在使用哪些内存区域
  - 正在使用哪些 $I/O$ 设备
4. 处理机相关信息
  - 如 $PSW$、$PC$ 等各种寄存器的值，用于实现进程切换
程序段：程序的代码（指令序列），是给进程自己用的。
数据段：运行过程中产生的各种数据（如：程序中定义的变量），是给进程自己用的。

例子：同时挂三个 $QQ$ 号，会对应三个 $QQ$ 进程，它们的 $PCB$、数据段各不相同，但程序段的内容都是相同的（都是运行着相同的 $QQ$ 程序）。

进程实体（进程映像）是静态的，反应进程在某一时刻的状态；进程是进程实体的运行过程，是动态的。
进程是系统进行资源分配和调度的一个独立单位。
一个进程被“调度”，就是指操作系统决定让这个进程上 $CPU$ 运行。

屏幕截图 2026-09-23 163036

2.1.3 进程的特征

动态性：进程是程序的一次执行过程，是动态地产生、变化和消亡的。动态性是进程最基本的特性。
并发性：内存中有多个进程实体，各进程可并发执行。
独立性：进程是能独立运行、独立获得资源、独立接受调度的基本单位。
异步性：各进程按各自独立的、不可预知的速度向前推进，异步性会导致并发程序执行结果的不确定性，操作系统需要提供进程同步机制解决异步问题。
结构性：每个进程都会配置一个 $PCB$。结构上看，进程由程序段、数据段、$PCB$ 组成。

屏幕截图 2026-09-23 162938

2.1.4 进程的状态与转换

进程的五种状态

进程的整个生命周期中，大部分时间都处于三种基本状态。

三种基本状态

运行态（Running）：占有 $CPU$，并在 $CPU$ 上运行

单 $CPU$ 情况下，同一时刻只会有一个进程处于运行态，多核 $CPU$ 情况下，可能有多个进程处于运行态
就绪态（Ready）：已经具备运行条件，但由于没有空闲 $CPU$，而暂时不能运行
阻塞态（Waiting/Blocked，又称：等待态）：因等待某一事件而暂时不能运行

另外两种状态

创建态（New，又称：新建态）：进程正在被创建，操作系统为进程分配资源、初始化 $PCB$
终止态（Terminated，又称：结束态）：进程正在从系统中撤销，操作系统会回收进程拥有的资源、撤销 $PCB$

进程 $PCB$ 中，会有一个变量 $\text{state}$ 来表示进程的当前状态。如：$1$ 表示创建态、$2$ 表示就绪态、$3$ 表示运行态…… 为了对同一个状态下的各个进程进行统一的管理，操作系统会将各个进程的 $PCB$ 组织起来。

状态	$CPU$	其他所需资源
运行状态	$\boldsymbol{\checkmark}$	$\boldsymbol{\checkmark}$
就绪状态	$\boldsymbol{\times}$	$\boldsymbol{\checkmark}$
阻塞状态	$\boldsymbol{\times}$	$\boldsymbol{\times}$
创建状态	操作系统为新进程分配资源、创建 $PCB$
终止状态	操作系统回收进程的资源、撤销 $PCB$

屏幕截图 2026-09-23 164832

进程状态之间的转换

创建态 $\rightarrow$ 就绪态：系统完成创建进程相关的工作
就绪态 $\rightarrow$ 运行态：进程被调度
运行态 $\rightarrow$ 就绪态：时间片到，或 $CPU$ 被其他高优先级的进程抢占
运行态 $\rightarrow$ 阻塞态：进程用“系统调用”的方式申请某种系统资源，或者请求等待某个事件发生，是进程自身做出的主动行为
阻塞态 $\rightarrow$ 就绪态：申请的资源被分配，或等待的事件发生，不是进程自身能控制的，是一种被动行为
运行态 $\rightarrow$ 终止态：进程运行结束，或运行过程中遇到不可修复的错误

注意：不能由阻塞态直接转换为运行态，也不能由就绪态直接转换为阻塞态（因为进入阻塞态是进程主动请求的，必然需要进程在运行时才能发出这种请求）

屏幕截图 2026-09-23 165102

2.1.5进程控制

进程控制就是要实现进程状态的转换。
进程控制用原语实现：

原语用关 / 开中断来实现
原语是一种特殊的程序
原语的执行必须一气呵成，不可中断

原语的原子性

原语的执行具有原子性，即执行过程只能一气呵成，期间不允许被中断。
可以用 “关中断指令” 和 “开中断指令” 这两个特权指令实现原子性。

$CPU$ 执行了关中断指令之后，就不再例行检查中断信号，直到执行开中断指令之后才会恢复检查。
这样，关中断、开中断之间的这些指令序列就是不可被中断的，这就实现了“原子性”。

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

注：关中断、开中断指令属于内核程序，运行在核心态。

1.1.6_1 进程通信

进程间通信是指两个进程之间产生数据交互。

进程是分配系统资源的单位（包括内存地址空间），因此各进程拥有的内存地址空间相互独立。
为了保证安全，一个进程不能直接访问另一个进程的地址空间。

进程通信分为三类：共享存储、消息传递、管道通信。

共享存储

设置一个共享内存区域，并映射到进程的虚拟地址空间。
要互斥地访问共享空间（由通信进程自己负责实现互斥）。

分为两种方式：

基于数据结构的共享：比如共享空间里只能放一个长度为 $10$ 的数组。这种共享方式速度慢、限制多，是一种低级通信方式。
基于存储区的共享：操作系统在内存中划出一块共享存储区，数据的形式、存放位置都由通信进程控制，而不是操作系统。这种共享方式速度很快，是一种高级通信方式。

为避免出错，各个进程对共享空间的访问应该是互斥的。
各个进程可使用操作系统内核提供的同步互斥工具（如$\text{(\text{P})}$、$\text{(\text{V})}$操作）。

消息传递

进程间的数据交换以格式化的消息（$\text{(\text{Message})}$）为单位。进程通过操作系统提供的“发送消息/接收消息”两个原语进行数据交换。

消息由消息头、消息体组成。
消息头包括：发送进程$\text{(\text{ID})}$、接受进程$\text{(\text{ID})}$、消息长度等格式化的信息。

分为两种通信方式：

直接通信方式

消息发送进程要指明接收进程的$\text{(\text{ID})}$，消息直接挂到接收进程的消息队列里。
发送原语：$\text{(\text{send})(Q, (\text{msg}))}$
接收原语：$\text{(\text{receive})((\text{P}), &(\text{msg}))}$

间接通信方式（信箱通信方式）

通过“信箱”间接地通信。
信箱是中间实体，可以多个进程往同一个信箱 $\text{(\text{send})}$ 消息，也可以多个进程从同一个信箱中 $\text{(\text{receive})}$ 消息。
发送原语：$\text{(\text{send})((\text{A}), (\text{msg}))}$，往信箱$\text{(\text{A})}$发送消息 $\text{(\text{msg})}$
接收原语：$\text{(\text{receive})((\text{A}), &(\text{msg}))}$，从信箱$\text{(\text{A})}$接受消息

管道通信

“管道”是一个特殊的共享文件，又名$\text{(\text{pipe})}$文件。其实就是在内存中开辟一个大小固定的内存缓冲区。

管道只能采用半双工通信，某一时间段内只能实现单向的传输。如果要实现双向同时通信，则需要设置两个管道。
各进程要互斥地访问管道（由操作系统实现）。
当管道写满时，写进程将阻塞，直到读进程将管道中的数据取走，即可唤醒写进程。
当管道读空时，读进程将阻塞，直到写进程往管道中写入数据，即可唤醒读进程。
管道中的数据一旦被读出，就彻底消失。因此，当多个进程读同一个管道时，可能会错乱。对此，通常有两种解决方案：①一个管道允许多个写进程，一个读进程（$2014$年$408$真题高教社官方答案）；②允许有多个写进程，多个读进程，但系统会让各个读进程轮流从管道中读数据（$\text{(\text{Linux})}$的方案）。

补充要点：
写进程往管道写数据，即便管道没被写满，只要管道没空，读进程就可以从管道读数据。
读进程从管道读数据，即便管道没被读空，只要管道没满，写进程就可以往管道写数据。

屏幕截图 2026-09-23 193108

2.1.6_2信号

信号（$\text{(\text{signal})}$）用于通知进程某个特定事件已经发生，进程收到一个信号后对该信号进行处理，可实现简单的进程间通信。 “信号”常作为异常处理的一种配套机制。

信号的发送

可以由一个进程给另一个进程发送信号
可以由操作系统内核给进程发送信号
一个进程也可以给自己发送信号
常使用 $\text{(\text{kill})}$ 函数（需指明接收进程的 $\text{(\text{pid})}$、信号的序号）。

信号的保存

在每个进程的 $\text{(\text{PCB})}$ 中，用两个 $\text{N bit}$ 位向量表示待处理信号、被阻塞信号。

$\text{(\text{pending})}$：待处理信号位向量
$\text{(\text{blocked})}$：被阻塞信号位向量，也叫信号掩码（$\text{(\text{signal}) mask}$）
判定可处理信号：$\text{(\text{pending})} \ & \ \sim\text{(\text{blocked})}$

信号的处理

处理时机

当进程从内核态转为用户态时（如：系统调用返回、或中断处理返回时），例行检查是否有待处理信号，如果有，就处理信号。

如何处理

执行默认的信号处理程序
- 操作系统内核对每一种信号都有默认处理程序
- 某些信号默认忽略，不必处理。
执行用户定义的信号处理程序
- 允许进程通过系统调用，自定义某些信号的处理程序
- 自定义信号处理程序将覆盖操作系统的默认处理

信号处理程序运行结束后，通常会返回进程的下一条指令继续执行（除非信号处理程序将进程阻塞或终止）
一旦处理了某个信号，就将 $\text{(\text{pending})}$ 位重置为 $0$
重复收到的同类信号，将被简单地丢弃（因为仅用 $1\ \text{bit}$ 记录一类待处理信号）
当同时收到多个不同类信号时，通常先处理序号更小的信号。

信号与异常的配合机制

“信号”可以作为“异常”的配套机制，让进程对操作系统的异常处理进行补充。在进程运行过程中，某些特殊事件可能引发“异常”，操作系统内核负责捕获并处理异常。

有些异常可以由内核完成全部处理（如：缺页异常），此时就不必再使用信号机制。
有些异常无法由内核完成全部处理，可能还需要用户进程配合，此时就可以用“信号机制”与“异常机制”相互配合（如：在$\text{(\text{Linux})}$中，发生除以$0$异常时，内核的异常处理程序会向用户进程发送$\text{(\text{SIGFPE})}$信号。$\text{(\text{SIGFPE})}$信号的默认处理程序会将进程终止并转储内存；当然进程可以自定义$\text{(\text{SIGFPE})}$信号处理程序）

屏幕截图 2026-09-23 195018

2.1.7_1 线程的概念与特点

有的进程可能需要“同时”做很多事，而传统的进程只能串行地执行一系列程序。为此，引入了“线程”，来增加并发度。

可以把线程理解为轻量级进程。
线程是一个基本的 $CPU$ 执行单元，也是程序执行流的最小单位。
引入线程之后，不仅是进程之间可以并发，进程内的各线程之间也可以并发，从而进一步提升了系统的并发度，使得一个进程内也可以并发处理各种任务（如 $QQ$ 视频、文字聊天、传文件）。

引入线程后，进程只作为除 $CPU$ 之外的系统资源的分配单元（如打印机、内存地址空间等都是分配给进程的）。

引入线程带来的变化

资源分配、调度

传统进程机制中，进程是资源分配、调度的基本单位
引入线程后，进程是资源分配的基本单位，线程是调度的基本单位

并发性

传统进程机制中，只能进程间并发
引入线程后，各线程间也能并发，提升了并发度

系统开销

传统的进程间并发，需要切换进程的运行环境，系统开销很大
线程间并发，如果是同一进程内的线程切换，则不需要切换进程环境，系统开销小
引入线程后，并发所带来的系统开销减小

线程的属性

线程是处理机调度的单位
多 $CPU$ 计算机中，各个线程可占用不同的 $CPU$
每个线程都有一个线程 $ID$、线程控制块（$TCB$）
线程也有就绪、阻塞、运行三种基本状态
线程几乎不拥有系统资源
同一进程的不同线程间共享进程的资源
由于共享内存地址空间，同一进程中的线程间通信甚至无需系统干预
同一进程中的线程切换，不会引起进程切换
不同进程中的线程切换，会引起进程切换
切换同进程内的线程，系统开销很小
切换进程，系统开销较大

2.1.7_2线程的实现方式

用户级线程（$ULT$）

用户级线程由应用程序通过线程库实现，所有的线程管理工作都由应用程序负责（包括线程切换）
用户级线程中，线程切换可以在用户态下即可完成，无需操作系统干预。
在用户看来，是有多个线程。但是在操作系统内核看来，并意识不到线程的存在。
“用户级线程”就是“从用户视角看能看到的线程”。
优缺点
优点：用户级线程的切换在用户空间即可完成，不需要切换到核心态，线程管理的系统开销小，效率高。
缺点：当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高。多个线程不可在多核处理机上并行运行。

屏幕截图 2026-09-23 202444

内核级线程（$KLT$，又称“内核支持的线程”）

内核级线程的管理工作由操作系统内核完成。
线程调度、切换等工作都由内核负责，因此内核级线程的切换必然需要在核心态下才能完成。
操作系统会为每个内核级线程建立相应的 $TCB$（Thread Control Block，线程控制块），通过$TCB$对线程进行管理。“内核级线程”就是“从操作系统内核视角看能看到的线程”。
优缺点
优点：当一个线程被阻塞后，别的线程还可以继续执行，并发能力强。多线程可在多核处理机上并行执行。
缺点：一个用户进程会占用多个内核级线程，线程切换由操作系统内核完成，需要切换到核心态，因此线程管理的成本高，开销大。

多线程模型

在支持内核级线程的系统中，根据用户级线程和内核级线程的映射关系，可以划分为几种多线程模型。

用户级线程是“代码逻辑”的载体
内核级线程是“运行机会”的载体
内核级线程才是处理机分配的单位。一段“代码逻辑”只有获得了“运行机会”才能被$CPU$执行。

多对一模型

多个用户级线程映射到一个内核级线程。且一个进程只被分配一个内核级线程。
优点：用户级线程的切换在用户空间即可完成，不需要切换到核心态，线程管理的系统开销小，效率高。
缺点：当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高。多个线程不可在多核处理机上并行运行。
重点：操作系统只“看得见”内核级线程，因此只有内核级线程才是处理机分配的单位。

一对一模型

一个用户级线程映射到一个内核级线程。每个用户进程有与用户级线程同数量的内核级线程。
优点：当一个线程被阻塞后，别的线程还可以继续执行，并发能力强。多线程可在多核处理机上并行执行。
缺点：一个用户进程会占用多个内核级线程，线程切换由操作系统内核完成，需要切换到核心态，因此线程管理的成本高，开销大。

多对多模型

$n$ 个用户级线程映射到 $m$ 个内核级线程（$n \ge m$）。每个用户进程对应 $m$ 个内核级线程。
克服了多对一模型并发度不高的缺点（一个阻塞全体阻塞），又克服了一对一模型中一个用户进程占用太多内核级线程，开销太大的缺点。
内核级线程中可以运行任意一个有映射关系的用户级线程代码，只有 $m$ 个内核级线程中正在运行的代码逻辑都阻塞时，这个进程才会阻塞。

特点：集二者之所长。

屏幕截图 2026-09-23 202241

2.1.7_3 线程的状态转化与组织控制

线程控制块 $TCB$

线程切换时，需要保存/恢复的信息：

程序计数器 $PC$：记录线程目前执行到哪里
其他寄存器：保存线程运行的中间结果
堆栈指针：堆栈保存函数调用信息、局部变量等

$TCB$ 其余信息：

线程标识符：$TID$，与 $PID$ 类似
线程运行状态：运行 / 就绪 / 阻塞
优先级：线程调度、资源分配的参考

线程表

一个进程内可将多个 $TCB$ 组织成一张线程表，进程的 $PCB$ 会管理这张线程表。

线程三状态转换

线程同样具备就绪、运行、阻塞三种基本状态，转换规则：

屏幕截图 2026-09-23 203246

2.2CUP调度

2.2.1调度的概念、层次

当有一堆任务要处理，但由于资源有限，这些事情没法同时处理。这就需要确定某种规则来决定处理这些任务的顺序，这就是**“调度”**研究的问题。

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

三层调度

	要做什么	调度发生在..	发生频率	对进程状态的影响
高级调度（作业调度）	按照某种规则，从后备队列中选择合适的作业将其调入内存，并为其创建进程	外存$\rightarrow$内存（面向作业）	最低	无$\rightarrow$创建态$\rightarrow$就绪态
中级调度（内存调度）	按照某种规则，从挂起队列中选择合适的进程将其数据调回内存	外存$\rightarrow$内存（面向进程）	中等	挂起态$\rightarrow$就绪态（阻塞挂起$\rightarrow$阻塞态）
低级调度（进程调度）	按照某种规则，从就绪队列中选择一个进程为其分配处理机	内存$\rightarrow$$CPU$	最高	就绪态$\rightarrow$运行态

高级调度（作业调度）

按照一定的原则从外存的作业后备队列中挑选一个作业调入内存，并创建进程。
每个作业只调入一次，调出一次。作业调入时会建立 $PCB$，调出时才撤销 $PCB$。

中级调度（内存调度）

按照某种策略决定将哪个处于挂起状态的进程重新调入内存。
一个进程可能会被多次调出、调入内存，因此中级调度发生的频率要比高级调度更高。

内存不够时，可将某些进程的数据调出外存。等内存空闲或者进程需要运行时再重新调入内存。
暂时调到外存等待的进程状态为挂起状态。被挂起的进程 $PCB$ 会被组织成挂起队列。

低级调度（进程调度 / 处理机调度）

按照某种策略从就绪队列中选取一个进程，将处理机分配给它。
进程调度是操作系统中最基本的一种调度，在一般的操作系统中都必须配置进程调度。
进程调度的频率很高，一般几十毫秒一次。

七状态模型

暂时调到外存等待的进程状态为挂起状态（挂起态，$\text{(\text{suspend})}$）
挂起态又可以进一步细分为就绪挂起、阻塞挂起两种状态
五状态模型 $\rightarrow$ 七状态模型

注意**“挂起”和“阻塞”**的区别，两种状态都是暂时不能获得 $CPU$ 的服务，但挂起态是将进程映像调到外存去了，而阻塞态下进程映像还在内存中。
有的操作系统会把就绪挂起、阻塞挂起分为两个挂起队列，甚至会根据阻塞原因不同再把阻塞挂起进程进一步细分为多个队列。

屏幕截图 2026-09-23 204542

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

进程调度（低级调度）

进程调度（低级调度），就是按照某种算法从就绪队列中选择一个进程为其分配处理机。

进程调度的时机

什么时候需要进程调度

当前运行的进程主动放弃处理机
- 进程正常终止
- 运行过程中发生异常而终止
- 主动阻塞（如等待 $\text{(\text{I/O})}$）
当前运行的进程被动放弃处理机
- 分给进程的时间片用完
- 有更紧急的事情需要处理（如 $\text{(\text{I/O})}$ 中断）
- 有更高优先级的进程进入就绪队列

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

在处理中断的过程中
进程在操作系统内核程序临界区中
原子操作过程中（原语）

注意：

进程在操作系统内核程序临界区中不能进行调度与切换

进程处于临界区时不能进行处理机调度

临界资源：一个时间段内只允许一个进程使用的资源。各进程需要互斥地访问临界资源。
临界区：访问临界资源的那段代码。

内核程序临界区一般是用来访问某种内核数据结构的，比如进程的就绪队列（由各就绪进程的 $\text{(\text{PCB})}$ 组成）。

内核程序临界区：访问的临界资源如果不尽快释放，极有可能影响到操作系统内核的其他管理工作，因此在访问内核程序临界区期间不能进行调度与切换。

普通临界区：访问的临界资源不会直接影响操作系统内核的管理工作，因此在访问普通临界区时可以进行调度与切换。

进程切换与过程

狭义的“调度”和“切换”的区别

狭义的进程调度：指的是从就绪队列中选中一个要运行的进程。（这个进程可以是刚刚被暂停执行的进程，也可能是另一个进程，后一种情况就需要进程切换）
进程切换：是指一个进程让出处理机，由另一个进程占用处理机的过程。
广义的进程调度：包含了选择一个进程和进程切换两个步骤。

切换过程

对原来运行进程各种数据的保存
对新的进程各种数据的恢复

例：程序计数器、程序状态字、各种数据寄存器等处理机现场信息，这些信息一般保存在进程控制块。

注意：进程调度、切换是有代价的，并不是调度越频繁，并发度就越高。如果过于频繁的进行进程调度、切换，必然会使整个系统的效率降低，使系统大部分时间都花在了进程切换上，而真正用于执行进程的时间减少。

进程调度方式

非剥夺调度方式（非抢占式）

只允许当前运行的进程主动放弃 $\text{(\text{CPU})}$。

特点：实现简单，系统开销小，但是无法及时处理紧急任务，适合于早期的批处理系统。

剥夺调度方式（抢占式）

可由操作系统剥夺当前进程的 $\text{(\text{CPU})}$ 使用权。当一个进程正在处理机上执行时，如果有一个更重要或更紧迫的进程需要使用处理机，则立即暂停正在执行的进程，将处理机分配给更重要紧迫的那个进程。

特点：可以优先处理更紧急的进程，也可实现让各进程按时间片轮流执行的功能（通过时钟中断）。适合于分时操作系统、实时操作系统。

屏幕截图 2026-09-23 205651

2.2.2_2调度器和闲逛进程

调度程序（$\text{(\text{scheduler})}$）

不支持内核级线程的操作系统，调度程序的处理对象是进程。
支持内核级线程的操作系统，调度程序的处理对象是内核线程。

进程三态切换与调度触发

②、③由调度程序引起，调度程序决定：

让谁运行？——调度算法
运行多长时间？——时间片大小

调度时机：什么事件会触发“调度程序”？

创建新进程
进程退出
运行进程阻塞
$\text{(\text{I/O})}$中断发生（可能唤醒某些阻塞进程）
非抢占式调度策略，只有运行进程阻塞或退出才触发调度程序工作
抢占式调度策略，每个时钟中断或 $k$ 个时钟中断会触发调度程序工作

闲逛进程（$\text{(\text{idle})}$）

调度程序永远的备胎，没有其他就绪进程时，运行闲逛进程（$\text{(\text{idle})}$）。

闲逛进程的特性：

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

2.2.3调度指标

$CPU$ 利用率

$CPU$ 利用率：指 $CPU$ “忙碌”的时间占总时间的比例。
$$
\text{利用率} = \frac{\text{忙碌的时间}}{\text{总时间}}
$$
也有题目会让我们计算某设备的利用率。

系统吞吐量

系统吞吐量：单位时间内完成作业的数量。
$$
\text{系统吞吐量}= \frac{\text{总共完成了多少道作业}}{\text{总共花了多少时间}}
$$

周转时间

周转时间，是指从作业被提交给系统开始，到作业完成为止的这段时间间隔。
它包括四个部分：作业在外存后备队列上等待作业调度（高级调度）的时间、进程在就绪队列上等待进程调度（低级调度）的时间、进程在 $CPU$ 上执行的时间、进程等待 $I/O$ 操作完成的时间。后三项在一个作业的整个处理过程中，可能发生多次。
$$
\text{（作业）周转时间} = \text{作业完成时间} - \text{作业提交时间}
$$
$$
\text{平均周转时间} = \frac{\text{各作业周转时间之和}}{\text{作业数}}
$$
$$
\text{带权周转时间} = \frac{\text{作业周转时间}}{\text{作业实际运行的时间}} = \frac{\text{作业完成时间} - \text{作业提交时间}}{\text{作业实际运行的时间}}
$$

带权周转时间必然 $\ge 1$
带权周转时间与周转时间都是越小越好
$$
\text{平均带权周转时间} = \frac{\text{各作业带权周转时间之和}}{\text{作业数}}
$$

等待时间

等待时间，指进程/作业处于等待处理机状态时间之和，等待时间越长，用户满意度越低。

对于进程来说，等待时间就是指进程建立后等待被服务的时间之和，在等待 $I/O$ 完成的期间其实进程也是在被服务的，所以不计入等待时间。
对于作业来说，不仅要考虑建立进程后的等待时间，还要加上作业在外存后备队列中等待的时间。

一个作业总共需要被 $CPU$ 服务多久，被 $I/O$ 设备服务多久一般是确定不变的，因此调度算法其实只会影响作业/进程的等待时间。
平均等待时间即各个进程/作业等待时间的平均值。

响应时间

响应时间，指从用户提交请求到首次产生响应所用的时间。

屏幕截图 2026-09-23 211742

2.2.4_1调度算法（批处理）

先来先服务（$FCFS$, First Come First Serve）

算法思想：主要从公平的角度考虑，类似于生活中排队。
算法规则：按照作业/进程到达的先后顺序进行服务。
用于作业/进程调度：用于作业调度时，考虑哪个作业先到达后备队列；用于进程调度时，考虑哪个进程先到达就绪队列。
是否可抢占？：非抢占式的算法。
优缺点
- 优点：公平、算法实现简单。
- 缺点：排在长作业（进程）后面的短作业需要等待很长时间，带权周转时间很大，对短作业来说用户体验不好。即，$FCFS$ 算法对长作业有利，对短作业不利。
是否会导致饥饿：不会。

短作业优先（$SJF$, Shortest Job First）

算法思想：追求最少的平均等待时间，最少的平均周转时间、最少的平均带权周转时间。
算法规则：最短的作业/进程优先得到服务（所谓“最短”，是指要求服务时间最短）。
用于作业/进程调度：即可用于作业调度，也可用于进程调度。用于进程调度时称为“短进程优先（$SPF$, Shortest Process First）算法”。
是否可抢占？：$SJF$ 和 $SPF$ 是非抢占式的算法。但是也有抢占式的版本——最短剩余时间优先算法（$SRTN$, Shortest Remaining Time Next）。
优缺点
- 优点：得到最短的平均等待时间、平均周转时间。
- 缺点：不公平。对短作业有利，对长作业不利。可能产生饥饿现象。另外，作业/进程的运行时间是由用户提供的，并不一定真实，不一定能做到真正的短作业优先。
是否会导致饥饿：会。如果源源不断地有短作业/进程到来，可能使长作业/进程长时间得不到服务，产生饥饿现象。如果一直得不到服务，则称为饿死。

重要考点备注

如果题目中未特别说明，所提到的“短作业/进程优先算法”默认是非抢占式的。

很多书上都会说“$SJF$ 调度算法的平均等待时间、平均周转时间最少”。
严格来说，这个表述是错误的，不严谨的。最短剩余时间优先算法得到的平均等待时间、平均周转时间还要更少。
应该加上一个条件在所有进程同时可运行时，采用 $SJF$ 调度算法的平均等待时间、平均周转时间最少；
或者说在所有进程都几乎同时到达时，采用 $SJF$ 调度算法的平均等待时间、平均周转时间最少；
如果不加上上述前提条件，则应该说抢占式的短作业/进程优先调度算法（最短剩余时间优先，$SRTN$ 算法）的平均等待时间、平均周转时间最少。

虽然严格来说，$SJF$ 的平均等待时间、平均周转时间并不一定最少，但相比于其他算法（如 $FCFS$），$SJF$ 依然可以获得较少的平均等待时间、平均周转时间。

如果选择题中遇到“$SJF$ 算法的平均等待时间、平均周转时间最少”的选项，那最好判断其他选项是不是有很明显的错误，如果没有更合适的选项，那也应该选择该选项。

高响应比优先（$HRRN$, Highest Response Ratio Next）

算法思想：要综合考虑作业/进程的等待时间和要求服务的时间。
算法规则：在每次调度时先计算各个作业/进程的响应比，选择响应比最高的作业/进程为其服务。
$$
\text{响应比} = \frac{\text{等待时间}+\text{要求服务时间}}{\text{要求服务时间}}
$$
$\text{响应比} \ge 1$
用于作业/进程调度：即可用于作业调度，也可用于进程调度。
是否可抢占？：非抢占式的算法。因此只有当前运行的作业/进程主动放弃处理机时，才需要调度，才需要计算响应比。
优缺点：综合考虑了等待时间和运行时间（要求服务时间）。
- 等待时间相同时，要求服务时间短的优先（$SJF$ 的优点）。
- 要求服务时间相同时，等待时间长的优先（$FCFS$ 的优点）。
- 对于长作业来说，随着等待时间越来越久，其响应比也会越来越大，从而避免了长作业饥饿的问题。
是否会导致饥饿：不会。

三种算法对比汇总表

算法	思想&规则	可抢占？	优点	缺点	考虑等待时间&运行时间？	会导致饥饿？
$FCFS$	按到达先后顺序服务	非抢占式	公平；实现简单	对短作业不利	等待时间$\checkmark$，运行时间$\times$	不会
$SJF$/$SPF$	要求服务时间短的优先	默认为非抢占式，抢占式版本为 $SRTN$	“最短的”平均等待/周转时间	对长作业不利，可能导致饥饿；难以做到真正的短作业优先	等待时间$\times$，运行时间$\checkmark$	会
$HRRN$	选择响应比最高的作业	非抢占式	上述两种算法的权衡折中，综合考虑等待时间和运行时间		等待时间$\checkmark$，运行时间$\checkmark$	不会

注：这几种算法主要关心对用户的公平性、平均周转时间、平均等待时间等评价系统整体性能的指标，但是不关心响应时间，也并不区分任务的紧急程度，因此对于用户来说，交互性很糟糕。因此这三种算法一般适合用于早期的批处理系统，当然，$FCFS$ 算法也常结合其他的算法使用，在现在也扮演着很重要的角色。而适合用于交互式系统的调度算法将在下个小节介绍。

2.2.4_2调度算法（交互）

优先级调度算法

算法思想

随着计算机的发展，特别是实时操作系统的出现，越来越多的应用场景需要根据任务的紧急程度来决定处理顺序。

算法规则

调度时选择优先级最高的作业/进程。

用于作业/进程调度

既可用于作业调度，也可用于进程调度。甚至，还会用于在之后会学习的 $(I/O)$ 调度中。

是否可抢占？

抢占式、非抢占式都有。做题时的区别在于：非抢占式只需在进程主动放弃处理机时进行调度即可，而抢占式还需在就绪队列变化时，检查是否会发生抢占。

优缺点

优点：用优先级区分紧急程度、重要程度，适用于实时操作系统。可灵活地调整对各种作业/进程的偏好程度。
缺点：若源源不断地有高优先级进程到来，则可能导致饥饿。

是否会导致饥饿

会

补充

就绪队列未必只有一个，可以按照不同优先级来组织。另外，也可以把优先级高的进程排在更靠近队头的位置。
根据优先级是否可以动态改变，可将优先级分为静态优先级和动态优先级两种。

静态优先级：创建进程时确定，之后一直不变。
动态优先级：创建进程时有一个初始值，之后会根据情况动态地调整优先级。
通常：
系统进程优先级高于用户进程
前台进程优先级高于后台进程
操作系统更偏好 $I/O$ 型进程（或称 $I/O$ 繁忙型进程）
注：与 $I/O$ 型进程相对的是计算型进程（或称 $CPU$ 繁忙型进程）。$I/O$ 设备和 $CPU$ 可以并行工作。如果优先让 $I/O$ 繁忙型进程优先运行的话，则越有可能让 $I/O$ 设备尽早地投入工作，则资源利用率、系统吞吐量都会得到提升。
如果采用的是动态优先级，什么时候应该调整？可以从追求公平、提升资源利用率等角度考虑。
如果某进程在就绪队列中等待了很长时间，则可以适当提升其优先级
如果某进程占用处理机运行了很长时间，则可适当降低其优先级
如果发现一个进程频繁地进行 $I/O$ 操作，则可适当提升其优先级

时间片轮转（$RR$，$Round-Robin$）

算法思想

公平地、轮流地为各个进程服务，让每个进程在一定时间间隔内都可以得到响应。

算法规则

按照各进程到达就绪队列的顺序，轮流让各个进程执行一个时间片（如 $100\ \text{ms}$）。若进程未在一个时间片内执行完，则剥夺处理机，将进程重新放到就绪队列队尾重新排队。

用于作业/进程调度

用于进程调度（只有作业放入内存建立了相应的进程后，才能被分配处理机时间片）。

是否可抢占？

若进程未能在时间片内运行完，将被强行剥夺处理机使用权，因此时间片轮转调度算法属于抢占式的算法。由时钟装置发出时钟中断来通知 $CPU$ 时间片已到。

优缺点

优点：公平；响应快，适用于分时操作系统；
缺点：由于高频率的进程切换，因此有一定开销；不区分任务的紧急程度。

是否会导致饥饿

不会

补充：时间片太大或太小分别有什么影响？

如果时间片太大，使得每个进程都可以在一个时间片内就完成，则时间片轮转调度算法退化为先来先服务调度算法，并且会增大进程响应时间。因此时间片不能太大。
另一方面，进程调度、切换是有时间代价的（保存、恢复运行环境），因此如果时间片太小，会导致进程切换过于频繁，系统会花大量的时间来处理进程切换，从而导致实际用于进程执行的时间比例减少。可见时间片也不能太小。

多级反馈队列调度算法

算法思想

对其他调度算法的折中权衡。

算法规则

设置多级就绪队列，各级队列优先级从高到低，时间片从小到大。
新进程到达时先进入第 $1$ 级队列，按 $FCFS$ 原则排队等待被分配时间片，若用完时间片进程还未结束，则进程进入下一级队列队尾。如果此时已经是在最下级的队列，则重新放回该队列队尾。
只有第 $k$ 级队列为空时，才会为 $(k+1)$ 级队头的进程分配时间片。

用于作业/进程调度

用于进程调度。

是否可抢占？

抢占式的算法。在 $k$ 级队列的进程运行过程中，若更上级的队列（$1$~$k-1$ 级）中进入了一个新进程，则由于新进程处于优先级更高的队列中，因此新进程会抢占处理机，原来运行的进程放回 $k$ 级队列队尾。

优缺点

对各类型进程相对公平（$FCFS$ 的优点）；每个新到达的进程都可以很快就得到响应（$RR$ 的优点）；短进程只用较少的时间就可完成（$SPF$ 的优点）；不必实现估计进程的运行时间（避免用户作假）；可灵活地调整对各类进程的偏好程度，比如 $CPU$ 密集型进程、$I/O$ 密集型进程（拓展：可以将因 $I/O$ 而阻塞的进程重新放回原队列，这样 $I/O$ 型进程就可以保持较高优先级）。

是否会导致饥饿

会

调度算法对比表

算法	思想&规则	可抢占？	优点	缺点	会导致饥饿？	补充
时间片轮转		抢占式	公平，适用于分时系统	频繁切换有开销，不区分优先级	不会	时间片太大或太小有何影响？
优先级调度		有抢占式的，也有非抢占式的。注意做题时的区别	区分优先级，适用于实时系统	可能导致饥饿	会	动态/静态优先级。各类型进程如何设置优先级？如何调整优先级？
多级反馈队列	较复杂，注意理解	抢占式	平衡优秀	一般不说它有缺点，不过可能导致饥饿	会

多级反馈队列调度算法是现代操作系统中最常用的进程调度算法。由于计算机的平均响应时间、公平性等指标很难同时达到最优，因此它通过综合多种算法思想（包括 $FCFS$ 、 $RR$ 、 $SPF$ 、优先级调度等），在不同场景下取得较好的折中效果。

2.2.4_3调度算法（多级队列调度算法）

算法思想

系统中按进程类型设置多个队列，进程创建成功后插入某个对应的队列。

算法规则

不同队列拥有不同优先级，图示优先级从高到低：系统进程队列 > 交互式进程队列 > 批处理进程队列
- 系统进程（如内存管理进程）
- 交互式进程（如游戏、打字软件）
- 批处理进程（如$AI$模型训练、视频特效渲染）
队列之间的调度方式分为两种：
- 固定优先级：高优先级队列为空时，低优先级队列的进程才能够被调度。
- 时间片划分：给各个队列分配固定的$CPU$时间比例，例如三个队列分配时间$50%$、$40%$、$10%$。
各个队列内部可以采用不同的调度策略，举例：
- 系统进程队列采用优先级调度
- 交互式队列采用$RR$
- 批处理队列采用$FCFS$

补充

多级队列调度和多级反馈队列调度核心区别：多级队列：进程归属队列固定不变；多级反馈队列：进程可以在不同队列之间动态迁移。

2.2.6多处理机调度

单处理机调度与多处理机调度对比

单处理机调度：只需决定让哪个就绪进程优先上处理机即可。
多处理机调度：①用调度算法决定让哪个就绪进程优先上处理机；②还需决定被调度的进程到底上哪个处理机。

多处理机调度的两个目标

负载均衡：尽可能让每个 $CPU$ 都同等忙碌。
处理机亲和性：尽量让一个进程调度到同一个 $CPU$ 上运行，以发挥 $CPU$ 中缓存（$Cache$）的作用。

方案一：公共就绪队列

所有 $CPU$ 共享同一个就绪进程队列（位于内核区）。每个 $CPU$ 运行调度程序，从公共就绪队列中选择一个进程运行；每个 $CPU$ 访问公共就绪队列时需要上锁，确保互斥。

优点：可以天然地实现负载均衡。
缺点：各个进程可能会频繁地换 $CPU$ 运行，亲和性不好。
提升处理机亲和性的方式
- 软亲和：由进程调度程序尽量保证“亲和性”。
- 硬亲和：由用户进程通过系统调用，主动要求操作系统分配固定的 $CPU$，确保“亲和性”。
  
  软亲和与硬亲和可以混用。

方案二：私有就绪队列

每个 $CPU$ 都有一个私有就绪队列。$CPU$ 空闲时运行调度程序，从私有就绪队列中选择一个进程运行。

优点：天然地实现了处理机亲和性。
缺点：很难天然实现负载均衡，需要额外策略。
负载均衡策略
- 推迁移（$Push$）策略：一个特定的系统程序周期性检查每个处理器的负载，如果负载不平衡，就从忙碌 $CPU$ 的就绪队列中“推”一些就绪进程到空闲 $CPU$ 的就绪队列。
- 拉迁移（$Pull$）策略：每个 $CPU$ 运行调度程序时，周期性检查自身负载与其他 $CPU$ 负载。如果一个 $CPU$ 负载很低，就从其他高负载 $CPU$ 的就绪队列中“拉”一些就绪进程到自己的就绪队列。

屏幕截图 2026-09-23 221828

2.3进程同步与互斥

2.3.1同步与互斥的基本概念

进程同步

并发性带来了异步性，有时需要通过进程同步解决这种异步问题。有的进程之间需要相互配合地完成工作，各进程的工作推进需要遵循一定的先后顺序。

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

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

进程互斥

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

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

对临界资源的访问，需要互斥的进行。即同一时间段内只能允许一个进程访问该资源

临界区代码的四个部分

do {
    entry section;     // 进入区
    critical section;  // 临界区
    exit section;      // 退出区
    remainder section; // 剩余区
} while(true);

进入区：检查是否可进入临界区，若可进入，需要“上锁”，设置正在访问临界资源的标志，阻止其他进程同时进入临界区。
临界区：访问临界资源的那段代码，临界区也可称为“临界段”。
退出区：负责“解锁”，解除正在访问临界资源的标志。
剩余区：其余代码部分，做其他处理。

注意：
临界区是进程中访问临界资源的代码段。
进入区和退出区是负责实现互斥的代码段。

临界区互斥访问需要遵循的原则

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

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

屏幕截图 2026-09-23 222717

2.3.2_1软件实现互斥

单标志法

算法思想：两个进程在访问完临界区后，会把使用临界区的权限转交给另一个进程。也就是说每个进程进入临界区的权限只能被另一个进程赋予。
共享变量：$\text{int } turn = 0$；$turn$ 表示当前允许进入临界区的进程号。
$\text{P0}$ 进程：
1. $\text{while }(turn != 0)$；
2. $\text{critical section}$；
3. $turn = 1$；
4. $\text{remainder section}$；
$\text{P1}$ 进程：
1. $\text{while }(turn != 1)$；
2. $\text{critical section}$；
3. $turn = 0$；
4. $\text{remainder section}$；
执行说明：$turn$ 的初值为 $0$，即刚开始只允许 $0$ 号进程进入临界区。若 $\text{P1}$ 先上处理机运行，则会一直卡在⑤。直到 $\text{P1}$ 的时间片用完，发生调度，切换 $\text{P0}$ 上处理机运行。代码①不会卡住 $\text{P0}$，$\text{P0}$ 可以正常访问临界区，在 $\text{P0}$ 访问临界区期间即时切换回 $\text{P1}$，$\text{P1}$ 依然会卡在⑤。只有 $\text{P0}$ 在退出区将 $turn$ 改为 $1$ 后，$\text{P1}$ 才能进入临界区。
结论：该算法可以实现同一时刻最多只允许一个进程访问临界区。
缺点：违背空闲让进。只能按 $\text{P0}\rightarrow\text{P1}\rightarrow\text{P0}\rightarrow\text{P1}\dots$ 轮流访问。若允许进入临界区的进程是 $\text{P0}$，而 $\text{P0}$ 一直不访问临界区，那么虽然此时临界区空闲，但是并不允许 $\text{P1}$ 访问。

双标志先检查法

算法思想：设置一个布尔型数组 $flag[]$，数组中各个元素用来标记各进程想进入临界区的意愿。比如 $flag[0]=\text{true}$ 意味着 $0$ 号进程 $\text{P0}$ 现在想要进入临界区。每个进程在进入临界区之前先检查当前有没有别的进程想进入临界区，如果没有，则把自身对应的标志 $flag[i]$ 设为 $\text{true}$，之后开始访问临界区。
共享变量：$\text{bool }flag[2]$；$flag[0]=\text{false}$；$flag[1]=\text{false}$；刚开始设置为两个进程都不想进入临界区。
$\text{P0}$ 进程：
1. $\text{while }(flag[1])$；
2. $flag[0]=\text{true}$；
3. $\text{critical section}$；
4. $flag[0]=\text{false}$；
  $\text{remainder section}$；
$\text{P1}$ 进程：
1. $\text{while }(flag[0])$；
2. $flag[1]=\text{true}$；
3. $\text{critical section}$；
4. $flag[1]=\text{false}$；
  $\text{remainder section}$；
执行说明：若按照 ①⑤②⑥③⑦… 的顺序执行，$\text{P0}$ 和 $\text{P1}$ 将会同时访问临界区。
缺点：违反忙则等待。原因在于，进入区的“检查”和“上锁”两个处理不是一气呵成的。“检查”后，“上锁”前可能发生进程切换。

双标志后检查法

算法思想：双标志先检查法的改版。前一个算法的问题是先“检查”后“上锁”，但是这两个操作又无法一气呵成，因此导致了两个进程同时进入临界区的问题。因此，人们又想到先“上锁”后“检查”的方法，来避免上述问题。
共享变量：$\text{bool }flag[2]$；$flag[0]=\text{false}$；$flag[1]=\text{false}$；刚开始设置为两个进程都不想进入临界区。
$\text{P0}$ 进程：
1. $flag[0]=\text{true}$；
2. $\text{while }(flag[1])$；
3. $\text{critical section}$；
4. $flag[0]=\text{false}$；
  $\text{remainder section}$；
$\text{P1}$ 进程：
1. $flag[1]=\text{true}$；
2. $\text{while }(flag[0])$；
3. $\text{critical section}$；
4. $flag[1]=\text{false}$；
  $\text{remainder section}$；
执行说明：若按照 ①⑤②⑥… 的顺序执行，$\text{P0}$ 和 $\text{P1}$ 将都无法进入临界区。
缺点：违背空闲让进、有限等待，会产生“饥饿”现象。两个进程都争着想进入临界区，但是谁也不让谁，最后谁都无法进入临界区。

Peterson（皮特森）算法

算法思想：结合双标志法、单标志法的思想。如果双方都争着想进入临界区，那可以让进程尝试“孔融让梨”（谦让）。
共享变量：$\text{bool }flag[2]$；表示进入临界区意愿的数组，初始值都是 $\text{false}$；$\text{int }turn = 0$；$turn$ 表示优先让哪个进程进入临界区。
$\text{P0}$ 进程：
1. $flag[0]=\text{true}$；
2. $turn = 1$；
3. $\text{while }(flag[1] && turn==1)$；
4. $\text{critical section}$；
5. $flag[0]=\text{false}$；
  $\text{remainder section}$；
$\text{P1}$ 进程：
1. $flag[1]=\text{true}$；
2. $turn = 0$；
3. $\text{while }(flag[0] && turn==0)$；
4. $\text{critical section}$；
5. $flag[1]=\text{false}$；
  $\text{remainder section}$；
进入区三步：1.主动争取；2.主动谦让；3.检查对方是否也想使用，且最后一次是不是自己说了“客气话”。
优点：遵循空闲让进、忙则等待、有限等待三个原则。
缺点：不遵循让权等待，会发生忙等。
总结：Peterson 算法相较于之前三种软件解决方案来说，是最好的，但依然不够好。

软件互斥算法对比小结

单标志法：在进入区只做“检查”，不“上锁”；在退出区把临界区的使用权转交给另一个进程；主要问题：不遵循空闲让进。
双标志先检查：在进入区先“检查”后“上锁”，退出区“解锁”；主要问题：不遵循忙则等待。
双标志后检查：在进入区先“加锁”后“检查”，退出区“解锁”；主要问题：不遵循空闲让进、有限等待，可能导致饥饿。
Peterson 算法：在进入区“主动争取—主动谦让—检查对方是否想进、己方是否谦让”；主要问题：不遵循让权等待，会发生忙等。

2.3.2_2硬件实现互斥

中断屏蔽方法

原理：进程访问临界区前执行关中断，此时不允许发生中断，不会触发进程切换；访问完临界区后再执行开中断，允许其他进程调度。

1
2
3

关中断;
临界区;
开中断;

优点：简单高效
缺点：只适用于单处理机；只适用于操作系统内核进程，不能用于用户进程，开/关中断指令只能在内核态执行。

$\text{TestAndSet}$（ $\text{TS}$ 指令 / $\text{(\text{TSL})}$ 指令）

$\text{(\text{TSL})}$ 指令由硬件实现，执行过程不可中断，属于原子操作。
用 $\text{(\text{C})}$ 语言描述逻辑：

bool TestAndSet (bool *lock){
    bool old;
    old = *lock;    // $old$ 存放 $lock$ 原来的值
    *lock = true;   // 将 $lock$ 设置为 $true$
    return old;     // 返回 $lock$ 原来的值
}

使用 $\text{(\text{TSL})}$ 实现互斥的算法逻辑：

while (TestAndSet (&lock)); // "上锁"并"检查"
临界区代码段...
lock = false;               // "解锁"
剩余区代码段...

逻辑： $old$ 记录临界区是否上锁；再将 $lock$ 设为 $true$；检查临界区上锁状态，若已上锁则循环重复前几步。
优点：实现简单；适用于多处理机环境
缺点：不满足让权等待，暂时无法进入临界区的进程会占用 $\text{(\text{(\text{C})PU})}$ 并循环执行指令，产生忙等。

$\text{(\text{Swap})}$ 指令（ $\text{(\text{X(\text{C})HG})}$ 指令）

又称 $\text{(\text{Exchange})}$ 指令，硬件实现，执行过程不可中断，属于原子操作，逻辑上同 $\text{(\text{TSL})}$。
用 $\text{(\text{C})}$ 语言描述指令作用：

Swap (bool *a, bool *b) {
    bool temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

使用 $\text{(\text{Swap})}$ 实现互斥的算法逻辑：

bool old = true;
while (old == true)
    Swap (&lock, &old);
临界区代码段...
lock = false;
剩余区代码段...

逻辑：先记录临界区上锁状态到 $old$，再将上锁标记 $lock$ 置为 $true$；若 $old$ 为 $false$，代表没有进程占用临界区，跳出循环进入临界区。
优点：实现简单，无需像软件方法一样排查逻辑漏洞；适用于多处理机环境
缺点：不满足让权等待，会产生忙等。

小结： $\text{(\text{TSL})}$ 与 $\text{(\text{Swap})}$ 本质都是利用硬件原子指令完成上锁+检查，适合多处理机；中断屏蔽仅单处理机、内核态可用。

屏幕截图 2026-09-28 211945

2.3.2_3互斥锁

互斥锁是实现临界区互斥访问的基础工具。逻辑上分为两个操作：$ \text{acquire}() $ 获取锁（上锁）、$ \text{release}() $ 释放锁（解锁）。

进程进入临界区前执行 $ \text{acquire}() $；退出临界区后执行 $ \text{release}() $。$ \text{acquire}() $ 与 $ \text{release}() $ 必须是原子操作，一般依靠硬件原子指令（$ \text{(\text{TSL})} $、$ \text{(\text{Swap})} $）实现。

伪代码逻辑：

bool available = true;    // true代表锁空闲，false代表锁被占用

acquire(){
    while(!available);   // 循环忙等，直到锁空闲
    available = false;   // 获取锁，将锁标记为占用
}

release(){
    available = true;    // 释放锁，标记锁空闲
}

自旋锁（忙等锁）

上面这种获取锁失败就循环检测、不主动让出 $ \text{(\text{CPU})} $ 的互斥锁称为自旋锁。$ \text{(\text{TSL})} $、$ \text{(\text{Swap})} $ 指令实现的锁本质都是自旋锁。

特点
1. 不满足让权等待，发生忙等；进程只有时间片用完才会被剥夺 $ \text{(\text{CPU})} $。满足空闲让进、忙则等待、有限等待。
2. 优点：等待时不发生进程上下文切换；如果临界区执行时间很短，整体开销很小。
3. 适合多处理机系统：一个 $ \text{(\text{CPU})} $ 上进程自旋等待，另一个 $ \text{(\text{CPU})} $ 上持有锁的进程可以继续执行，能很快释放锁。
4. 不适合单处理机系统：自旋的进程占用 $ \text{(\text{CPU})} $，持有锁的进程得不到调度，永远无法释放锁，死循环自旋。

小结：自旋锁等待期间 $ \text{(\text{CPU})} $ 空转消耗资源；临界区短、多核场景收益大。

挂起等待锁（睡眠互斥锁 $ \text{(\text{Mutex})} $）

为了解决自旋锁忙等浪费 $ \text{(\text{CPU})} $ 的问题，设计挂起等待锁。

获取锁失败时：进程从运行态变为阻塞态，主动放弃 $ \text{(\text{CPU})} $，进入锁对应的等待队列（满足让权等待）。
锁被释放时：操作系统从等待队列唤醒一个阻塞进程，变为就绪态等待调度。
特点
1. 满足让权等待，不会忙等，$ \text{(\text{CPU})} $ 可以调度其他进程工作。
2. 缺点：进程阻塞、唤醒需要上下文切换，有系统开销。
3. 适合临界区执行时间较长的场景。

自旋锁 vs 挂起等待锁对比表

类型	获取锁失败行为	是否忙等	是否满足让权等待	开销	适用场景
自旋锁	循环轮询检测锁，不放弃 $ \text{(\text{CPU})} $	忙等	不满足	无上下文切换，$ \text{(\text{CPU})} $ 空转消耗	多核、临界区很短
挂起等待锁($ \text{(\text{Mutex})} $)	进程阻塞，让出 $ \text{(\text{CPU})} $，进入等待队列	不忙等	满足	阻塞唤醒，上下文切换开销	临界区较长，单/多核通用

补充：现代操作系统存在两阶段锁（混合锁），先自旋一小段时间；自旋仍拿不到锁，则把进程阻塞挂起，结合两种锁的优点。

考点回顾：软件 $ \text{(\text{Peterson})} $ 算法、$\text{(\text{TSL})}$、$\text{(\text{Swap})}$ 指令实现互斥，全部属于自旋锁，都不满足让权等待。想要实现让权等待，需要依靠信号量机制。

2.3.4_1信号量机制

信号量本质是一个变量（可以是整数，也可以是记录型变量），用来表示系统中某种资源的数量。用户进程通过操作系统提供的一对原语操作信号量，实现进程互斥、进程同步。

原语：特殊程序段，执行一气呵成，不可被中断，一般通过关中断/开中断指令实现。 $wait(S)$、$signal(S)$ 原语，常简称为 $P$、$V$ 操作；做题中 $wait(S)$ 记作 $P(S)$，$signal(S)$ 记作 $V(S)$。

整型信号量

用一个整型变量作为信号量，数值代表某种资源的数量。

与普通整型变量区别：对信号量仅可执行**初始化、$P$、$V$**三种操作。
伪代码：

int S = 1;

void wait(int S){
    while(S <= 0);
    S = S - 1;
}

void signal(int S){
    S = S + 1;
}

存在的问题：不满足让权等待原则，资源不足时循环忙等，会浪费 $CPU$。

记录型信号量

大题、小题超高频出题点。为解决整型信号量忙等问题而提出。

结构体定义

typedef struct {
    int value;        // 剩余资源数
    struct process *L; // 等待该资源的进程队列
} semaphore;

$(S.value)$ 初值代表系统中该类资源的总数。

$(P(wait))$ 操作

void wait(semaphore S){
    S.value --;
    if (S.value) < 0) {
        block(S.L);
    }
}

先执行 $S.value–$，代表申请 $1$ 个单位资源。
若 $S.value < 0$：资源耗尽，调用 $block$ 原语，进程从运行态转为阻塞态，主动放弃处理机，挂入等待队列 $(S.L)$。
该机制满足让权等待，无忙等现象。

$V(signal)$ 操作

void signal(semaphore S){
    S.value ++;
    if (S.value) <= 0) {
        wakeup(S.L);
    }
}

先执行 $(S.value)++$，代表释放 $1$ 个单位资源。
若 $(S.value) \le 0$：队列仍存在等待进程，调用 $wakeup$ 原语，唤醒等待队列队首进程，进程由阻塞态转为就绪态。

核心要点

$P$ 操作：先 $(S.value)–$，之后可能执行 $block$ 原语。
$V$ 操作：先 $(S.value)++$，之后可能执行 $wakeup$ 原语。
要求能够自行推断执行 $block$ 或 $wakeup$ 的触发条件。
用途：实现系统资源的申请与释放；实现进程互斥、进程同步。

整型信号量 vs 记录型信号量对比

类型	数据结构	资源不足时行为	是否满足让权等待
整型信号量	单纯整型变量	循环忙等，占用 $CPU$	不满足
记录型信号量	结构体（$value$ + 等待队列）	进程阻塞，让出 $CPU$	满足

2.3.4_2用信号量来实现进程互斥同步

P、V实现进程互斥

适用场景：多个进程不能同时访问临界资源。

分析并发进程，划定临界区。
设置互斥信号量 $mutex$，初值为 $1$。
临界区之前执行 $P(mutex)$（申请资源，加锁）。
临界区之后执行 $V(mutex)$（释放资源，解锁）。

semaphore mutex = 1;

P1(){
    ...
    P(mutex);
    // 临界区代码
    V(mutex);
    ...
}

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

要点
- $mutex$ 代表进入临界区的名额，初值$1$代表只有1个名额。
- $P(P、V)V$ 必须成对出现。缺$P$无法互斥；缺$V$资源永远不释放，进程永久阻塞。
- 不同临界资源，要用不同互斥信号量。

P、V实现进程同步

适用场景：保证两个操作一前一后有序执行。

口诀：前V后P

找出需要保证先后顺序的两处代码。
设置同步信号量 $S$，初值为 $0$。
在前操作代码之后执行 $V(S)$。
在后操作代码之前执行 $P(S)$。

semaphore S = 0;

P1(){
    代码1;
    代码2;
    V(S);   // 前操作完成，释放资源
    代码3;
}

P2(){
    P(S);   // 后操作开始前，申请资源
    代码4;
    代码5;
    代码6;
}

逻辑说明
- 信号量$S$代表“前操作完成”这个资源，初始没有，所以初值$0$。
- 若先执行$V(S)$：$S++$，$S=1$；后续$P(S)$，$S–$，$S=0$，$P2$直接继续执行。
- 若先执行$P(S)$：$S–$，$S=-1$，$P2$阻塞；等到$P1$执行$V(S)$，唤醒$P2$继续运行。
- 最终保证：代码4一定在代码2之后执行。

(P、V)实现进程前驱关系

本质：多级同步问题，每一组前驱关系都当作一对同步问题处理。

分析问题，画出前驱图，找出所有前驱依赖。
每一对前驱关系单独设置同步信号量，初值为$0$。
在“前操作”之后执行 $V$ 操作。
在“后操作”之前执行 $P$ 操作。

(P、V)对比总结

类型	信号量初值	使用规则
互斥	$1$	临界区前$P$，临界区后$V$
同步	$0$	前操作后$V$，后操作前$P$，口诀：前V后P
前驱关系	$0$	多组同步，每组单独一个同步信号量

屏幕截图 2026-09-28 220153

2.3.5同步互斥问题

2.3.6管程

为什么引入管程

解决信号量机制编程麻烦、易出错的问题。

管程定义与组成

管程是一种特殊的软件模块，由以下部分组成：

管程名字
局部于管程的共享数据结构说明
对该数据结构进行操作的一组过程（函数）
对局部于管程的共享数据设置初始值的语句

Tips：“过程”其实就是“函数”

基本特征

局部于管程的数据只能被局部于管程的过程所访问。
一个进程只有通过调用管程内的过程才能进入管程访问共享数据。
每次仅允许一个进程在管程内执行某个内部过程。
- 各外部进程/线程只能通过管程提供的特定“入口”才能访问共享数据。
- 各进程必须互斥访问管程的特性是由编译器实现的，程序员无需手动实现互斥。

补充

可在管程中设置条件变量及等待/唤醒操作以解决同步问题。
进程在条件变量等待时，会先释放管程的使用权，让出“入口”；可通过唤醒操作将等待在条件变量上的进程或线程唤醒。

拓展1：用管程解决生产者消费者问题

引入管程的目的：更方便地实现进程互斥和同步。

需要在管程中定义共享数据（如生产者消费者问题的缓冲区）。
需要在管程中定义用于访问这些共享数据的“入口”——其实就是一些函数（如生产者消费者问题中，可以定义一个函数用于将产品放入缓冲区，再定义一个函数用于从缓冲区取出产品）。
只有通过这些特定的“入口”才能访问共享数据。
管程中有很多“入口”，但是每次只能开放其中一个“入口”，并且只能让一个进程或线程进入。

例：生产者消费者问题中，各进程需要互斥地访问共享缓冲区。管程的这种特性即可保证一个时间段内最多只会有一个进程在访问缓冲区。注意：这种互斥特性是由编译器负责实现的，程序员不用关心。
可在管程中设置条件变量及等待/唤醒操作以解决同步问题。可以让一个进程或线程在条件变量上等待（此时，该进程应先释放管程的使用权，也就是让出“入口”）；可以通过唤醒操作将等待在条件变量上的进程或线程唤醒。

程序员可以用某种特殊的语法定义一个管程（比如: monitor ProducerConsumer ...... end monitor;），之后其他程序员就可以使用这个管程提供的特定“入口”很方便地实现进程同步/互斥。

屏幕截图 2026-10-03 210548

2.4死锁

2.4.1死锁的概念

什么是死锁

各进程互相等待对方手里的资源，导致各进程都阻塞，无法向前推进的现象。

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

共同点：都是进程无法顺利向前推进的现象（故意设计的死循环除外）

	区别
死锁	死锁：至少是$$2$$个进程一起死锁，死锁进程处于阻塞态
饥饿	饥饿：可以只有$$1$$个进程饥饿，饥饿进程可能阻塞也可能就绪
死循环	死循环：可能只有$$1$$个进程发生死循环，死循环的进程可上处理机

补充：死锁和饥饿是操作系统要解决的问题，死循环是应用程序员要解决的

饥饿：由于长期得不到想要的资源，某进程无法向前推进的现象。例：在短进程优先（SPF）算法中，若有源源不断的短进程到来，则长进程将一直得不到处理机，从而发生长进程“饥饿”。

死循环：某进程执行过程中一直跳不出某个循环的现象。有时是因为程序逻辑bug导致的，有时是程序员故意设计的。

死锁和饥饿是由于操作系统分配资源的策略不合理导致的；死循环是由代码逻辑错误导致的。死锁和饥饿是操作系统的问题，死循环是应用程序的问题。

死锁产生的必要条件

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

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

注意：发生死锁时一定有循环等待，但是发生循环等待时未必死锁（循环等待是死锁的必要不充分条件）。
如果同类资源数大于$$1$$，则即使有循环等待，也未必发生死锁。但如果系统中每类资源都只有$$1$$个，那循环等待就是死锁的充分必要条件了。

什么时候会发生死锁

对系统资源的竞争。各进程对不可剥夺的资源（如打印机）的竞争可能引起死锁，对可剥夺的资源（$$CPU$$）的竞争是不会引起死锁的。
进程推进顺序非法。请求和释放资源的顺序不当，也同样会导致死锁。例如，并发执行的进程$$P1$$、$$P2$$分别申请并占有了资源$$R1$$、$$R2$$，之后进程$$P1$$又紧接着申请资源$$R2$$，而进程$$P2$$又申请资源$$R1$$，两者会因为申请的资源被对方占有而阻塞，从而发生死锁。
信号量的使用不当也会造成死锁。如生产者-消费者问题中，如果实现互斥的$$P$$操作在实现同步的$$P$$操作之前，就有可能导致死锁。（可以把互斥信号量、同步信号量也看做是一种抽象的系统资源）

总之，对不可剥夺资源的不合理分配，可能导致死锁。

死锁的处理策略

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

屏幕截图 2026-10-03 211419

2.4.2预防死锁

核心思想：破坏死锁产生四个必要条件中的至少一个，从根源上杜绝死锁发生。

破坏互斥条件

方法：将临界资源改造为可共享使用的资源，典型例子：SPOOLing技术，把独占设备逻辑上改造为共享设备。
缺点：可行性不高，很多资源无法改造为共享资源；出于安全考虑，很多场景必须保留互斥访问。

破坏不剥夺条件

方案一：进程申请新资源得不到满足时，立即释放当前拥有的所有资源，后续需要时再重新申请。
方案二：进程所需资源被其他进程占用时，由操作系统协助强行剥夺资源，一般结合进程优先级。
缺点：
1. 实现复杂；
2. 剥夺资源可能造成进程已完成的工作失效；
3. 反复申请释放资源，增大系统开销；
4. 多次资源释放重申请，可能导致进程饥饿。

破坏请求和保持条件

方法：静态资源分配法，进程运行前一次性申请全部需要的资源，资源未全部满足则不启动进程；进程运行期间不再申请新资源。
缺点：资源利用率低；长期占用资源，可能造成进程饥饿。

破坏循环等待条件

方法：顺序资源分配法。给全部资源分配唯一编号，进程必须按编号从小到大的顺序申请资源；同类资源一次性申请完毕。
原理：进程只有持有小编号资源，才能申请更大编号资源；持有大编号资源的进程无法反向申请小编号资源，消除循环等待链。
缺点：
1. 新增设备不方便，可能需要重新分配全部资源编号；
2. 进程实际使用资源顺序和编号顺序不一致，造成资源浪费；
3. 用户编程时必须遵守资源申请次序，编程麻烦。

屏幕截图 2026-10-03 212400

2.4.3 避免死锁

银行家算法

银行家算法由荷兰学者 $Dijkstra$ 为银行系统设计，用于发放贷款，后引入操作系统，用于避免死锁。

核心思想：进程提出资源申请时，预先判断本次资源分配是否会让系统进入不安全状态；若会进入不安全状态，则暂时拒绝请求，让进程阻塞等待。

基本数据结构

设系统共有 $m$ 类资源，$n$ 个进程。

$Available$：长度为 $m$ 的一维数组，表示当前系统剩余可用资源数量。
$Max$：$n \times m$ 矩阵，记录每个进程对各类资源的最大需求。
$Allocation$：$n \times m$ 矩阵，记录已经分配给各进程的资源数量。
$Need$：$n \times m$ 矩阵，满足 $Need = Max - Allocation$，代表各进程还需要的资源数量。
$Request$：长度为 $m$ 的一维数组，表示某个进程本次申请的资源数量。

银行家算法执行步骤

检查本次申请资源是否超过该进程声明的最大需求：若 $Request[i] > Need[i]$，申请非法，直接拒绝。
检查系统当前可用资源能否满足本次请求：若 $Request[i] > Available[i]$，资源不足，进程阻塞等待。
试探分配，临时修改各数据结构：
$Available = Available - Request$
$Allocation[i] = Allocation[i] + Request$
$Need[i] = Need[i] - Request$
执行安全性算法，检验试探分配后的系统状态。
- 若安全：正式执行资源分配。
- 若不安全：回滚恢复所有数据结构，进程阻塞等待。

安全性算法（寻找安全序列）

查找当前可用资源能够满足其 $Need$ 的进程。
找到后将该进程加入安全序列；进程执行结束，回收它占有的全部资源，资源并入 $Available$。
循环重复上述查找。
若全部 $n$ 个进程都可以加入安全序列，说明系统处于安全状态；否则为不安全状态。

安全状态与不安全状态

安全序列：按该序列依次分配资源，所有进程都可以顺利执行完毕。一个系统可以存在多个安全序列。
分配资源后找不到任何安全序列，则系统进入不安全状态。
重要结论：
- 系统处于安全状态，一定不会发生死锁。
- 系统处于不安全状态，未必死锁，但发生死锁时系统一定处于不安全状态。

不安全状态只是存在死锁可能性，不是必然死锁；只要找到一条安全序列，系统就是安全的。

2.4.4死锁的检查与处理

一、死锁的检测

检测死锁需要满足两个前提：

使用对应数据结构存储资源请求、资源分配信息。
提供检测算法，判断系统是否进入死锁状态。

数据结构：资源分配图

包含两种结点：

进程结点 $P_i$
资源结点 $R_j$

包含两种有向边：

请求边：进程结点 $\rightarrow$ 资源结点，表示进程请求该资源
分配边：资源结点 $\rightarrow$ 进程结点，表示资源已经分配给该进程

死锁检测算法（资源分配图化简）

在资源分配图中，找到不阻塞且非孤立的进程 $P_i$。

不阻塞：进程申请资源数量 $\le$ 系统当前空闲资源数量，该进程可以运行完毕。
消除该进程所有请求边、分配边，使其变为孤立结点。进程运行结束后，释放它占有的全部资源。
进程释放的资源，可以唤醒其他阻塞进程，部分阻塞进程转变为不阻塞进程，循环执行化简操作。

若最终可以消除全部边：图是可完全简化的，系统无死锁。
若最终不能消除所有边：图不可完全简化，系统发生死锁。

死锁定理：若资源分配图是不可完全简化的，说明发生了死锁。
化简后，仍然连着边的进程，就是死锁进程。

补充：不是系统内全部进程都是死锁进程，只有化简后保留边的进程处于死锁。

二、死锁的解除

检测到死锁之后，需要采取措施解除死锁，共三种方法。

资源剥夺法
挂起部分死锁进程，抢占其占用资源，将资源分配给其余死锁进程。
需要防范被挂起进程长期得不到资源，产生饥饿问题。
撤销进程法（终止进程法）
强制撤销部分、甚至全部死锁进程，回收进程占用的资源。
优点：实现简单。
缺点：代价较大；部分进程已经长时间运行，终止后所有工作作废，需要重新执行。
进程回退法
将一个或多个死锁进程回退到能够避开死锁的状态。
要求系统记录进程历史运行信息，设置还原点。

选择被处理进程的判断依据

进程优先级
已经执行的时间长度
距离完成还需要的时间
进程已经占用的资源量
进程类型：交互式 / 批处理式

2.1 进程与线程

2.1.1 程序与进程

2.1.2 进程的组成

2.1.3 进程的特征

2.1.4 进程的状态与转换

进程的五种状态

三种基本状态

另外两种状态

进程状态之间的转换

2.1.5进程控制

原语的原子性

相关原语

1. 进程的创建

2. 进程的终止

3. 进程的阻塞和唤醒

进程的阻塞

进程的唤醒

4. 进程的切换

1.1.6_1 进程通信

共享存储

消息传递

直接通信方式

间接通信方式（信箱通信方式）

管道通信

2.1.6_2信号

信号的发送

信号的保存

信号的处理

处理时机

如何处理

信号与异常的配合机制

2.1.7_1 线程的概念与特点

引入线程带来的变化

资源分配、调度

并发性

系统开销

线程的属性

2.1.7_2线程的实现方式

用户级线程（$ULT$）

内核级线程（$KLT$，又称“内核支持的线程”）

多线程模型

多对一模型

一对一模型

多对多模型

2.1.7_3 线程的状态转化与组织控制

线程控制块 $TCB$

线程表

线程三状态转换

2.2CUP调度

2.2.1调度的概念、层次

三层调度

高级调度（作业调度）

中级调度（内存调度）

低级调度（进程调度 / 处理机调度）

七状态模型

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

进程调度（低级调度）

进程调度的时机

什么时候需要进程调度

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

进程切换与过程

狭义的“调度”和“切换”的区别

切换过程

进程调度方式

非剥夺调度方式（非抢占式）

剥夺调度方式（抢占式）

2.2.2_2调度器和闲逛进程

调度程序（$\text{(\text{scheduler})}$）

进程三态切换与调度触发

闲逛进程（$\text{(\text{idle})}$）

2.2.3调度指标

$CPU$ 利用率

系统吞吐量

周转时间

等待时间

响应时间

2.2.4_1调度算法（批处理）

先来先服务（$FCFS$, First Come First Serve）

短作业优先（$SJF$, Shortest Job First）

高响应比优先（$HRRN$, Highest Response Ratio Next）