操作系统 · 期末终极复习

1 操作系统概述 ★★★★ 高频选择

1.1 OS 核心定义

操作系统是管理计算机硬件与软件资源的系统软件，是用户与硬件之间的接口，是计算机系统的内核与基石。

三个角色：资源管理者 → 用户接口提供者 → 虚拟机扩展者

1.2 OS 四大功能

功能	核心内容	考试关键词
处理器管理	进程控制、同步、通信、调度	PCB、就绪队列、调度算法
存储器管理	内存分配、地址映射、内存保护、虚拟内存	页表、TLB、缺页、置换
设备管理	缓冲区、设备分配、设备驱动	DMA、SPOOLing、中断
文件管理	文件存储、目录管理、文件保护	inode、FAT、位示图

1.3 OS 四大特征

特征	含义	考试陷阱
并发	宏观上同时运行，微观上交替执行（单核）	并发 ≠ 并行！单核只能并发不能并行
共享	多个进程共享系统资源	互斥共享 vs 同时共享
虚拟	将物理实体映射为多个逻辑对应物	时分复用（虚拟处理器）vs 空分复用（虚拟内存）
异步	进程以不可预知的速度推进	异步性导致结果不确定，需要同步机制

经典选择题陷阱：

❌ "多道程序系统中，内存中程序可以并发执行" → 错！内存中多道程序可以并发（单核交替）或并行（多核同时），但程序本身不一定是并发的。

❌ "单核CPU上可以并行执行多个进程" → 错！单核只能并发不能并行。

❌ "并发就是多个事件在同一时刻发生" → 错！并行才是同一时刻；并发是同一时间间隔内。

1.4 并发 vs 并行 — 必考概念

	并发 (Concurrency)	并行 (Parallelism)
时间维度	同一时间间隔内	同一时刻
CPU要求	单核即可（交替执行）	需要多核
宏观/微观	宏观同时，微观交替	宏观微观都同时
经典例子	单核CPU运行多个进程	多核CPU同时运行多个线程

"并发的间隔，并行的时刻" — 并发是时间段内的概念，并行是时间点上的概念。

1.5 分时 / 实时 / 批处理对比

系统类型	关键特征	典型场景	考试关键
批处理	无交互、吞吐量大、周转时间	科学计算、日志分析	追求系统吞吐量
分时系统	交互性强、时间片轮转	Unix/Linux终端	追求响应时间
实时系统	必须截止时间前完成	导弹控制、自动驾驶	追求可靠性+截止时间

1.6 中断与系统调用

中断是OS夺回CPU控制权的唯一途径。用户态→核心态的切换通过中断实现。

graph LR A[用户程序] -->|"系统调用(int 0x80)"| B[陷入指令] B --> C[核心态] C --> D[执行系统服务] D --> E[返回用户态] style C fill:#a371f7,stroke:#fff,color:#fff style A fill:#58a6ff,stroke:#fff,color:#fff

❌ "系统调用就是中断" → 错！系统调用通过陷入指令(trap)触发，属于软中断/异常，不是外部中断。

❌ "用户态程序可以直接访问内核数据" → 错！用户态只能通过系统调用访问内核。

2 进程与线程 + CPU调度必考大题

2.1 进程控制块 PCB

PCB是进程存在的唯一标志。OS通过PCB感知进程的存在。

PCB包含	说明
进程标识符 PID	唯一标识一个进程
程序计数器 PC	下一条指令地址
CPU寄存器	通用寄存器、状态寄存器
进程状态	就绪/运行/阻塞等
内存管理信息	页表、段表指针
I/O状态信息	打开文件表、设备分配

2.2 进程状态转换（必考图）

stateDiagram-v2 [*] --> 创建态创建态 --> 就绪态 : 创建完毕就绪态 --> 运行态 : 被调度运行态 --> 就绪态 : 时间片用完运行态 --> 阻塞态 : I/O请求/等待事件阻塞态 --> 就绪态 : I/O完成/事件到达运行态 --> 终止态 : 执行完毕终止态 --> [*]

❌ "运行态→阻塞态是进程主动的" ✓ 对的（进程执行I/O操作主动阻塞）

❌ "阻塞态→就绪态是进程主动的" ✗ 错！是被动的，等待的事件发生后由OS唤醒

❌ "运行态直接变成就绪态" 可能（时间片用完，被抢占）

关键：运行→阻塞（主动）；阻塞→就绪（被动）；就绪→运行（被动被调度）；运行→就绪（被动被抢占）

2.3 用户级线程 vs 内核级线程

对比项	用户级线程 ULT	内核级线程 KLT
调度者	用户空间线程库	OS内核
系统调用阻塞	阻塞整个进程	只阻塞该线程
多核利用	不能（内核看到一个进程）	能（每个线程独立调度）
切换开销	小（无需内核态切换）	大（需要内核态切换）
典型实现	早期Java线程、POSIX Pthreads（用户模式）	Linux任务、Windows线程

"用户快但不独立，内核慢但真并行"

2.4 CPU调度算法总览

FCFS（先来先服务）

