全局框架

  • 全局框架
    • 系统层次
      • 核心矛盾：速度差
        • CPU 运算快、内存慢、外设更慢
      • 系统用层次结构（寄存器/Cache/内存/磁盘）和并行性（流水线/乱序/多核/DMA）来隐藏或者摊薄延迟
      • 指令在 CPU 里按“取值-译码-执行-访存-写回“的数据通道运行
      • 为了加速，做流水线把这 5 步重叠
      • 内存访问通过 Cache 利用局部性降低平均延迟
      • 虚拟内存通过 MMU/TLB 把程序看到的地址映射到物理内存
      • I/O 慢是由于设备与总线带宽/延迟远弱于 CPU，因此依赖中断、缓冲与 DMA 来减少 CPU 参与

指令系统与数据表示

  • 指令系统与数据表示
    • 整数与位运算的数据表示
      • 位、字节、字
        • bit：0/1
        • Byte：8bit
        • Word（字）：CPU 自然处理的宽度，与寄存器/ALU/地址宽度相关
        • 为什么 byte 是最小编址单位：大多数现代机器按照字节编址，方便表示字符/结构体/网络数据等
      • 原码/反码/补码
        • 原码
          • 表示方法：最高位符号位，剩下是绝对值
          • 问题：
            • 有 +0 和 -0 两种零
            • 加减法需要额外处理符号，硬件复杂
        • 反码
          • 正数同原码
          • 负数：对正数位取反
          • 问题
            • 仍然有 +0 和 -0
            • 加法需要回卷进位
        • 补码
          • 正数：与无符号相同
          • 负数：按位取反 + 1
          • 关键性质：
            • 只有一个 0（没有 -0）
            • 加减法统一为同一套加法器：a-b=a+(~b+1)
            • 符号扩展简单：高位补符号位即可
            • 范围不对称 [-2^{n-1},2^{n-1}-1]
          • 快速转换
            • 补码->十进制
              • 最高位 0：按无符号直接算
              • 最高位 1：取反 +1 得到绝对值，再加负号
            • 十进制->补码
              • 正数：直接写二进制，左侧补 0
              • 负数：先写绝对值二进制 -> 取反+1
        • 有符号/无符号加法与溢出判断
          • 无符号溢出(Unsigned overflow)
            • 本质：结果超出 [0, 2^n-1]
            • 判定方法：看进位 Carry-out
          • 有符号溢出
            • 本质：结果超出 [-2^{n-1},2^{n-1}-1]
            • 判断口径统一
              • 同号相加，异号结果 => 溢出
              • 异号相加不会溢出
            • 等价位级判定
              • 符号位的进位与最高位进位输出不同=>溢出
        • 字节序：大端 vs 小端
          • 对 32-bit 只 0x12 34 56 78 高位在左
          • 大端
            • 低地址存高字节
            • 内存从低地址到高地址 12 34 56 78
            • 直觉：与人类书写一致
          • 小端
            • 低地址存低字节
            • 内存从低地址到高地址：78 56 34 12
            • 直觉：低地址就是低位，做逐字节扩展/截断更自然
            • x86 等主流架构长期使用小端
          • 对齐与 Padding
            • 对齐
              • 要求：某类型对象的地址必须是某个中的倍数(4/8)
            • 为什么要对齐
              • 硬件访问效率：CPU/总线按照字/双字读写；未对齐可能需要两次内存读写再拼接
              • Cache line 与内存访问粒度：对齐能减少跨行/跨 cache line 的概率
            • Padding（填充）
              • 为了满足对齐，编译器会在结构体字段之间或末尾插入空字节
              • 结构体大小通常是其最大对齐需求的倍数
    • 浮点数(IEEE 754) 与误差本质
      • IEEE 754 基本格式
        • 浮点数表示
          • S（符号位）：0 正 1 负
          • E（指数/阶码）：带拍支 bias
          • F（尾数/小数部分）：有效数 significand 的小数部分
          • 单精度 float（32-bit）
            • S: 1 位
            • E: 8 位，bias = 127
            • F: 23 位
          • 双精度 double（64-bit）
            • S：1 位
            • E: 11 位，bias=1023
            • F: 52 位
          • 规格化、非规格、0、INF、NaN
            • 规格化
              • 指数 E 既不是全 0 也不是全 1
              • 有隐含的 leading 1：1.F
            • 非规格化
              • 指数 E 全 0，尾数 F 非 0
              • 没有隐含 1：有效数是 0.F
              • 目的：渐进下溢，让非常接近 0 的数仍然能表示
            • 0
              • E 全 0，F 全 0
              • 有 +0 和 -0
            • Inf 无穷
              • E 全 0，F 全 0
              • 有 +0 和 -0
            • NaN（非数）
              • E 全 1，F 非 0
              • 来自非法操作：0/0
              • NaN 会传播
          • 0.1 + 0.2 != 0.3
            • 十进制小数在二进制中往往是无线不循环小数
            • 0.1 的二进制是 0.0001100111
            • float/double 只能保存有限位尾数
            • 存储时发生舍入，计算时再舍入，误差叠加
            • 比较时用 ==，就可能不相等

