【872专业课】操作系统第二章:进程与线程
一、章节主线
进程/线程是什么 ↓进程如何创建、切换、通信 ↓处理机如何调度 ↓并发进程如何同步、互斥 ↓资源竞争为什么会死锁,如何处理高频考查清单
- PCB 的作用、进程实体的组成、进程状态转换。
- 原语、进程控制、进程切换与上下文。
- 进程通信:共享存储、消息传递、管道;信号与信号量的区别。
- 用户级线程、内核级线程及多线程模型。
- 三层调度及调度时机;甘特图和调度指标计算。
- FCFS、SJF/SPF/SRTN、HRRN、RR、优先级、多级队列、多级反馈队列。
- 临界资源、临界区、互斥四原则;软件/硬件互斥方法。
- P/V 操作实现互斥、同步、前驱关系及经典问题。
- 死锁四个必要条件、银行家算法、安全性算法、死锁检测与解除。
二、进程的概念、组成与特征
2.1 程序、进程、进程实体
| 名称 | 含义 | 关键辨析 |
|---|---|---|
| 程序 | 静态的可执行文件或代码集合 | 存放在外存,不能直接反映运行时状态 |
| 进程 | 程序的一次执行过程 | 动态地产生、变化和消亡;同一程序多次运行可对应多个进程 |
| 进程实体/进程映像 | 某一时刻进程的静态组成 | 由 PCB、程序段、数据段组成 |
**严格定义:**进程是进程实体的运行过程,是系统进行资源分配和调度的一个独立单位。
2.2 进程实体的组成
- PCB(Process Control Block,进程控制块)
- 操作系统管理进程所需的全部信息。
- 常见信息:进程标识符 PID、用户标识符 UID、进程状态、处理机现场、调度信息、资源清单、记账信息等。
- **PCB 是进程存在的唯一标志。**创建进程时建立 PCB,终止进程时回收 PCB。
- 程序段:包含程序指令。
- 数据段:包含程序运行过程中产生的数据。
同一个程序的多个进程可以共享相同的程序段,但它们的 PCB 和数据段不同。
2.3 进程的五个特征
| 特征 | 含义 |
|---|---|
| 动态性 | 进程是程序的一次执行过程,动态地产生、变化和消亡;是最基本特征 |
| 并发性 | 内存中有多个进程实体,各进程可以并发执行 |
| 独立性 | 进程是能独立运行、独立获得资源、独立接受调度的基本单位 |
| 异步性 | 各并发进程以独立且不可预知的速度推进,导致执行结果可能具有不确定性 |
| 结构性 | 每个进程都配置一个 PCB;从结构上看,进程实体由程序段、数据段和 PCB 组成 |
**易错:**程序是静态的,进程是动态的;“进程实体”是静态的,而“进程”是动态的运行过程。
三、进程状态与组织
3.1 五状态模型
| 状态 | 含义 |
|---|---|
| 创建态 | 正在创建进程;操作系统分配资源、初始化 PCB |
| 就绪态 | 已具备运行条件,但暂时没有获得处理机 |
| 运行态 | 正在处理机上执行 |
| 阻塞态/等待态 | 正在等待某事件或资源,暂时不能继续执行;进程映像仍在内存 |
| 终止态 | 进程已结束,等待操作系统回收资源和 PCB;回收完成后进程消失 |
3.2 状态转换

