操作系统笔记

复习顺序

第一优先级是六类综合应用题：

1. 进程调度算法
2. 银行家算法
3. P、V操作
4. 分页和分段地址转换
5. FIFO、LRU、OPT页面置换
6. FCFS、SSTF、SCAN磁盘调度

第一章 操作系统概述

1. 操作系统的定义

操作系统是控制和管理计算机系统内各种硬件和软件资源、有效组织多道程序运行的系统软件，是用户与计算机之间的接口。

可以从三方面理解：

• 操作系统是什么：系统软件
• 操作系统管理什么：计算机中的软硬件资源
• 操作系统有什么作用：扩充硬件功能，方便用户使用

操作系统位于裸机之上，是计算机系统中的第一层软件。

2. 操作系统的五大功能

1. 进程和处理机管理
2. 存储管理
3. 文件管理
4. 设备管理
5. 用户接口管理

3. 操作系统的四大特征

并发性

两个或多个事件在同一时间段内发生。

单CPU中，多个进程在宏观上同时运行，在微观上交替占用CPU。

共享性

系统中的资源可以被多个并发进程共同使用。

共享分为：

• 互斥共享：同一时刻只能由一个进程使用
• 同时共享：多个进程可以在同一时间段内共同使用

虚拟性

通过某种技术，把一个物理实体变成若干个逻辑上的对应物。

异步性

多个进程按照各自独立、不可预知的速度向前推进，表现为走走停停。

其中，操作系统最基本的两个特征是：

并发性和共享性

4. 并发与并行

概念	含义
并发	多个事件在同一时间段内发生
并行	多个事件在同一时刻真正同时发生

单CPU可以实现并发，真正并行通常需要多核或多个处理器。

5. 多道程序设计

多道程序设计是把多个程序同时放入内存，使它们在一台处理机上并发运行。

当一个程序等待I/O时，CPU可以执行另一个程序。

作用：

• 提高CPU利用率
• 提高系统资源利用率
• 提高系统吞吐量

程序道数不是越多越好。进程过多会增加调度、切换和资源竞争的开销。

批注

类比算法的"时间换空间"——并发度（资源占用）↑，开销（时间成本）也 ↑，要在此消彼长中找平衡点。三类开销分别是：

• 调度开销：调度器本身消耗 CPU，进程越多决策越频繁
• 切换开销：保存/恢复上下文、TLB 与 Cache 失效
• 竞争开销：CPU、内存、I/O 争抢加剧，缺页/锁等待变多

6. 操作系统的主要类型

三者区分的主线——对响应时间的要求不同

• 响应时间：从提交请求到第一次收到回应的等待时间（聚焦"等多久才有反馈"）
• 周转时间：从提交作业到整个任务跑完的总时间（聚焦"全部完成要多久"）
• 批处理追求吞吐量大，响应时间/周转时间长无所谓（人不在现场等）；分时要把响应时间压到秒级（人在终端前）；实时必须严格保证截止时间（毫秒级，错过就出事）。

多道批处理系统

特点：

• 吞吐量较大
• 资源利用率较高
• 交互能力差
• 作业周转时间较长

分时系统

多个用户共享CPU时间，每个用户轮流获得时间片。

特点：

1. 多路性
2. 独立性
3. 及时性
4. 交互性

时间片一定时，用户数量越多，响应时间通常越长。

实时系统

系统必须在规定时间内对外部事件作出响应。

常用于工业控制、航空航天、医疗监控和武器控制。

其他类型还有网络操作系统、分布式操作系统、个人机操作系统和嵌入式操作系统。

第二章 进程与线程

1. 进程的定义

进程是程序在并发环境中的一次执行过程。

进程通常由以下三部分组成：

1. 程序段
2. 数据段
3. 进程控制块PCB

传统操作系统中，进程是系统进行资源分配和调度的独立单位。

2. 程序与进程的区别

项目	程序	进程
性质	静态	动态
含义	指令和代码的集合	程序的一次执行过程
生命周期	可以长期保存	有创建、运行和结束过程
状态	没有运行状态	有就绪、运行、阻塞等状态
资源	不直接分配运行资源	系统为其分配资源
组成	主要是程序代码	程序段、数据段和PCB

进程三部分对照

• 程序段：指令代码，只读可共享（多进程跑同一程序时共用一份）
• 数据段：运行时的数据（变量、栈、堆），每个进程独立一份
• PCB：进程的"身份证/档案"，含 PID、CPU 现场、调度/资源信息；PCB 是进程存在的唯一标志，销毁 PCB 即销毁进程

同一个程序多次运行，会形成多个不同的进程。

程序与进程不是一一对应的关系。

3. 进程的特性

1. 动态性
2. 并发性
3. 独立性
4. 异步性
5. 结构性

其中，动态性和并发性是进程最基本的属性。

4. PCB

PCB是进程控制块，是进程存在的唯一标志。

操作系统通过PCB感知、管理和控制进程。

PCB的主要内容：

1. 进程标识符
2. 处理机状态信息
3. 进程调度信息
4. 进程控制信息

处理机状态信息用于保存程序计数器、寄存器等运行现场。

进程调度信息包括进程状态、优先级等信息。

5. 进程的三种基本状态

就绪态

进程已经获得除CPU以外的所有必要资源，只等待获得CPU。

运行态

进程已经获得CPU，正在运行。

阻塞态

进程正在等待某个事件或资源，暂时不能继续运行。

6. 进程状态转换

就绪态 ──进程调度──→ 运行态

运行态 ──时间片用完或被抢占──→ 就绪态

