操作系统

重点在 6 类计算题：甘特图、首次/最优/最差适应、分页地址转换、置换算法缺页、银行家、inode 框图。

易错速查

• fork 返回：父=子PID>0，子=0，错<0；fork 进程数 = 叶子节点数
• 并发 ≠ 并行：单核可并发不可并行
• 进程 = 资源分配单位；线程 = 调度单位；同进程线程共享地址空间
• 优先级调度同优先级跑完再切；RR 时片到立刻切
• 临界区三要求：互斥 / 进步 / 有限等待（不是"公平"也不是"无饥饿"）
• wait/signal 阻塞实现：S-- 后若 S<0 阻塞，S++ 后若 S<=0 唤醒
• 生产者-消费者：必须 wait(empty/full) 先于 wait(mutex)，反则死锁
• 死锁四条件：互斥 / 占有并等待 / 非抢占 / 循环等待
• 银行家用 Need 跑安全性；检测算法用 Request
• 安全 ⊂ 无死锁；非安全 ↛ 必死锁
• 首次/最优 > 最差适应
• 50% 规则：$N$ 个已分配块 → 约 $0.5N$ 个外部碎片
• 外部碎片分页无、分段有；内部碎片分页有、分段无
• $\text{PA} = f \times 2^n + d$；多级页表高位是 $p_1$
• 缺页率 $p$ 必须 $\sim 10^{-6}$ 级 EAT 才可接受
• 缺页处理 7 步：trap → 保存状态 → 查 PCB → 取空闲帧（无则置换）→ 读盘 → 改页表（valid 置 v）→ 重启指令
• 脏位 = 写过的标志；置换时脏页写回、干净页丢弃 → 省一半 I/O
• 增强二次机会优先级：$(0,0)>(0,1)>(1,0)>(1,1)$，给"脏页"加保留权重
• Belady 异常仅 FIFO 出现；栈算法（LRU、OPT）一定不会
• OPT 不可实现；LRU 用过去近似未来
• 全局置换可能引发抖动；局部置换把抖动局限在单进程
• SSTF 可能饥饿；SCAN / LOOK 不会
• 文件分配：连续 = 起始+长度（外部碎片）；链式 = 每块带 next 指针（只能顺序）；FAT = 链式 + 集中查找表常驻内存（支持随机访问）；索引 = 每文件一索引块；inode = 组合方案
• inode 不存文件名；文件名在目录条目里
• $T_{\text{access}} = T_{\text{seek}} + T_{\text{rot}} + T_{\text{transfer}}$；平均旋转 = $30/\text{RPM}$ 秒
• 缓冲 (Buffer) 可能是数据唯一存储；缓存 (Cache) 是已有数据的副本

进程管理

多进程图像

CPU 工作原理

• 取指-执行循环：PC → 取指 → IR → 解码 → 执行 → PC 自增
• 跳转指令直接修改 PC
• 上电后 CPU 自动循环；管理 CPU 最直观的方法：设好 PC 初值，CPU 自动干活

进程定义

• 进程 (process)：程序的一次执行，活动实体
• 程序 (program)：磁盘上的可执行文件，被动实体
• 同一程序可对应多进程：text 段共享，heap/data/stack 独立
• 进程"看上去"独立使用 CPU + 私有地址空间

PCB（Process Control Block）

• PCB = 进程的"现场存档"，切换时靠它恢复
• 包含：
  • 进程状态、PID
  • PC、CPU 寄存器组、栈指针、条件码、PSW
  • 调度信息（优先级、所属队列指针）
  • 内存管理信息（base/limit 或页表指针）
  • 记账（CPU 时间）
  • I/O 状态（打开文件表、设备列表）
• PCB 字段在进程生存期内会变（PC、状态、寄存器）

进程 5 态图

• New：刚创建
• Ready：就绪，等被调度
• Running：在 CPU 上执行
• Waiting / Blocked：等 I/O 或事件
• Terminated：执行结束

转换条件：

• new → ready：admit
• ready → running：dispatch
• running → ready：时间片到 / 高优先级抢占 / 中断
• running → waiting：发起 I/O 或 wait()
• waiting → ready：I/O 完成 / 事件发生
• running → terminated：exit

fork / exec / wait

• pid_t fork()：复制父进程（COW 写时复制优化），独立 PID、单线程
  • 父返回子 PID，子返回 0，错返回 -1
  • 父子并发顺序由调度器决定
• execve(path, argv, envp)：替换地址空间，PID 不变
• wait(&status)：父阻塞直到任一子终止，回收 PCB
• waitpid(pid, &s, WNOHANG)：非阻塞
• shell 模型：while(1){ read cmd; if(!fork()) exec(cmd); else wait(); }

fork 树叶节点

• 给一段含若干 fork() 的代码，求最终进程数 → 画 fork 树，数叶子
• 每个 fork()：当前节点分裂成父继续 + 子新枝
• 注意分支条件、循环：不是所有进程都执行后续 fork
• $n$ 次连续无条件 fork → $2^n$ 个进程

僵尸 vs 孤儿

• 僵尸 (zombie)：子已 exit、父未 wait → 内核留 PCB 残骸；ps 显示 <defunct>
• 孤儿 (orphan)：父先 exit → 子被 init (PID=1) 收养并回收
• 级联终止：部分系统父死则所有子皆死

上下文切换

必考简答："请描述内核在进程间进行上下文切换时的步骤"

• 标准 4 步：
  • 响应时钟中断，OS 保存当前进程 PC 和用户栈指针，控制权交内核中断处理程序
  • 中断处理程序把其余寄存器、机器状态（如浮点）存到当前进程 PCB
  • OS 调用调度器选下一个要执行的进程
  • 从新进程 PCB 取出寄存器状态，恢复处理器到该进程被中断时的状态，用户模式继续执行
• 切换是纯 overhead；涉及用户态↔内核态切换

多道程序 CPU 利用率

• $\eta_{\text{CPU}} = \dfrac{\text{CPU 忙时间}}{\text{总执行时间}}$
• 单道：CPU 等 I/O 时空闲；多道：用其他进程填 I/O 等待
• 同理可算各 I/O 设备利用率

线程

线程 vs 进程

	进程	线程
单位角色	资源分配	调度
地址空间	独立	共享所属进程
切换开销	大（切页表）	小

• 同一进程内线程共享：代码段、数据段、打开文件、信号处理
• 同一进程内线程独立：tid、PC、寄存器组、栈
• 不同进程不共享地址空间

并发与并行

• 并行 (parallel)：多任务物理上同时执行，需多核
• 并发 (concurrent)：多任务逻辑上同时推进，单核时间片即可
• 可以并发但无并行：单核 CPU 时间片轮转——宏观同时、微观同一刻仅一个真正执行

Amdahl 定律

$\text{Speedup} \le \frac{1}{S + \dfrac{1-S}{N}}$

• $S$ = 串行比例，$1-S$ = 并行比例，$N$ = 核数
• $N \to \infty$ 时上界 $1/S$，串行部分是终极瓶颈
• 题型：给并行比例和核数，代入算加速比

用户级 vs 内核级线程

	用户级	内核级
管理者	用户线程库	内核
切换	用户态，快	系统调用，慢
内核可见	否	是
单线程阻塞	整进程阻塞	仅该线程阻塞
真正并行	多核上不行	可以

• 用户级切换核心：Yield() 保存当前 esp 到 TCB → 取下一 TCB 的 esp → 切栈
• 每线程需要独立栈 + TCB

硬件类比：线程 = FSM；Yield = 多个 FSM 共享一条 datapath，靠 TCB 保存/恢复状态

CPU 调度

调度准则