创建态 --创建完成--> 就绪态 --被调度--> 运行态 ↑ ↓ 事件发生/资源得到 请求资源或等待事件 │ ↓ └----------- 阻塞态
运行态 --时间片到/被抢占/主动让出--> 就绪态运行态 --正常结束/异常结束/exit--> 终止态- 创建态 → 就绪态:创建工作完成,PCB 放入就绪队列。
- 就绪态 → 运行态:进程调度程序选中该进程并分配处理机。
- 运行态 → 就绪态:时间片耗尽、被更高优先级进程抢占、主动
yield等。 - 运行态 → 阻塞态:请求暂时不能得到的资源或等待某事件。
- 阻塞态 → 就绪态:等待的事件发生或资源可用;阻塞进程不能直接回到运行态,必须先进入就绪态。
- 运行态 → 终止态:正常完成、异常结束或被强制终止。
单处理机同一时刻最多一个进程处于运行态;多处理机可以有多个进程同时运行。
3.3 进程的组织
操作系统通常通过 PCB 组织进程:
- 链接方式:用指针把同一状态的 PCB 链接成队列,如运行队列、就绪队列、阻塞队列。
- 索引方式:建立就绪表、阻塞表等索引结构,表项指向相应 PCB。
- 阻塞队列可按阻塞原因进一步划分,如等待不同 I/O 设备或不同事件的队列。
3.4 挂起态与七状态模型
挂起表示进程映像被调到外存,暂时不参与处理机竞争;阻塞表示进程映像仍在内存中,只是等待事件。
- 就绪挂起:进程在外存等待,已经具备运行条件。
- 阻塞挂起:进程在外存等待,同时还没有满足某个事件条件。
- 中级调度负责在挂起队列与内存之间调入/调出进程。
四、进程控制与进程切换
4.1 原语
原语是完成某种进程控制功能的特殊程序段,执行必须具有原子性,即一气呵成、不可被中断。
- 原语通常由内核完成,用户程序不能直接执行特权指令。
- 可用“关中断指令 + 开中断指令”保证原子性:关中断后暂不检查外部中断,执行完原语再开中断。
- 关中断/开中断属于特权指令;若允许用户随意关中断,用户程序可能长期垄断 CPU,系统无法响应中断。
4.2 常见进程控制原语
| 原语 | 典型功能 | 关键动作 |
|---|---|---|
| 创建 | 建立新进程 | 初始化 PCB、分配资源、设置初始状态、插入就绪队列 |
| 终止 | 撤销进程 | 回收资源、撤销 PCB;可能由 exit、异常或系统强制终止触发 |
| 阻塞 | 运行进程主动等待事件/资源 | 修改状态为阻塞、保存必要现场、插入相应阻塞队列、让出处理机 |
| 唤醒 | 等待事件发生 | 修改状态为就绪、从阻塞队列移出、插入就绪队列;阻塞与唤醒必须成对 |
| 调度与切换 | 更换运行进程 | 保存原进程现场,恢复新进程现场,更新 PCB 和队列 |
阻塞与唤醒的对应关系:“因何事阻塞,就应由何事唤醒”。
任何进程控制原语通常都包含三类工作:
- 更新 PCB 信息,如状态、处理机现场。
- 将 PCB 插入或移出合适的队列。
- 分配或回收资源。
4.3 进程上下文与切换
CPU 中的寄存器保存着进程的运行现场,常见内容包括:
- PC(程序计数器):下一条指令地址。
- IR(指令寄存器):当前正在执行的指令。
- PSW(程序状态字):程序状态和控制信息。
- 通用寄存器及其他必要的处理机现场。
进程切换时:
- 将原运行进程的 PC、PSW、通用寄存器等保存到其 PCB。
- 更新原进程状态并放入对应队列。
- 取出新进程的现场,恢复到 CPU 寄存器。
- 更新新进程状态为运行态并开始执行。
进程调度与进程切换的区别:
- 狭义进程调度:从就绪队列中选出一个进程。
- 进程切换:一个进程让出处理机,另一个进程占用处理机。
- 广义进程调度:选择进程 + 进程切换。
进程切换有开销,过于频繁会使 CPU 大量时间用于保存、恢复现场,而不是执行有效程序。
五、进程通信(IPC)
进程是资源分配单位,各进程地址空间彼此独立。为了安全,一个进程不能直接访问另一个进程的地址空间,因此进程通信需要操作系统支持。
5.1 共享存储
操作系统在内存中划出共享区,并通过增加页表项或段表项,将同一片物理存储映射到多个进程的地址空间。
- 基于数据结构的共享:共享区格式由操作系统规定,限制多、速度较慢,属于低级通信。
- 基于存储区的共享:数据形式和存放位置由通信进程控制,速度快,属于高级通信。
- 共享区仍然需要同步和互斥,例如用信号量保护读写。
5.2 消息传递
以格式化消息为单位,通过操作系统提供的发送/接收原语通信。
- 直接通信:发送方直接指定接收方,如
send(Q, msg)、receive(P, &msg)。 - 间接通信/信箱通信:以信箱为中间实体,如
send(A, msg)、receive(A, &msg);多个进程可以向同一信箱发送或从同一信箱接收。
5.3 管道通信
管道是内存中的固定大小缓冲区,也可视为特殊的共享文件。
- 通常是半双工:同一时段只能单向传输;双向同时通信需要两个管道。
- 管道读写由操作系统保证互斥。
- 管道写满时,写进程阻塞,直到有数据被读走。
- 管道读空时,读进程阻塞,直到有数据被写入。
- 数据被读出后即消失;多个读进程同时读取可能造成数据分配问题,系统可规定一个读进程,或让多个读进程轮流读取。
- 管道未写满不代表不能读,只要管道中有数据就可以读;管道未读空也不代表不能写,只要仍有空闲空间就可以写。
5.4 信号:一种通信机制