运行态 ──等待事件或资源──→ 阻塞态

阻塞态 ──等待事件完成──→ 就绪态

阻塞态不能直接转为运行态，必须先进入就绪态。

进程的阻塞通常是进程自身的主动行为。

进程等待的事件完成后，由唤醒原语将其转为就绪态。

7. 单CPU中各状态的进程数量

系统中共有N个进程：

状态	最小值	最大值
运行态	0	1
阻塞态	0	N
就绪态	0	N-1

8. 为什么引入线程

进程的创建、撤销和切换开销较大。

我的理解

引入线程之前是一个进程就是一个任务，创建、撤销、切换只要次数上来累计开销都挺大。引入线程之后，能共享同一组资源的不同任务可以在一个进程下被 CPU 调度，比频繁以进程作为调度对象节省开销。

引入线程可以：

• 减少创建和切换开销
• 提高系统并发程度
• 方便同一进程中的任务共享资源

9. 线程的定义

线程是进程中的一个执行单元，是CPU调度和分派的基本单位。

三层关系

• 进程管资源（占内存、开文件、拥有独立地址空间）
• 线程用 CPU（被调度器分配时间片）
• 同进程内的线程共享资源、轮流上 CPU

引入线程后：

进程：资源分配的基本单位
线程：CPU调度和分派的基本单位

10. 进程与线程的区别

项目	进程	线程
基本作用	资源分配的基本单位	CPU调度的基本单位
地址空间	不同进程相互独立	同一进程中的线程共享
系统资源	拥有独立资源	共享所属进程的资源
创建和切换开销	较大	较小
通信	需要进程通信机制	同一进程内可直接共享数据
独立性	较强	较弱

每个线程拥有自己的程序计数器、寄存器、栈和运行状态。

11. 进程通信

进程间的三种高级通信方式：

1. 共享内存
2. 管道文件
3. 消息传递

第三章 进程同步、互斥与PV操作

1. 进程同步

进程同步是多个相互合作的进程之间存在执行顺序上的制约关系。

简单理解：

同步是协作，强调先后顺序

例如：

进程A产生数据
→ 进程B才能使用数据

2. 进程互斥

进程互斥是多个进程不能同时访问同一个临界资源。

简单理解：

互斥是竞争，同一时刻只能有一个进程使用资源

3. 临界资源与临界区

临界资源是一次只允许一个进程使用的资源。

例如：

• 打印机
• 共享变量
• 共享文件

临界区是进程中访问临界资源的程序段。

临界资源：被访问的资源
临界区：访问资源的程序代码

我的理解

临界 = 不能被不同进程在同一时刻共同使用（是其本身的属性，不是"当前正在被用"）。判断标准：改了会出错 + 多人想同时改 = 临界资源；只读资源、进程私有资源则不是。临界区就是访问临界资源的代码段。

4. 互斥访问的四个原则

空闲让进

临界区空闲时，应允许申请进入的进程进入。

忙则等待

临界区已有进程时，其他进程必须等待。

有限等待

进程申请进入临界区后，应在有限时间内获得进入机会。

让权等待

进程不能进入临界区时，应释放CPU，而不是一直占用CPU等待。

5. 原语

原语是操作系统中不可中断、不可分割执行的操作。

P、V操作属于原语。

6. 信号量

信号量用于实现进程同步和互斥，通常用S表示。

S >= 0：表示可用资源数量
S < 0：|S|表示等待该资源的进程数量

如果有m个进程竞争一个互斥资源，信号量初值为1，则取值范围为：

[-(m-1), 1]

7. P操作

P操作表示申请资源。

S = S - 1;

if (S < 0) {
    阻塞当前进程;
}

执行P操作后，如果S < 0，当前进程进入阻塞态。

一句话本质

每个 P 都是 --，每个 V 都是 ++，操作的对象是计数器。

8. V操作

V操作表示释放资源。

S = S + 1;

if (S <= 0) {
    唤醒一个等待进程;
}

被唤醒的进程从阻塞态转为就绪态。

9. 使用PV操作实现互斥

设互斥信号量：

semaphore mutex = 1;

进程结构：

P(mutex);

访问临界资源;

V(mutex);

P、V操作应分别放在临界区的入口和出口。

互斥一句话

mutex 是计数器（初值=1），P 拿资源、释放后 V 还资源。mutex=1 空闲，mutex=0 占用，负数表示有进程在等。

10. 使用PV操作实现同步

要求A执行完成后，B才能执行：

semaphore S = 0;

进程A：

执行A;
V(S);

进程B：

P(S);
执行B;

互斥 vs 同步的本质区别

• 初值不同：互斥 mutex = 1（一开始就有 1 把钥匙，谁都能拿）；同步 S = 0（一开始没通行证，必须等 A 的 V 才会有）
• 顺序不同：互斥谁都能直接 P；同步必须先有 V，才能 P——A 的 V 是给 B 的"开工许可"

一句话：互斥是"抢资源"，同步是"等开工"

11. 生产者—消费者模型

有n个缓冲区时：

semaphore empty = n;
semaphore full = 0;
semaphore mutex = 1;

生产者：

P(empty);
P(mutex);

放入数据;

V(mutex);
V(full);

消费者：

P(full);
P(mutex);

取出数据;

V(mutex);
V(empty);

含义：

• empty：空缓冲区数量
• full：已有数据的缓冲区数量
• mutex：保证对缓冲区的互斥访问

生产者-消费者模型的本质