• CPU 利用率：CPU 忙占比，最大化
• 吞吐量 (throughput)：单位时间完成进程数，最大化
• 周转时间 (turnaround)：$T_{\text{完成}} - T_{\text{到达}}$，含等待 + CPU + I/O，最小化
• 等待时间 (waiting)：在就绪队列中等待时间之和，最小化
• 响应时间 (response)：$T_{\text{首次执行}} - T_{\text{到达}}$，最小化

准则冲突

• CPU 利用率 vs 响应时间：低响应 → 频繁切换 → 切换开销占 CPU → 利用率降
• 平均周转 vs 最大等待：SJF 让平均周转最小，但短作业不断到达时长作业最大等待时间无界
• I/O 设备利用率 vs CPU 利用率：I/O 密集多 → 设备忙 CPU 闲；CPU 密集多 → 反之

算法对比

算法	抢占	平均等待	饥饿	一句话
FCFS	否	差	否	FIFO；护送效应让长作业堵后续
SJF	否	最优	可能	选 burst 最短，需预测
SRTF	是	最优	可能	抢占式 SJF
优先级	可选	取决	是	老化（aging）解饥饿
RR	是	中	否	FCFS + 时片 $q$，保响应
MLQ	取决	取决	可能	进程永久分到某队列
MLFQ	是	接近 SJF	升级避免	队列间可迁移

多级队列调度（MLQ, Multilevel Queue）

把就绪队列拆成多个独立队列，每个队列独立调度：

• 经典分法：
  • 前台队列（交互进程）→ 用 RR，保响应时间
  • 后台队列（批处理）→ 用 FCFS，保吞吐量
• 队列之间的调度策略：
  • 固定优先级抢占：高优先级队列里有进程就先跑；低优先级可能饥饿
  • 时间片分配：如 80% CPU 给前台、20% 给后台
• 典型 5 级（高→低）：系统进程 → 交互进程 → 交互编辑进程 → 批处理 → 学生进程
• 关键缺点：进程被永久分配到某个队列，无法在队列间移动 → 不灵活

多级反馈队列调度（MLFQ, Multilevel Feedback Queue）

MLQ 的改进：进程可在队列间迁移，"反馈"指根据进程行为动态调整其优先级。

由 5 个参数定义：

• 队列数量
• 每个队列的调度算法（如 RR、FCFS）
• 升级条件：进程在低优先级队列等太久 → 升到高优先级队列（避免饥饿）
• 降级条件：用完时间片还没跑完 → 降到低优先级队列（惩罚长任务）
• 新进程进入哪个队列（通常从最高优先级开始）

经典 3 队列例子：

队列	算法	时间片	时片用完后
Q1（最高）	RR	8 ms	没跑完 → 降到 Q2
Q2（中）	RR	16 ms	没跑完 → 降到 Q3
Q3（最低）	FCFS	—	—

执行规则：Q1 空才跑 Q2，Q2 空才跑 Q3（高优先级队列优先）

设计思想——为什么这样能接近 SJF 又不需预知 burst：

• 短任务：几次小时间片就跑完，始终待在 Q1——享受高优先级和短响应
• 长任务：反复用完时间片 → 逐级降到 Q3 → 让 CPU 给短任务先跑
• I/O 密集任务：跑一会就阻塞（没用完时间片）→ 留在高优先级队列 → 响应快
• CPU 密集任务：跑满时间片 → 降级 → 不抢交互任务的响应
• 老化：在低优先级队列等过久 → 升回高优先级，避免饥饿

类比：自助餐排队——短餐人快速走完不被打扰；点大份的被让到长队慢慢等；等太久的会被服务员叫到前面

MLFQ ≈ "自动识别短/长任务的 SJF"——不需要预测 burst，靠观察实际行为来分类

优先级 vs 时间片（同优先级时的行为差异）

容易混淆：同样面对"多个进程同优先级"，两种调度处理完全不同

优先级调度（非抢占）：

• 选最高优先级跑；同优先级按 FCFS 排
• 一旦选中 → 跑到结束或阻塞才切（非抢占语义）
• 后果：先到的同优先级进程独占 CPU 直到自愿让出，后到的同优先级要排队等

时间片调度（RR）：

• 所有进程视为同优先级（或同一队列内同优先级）
• 每个进程跑 $q$ 个时间片 → 不论完没完，强制切换到下一个
• 后果：轮流执行，无人能霸占

对比例子：P1、P2 同优先级，都在 $t=0$ 就绪，burst 都是 10ms

• 优先级调度：P1 跑 10ms 跑完 → 再跑 P2 10ms 跑完。P2 等 10ms
• RR（$q=2$ms）：P1 跑 2ms → P2 跑 2ms → ... 交替 5 次。P1、P2 都"边跑边等"，响应快但周转一样

SJF 视角：优先级调度是个框架

这条理解能把零散的算法串起来

核心观察：很多算法都能写成"选优先级最高的进程跑"，只是"优先级"定义不同：

算法	优先级定义
FCFS	到达越早 → 优先级越高
SJF	预测 burst 越短 → 优先级越高（即 1/burst）
优先级调度	用户/系统显式指定
RR	所有进程优先级相同 + 时间片强制切换
单调速率（实时）	周期越短 → 优先级越高
最早截止期限优先（EDL）	截止越早 → 优先级越高

所以"SJF 是优先级调度的特例"= 把"短作业优先"重新解读成"短作业优先级高"——本质都是"选最高优先级跑"，只是排队依据换了。

类比：所有调度算法都是"在就绪队列前排个顺序"——FCFS 按到达排，SJF 按 burst 排，优先级按 priority 排，RR 按"轮到谁就谁"排

RR 时间片

• $q \to \infty$ 退化为 FCFS
• $q \to 0$ 上下文切换开销主导
• 经验：$q$ 远大于上下文切换时间，10–100 ms
• $n$ 个进程时单进程等待上界 $(n-1)q$

甘特图画法

必考大题：给若干进程的到达时间和 burst，画甘特图，求周转和等待

• FCFS：按到达顺序依次跑完
• SJF（非抢占）：当前进程跑完后从就绪队列选 burst 最短
• 非抢占优先级：同 SJF，但选优先级最高，同优先级按到达顺序
• RR ($q$)：每段最多跑 $q$；未跑完入就绪队尾；新到进程入队尾
• 计算：
  • $T_{\text{周转}} = T_{\text{完成}} - T_{\text{到达}}$
  • $T_{\text{等待}} = T_{\text{周转}} - T_{\text{burst}}$
  • 平均取算术平均
• 易错：RR 中"同时到达"和"被抢占下来"的入队顺序，多数教材新到的排在被抢占的之前

SJF burst 预测（指数平均）

$\tau_{n+1} = \alpha t_n + (1-\alpha)\tau_n$

• $t_n$：第 $n$ 次实际 burst；$\tau_n$：预测
• $\alpha = 0$：$\tau_{n+1} = \tau_n$，忽略历史，恒用初始猜测
• $\alpha = 1$：$\tau_{n+1} = t_n$，只信最近一次
• $\alpha = 1/2$：近期与远期等权

Windows 优先级

• 线程优先级 = 优先级类基值 + 相对优先级偏移
• 优先级类基值（NORMAL 相对优先级位置）：
  • REALTIME_PRIORITY_CLASS：24
  • HIGH_PRIORITY_CLASS：13
  • ABOVE_NORMAL_PRIORITY_CLASS：10
  • NORMAL_PRIORITY_CLASS：8
  • BELOW_NORMAL_PRIORITY_CLASS：6
  • IDLE_PRIORITY_CLASS：4
• 相对优先级偏移（相对 NORMAL）：
  • IDLE = $-15$
  • LOWEST = $-2$
  • BELOW_NORMAL = $-1$
  • NORMAL = $0$
  • ABOVE_NORMAL = $+1$
  • HIGHEST = $+2$
  • TIME_CRITICAL = $+15$
• 求线程优先级：类基值 + 偏移

进程同步

竞态与临界区