算法思想：按进程到达顺序排队，先到先执行，非抢占。

考试答题模板：

按到达时间排序
依次计算每个进程的完成时间 = max(上一进程完成时间, 本进程到达时间) + 服务时间
周转时间 = 完成时间 - 到达时间
带权周转时间 = 周转时间 / 服务时间

例题：进程 P1(0,3), P2(2,6), P3(4,4), P4(6,2) — 格式(到达时间, 服务时间)

进程	到达	服务	开始	完成	周转	带权周转
P1	0	3	0	3	3	1.0
P2	2	6	3	9	7	1.17
P3	4	4	9	13	9	2.25
P4	6	2	13	15	9	4.5

平均周转 = (3+7+9+9)/4 = 7.0，平均带权 = (1+1.17+2.25+4.5)/4 = 2.23

护航效应(Convoy Effect)：长进程在前，短进程在后排队等待，导致平均周转时间增大。FCFS对短进程不友好。

SJF（短作业优先）/ SPF（短进程优先）

算法思想：选择服务时间最短的进程执行。分抢占式（SRTF）和非抢占式。

非抢占式SJF 做题步骤：

当前时刻，从已到达的进程中选服务时间最小的
该进程执行到完成
时刻推进到完成时间，重复步骤1

抢占式SRTF 做题步骤：

当前时刻，从已到达进程中选剩余服务时间最小的
每次新进程到达时重新比较剩余时间
如果新到达进程的剩余时间更短，抢占当前进程

SRTF 例题：P1(0,7), P2(2,4), P3(4,1), P4(5,4)

进程	到达	服务	开始	完成	周转	带权
P1	0	7	0	16	16	2.29
P2	2	4	2	7	5	1.25
P3	4	1	4	5	1	1.0
P4	5	4	7	11	6	1.5

SRTF平均等待时间最优（可证明），但存在饥饿问题。

SJF快速计算技巧：将所有进程按服务时间从小到大排列，画甘特图时只需按"已到达中选最短"原则依次放置即可。无需繁琐的时间推进计算。

HRRN（高响应比优先）

算法思想：每次调度时计算所有已到达进程的响应比，选择响应比最高的执行。

响应比 R = (等待时间 + 服务时间) / 服务时间 = 1 + 等待时间/服务时间

特点：非抢占，兼顾短进程（分母小→R大）和长进程（等待久→R大），是FCFS和SJF的折中。

HRRN做题技巧：每次调度时，只计算已到达进程的R值，选最大的执行。特别注意：R值计算时等待时间是从到达时刻到当前调度时刻。

"响应比 = 1 + 等/服" — 等得越久、服务越短，响应比越高。

RR（时间片轮转）

算法思想：就绪队列FIFO，每个进程执行一个时间片q，时间片用完排到队尾。

RR做题模板：

建立就绪队列，初始按到达时间排列
取队首进程执行q时间
如果进程未完成，排到队尾；如果完成，出队
时间推进q，期间到达的新进程加入队尾
重复直到所有进程完成

例题：P1(0,5), P2(1,3), P3(2,8), q=2

进程	到达	服务	完成	周转
P1	0	5	10	10
P2	1	3	7	6
P3	2	8	18	16

平均周转 = (10+6+16)/3 = 10.67

❌ RR的最大陷阱：时间片用完时，进程不是直接重新执行，而是排到队尾！

❌ 新到达的进程排在队尾，不是队首！

❌ 如果进程恰好在时间片结束时完成，不需要再排队。

RR快速画图技巧：画一条时间轴，每隔q标注一个时间点。每次时间点检查：①当前进程是否完成 ②队列中下一个是谁 ③这个时间片内有没有新进程到达。

优先级调度

抢占式 vs 非抢占式：关键在于新到达的高优先级进程能否抢占当前运行的低优先级进程。

	非抢占式优先级	抢占式优先级
抢占规则	当前进程运行完，再从就绪队列选最高优先级	新到达的高优先级立即抢占CPU
优点	实现简单，上下文切换少	高优先级响应快
缺点	高优先级可能等很久	低优先级可能饥饿

饥饿(Starvation)：低优先级进程迟迟得不到CPU。解决方案：老化(Aging)——等待越久优先级越高。

多级反馈队列（MFQ）— 考研最爱

核心机制：

多个就绪队列，优先级从高到低，时间片从小到大
新进程进入最高优先级队列
用完时间片未完成→降级到下一级队列
CPU型进程会逐步降级，I/O型进程留在高优先级

MFQ大题套路：题目会给出多个队列和时间片大小。按时间轴逐步推进，记住三条规则：①高优先级队列非空时不调度低优先级 ②同队列内RR ③进程只能向下移动。

"新来就上最高楼，时间到了往下降，I/O回来回原层"

2.5 调度算法对比总表

算法	抢占	优点	缺点	适用	易考指数
FCFS	否	简单、公平	护航效应、短作业不利	批处理	★★★★
SJF/SPF	均可	平均等待最少(抢占)	需预知服务时间、长作业饥饿	批处理	★★★★★
HRRN	否	兼顾长短、不会饥饿	需计算响应比	批处理	★★★★
RR	是	公平、响应快	q太小→切换多；q太大→退化为FCFS	分时系统	★★★★★
优先级	均可	区分紧急程度	低优先级饥饿	实时系统	★★★★
MFQ	是	自适应、兼顾各类进程	参数设置复杂	通用OS	★★★★★