• 目的：解决速度不匹配、实现解耦并发
• 缓冲区：内存里分成 n 个段，每段存 1 个数据
• 三变量：empty（空段数）、full（满段数）、mutex（使用权）
• 核心：生产者把"空"变"满"（empty--, full++），消费者反之；empty + full = n 恒成立

12. PV应用题分析步骤

1. 确定有几个进程或几类进程
2. 判断进程之间是同步还是互斥
3. 设置信号量并写明含义
4. 确定信号量初值
5. 将P、V放在正确位置
6. 检查不同执行顺序下能否满足题目要求

第四章 处理机调度

1. 作业调度与进程调度

核心理解

• 作业调度 = 把作业从外存调入内存、建立进程（管"进程从无到有"）
• 进程调度 = 从就绪队列选进程、分配 CPU（管"谁上 CPU"）
• 流程：作业（外存）→ 作业调度 → 进程（内存）→ 进程调度 → CPU

作业调度

从外存的后备作业队列中选择作业，将其调入内存并建立进程。

作业调度也称高级调度。

进程调度

从就绪队列中选择一个进程，将CPU分配给它。

进程调度也称低级调度。

后备作业
→ 作业调度
→ 调入内存并建立进程
→ 就绪队列
→ 进程调度
→ 获得CPU

作业被调入内存后，不代表立即获得CPU。

2. 调度评价指标

周转时间

周转时间 = 完成时间 - 到达时间

带权周转时间

带权周转时间 = 周转时间 ÷ 运行时间

平均周转时间

平均周转时间
= 所有进程周转时间之和 ÷ 进程数量

平均带权周转时间

平均带权周转时间
= 所有进程带权周转时间之和 ÷ 进程数量

只考虑CPU调度时：

等待时间 = 周转时间 - 运行时间

响应比

响应比
=（等待时间 + 运行时间）÷ 运行时间
= 1 + 等待时间 ÷ 运行时间

3. 先来先服务算法FCFS

按照进程到达的先后顺序调度。

特点：

• 非抢占式
• 算法简单、公平
• 对短进程不利
• 长进程可能使后面的短进程等待较长时间

4. 非抢占式短进程优先SJF

每次CPU空闲时，从已经到达的进程中选择运行时间最短的进程。

进程一旦开始运行，就一直运行到结束。

特点：

• 可以降低平均周转时间
• 长进程可能产生饥饿
• 只能从已经到达的进程中选择

5. 抢占式短进程优先SRTF

也称最短剩余时间优先。

系统选择剩余运行时间最短的进程。

如果新到达进程的运行时间小于当前进程的剩余时间，新进程会抢占CPU。

6. 优先级调度算法

优先级调度

优先级调度 = 优先级规则（看数值大还是小代表优先）+ 抢占/非抢占（高优先级新进程到时是否抢当前 CPU）。做题前先确认题目的优先级规则。

系统选择优先级最高的进程运行。

抢占式优先级调度中，如果新到达进程的优先级更高，会抢占当前进程。

计算前必须确认题目规定：

数值越大优先级越高
或
数值越小优先级越高

7. 高响应比优先算法HRRN

每次选择响应比最高的进程运行。

该算法同时考虑：

• 进程运行时间
• 进程等待时间

因此可以减少长进程长期等待的问题。

8. 时间片轮转算法RR

时间片本质

调度器给每个进程分配的固定时长 CPU 使用权；时间一到调度器强制剥夺（不是进程主动让出），切换给下一个进程。所以 RR 是抢占式调度。

系统为每个进程分配一个固定时间片。

时间片用完后，进程尚未结束：

运行态 → 就绪态

然后进入就绪队列末尾。

特点：

• 属于抢占式调度
• 适用于分时系统
• 时间片过大时接近FCFS
• 时间片过小时切换开销过大

6 个算法精简对比

算法	选择谁	抢占	一句话
FCFS	先到先跑	❌	排队
SJF	最短的	❌	谁短谁先
SRTF	剩余最短	✅	抢最短的
优先级	优先级最高	可选	看优先级 + 规则
HRRN	响应比最高	❌	算响应比
RR	时间片轮转	✅	轮流来

判断抢占：新进程到达时检查要不要换 → 抢占；当前跑完才选 → 非抢占 判断优先级：题目没说时默认"数值大 = 高"，但必看题目规定

9. 调度计算步骤

计算开始/完成时间的核心

开始时间 = max(到达时间, 上一进程完成时间) —— 只有两个条件都满足才能开始跑 完成时间 = 开始时间 + 运行时间

计算开始时间需要结合：

1. 调度原则（FCFS 按到达，SJF 按最短…）
2. 到达时间（还没到的进程不能选）
3. 前一个进程的完成时间（CPU 还在忙就不能开始）

1. 根据时间判断已经到达的进程
2. 根据调度算法选择进程
3. 画出执行时间线或甘特图
4. 计算开始时间和完成时间
5. 计算周转时间和带权周转时间
6. 计算平均值

第五章 死锁

1. 死锁的定义

死锁是多个进程因竞争资源而相互等待，导致这些进程都无法继续执行的状态。

2. 死锁产生的原因

1. 系统资源数量有限
2. 进程申请和释放资源的顺序不合理

3. 死锁的四个必要条件

互斥条件

资源同一时刻只能由一个进程使用。

占有且申请条件

进程已经占有部分资源，又申请新的资源，并且在等待时不释放已有资源。

也称请求和保持条件。

不可抢占条件

进程已经获得的资源，在使用完成前不能被其他进程强行夺走。

循环等待条件

多个进程之间形成首尾相连的循环等待关系。

四个条件必须同时成立，才可能产生死锁。

