速成 · 计算机系统基础

#速成

这门课的上下半部分不是两门互不相干的课。

  • 计算机组成原理回答：一条指令怎样被编码，硬件怎样让它真的执行；
  • 操作系统回答：许多程序怎样安全、并发地共享处理器、内存和外设。

把二者接起来，就是完整的执行链：

源程序→机器指令→CPU 数据通路→主存与 Cache→异常或系统调用→内核资源管理.\text{源程序} \to\text{机器指令} \to\text{CPU 数据通路} \to\text{主存与 Cache} \to\text{异常或系统调用} \to\text{内核资源管理}.

复习时不要只背名词。每遇到一个机制，都问三件事：状态放在哪里、谁触发变化、硬件和内核各做哪一段。

硬件与操作系统怎样接力

层次核心对象常见题型
数字表示位、补码、浮点数进制转换、溢出、表示范围
数字逻辑门、组合电路、时序电路化简、真值表、状态机
指令系统MIPS 指令与寄存器R/I/J 编码、寻址、汇编
处理器数据通路和控制信号单周期走线、流水线冒险
存储层次RAM、Cache、虚拟存储地址划分、命中、页表
OS 入口异常、中断、系统调用用户态到内核态的链路
进程管理进程、线程、调度状态转换、周转时间
并发控制临界区、信号量、死锁P/V 伪代码、Banker
持久化与外设I/O、磁盘、文件系统磁盘调度、文件分配

第一部分：计算机组成原理

1. 数值表示：先确定位宽和解释方式

同一串比特没有天然含义。它可以被解释为无符号整数、补码整数、指令或浮点数。

对 nn 位补码：

−2n−1≤x≤2n−1−1.-2^{n-1}\le x\le 2^{n-1}-1.

做补码题时固定四步：

  1. 写清位宽；
  2. 正数按普通二进制写，负数由绝对值按位取反再加一；
  3. 在固定位宽内完成加法；
  4. 丢弃最高进位，再单独判断溢出。

有符号加法的溢出判据是：

两个同号数相加，结果却与它们异号。

无符号数则看最高位进位。二者不能混用。

IEEE 754 单精度分为符号位、8 位阶码和 23 位尾数字段。正规数为

(−1)s(1.f)2 2E−127.(-1)^s(1.f)_2\,2^{E-127}.

先分类 E=0E=0、0<E<2550<E<255、E=255E=255，再计算；不要一上来就套正规数公式。

2. 组合逻辑与时序逻辑

组合电路的输出只由当前输入决定；时序电路还依赖先前状态。

逻辑化简常用：

AB‾=Aˉ+Bˉ,A+B‾=AˉBˉ.\overline{AB}=\bar A+\bar B, \qquad \overline{A+B}=\bar A\bar B.

Karnaugh 图的关键不是“画圈”，而是：

  • 每圈格数必须是 2k2^k；
  • 允许跨边界相邻；
  • 尽量圈大，可重叠；
  • 圈内发生变化的变量被消去。

分析时序电路时按固定链条：

激励方程→次态方程→输出方程→状态表→状态图.\text{激励方程} \to\text{次态方程} \to\text{输出方程} \to\text{状态表} \to\text{状态图}.

设计状态机则反过来：先从题意定义状态，再编码、选触发器、列激励并化简。

3. MIPS 指令格式

MIPS 的三个基本格式：

格式字段主要用途
R 型opcode, rs, rt, rd, shamt, funct寄存器运算
I 型opcode, rs, rt, immediate立即数、访存、条件分支
J 型opcode, instr_index大范围直接跳转

R 型手算顺序：

  1. 按助记符确认 rs,rt,rdrs,rt,rd，不要照汇编书写顺序机械抄；
  2. 每个寄存器编号写成 5 位；
  3. opcode 和 funct 各写 6 位；
  4. 拼成 32 位，再转十六进制。

I 型的 16 位立即数究竟符号扩展还是零扩展，由指令语义决定：

  • 地址偏移、分支位移、加法立即数通常符号扩展；
  • andi、ori 等把立即数当位模式，使用零扩展。

条件分支目标为

PCtarget=(PC+4)+(signext⁡(imm16)≪2),PC_{\text{target}} =(PC+4)+(\operatorname{signext}(imm16)\ll2),

所以汇编器填写

imm16=T−(PC+4)4.imm16=\frac{T-(PC+4)}4.

J 型目标地址为

(PC+4)31:28 ∥ instr_index ∥ 00.(PC+4)_{31:28}\,\Vert\,instr\_index\,\Vert\,00.