2.6 周转时间计算技巧（非常重要）

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

带权周转时间 W = 周转时间 / 服务时间

平均周转时间 = Σ周转时间 / n

快速计算技巧：

先用甘特图求出每个进程的完成时间
周转 = 完成 - 到达
带权 = 周转 ÷ 服务（带权 ≥ 1.0）
检查方法：所有带权周转 ≥ 1.0，如果不满足肯定是算错了

最容易错：忘记区分到达时间和开始执行时间。周转时间 = 完成-到达，不是完成-开始！

3 同步与互斥超级重点·必考大题

3.1 核心概念

概念	定义	关系
临界资源	一次只允许一个进程访问的资源	打印机、共享变量
临界区	访问临界资源的代码段	进入区→临界区→退出区→剩余区
互斥	多个进程不能同时进入临界区	"你进我不进"
同步	多个进程按特定顺序执行	"你做完我才能做"

"互斥是排他，同步是协作；互斥解决竞争，同步解决顺序"

3.2 信号量机制（Semaphore）

信号量是一个整数变量，只能通过P操作(wait/down)和V操作(signal/up)访问。

// P操作（申请资源）          // V操作（释放资源）
void P(semaphore S) {        void V(semaphore S) {
    while (S <= 0);  // 等      S++;  // 资源+1
    S--;    // 资源-1          // 唤醒一个等待进程
}                            }

3.3 PV操作解题万能模板

Step 1：分析有几个"竞争/合作"关系 → 每种关系一个信号量

Step 2：确定信号量初值 — 互斥信号量初值=1，同步信号量初值=0或资源数

Step 3：画前驱图 — 谁先执行？谁等谁？

Step 4：P在前驱之后，V在前驱之前 — 记住"前V后P"原则

Step 5：配对检查 — 每个P必须有对应的V，否则死锁/永远等待

❌ PV经典错误：

错误1：P和V顺序写反 → 死锁

错误2：忘记初始化信号量 → 行为不确定

错误3：互斥信号量和同步信号量混淆 → 互斥初值=1，同步初值=0

错误4：在临界区内执行V(mutex)而非P(mutex) → 破坏互斥

"PV结对，前V后P；互斥初值为1，同步初值为0"

3.4 生产者-消费者（经典必考）

semaphore mutex = 1;   // 互斥访问缓冲区
semaphore empty = N;   // 空缓冲区位数量
semaphore full = 0;    // 满缓冲区位数量

// 生产者                         // 消费者
void producer() {                void consumer() {
    while(1) {                    while(1) {
        生产一个item;               P(full);    // 等有东西
        P(empty);  // 等空位        P(mutex);
        P(mutex);                 从缓冲区取item;
        放入缓冲区;                  V(mutex);
        V(mutex);                  V(empty);  // 腾空位
        V(full);  // 通知有东西      消费item;
    }                            }
}                               }

关键易错：P(empty)和P(mutex)的顺序！

必须先P(empty)再P(mutex)，否则：消费者拿了mutex等full，生产者等mutex放东西 → 死锁！

同样的：消费者必须先P(full)再P(mutex)。

3.5 读者-写者问题

semaphore rw_mutex = 1;  // 写者互斥
semaphore mutex = 1;     // 保护read_count
int read_count = 0;

// 读者                            // 写者
void reader() {                  void writer() {
    while(1) {                    while(1) {
        P(mutex);                   P(rw_mutex);
        read_count++;               写文件;
        if(read_count == 1)          V(rw_mutex);
            P(rw_mutex); // 第一个读者锁住写者
        V(mutex);                 }
        读文件;                   }
        P(mutex);
        read_count--;
        if(read_count == 0)
            V(rw_mutex); // 最后一个读者释放写者
        V(mutex);
    }
}

读者优先策略：只要有读者在读，新读者可以进入，写者必须等。这样写者可能饥饿。

写者优先策略：引入一个额外信号量，写者到达后阻塞后续读者。

3.6 哲学家进餐

semaphore chopstick[5] = {1,1,1,1,1};
semaphore mutex = 1;  // 限制最多4人同时拿筷子

void philosopher(int i) {
    while(1) {
        思考;
        P(mutex);  // 进入拿筷子区
        P(chopstick[i]);        // 拿左边
        P(chopstick[(i+1)%5]);  // 拿右边
        V(mutex);
        吃饭;
        V(chopstick[i]);        // 放左边
        V(chopstick[(i+1)%5]);  // 放右边
    }
}

死锁条件：如果5个人同时拿起左边的筷子，都在等右边的 → 死锁。

解决方案：①最多允许4个哲学家同时拿筷子 ②奇数号先拿左再拿右，偶数号反之 ③同时拿两根筷子（用mutex保护拿筷子的操作）。

3.7 PV做题流程总结