4. 处理死锁的四种方法

1. 预防死锁
2. 避免死锁
3. 检测死锁
4. 解除死锁

5. 死锁预防

死锁预防 = 破坏四个必要条件

• 破坏互斥 → 让资源可共享
• 破坏占有且申请 → 要么一次拿完，要么先放后拿
• 破坏不可抢占 → 申请不到就释放已有资源
• 破坏循环等待 → 资源编号，按序申请

只需记住破坏哪一个，具体实现不考。

破坏互斥条件

使资源可以共享。

缺点：打印机等资源本身无法同时共享。

破坏占有且申请条件

要求进程一次性申请全部资源，或者申请新资源前释放已有资源。

缺点：

• 资源利用率低
• 进程可能长期等待
• 可能产生饥饿

破坏不可抢占条件

进程申请新资源失败时，释放已经占有的资源。

缺点：

• 实现复杂
• 已完成的工作可能失效
• 并非所有资源都适合抢占

破坏循环等待条件

对资源统一编号，进程必须按照编号递增顺序申请资源。

缺点：

• 限制资源申请顺序
• 使用不灵活
• 可能降低资源利用率

6. 死锁避免与安全状态

死锁避免是在分配资源前进行判断，只允许系统进入安全状态。

银行家算法属于死锁避免算法。

安全状态：一定不会发生死锁
不安全状态：可能发生死锁，但不等于已经死锁

安全 vs 不安全

• 安全：存在一个安全序列，按这个顺序跑完所有进程都不会卡住
• 不安全：找不到这样的序列——但不等于已死锁，只是"有死锁风险"

银行家算法的核心就是：只在安全时才分配资源。

7. 银行家算法的数据

银行家算法总览

银行家算法 = 数据准备（第 7 节）+ 安全性检查（第 8 节）+ 资源请求判断（第 9 节）

题型 1：判断系统是否安全（直接跑安全性检查）
题型 2：判断能否批准资源请求（5 步流程：检查条件 → 试分配 → 安全性检查 → 决定）

核心思想：分配前先推演——按某种顺序能不能让所有进程跑完？能 → 安全，分配；不能 → 不安全，拒绝

Max：进程的最大资源需求量

Allocation：已经分配给进程的资源量

Need：进程还需要的资源量

Available：系统当前可用资源量

Need = Max - Allocation

8. 安全性检查

安全性检查 = 反复找一个能跑完的进程

1. 初始：Work = Available
2. 找：谁 Need ≤ Work？（能跑完的）
3. 假设它跑完：Work += Allocation（资源还回来）
4. 重复：直到所有人都跑完 → 安全（记下安全序列）；卡住找不到 → 不安全

判不安全的深入理解：有多个选择时（分叉），如果每一条分支都跑不通（所有路径都卡住）→ 才算真正不安全 考试技巧：随便挑一个分支往下做；草稿要干净，标清每一步的 Work 值，方便回溯换分支

设置：

Work = Available

寻找满足以下条件的进程：

Need[i] <= Work

假设该进程能够完成并释放资源：

Work = Work + Allocation[i]

继续寻找下一个进程。

如果所有进程最终都能完成，则系统处于安全状态，完成顺序就是安全序列。

银行家算法做题模板（4 步法）

Step 1 算 Need：Need = Max - Allocation（每行单独算） Step 2 算 Available：Available = 总资源 - 所有 Allocation 加起来Step 3 设 Work：Work = Available，写在草稿最上面 Step 4 反复找：Need ≤ Work 的进程 → 让它跑完 → Work += Allocation（注意：加的是 Allocation，不是 Need）

关键：模拟"进程跑完还资源"时，系统增加的是这个进程原本已经占有的（Allocation），不是它还需要多少（Need）

判安全：所有进程都跑完 → 安全（写下安全序列） 判不安全：卡住 / 第一步就找不到能跑的 → 不安全 分支回溯：多个选择时随便挑一个，卡了就换下一个；所有分支都卡 → 真正不安全

草稿要点：

• 每步标清 Work 的值
• 用箭头画清资源流转
• 选完的进程打勾，避免重复选

9. 处理进程资源请求

请求 = 加到 Pi 的 Allocation 上

试分配就是 Request 加到 Pi 原本的 Allocation 上，Pi 的 Need 减少，系统 Available 减少。

进程Pi提出请求Request[i]。

先检查：

Request[i] <= Need[i]

Request[i] <= Available

满足后进行试分配：

Available = Available - Request[i]

Allocation[i] = Allocation[i] + Request[i]

Need[i] = Need[i] - Request[i]

再进行安全性检查。

• 系统安全：正式分配
• 系统不安全：撤销试分配，让进程等待

10. 保证不死锁的资源数量

有n个进程，每个进程最多需要k个同类资源。

保证系统不会因为该类资源发生死锁，需要：

资源总数R >= n × (k - 1) + 1

11. 解除死锁的方法

死锁已经发生，只能"收拾残局"

1. 杀进程（撤销死锁进程）
2. 抢资源（剥夺资源给别的进程）
3. 回退（让进程回到之前的安全状态）

口诀：杀、抢、退——理解就好，不深究。

第六章 存储管理

1. 逻辑地址与物理地址

逻辑地址是程序中使用的地址，也称相对地址。

物理地址是内存中存储单元的实际地址，也称绝对地址。

2. 重定位

把逻辑地址转换为物理地址的过程称为重定位或地址转换。

静态重定位

程序装入内存时，一次性完成全部地址转换。

特点：

• 实现简单
• 程序运行过程中不能随意移动

动态重定位