• 竞态条件：并发访问共享数据，结果依赖执行顺序
• counter++ 实为 read-modify-write 三步，可被中间打断

临界区程序的 4 段式骨架（进程反复循环这 4 段，外层 do { ... } while(TRUE)）：

• 进入区 (entry)：请求进入临界区的代码，如 wait(mutex)、Peterson 的 flag[i]=TRUE; turn=j; while(...)
• 临界区 (CS)：真正读写共享资源，如 counter++、改链表、写共享文件
• 退出区 (exit)：释放许可、通知他人，如 signal(mutex)、flag[i]=FALSE
• 剩余区 (remainder)：与共享资源无关的本职工作
• 区分 4 段的意义：精确定义"进步"——只有不在剩余区的进程才能参与谁进 CS 的竞争

三个要求

• 互斥 (Mutual Exclusion)：$P_i$ 在 CS 时其他进程不得在自己 CS
• 进步 (Progress)：无人在 CS 且有人想进时，只有不在剩余区的进程能参与选择，且选择不能无限推迟
• 有限等待 (Bounded Waiting)：从请求到被允许之间，其他进程进入 CS 的次数有上限

Peterson 算法

下面 4 段对应进入区 / CS / 退出区 / 剩余区：

// 共享：boolean flag[2]; int turn;
// 进程 Pi (j = 1-i)
do {
	// --- entry section ---
	flag[i] = TRUE;        // 我想进
	turn = j;              // 礼让对方
	while (flag[j] && turn == j) ;  // 忙等

	/* --- critical section --- */

	// --- exit section ---
	flag[i] = FALSE;

	/* --- remainder section --- */
} while (TRUE);

三要求证明：

• 互斥：两人都过 while 需 flag[j]==FALSE 或 turn != j；两人都设了 flag[i]=TRUE，所以全靠 turn，而 turn 不可能同时等于 0 又等于 1 → 矛盾
• 进步：若 $P_0$ 想进而 $P_1$ 不想（flag[1]==FALSE），$P_0$ 的 while 立即通过
• 有限等待：$P_1$ 退出后 flag[1]=FALSE，$P_0$ 立即可进；$P_1$ 想再进会先 turn=0 礼让 → $P_0$ 至多等 $P_1$ 一次

现代 CPU 重排指令，Peterson 在硬件上正确需配 memory barrier

互斥锁与信号量

• 互斥锁 (mutex)：acquire() / release()，二元
• 信号量 (semaphore)：整型 $S$ + 两原子操作
  • wait(S) / P(S)：$S$ 减 1，若 $S<0$ 阻塞
  • signal(S) / V(S)：$S$ 加 1，若 $S\le 0$ 唤醒一个等待者
• 分类：
  • 二进制信号量：取 0/1，类似 mutex
  • 计数信号量：可大于 1，控制 $n$ 个同类资源并发

硬件类比：信号量 = 令牌计数器；wait 取令牌，signal 还令牌；耗尽则排队

信号量阻塞实现

typedef struct {
	int value;
	struct process *list;
} semaphore;

wait(S) {
	S->value--;
	if (S->value < 0) {
		add this process to S->list;
		block();
	}
}

signal(S) {
	S->value++;
	if (S->value <= 0) {
		remove a process P from S->list;
		wakeup(P);
	}
}

• $|S|$（当 $S<0$）= 等待队列长度
• 避免忙等

信号量三种用法

• 互斥：初值 1，wait; CS; signal;
• 同步顺序（A 先 B 后）：初值 0，A 末尾 signal，B 开头 wait
• 有限资源：初值 $n$，wait 占用一个、signal 归还一个

经典：生产者-消费者

semaphore mutex=1, empty=N, full=0;

// Producer
wait(empty); wait(mutex);
add item;
signal(mutex); signal(full);

// Consumer
wait(full); wait(mutex);
remove item;
signal(mutex); signal(empty);

注意

顺序必须 wait(empty/full) 先于 wait(mutex)！反之死锁：消费者拿到 mutex 却等 full=0，生产者拿不到 mutex 永远不能 signal(full)。

硬件类比：环形缓冲 = 硬件 FIFO 配 full/empty 信号线

死锁

定义

• 一组阻塞进程，每个持有部分资源 且 等待该组中其他进程持有的资源
• 典型：两个磁盘 $P_1$、$P_2$ 各占一个且各需另一个
• 信号量交叉 wait（持 S 等 Q vs 持 Q 等 S）同理

四个必要条件

四条同时成立才会死锁：

• 互斥 (Mutual Exclusion)：至少一种资源非共享模式
• 占有并等待 (Hold and Wait)：进程持有至少一个资源同时等待其他
• 非抢占 (No Preemption)：资源不能被抢占
• 循环等待 (Circular Wait)：存在等待环 $P_0 \to P_1 \to \cdots \to P_n \to P_0$

三种处理策略

• 预防 (Prevention)：破坏四条件之一
• 避免 (Avoidance)：利用先验信息（Max），动态保持安全状态
• 检测 + 恢复：允许发生，事后处理
• 鸵鸟：忽视，重启了事（多数实际 OS 选这条）

预防——破坏四条件

• 互斥：天然必须，难破
• 占有并等待：一次申请全部 / 申请前先释放；缺点利用率低、可能饥饿
• 非抢占：申请失败则隐式释放已持有；适合 CPU/寄存器，不适合打印机
• 循环等待：全局编号资源，按递增顺序申请

安全状态

• 系统能按某顺序为每进程分配资源（不超 Max）仍不死锁 → 安全
• 存在安全序列 $\langle P_1, \ldots, P_n \rangle$，对每个 $P_i$：

$P_i \text{ 剩余需求} \le \text{当前可用} + \sum_{j<i} \text{Allocation}(P_j)$

• 包含关系：死锁 ⊂ 非安全 ⊂ 所有状态
• 安全 → 一定不死锁；非安全 ↛ 必死锁

银行家算法

适用多实例资源；每进程预声明 Max；进程获取所有资源后须有限时间内释放。

数据结构（$n$ 进程、$m$ 资源类型）：

• Available[m]：当前可用资源向量
• Max[n][m]：每进程最大需求
• Allocation[n][m]：当前已分配
• Need[n][m] = Max - Allocation

安全性算法

Work = Available;  Finish[*] = false

loop:
	找 i: Finish[i] == false 且 Need[i] <= Work
	若有: Work += Allocation[i]; Finish[i] = true; 继续
	若无: 退出

若所有 Finish[i] == true → 安全，记录到的 i 顺序即安全序列

资源请求算法

检查 Request[i] <= Need[i]    // 否则报错（超声明）
检查 Request[i] <= Available  // 否则等待

试分配：
	Available     -= Request[i]
	Allocation[i] += Request[i]
	Need[i]       -= Request[i]

跑安全性算法：
	safe   → 正式分配
	unsafe → 撤销试分配，等待

检测算法

• 多实例：类似安全性算法，但用 Request 代替 Need
• Finish[i] 初始：Allocation[i] == 0 的为 true
• 安全性 vs 检测：前者事前预防用 Need，后者事后判定用 Request

恢复

• 进程终止：全杀 / 逐杀
• 资源抢占：选牺牲者（成本函数）→ 回滚（完全/部分）→ 防饥饿（被选次数计入成本）

内存管理

基础

逻辑地址 vs 物理地址

• 逻辑地址 (虚拟地址)：CPU 生成的地址
• 物理地址：内存单元看到的地址
• 运行时映射由 MMU（内存管理单元）硬件完成
• 用户程序永远看不到真实物理地址

朴素方案：连续分配

• 每个进程占一整块连续物理内存
• 基地址寄存器 (base)：进程的最小合法物理地址
• 界限地址寄存器 (limit)：合法范围大小
• 合法范围 $[\text{base}, \text{base}+\text{limit})$，越界 trap
• 简单 MMU = 重定位寄存器：$\text{PA} = \text{LA} + \text{base}$
• 只有 OS 通过特权指令改 base/limit；进程切换时由 OS 从 PCB 加载