flowchart TD A["读题：找进程、找资源、找顺序"] --> B["确定信号量种类"] B --> C["互斥信号量初值=1"] B --> D["同步信号量初值=0 或 N"] C --> E["每个进程：P(互斥)...临界区...V(互斥)"] D --> F["前驱图：前V后P"] E --> G["检查：每个P都有对应的V?"] F --> G G -->|"是"| H["✅ 完成"] G -->|"否"| I["❌ 死锁/饿死，修正"]

4 死锁 ★★★★★ 高频计算

4.1 死锁四个必要条件

graph LR A["① 互斥条件"] --> E["死锁"] B["② 请求保持"] --> E C["③ 不可剥夺"] --> E D["④ 环路等待"] --> E style E fill:#f85149,stroke:#fff,color:#fff

必须同时满足4个条件才死锁。打破任意一个即可预防死锁。

"互请不环" — 互斥、请求保持、不可剥夺、环路等待。记法：互(互斥)请(请求保持)不(不可剥夺)环(环路等待)。

4.2 银行家算法 — 超详细步骤

核心数据结构：

Available[m]：系统当前可用资源
Max[n][m]：进程最大需求
Allocation[n][m]：已分配
Need[n][m] = Max - Allocation：还需资源

银行家算法万能模板（考试按这个步骤写，阅卷给满分）：

Step 1 — 计算Need矩阵：Need = Max - Allocation（每个元素对应相减）

Step 2 — 初始化：Work = Available，Finish全为False

Step 3 — 循环查找：找一个未完成进程 i，满足 Finish[i]==False 且 Need[i] ≤ Work

Step 4 — 分配回收：Work = Work + Allocation[i]，Finish[i] = True

Step 5 — 重复：重复Step 3-4直到所有Finish为True（安全）或找不到满足条件的进程（不安全）

经典例题

系统有资源 A=10, B=5, C=7。5个进程：

	Max			Allocation
进程	A	B	C	A	B	C
P0	7	5	3	0	1	0
P1	3	2	2	2	0	0
P2	9	0	2	3	0	2
P3	2	2	2	2	1	1
P4	4	3	3	0	0	2

Step 1：计算Need

进程	Need A	Need B	Need C
P0	7	4	3
P1	1	2	2
P2	6	0	0
P3	0	1	1
P4	4	3	1

Step 2：Available = (10,5,7) - ΣAllocation = (10-7, 5-2, 7-5) = (3, 3, 2)

安全序列查找技巧：

① 先找Need全为0的进程（已经满足），直接回收

② 从Need最小的进程开始试，优先看Need中数字小的

③ 每次回收后Available增加，后面的进程更容易满足

④ 安全序列不是唯一的！只要找到一个就说明系统安全

银行家算法最容易错的三步：

① Available算错 — Available = 系统总资源 - ΣAllocation（注意是每类资源分别减）

② Need[i] ≤ Work 是按分量比较（每个资源都要满足），不是和的大小

③ 每次找到一个安全进程后，要把它的Allocation全加到Work上，不要只加一部分

4.3 死锁检测 vs 死锁避免 vs 死锁预防

策略	时机	方法	特点
死锁预防	系统启动前	破坏四个必要条件之一	静态、严格
死锁避免	运行中、每次分配前	银行家算法	动态、需预知Max
死锁检测+恢复	死锁发生后	资源分配图化简/终止进程	事后补救
鸵鸟策略	不处理	假装死锁不会发生	Windows/Linux采用

5 内存管理绝对重点·必考

5.1 连续分配算法

算法	策略	空闲分区组织	优缺点
首次适应(FF)	找第一个够大的	地址递增排列	简单快速，低地址碎片多
最佳适应(BF)	找最小的够大的	容量递增排列	产生最多外部碎片
最坏适应(WF)	找最大的空闲分区	容量递减排列	大分区被切碎
循环首次适应	从上次位置开始找	地址递增+起始指针	分布更均匀

"首次快碎片多，最佳最浪费（碎片），最坏切大块"

5.2 分页存储管理

地址转换公式（必背！）

逻辑地址 A → 物理地址：

页号 P = A / 页面大小（取整）

页内偏移 W = A % 页面大小（取余）

物理地址 = 页框号 × 页面大小 + W

快速计算技巧：如果页面大小=2ⁿ（通常是2¹²=4KB），地址转换极其简单：

逻辑地址二进制：前(32-n)位=页号，后n位=页内偏移（直接拆分二进制位）

然后页号→页框号（查页表），拼接偏移 = 物理地址

快表 TLB

flowchart LR CPU -->|"逻辑地址"| A{"TLB命中?"} A -->|"是 ✅"| B["直接从TLB取页框号"] A -->|"否 ❌"| C["访问内存中的页表"] C --> D["获取页框号"] D --> E["更新TLB"] B --> F["拼接物理地址"] E --> F

有效访问时间 EAT = 命中率×TLB时间 + (1-命中率)×(TLB时间+内存时间)

5.3 页面置换算法（超级重点）

OPT（最佳置换算法）