程序运行过程中，每次访问指令或数据时进行地址转换。

特点：

• 需要硬件支持
• 程序运行过程中可以移动
• 更适合现代存储管理

3. 固定分区与可变分区

固定分区

系统预先把内存划分为若干固定分区。

特点：

• 分区大小预先确定
• 可以支持多道程序
• 容易产生内部碎片

可变分区

系统根据作业大小动态划分连续内存空间。

特点：

• 分区大小适合作业需要
• 容易产生外部碎片

4. 内部碎片与外部碎片

类型	含义	常见方式
内部碎片	已分配区域内部没有使用的空间	固定分区、分页
外部碎片	已分配区域之间分散的小空闲区	可变分区、分段

5. 可变分区分配算法

首次适应算法FF

从空闲分区表开头开始，选择第一个满足要求的分区。

空闲分区一般按地址递增排列。

循环首次适应算法NF

从上一次查找结束的位置继续向后寻找。

查找到末尾后，再从表头继续查找。

最佳适应算法BF

选择能够满足要求的最小空闲分区。

空闲分区一般按容量递增排列。

容易产生大量很小的外部碎片。

最差适应算法WF

选择当前最大的空闲分区。

空闲分区一般按容量递减排列。

会不断消耗系统中的大空闲分区。

6. 可变分区回收

回收一个分区时：

上下都不是空闲区
→ 新增一个空闲分区

只有上方是空闲区
→ 与上方空闲区合并

只有下方是空闲区
→ 与下方空闲区合并

上下都是空闲区
→ 三个区域合并
→ 空闲分区数量减少1

7. 紧凑技术

紧凑技术通过移动已分配区域，把分散的外部碎片集中成一个较大的连续空闲区。

紧凑不会增加内存容量，通常需要动态重定位支持。

可变分区 · 三件套

• 分配 = 4 个算法（FF/NF/BF/WF）选策略
• 回收 = 看上下是否空闲，决定合并/新增
• 紧凑 = 物理移动已分配区域，需要动态重定位支持

共同目的：减少/消除外部碎片

8. 分页存储管理

分页把逻辑地址空间划分为大小相同的页面，把内存划分为同样大小的物理块。

页表保存：

页号 → 物理块号

每个进程通常有自己的页表。

逻辑地址由两部分组成：

逻辑地址 = 页号 + 页内偏移量

9. 分页地址转换

分页单位换算（必背）

换算规则：1KB = 1024 = 2¹⁰，每升一级 × 2¹⁰

单位	字节数	2 的幂
1B	1	2⁰
1KB	1024	2¹⁰
1MB	1024×1024	2²⁰
1GB	1024³	2³⁰

页面大小计算规则：nKB = 1024 × n = 2⁽¹⁰⁺ᵏ⁾（k = log₂n）

页面大小	字节数	2 的幂	n（位数）
1KB	1024	2¹⁰	10
2KB	2048	2¹¹	11
4KB	4096	2¹²	12（最常考）
8KB	8192	2¹³	13
16KB	16384	2¹⁴	14
32KB	32768	2¹⁵	15

计算技巧：页面大小 = 2ⁿ → n 就是页内偏移的位数（后面地址位数题要用）

已知逻辑地址A和页面大小L：

页号 = A ÷ L的整数部分

页内偏移量 = A mod L

查页表获得物理块号后：

物理地址
= 物理块号 × 页面大小 + 页内偏移量

如果题目给出用户区起始地址：

物理地址
= 用户区起始地址
+ 物理块号 × 页面大小
+ 页内偏移量

10. 分页地址位数

如果页面大小为：

2^n字节

则页内偏移量占n位。

如果逻辑空间有：

2^m页

则页号占m位。

逻辑地址位数 = 页号位数 + 页内偏移位数

算对的自检

页内偏移（余数）必然 < 页大小（除数）——算完用它验证一下，不等就算错了

11. 分段存储管理

分段按照程序的逻辑结构划分程序。

逻辑地址表示为：

(段号，段内偏移量)

段表项通常包括：

• 段始址
• 段长
• 状态信息

地址转换时先判断：

段内偏移量 < 段长

分段越界判断

判断依据：段内偏移量 < 段长（偏移必须小于段大小，否则越界报错） 物理地址公式：段始址 + 段内偏移量（仅一个加法）

合法时：

物理地址 = 段始址 + 段内偏移量

12. 地址越界、缺页和缺段

地址越界

页号或段号超过程序合法范围，或者段内偏移量超过段长。

缺页

页号合法，但页面当前不在内存中，产生缺页中断。

缺段

段号合法，但该段当前没有装入内存，产生缺段中断。

地址越界：访问的地址本身不合法 缺页或缺段：地址合法，只是内容当前不在内存

三种异常的本质区别

• 地址越界：地址本身不合法（程序员 bug，超出了段长/页号范围）
• 缺页/缺段：地址合法，但内容当前不在内存（需要从磁盘调入）

第七章 虚拟存储器与页面置换

1. 虚拟存储器的定义

虚拟存储器是操作系统为用户提供的、比实际物理内存更大的逻辑地址空间。

虚拟存储器的容量不是无限的，主要受到以下因素限制：

• 地址字长
• 外存容量

内存 vs 外存

• 内外不是按物理位置分的——是按 CPU 能不能直接访问分的
• 内存（RAM）：CPU 能直接访问，快但小
• 外存（硬盘/SSD/U盘）：CPU 不能直接访问，要先搬到内存；慢但大
• 硬盘虽然在电脑里，但因为 CPU 不能直接读，也叫"外存"