CPU 执行与控制

  • CPU 执行与控制
    • 单周期 Datapath
      • 必备组件
        • PC 当前指令地址寄存器
        • Instruction Memory/I-Cache：根据 PC 取指令
        • Register File （寄存器堆）：两读一写（rs1、rs2 读；rd 写）
        • Immediate Generator（立即数生成/符号扩展）
        • ALU：算数逻辑/比较/地址计算
        • Data Memory/D-Cache：load/store 访问
        • Adders：
          • PC + 4
          • PC + imm （分支目标）
        • 关键 MUX（多路选择器）
          • ALUSrc：ALU 第二操作数是来自 rs2 还是 imm
          • MemToReg：写回 rd 的数据来自 ALU 还是内存
          • PCSrc：下一 PC 来自 PC+4 还是分支目标
        • Control Unit（控制器）：根据 opcode/funct 产生控制信号
        • datapath = 一堆功能模块 + 多根线 + MUX 选路
    • 四条指令在 datapath 里怎么走
      • R 型算数：add rd, rs1, rs2
        • 目标：rd = rs1 + rs2
        • 数据流
          • PC -> 取指令
          • 寄存器堆读 rs1、rs2
          • ALU 计算 ALUOut = rs1 + rs2
          • 写回：rd <- ALUOut
          • PC 更新：PC <- PC + 4
        • 关键控制
          • RegWrite = 1 写寄存器
          • ALUSrc = 0 第二操作数来自 rs2
          • MemRead = 0, MemWrite = 0
          • MemToReg = 0（写回来自 ALU）
          • Branch = 0（不分支）
          • ALUOp = R-type（由 funct 决定是 add/sub/and/or）
      • 访存读：lw rd, imm(rs1)
        • 目标：rd = Mem[rs1+imm]
        • 数据流
          • 取指
          • 读寄存器 rs1 (base)，rs2 通常也读但不用
          • ALU 计算有效地址：ALUOut = rs1 + imm
          • 数据内存读：MemOut = Mem[ALUOut]
          • 写回：rd <- MemOut
          • PC <- PC + 4
      • 访存写：sw rs2, imm(rs1)
        • 目标：Mem[rs1+imm] = rs2
        • 数据流
          • 取指
          • 读 rs1（base） 和 rs2（要写入的数据）
          • ALU 算地址：ALUOut = rs1 + imm
          • 数据内存写：Mem[ALUOut] <- rs2
          • PC <- PC + 4
      • 条件分支：beq rs1, rs2, imm
        • 目标：如果 rs1 == rs2，则 PC <- PC + imm；否则 PC <- PC + 4
        • 数据流
          • 取指
          • 读 rs1，rs2
          • ALU 做比较：Zero = (rs1-rs2==0)
          • 同时计算目标分支：Target = PC + imm
          • PC 选择
            • if Branch & Zero：PC <- Target
            • else: PC <- PC + 4
    • 单周期 vs 多周期
      • 单周期
        • 每条指令都在一个周期完成
        • 周期必须长到容纳最慢指令路径
        • 结果：简单但浪费，端指令也被迫跑长周期
      • 多周期
        • 把一条指令拆分成多个步骤，每一步一个周期
        • 不同指令用不同步骤数量
        • 可以复用硬件
    • 性能
      • 性能公式
        • IC：执行的指令条数
        • CPI：平均每条指令需要多少周期
        • Cycle Time：每周期多长时间 (=1/主频)
      • Amdahl 定律（优化上限）
        • 如果系统中某部分占比位 f，该部分加速 S 倍，总加速比
      • IPC、吞吐、延迟
        • 延迟：完成单个任务/单条指令/一次请求需要的时间
        • 吞吐：单位时间完成多少任务
        • IPC：每周期完成多少条指令
        • 吞吐 = IPC x 频率