思想：淘汰未来最长时间不再访问的页面。理论上最优，但无法实现（需要预知未来）。用作其他算法的比较基准。

例题：页框数=3，页面引用串：7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1

缺页次数=9，缺页率=9/20=45%

OPT快速做法：需要淘汰时，从当前页框中的每个页面出发，往后找到下一次出现的位置，选最远的那个淘汰。如果某个页面以后都不出现，直接选它淘汰。

FIFO（先进先出）

思想：淘汰最早进入内存的页面。实现简单，用队列。

Belady异常：FIFO算法中，增加页框数反而导致缺页率增加！这是FIFO独有的异常现象。

例如：引用串 1,2,3,4,1,2,5,1,2,3,4,5

3个页框 → 缺页9次；4个页框 → 缺页10次（反而更多！）

只有FIFO会出现Belady异常！LRU和OPT都不会。

LRU（最近最久未使用）

思想：淘汰最近最长时间没有被访问的页面。基于"过去未使用→将来也不太可能使用"的局部性原理。

LRU手算万能模板：

① 维护一个访问时间戳或栈，记录每个页面上次访问的时间

② 缺页时，淘汰时间戳最小（栈底）的页面

③ 每次访问后更新该页面的时间戳（或移到栈顶）

LRU快速计算技巧：从当前时刻向前看每个页框中的页面，找到距离当前访问最远的上一次出现，淘汰那个。

可以列表格跟踪，每列是时间，每行是页框，标记每次访问后页框中的页面。

CLOCK（时钟置换 / NRU）

思想：将页框排成环形链表，每个页框有一个访问位。指针循环扫描：

如果访问位=1 → 置0，指针前移
如果访问位=0 → 淘汰该页

相当于给页面"第二次机会"。是LRU的近似实现，性能接近LRU但开销更小。

flowchart TD A["缺页发生"] --> B["指针指向当前页"] B --> C{"访问位==0?"} C -->|"是"| D["淘汰该页，装入新页，访问位置1"] C -->|"否"| E["访问位置0"] E --> F["指针前移一位"] F --> C

改进CLOCK：同时考虑访问位A和修改位M，优先淘汰A=0且M=0的页面（既没被访问也没被修改）。

5.4 缺页率计算

缺页率 = 缺页次数 / 总访问次数

❌ 首次访问页面一定缺页（初始时内存为空），别漏算！

❌ 如果题目问"缺页中断次数"，包括第一次装入时的中断。

6 文件系统 ★★★★ 重点

6.1 文件逻辑结构 vs 物理结构

	逻辑结构	物理结构
含义	用户看到的文件组织方式	文件在磁盘上的存储方式
类型	无结构(流式)、有结构(记录式)	连续、链接、索引
决定者	用户/应用程序	OS/文件系统

6.2 文件物理结构（重点）

分配方式	实现	优点	缺点
连续分配	文件占连续盘块	顺序访问快、简单	外部碎片、文件难扩展
隐式链接	每块指向下一块	无外部碎片	随机访问慢、指针占空间
显式链接(FAT)	FAT表集中记录链接	随机访问快于隐式链接	FAT表占内存
索引分配	索引块存所有盘块号	支持直接访问	索引块额外开销
多级索引	一级→二级→三级索引	支持大文件	访问需多次读盘
混合索引	inode：直接+间接索引	大小文件兼顾	实现复杂

6.3 inode 混合索引（必考计算）

Unix/Linux inode 典型结构：

10个直接块（直指数据块）
1个一级间接块（指向索引块，索引块再指向数据块）
1个二级间接块
1个三级间接块

设盘块大小=4KB，盘块号占4字节：

每块可存盘块号数 = 4KB / 4B = 1024个

直接块：10 × 4KB = 40KB

一级间接：1024 × 4KB = 4MB

二级间接：1024² × 4KB = 4GB

三级间接：1024³ × 4KB = 4TB

最大文件大小 ≈ 4TB

地址计算技巧：给定逻辑块号，判断在哪个区域：

块号 0-9 → 直接块
块号 10-1033 → 一级间接（10 + 1024 = 1034）
1034以上 → 二级/三级间接

6.4 位示图

用1 bit表示一个盘块的使用状态：0=空闲，1=已分配。

位示图大小 = 磁盘总块数 / 8 字节

位示图→盘块号换算：第i行第j列（从0开始），每行n位 → 盘块号 = i×n + j

盘块号→位示图：行号 = 盘块号 / n，列号 = 盘块号 % n

7 磁盘调度算法 ★★★★★ 必考计算

7.1 磁盘结构速览

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

其中寻道时间占比最大，磁盘调度算法就是为了减少寻道时间。

7.2 四大算法详解

FCFS（先来先服务）

按请求顺序依次服务。公平但效率低。

例题：磁头在50号，请求序列：98, 183, 37, 122, 14, 124, 65, 67

移动路径：50→98→183→37→122→14→124→65→67

总移动道数 = |98-50|+|183-98|+|37-183|+|122-37|+|14-122|+|124-14|+|65-124|+|67-65|

= 48+85+146+85+108+110+59+2 = 643道

SSTF（最短寻道时间优先）