2. 虚拟存储器的三个特征

虚拟存储器的本质

• 虚拟存储器 = 内存（真）+ 外存（假装）——OS 让程序以为内存很大
• 把外存幻觉成内存，要用时搬上来
• 容量上限受两个限制：
  • 外存容量（仓库要够大）
  • 地址字长（CPU 编址能力，位数越多能指向越大内存）
  • 取两者中较小的那个

地址字长举例：

• 32 位地址 → 最多 2³² = 4GB
• 64 位地址 → 最多 2⁶⁴ ≈ 1.8 × 10¹⁹ 字节
• 即使有 1TB 硬盘，32 位 CPU 也只能"指向" 4GB 范围

多次性

程序不需要一次全部装入内存，可以分多次调入。

对换性

程序运行过程中，页面可以在内存和外存之间换入、换出。

虚拟性

用户看到的逻辑存储空间大于实际物理内存。

3. 请求分页

---

普通分页 vs 请求分页

• 普通分页：一次性把所有页面都装入内存，程序才能跑
• 请求分页：用到才装——用到哪页才从外存调入哪页，没用到就放外存
• 请求分页会产生缺页中断（访问不在内存的页时）
• ⭐️请求分页是虚拟存储器的实现方式

"装入"的对象：程序的页面（4KB 一小块）—— 里面装的是代码段 / 数据段 / 栈 / 堆等程序内容

请求分页的本质：当前要用的代码和数据放进内存，其他暂时放在外存（用到时再调）

请求分页是在普通分页基础上增加虚拟存储功能。****

程序开始运行时，只装入当前需要的页面。

访问未装入内存的页面时：

产生缺页中断
→ 从外存调入页面
→ 更新页表
→ 重新执行被中断的指令

请求分页需要：

1. 页表机制
2. 缺页中断机构
3. 地址转换机构
4. 一定容量的内存和外存

请求分页的 4 个需求

• 页表机制：记录每个页面在不在内存（状态位）
• 缺页中断机构：发现页面不在内存时自动处理（暂停 + 调入 + 继续）
• 地址转换机构：把逻辑地址变成物理地址
• 内存 + 外存：硬件基础（内存放当前在用的，外存放暂时不用的）

4. 页表项

请求分页中的页表项通常包括：

1. 物理块号
2. 存在位或状态位
3. 访问字段
4. 修改位
5. 外存地址

页表项 5 字段

• 物理块号：页面在内存的块号
• 存在位：页面是否在内存（1 在，0 不在）
• 访问字段：记录访问情况，供置换算法用
• 修改位：页面是否被修改过（淘汰时决定是否写回硬盘）
• 外存地址：页面在硬盘的位置，缺页时调入用

存在位：

存在位为1：页面在内存中
存在位为0：页面不在内存中

5. 缺页次数与置换次数

缺页 vs 页面置换

• 缺页：要用的页面不在内存（必发生）
• 页面置换：内存满 + 缺页 → 淘汰一个旧页面，腾出位置
• 关系：内存有空块 → 只缺页不置换；内存无空块 → 缺页 + 置换
• 因此缺页次数 ≥ 置换次数

页面不在内存时，发生缺页。

如果内存还有空闲物理块：

发生缺页
但不发生页面置换

如果内存已经没有空闲物理块：

发生缺页
同时需要淘汰一个页面

因此：

缺页次数通常大于或等于置换次数

6. FIFO页面置换算法

淘汰最早进入内存的页面。

特点：

• 实现简单
• 不考虑页面实际使用情况
• 可能出现Belady异常

Belady异常是：

分配的物理块数量增加
缺页次数反而增加

7. OPT页面置换算法

淘汰未来最长时间不会被访问，或者以后不再访问的页面。

特点：

• 理论上缺页次数最少
• 实际系统无法预知未来
• 常用于评价其他置换算法

8. LRU页面置换算法

淘汰过去最长时间没有被访问的页面。

判断时，从当前位置向前看，哪个页面最久没有使用，就淘汰哪个页面。

特点：

• 符合程序局部性
• 性能较好
• 实现开销较大

三个置换算法对比

算法	淘汰谁	一句话
FIFO	最早进入内存的页面	谁先来谁先走
OPT	未来最久不被访问的页面	谁将来最没用
LRU	过去最久没被访问的页面	谁过去最没用

FIFO = 看"最早"；OPT = 看"未来"；LRU = 看"过去最久没用"

关键：FIFO 按"第一次进来"的时间算（用了多少次都不更新），这就是 Belady 异常的根源

LRU 本质：找"最近一次使用位置最远的"淘汰——即"过去最久没用"的。两个候选使用次数相同时，也是用这个规则判断谁离当前更远

多候选时的处理：FIFO / OPT / LRU 都有可能出现多个"符合规则"的候选——任选一个即可，都给分

9. 页面置换题步骤

1. 写出页面访问序列
2. 画出物理块
3. 从左到右逐个访问页面
4. 页面已在内存中，不缺页
5. 页面不在内存中，发生缺页
6. 没有空闲块时，按照算法淘汰页面
7. 记录缺页次数和淘汰序列

缺页率
= 缺页次数 ÷ 页面访问总次数 × 100%

10. 抖动

抖动是进程频繁发生缺页，大部分时间用于页面换入、换出，CPU利用率很低的现象。

常见原因：

• 分配给进程的物理块太少
• 同时运行的进程过多
• 页面置换策略不合理

抖动 - 考试导向