流水线与冒险

  • 流水线与冒险
    • 五级流水线核心内容
      • 五段功能定义
        • IF：取值；PC->I-Cache；计算 PC+4
        • ID：译码；读寄存器；生成立即数
        • EX：ALU 运算；地址计算；分支比较
        • MEM：访问 D-Cache
        • WB：写回寄存器 rd
      • 流水线寄存器
        • 为了让每段每周期独立推进，段与段之间插入寄存器
        • IF/ID、ID/EX、EX/MEM、MEM/WB 它们保存上一段的输出给下一段用（包含数据与控制信号）
      • 理想吞吐与延迟
        • 非流水：一条指令用 5 个周期，下一条等它结束
        • 流水：启动后每周期完成 1 条
        • 延迟：单条仍然=5 个阶段
        • 吞吐：理想从 1/5 提升到 1
      • 流水线的代价
        • 需要通多寄存器与控制逻辑
        • 分支错预测要清刷流水线
        • 结构冲突要加资源或停顿
    • 结构冒险
      • 定义
        • 同一周期内两个阶段需要同一个硬件资源
      • 例子
        • 单端口存储器：IF 要取值，MEM 要访存
        • 同一周期冲突 -> 必须 stall 或改造硬件
        • 解决方案
          • 分离 I-Cache/D-Cache
          • 多端口存储器
    • 数据冒险
      • 三种依赖
        • RAW(Read After Write)真依赖：后读依赖前写，最关键
        • WAR(Write After Read)反依赖：后写不能早于前读
        • WAW(Write After Write)输出依赖：两条写同一目的寄存器
      • 为什么会 RAW：写回晚，读取早
        • 读寄存器在 ID
        • 写回寄存器在 WB
      • Fowwarding （旁路/转发）机制
        • 不等写回到寄存器堆，直接把产生的结果从后端绕回到前段使用
        • 转发路径
          • EX/MEM -> ID/EX（给下一条的 EX 用）
          • MEM/WB -> ID/EX （给下一条或下下条的 EX 用）
      • Stall(插泡)与 load-use hazard
        • load-use 典型序列
          • lw r1, 0(r2)
          • add r3, r1, r4
          • 原因
            • lw 的数据到 MEM 末才可用
            • add 需要在 EX 用到 r1
            • 时间上赶不上，即使有 forwarding 也不够快
          • 结论：需要插入一个 bubble
          • 实现
            • 冻结 PC 和 IF/ID
            • 往 ID/EX 注入一个 NOP （控制信号清零）形成 bubble
    • 控制冒险
      • 定义：PC 的下一值不确定：到底走 PC+4 还是分支目标
      • 分支决定在哪里做决定 penalty
        • 如果分支在 EX 才能确定
        • 在分支结果出来之前，流水线已经取了后续若干条
        • 一旦发现分支 taken，就要把错路径指令 flush 掉
      • 基础策略
        • stall until branch resolved：等分支算出来再取后续
        • predict not taken：默认不跳，先取顺序；若实际 taken -> flush
        • 动态分支预测：用分支历史表、2-bit 饱和计数器等降低错预测
        • BTB：预测 taken 时快速给出目标地址
        • 延迟槽
      • penalty
        • 分支罚时：错预测或 taken 导致需要清空的阶段数