每次选择距离当前磁头最近的请求。类似于SJF（短作业优先）。

移动路径：50→65→67→37→14→98→122→124→183

总移动 = |65-50|+|67-65|+|37-67|+|14-37|+|98-14|+|122-98|+|124-122|+|183-124|

= 15+2+30+23+84+24+2+59 = 239道

SSTF可能造成饥饿：如果一直有靠近磁头的新请求，远处的请求永远得不到服务。

SCAN（电梯算法）

磁头向一个方向移动，服务沿途所有请求，到达端点后反向移动。

磁头初始50，向磁道号增大方向（0→199）：

移动路径：50→65→67→98→122→124→183→199→37→14

总移动 = |65-50|+|67-65|+...+|199-183|+|199-37|+|37-14|

= 15+2+31+24+2+59+16+162+23 = 334道

❌ SCAN需要走到端点才折返！即使中间没有请求也要走到底。这是SCAN和LOOK的区别。

LOOK算法：走到该方向最后一个请求就折返，不需要走到端点。

CSCAN（循环扫描）

磁头向一个方向移动，服务沿途请求，到达端点后快速返回到起始端（不服务），再从起始端继续向同一方向扫描。

磁头初始50，向增大方向：

移动路径：50→65→67→98→122→124→183→199→0→14→37

总移动 = (到199路径) + (199→0) + (0到37路径)

= 133 + 199 + 37 = 369道

7.3 磁盘调度算法对比

算法	寻道性能	公平性	饥饿	易考指数
FCFS	差	最好	无	★★★
SSTF	较好	差	有	★★★★
SCAN	好	较好	无	★★★★★
CSCAN	较好	好	无	★★★★★
LOOK	好	较好	无	★★★★

"先进先出最简单，最短优先易饿死，电梯走到头才回，循环扫描单向转"

8 I/O系统 ★★★ 概念为主

8.1 DMA（直接存储器访问）

DMA控制器代替CPU在外设和内存之间直接传输数据，CPU只需在传输开始和结束时干预。

sequenceDiagram participant CPU participant DMA participant 设备 participant 内存 CPU->>DMA: 设置传输参数(源/目的/长度) DMA->>设备: 启动读/写 loop 逐字传输(周期窃取) 设备->>DMA: 数据 DMA->>内存: 写入数据 end DMA->>CPU: 中断通知传输完成

❌ "DMA传输过程中CPU完全不参与" → 错！CPU需要设置初始参数、响应完成中断。

❌ "DMA可以代替CPU执行程序" → 错！DMA只传输数据，不执行指令。

8.2 I/O控制方式对比

方式	CPU参与度	传输单位	适用
程序直接控制	CPU全程参与（轮询）	字/字节	简单慢速设备
中断驱动	CPU在传输时被中断	字/字节	中低速设备
DMA	CPU只在开始/结束参与	数据块	高速设备（磁盘）
通道	CPU只需发I/O指令	一组数据块	大型机

8.3 SPOOLing（假脱机）

在磁盘上开辟输入井/输出井，将独占设备虚拟为共享设备。

核心组件：输入井、输出井、输入进程、输出进程

经典应用：共享打印机（多个用户"同时"打印，实际先写到磁盘输出井）

"SPOOLing = 磁盘帮你排队，独占变共享"

8.4 缓冲区

类型	原理	优点
单缓冲	1个缓冲区，处理+传输串行	实现简单
双缓冲	2个缓冲区交替使用	传输与处理并行
循环缓冲	多个缓冲区组成环	应对突发数据
缓冲池	系统级统一管理	利用率高

🔥 高频考点排行榜

排名	考点	章节	热度	题型	分值预估
🥇	PV操作（信号量同步）	Ch3	★★★★★	大题10-15分	15分
🥈	银行家算法	Ch4	★★★★★	大题8-12分	12分
🥉	页面置换算法(LRU)	Ch5	★★★★★	大题8-10分	10分
4	磁盘调度(SCAN/CSCAN)	Ch7	★★★★★	大题8-10分	10分
5	CPU调度(RR/SRTF/MFQ)	Ch2	★★★★★	大题8-12分	12分
6	地址转换(分页/分段)	Ch5	★★★★	选择+大题	8分
7	inode混合索引计算	Ch6	★★★★	选择+计算	6分
8	死锁四条件+判断	Ch4	★★★★	选择+简答	5分
9	位示图计算	Ch6	★★★	选择	3分
10	并发vs并行/OS特征	Ch1	★★★	选择	3分

🚀 期末速通路线

三天冲刺路线

Day 1（6-8小时）

上午（3h）：第2章 CPU调度算法（FCFS/SJF/RR/MFQ）+ 第3章 PV操作（生产者-消费者+读者-写者+哲学家）

下午（3h）：第5章分页+页面置换（LRU/FIFO/OPT/CLOCK）刷题5-8道

晚上（2h）：第4章死锁+银行家算法刷题3道

Day 2（5-6小时）

上午（3h）：第7章磁盘调度（SSTF/SCAN/CSCAN）+ 第6章 inode+位示图计算