适配算法

可变分区时 OS 维护"孔 (hole)"列表。来了一个 $n$ 字节请求怎么分：

• 首次适应 (First Fit)：扫分区列表，第一个 $\ge n$ 的就分
• 最优适应 (Best Fit)：遍历找最小但够用的；产生最小剩余孔
• 最差适应 (Worst Fit)：遍历找最大的；产生最大剩余孔
• 题型：给若干分区和按序到达的进程，三种算法分别放置 → 看谁能放下最多 → 排效率
• 经验排序：首次 ≈ 最优 > 最差

碎片

• 外部碎片：总空闲足够但不连续（可变分区反复分配/释放产生）
• 内部碎片：分配块 > 实际需要（固定分区、分页最后一页）
• 50% 规则：$N$ 个已分配块 → 约 $0.5N$ 个外部碎片块 → 约 $1/3$ 内存不可用
• 紧缩 (compaction) 消除外部碎片：移动进程合并空闲孔；需运行时绑定，代价大

分段、分页都是为了缓解碎片：分段把整块切成几段（仍有外部），分页彻底切成等大小块（消灭外部，只剩内部）

分段

动机

• 程序天然由若干逻辑段组成：代码段、数据段、栈、堆、各子程序
• 连续分配把整个程序当一整块；分段允许把不同段分别放到物理内存的不同位置
• 贴近程序员视角

地址格式与段表

• 逻辑地址二维：$(s, d)$，$s$ = 段号，$d$ = 段内偏移
• 段表：每条记录一段的 (base, limit)
• 翻译流程：
  • 用 $s$ 索引段表，取出 $(\text{base}_s, \text{limit}_s)$
  • 若 $d < \text{limit}_s$：$\text{PA} = \text{base}_s + d$
  • 否则越界 trap
• 每段可独立设置保护位（如代码段只读+可执行、数据段可读写）

优缺点

• 优：贴近用户视角；段粒度保护与共享自然
• 缺：段大小不一 → 仍有外部碎片

分页

动机

• 彻底消灭外部碎片：物理和逻辑都切成等大小块
• 不再要求连续分配 → 任何空闲帧都可用
• 代价：仍有少量内部碎片（最后一页未填满，最多浪费 1 页）

页与帧

• 页 (page)：逻辑内存的固定大小块
• 帧 (frame)：物理内存的固定大小块
• 页大小 = 帧大小 = $2^n$ 字节（典型 4 KB）
• 大小相等才能让任意页放进任意帧
• 页表 (page table)：每进程一张，把逻辑页号映射到物理帧号

地址格式与翻译

逻辑地址空间 $2^m$，页大小 $2^n$：

$\text{LA} = \underbrace{p}_{m-n\ \text{位（页号）}} \mid \underbrace{d}_{n\ \text{位（页内偏移）}}$

• $p = \lfloor \text{LA}/2^n \rfloor$（高位）
• $d = \text{LA} \bmod 2^n$（低位）
• 查页表得帧号 $f = \text{PageTable}[p]$
• $\boxed{\text{PA} = f \times 2^n + d}$

页内偏移 $d$ 不变穿过翻译——只有页号 $p$ 被换成帧号 $f$。

解题步骤

• 把逻辑地址转 $m$ 位二进制
• 高 $(m-n)$ 位为页号 $p$，低 $n$ 位为偏移 $d$
• 查页表得 $f$
• 物理地址按公式 $f \times 2^n + d$，或直接拼接 $f$ 的二进制与 $d$

易错：高几位是页号、低几位是偏移；别把页大小 $2^n$ 错算成 $n$

TLB 与 EAT

• 朴素分页需 2 次访存（查页表 + 取数据）
• TLB (Translation Lookaside Buffer)：硬件关联存储器，缓存最近 $(p \to f)$ 映射
• 命中率 $\alpha$ 时：

$EAT = \alpha \beta + (1-\alpha) \cdot 2\beta = (2-\alpha)\beta$

• $\beta$ = 一次内存访问时间
• 含 TLB 时间 $\epsilon$：$EAT = \alpha(\epsilon+\beta) + (1-\alpha)(\epsilon+2\beta)$
• 共享页：可重入代码（只读、不自修改）多进程指向同一帧

分段 vs 分页

对比	分段	分页
大小	可变	固定 $2^n$
用户可见	是	否
地址格式	$(s, d)$	$(p, d)$
外部碎片	有	无
内部碎片	无	有（最后一页）

多级页表

动机

• 32-bit + 4KB 页 → 单级页表 $2^{20}$ 项 × 4B = 4 MB / 进程，浪费严重
• 进程地址空间通常稀疏（很多页根本没用）
• 多级页表：对页表自身再分页，未使用的子表不分配

二级页表格式

逻辑地址按位切三段，高位是 $p_1$：

$\text{LA} = \underbrace{p_1}_{\text{一级索引}} \mid \underbrace{p_2}_{\text{二级索引}} \mid \underbrace{d}_{n\ \text{位（页内偏移）}}$

翻译流程：

• $p_1$ 索引一级页表 → 得对应二级页表的基址（或"该子表未分配"标志）
• $p_2$ 索引该二级页表 → 得帧号 $f$
• $\text{PA} = f \times 2^n + d$

解题步骤

• 把逻辑地址转 $m$ 位二进制
• 按 $(p_1, p_2, d)$ 位数切分
• $p_1$ 查一级页表 → 决定看哪张二级页表
• $p_2$ 查该二级页表 → 取帧号 $f$
• 物理地址按公式

$k$ 级页表 → $k+1$ 次访存（TLB 缓解）

其他页表结构（了解）

• 哈希页表：$(p, f, \text{next})$ 链表，处理冲突；大地址空间用
• 反向页表：全系统一张，每物理帧一条 $(\text{pid}, p)$；空间小，需 (pid, p) 联合搜索，哈希加速

内存换入

虚拟内存动机

• 背景：程序变大、内存不够；直接在磁盘上跑太慢（金字塔存储层次）
• 目标：
  • 程序可大于物理内存——突破物理内存大小限制
  • 多用户/多进程共享物理内存——同时跑多个程序，提升 CPU 利用率和吞吐
  • 实际内存对用户透明——把内存抽象成"统一巨大数组"，简化编程
  • 加载更快——只调入需要的部分（懒加载）
• 实现手段：逻辑内存 / 物理内存分离，由 MMU（硬件）做地址映射，请求调页做按需装入
• 段页结合：上层分段（贴用户视角，按代码/数据/栈划分），下层把每段分页存到物理内存（消外部碎片）
• 关键效果：虚拟内存可以大于物理内存——靠"内存中只放当前用的页 + 磁盘 swap 存其余"实现

类比：虚拟内存 = 给每个进程一张"假的大内存地图"，MMU + 调页机制让映射动态生效

Valid / Invalid 位

页表每项有一位 valid bit，区分这一页能否直接访问：

• valid (v)：页面合法且已在内存——可直接翻译访问
• invalid (i)：两种情况合并：
  • 页面不在进程逻辑地址空间（非法地址）→ 访问 → trap → 进程终止
  • 页面合法但只在磁盘（被换出或没调入）→ 访问 → 缺页错误 (page fault) → 调入

设计上把"非法"和"在磁盘"用同一位标记，是因为两者都需要 trap 到内核，由内核查 PCB 进一步区分

按需调页（Demand Paging）

• 进程启动时不把整个程序加载进内存，只在访问到某页时才把它从磁盘调入（lazy / 惰性调用）
• 对比"全部加载"：
  • 全部加载：浪费空间、装入慢、未必用得到所有页
  • 按需调页：只占当前用的帧 → 多道度更高 → 吞吐量更高