4. 从 C 到 MIPS

数组元素地址：

addr⁡(a[i])=base⁡(a)+i×sizeof⁡(a[0]).\operatorname{addr}(a[i]) =\operatorname{base}(a)+i\times\operatorname{sizeof}(a[0]).

翻译循环或分支时，先写控制流，再填数据操作：

  1. 标出循环头、循环体和退出标签；
  2. 把条件改写成 MIPS 可比较的形式；
  3. 明确每个变量放在哪个寄存器；
  4. 最后检查 load/store 的字节偏移。

函数调用必须区分两类寄存器：

  • 调用者保存：调用前若还要用，调用者自己压栈；
  • 被调用者保存：函数若要改，入口保存、返回前恢复。

栈帧里还要考虑返回地址、局部变量和对齐。递归只是每次调用都有独立栈帧，并不是另一套机制。

5. 单周期 CPU：让每条指令走一遍数据通路

单周期题不要背整张图，按信息流追踪：

  1. PC 送入指令存储器并同时计算 PC+4PC+4；
  2. 指令字段选出寄存器和立即数；
  3. ALU 完成算术、地址或比较；
  4. 必要时访问数据存储器；
  5. 多路选择器决定写回数据和下一条 PC。

控制信号的本质是“选择哪条路”或“是否写入”：

  • RegWrite：是否写寄存器；
  • MemRead、MemWrite：是否访问数据存储器；
  • ALUSrc：ALU 第二操作数来自寄存器还是立即数；
  • MemtoReg：写回来自 ALU 还是存储器；
  • Branch、Jump：下一条 PC 怎样选。

新增一条指令时，先问已有数据通路能不能运送它需要的数据，再补硬件和控制信号；不要只改控制表。

6. 五级流水线

经典五级为：

IF→ID→EX→MEM→WB.IF\to ID\to EX\to MEM\to WB.

理想情况下，nn 条指令在 kk 级流水线中的周期数近似

k+n−1.k+n-1.

实际还要加暂停和清空周期。时钟周期由最慢流水级加流水寄存器开销决定，所以级数越多不等于性能无限提高。

数据冒险先列读写关系：

  • RAW：后指令要读前指令尚未写出的结果，最常见；
  • WAR、WAW 在经典顺序五级 MIPS 中通常不会发生。

转发解决“结果已经算出但还没写回”的情况；load-use 冒险中，数据到 MEM 末尾才得到，紧随其后的使用者通常仍需暂停一拍。

控制冒险来自分支结果尚未确定。常见处理是暂停、预测或在判错后清空错误路径。

画时序图的固定步骤：

  1. 先画没有冒险的斜线；
  2. 标出每条指令何时需要源操作数、何时产生结果；
  3. 按题目给定的转发能力判断能否直送；
  4. 不能转发才插入 stall；
  5. 再处理分支 flush。

7. Cache

地址总能拆成：

Tag∣Index∣Block Offset.\text{Tag}\mid\text{Index}\mid\text{Block Offset}.

若块大小为 BB 字节：

b=log⁡2Bb=\log_2B

位是块内偏移。若 Cache 数据容量为 CC，EE 路组相联，则

S=CBES=\frac{C}{BE}

组，组索引位数为

s=log⁡2S.s=\log_2S.

Tag 位数等于地址总位数减去 s+bs+b。

模拟访问序列时，为每一组单独维护有效位、Tag、脏位和替换次序。不要把“访问相同组”误当成“命中”；Tag 也必须相等。

Cache 的实际总容量还包括 Tag、有效位、脏位和替换状态，不能只答数据区容量。

平均访存时间常写为

AMAT=Thit+RmissPmiss.AMAT=T_{\text{hit}} +R_{\text{miss}}P_{\text{miss}}.

写策略要同时说明 write-through 或 write-back，以及 write-allocate 或 no-write-allocate。

8. 主存芯片扩展

把目标存储器写成“字数 ×\times 位数”。

  • 位扩展倍数 = 目标字长 / 芯片字长；
  • 字扩展倍数 = 目标字数 / 芯片字数；
  • 总片数 = 两者乘积。

低位地址送到所有芯片内部选字，高位地址经过译码选择哪一组芯片。数据位宽扩展时，多片芯片并行贡献同一个字的不同位。

第二部分：操作系统

9. 用户态怎样进入内核

操作系统的基本特征是并发、共享、虚拟和异步。应用不能直接执行特权操作，而是通过受控入口进入内核。