下午（2-3h）：做1套完整真题（计时，模拟考试），重点检查PV题和页面置换题

Day 3（4-5小时）

上午（2h）：回顾错题，重做银行家算法和LRU（最容易算错）

下午（2h）：过一遍选择题（第1章概述+第8章I/O），背口诀

考前1h：看易错点总表+算法对比表

一天速记路线（考前抱佛脚版）

上午 4h：PV解题模板 + 银行家算法模板 + LRU/CLOCK置换过程 → 刷各1道经典题

下午 3h：RR甘特图 + 磁盘SCAN/CSCAN + 地址转换公式 → 刷各1道

晚上 2h：背口诀 + 看易错点 + 看算法对比表

考前30分钟看什么

PV"前V后P"原则 — 互斥初值1，同步初值0
银行家算法步骤 — Need=Max-Alloc, Work找Need≤Work的
LRU淘汰规则 — 淘汰最久未用的
周转时间公式 — T=完成-到达，带权=T/服务
并发≠并行
Belady异常只有FIFO有
SCAN走到端点才折返

📋 做题模板库

模板1：银行家算法万能模板

// ====== 银行家算法 万能答题模板 ======
// 给分点：每一步都要写清楚！

// 1. 计算Need矩阵
Need[i][j] = Max[i][j] - Allocation[i][j]

// 2. 计算Available
Available = 系统总资源 - ΣAllocation（每类资源分别计算）

// 3. 安全性检查
Work = Available
Finish = [false, false, ..., false]

while (存在i满足 Finish[i]==false 且 Need[i] <= Work):
    Work = Work + Allocation[i]
    Finish[i] = true
    // 👆 记录进程i到安全序列中

if 所有Finish[i]==true:
    系统安全，安全序列为: [记录的顺序]
else:
    系统不安全！

// 4. 若收到资源请求Request[i]
if Request[i] <= Need[i] 且 Request[i] <= Available:
    Available -= Request[i]
    Allocation[i] += Request[i]
    Need[i] -= Request[i]
    重新进行安全性检查（回到步骤3）
else:
    拒绝请求

模板2：页面置换算法模板

// ====== 页面置换 万能答题模板 ======

// 页框数 = M，引用串 = R[0..N-1]

// 画表（列为时间步，行为页框）
//   T0  T1  T2  T3  T4  ...
// ┌───┬───┬───┬───┬───┐
// │   │   │   │   │   │  ← 页框0
// │   │   │   │   │   │  ← 页框1
// │   │   │   │   │   │  ← 页框2
// └───┴───┴───┴───┴───┘
// ✓=命中  ✗=缺页

// FIFO: 记录每个页面进入时间，淘汰最早进入的
// LRU:  记录每个页面上次访问时间，淘汰最久未访问的
// OPT:  往后看每个页面下次出现的位置，淘汰最远的
// CLOCK: 访问位环形扫描，0→淘汰，1→置0并前进

模板3：PV操作模板

// ====== PV操作 万能答题模板 ======

// Step 1: 声明信号量 + 初始化
semaphore mutex = 1;   // 互斥（每个临界资源一个）
semaphore cond_i = 0;  // 同步（每种同步关系一个）

// Step 2: 每个进程结构
Px() {
    P(cond);     // 有前置条件？先P
    P(mutex);    // 进入临界区
    临界区操作;
    V(mutex);    // 退出临界区
    V(cond);     // 释放后续条件
}

// Step 3: 自检
// ① 每个P都有对应V？
// ② mutex的PV在同一个进程中成对出现？
// ③ 同步信号量的P和V分别在两个进程中？

模板4：RR调度模板

// ====== RR调度 万能答题模板 ======
// 时间片 q = ?

// Step 1: 建立就绪队列，按到达时间排序
// Step 2: 维护时间和就绪队列
t = 0;
while (还有进程未完成) {
    if (就绪队列为空) t++; continue;
    P = 取队首进程;
    执行 min(q, P.剩余时间);
    t += 执行时间;
    // 这段时间内新到达的进程加入队尾
    if (P未完成) P加入队尾;
}
// Step 3: 计算周转 = 完成 - 到达

⚠️ 易错点总表

#	知识点	常见错误	正确做法	丢分风险
1	周转时间	用完成-开始，而非完成-到达	周转 = 完成 - 到达时间	高
2	RR队列	新到达进程放队首	新到达进程放队尾	高
3	FIFO置换	忘记Belady异常	只有FIFO有这个异常，LRU/OPT没有	中
4	PV操作	P(mutex)和P(同步)顺序写反→死锁	先P同步再P互斥	极高
5	信号量初值	互斥信号量初值写成0	互斥=1，同步=0或资源数	高
6	银行家Need	Max矩阵中的元素抄错	Need = Max - Allocation，逐元素减	高
7	银行家安全序列	Work只加部分资源	Work += Allocation[i]的所有分量	中
8	磁盘SCAN	不到端点就折返	SCAN必须走到端点（LOOK才提前折返）	高
9	缺页率	忘记首次访问一定缺页，或忘记算初始装入	第一次访问每个页面一定缺页	中
10	地址转换	页大小不是2^n时硬拆分二进制	页大小=2^n时才能用二进制拆分法	中
11	并发vs并行	"单核可以并行"	单核只能并发，多核才能并行	中
12	死锁条件	只满足3个条件也可能死锁	必须同时满足4个才死锁	中