• 这是什么：频繁换页导致 CPU 利用率低的现象
• 怎么考：⭐ 选择/填空（解释什么是抖动 + 原因）
• 不考：大题
• 学到什么程度：理解现象 + 记住 3 个原因就够了

第八章 设备管理

1. 设备管理的主要功能

1. 监视设备状态
2. 分配和回收设备
3. 控制和完成I/O操作
4. 管理缓冲区
5. 实现设备独立性
6. 提高设备利用率

2. 按资源分配方式分类

独占设备

一段时间内只能由一个进程使用。

例如打印机。

共享设备

可以被多个进程交替使用。

例如磁盘。

虚拟设备

通过技术把独占设备改造成逻辑上可以共享的设备。

3. 按信息交换单位分类

块设备

以数据块为单位传送数据。

例如磁盘。

字符设备

以字符为单位传送数据。

例如键盘、打印机和终端。

4. 设备独立性

设备独立性是用户程序与实际使用的物理设备无关。

用户程序使用逻辑设备名，操作系统负责将其映射到具体的物理设备。

5. 设备驱动程序

设备驱动程序是直接控制设备打开、关闭、读、写和数据传输的核心模块。

它位于操作系统和设备控制器之间。

6. I/O控制方式

程序查询方式

CPU不断查询设备状态，CPU利用率较低。

中断方式

CPU启动设备后执行其他程序，设备完成后通过中断通知CPU。

DMA方式

DMA控制器负责设备和内存之间的成批数据传送，不需要CPU逐个传送数据。

通道方式

通道是I/O专用处理器，可以执行通道程序并控制多个设备。

需要CPU干预最少的是通道方式。

I/O 控制方式 · 三个核心解惑点

• 核心问题：让 CPU 少等设备，演进：查询 → 中断 → DMA → 通道
• OS vs 计组：OS 看效率和利用，计组看硬件实现
• DMA vs 通道：通道 = DMA 超集。区别就一条——通道有指令集能跑程序、可独立决策、能管多设备；DMA 只能听 CPU 指挥搬数据

7. 通道瓶颈

多个设备共用数量有限的通道时，通道可能限制I/O系统的并行能力。

改善方法：

• 增加通道数量
• 增加设备与通道之间的连接路径

8. 引入缓冲区的原因

1. 缓解CPU与I/O设备之间速度不匹配
2. 减少CPU中断次数
3. 放宽CPU对中断响应时间的要求
4. 解决数据传送单位大小不一致
5. 提高CPU与设备并行工作的程度

缓冲区位于主存中。

缓冲区是什么

缓冲区 = 内存里的小池子，连接设备和磁盘/打印机，做中转和速度匹配。

9. 单缓冲、双缓冲和环形缓冲

单缓冲

只设置一个缓冲区。

实现简单，但设备和进程仍可能相互等待。

双缓冲

设置两个缓冲区交替使用。

设备向一个缓冲区输入数据
同时进程处理另一个缓冲区中的数据

双缓冲的并行程度高于单缓冲。

双缓冲精髓：轮换

A 装 + B 用 → 切到 B 装 + A 用 → CPU 和设备同时干活、各不耽误。

环形缓冲

多个缓冲区首尾相接组成环形。

适合连续、高速的数据传送，需要管理空缓冲区、满缓冲区以及读写位置。

环形缓冲精髓

池子数固定 + 循环复用（不释放）→ 减少"申请/释放"开销 → 提高效率。适合数据流特别大且连续的场景。

缓冲区 · 核心要点

• 本质：内存里开一块中转站
• 核心问题：CPU 不等 I/O 设备（不是设备等 CPU）—— CPU 启动 I/O 后干别的，I/O 慢慢塞缓冲区
• 5 个原因都围绕"速度差"：解决 CPU 与 I/O 速度不匹配、提高并行
• 三种缓冲演进：单（1 个，相互等）→ 双（2 个，并行）→ 环形（多个连续流）

10. SPOOLing技术

SPOOLing也称假脱机技术。

它利用磁盘空间和常驻内存进程，把独占设备改造成逻辑上的共享设备。

11. SPOOLing系统的组成

1. 输入井
2. 输出井
3. 输入缓冲区
4. 输出缓冲区
5. 输入进程
6. 输出进程

输入井和输出井位于磁盘中。

输入缓冲区和输出缓冲区位于主存中。

6 组件对应到打印流程（打印只用"输出"那 3 个）

• ① 用户提交 → 数据在用户内存
• ② 搬中转 → 输出缓冲区（内存）搬数据
• ③ 写仓库 → 输出井（磁盘）长期存 + 排队
• ④ 取任务 → 输出进程按队列取出
• ⑤ 再中转 → 输出缓冲区（内存）喂打印机
• ⑥ 打印 → 打印机

3 输入 + 3 输出 = 对称结构；考试重点是输出（打印），输入理解"对称"即可。

12. SPOOLing打印过程

用户提交打印数据 → 系统在输出井中申请磁盘空间 → 将打印数据写入输出井 → 填写打印请求表 → 将请求挂入打印请求队列 → 打印机空闲时，输出进程取出请求 → 将数据送入内存输出缓冲区 → 控制打印机打印

13. SPOOLing的优点

• 将独占设备改造成虚拟共享设备
• 提高设备利用率
• 提高CPU与设备并行工作的程度
• 减少进程等待低速设备的时间
• 属于以空间换时间的技术

SPOOLing · 核心要点

• 本质：用磁盘当中转站，把独占设备"假共享"
• 核心机制：进门（写磁盘，快）+ 出门（按队列打印，慢）= 解耦
• 6 组成：输入/输出井（磁盘）+ 输入/输出缓冲区（内存）+ 输入/输出进程
• 打印流程：提交 → 入输出井 → 排队 → 输出进程取出 → 送输出缓冲区 → 打印机
• 特点：以空间换时间——磁盘换 CPU 和设备的等待时间