存储体系

  • 存储体系
    • 核心矛盾
      • CPU 周期是纳秒级，DRAM 访问通常是几十到上百纳秒级，差一个数量级
      • 解决思路：分层存储 + 局部性
      • Cache 用更贵更快的 SRAM 缓存最近用过的数据块，依赖时间/空间局部性降低平均访存时间
    • Cache 基础概念
      • Cache line （缓存行）
        • Cache 以“行/块“位单位搬运数据
        • CPU 读写某地址时，实际会把该地址所在的整条 cache line 搬到 Cache。
        • 推论：顺序访问数组通常很友好；跨行访问容易 miss
      • Hit/Miss 与三大指标
        • Hit time：命中时访问延迟
        • Miss rate：未命中比例
        • Miss penalty：未命中后去下一级/内存取回的代价
        • 平均访存时间 AMAT
          • AMAT = Hit Time + Miss Rate * Miss Penalty
      • MISS 分类
        • Compulsory miss（冷启动）：第一次访问必 miss
        • Capacity miss（容量）：工作集超过 Cache 容量
        • Conflict miss（冲突）：映射/组相联导致不同块争同一行
      • 映射方式：直接映射/全相联/组相联
        • 前置数据
          • Cache 总容量 (不含tag/元数据) = C bytes
          • Cache line 大小 = B bytes
          • 总行数 (lines) = L = C/B
          • 相联度 (ways) = A
          • 组数 (sets) = S = L/A
        • 直接映射
          • 每个内存块只能映射到唯一一个 cache 行
          • 优点：硬件简单、命中快
          • 缺点：冲突 miss 多
        • 全相联
          • 任意内存块可放任意行
          • 优点：几乎无冲突 miss
          • 缺点：需要对所有行比较 tag（实现复杂、命中更慢、耗能更高）
        • 组相联
          • 内存块映射到某个 set，但可以放在 set 内任一 way。
          • 折中方案
      • 地址拆分
        • 对于字节编址系统，地址通常拆分为：tag+index+block offset
          • offset 块内偏移
            • 表示在一条 cache line 內的字节位置
            • 位数 offset bits = log2(B)
          • index 组索引
            • 选择 set
            • index bits = log2(S)
          • tag 标记
            • 用于判断该 set 中某一 way 是否是想要的内存块
            • tagbits = Address bits - index bits - offset bits
        • 替换策略
          • LRU：替换最久没用的行
          • Pseudo-LRU（伪 LRU）：用更少 bit 近似 LRU
          • FIFO：先进先出
        • 写策略
          • write-throught（写穿）
            • 写命中：同时写 Cache 和下一级
            • 优点：下一级始终最新，实现简单
            • 缺点：写流量大
          • write-back（写回）
            • 写命中：只写 Cache，把该行标记为 dirty
            • 该行被替换时才写回下一级
            • 优点：显著减少写带宽压力
            • 缺点：一致性更复杂（多核）
          • 写不命中 write miss 的两种策略
            • write-allocate（写分配）：先把整条 line 读入 Cache，再在 Cache 上写，与 write-back 搭配
            • no-write-allocate（不写分配）：不把 line 加入 Cache，直接写下一级，常与 write-throught 搭配
        • 多级 Cache 的 AMAT
          • L1/L2 两级
            • AMAT=HitTime_L1​+MissRate_L1​×(HitTime_L2​+MissRate_L2​×MissPenalty_L2​)
        • 多核：一致性 vs 一致性协议
          • Cache Coherence（一致性）
            • 目标：对于同一内存地址 X，各核的 cache 中 X 的副本要看起来像一个指在变化，不能读各自的旧值
            • 解决办法：一致性协议(MESI)保证写入能让其他核的副本失效/更新
          • Memory Consistency（一致性模型，针对不同地址的顺序）
            • 目标：规定不同核对不同地址的读写在时间顺序上允许怎么样被观察到
            • 是内存模型讨论的问题，涉及重排序与屏障。
          • Coherence 解决同一地址副本一致，Consistency 解决不同地址操作的可见顺序，前者靠协议，后者靠内存模型和 fence。
        • MESI 协议
        • False Sharing
          • 定义
            • 不同核访问的是不同变量，但是这些变量恰好落在同一条 cache line 里
            • 其中一个核写它自己的变量，会把整条 line 的其他核副本失效，导致另一核反复 miss
          • 性能问题
            • 引发 invalidation（整条 line 粒度）
            • 两个核交替写同一条 line 上不同字节
            • line 在核之间反复迁移，带来大量一致性流量