三类事件要分清：

  • 中断：外设或时钟异步触发；
  • 异常：当前指令执行导致，如缺页、除零；
  • 系统调用：程序主动执行陷入指令，请求内核服务。

统一入口链：

事件发生→硬件保存最小现场→切换内核态和入口→内核处理→恢复现场→返回用户态.\text{事件发生} \to\text{硬件保存最小现场} \to\text{切换内核态和入口} \to\text{内核处理} \to\text{恢复现场} \to\text{返回用户态}.

启动过程则从固件建立最初环境开始，经引导程序装入内核，内核初始化内存、异常入口、进程和设备，最后启动第一个用户进程。

10. 连续分配、分页与分段

连续可变分区中的 First Fit、Next Fit、Best Fit、Worst Fit 都是在空闲区表上选洞。外部碎片是空闲空间总量够但不连续；内部碎片是分给进程的块内部没有用完。

分页把虚拟地址拆成：

VPN∣Offset.\text{VPN}\mid\text{Offset}.

若页大小为 2p2^p 字节，页内偏移就是 pp 位。地址转换：

虚页号→页表或 TLB物理页框号,\text{虚页号} \xrightarrow{\text{页表或 TLB}} \text{物理页框号},

页内偏移原样拼接。

页表计算题固定五步：

  1. 由页大小求 offset 位数；
  2. 用地址总位数减出 VPN 位数；
  3. 按各级索引位数切地址；
  4. 由“基址 + 索引 ×\times 表项大小”求表项地址；
  5. 从表项取页框号，再拼接 offset。

TLB 是页表项的高速缓存。TLB miss 不等于缺页；它可能只需查内存中的页表。页表项无效才进入缺页处理。

分段按程序的逻辑单元管理，地址是“段号 + 段内偏移”；页是固定大小的物理管理单位。段页式先按段找到该段页表，再分页转换。

11. 虚拟内存与页面置换

虚拟内存建立在局部性上，只把当前需要的页面装入内存。缺页时：

  1. CPU 发现页表项无效并陷入内核；
  2. 内核确认访问合法；
  3. 选择空闲页框或牺牲页；
  4. 脏页必要时写回；
  5. 从磁盘读入所需页；
  6. 更新页表和 TLB；
  7. 重新执行导致缺页的指令。

置换算法：

  • OPT：淘汰未来最晚再用的页，只能作为理论最优基准；
  • FIFO：淘汰最早进入的页，可能出现 Belady 异常；
  • LRU：淘汰最长时间未使用的页；
  • Clock：用访问位近似 LRU。

手算时逐次写页框状态和是否缺页，不能只凭直觉数。

页面频繁换入换出、有效执行时间很少就是抖动。减少并发度、使用局部置换或工作集思想能缓解。

12. 进程与线程

程序是静态代码；进程是一次正在进行的执行，拥有地址空间和资源；线程是进程中的执行流，共享进程资源但有自己的寄存器现场和栈。

进程常见状态：

就绪⇄运行⇄阻塞.\text{就绪} \rightleftarrows \text{运行} \rightleftarrows \text{阻塞}.
  • 调度：就绪 →\to 运行；
  • 时间片到或被抢占：运行 →\to 就绪；
  • 等待 I/O 或同步条件：运行 →\to 阻塞；
  • 事件完成：阻塞 →\to 就绪。

上下文切换不是“进程自己继续执行”，而是内核保存旧现场、选择新执行实体、恢复新现场。切换有开销但不直接完成用户工作。

13. 进程同步

临界区问题要满足互斥、前进和有限等待。信号量是带原子 P/V 操作的整数：

  • P：申请资源；资源不可用时阻塞；
  • V：释放资源；必要时唤醒等待者。

做同步题时先把信号量按职责命名：

  • mutex 只保护临界区；
  • empty、full 记录缓冲区空槽和已有产品；
  • 事件型信号量表达先后关系。

生产者—消费者的典型顺序：

生产者消费者
P(empty)P(full)
P(mutex)P(mutex)
放入产品取出产品
V(mutex)V(mutex)
V(full)V(empty)

先等待资源再拿互斥锁，可避免“拿着锁睡眠，另一方永远进不来”的死锁。

14. CPU 调度

常见指标：

周转时间=完成时刻−到达时刻,\text{周转时间} =\text{完成时刻}-\text{到达时刻}, 带权周转时间=周转时间服务时间,\text{带权周转时间} =\frac{\text{周转时间}}{\text{服务时间}}, 响应时间=首次运行时刻−到达时刻.\text{响应时间} =\text{首次运行时刻}-\text{到达时刻}.