SPOOLing 简答模板（2 道最常考）

模板 1：简述 SPOOLing 工作过程

1. 用户提交数据，系统在输出井（磁盘）申请空间
2. 数据写入输出井，形成打印请求队列
3. 打印机空闲时，输出进程按队列取出
4. 数据送入内存的输出缓冲区
5. 控制打印机打印

模板 2：如何把独占设备改造成共享

• 核心思路：磁盘当中转
• 进程不直接用打印机，数据先写入磁盘的输出井排队
• 输出进程按队列取出，送给打印机
• 实质是以磁盘空间换时间

第九章 磁盘调度

1. 磁盘访问时间

磁盘访问时间
= 寻道时间
+ 旋转延迟时间
+ 数据传输时间

寻道时间

磁头移动到目标柱面所需的时间。

旋转延迟时间

等待目标扇区旋转到磁头下方所需的时间。

数据传输时间

实际读取或写入数据所需的时间。

磁盘调度的主要目的是缩短寻道时间。

2. 先来先服务算法FCFS

按照磁盘请求到达的先后顺序进行处理。

特点：

• 简单、公平
• 不会产生饥饿
• 磁头可能频繁来回移动
• 总寻道距离可能较大

3. 最短寻道时间优先SSTF

每次选择距离当前磁头位置最近的请求。

特点：

• 通常可以减少寻道距离
• 远处请求可能长期得不到处理
• 可能产生饥饿

4. 扫描算法SCAN

磁头先沿一个方向移动，依次处理该方向上的请求，到达端点后反向处理。

也称电梯算法。

特点：

• 磁头移动比较有规律
• 性能比较稳定
• 不容易产生长期等待
• 必须先判断磁头当前移动方向

严格SCAN会移动到磁盘端点后再反向。

部分题目中的“电梯算法”可能按LOOK处理，即到当前方向最后一个请求后直接反向，考试时按照题目和老师例题口径计算。

磁盘调度 · 3 算法例题对比

例题：磁头在 50，请求 30、100、20、150、80，方向向大，范围 0~200

算法	走法	总距离
FCFS	50→30→100→20→150→80	20+70+80+130+70 = 370
SSTF	50→30→20→80→100→150	20+10+60+20+50 = 160
SCAN	50→80→100→150→200→30→20	30+20+50+50+170+10 = 330

计算口诀：相邻柱面号取绝对值相加（不是首尾相减）

算法取舍：

• SSTF 距离最优（160）但会饿死远端请求
• SCAN 距离次之（330）但公平稳定——像电梯
• 实际系统多采用 SCAN/LOOK（牺牲距离换公平）

5. 磁盘调度计算步骤

1. 写出磁头初始位置
2. 判断磁头移动方向
3. 根据算法排列请求顺序
4. 写出完整移动路径
5. 计算相邻柱面差的绝对值
6. 将所有移动距离相加
7. 题目给出每移动一个柱面的时间时，再计算寻道时间

总寻道时间
= 总移动柱面数 × 每柱面移动时间

磁盘调度做题 · 4 个易错点

• 取绝对值：|A-B|，不是 A-B
• 相邻求和：按顺序一段段加，不是首尾相减
• 看方向：SCAN 必须先判断磁头移动方向
• SCAN vs LOOK：严格 SCAN 到端点；LOOK 到最大请求就反

答题套路：初始位置 → 方向 → 排序（按算法）→ 算距离（|相邻|相加）→ × 每柱面时间

第十章 客观题补充

这部分优先级低于前面的简答题和综合题，只需要掌握基本结论。

1. 用户态与内核态

设置用户态和内核态的目的是保护操作系统内核和系统资源，不是为了提高运行速度。

用户程序通常在用户态下运行。

操作系统内核和原语通常在内核态下运行。

2. 系统调用

系统调用是操作系统提供给应用程序的接口。

用户程序通过系统调用请求操作系统服务。

3. 中断处理过程

保存现场
→ 分析中断原因
→ 执行中断处理程序
→ 恢复现场
→ 中断返回

CPU通常在执行完一条指令后检查是否有中断。

4. 快表TLB

快表是保存部分页表项的高速缓存。

先查询快表

快表命中
→ 直接得到物理块号

快表未命中
→ 再访问内存中的页表

忽略快表查询时间时：

• 快表命中：访问一次内存
• 快表未命中：访问页表一次，再访问数据一次，共两次内存访问

5. 段页式管理

段页式先分段，再对每一段分页。

不使用快表时，访问一次数据通常需要：

访问段表
→ 访问页表
→ 访问数据

即访问三次内存。

6. 文件系统

从用户角度看，文件系统的主要作用是：

实现文件的按名存取

多级目录通过路径名和文件名访问文件。

位示图用于管理磁盘空闲空间。

逻辑文件通常分为：

1. 流式文件
2. 记录式文件

7. 文件物理分配

连续分配

支持顺序访问和直接访问，速度快，但容易产生外部碎片，文件扩展困难。

链接分配

文件容易扩展，不产生外部碎片，但不适合直接访问。

索引分配

通过索引块保存文件数据块地址，支持直接访问，但需要额外索引空间。

8. 覆盖与交换

覆盖和交换技术的主要目的是节省主存空间，不是物理增加内存容量。

交换是把暂时不能运行的进程换出到外存，需要运行时再换回内存。