• 触发条件：访问的页 valid 位 = i 且合法（在进程逻辑空间内）→ 缺页错误

缺页错误处理 7 步

必考简答：完整背下这 7 步

• trap 到内核——MMU 发现 valid=i，触发缺页中断
• 保存用户寄存器与进程状态——和普通中断一样要保现场
• 查进程内部表（通常与 PCB 一起保存），判断该引用是合法还是非法
  • 非法 → 终止进程
  • 合法但只在磁盘 → 继续
• 找一个空闲帧——从空闲帧链表取一个；若没有 → 触发页面置换
• 调度磁盘 I/O，将所需页面读入刚分配的帧
• 修改进程内部表和页表：填入帧号，valid 位置 v
• 重启被中断的指令——进程继续，仿佛该页一直在内存

关键："重启指令"很重要——缺页发生在指令执行中途，恢复后需要从头重跑那条指令

空闲帧列表与按需零填充

• OS 维护一个空闲帧列表 (free frame list)：所有可分配的物理帧池
• 系统启动时所有可用内存都进列表
• 按需零填充 (zero-fill on demand)：帧分配前先清零
  • 防泄漏：避免新进程读到上一个进程留在帧里的数据
  • "按需"：只在分配那一刻清，不预先清

有效访问时间

$EAT = (1-p) \cdot t_{\text{mem}} + p \cdot t_{\text{fault}}$

• $p$ = 缺页概率，$t_{\text{mem}}$ = 内存访问时间，$t_{\text{fault}}$ = 缺页处理时间
• 缺页处理时间三大块：处理中断 + 读入页面（磁盘 I/O 主导）+ 重启进程
• 典型量级：$t_{\text{mem}} \approx 200$ ns，$t_{\text{fault}} \approx 8$ ms = $8\times 10^6$ ns
• 例：$p = 10^{-3}$（千分之一缺页）→ $EAT \approx 0.999 \times 200 + 10^{-3} \times 8\times 10^6 \approx 8200$ ns，比纯内存慢 40 倍
• 缺页率 $p$ 必须降到 $\sim 10^{-6}$ 量级 EAT 才接近原速

EAT 与缺页率线性正相关——靠局部性把 $p$ 压到极低

写时复制（COW）

• fork() 后父子共享物理页，全部标记 COW（只读）
• 任一方写时触发保护错误 → OS 真正复制那一页 → 改回可写
• 配合 exec()（立刻替换地址空间）几乎零拷贝

内存换出

基本页面置换流程

缺页且无空闲帧时，把原 7 步缺页处理改为：

• 找到所需页面的磁盘位置
• 找一个空闲帧：
  • 有 → 用
  • 无 → 跑页面置换算法选 victim 帧
• 处理 victim：
  • 写回磁盘（仅当脏）
  • 修改对应页表（把 victim 的 valid 改为 i）
• 将所需页面读入空闲帧；修改页表（把目标页 valid 改为 v）
• 从缺页位置继续用户进程

若 victim 是脏页，本次缺页要做 2 次磁盘传输（一调入 + 一调出），访问时间翻倍——这是脏位优化的动机

脏位（dirty bit / 修改位 modify bit）

• 每个页表项有一位 dirty bit
• 页面被写入时由硬件自动置 1
• 页面只被读、未被修改 → dirty = 0
• 置换时检查脏位：
  • dirty = 1（脏页）→ 内存与磁盘内容不一致 → 必须写回磁盘，再丢弃
  • dirty = 0（干净页）→ 磁盘里已有相同副本 → 直接丢弃，省掉写回 I/O
• 效果：理论上降低一半 I/O 时间（无写回的情况下）

类比：脏位 = cache 的 dirty bit，思想完全一致——只有被改过的才要写回

脏位的两个用途

脏位不只是置换时省 I/O，增强二次机会算法也用它：

• 与引用位组成 (ref, dirty) 二元组，分四档优先级置换
• (0,0) 最佳：最近没用且没改 → 替换零成本
• (0,1)：没用但改过 → 要写回
• (1,0)：近期用过但没改 → 留着，可能再用
• (1,1) 最差：近期用过且改过 → 既贵又有用
• 给已修改页面更高保留优先级，进一步降低 I/O 频率

FIFO

• 选最早进入内存的页置换
• 实现：维护进入顺序队列
• 可能 Belady 异常

OPT (MIN)

• 选未来最长时间不会使用的页
• 理论下界，不可实现（需未来信息）
• 用作基准比较

LRU

• 选最近最长未使用的页
• 用过去近似未来（局部性原理）
• 实现：
  • 计数器：每次访问写时间戳；置换时找最小
  • 栈：访问页移到栈顶；栈底为 LRU
• 硬件代价高，纯 LRU 罕见，多用近似

缺页计算

• 给引用串和帧数，分别算 FIFO / OPT / LRU 缺页次数
• 做法：画表格，每列一次引用，每行一帧，逐步填入，标缺页
• 第一次出现一定缺页（首次填入空帧）
• 未命中时按算法选 victim：
  • FIFO：换最早进入的
  • LRU：往左看最远未访问的
  • OPT：往右看未来最远访问的，永不再出现的优先

Belady 异常

• 现象：用 FIFO 时增加帧数反而缺页增加
• 原因：FIFO 只看进入时间，不考虑未来访问；增加帧数后可能错误保留了不会再用的页、错误替换即将访问的页
• 经典反例引用串：1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5，3 帧 vs 4 帧
• 只在 FIFO 发生；LRU / OPT 等栈算法不会

LRU 近似

真正的 LRU 需要硬件时钟或全栈维护，代价大。实践中用引用位近似：

• 引用位 (reference bit)：每页一位，访问时硬件置 1，OS 周期性清零
• 额外引用位算法：每页保留 8 位移位寄存器，每个时钟周期右移 1 位并把引用位写最高位
  • 00000000 → 8 周期内未用
  • 把寄存器当无符号数，值最小的页被替换（如 01110111 < 11000100 → 前者更早冷下来）
• 二次机会 / Clock 算法：FIFO + 引用位
  • 选中 victim 时检查引用位
  • =0 → 直接替换
  • =1 → 清 0，给"第二次机会"，跳到下一页继续找
  • 若所有引用位都是 1 → 退化为纯 FIFO（绕一圈把所有位清 0）
• 增强二次机会：(ref, dirty) 二元组优先级 $(0,0)>(0,1)>(1,0)>(1,1)$（见上节脏位的两个用途）

基于计数的页面置换

为每页保留引用次数计数器：

• LFU（Least Frequently Used）最不经常使用：换计数最小的页——历史上很少用，未来也大概率不用
• MFU（Most Frequently Used）最经常使用：换计数最大的页——基于"计数小的可能是刚调入还没用够"的论点
• 实践中两者都不如 LRU 近似常见

帧分配策略

固定数量帧如何分给多个进程？

• 平均分配：每进程 $m/n$ 帧——简单但有些进程用不完，浪费
• 比例分配：按进程地址空间大小比例分——未考虑优先级
• 基于优先级：优先级高的分更多帧，加快执行

全局置换 vs 局部置换

• 全局置换：进程可从所有帧池里选 victim（甚至抢别人的帧）
  • 灵活、动态调整、可能因偶发高峰扩张
  • 可能引发系统抖动（一个进程抢光别人的帧）
• 局部置换：每个进程只在自己分到的帧里选 victim
  • 抖动局限在单进程内，不波及其他

抖动 (Thrashing)

• 进程换页时间 > 执行时间
• 死循环：多道度↑ → 帧不足 → 缺页↑ → CPU 利用率↓ → 调度器再加进程 → 更糟
• 解：局部置换 / 工作集策略 / PFF 控制 / 降低多道度

存储管理

磁盘

结构

• 盘片 (platter) → 磁道 (track) → 扇区 (sector，读写最小单位) → 柱面 (cylinder) → 磁头 (head)
• 所有磁头随磁臂一起径向移动