算法要点：

  • FCFS 简单但可能出现短作业等待长作业；
  • SJF 平均等待时间好，但需估计服务时间；
  • SRTF 是可抢占的最短剩余时间优先；
  • RR 按时间片轮转，时间片过大趋近 FCFS，过小切换开销高；
  • 优先级调度可能饥饿，aging 可逐渐提高等待者优先级。

计算题一定画 Gantt 图；动态到达时，每个决策点只在已经到达的进程中选择。

15. 死锁

死锁同时需要四个条件：

  1. 互斥；
  2. 占有并等待；
  3. 不可抢占；
  4. 循环等待。

处理思路有预防、避免、检测和恢复。Banker 算法判断的不是“当前能否立刻满足所有需求”，而是是否存在某个安全序列。

令

Need=Max−Allocation.Need=Max-Allocation.

安全性检查：

  1. Work 初始化为 Available；
  2. 找到一个 Needi≤WorkNeed_i\le Work 的未完成进程；
  3. 假设它完成并释放资源，令 Work←Work+AllocationiWork\leftarrow Work+Allocation_i；
  4. 重复；若所有进程都能依次完成，则状态安全。

安全状态保证存在完成顺序；不安全状态不等于此刻已经死锁，但未来可能无法避免。

16. I/O 与磁盘

外设速度慢且行为异步。常见数据传送方式：

  • 程序查询：CPU 反复轮询；
  • 中断驱动：设备完成后通知 CPU；
  • DMA：控制器直接在设备和主存间搬运一批数据，CPU 只负责设置和收尾。

缓冲可以吸收速度差；spooling 用磁盘把独占设备虚拟成可排队共享的设备。

磁盘访问时间主要由寻道、旋转等待和传输构成。调度算法：

  • FCFS：按请求顺序；
  • SSTF：先服务最近磁道，可能让远端请求饥饿；
  • SCAN：磁头像电梯一样来回；
  • C-SCAN：只沿一个方向服务，回程不服务，等待更均匀。

计算磁头移动量时，先在数轴上标当前磁道、方向和全部请求，再按算法逐个连线。

17. 文件系统

文件系统要回答：

  1. 名字怎样映射到文件元数据；
  2. 文件偏移怎样映射到磁盘块；
  3. 空闲块怎样记录；
  4. 崩溃后怎样保持一致性。

常见分配：

方式优点代价
连续分配顺序和随机访问快外部碎片、扩展困难
链接分配易增长、无外部碎片随机访问慢、指针开销
索引分配支持随机访问和增长索引块占空间

目录项把文件名连接到 inode 或等价元数据。inode 保存类型、权限、大小、时间、块地址等，不保存路径名本身；硬链接是多个目录项指向同一 inode。

空闲空间可用位图或空闲链表管理。位图便于寻找连续空闲块，但需要存储和扫描。

高频综合题的统一做法

地址题

先写出总位数，再按“页内偏移 / Cache 块内偏移最先由大小决定”的原则切字段。每个索引都明确单位是字节、字、块、页还是表项。

流水线题

先列每条指令读哪些寄存器、写哪个寄存器，再根据题目给定的转发路径和寄存器堆时序判断暂停；不能把课本中的完整转发能力擅自带入题目。

同步题

先写不变量，例如

empty+full=N,empty+full=N,

再为互斥和先后关系分别设信号量。最后逐条检查是否可能持锁阻塞、是否可能漏唤醒。

页面置换与调度题

都画时间线。每一步只根据当时可见的信息更新状态，不事后用未来信息，OPT 除外。

考前最后检查

  • 补码位宽、符号扩展和溢出判据有没有混；
  • R/I/J 字段、分支基准 PC+4PC+4 是否写对；
  • 单周期指令经过哪些部件、哪些写使能打开；
  • 流水线题是否按题目给定的转发能力判断；
  • Cache 是否同时比较 Index 和 Tag；
  • TLB miss、页表命中、缺页三者是否分清；
  • 进程状态转换的触发者是否写清；
  • P/V 顺序是否会拿锁后睡眠；
  • 调度题是否只选已经到达的进程；
  • Banker 的 Need、Work 是否逐轮更新；
  • 磁盘调度是否考虑初始方向；
  • 文件名、目录项、inode、数据块是否分层。

如果这些链条都能不用背诵地解释出来，这门课就不再是两堆术语，而是一台机器从通电到运行多个程序的完整故事。

评论