虚拟内存

  • 虚拟内存
    • 要解决的问题
      • 抽象：每个进程看到连续的虚拟内存空间（VA）
      • 保护：权限控制（R/W/X，用户态/内核态）
      • 共享：共享库/共享内存/页共享
      • 扩展：按需分页 + 换入换出
    • 页
      • 虚拟页：进程看到的虚拟地址空间被切分成的固定大小块
      • 物理页框：正式物理内存被切成同样大小的块
      • 二者的大小相同，比如常见 4KB
      • 虚拟内存用虚拟页编号，物理内存用页框编号，页表负责把虚拟页号 -> 物理页框号
      • 地址和页对应
        • 页大小是 4KB
        • 4KB = 4096 字节 = 2^12
        • 一个地址的低 12 位代表页内偏移
        • 高位表示虚拟页号（VPN）
    • 地址转换链路
      • VA -> TLB -> page table -> PTE -> PA -> Cache/Memory
      • 术语解释
        • VA：进程发出的地址
        • PA：真实内存地址
        • VPN：虚拟页号
        • VPO：页内偏移
        • PPN：物理页框号
        • PTE：页表项，记录 VPN -> PPN 的映射与权限等元数据
        • TLB：页表项的高速缓存
      • 页大小与地址拆分
        • 页大小是 PageSize = 2^k 字节
          • offsetBits = k
          • VPNBits = AddrBits - k
        • 转换过程
          • CPU 产生 VA
          • MMU 用 VA 的 VPN 去查 TLB
          • TLB hit：直接得到 PPN + 权限
          • 物理地址 PA = (PPN « offsetBits) | Offset
          • TLB miss：用 VPN 去查页表
          • 拿到 PTE
            • 有效 -> 填入 TLB -> 形成 PA -> 继续访问
            • 无效 -> 触发异常
      • 页表结构
        • PTE 包含什么
          • PPN：物理页框号
          • Present/Valid：是否在内存
          • R/W/X：读写执行权限
          • U/S：用户/内核权限
          • Accessed/Referenced(A)：是否被访问过
          • Dirty(D)：是否被写过
        • 为什么需要多级页表
          • 单级页表
            • VA 空间大，VPN 组合数巨大
            • 每个进程都有一张覆盖整个虚拟空间的大表
          • 多级页表做法
            • 把 VPN 再拆分成多端：VPN1/VPN2/…/VPNn
            • 顶层页表只在需要时为某个范围分配下一级页表
            • 没用到的地址区间不分配页表 -> 按需分配页表
        • 多级页表的 Page Walk
          • 先用 VPN 的高段索引顶层页表，取到二级页表的地址
          • 再用下一段索引二级页表页
          • 最终找到叶子 PTE 得到 PPN
          • 代价：要读多次内存
        • TLB
          • 没有 TLB
            • 每次 load/store 都要走 page walk，可能是 4/5 级
            • 意味着每次访问内存前都要额外多次访存
          • TLB 的本质
            • 缓存最近用过的 VPN -> PPN + 权限
            • 命中时地址翻译几乎是常数空间
      • 缺页异常
        • 典型原因
          • Demand paging（按需分页）：页还没加载到内存
          • Swap out：页被换出到磁盘
          • 权限违规：写只读页
          • Copy-on-write：写共享只读页
        • 缺页处理流程
          • CPU 访问 VA，发现 PTE present = 0 或者权限不符合
          • 触发异常，陷入内核（保存上下文，切换到内核栈）
          • 内核 fault handler 判断 fault 类型
            • 是合法的按需页/非法地址
          • 合法
            • 找到磁盘位置
            • 分配物理页框
            • 发起 IO 把页读入内存
            • 更新页表 PTE
            • 更新 TLB
          • 恢复进程执行
    • 页面置换
      • 当需要一个物理页框但是没有空闲页时，OS 必须选择一个牺牲页换出
      • LRU
      • Clock/Second-Chance(近似 LRU)
        • 维护环形指针
        • 每个页有 Accessed/Referenced 位
        • 扫描时
          • 若 A=0：淘汰
          • 若 A=1：把 A 清 0，给第二次机会，指针继续走
      • 共享与写时复制(COW)
        • 为什么需要 COW
          • fork 的语义：子进程得到父进程内存的副本
          • 如果把所有页都复制一遍，成本极高
        • COW
          • fork 后，父子进程的页表都指向同一批物理页框
          • 把这些页的 PTE 权限改为只读
          • 当父或子尝试写入某页
            • 写入触发 page fault
            • 内核分配新物理页
            • 复制旧页内容到新页
            • 修改该进程页表让它指向新页，恢复写权限
            • 另一个进程仍然指向旧页