信号用于通知进程某个特定事件已经发生,属于进程通信机制;不要与用于同步互斥的信号量混淆。
- 进程通过
kill(pid, sig)等方式发送信号。 - PCB 中可用
pending记录待处理信号,用blocked/signal mask 记录被阻塞或屏蔽的信号。 - 进程从内核态返回用户态时,通常检查是否有未被屏蔽的待处理信号。
- 处理方式:执行系统规定的默认处理程序,或执行进程自定义的处理程序。
- 信号处理程序结束后通常返回下一条指令继续执行;信号也可能使进程阻塞或终止。
- 同一类信号通常只用 1 bit 记录,重复到达可能被合并或丢弃;不同系统的信号类型和细节可能不同。
六、线程
6.1 引入线程的原因与基本概念
一个进程内部可能需要同时处理视频、文字聊天、文件传输等任务。若只有进程作为执行流单位,只能串行处理;引入线程后,一个进程内部的多个线程也可以并发。
- 线程是一个基本的 CPU 执行单元,也是程序执行流的最小单位。
- 线程是处理机分配的基本单位;进程主要作为除 CPU 外的系统资源分配单位。
- 同一进程的线程共享进程的地址空间、代码、数据、文件等资源,但各线程有自己的线程 ID、寄存器现场、栈和线程控制块 TCB。
- 线程也有就绪、运行、阻塞等基本状态。
- 同一进程内切换线程通常不需要切换地址空间,开销小;切换到其他进程会引起进程切换,开销较大。
6.2 用户级线程与内核级线程
| 对比项 | 用户级线程 ULT | 内核级线程 KLT |
|---|---|---|
| 管理者 | 应用程序和线程库 | 操作系统内核 |
| 内核是否看得见 | 看不见 | 看得见,并为其建立 TCB |
| 切换位置 | 用户态即可完成 | 需要内核参与,通常要进入核心态 |
| 阻塞影响 | 一个线程阻塞,整个进程可能阻塞 | 一个线程阻塞,其他线程可继续运行 |
| 多核并行 | 同一进程的多个 ULT 不能真正并行到多个核 | 多个 KLT 可在多核上并行 |
| 优点 | 管理和切换开销小、效率高 | 并发能力强,支持多核并行 |
| 缺点 | 阻塞影响整个进程,不能利用多核 | 内核管理开销大,切换成本高 |
6.3 多线程模型
| 模型 | 映射关系 | 特点 |
|---|---|---|
| 多对一 | 多个 ULT → 1 个 KLT | 切换快,但一个 ULT 阻塞会阻塞整个进程,不能多核并行 |
| 一对一 | 1 个 ULT → 1 个 KLT | 并发和多核能力强,但内核线程多、开销大 |
| 多对多 | n 个 ULT → m 个 KLT,n ≥ m | 兼顾并发能力和内核开销 |
**重点:**操作系统只看得见 KLT,因此只有 KLT 才是处理机分配单位。可把 ULT 理解为“代码逻辑的载体”,把 KLT 理解为“运行机会的载体”。
七、处理机调度的概念与层次
7.1 调度的基本概念
当任务很多而处理机、内存等资源有限时,操作系统需要决定处理顺序,这就是调度。
7.2 三层调度
| 层次 | 又称 | 主要工作 | 发生位置 | 频率 | 状态影响 |
|---|---|---|---|---|---|
| 高级调度 | 作业调度 | 从外存后备队列选择作业调入内存并建立进程 | 外存 → 内存 | 最低 | 无 → 创建态 → 就绪态 |
| 中级调度 | 内存调度 | 从挂起队列选择进程,将其数据调回内存 | 外存 → 内存 | 中等 | 挂起态 → 就绪态,或阻塞挂起 → 阻塞态 |
| 低级调度 | 进程/处理机调度 | 从就绪队列选择进程分配处理机 | 内存 → CPU | 最高,常为几十毫秒一次 | 就绪态 → 运行态 |
高级调度面向作业,通常一次调入、一次调出;中级调度面向进程,一个进程可能多次换入换出;低级调度发生最频繁,是操作系统中最基本的调度。
7.3 调度程序与闲逛进程
调度程序决定:
- 让谁运行:调度算法。
- 运行多长时间:时间片大小。
- 什么时候调度:调度触发事件。
没有其他就绪进程时,系统运行闲逛进程(idle):
- 优先级最低。
- 可以执行 0 地址指令,占用一个完整指令周期。
- 通常设计为低能耗,以便等待中断或新任务。
八、进程调度时机、方式与指标
8.1 需要调度的情况
当前进程主动放弃处理机:
- 正常结束或异常结束。
- 主动请求阻塞,如等待 I/O。
当前进程被动放弃处理机:
- 时间片用完。
- 有更紧急的任务到达,如高优先级进程进入就绪队列。
- I/O 中断唤醒了更合适的进程。
8.2 不宜进行调度与切换的情况
- 正在处理中断的过程。
- 进程正在操作系统内核程序临界区中。
- 正在执行原语等原子操作。
普通临界区不直接影响内核管理工作,因此一般可以发生调度;内核程序临界区通常访问就绪队列等关键内核数据结构,不能在未释放锁时切换。
8.3 调度方式
| 方式 | 含义 | 优点 | 缺点/适用 |
|---|---|---|---|
| 非剥夺/非抢占 | 只允许运行进程主动放弃 CPU | 实现简单、开销小 | 不能及时响应紧急任务,适合早期批处理系统 |
| 剥夺/抢占 | 更重要或更紧急的进程到达时,强行暂停当前进程 | 响应快,可实现时间片轮转,适合分时、实时系统 | 实现复杂,切换开销较大 |
8.4 调度算法评价指标
| 指标 | 公式/含义 | 趋势 |
|---|---|---|
| CPU 利用率 | CPU 忙碌时间 / 总时间 | 越大越好 |
| 系统吞吐量 | 单位时间内完成的作业数 | 越大越好 |
| 周转时间 | 完成时间 - 提交/到达时间 | 越小越好 |
| 平均周转时间 | 所有作业周转时间的平均值 | 越小越好 |
| 带权周转时间 | 周转时间 / 实际运行时间 | 必然 ≥ 1,越小越好 |
| 平均带权周转时间 | 所有带权周转时间的平均值 | 越小越好 |
| 等待时间 | 等待处理机的时间总和 | 越小越好 |
| 响应时间 | 从提交请求到首次得到响应的时间 | 越小越好 |
等待时间的口径:
- 对进程:只算建立后等待处理机的时间;等待 I/O 完成属于被服务过程,不算进程等待时间。
- 对作业:还要包括在外存后备队列中等待高级调度的时间。
- 纯 CPU 型进程可用:
等待时间 = 周转时间 - 运行时间。 - 有 I/O 的作业:
等待时间 = 周转时间 - CPU 服务时间 - I/O 服务时间。
8.5 调度计算通用步骤
- 写出每个进程的到达时间、运行时间、优先级等条件。
- 从时间轴起点开始,按算法规则选择当前可运行的进程。
- 只在算法规定的事件发生时重新调度:完成、阻塞、时间片到、新进程到达等。
- 画甘特图,记录每个进程的完成时间和首次开始时间。
- 计算:
周转时间 = 完成时间 - 到达时间等待时间 = 周转时间 - CPU 运行时间 - I/O 时间带权周转时间 = 周转时间 / CPU 运行时间响应时间 = 首次开始运行时间 - 到达时间
同一时刻既有新进程到达,又有当前进程时间片用完时,题目若无特殊说明,通常先把新到达进程放入就绪队列,再把时间片用完的进程放到队尾。
九、常见调度算法
9.1 算法总表
| 算法 | 核心规则 | 抢占性 | 主要优点 | 主要问题 | 饥饿 |
|---|---|---|---|---|---|
| FCFS | 按到达先后服务 | 非抢占 | 公平、简单 | 长作业拖累短作业,平均指标可能差 | 否 |
| SJF/SPF | 选择服务时间最短者 | 默认非抢占 | 平均等待/周转通常较小 | 长作业不利,需估计运行时间 | 是 |
| SRTN | 选择剩余运行时间最短者 | 抢占 | 平均等待/周转可更小 | 切换多,长作业可能饥饿 | 是 |
| HRRN | 选择响应比最高者 | 非抢占 | 综合等待时间和运行时间,较公平 | 每次调度要重新计算响应比 | 否 |
| RR | 每次运行一个时间片,未完成则排到队尾 | 抢占 | 公平、响应快、适合分时 | 时间片过小切换开销大,过大退化为 FCFS | 否 |
| 优先级 | 选择优先级最高者 | 可抢占或非抢占 | 能体现紧急程度,适合实时 | 低优先级可能长期等待 | 可能 |
| 多级队列 | 按进程类型固定分队列 | 取决于队列策略 | 不同类别可用不同算法 | 队列之间可能不公平 | 可能 |
| 多级反馈队列 | 进程可在队列间反馈降级 | 抢占 | 兼顾公平、响应、短作业和灵活性 | 规则复杂,低级队列可能饥饿 | 可能 |
9.2 先来先服务 FCFS
- 作业调度:按进入后备队列先后顺序。
- 进程调度:按进入就绪队列先后顺序。
- 非抢占式;当前进程完成或阻塞后才调度。
- 对长作业有利,对短作业不利,容易出现“排在长作业后面的短作业等待很久”的现象。
- 不会饥饿,因为先到者最终会得到服务。
9.3 短作业优先 SJF / 短进程优先 SPF
- 每次选择当前已到达且要求服务时间最短的作业/进程。
- 用于进程调度时严格称为 SPF。
- 默认是非抢占式;抢占式版本称为最短剩余时间优先 SRTN。
- 当所有进程同时到达或几乎同时可运行时,SJF 的平均等待时间、平均周转时间最小;在一般到达条件下,不能无条件地说 SJF 一定最小。
- 缺点:对长作业不公平,源源不断的短作业可能造成长作业饥饿;运行时间通常由用户提供,可能不准确。
9.4 最高响应比优先 HRRN
响应比:
响应比 = (等待时间 + 要求服务时间) / 要求服务时间 = 1 + 等待时间 / 要求服务时间- 每次调度时,在已到达进程中选择响应比最高者。
- 非抢占式,通常在当前进程主动放弃处理机时重新计算。
- 等待时间相同时,短作业响应比高,体现 SJF 的优点。
- 服务时间相同时,等待时间长者响应比高,体现 FCFS 的公平性。
- 长作业等待越久,响应比越高,因此一般不会饥饿。
9.5 时间片轮转 RR
- 只用于进程调度。
- 按就绪队列顺序轮流运行一个时间片;未完成的进程被抢占并放到队尾。
- 由时钟中断通知时间片到期,属于抢占式调度。
- 时间片太大:可能每个进程一次完成,退化为 FCFS,响应时间变大。
- 时间片太小:进程切换频繁,切换开销增加,有效执行比例下降。
- 常用于分时系统,公平、响应快,不会饥饿。
9.6 优先级调度
- 每个进程有优先级,调度时选择优先级最高者。
- 可用于作业和进程调度,可做成抢占式或非抢占式。
- 非抢占式:只在当前进程主动放弃处理机时调度。
- 抢占式:就绪队列改变时检查新进程是否能抢占当前进程。
- 静态优先级:创建时确定,之后不变;动态优先级:运行过程中按情况调整。
- 常见设置:系统进程高于用户进程,前台高于后台,I/O 繁忙型通常可优先于 CPU 繁忙型。
- 动态调整思路:等待时间长则提高优先级;占用 CPU 时间长则降低优先级;频繁 I/O 的进程可适当提高优先级。
- 若高优先级进程源源不断到达,低优先级进程可能饥饿。
9.7 多级队列调度
按进程类型建立多个固定就绪队列,进程创建后通常进入固定队列,队列内部可以使用不同算法:
- 系统进程队列:优先级调度。
- 交互式进程队列:RR。
- 批处理进程队列:FCFS。
队列之间可以采用:
- 固定优先级:高优先级队列为空时,低优先级队列才运行。
- 时间片划分:不同队列获得固定比例的处理机时间,如 50%、40%、10%。
9.8 多级反馈队列
核心规则:
- 建立多个就绪队列,优先级从高到低,时间片从小到大。
- 新进程先进入第 1 级队列,按 FCFS 排队。
- 若进程用完时间片仍未完成,则降到下一级队列队尾;已在最低级时重新放回最低级队尾。
- 只有第
k级及以上队列为空,才调度第k+1级队列。 - 低级队列运行时,若更高级队列有新进程到达,高级进程抢占处理机,原进程回到原队列队尾。
特点:
- 新进程响应快,体现 RR。
- 短进程可能在高级队列中较快完成,体现 SJF。
- 不要求用户准确提供运行时间。
- 对 CPU 密集型、I/O 密集型进程可以灵活调整偏好。
- 低级队列可能长期得不到服务,存在饥饿风险。
9.9 多处理机调度
相比单处理机,除了决定“让哪个进程运行”,还要决定“在哪个 CPU 上运行”。目标:
- 负载均衡:尽可能让各 CPU 忙碌程度相近。
- 处理机亲和性:尽量让进程继续在原 CPU 上运行,以利用缓存。
两种就绪队列方案:
| 方案 | 特点 |
|---|---|
| 公共就绪队列 | 所有 CPU 共享一个队列;天然负载均衡,但队列需加锁,进程可能频繁换 CPU,亲和性差 |
| 私有就绪队列 | 每个 CPU 一个队列;天然亲和性,但需要负载均衡 |
私有队列的负载均衡:
- Push 迁移:系统程序周期性检查,把忙 CPU 队列中的进程推到空闲 CPU。
- Pull 迁移:空闲 CPU 主动从忙 CPU 队列拉取进程。
亲和性还分为软亲和和硬亲和:软亲和由调度程序尽量保证,硬亲和由用户通过系统调用指定固定 CPU。
十、进程同步与互斥
10.1 同步
并发进程以各自独立、不可预知的速度推进,可能导致一个进程在另一个进程准备好之前就继续执行。同步就是通过协调,让并发进程按要求有序推进,体现的是直接制约关系。
10.2 互斥与临界资源
- 临界资源:一个时间段内只允许一个进程使用的资源,如打印机、摄像头、共享变量、共享缓冲区。
- 临界区:进程中访问临界资源的代码段。
- 进入区:检查能否进入并上锁。
- 退出区:解锁、释放临界资源。
- 剩余区:其他代码。
互斥是间接制约关系:一个进程访问临界资源时,其他进程必须等待其释放。
实现互斥的四个原则:
- 空闲让进:临界区空闲时,请求进程应立即进入。
- 忙则等待:已有进程进入临界区时,其他进程必须等待。
- 有限等待:请求访问的进程应在有限时间内进入,避免饥饿。
- 让权等待:不能进入临界区时应立即释放处理机,避免忙等待。
十一、进程互斥的实现方法
11.1 软件实现方法(两个进程)
| 方法 | 核心思想 | 主要问题 |
|---|---|---|
| 单标志法 | turn 表示轮到谁,访问后把机会交给另一个进程 | 必须轮流访问,违反空闲让进 |
| 双标志先检查 | 先检查对方意愿,再设置自己的 flag | 检查和上锁不是原子操作,可能同时进入,违反忙则等待 |
| 双标志后检查 | 先设置自己的 flag,再检查对方 | 双方都想进时都等待,违反空闲让进和有限等待,可能饥饿 |
| Peterson 算法 | flag 表示意愿,turn 表示谦让;双方竞争时让最后谦让者等待 | 满足互斥、空闲让进、有限等待,但仍忙等,违反让权等待 |
Peterson 算法的记忆:先表达意愿,再主动谦让,最后检查对方意愿和轮到谁。

