笔试速练

A、C 是 OS（资源管理）；B、D 是应用（业务逻辑）。 判断口诀：凡涉及”分配/协调/管理硬件资源”的都是 OS；凡是业务逻辑的都是应用。

并发（同一时间段内交替推进，不是同时刻）。并行需要多核 CPU 真正同时执行。

用户态 → 核心态，触发指令 陷入指令（trap）。系统调用是用户程序获得 OS 服务的唯一途径。

1 - 0.5⁴ = 1 - 0.0625 = 93.75%

1 - 0.8ⁿ ≥ 0.8 → 0.8ⁿ ≤ 0.2

试值：0.8⁵ ≈ 0.328 > 0.2（不够）；0.8⁸ ≈ 0.168 < 0.2（够）→ n ≥ 8

微内核把 OS 服务拆成多个用户态进程，一个服务崩溃不影响其他服务和内核；单内核所有服务在同一内核态，一个 bug 整个 OS 崩（比如 Linux 早期某个驱动 BUG 让整机重启）。代价：微内核服务间走 IPC 比单内核函数调用慢。

用 I/O 等待时间换 CPU 工作时间——一个程序等 I/O 时，OS 立即把 CPU 调度给另一个就绪程序。

并发是前提，派生出共享、虚拟、异步——没有并发就不需要共享、不需要虚拟、不会有异步。

硬盘上 Chrome 程序文件只有一份（静态代码），OS 把它装载到内存中产生 8 个独立的运行实例（每个有自己的内存空间、PCB、寄存器现场）——这正是”程序 vs 进程”的本质：程序静态、进程动态；一个程序可以对应多个进程。

阻塞结束后必须先回到就绪态重新排队，因为 OS 的统一规则是”所有想用 CPU 的进程必须先在就绪队列排队”。直接阻塞→运行会绕过调度公平性。

不认。PCB 是 OS 识别和管理进程的唯一标志——没有 PCB，OS 完全不知道有这个进程存在。”创建进程”=建立 PCB，”销毁进程”=删除 PCB。

1. 保存现场：CPU 寄存器、PC、PSW 保存到 A 的 PCB
2. 入队更新：A 的 PCB 状态改为"就绪"或"阻塞"，挂到对应队列
3. 选择新进程：调度器从就绪队列选中 B
4. 恢复现场：从 B 的 PCB 读出寄存器/PC，写回 CPU
5. 上 CPU：B 的 PCB 状态改"运行"，从 B 的 PC 继续执行

线程切换也要保存寄存器值。真正快在于：同一进程内的线程共享地址空间，切换时不需要切换页表，TLB 不会失效——省掉了进程切换里最贵的一笔开销。

口诀：进程切寄存器 + 切地址空间，线程只切寄存器

4 步因果链： 1. 内核只看到进程，不知道有线程 2. 某线程调用阻塞 I/O，内核以为是”进程”在等 I/O 3. 内核把整个进程挂起到阻塞态 4. 同进程所有线程一起被冻结

抢占式 = OS 可以主动把进程从 CPU 上踢下来。物理基础是时钟中断——没有时钟中断，OS 一旦把 CPU 交给用户程序就拿不回来（除非进程主动等 I/O 或结束）。

长作业可能饥饿——如果短作业源源不断到达，长作业永远排在最后，可能永远轮不到执行。

解法：HRRF（最高响应比优先）——把”等待时间”也加入考量，等久的会因为响应比变高而被优先。

RR 频繁切换让每个进程都被反复打断，丧失了”快速结束短作业”的机会。RR 的真正价值不在平均周转，而在响应时间——每个进程在很短时间内就能拿到一次 CPU。适合分时系统不适合批处理。

• q 过大：退化为 FCFS（每个进程一上 CPU 就跑到底）
• q 过小：切换开销过大（保存/恢复 PCB 的时间占比上升，CPU 实际工作时间下降）
• 经验值：q 略大于一次典型交互响应所需的 CPU 时间

信号量 S 自己是共享变量，PV 操作就是访问临界资源。如果 PV 不原子，信号量自己就先竞态了——根本保护不了别的临界区。这是个套娃问题——信号量原子性靠硬件原子原语（LOCK/CAS/关中断）保证。

5 步链式死锁： 1. mutex 永远停在 0 2. A 自己下次 P(mutex) 也阻塞——把自己锁外面了 3. 其他进程 P(mutex) 全部进入等待队列 4. 没人执行 V(mutex) 5. 等待队列永远没人叫醒 → 死锁

消费者自己 V 自己等的信号量——绕过同步通知，在缓冲区还是空的时候就去取数据，读到垃圾值。

铁律：V(s) 必须由”触发那个事件的进程”来做——full 的语义是”缓冲区有数据” → 只有生产者放完数据才能 V(full)。

口诀：P 自己等的，V 别人等的

当缓冲区满（empty = 0）时死锁： 1. 生产者 A 先 P(mutex)（拿到锁） 2. 接着 P(empty) → 0 → -1，A 阻塞睡眠 3. A 抱着锁睡觉——没人能再 P(mutex) 4. 所有其他生产者全部阻塞，消费者也可能因为后续操作卡住 5. 死锁