IO 总线

  • IO 总线
    • IO 本质上慢
      • 设备物理特性：SSD/网卡/磁盘的延迟远远高于 CPU
      • 路径长：系统调用、内核态切换、驱动、协议栈、队列管理
      • 数据搬运：拷贝次数多、缓存一致性/同步开销高
    • I/O 的基本硬件/软件组件
      • 设备、控制器、驱动
        • 设备：网络、磁盘、USB 设备等
        • 控制器：设备侧的执行单元，负责 DMA、队列、寄存器接口等
        • 驱动：内核中的软件，负责配置设备、提交请求、处理中断、管理队列
      • 数据通路常见参与者
        • CPU 核心
        • Cache
        • 内存
        • I/O 互联 (PCIe)
        • 设备控制器
        • 设备介质
    • 轮询 vs 中断
      • 轮询
        • 做法：CPU 不断读取设备状态寄存器
        • 优点：实现简单、延迟可控
        • 缺点：浪费 CPU、高并发/多设备会严重占用 CPU
      • 中断
        • 设备完成后发中断信号，CPU 暂停当前执行，进入中断处理程序(ISR)
        • 优点：
          • CPU 不需要忙等->提升整体吞吐
        • 缺点：
          • 有中断开销：恢复/保存上下文、切换栈、处理 ISR
          • 中断频繁造成抖动
    • DMA
      • 不用 DMA 的程序搬运
        • CPU 循环从设备寄存器读数据，再写入内存
        • 缺点：CPU 被数据搬运绑死，带宽高、功耗高
      • DMA 的本质
        • DMA 让设备/控制器直接读写内存，CPU 只做设置与收尾
        • CPU 配置 DMA 描述符：内存地址、长度、方向、队列位置
        • DMA 引擎通过总线把数据直接写入/读出 DRAM
        • 完成后用中断通知 CPU（或写状态寄存器）
      • DMA 为什么更快
        • 释放 CPU 周期
        • DMA 更贴近总线/设备，能更高效做 burst 传输
        • 配合 ring buffer/descriptor queue 能批量提交
    • 内存映射 I/O 与端口 I/O
      • MMIO
        • 设备寄存器被映射到某段物理地址空间
        • CPU 用普通的 load/store 指令读写这些地址，就等价于读写设备寄存器
      • Port-mapped I/O
        • 使用专门的 IN/OUT 指令访问 I/O 端口空间
        • 现代系统多以 MMIO 为主
    • 零拷贝
      • 传统读文件再发网络的拷贝路径
        • read()：磁盘->内核页缓存->拷贝到用户缓冲区
        • write()：用户缓冲区->再拷贝回内核 socket buffer -> 网卡 DMA 发走
        • 至少需要两次 CPU 拷贝（内核<->用户，用户<->内核）
      • sendfile 思路
        • 直接让内核把 page cache 中的文件页挂到 socket 发送队列
        • 避免拷贝到用户态再拷回内核态
        • 网卡通过 DMA 从内核缓冲直接发
      • mmap 思路
        • mmap 把文件映射进进程地址空间
        • 应用像访问内存一样访问文件内容，缺页时 OS 按需把页载入 page cache
        • 适合随机访问，但是直接转发场景 sendfile 更适合