访问时间

$T_{\text{access}} = T_{\text{seek}} + T_{\text{rot}} + T_{\text{transfer}}$

• $T_{\text{seek}}$（寻道）：磁臂移动到目标磁道，最耗时
• $T_{\text{rot}}$（旋转）：等扇区转到磁头下；平均 = 半圈 = $\dfrac{30}{\text{RPM}}$ 秒
• $T_{\text{transfer}}$（传输）：数据从盘面传到控制器
• 优化核心：减少寻道次数和距离

调度算法

算法	思路	饥饿
FCFS	来什么顺序就什么顺序	否
SSTF	每次选离当前磁头最近的请求	可能
SCAN（电梯）	单向到物理边界再反向	否
C-SCAN	到边界跳回另一端继续单向扫	否
LOOK	SCAN 但只到最远请求就反转	否

• SSTF 优化总寻道但可能饿远端请求
• SCAN 两端等待不均；C-SCAN 等待更均匀
• LOOK 是 SCAN 的实际改进：不浪费到物理边界
• 解题：给请求队列和起点，按算法规则写出访问顺序，算总移动距离

文件系统

文件属性与操作

• 属性：name / type / size / location / protection / time / owner / identifier
• name 在目录条目，不在 inode
• 操作：create / write / read / reposition (seek) / delete / truncate / open / close
• 打开文件表：系统级（磁盘位置、计数）+ 每进程级（fd、文件指针、权限）
• 文件描述符 (fd)：每进程表中的索引

目录结构

• 单级：名冲突、无分组
• 两级：每用户一目录；跨用户访问 user/file
• 树形：CWD、绝对/相对路径
• 无环图 (DAG)：共享文件 → 硬链接（多目录条目指同 inode，引用计数）vs 符号链接（特殊文件存路径）
• 通用图：可能成环，垃圾回收难，常禁链接到目录

文件分配方法（总览）

文件如何在磁盘上占块？三种基本方案 + 一种组合：

方法	目录条目	优	缺
连续分配	(起始块, 长度)	顺序快、直接访问	外部碎片、扩展难、需预知大小
链式分配	(首块, 尾块)	无外部碎片、易扩展	只能顺序、指针占空间、单链断 = 全断
FAT	首块号	链式改进，FAT 表驻内存支持随机访问	表本身占空间
索引分配	索引块号	直接访问、无外部碎片	小文件浪费索引块、单索引块限文件大小
组合（inode）	inode	综合优点	略复杂

衡量指标：存储利用率（碎片）+ 访问表现（顺序/随机速度）

连续分配

• 每个文件占磁盘上一组连续的块
• 目录条目：(start, length)——只需起始块号和长度
• 优点：
  • 顺序访问极快：一路读下去，磁头几乎不动
  • 支持直接访问：第 $i$ 块物理地址 = start + i
• 缺点：
  • 外部碎片——反复创建/删除留下大量小空洞
  • 文件扩展难——后面的块可能已被其他文件占；要扩 → 整体移动
  • 需预知文件大小——开多大都尴尬
• 适用：只读文件（CD-ROM、归档）

链式分配

• 每个文件 = 散落各处的磁盘块链表
• 目录条目：(首块号, 尾块号)；每个块内含指向下一块的指针
• 优点：
  • 无外部碎片——任意空闲块都能用
  • 创建/扩展/缩短都容易——改指针即可
• 缺点：
  • 只能顺序访问——找第 $i$ 块必须从首块一路链下去
  • 指针占空间——每块挤掉若干字节给指针
  • 可靠性差——指针坏一块、整个文件链断在那里

FAT（File Allocation Table，文件分配表）

链式分配的关键改进，MS-DOS / FAT16 / FAT32 用此方案

• 思想：把所有"下一块"指针集中存到磁盘开头的一张表里，不再分散到每块尾
• 数据结构：
  • FAT 表：每个磁盘块对应一项，按块号索引，内容是该块在文件链中的下一块号（或"文件结束"标志 EOF / "空闲"标志）
  • 目录条目：只记首块号
• 访问流程：
  • 磁头读到 FAT 表（启动时常驻内存）
  • 从目录拿首块号 → 在 FAT 中查 → 得第 2 块号 → 再查 → ... → 直到 EOF
  • 磁头只需移动一次到目标数据块
• 关键优势：
  • 支持随机访问——FAT 在内存里链遍历几乎免费，定位第 $i$ 块只需一次磁盘 I/O
  • 比传统链式的"每读一块走一次磁盘"快得多
• 缺点：
  • FAT 表本身占空间——磁盘越大表越大；要常驻内存
  • 表损坏 = 整个文件系统瘫痪 → 通常存两份冗余

类比：传统链式 = 链表（每节点带 next 指针）；FAT = 索引数组（用数组下标 + 下一项 ID 模拟链表，整张表常驻内存——查表 O(1)，磁盘 I/O 只为读数据）

索引分配

• 每文件一个索引块：磁盘块地址数组
• 目录条目：索引块号
• 创建时索引指针全置 NULL
• 第 $i$ 次写入第 $i$ 块时，从空闲管理器拿一块，地址写到索引块第 $i$ 项
• 直接访问：数据块 = 索引块[i]
• 优点：
  • 支持随机访问
  • 无外部碎片
• 缺点：
  • 每个文件都要占一整块索引——小文件浪费严重
  • 单索引块限文件最大尺寸——块装得下多少指针，文件就最多多少块
• 解决最大尺寸限制：
  • 链式索引块：多个索引块串成链（每个索引块末尾指针指向下一个索引块）
    • 缺点：仍是顺序遍历索引块、可靠性差
  • 多级索引块（类似多级页表）：第一级指向第二级
    • 缺点：访问多级才能找到数据块、增加 I/O
  • 组合方案：综合上述——UNIX inode 即采用

UNIX inode 组合方案

• inode 含 15 个指针：
  • 前 12 个：直接块，直接指向数据块（小文件不需要多级索引）
  • 第 13 个：一级间接 → 块存 $B/P$ 个数据块指针
  • 第 14 个：二级间接 → 块存 $B/P$ 个一级间接块指针
  • 第 15 个：三级间接 → 块存 $B/P$ 个二级间接块指针
• $B$ = 块大小（字节），$P$ = 指针大小（字节）

最大文件大小：

$\text{Max} = \left(12 + \frac{B}{P} + \left(\frac{B}{P}\right)^2 + \left(\frac{B}{P}\right)^3\right) \cdot B$

这种"小文件直接访问、大文件多级间接"的分级思路是 UNIX 文件系统的核心，与多级页表设计动机一致——常用情况一步到位、稀有情况多走几步

inode 框图解题要点

• 给块大小 $B$、指针大小 $P$ → 每间接块容量 $B/P$ 个指针
• 给"可用块从 X 开始按顺序分配，坏块跳过"
• 分阶段画框图（如原始 3 块 → 加 7 → 加 24 → 加 64）：
  • 先填 12 个直接指针对应的数据块
  • 满 12 后启用一级间接：先分配一个间接块，再依次填其指针
  • 满后启用二级间接：先分一个二级块、再为它分一级间接块、再分数据块
  • 三级同理
• 三处易错：
  • 间接块本身要占磁盘块号（也是从可用块取）
  • 坏块要跳过
  • 每张间接块只容 $B/P$ 个指针

空闲空间管理

• 位图：每块 1 bit，0 = 空闲；硬件指令快速找第一个 0
• 链表：所有空闲块串成链；简单但遍历慢
• 分组：第一空闲块存 $n-1$ 个空闲块号 + 下组首
• 计数：存 (起始块号, 连续空闲数)；连续时极省

高速缓存与 I/O

缓冲 vs 缓存