铁律：同步 P 必须在互斥 P 之前——避免抱锁睡觉。

情况 1（读者数固定）：W 等当前所有读者完成。 情况 2（读者源源不断到来）：W 可能永远等不到——readcount 永远 ≥ 1，rw 永远不释放。这就是”读者优先”算法的写者饥饿问题。

1. 互斥：资源一次只能被一个进程使用
2. 不可抢占：资源只能由占用进程主动释放
3. 占有并等待：进程已占有部分资源，请求新资源时不放弃已占
4. 循环等待：存在进程链，每个等待下一个占用的资源

口诀：互斥/不抢/占等/循环——4 个全有才死锁，破坏任一个就避免死锁。

1. 初始化：Work ← Available, Finish[i] ← false (所有 i)
2. 找 Finish=false 且 Need[i] ≤ Work 的进程：
   - 找到 → Work ← Work + Allocation[i], Finish[i] ← true，回 2
   - 找不到 → 跳 3
3. 检查 Finish 数组：
   - 全为 true → 安全
   - 有 false → 不安全

口诀：找得到就走、找不到就停、停下后看完没完

死锁 ⊂ 不安全 ⊂ 全状态

• 安全：存在安全序列让所有进程完成
• 不安全：找不到安全序列，有死锁风险但不一定死锁
• 死锁：实际发生进程互相等待

银行家算法的策略：只允许进入安全状态——不安全就拒绝分配。

Step 1: 画关系
  - 哪些进程互斥关系？
  - 哪些进程同步先后关系？

Step 2: 设信号量
  - 互斥资源：mutex（初值 1）
  - m 个同类资源：S（初值 m）
  - 同步事件：S（初值 0）

Step 3: 写 PV
  - 互斥 P/V 在同一进程内成对
  - 同步 P/V 跨进程交叉
  - 铁律：同步 P 在前，互斥 P 在后

① 内部碎片（分配单元内部浪费） ② 外部碎片（空闲单元间小到没法分）

口诀：被分了用不完=内部，分不出去=外部

页号 p = ⌊2500 / 1024⌋ = 2
页内偏移 d = 2500 - 2 × 1024 = 452
物理地址 = 5 × 1024 + 452 = 5120 + 452 = 5572

⚠️ 必须算到具体数值（5572），不能停在 5×1024+452。

• 第一个：TLB 命中率分析（p 是 TLB 命中率）
• 第二个：缺页率分析（f 是缺页率，T_缺页 是磁盘 I/O 级毫秒）

两个容易混淆——看清题面给的是哪种场景。

EAT = 0.999 × 100 + 0.001 × 10⁷
    = 99.9 + 10000
    ≈ 10100 ns

变慢 = 10100 / 100 = 100 倍

反直觉：千分之一缺页率就慢 100 倍——所以 OS 拼命压低缺页率到 0.001% 以下。

Belady 异常：FIFO 算法增加页框数，缺页率反而上升——反直觉。

只有 FIFO 有——OPT、LRU、CLOCK 都没有。原因：FIFO 只看进入时间不看活跃度，多一个页框可能让常用页晚被淘汰反而让”该淘汰的”提前出局。

OPT/LRU 因为驻留集随页框单调扩张，多一个页框只会”多保留有用的页”。

• FIFO：命中时不更新顺序（队列结构不变，淘汰仍按进入时间）
• LRU：命中时把该页移到”最新”那端（淘汰最久没用的）

口诀：“FIFO 看进来，LRU 看用过”

3 次： 1. 查段表（得页表起址） 2. 查页表（得页框号） 3. 访问数据

⚠️ 不是 2 次。

基于局部性原理： - 时间局部性：最近访问的，很可能马上又访问（循环、局部变量） - 空间局部性：访问某地址，很可能马上访问相邻地址（数组、顺序代码）

所以”只把当前用的页装内存，其他放磁盘”在大多数程序上都有效——磁盘 I/O 的高代价被局部性的高命中率摊销。

抖动：驻留集 < 工作集 → CPU 大量时间处理缺页中断而非用户代码 → 进程互相抢页 → CPU 利用率急剧下降。

3 种解法： 1. 工作集模型：根据进程的工作集大小动态分配页框 2. PFF 缺页频率控制：监测缺页率，超阈值分配更多页框 3. 挂起部分进程：降低多道程度，让剩下的进程都有足够页框

口诀：“分页死板省内存，分段灵活便共享”

核心区别是”搬数据的工作由谁做“： - 中断驱动：CPU 在每次中断时亲自把数据从设备控制器寄存器搬到内存 - DMA：DMA 控制器代替 CPU 完成搬运，CPU 只在传输开始和结束时介入

8 字金句：“中断驱动 = CPU 搬，DMA = 控制器搬”

100 万包/秒 × 1KB/包 = 10 亿次中断/秒。CPU 时钟 3 GHz 也撑不住——每次中断处理至少几百个时钟，CPU 100% 都在处理中断，没时间执行用户代码——这叫中断风暴。