11.2 硬件实现方法
中断屏蔽
进入临界区前关中断,离开临界区后开中断。关中断期间不能发生进程切换。
- 优点:简单、高效。
- 缺点:不适用于多处理机;只能用于内核进程,不适用于用户进程。
TestAndSet(TSL)
硬件保证“检查锁状态 + 上锁”不可被打断。若锁已被占用,进程循环执行 TSL,直到锁释放。
- 优点:实现简单,适用于多处理机。
- 缺点:忙等,不满足让权等待。
Swap / Exchange / XCHG
原子地交换局部变量与锁变量,逻辑效果与 TSL 类似。
- 优点:简单,适用于多处理机。
- 缺点:等待进程忙等,浪费 CPU。
11.3 互斥锁与自旋锁
需要连续循环检查、忙等的锁可称为自旋锁,如 TSL、Swap 等。
- 等待期间不切换上下文,若临界区很短,多处理机上代价可能较小。
- 单处理机上不适合忙等:等待者占着唯一 CPU,持锁者无法运行并解锁。
十二、信号量机制
12.1 基本概念
信号量是由操作系统提供的、只能通过原语访问的变量,常用于表示某类资源的数量或同步事件。
P(S)/wait(S):申请一个资源。V(S)/signal(S):释放一个资源。- P、V 操作必须是原子的,常简写为
P(S)、V(S)。 - 记录型信号量通常带有
value和等待队列L。
12.2 整型信号量与记录型信号量
**整型信号量:**P 操作检查并减 1,资源不足时忙等;简单但不满足让权等待。
**记录型信号量:**资源不足时执行 block,把进程放入等待队列;V 操作在有等待者时执行 wakeup。因此不会忙等,满足让权等待。
记录型信号量的典型逻辑:
P(S): S.value-- if S.value < 0: block(this process) insert this process into S.L
V(S): S.value++ if S.value <= 0: remove one process from S.L wakeup(that process)记忆:
S.value初值 = 资源总数。- P 一次 = 申请一个资源。
- V 一次 = 释放一个资源。
S.value < 0可表示等待该资源的进程数。
12.3 P/V 解题的统一方法
- 关系分析:列出进程,区分互斥关系、同步关系和资源数量。
- 整理顺序:把“前操作 → 后操作”写清楚,记忆为“前 V 后 P”。
- 设置信号量:互斥信号量通常初值为 1;同步信号量初值取决于事件/资源的初始数量。
- 检查死锁:在同一进程中,申请同步资源的 P 操作应先于申请互斥锁的 P 操作;V 操作不会阻塞,两个 V 的先后通常可交换。
十三、信号量解决互斥、同步和前驱关系
13.1 实现互斥
semaphore mutex = 1;
P(mutex);临界区;V(mutex);- 不同临界资源需要不同的互斥信号量。
- P、V 必须成对出现;缺少 P 无法保证互斥,缺少 V 会导致资源永不释放。
13.2 实现同步
若必须保证 操作 A 先于 操作 B:
semaphore S = 0;
进程 A: 操作 A; V(S);
进程 B: P(S); 操作 B;若 B 先执行到 P(S),因 S=0 被阻塞;A 完成后 V(S) 唤醒 B。因此口诀是:前 V,后 P;同步信号量初值通常为 0。
13.3 实现前驱关系
前驱图中的每一条有向边都是一个同步关系:
- 每条边设置一个初值为 0 的同步信号量。
- 前驱代码执行完后
V对应信号量。 - 后继代码执行前
P对应信号量。
前驱关系本质上是多组同步关系的组合。
十四、经典同步问题
14.1 生产者—消费者问题
缓冲区大小为 n,初始为空。
semaphore mutex = 1; // 缓冲区互斥semaphore empty = n; // 空闲缓冲区数量semaphore full = 0; // 产品数量
producer() { while (1) { 生产一个产品; P(empty); P(mutex); 放入缓冲区; V(mutex); V(full); }}
consumer() { while (1) { P(full); P(mutex); 从缓冲区取出产品; V(mutex); V(empty); 使用产品; }}三种信号量含义:
empty:生产者申请空位,消费者释放空位。full:消费者申请产品,生产者增加产品。mutex:保护缓冲区的临界访问。
顺序易错点:P(empty) 必须在 P(mutex) 前,P(full) 必须在 P(mutex) 前。若先锁住 mutex 再等待空位/产品,可能出现“持有互斥锁的一方阻塞,另一方无法进入缓冲区释放资源”的死锁。
14.2 多生产者—多消费者(盘子/水果问题)
爸爸只放苹果,妈妈只放橘子,女儿只取苹果,儿子只取橘子;盘子容量为 1 时可设置:
semaphore mutex = 1;semaphore apple = 0;semaphore orange = 0;semaphore plate = 1;
dad() { while (1) { 准备苹果; P(plate); P(mutex); 放入苹果; V(mutex); V(apple); }}
mom() { while (1) { 准备橘子; P(plate); P(mutex); 放入橘子; V(mutex); V(orange); }}
daughter() { while (1) { P(apple); P(mutex); 取出苹果; V(mutex); V(plate); 吃苹果; }}
son() { while (1) { P(orange); P(mutex); 取出橘子; V(mutex); V(plate); 吃橘子; }}分析时从“事件”而不是单个进程出发:
- 放入苹果 → 女儿取苹果。
- 放入橘子 → 儿子取橘子。
- 取走水果、盘子变空 → 父亲或母亲放水果。
盘子容量为 1 时,某些题目中仅靠 apple、orange、plate 三个同步信号量也可能保证互斥;但容量大于 1 时必须有专门的互斥信号量。考试中若无特殊限制,加入 mutex 最稳妥。
14.3 吸烟者问题
这是“可生产多种产品的单生产者—多消费者”问题。设:
semaphore offer1 = 0; // 组合一semaphore offer2 = 0; // 组合二semaphore offer3 = 0; // 组合三semaphore finish = 0; // 抽烟完成int i = 0;
provider() { while (1) { if (i == 0) { 放组合一; V(offer1); } else if (i == 1) { 放组合二; V(offer2); } else { 放组合三; V(offer3); } i = (i + 1) % 3; P(finish); }}
smoker1() { while (1) { P(offer1); 取组合一并吸烟; V(finish); } }smoker2() { while (1) { P(offer2); 取组合二并吸烟; V(finish); } }smoker3() { while (1) { P(offer3); 取组合三并吸烟; V(finish); } }核心是:供应者轮流产生三类事件;对应消费者在事件发生后被唤醒;消费者完成后 V(finish) 允许供应者继续。
14.4 读者—写者问题
要求:多个读者可并发读;写者与任何其他访问互斥;写者写入时不允许读者或其他写者访问。
读者优先方案:
semaphore rw = 1; // 文件读写锁semaphore mutex = 1; // 保护 countint count = 0; // 当前读者数
writer() { P(rw); 写文件; V(rw);}
reader() { P(mutex); if (count == 0) P(rw); // 第一个读者加锁 count++; V(mutex);
读文件;
P(mutex); count--; if (count == 0) V(rw); // 最后一个读者解锁 V(mutex);}- 第一个读者负责申请
rw,最后一个读者负责释放rw。 mutex保护count的检查和修改。- 读者之间不互斥,读者可并发读。
- 读者持续到达时,写者可能饥饿。
为避免写者饥饿,可增加 w:读者进入前先 P(w),完成进入后 V(w);写者先 P(w) 再 P(rw)。这样新来的读者不会无限越过等待中的写者,通常表现为相对公平的读写法。
14.5 哲学家进餐问题
5 个哲学家、5 根筷子,哲学家 i 左筷子为 chopstick[i],右筷子为 chopstick[(i+1)%5]。
朴素写法:先拿左筷子,再拿右筷子。若 5 人同时拿左筷子,就会循环等待右筷子,产生死锁。
常见避免死锁的方法:
- 最多允许 4 个哲学家同时尝试进餐。
- 奇数号先拿左后拿右,偶数号先拿右后拿左,破坏循环等待。
- 只有在互斥条件下执行“拿两根筷子”的过程:
semaphore chopstick[5] = {1, 1, 1, 1, 1};semaphore mutex = 1;
Pi() { while (1) { P(mutex); P(chopstick[i]); P(chopstick[(i + 1) % 5]); V(mutex); 吃饭; V(chopstick[i]); V(chopstick[(i + 1) % 5]); 思考; }}第三种方法的关键不是保证两根筷子在进入区开始时都空闲,而是保证所有“拿筷子”的动作互斥执行,避免多个进程同时各拿一根后循环等待。
14.6 管程
信号量灵活但容易写错 P/V 顺序。管程是更高级的同步机制,强调封装。
管程包含:
- 局部共享数据结构。
- 操作这些数据结构的一组过程/函数。
- 初始化语句。
- 管程名称。
基本特征:
- 管程内的数据只能由管程内的过程访问。
- 进程必须调用管程过程才能访问共享数据。
- 任意时刻只允许一个进程在管程内执行某个内部过程,互斥由编译器负责。
- 管程内可设置条件变量以及等待/唤醒操作解决同步;等待时进程应释放管程入口,唤醒后再竞争进入。
**对比:**信号量把互斥和同步控制交给程序员写 P/V;管程通过封装和编译器机制减少出错机会。
十五、死锁
15.1 死锁、饥饿、死循环
| 问题 | 含义 | 进程状态 |
|---|---|---|
| 死锁 | 多个进程互相等待对方占有的资源,全部阻塞,无法推进 | 至少两个进程,处于阻塞态 |
| 饥饿 | 某进程长期得不到所需资源或处理机 | 可能只有一个进程;可能阻塞,也可能就绪 |
| 死循环 | 程序逻辑陷入循环,无法按预期结束 | 进程可能仍在运行态 |
死锁和饥饿多是资源分配或调度策略问题;死循环通常是程序逻辑问题。
15.2 死锁的四个必要条件
死锁必须同时满足以下四个条件,破坏任意一个即可预防死锁:
- 互斥条件:资源一次只能被一个进程使用。
- 不剥夺条件:进程已获得的资源未使用完前,不能被其他进程强行夺走,只能主动释放。
- 请求和保持条件:进程已经保持至少一个资源,又请求新资源;新资源被占用时,进程阻塞但仍保持已有资源。
- 循环等待条件:存在进程—资源的循环等待链,每个进程等待下一个进程占有的资源。
注意:有死锁一定存在循环等待;有循环等待不一定有死锁。若每类资源只有一个实例,循环等待可作为死锁的充分必要条件;资源有多个实例时,单纯出现环不一定死锁。
15.3 死锁的常见原因
- 多个进程竞争不可剥夺资源。
- 进程申请和释放资源的顺序不当。
- 信号量使用不当,例如生产者消费者中先
P(mutex)再等待P(empty)/P(full)。 - CPU 等可剥夺资源的竞争一般不会造成死锁。
15.4 死锁处理策略
- 预防死锁:破坏四个必要条件中的一个或多个。
- 避免死锁:动态判断资源分配是否使系统进入不安全状态,典型是银行家算法。
- 检测和解除:允许死锁发生,检测后再恢复系统。
十六、预防死锁
16.1 破坏互斥条件
把独占资源改造成逻辑上的共享资源,例如用 SPOOLing 技术把打印机请求先写入磁盘缓冲区,再由专门输出进程统一打印。
- 优点:进程不必长期阻塞等待独占设备。
- 缺点:不是所有资源都能共享化;有些资源必须保持互斥以保证安全。
16.2 破坏不剥夺条件
- 方案一:进程申请新资源失败时,立即释放已有资源,之后再重新申请。
- 方案二:由操作系统剥夺其他进程已占有的资源。
缺点:实现复杂;释放资源可能使前期工作失效;反复申请释放增加开销;可能导致饥饿。通常更适合 CPU 等易保存和恢复状态的资源。
16.3 破坏请求和保持条件
采用静态分配:进程运行前一次性申请全部资源,资源未满足前不运行;运行后一直占有全部资源。
- 优点:实现简单,可破坏“保持已有资源并请求新资源”。
- 缺点:资源长期占用,利用率低;进程可能因无法一次获得全部资源而饥饿。
16.4 破坏循环等待条件
采用顺序资源分配法:给资源编号,进程必须按编号递增顺序申请,同类资源一次申请完。
- 已持有大编号资源的进程不能再反向申请小编号资源,因此不会形成循环等待。
- 缺点:新增设备时编号调整麻烦;实际使用顺序可能不同,造成浪费;程序员必须遵守规定顺序。
十七、避免死锁:安全性与银行家算法
17.1 安全状态与安全序列
- 安全序列:按该顺序分配资源时,每个进程都能获得其最大剩余需求并完成,完成后归还资源。
- 只要存在一个安全序列,系统就是安全状态。
- 安全序列可能有多个。
- 不安全状态不等于已经死锁,但发生死锁时系统一定处于不安全状态。
- 安全状态一定不会发生死锁。
17.2 银行家算法的数据结构
设有 n 个进程、m 类资源:
| 数据结构 | 含义 |
|---|---|
Max | 每个进程对各类资源的最大需求矩阵 |
Allocation | 当前已经分配给各进程的资源矩阵 |
Need | 还可能需要的资源矩阵,Need = Max - Allocation |
Available | 当前系统尚未分配的资源向量 |
Request_i | 进程 P_i 本次申请的资源向量 |
17.3 资源请求算法
进程 P_i 申请 Request_i:
- 若
Request_i ≤ Need_i,继续;否则说明超过了进程事先声明的最大需求,属于错误。 - 若
Request_i ≤ Available,继续;否则资源不足,P_i阻塞等待。 - 试探分配:
Available = Available - Request_iAllocation_i = Allocation_i + Request_iNeed_i = Need_i - Request_i
- 执行安全性算法:
- 若安全,正式分配。
- 若不安全,恢复原数据,不分配并让进程等待。
向量比较按每一类资源分别比较。
17.4 安全性算法
Work = AvailableFinish[i] = false(所有进程)
反复寻找某个 i: Finish[i] == false 且 Need[i] <= Work若找到: Work = Work + Allocation[i] Finish[i] = true 把 Pi 加入安全序列若所有 Finish[i] 都为 true:安全否则:不安全理解:若当前 Work 能满足某个进程的全部剩余需求,就假设该进程先完成,完成后归还它已经持有的 Allocation,于是可用资源增加,再继续寻找下一个进程。
**做题技巧:**每轮优先找 Need 不超过当前 Available/Work 的进程;找到一个就把它已分配的资源加回 Work。只要所有进程都能加入安全序列即可。

十八、死锁的检测与解除
18.1 死锁检测
系统不预防也不避免死锁时,需要:
- 用资源分配图或矩阵保存资源请求、分配信息。
- 用检测算法判断是否存在死锁。
资源分配图:
- 进程结点通常用圆表示。
- 资源结点用矩形表示,矩形中的小圆表示资源实例数。
- 资源 → 进程表示分配边。
- 进程 → 资源表示请求边。
18.2 资源分配图化简法
- 找一个当前不阻塞、且其请求可由现有空闲资源满足的进程。
- 假设该进程执行完,删除其请求边和分配边,并把它占有的资源归还。
- 重复上述过程。
- 若能消除所有边,说明没有死锁;若最终仍有边,剩余进程就是死锁进程。
**死锁定理:**如果某时刻资源分配图不可完全简化,则系统发生死锁。
18.3 死锁解除
- 资源剥夺法:挂起某些死锁进程,抢占其资源并分给其他进程;要防止被挂起进程长期饥饿。
- 撤销进程法:强制撤销部分或全部死锁进程,释放资源;实现简单,但可能丢失大量已完成工作。
- 进程回退法:让一个或多个进程回退到足以解除死锁的安全点,需要记录历史状态并设置还原点。
选择牺牲进程时可考虑:优先级、已运行时间、距离完成还剩多久、已占用资源数量、交互式还是批处理等。
十九、最后冲刺:高频易错点
- PCB 是进程存在的唯一标志,不是程序段,也不是数据段。
- 进程实体由 PCB + 程序段 + 数据段 构成;进程是进程实体的运行过程。
- 阻塞进程即使等待事件结束,也要先回到就绪态,不能直接运行。
- 挂起态与阻塞态不同:挂起在外存,阻塞通常仍在内存。
- 原语通过关中断/开中断保证原子性,属于内核特权机制。
- 进程切换必须保存/恢复上下文;上下文包括 PC、PSW、通用寄存器等。
- 线程是处理机分配单位,进程是资源分配单位;只有 KLT 对操作系统可见。
- FCFS、默认 SJF、HRRN 通常是非抢占;RR、SRTN 是抢占;优先级取决于题目说明。
- HRRN 公式是:
(等待时间 + 要求服务时间) / 要求服务时间。 - 带权周转时间不是“等待时间/运行时间”,而是“周转时间/运行时间”。
- 同步问题通常信号量初值为 0,口诀是“前 V 后 P”;互斥问题的 mutex 初值为 1。
- 生产者消费者中,先申请
empty/full,再申请mutex,否则可能死锁。 count的检查和修改要用互斥信号量保护;读者优先可能导致写者饥饿。- 哲学家问题的核心不是“有没有互斥”,而是“同时申请多个资源”导致循环等待。
- 死锁四条件必须同时满足;安全状态、可安全序列与死锁不是同义词。
- 银行家算法先检查
Request ≤ Need、再检查Request ≤ Available,最后做试探分配和安全性检查。
二十、建议背诵的最小框架
进程:动态执行过程;实体 = PCB + 程序段 + 数据段;PCB 是唯一标志状态:创建、就绪、运行、阻塞、终止;阻塞唤醒必须成对控制:原语保证原子性;进程切换保存/恢复上下文通信:共享存储、消息传递、管道、信号线程:CPU 分配单位;ULT/KLT;多对一、一对一、多对多调度:高级作业、中级内存、低级处理机指标:利用率、吞吐量、周转、带权周转、等待、响应算法:FCFS、SJF/SRTN、HRRN、RR、优先级、多级队列、反馈队列互斥:临界资源、临界区;空闲让进、忙则等待、有限等待、让权等待信号量:P 申请、V 释放;互斥初值 1,同步初值 0,前 V 后 P经典题:生产者消费者、读者写者、哲学家、吸烟者、前驱关系死锁:互斥、不可剥夺、请求保持、循环等待;预防、避免、检测解除如果这篇文章对你有帮助,欢迎分享给更多人!
部分信息可能已经过时