• 缓冲 (Buffer)：在生产者-消费者之间，做速度匹配 / 大小适配；可能是数据唯一存储
• 缓存 (Cache)：已有数据的副本，加速访问
• 文件系统 buffer cache：内存中缓存最近用过的磁盘块

I/O 设备分类

• 块设备：固定块、可随机访问；接口 read/write/seek；磁盘
• 字符设备：流式、不可寻址；接口 get/put；键盘、鼠标
• 速度差异跨 $10^6$ 量级（键盘 $\sim 0.01$ KB/s ↔ PCIe $\sim 100$ GB/s）

数据传输方式

方式	CPU 介入	适用
轮询 (PIO)	全程忙等读状态位	短传输
中断驱动	每字节中断一次	中速少量
DMA	仅启动 + 完成时中断	大块数据

• DMA 控制器代 CPU 在设备和内存间搬运数据
• DMA 期间 CPU 可同时用 cache 做其他事
• 高速设备反而用轮询：中断频率太高，开销大于轮询

I/O 软件层次（自上而下）

• 用户空间 I/O 库（stdio）
• 设备无关 OS 软件（命名、保护、缓冲、错误）
• 设备驱动
• 中断处理程序
• 硬件

I/O 保护

• 所有 I/O 指令是特权指令
• 用户必须通过系统调用陷入内核 → OS 检查合法性 → 代为执行

知识性简答题速答

期末常见简答题——给出问题与答案要点，对照背诵；详细机制见前文对应章节

进程与通信

Q：操作系统为何允许进程协作？列出 IPC 两种模型

• 协作原因（4 条）：
  • 信息共享：多进程访问同一份数据（共享文件）
  • 计算加速：单任务拆给多进程，多核并发跑
  • 模块化：把系统功能划成不同进程，独立开发部署
  • 方便：单用户多任务（编辑器 + 编译器 + 播放器同开）
• IPC 两种模型：
  • 共享内存 (Shared Memory)：进程把同一段物理内存映射进各自地址空间，靠读写公共变量交换信息
  • 消息传递 (Message Passing)：靠 send(message) / receive(message) 两个原语，不共享地址空间

Q：共享内存与消息传递如何对比？

维度	共享内存	消息传递
速度	快，用户态读写	慢，每次进出内核
数据量	大块数据合适	适合少量数据交换
同步	要自己处理冲突（信号量）	天然同步、收发即同步
多核场景	高速缓存一致性开销	多核反而更好
分布式	不支持跨机	天然支持跨机

Q：消息传递的直接通信 vs 间接通信？

• 直接通信：send(P, msg) / receive(Q, msg)——必须明确指定对方身份
  • 每对进程自动建立链路；一对一
• 间接通信：通过邮箱/端口——send(A, msg) / receive(A, msg)
  • 只要共享邮箱即可；可多对多

Q：阻塞 vs 非阻塞消息传递？

• 阻塞发送：发送进程停下来等接收方收到才继续（同步）
• 非阻塞发送：把消息扔出去立刻返回（异步）
• 阻塞接收：没消息就睡，有消息才醒
• 非阻塞接收：返回有效消息或空消息

Q：上下文切换需要做什么？描述步骤

• 响应时钟中断：OS 保存当前进程的 PC 和用户栈指针，控制权转给内核中断处理程序
• 保存其他寄存器和机器状态（通用寄存器、浮点、PSW）到当前进程 PCB
• 调用调度器选下一个要执行的进程
• 从新进程 PCB 中恢复寄存器状态和 PC，返回用户态继续执行
• 关键：切换是纯 overhead，涉及用户态↔内核态切换

Q：并发与并行的区别？

• 并行 (Parallel)：多任务在物理上同时执行，需多核
• 并发 (Concurrent)：多任务逻辑上同时推进，单核时间片即可
• 关系：可以并发但无并行（单核时间片轮转），并行一定并发

Q：用户级线程 vs 内核级线程？

	用户级	内核级
管理者	用户线程库	内核
切换	用户态，快	系统调用，慢
内核可见	否	是
单线程阻塞	整个进程阻塞	仅该线程阻塞
多核并行	不行	可以

同步与死锁

Q：临界区程序需要满足哪三个要求？

• 互斥 (Mutual Exclusion)：任一时刻最多一个进程在临界区
• 进步 (Progress)：无人在 CS 且有人想进时，只有不在剩余区的进程参与选择，且选择不能无限推迟
• 有限等待 (Bounded Waiting)：从请求到允许之间，其他进程进入 CS 的次数有上限

Q：Peterson 算法如何保证互斥？

• 两人都过 while(flag[j] && turn == j) 需要 flag[j]==FALSE 或 turn != j
• 两人都设了 flag[i]=TRUE，所以只能靠 turn
• 但 turn 不可能同时等于 0 又等于 1 → 矛盾，故不能两人同时进 CS

Q：生产者-消费者为何 wait(empty) 要在 wait(mutex) 之前？

• 反过来 wait(mutex); wait(empty); 时：
  • 消费者拿到 mutex 后等 full=0 阻塞
  • 生产者拿不到 mutex 永远 signal 不了 full
  • → 死锁
• 正序保证"先确认资源可用，再竞争互斥"

Q：死锁的四个必要条件？

四条同时成立才会死锁（破坏任一即可避免）：

• 互斥 (Mutual Exclusion)：至少一种资源非共享
• 占有并等待 (Hold and Wait)：持有部分资源且等待更多
• 非抢占 (No Preemption)：已分配资源不能强行剥夺
• 循环等待 (Circular Wait)：存在等待环 $P_0 \to P_1 \to \cdots \to P_n \to P_0$

Q：银行家算法与检测算法的区别？

• 银行家（避免）：事前——拿 Need 跑安全性算法，预判分配后是否安全
• 检测（事后）：事后——拿 Request 跑类似算法，找现存的死锁进程
• 都用类似的"找可完成进程 → 释放资源 → 继续"循环
• 关键差别：用 Need 还是 Request

内存与虚拟内存

Q：什么是虚拟内存？有什么作用？

• 虚拟内存：把进程的逻辑地址空间与物理内存分离，由 MMU 硬件做映射，磁盘做后备存储
• 作用（4 点）：
  • 程序可以大于物理内存
  • 多进程共享物理内存，提高 CPU 利用率
  • 实际内存对用户透明，简化编程
  • 加载更快（按需调页）

Q：什么是请求调页？为什么用它？

• 请求调页 (Demand Paging)：进程启动时不全部加载，只有访问到某页才调入（lazy）
• 对比"全部加载"：避免空间浪费 + 提升多道度 + 启动快
• 实现：靠valid/invalid 位——访问 invalid 页触发缺页错误

Q：缺页错误的处理步骤？

• trap 到内核——MMU 发现 valid=i
• 保存用户进程状态
• 查 PCB 判合法性——非法 → 终止进程
• 找空闲帧——无空闲 → 跑页面置换选 victim
• 磁盘 I/O 读入页面到帧
• 更新页表——填帧号、置 valid=v
• 重启被中断的指令——进程继续

Q：什么是 Belady 异常？哪些算法有？

• 现象：增加帧数反而缺页增加（违反直觉）
• 经典反例：引用串 1,2,3,4,1,2,5,1,2,3,4,5，3 帧 vs 4 帧
• 仅 FIFO 出现；LRU、OPT 等栈算法不会
• 原因：FIFO 只看进入顺序，不考虑未来访问，增加帧后可能保留了没用的页

Q：什么是抖动？原因？如何缓解？

• 抖动 (Thrashing)：进程的换页时间 > 执行时间——CPU 大部分时间在搬页而不是干活
• 死循环：多道度↑ → 每进程帧不足 → 缺页率↑ → CPU 利用率↓ → 调度器再加进程 → 更糟
• 缓解：
  • 局部置换：进程只能换自己的帧，把抖动局限单进程
  • 工作集策略：给进程分够当前局部性所需的帧数
  • PFF 控制：监控缺页率，超阈值则加帧、过低则收帧
  • 降低多道度：换出一个进程，让其余有足够帧