现代网卡都用 DMA + 中断聚合（Linux NAPI）。

M 期间缓冲区被占用，设备不能往里写新数据（会覆盖正在拷出的数据）——M 是被迫串行的”独木桥”，不能与任何动作并行。

双缓冲让 M 进入 max 是因为多一个缓冲区给设备用——M 用缓冲 1 时，T 用缓冲 2 工作，M 不再阻塞 T。

输出井——打印是输出方向（用户进程 → 设备）。

判断口诀：“输入是数据进来（设备→进程），输出是数据出去（进程→设备）——按数据流向决定”

远端请求可能饥饿——如果近端请求源源不断到来，远端的请求永远轮不到。

SCAN/LOOK 通过”扫描方向”机制避免饥饿——每个请求都会被”扫到”。

参考 cheatsheet #1-#4。结果：

结论： - SJF 平均最优（但长作业饥饿） - RR 平均最差但响应时间最好 - HRRF 接近 SJF 且无饥饿 - FCFS 最简单但短作业不公

Available = (10,5,7) - 各进程 Allocation 总和
         = (10,5,7) - (7,2,3) = (3,3,4)

Need：
  P0: (7,4,3)
  P1: (1,2,2)
  P2: (6,0,0)
  P3: (0,1,1)

推演：
  Work=(3,3,4), 找 Need ≤ Work：P3.Need=(0,1,1) ✓ → P3 完成
  Work=(3,3,4)+(2,1,1)=(5,4,5), 找：P1.Need=(1,2,2) ✓ → P1 完成
  Work=(5,4,5)+(2,0,0)=(7,4,5), 找：P0.Need=(7,4,3) ✓ → P0 完成
  Work=(7,4,5)+(0,1,0)=(7,5,5), 找：P2.Need=(6,0,0) ✓ → P2 完成

安全！安全序列 = P3 → P1 → P0 → P2

完整推演：

t=1: 7 → F, [7]
t=2: 0 → F, [7,0]
t=3: 1 → F, [7,0,1]
t=4: 2 → F, 淘汰 7, [0,1,2]
t=5: 0 → H, [1,2,0]
t=6: 3 → F, 淘汰 1, [2,0,3]
t=7: 0 → H, [2,3,0]
t=8: 4 → F, 淘汰 2, [3,0,4]
t=9: 2 → F, 淘汰 3, [0,4,2]
t=10: 3 → F, 淘汰 0, [4,2,3]
t=11: 0 → F, 淘汰 4, [2,3,0]
t=12: 3 → H, [2,0,3]
t=13: 2 → H, [0,3,2]
t=14: 1 → F, 淘汰 0, [3,2,1]
t=15: 2 → H, [3,1,2]
t=16: 0 → F, 淘汰 3, [1,2,0]
t=17: 1 → H, [2,0,1]
t=18: 7 → F, 淘汰 2, [0,1,7]
t=19: 0 → H, [1,7,0]
t=20: 1 → H, [7,0,1]

缺页 = 12
缺页率 = 12/20 = 60%

FCFS: 50→86→147→91→177→94→150→102→175→130 距离 = 36+61+56+86+83+56+48+73+45 = 544

SSTF: 每次选最近的 50→86→91→94→102→130→147→150→175→177 距离 = 36+5+3+8+28+17+3+25+2 = 127

SCAN（向外扫到 199 再反向）： 50→86→91→94→102→130→147→150→175→177→199（边界）→ 没有更内的请求，停 距离 = (199-50) = 149（不计回程）

LOOK（不到边界，扫到最远请求 177）： 50→86→91→94→102→130→147→150→175→177 距离 = 177-50 = 127

时序：

1. 时钟中断信号触发，CPU 完成当前指令后跳转到中断处理程序入口
2. 保护现场：CPU 自动把 PC、PSW 入栈；中断处理程序保存通用寄存器到 A 的 PCB
3. CPU 切换到核心态
4. 调度器查就绪队列选中 B（这一步本身可能涉及优先级计算、HRRF 响应比等）
5. 状态切换：A 的 PCB 状态改”就绪”，B 的 PCB 状态改”运行”
6. 切换地址空间：把 B 的页表基址（CR3 寄存器）加载到 MMU
7. TLB 失效：因为页表换了，所有 TLB 条目作废，下次访存先 TLB miss
8. 恢复现场：从 B 的 PCB 读出寄存器/PC，写回 CPU
9. 返回用户态，CPU 从 B 的 PC 继续执行

为什么开销大： - 步骤 6-7：切换页表 + TLB 失效——之后一段时间访存全部 miss，性能掉一截 - 步骤 2、8：寄存器组保存恢复（x86-64 大约 16+ 通用寄存器 + 浮点 SIMD） - 总开销：现代 CPU 上1-10 微秒——所以频繁切换会浪费大量 CPU

对比线程切换： - 步骤 6-7 不需要（同进程内地址空间相同） - 这就是”线程切换比进程切换快”的根本原因