📊 三大类算法对比总表

CPU调度算法

算法	抢占	优点	缺点	易考	口诀
FCFS	否	公平简单	护航效应	★★★★	先来先跑
SJF	否	平均等待最小	长作业饿死	★★★★	短者优先
SRTF	是	理论最优	实现困难	★★★★★	剩余最短抢CPU
HRRN	否	兼顾长短	计算开销	★★★★	等得久+任务短
RR	是	响应公平	q难调	★★★★★	转一圈就换人
MFQ	是	自适应	参数多	★★★★★	短上长下

页面置换算法

算法	淘汰策略	Belady异常	实现难度	易考	口诀
OPT	未来最远不用的	无	无法实现	★★★★	最佳就是预知未来
FIFO	最早进来的	有！	简单	★★★★★	来得早走得早
LRU	最近最久未用	无	中等	★★★★★	最懒的走
CLOCK	访问位=0的	无	简单	★★★★	给第二次机会

磁盘调度算法

算法	策略	饥饿	易考	口诀
FCFS	按请求顺序	无	★★★	排队服务
SSTF	距磁头最近的	有	★★★★	谁近服务谁
SCAN	单向到底折返	无	★★★★★	电梯到底才回
CSCAN	单向到底跳回起始	无	★★★★★	循环扫不停

🧠 口诀汇总

章节	口诀	对应知识点
Ch1	并发的间隔，并行的时刻	并发 vs 并行
Ch1	批处理要吞吐，分时要响应，实时要可靠	三大OS类型目标
Ch2	运行阻塞是主动，阻塞就绪是被动	进程状态转换
Ch2	新来就上最高楼，时间到了往下降	多级反馈队列
Ch2	响应比 = 1 + 等/服	HRRN公式
Ch2	用户快但不独立，内核慢但真并行	用户级vs内核级线程
Ch3	互斥是排他，同步是协作	互斥 vs 同步
Ch3	互请不环	死锁四条件（互斥、请求保持、不可剥夺、环路）
Ch3	PV结对，前V后P；互斥初1，同步初0	PV操作规则
Ch4	Need = Max - Alloc	银行家算法Need矩阵
Ch5	首次快碎片多，最佳最浪费，最坏切大块	连续分配算法
Ch5	OPT看未来，FIFO看过去，LRU看最近	页面置换算法
Ch5	只有FIFO有Belady异常	Belady异常
Ch7	电梯走到头才回，循环扫描单向转	SCAN vs CSCAN
Ch8	SPOOLing = 磁盘帮你排队	SPOOLing技术

1.1 OS 核心定义

1.2 OS 四大功能

1.3 OS 四大特征

1.4 并发 vs 并行 — 必考概念

1.5 分时 / 实时 / 批处理 对比

1.6 中断与系统调用

2.1 进程控制块 PCB

2.2 进程状态转换（必考图）

2.3 用户级线程 vs 内核级线程

2.4 CPU调度算法总览

FCFS（先来先服务）

SJF（短作业优先）/ SPF（短进程优先）

HRRN（高响应比优先）

RR（时间片轮转）

优先级调度

多级反馈队列（MFQ）— 考研最爱

2.5 调度算法对比总表

2.6 周转时间计算技巧（非常重要）

3.1 核心概念

3.2 信号量机制（Semaphore）

3.3 PV操作解题万能模板

3.4 生产者-消费者（经典必考）

3.5 读者-写者问题

3.6 哲学家进餐

3.7 PV做题流程总结

4.1 死锁四个必要条件

4.2 银行家算法 — 超详细步骤

经典例题

4.3 死锁检测 vs 死锁避免 vs 死锁预防

5.1 连续分配算法

5.2 分页存储管理

地址转换公式（必背！）

快表 TLB

5.3 页面置换算法（超级重点）

OPT（最佳置换算法）

FIFO（先进先出）

LRU（最近最久未使用）

CLOCK（时钟置换 / NRU）

5.4 缺页率计算

6.1 文件逻辑结构 vs 物理结构

6.2 文件物理结构（重点）

6.3 inode 混合索引（必考计算）

6.4 位示图

7.1 磁盘结构速览

7.2 四大算法详解

FCFS（先来先服务）

SSTF（最短寻道时间优先）

SCAN（电梯算法）

CSCAN（循环扫描）

7.3 磁盘调度算法对比

8.1 DMA（直接存储器访问）

8.2 I/O控制方式对比

8.3 SPOOLing（假脱机）

8.4 缓冲区

三天冲刺路线

一天速记路线（考前抱佛脚版）

考前30分钟看什么

模板1：银行家算法万能模板

模板2：页面置换算法模板

模板3：PV操作模板

模板4：RR调度模板

CPU调度算法

页面置换算法

磁盘调度算法

1.5 分时 / 实时 / 批处理对比