存储与文件系统

Q：磁盘访问时间由哪几部分组成？哪个最耗时？

$T_{\text{access}} = T_{\text{seek}} + T_{\text{rot}} + T_{\text{transfer}}$

• 寻道 $T_{\text{seek}}$：磁臂移到目标磁道——最耗时，优化重点
• 旋转 $T_{\text{rot}}$：等扇区转到磁头下，平均 = 半圈 = $\dfrac{30}{\text{RPM}}$ 秒
• 传输 $T_{\text{transfer}}$：数据从盘面传到控制器

Q：SSTF 为什么可能饥饿？

• SSTF 每次选离当前磁头最近的请求
• 若中部请求持续到达，远端请求永远不被选——饿死
• SCAN/LOOK/C-SCAN 单向扫到底，保证每个请求都被处理，不会饥饿

Q：什么是 inode？它有什么特点？

• inode = 文件元数据 + 索引指针的组合块（UNIX 文件系统核心）
• 内容：
  • 文件类型、大小、权限、时间戳、所有者
  • 15 个磁盘指针：12 直接 + 1 一级间接 + 1 二级间接 + 1 三级间接
• 关键性质：inode 不存文件名——文件名在目录条目里指向 inode 号
• 这样设计才能支持硬链接（多个目录条目指向同一 inode）

Q：文件分配方法有哪几种？各自优缺？

方法	目录条目	优	缺	典型应用
连续	(起始, 长度)	顺序快、直接访问	外部碎片、扩展难	CD-ROM
链式	(首块, 尾块)	无外部碎片、易扩展	只能顺序、指针散布、链断 = 全断	早期系统
FAT	首块号	链式 + 集中表常驻内存 → 支持随机访问	表占空间、表损=全瘫	MS-DOS
索引	索引块号	直接访问、无外部碎片	小文件浪费索引块	—
组合（inode）	inode 号	小文件零开销、大文件支持好	略复杂	UNIX

I/O 系统

Q：什么是直接内存访问 (DMA)？画图解释

• DMA：专用控制器代 CPU 在设备和内存之间直接搬运数据
• 动机：大块数据传输（如读 1MB）若全靠 CPU 搬运（磁盘 → CPU 寄存器 → 内存）会让 CPU 极忙
• 过程 4 步：
  • ① 主机把 DMA 命令块写到内存（含源地址 / 目的地址 / 字节数）
  • ② CPU 把命令块地址写到 DMA 控制器寄存器
  • ③ DMA 控制器取得内存总线控制权，独立完成数据传输
  • ④ 传输完成后 DMA 向 CPU 发中断通知
• DMA 占用内存总线时 CPU 不能用内存，但仍可用 cache 干别的——总体性能提升

DMA 工作示意图：

       ┌─────────┐    ① CPU 配置命令块         ┌─────────┐
       │   CPU   │──────────────────────────►  │ Memory  │
       │         │    (源/目的/大小)            │ 0x1000  │
       └────┬────┘                              └────▲────┘
            │ ② 写 DMA 寄存器                       │
            │                                       │
            ▼                                       │ ③ 直接读写
       ┌─────────┐                                  │   (无 CPU)
       │   DMA   │ ─────────────────────────────────┘
       │  Ctrl   │
       └────┬────┘
            │ 控制设备
            ▼
       ┌─────────┐
       │ Device  │   (Disk / NIC / ...)
       └─────────┘

       ④ DMA 完成 ──── 中断 ───► CPU "数据到了"

期间 CPU 与 DMA 并行：CPU 跑别的程序 + 用 cache；DMA 走总线搬数据

Q：中断机制如何工作？

• CPU 每执行一条指令检测中断请求线 (IRL)
• 检测到信号 → 保存现场到 PCB → 跳到内存固定位置的中断处理程序
• 中断处理程序：
  • 用中断向量号查表找处理函数地址——避免轮询所有设备
  • 执行处理 → 恢复现场 → 返回中断指令
• 优先级机制：高优先级可抢占低优先级；屏蔽 ≠ 永久丢弃，只是延迟
• 也用于异常：除零、缺页、特权指令违例

Q：缓冲 (Buffer) 和缓存 (Cache) 有什么区别？

	缓冲 Buffer	缓存 Cache
角色	生产者-消费者之间的中转站	已有数据的副本
数据	可能是唯一存储	一定有原本
目的	速度匹配、大小适配	加速访问
例	I/O 缓冲区、socket 缓冲区	文件系统 buffer cache、CPU L1

Q：I/O 软件分哪几层？

自上而下（每层只与上下相邻层交互）：

• 用户空间 I/O 库（如 stdio、printf）
• 设备无关 OS 软件（命名、保护、缓冲、统一接口）
• 设备驱动（封装具体设备差异）
• 中断处理程序（响应设备完成信号）
• 硬件（控制器 + 设备）

Q：为什么 I/O 指令必须是特权指令？

• 防止用户进程：
  • 直接访问别人的文件 / 设备
  • 故意发非法 I/O 让系统崩溃
  • 绕过权限检查
• 用户必须经系统调用陷入内核——OS 检查合法性后代为执行

速记

• 进程 = 资源分配；线程 = 调度；同进程线程共享地址空间
• fork 计算 = 数叶子节点
• 并发可单核，并行必多核
• 上下文切换 4 步：保 PC/sp → 存其余寄存器到 PCB → 调度 → 恢复
• 调度准则：CPU 利用率、吞吐量、周转、等待、响应
• 5 大冲突：响应 vs 利用率 / 平均周转 vs 最大等待 / I/O 设备 vs CPU
• 6 算法：FCFS / SJF / SRTF / 优先级 / RR / MLFQ
• 临界区三要求：互斥 / 进步 / 有限等待
• Peterson 互斥证明：turn 不能同时等于 0 和 1
• 信号量 wait 顺序：先 wait(empty/full) 再 wait(mutex)
• 死锁四条件：互斥 / 占有等待 / 非抢占 / 循环等待
• 安全 ⊂ 无死锁；银行家用 Need、检测用 Request
• 适配算法效率：首次 ≈ 最优 > 最差
• 50% 规则：N 个已分配 → 约 0.5N 个外部碎片块
• $\text{PA} = f \times 2^n + d$；多级页表高位是 $p_1$
• $EAT_{\text{TLB}} = (2-\alpha)\beta$；$EAT_{\text{缺页}} = (1-p) t_{\text{mem}} + p \cdot t_{\text{fault}}$
• 缺页 7 步：trap → 存状态 → 检查 → 取帧 → 读盘 → 改页表 → 重启指令
• 虚拟内存大于物理内存：靠 valid 位 + 请求调页 + 磁盘 swap
• 脏位 = 写过 → 置换时必须写回；干净页丢弃，省一半 I/O
• 增强二次机会：(0,0)>(0,1)>(1,0)>(1,1)
• 全局置换可能抖动；局部置换隔离单进程
• Belady 仅 FIFO
• OPT 不可实现；LRU 用过去近似未来
• SSTF 可饥饿；SCAN / LOOK 不会
• $T_{\text{access}} =$ 寻道 + 旋转 + 传输；平均旋转 = $30/\text{RPM}$
• 文件分配：连续（外部碎片，难扩）/ 链式（顺序，指针散在每块）/ FAT（链式+集中表常驻内存，支持随机访问，MS-DOS 用）/ 索引（每文件一索引块）/ inode 组合
• UNIX inode：12 直接 + 一级 + 二级 + 三级；不存文件名
• 最大文件 $(12 + B/P + (B/P)^2 + (B/P)^3) \cdot B$
• 缓冲 = 可能唯一存储；缓存 = 副本
• DMA 只在启动和完成时打扰 CPU