深入理解计算机系统

参考资料

• 深入理解计算机系统

计算机系统漫游

• 科普一个简单程序的全生命周期
• 考虑到所有内容后续都会详叙, 在此不做展开
• Amdahl 定律描述了改善任何过程的一般原则 (抓大头)

信息的表示和处理

位向量与计算机中的表示

• 字节是计算机中最小的可寻址内存单位
• C 语言用编译时的不同的机器级代码表示类型, 生成的程序并不包含类型信息
• 字长决定的最重要的系统参数就是虚拟地址空间的最大大小
• 三个场景关注大小端
  • 网络协议中, 数据在网络中传输时
  • 汇编语言中
  • C 语言的高级技巧
• 长度为 n 的位向量上 ^, ~, & 运算形成布尔环
  • 用位向量编码集合子集是, ^, ~, & 恰为并集, 补集, 交集
• 我们一般对有符号数使用算术右移 (进行类型拓展时同理)
• 我们对位向量加上一个解释去表示类型

整数表示与运算

• 补码可以理解为最高位权为 \(-2^{n-1}\)
• C 语言有无符号数转换只转换解释, 不转换位模式
  • 比较时小心有符号数被强转为无符号数
• 无符号类型截断就是取模, 对有符号数进行类型转换时, 先解释为无符号数, 再取模, 再解释为有符号数
• 有符号数的相加也可以理解为无符号数的相加, 只是结果需要解释为有符号数
  • 会出现正溢出和负溢出
• 无符号数与有符号数的加法逆元位模式一致
  • 对位模式取反再加一
  • 除了最小的有符号数没有加法逆元
• 无符号数与有符号数的乘法位模式一致
  • 先看成无符号数, 相乘, 取模, 再解释为有符号数
• C 语言有符号整数除法的结果是向零截断的
  • 所以右移运算不能直接替代除法, 需要补偿
  • 补偿方法为, 负数时, 先加上 \(2^k - 1\), 再右移
• C 语言取模结果的符号与被除数 \(x\) 的符号一致
  • 计算方法依旧一致, 先获得商 (向零截断), 再用被除数减去商乘以除数
  • 所以这里有无符号数除法和取模的位模式存在差异

浮点数

• \((-1)^s \times 2^E \times M\)
• 根据 \(E\) 的位模式, 将浮点数划分为以下几种
  • 全为 \(0\) 非规格化
  • 全为 \(1\) 时, \(M\) 的位模式全为 \(0\) 表示无穷大, 否则为 NaN
  • 之间的数, 规格化

规格化数

• \(E\) 的解释为 \(E = e - bias\), 其中 \(bias = 2^{k-1} - 1\) (偏置一半)
• \(M\) 的解释为 \(M = 1 + \sum_{i=0}^{n-2} 2^{-i} \times M_i\) (\(1\) + 其位模式解释为小数点在开头的定点小数)

非规格化数

• \(E\) 的解释为 \(E = 1 - bias\)
• \(M\) 的解释为 \(M = \sum_{i=0}^{n-2} 2^{-i} \times M_i\) (小数点在开头的定点小数)
• 非规格化数用于表示 \(0\) 以及接近 \(0\) 的数
• 作用
  • 使得非规格化数的最大值到规格化数的最小值之间的过渡更加平滑
  • 并且单调, 使得浮点数的比较可以直接用位模式比较
  • 实现逐渐下溢, 这保证了 x != y 时 x - y != 0

浮点数的舍入

• 向最近偶数舍入, 先向最近的整数, 若刚好位于两数中间, 则向偶数方向舍入 (默认, 为了减少统计误差)
• 向零舍入, 向上舍入, 向下舍入

浮点数的运算

• 大部分与整数运算一致
• 实数加法 / 乘法不服从结合律
• 浮点乘法在加法上不服从分配律
• NaN 没有加法逆元

程序的机器级表示

X86-64 指令集

• 大部分略
• 任何为寄存器生成 \(32\) 位值的指令都会把该寄存器的高位部分置成 \(0\)
• 除数和余数是一个指令的两个结果
• 部分早期处理器将更新程序计数器作为执行一条指令的第一步
  • 这使得相对寻址指令,实际生成的机器代码当中的相对值是基于下一条指令的

if (x > 0)
    y = 1;
else
    y = -1;

cmpq $0, x
jg .L1
movq $-1, y
jmp .L2
.L1:
movq $1, y
.L2:

• 这是编译器惯有的 if 翻译方法
• 当然, 相较于基于条件控制转移, 我们更喜欢基于条件数据传送 (显然它是包含条件控制转移的, 就是修改 PC)
  • 也就是根据不同的条件返回不同的数据, 这样的话能有效利用流水线
  • 有的时候也不得不用这个条件转移, 比如说条件控制转移的源位置可能不合法直接就段错误

while (x > 0)
    y++;

goto .L1
.L2:
incq y
.L1:
cmpq $0, x
jg .L2

• 这是编译器惯有的 while 翻译方法

cmpq $0, x
    jle .L_DONE     ; 如果初始条件 x <= 0, 直接跳过循环
.L_LOOP:            ; 循环体开始
    incq y
    cmpq $0, x
    jg .L_LOOP      ; 如果 x > 0, 跳回开头
.L_DONE:

• guarded-do, 如果初始条件不成立就直接跳过循环, 否则把代码变换为 do-while 循环
• for 循环, 就是简单包装一下, 就不详叙了
• switch 语句, 就是根据不同的情况跳转到不同的标签 (详见编译原理)

过程

• 尽可能低代价的进行传递控制, 传递数据, 分配和释放内存
• 传递控制就保存一下当前的 PC, 然后跳转到目标地址
• 传递数据就直接用寄存器传递, 或者用运行时栈传递
• 分配和释放内存就直接用栈来实现
• 当所有的局部变量都可以保存在寄存器中, 而且该函数不会调用任何其他函数时, 函数就可能没有栈帧
• 栈帧也需要对齐

数据处理

• 有些时候, 局部数据必须存放在内存中
  • 寄存器不足够存放所有的本地数据
  • 对一个局部变量使用地址运算符
  • 某些局部变量是数组或结构, 因此必须能够通过数组或结构引用被访问到
• 部分寄存器被划分为被调用者保存寄存器, 保证调用前后寄存器的值不变
  • 其他的叫调用者保存寄存器, 调用者在调用前必须保存好它们的值 (如果需要), 调用后再恢复
• 因为栈向下增长, 所以栈上数组溢出时, 会覆盖上面的栈帧
• 为了处理变长数组, 编译器会记录栈帧底指针, 通过腾出一个被调用者保存寄存器来保存它
  • 解决栈顶指针变化导致的偏移量失效
• 数组寻址时的简单加乘计算被集成进专门的单元中, 非常快
• 过程返回时小于 \(16\) 字节会用 \(1\) - \(2\) 个寄存器, 否则会调用拷贝
  • 大对象现代编译器更喜欢做一个 RVO 优化, 传入一个调用者提供的内存地址, 被调用者直接在该地址上构造

浮点数机器语言

• AVX 指令集
  • 扩展了 \(256\) 位的向量寄存器
  • 用于浮点数标量是仅使用 \(256\) 位中的低 \(32\) 或 \(64\) 位 (仅)
  • \(256\) 位叫 YMM 寄存器
  • 低 \(128\) 位叫 XMM 寄存器
• GCC 在做单双精度转换时, 会复制一份原始值, 并行转换出两个结果
• 所有的 XMM 寄存器都是调用者保存
• 编译器会将浮点常量的二进制表示存储在内存的数据段中 (没有真立即数)
• 比较时如果任一操作数是 NaN, 会设置 PF

处理器体系结构

Y86-64 指令集

• Y86-64 的指令集是 X86-64 的子集, 只处理 8 字节的整数操作
• 还有很多简化, 不详叙
• pushq %rsp 压入减去 \(8\) 前的 %rsp (同 X86-64)
• popq %rsp 不自动修改 %rsp
• 机器码
  • 第一个字节为指令
  • 可选第二个字节为两个寄存器
  • 可选接下来 \(8\) 个字节常数 (小端)
• 状态码
  • AOK 正常
  • HLT 处理器执行了 halt 指令, 正常停机
  • ADR 非法地址访问
  • INS 非法指令

HCL (硬件控制语言)

• 具体形式还是比较简单的, 不详叙, 注意不要混淆编程语言
• 将很多的逻辑门组合成一个网, 就能构建计算块, 称为组合电路
  • 每个逻辑门的输入必须连接系统输入 / 某个存储器单元的输出 / 某个逻辑门的输出
  • 两个或多个逻辑门的输出不能连接在一起
  • 这个网必须是无环的
• 多路复用器, 用所有控制输入组合的布尔表达式来选择数据输入的其中一个作为输出
  • 有字级形式 -> 类似 switch
  • HCL 中可以有允许不互斥的选择表达式, 但实际电路必须确保只有第一个满足的情况才会被选中
• 为了将组合电路时序化, 我们需要引入时钟信号
• 存储设备都是由同一个时钟控制的
  • 时钟寄存器存储单个位或字, 时钟信号控制寄存器加载输入值
  • 随机访问存储器存储多个字, 用地址来选择该读或该写哪个字 (包括内存与寄存器)
    • 寄存器文件属于随机访问存储器, 就是汇编中的寄存器
    • 寄存器文件有两个读端口和一个写端口, 可以同时读取两个寄存器 + 写入一个寄存器
    • 同时读写一个寄存器会读到一个变化

Y86-64 的顺序实现

• 我们构建一个非常简单的单周期指令硬件模型 SEQ
• 一条指令包括很多操作
  • 取指, 根据 PC 取指令, 并计算下一条指令的 PC
  • 译码, 从寄存器文件中读取操作数 (最多 \(2\) 个)
  • 执行, 执行指令, 并设置条件码
  • 访存, 读写内存 (我们不支持内存地址作为操作, 访存可以在执行后面)
  • 写回, 将结果写回寄存器文件 (最多 \(2\) 个)
  • 更新 PC
• 处理器从来不需要为了完成一条指令的执行而去读由该指令更新的状态
• 时钟控制程序寄存器与条件码寄存器就足够了
  • 寄存器文件与内存当在组合逻辑里

流水线的通用实现

• 非流水线就是让电走一会, 然后放在寄存器里
  • 把它拆成多阶段, 每个阶段都有自己的寄存器, 每个阶段的输出作为下一个阶段的输入
  • 显著扩大了吞吐, 但因为寄存器的时间开销, 延迟也会变大
• 实际设计流水线时如何均匀划分是一个很大的问题 (短板效应)
• 流水线技术显然有一个问题, 带反馈的指令会导致流水线改变系统行为 (使用的寄存器的值可能还未准备好)

Y86-64 流水线实现

• 一个重要的改进是, 将之前每个时钟周期最后计算程序计数器, 改到在下一个周期的开头当中去计算
  • 所以这回程序计数器连寄存器都没有了, 这种只保证可见, 不真正有实体的思想在底层还是很常见的, 比如说乱序执行
• 划分五级流水线, 并有五个流水线寄存器
  • 计算 PC 的预测值
  • F (Fetch) 保存 PC 的预测值
  • 取指
  • D (Decode) 保存刚刚取出的指令位
  • 译码
  • E (Execute) 保存译码后的数据
  • 执行
  • M (Memory) 保存执行结果
  • 访存
  • W (Write-back) 保存最终要写回寄存器文件的数据
  • 写回
• 信号命名系统的重设计
  • 大写前缀表示流水线寄存器 (上一周期产生并锁存的状态)
  • 小写前缀表示当前阶段逻辑电路刚刚计算出来产生的信号
• 当指令 \(I\) 到达写回阶段时, 译码阶段正在处理指令 \(I+4\), 如果直接用译码器的输出, 指令 \(I\) 的结果会被写入指令 \(I+4\) 指定的寄存器中
  • 必须让目的寄存器 ID (dstE 和 dstM) 跟随指令一起流动
• Select A 模块
  • 没有指令会同时需要从寄存器读出的 valA 和 valP
  • 所以去掉一个, 减少流水线寄存器的宽度 (流水线设计常见优化)
• PC 的预测
  • 由于执行一条指令的时候, 上一个指令还没结束, 不能确切知道下一个地址, 所以必须要分支预测
  • 如果说存在跳转的话呢总是预测会发生跳转 (\(60%\) 成功率)
  • 当分支预测失败的时候, 就取回正确的这个跳转值
  • 特殊的是 ret 指令的下一条, 必须需要访存才能知道跳转到哪所以会直接等待
• 还有一种分支预测策略 (\(65%\) 成功率)
  • 如果分支地址比下一条地址低就预测分支
  • 因为循环往往是前向跳转的而且它通常会执行多次
• 部分处理器会有一个专门用来预测返回地址的硬件栈 (对程序员不可见)

流水线冒险

• 数据冒险指当下一条指令需要上一条指令计算出的结果叫做
• 控制冒险指处理器无法根据当前取出的指令确定下一条指令的地址
• 数据冒险解决方案
  • 等待
    • 将指令阻塞在译码阶段
    • 向后续阶段插入气泡 (将流水线寄存器清零)
    • 非常慢
  • 数据转发
    • 之前的指令写回之前, 就将结果转发给后续指令
    • 在后续指令的即将执行的时候, 多路选择器会检查 E / M / W 这三个流水线寄存器
    • 非常快
    • 这样就支持之前的指令在执行后到写回前直接转发结果给后续指令的执行前
  • 但是, 如果两条指令紧紧跟随, 并且后续指令依赖于前一条指令的访存结果, 就不能转发
    • 暂停一周期即可
• 控制冒险解决方案
  • ret 指令必须访存才能知道返回地址, 所以必须等待三周期才能执行
    • 等待虽然会使 F 寄存器中的值不变但是取指不会停止呀
    • 所以需要在 D 阶段插入三个气泡将取来的指令删掉
    • 当 ret 在 D 阶段, E 阶段是 pushq %rsp, D 流水线寄存器同时发生了冒险暂停和气泡, 先暂停, 然后气泡, 这是连 CSAPP 作者第一遍都写出 bug 的事情
  • 条件跳转预测错误
    • 用气泡来取消后续指令
    • 浪费 2 个时钟周期

异常处理

• 流水线当中多个阶段同时出现异常显然是上报最深的
• 如果异常发生在错误预测的分支当中, 当然会消除这个异常
• 保证异常指令之后的所有指令都不能影响系统状态
• 实现方法
  • 当检测到异常时, 作为状态码跟着指令流动, 最终在写回阶段处理 (实现了 1, 2)
  • 同时立刻禁止全局的状态更新 (实现了 3)

未完成的工作

• 我们估算现在每周期能发射 \(- 27\) 条指令, 如果想进一步提升效率, 应该集中于更好的分支预测策略

• 多周期指令

  • 真正的处理器中有很多指令需要多个周期才能执行完成
  • 一个简单的解决方案是让这些指令在执行阶段停留多个周期
  • 另一种方案是让这些指令在执行阶段完成后, 进入一个专门的多周期指令缓冲区
  • 后续指令可以继续执行, 但是如果后续指令依赖于多周期指令的结果, 就必须等待
• 存储
  • 我们简化了存储系统, 真实系统中有多级缓存
  • 有些是只读的缓存, 有些是读写的缓存, 还有缓存的是虚拟地址到物理地址的翻译
  • 如果降级到内存都找不到的话他可能在磁盘当中, 这会触发一个缺页异常 (因为需要数百万个周期, 等不起)

优化程序性能

• 用每元素周期数来衡量程序性能
  • 元素指最小数据单元
• 妨碍优化因素
  • 内存别名使用, 指针可能指向相同的内存位置
  • 函数调用, 函数调用可能有副作用

消除妨碍编译器优化的障碍 (机器无关)

• 循环不变量应被提取到循环外部, 但编译器无法确定函数调用是否有副作用
• 每次获取数据时都进行边界检查可能会导致流水线预测错误
• 代码移动 / 循环不变量外提
  • 消除了重复的函数调用
• 直接数据访问
  • 消除了函数调用开销和边界检查
  • 令人惊讶的是性能实际上并没有提升, 因为他压根就不是瓶颈
  • 瓶颈在于你的循环内的每次复制都是往一个内存当中去写
• 引入临时变量
  • 消除了每次循环内对同一内存位置的读写
  • 并且这个优化看似很简单但实际上编辑器却没法帮你做
• 为什么编译器没法帮你做
  • 因为编译器无法确定指针是否会指向相同的内存位置
  • 也就是内存别名的问题
• O2 优化的话, 那么你就会发现编辑器能帮你做一点小事
  • 当他写回内存的时候不会再读取一次而是会使用上次写回的值

现代处理器

• 超标量与乱序执行
  • 超标量: 每个时钟周期可以发射和执行多条指令
  • 乱序执行: 只要数据准备好了, 指令就可以执行, 不必严格遵守代码编写的顺序
  • 投机执行: 遇到分支时, 处理器不等待判断结果, 而是利用分支预测先猜一个方向执行下去
• 延迟与吞吐量
  • 延迟: 完成一个运算需要的时间
  • 吞吐量: 单位时间内可以完成多少个运算
  • 优化的终极目标从延迟受限变成吞吐量受限
    • 也就是不因数据依赖而等待

机器相关的优化

• 循环展开
  • 一次循环当中处理多个元素
  • 减少循环控制开销, 但要更小心边界处理
  • 增加指令级并行性, 但是依旧有数据依赖关系
• 提高并行性
  • 多个累积变量, 满足结合率可以随便改变计算的顺序
  • 重新结合变换, 先计算非数据依赖部分
• 使用 SIMD 指令
  • 单指令多数据流, 一条指令操作多个数据
• 一些限制
  • 寄存器数量有限
  • 分支预测失败
    • 可以考虑让编辑器尽可能生成条件传送指令

内存性能

• 吞吐量大, 但是延迟高
  • 数组操作就可以并行化利用吞吐量 (易预测的内存访问模式)
  • 链表操作则受限于延迟
• 写操作通常看起来很快, 因为 CPU 使用了存储缓冲区 (而不是高速缓存 / 内存)
• 但写后读会导致严重的性能惩罚
  • 因为读操作必须检查存储缓冲区, 看看有没有未写入的数据需要转发 (连转发都没有就更吓人了)
  • 这会导致数据依赖链, 使得流水线停顿

存储器层次结构

• 读访问时间是局部性的一个函数

存储技术

存储器分类

• SRAM 静态随机存取存储器
  • 用六晶体管电路存储每一位数据
  • 双稳态
  • 用于高速缓存
• DRAM 动态随机存取存储器
  • 用电容存储每一位数据 (需要不停地刷新)
  • DRAM 有 \(d\) 个超单元 (字), 每个超单元有 \(w\) 个 DRAM 单元 (位)
  • 所有超单元按行列组织起来 (提高了延时但是降低了针脚数量)
  • 内存控制器需要提供行列, 分别是 RAS 和 CAS 信号
    • RAS 行地址选通信号, 会把一整行的所有超单元都移动到内部行缓冲区
    • CAS 列地址选通信号, 会选择行缓冲区当中的某个超单元
  • 用于主存
• FPM DRAM 快速页面模式 DRAM
  • 先提交一个行地址
  • 不修改行地址情况下想要访问多列, 只需一直提交列地址就行 (一直都在行缓冲区里)
  • EDO DRAM 扩展数据输出 DRAM, 允许在 CAS 信号频率更高
• SDRAM 同步动态随机存取存储器
  • 时钟同步, 可以在一个时钟周期内发出多个请求
  • 更快
  • DDR SDRAM 两个时钟沿作为控制信号
• VRAM 视频随机存取存储器
  • 双端口, 允许同时读写
  • 输出本质上是缓冲区一直位移
  • 用于图形适配器 (现代用 GDDR)
• ROM 只读存储器
  • 非易失性存储器
• PRAM 可编程只读存储器
  • 每个存储器有一个可被高电流熔断的熔丝
  • 可以编程但只能写一次
• EPROM 可擦除可编程只读存储器
  • 可以用紫外线擦除
  • 编程 \(1000\) 次
• EEPROM 电可擦除可编程只读存储器
  • 用电信号擦除
  • 编程 \(100,000\) 次
• flash 存储器
  • 一种 EEPROM
  • 擦除单位是块, 写入单位是字
  • 用于固态硬盘

存储设备

• 数据流通过总线在 CPU 和 DRAM 之间传输
  • 一次传输称为一次总线事务 (读或写)
  • 一次读事务
    • CPU 发出读请求, 包括地址和控制信号到 IO 桥
    • IO 桥将地址翻译为 DRAM 地址, 并发出 RAS 和 CAS 信号
    • DRAM 将数据发送回 IO 桥
    • IO 桥将数据发送回 CPU
• 磁盘对外表现为若干个扇区, 每个扇区 \(512\) 字节 (磁盘控制器维护映射到盘面, 磁道, 扇区)
• 这些 IO 设备通过对应控制器 / 直连连接到 IO 总线
  • IO 总线连接到 IO 桥
• CPU 使用内存映射 IO 来向设备发送命令
  • 地址空间中有一块地址是为与 IO 设备通信保留的 (端口)
  • 一次磁盘读
    • 发送一个命令字与其他的参数到磁盘的端口
    • 指明应该读的逻辑块号
    • 指明应该存储磁盘扇区内容的主存地址
    • 磁盘控制器将逻辑块号映射为物理地址
    • DMA 将数据从磁盘传送到主存
    • 传送完成后, 磁盘控制器向 CPU 发送一个中断
• SSD 的随机写很慢
  • 想修改一个页, 必须先擦除整个块
  • 而且经常会擦除有用的数据, 还得重新写回去

局部性

• 局部性就是程序重复访问相同 / 相邻的数据项集合的倾向 (时空)
• 循环体越小, 循环次数越多, 指令的局部性越好
• 重复引用相同的变量有很好的时间局部性
• 步长越小越好

存储器层次

• 每一层都保存着下一层取出的数据
  • 寄存器, 字
  • L1 缓存, 缓存行
  • L2 缓存, 缓存行
  • L3 缓存, 缓存行
  • 主存, 磁盘块
  • 磁盘, 远程网络服务器的文件
• 形式化的
  • 数据总是以块大小为传送单元在 \(K\) 与 \(K + 1\) 层之间传输
    • 需要时, 先在 \(K\) 层查找, 找到就命中
    • 否则就从 \(K + 1\) 层取回一个块 (不命中)
    • 并且替换 \(K\) 层的一个块
  • 一个空的缓存有时被称为冷缓存
    • 这时候不命中叫强制性不命中
  • 缓存的块放在哪必须有一个映射策略
    • 有时候缓存没有满, 但是因为策略的冲突导致一直不命中, 就叫做冲突不命中
  • 缓存太小导致当前阶段的工作集合大于缓存, 那么就是容量不命中

高速缓存存储器

• 定义: \((S, E, B, m)\)
  • \(m\) 物理地址总线宽度
  • \(S = 2^s\) 组数
  • \(E\) 每个组中的行数 (相联度)
  • \(B = 2^b\) 块大小 (每一行里存储的字节数)
  • \(C = S \times E \times B\) 总容量 (只算数据区, 不标记位)
• 块是真正的数据单元, 行是包含数据块和元数据 (有效位, 标记位) 的容器, 组是行的集合
• 缓存时将内存地址作为 key, 切割成三段
  • 标记, 存在行的元数据中
  • 组索引, 用于选择组 (策略性)
  • 块偏移, 用于选择块内字节 (策略性)

直接映射高速缓存

• 每个组只有一行
• 没有标记, 直接找就行
• 注意地址划分时用中间位做组索引
  • 高位会破坏空间局部性 (临近的内存老是进一个组)
• 但是依旧会冲突不命中 (抖动)
  • 解决办法是数组开大点

组相联高速缓存

• 一个组里有多个行
• 并行检查组内所有行的标记位
• 替换策略
  • 随机
  • LFU
  • LRU

全相联高速缓存

• 只有一组, 所有行都在这一组里
• 没有组索引位, 地址只分两部分
• 极少发生冲突不命中
• 但硬件极贵且慢

写操作

• 要保证缓存和主存的数据一致
• 写命中
  • 直写, 就是同时写缓存和主存
  • 写回, 只写缓存, 并把该行标记为脏, 只有当这行被驱逐时, 才写回主存 (时间局部性)
• 写不命中
  • 写分配, 先把块读入缓存, 然后再写 (空间局部性, 因为大概率马上会写旁边的字)
  • 非写分配, 直接写主存, 不进缓存
• 一般来说, 写命中用写回, 写不命中用写分配

真实硬件

• L1 缓存分为指令缓存和数据缓存
• L2 / L3 缓存通常是统一缓存
• 参数选择
  • 缓存越大命中率越高, 但越慢
  • 块越大空间局部性越好, 但冲突不命中率也会增加 (因为行数变少), 传送时间也会增加, 一般是 \(64\) 字节
  • 相连度越高冲突不命中率越低, 但硬件复杂且慢
    • L1 为了快, 相连度较低 (如 \(8\) 路)
    • L3 为了减少去主存的次数, 相连度较高 (如 \(16\) 路)

编写高速缓存友好的代码

• 让最常见的情况运行得快 (核心函数的关键循环)
• 尽量减小每个循环内部的缓存不命中数量
• 存储器山
  • 用步长描述空间局部性
  • 用工作集大小描述时间局部性
  • 用读吞吐量描述性能
• 我们看到
  • 工作集小于 \(32 KB\) 时,数据全在 L1 缓存, 读吞吐量极高 (\(~12 GB/s\))
  • 工作集稍大 (\(< 256 KB\)) 时, 溢出到 L2 缓存, 读吞吐量掉一半
  • 工作集更大 (\(< 8 MB\)) 时, 溢出到 L3 缓存
  • 工作集极大时, 只能去主存拿数据, 读吞吐量跌入谷底 (\(~900 MB/s\))
  • 步长越大 (跟块大小比), 读吞吐量越低
  • 即使数据量很大, 只要步长为 \(1\), 读吞吐量依旧很高 (CPU 硬件预取发挥作用)
• 重新排列循环使步长为 \(1\)
• 分块以提高时间局部性
  • 尽可能让工作集适应缓存大小
  • 认可做一些算法上没意义的分治

链接

• 目标文件
  • 可重定位目标文件 (编译器生成, 未完全链接)
  • 共享目标文件 (动态链接库, 在运行时加载)
  • 可执行目标文件 (链接器生成, 完全链接)
• 静态链接: 将一组可重定位目标文件生成一个完全链接的, 可以加载和运行的可执行目标文件
• 动态链接: 在程序运行时将共享目标文件加载到内存中, 并将它们链接到正在运行的程序
• 链接器的两大任务:
  • 符号解析: 将每个符号引用正好和一个符号定义关联起来
  • 重定位: 把每个符号定义与一个内存位置关联起来, 并修改所有对这些符号的引用

可重定位目标文件 (ELF 格式)

• ELF 头: 机器与文件的元数据
• 代码与数据
  • .text: 已编译程序的机器代码
  • .rodata: 只读数据, 如 printf 格式串, switch 跳转表
  • .data: 已初始化 (且非 \(0\)) 的全局变量和静态变量
  • .bss: 未初始化, 或初始化为 \(0\) 的全局变量和静态变量 (仅占位符, 不占用磁盘空间)
  • 还有很多
• 调试信息
  • .debug: 调试符号表, 程序中定义和引用的变量和类型定义, 源代码 (仅在 -g 时生成)
  • .line: 原始 C 源程序中的行号和 .text 节中机器指令之间的映射
• .symtab: 符号表, 存放在程序中定义和引用的函数和全局变量的信息
  • 包含符号所在节的索引 (st_shndx): 指向节头部表的索引
    • SHN_UNDEF (0): 未定义符号 (其它模块定义)
    • SHN_ABS (0xfff1): 绝对符号 (不受重定位影响)
    • SHN_COMMON (0xfff2): COMMON 符号, 未分配位置的未初始化数据 (不知道是否在别的模块定义)
• .rel.text / .rel.data: 重定位信息, 存放链接时需要修改的代码和数据位置
• .strtab: 字符串表, 存放符号表 / 节头部表中使用的字符串
• 节头部表: 节在文件中的组织方式与节本身的元数据

符号解析

• 局部符号不用管, 编译器保证唯一
• 支持函数重载的语言需要名字重整
• 解析多重定义的全局符号
  • 强弱符号规则
    • 强符号: 函数, 已初始化的全局变量
    • 弱符号: 未初始化的全局变量
  • 不允许多个同名强符号
  • 一个强符号覆盖多个弱符号
  • 多个弱符号时任选一个 (一般选最大的)
• int x = 1; + double x; 会导致链接器选择 int x (强符号), 但 double x 会把 x 当作 double 使用, 导致严重错误
  • 使用 -fno-common: 禁用弱符号 (放进 .bss)
  • 使用 -Werror: 把警告变报错

静态库链接

• 链接的时候 .o 太多, 合并写在一起又太大
• 静态库 (.a) 是将多个 .o 打包成一个文件
  • 通过头部索引来定位每个 .o
  • 链接器只会复制被引用的 .o 进可执行文件

链接器的扫描算法

• 链接器按从左到右的顺序扫描命令行参数
• 维护三个集合
  • E: 将被合并到输出文件的目标文件集合
  • U: 当前引用了但未找到定义的符号集合
  • D: 当前已经找到定义的符号集合
• 链接器执行以下步骤
  • 对于每个输入文件, 如果是目标文件, 将该文件加入 E, 更新 U 和 D
  • 如果是库文件, 遍历库中的成员, 如果某个成员定义了 U 中的符号, 将该成员加入 E, 更新 U 和 D
    • 重复扫描库, 直到 U 和 D 不再变化
    • 丢弃库中未被使用的其他成员
  • 扫描结束后, 如果 U 非空, 报错 undefined reference
• 根据该流程, 链接时必须注意命令行顺序
  • 引用符号的文件必须放在定义符号的库之前
  • 如果有循环依赖的库, 必须重复写
    • gcc foo.c libx.a liby.a libx.a

重定位

• 给每个符号分配最终的运行时内存地址, 并修改代码中的引用, 使其指向正确的地址
• 重定位节和符号定义
  • 将所有输入模块中相同类型的节合并
  • 根据合并后的结果, 为每个节和每个符号分配唯一的运行时内存地址
• 重定位节中的符号引用
  • 遍历代码和数据, 找到所有对外部符号的引用, 将其修改为上一步分配好的实际地址 (依赖于重定位条目)
• 重定位条目
  • offset: 需要修改引用的位置 (在节内的偏移)
  • type: 重定位类型 (绝对地址 vs 相对地址)
  • symbol: 符号表索引 (指向哪个符号)
  • addend: 一个常数修正值 (用于计算偏移)
• 重定位类型
  • 相对寻址: \(\text{目标地址} + \text{修正值} - \text{引用自身的运行时地址}\) (修正值用于调整 PC 自动加的偏移)
  • 绝对寻址: \(\text{目标地址} + \text{修正值}\) (修正值用于让编译器表达特定的偏移的语义)

可执行目标文件

• 多个节被以方便加载的方式逻辑上合并
• 元数据 (不加载)
  • ELF 头依旧, 包含程序的入口点
• 代码段 (只读可执行)
  • .text
  • .rodata
  • .init
  • .plt (动态链接相关)
• 数据段 (可读写不可执行)
  • .data
  • .bss
  • .got (动态链接相关)
• 调试与分析用的信息 (可用 strip 去掉)
  • 调试用的
  • 静态链接时用的重定位表与符号表
• 动态链接相关的信息 (不加载, 但也不能去掉)
  • .interp: 指向动态链接器路径的字符串
  • .dynamic: 动态链接信息
• 节头部表仍然保留, 用于分析 (不加载, 可被部分去掉)
• 程序头部表, 标记段是否加载到内存与权限
• 段在文件中的偏移量对页大小取余应等于段在内存中的虚拟地址对页大小取余
  • 服务惰性加载
• execve 系统调用会由加载器执行以下步骤
  • 读取可执行文件的 ELF 头, 验证文件格式
  • 读取程序头部表, 确定需要加载的段
  • 将文件的段映射到虚拟内存 (并没有真正分配物理内存)
  • 初始化 .bss 段对应的内存区域为 \(0\)
  • 设置栈, 包括传递给程序的命令行参数和环境
  • 跳转到程序的入口点 (_start -> __libc_start_main -> main)
  • 访问缺页时, 操作系统分配物理内存并将数据从磁盘读入内存
• 内存布局
  • 代码段
  • 数据段
  • 堆 (向高地址增长)
  • 共享库映射区
  • 用户栈 (向低地址增长)
  • 内核区域 (不可见)

动态链接共享库

• 静态库有两个主要缺陷
  • 更新麻烦: 库更新了, 所有使用它的程序都需要重新编译链接
  • 浪费内存: 常用的库的代码会被复制到每个进程的内存中
• 共享库解决了这些问题
  • 磁盘共享: 文件系统中只有一个 .so 文件, 所有程序引用它
  • 内存共享: 代码段（.text）在物理内存中只有一份, 被多个进程映射共享
• 编译: 使用 -fpic (生成位置无关代码)和 -shared(生成共享库`)
  • gcc -shared -fpic -o libvector.so addvec.c multvec.c
• 链接: 链接器只复制符号表和重定位信息, 不复制实际代码
  • gcc -o main main.c libvector.so
• 当动态链接程序启动时, 加载器会自动加载所需的共享库并完成重定位
  • 通过 ldd main 可以查看程序依赖的共享库
• 也可以使用系统调用在运行时加载共享库
  • dlopen: 打开共享库, 返回句柄
  • dlsym: 根据名字查找符号的地址
  • dlclose: 卸载库
  • dlerror: 获取错误信息

位置无关代码 (PIC)

• 同一个共享库会被映射到不同进程的不同虚拟地址, 所以代码不能包含任何绝对地址
  • 在数据段中建立全局偏移量表 (GOT), 存放全局变量的绝对地址
  • 代码段引用变量时, 通过 PC 相对寻址找到 GOT 中的条目 (跳转一下)
  • GOT 进程私有, 可写, 动态链接器在加载时填入真实地址
• 但是这样进程初始化太慢了
  • 延迟绑定: 只有在函数第一次被调用时, 才去解析它的地址
  • 通过加一个过程链接表 (PLT) 实现
    • 因为原本 GOT 是数据, 不可执行
    • 拿名义上是表, 实际上是一组小代码的 PLT 封装上
  • 程序直接调用 PLT 条目, PLT 条目跳转到 GOT 条目, GOT 条目存放函数地址
  • 第一次调用时, GOT 条目指向 PLT 的下一条指令, PLT 会调用动态链接器 (PLT[0]) 解析地址并更新 GOT
• 实际上现在都是动态重定位, 所有能相对寻址的都相对寻址
  • 外部变量和函数都通过 GOT 和 PLT 访问
  • 绝对寻址只出现在运行时, 已经被重定位

库打桩

• 截获对共享库函数的调用, 并执行自定义代码
• 编译时打桩: 代码里实现类似代理模式的机制
• 链接时打桩
  • 不需要源代码, 但需要重新链接
  • --wrap name 标志
  • 会让对 name 的引用变成对 __wrap_name 的引用 (你写一个 __wrap_name 函数覆盖)
  • 而你想调用真正的 name 时, 调用 __real_name
• 运行时打桩
  • 设定环境变量 LD_PRELOAD, 其指定的共享库会在其他库之前被加载
  • 你在这个库中实现函数, 动态链接器会优先使用它
  • 想调用原函数时, 使用 dlsym(RTLD_NEXT, "name") 获取原函数地址

处理目标文件的工具

• ar: 创建静态库
• strings: 列出文件中的可打印字符串
• strip: 删除符号表信息
• nm: 列出符号表中的符号
• size: 列出各节的大小
• readelf: 显示 ELF 文件结构
• objdump: 反汇编机器指令 objdump -d
• ldd: 列出可执行文件需要的共享库

异常

• 异常是指任何改变程序正常顺序执行的事件
  • 陷阱: 程序执行特定指令时故意产生的同步异常 (系统调用)
    • 目的是利用硬件机制, 如特权级转换, 来执行受保护的操作
  • 中断: 来自外设的异步异常 (时钟中断)
  • 故障: 程序错误引起的同步异常 (缺页中断)
  • 终止: 严重错误引起的异常, 不能被处理

信号

• 软件中断, 由内核或其它进程通知进程某个事件发生
• 信号的生命周期
  • 发送: 内核更新目标进程上下文中的状态
  • 待处理: 信号已发出但尚未被接收处理
    • 信号不会排队, 任何时刻, 一种类型的信号至多只有一个待处理 (后续到达的会被丢弃)
  • 接收: 目标进程对信号做出反应 (忽略, 终止或执行处理程序)
    • 当内核把进程从内核模式切换回用户模式时会检查待处理信号集合
  • 进程可以显式地阻塞某些信号, 使其一直处于待处理状态
    • SIGKILL 和 SIGSTOP 不能被阻塞, 忽略或捕获
• 信号数据结构
  • 信号本身是位图, 每一位代表一种信号类型
  • 用于阻塞信号的掩码也是位图

发送信号的机制

• 每个进程属于一个进程组, 进程组内的所有进程可以接收发送给该进程组的信号
  • getpgid(pid) / setpgid(pid, pgid): 获取 / 设置进程的进程组 ID
• Shell 中的作业控制使用进程组来区分前台作业和后台作业
• 键盘发送信号给前台进程组
  • Ctrl+C: 发送 SIGINT (中断)
  • Ctrl+Z: 发送 SIGTSTP (挂起)
• 命令行工具发送信号
  • kill -9 15213: 发送信号 9 给进程 15213
  • kill -9 -15213: 发送信号 9 给进程组 15213 中的所有进程 (负数代表进程组)
• 函数调用发送信号
  • kill(pid, sig): 发送信号给其他进程
  • alarm(secs): 给自己发送 SIGALRM (闹钟)
    • 默认行为是终止进程

接收与处理信号

• 当内核发现有未被阻塞的待处理信号时, 强制进程接收
• 进程可以通过 signal() (有兼容性问题) 或 sigaction() (标准 POSIX) 函数修改默认行为
  • SIG_IGN: 忽略信号
  • SIG_DFL: 恢复默认行为
  • 捕获信号: 指定一个信号处理程序
• sigprocmask: 显式地阻塞或解除阻塞信号
• 当处理程序正在处理信号 s 时, 内核会自动阻塞后续的 s 信号, 防止递归处理
• 安全性规则
  • 处理程序越简单越好
  • 只能调用异步信号安全的函数 (无锁, 无静态数据)
    • 可重入函数 + 死锁免疫
  • 保存和恢复 errno (防止破坏主程序的错误状态)
  • 保护共享数据 (访问全局数据结构时, 阻塞所有信号)
  • 使用 volatile 和 sig_atomic_t (防止编译器优化和非原子操作)
• 针对信号不排队, 在处理程序中默认使用循环检查所有可能来源
  • 例如多个子进程几乎同时结束, 发送多个 SIGCHLD
• 信号像极了条件变量, 对其的并发保护应该类似
• 显式等待信
• 号
  • while (!flag) pause(); (有并发问题)
  • while (!flag) sleep(1); (效率低)
  • sigsuspend(&mask); (正确解法, 原子操作)

非本地跳转 (现代语言异常的实现思想)

• int setjmp (jmp_buf env): 保存当前执行环境 (寄存器, 栈指针)
  • 返回值不可赋给变量, 只能直接用在条件判断中
• int longjmp (jmp_buf env, int val): 恢复到最近的 setjmp 保存的执行环境, 并使 setjmp 返回 val
  • 跳过的逻辑没人保证会被执行, 所以要小心资源泄漏
• 可以用来当作轻量级的异常处理机制
  • setjmp 放在可能抛出异常的代码前面
  • longjmp 放在抛出异常的地方
  • 这样就能跳过中间的代码, 直接回到 setjmp 处处理异常
• 信号处理程序运行结束后, 控制流会返回到被中断的指令处继续执行
  • 但使用非本地跳转, 我们可以让程序从信号处理程序直接跳转到代码的任意位置, 从而实现重置状态或重启任务的效果
  • sigsetjmp 和 siglongjmp 是 setjmp 和 longjmp 的增强版, 专门用于信号处理场景
  • 会保存和恢复信号屏蔽字, 防止信号被永久阻塞 (进入信号处理程序时该信号会被自动阻塞)
• 信号处理时的关键
  • 必须先调用 sigsetjmp 保存环境, 再注册信号处理程序 (防止出现未 setjmp 就 longjmp 的竞态条件)
• siglongjmp 并没有被列在官方的异步信号安全函数列表
  • 如果在信号处理程序中调用 siglongjmp 跳过了主程序中的非安全函数, 可能会破坏程序状态 (跳过锁的释放导致死锁)

操作进程的工具

• strace: 跟踪系统调用
• ps: 显示运行中进程, 包括僵尸进程
• top: 实时显示系统中运行的进程的资源使用情况
• pmap: 显示进程的内存映射
• /proc 文件系统: 提供内核数据结构的视图, 如 /proc/[pid]/maps 显示进程内存映射

虚拟内存

• void *mmap(void *addr, size_t length, int prot, int flags, int fd, off_t offset);
  • addr: 建议的映射起始地址 (通常为 NULL, 让内核选择)
  • length: 映射的字节数
  • prot: 内存保护标志
    • PROT_READ: 可读
    • PROT_WRITE: 可写
    • PROT_EXEC: 可执行
    • PROT_NONE: 不可访问
  • flags: 映射选项
    • MAP_SHARED 与 MAP_PRIVATE 二选一: 共享还是写时复制
    • MAP_ANONYMOUS: 不映射文件, fd 应为 -1
    • MAP_FIXED: 强制映射到 addr 指定的地址
  • fd: 文件描述符 (如果映射文件, 否则为 -1)
  • offset: 文件映射的起始偏移量 (必须是页面大小的整数倍)
  • 返回值: 映射区域的起始地址, 失败时返回 MAP_FAILED ((void *) -1)
• mmap() 使用场景
  • MAP_ANONYMOUS|MAP_PRIVATE 用于分配大块内存 (如大数组, 共享内存)
  • 映射文件到内存, 方便随机访问大文件
  • MAP_SHARED 用于进程间通信
• 其实操作系统也是这么干的
  • 例如 fork() 时, 写时复制父进程的内存页
  • 加载可执行文件时, 映射代码段和数据段到内存
  • 分配堆栈空间时, 映射一块匿名内存

系统级 I/O

• 文件描述符表是每个进程私有的
• 输入输出文件时, 可能出现不足值
  • 例如从网络套接字读取数据时, 可能只读到部分请求的数据
  • 向套接字或管道写数据时, 可能只写入部分数据 (内核缓冲区满)
  • 程序必须检查返回值, 并在需要时继续读取剩余数据
• 封装标准 I/O
  • 无缓冲输入输出时如果不足, 循环读取直到满足请求或出错
  • 提供带缓冲的输入, 减少系统调用次数 (支持多线程)
• 如果 open 同一个文件两次, 会有两个文件表项 (因为每个都有独立的读取位置)
  • fork 会复制父进程的文件描述符表, 文件表项是共享的
• dup2(oldfd, newfd): 复制文件描述符
  • 如果 newfd 已经打开, 先关闭它
  • 然后让 newfd 指向 oldfd 指向的文件表项
  • 返回 newfd, 失败时返回 -1
• C 语言标准 I/O 是有缓冲的, 读写切换依赖 fseek
  • 所以不适用于不可 fseek 的 Socket

网络编程

• 略

并发编程

基于进程的并发编程

• 父进程监听连接, 每次 accept 后 fork 一个子进程处理请求
• 套接字的文件表项被父子进程共享, 应有引用计数机制, 决定何时关闭连接
• 需要处理僵尸进程 (注册 SIGCHLD 处理程序)
• 隔离性好, 但是数据共享困难且开销大

基于 I/O 多路复用的并发编程

• 略

基于线程的并发编程

• 略

线程安全函数

• 四类线程不安全函数
  • 不保护共享变量 -> 加锁
  • 依赖跨调用状态 -> 重写函数, 由调用者传递状态
  • 返回指向静态变量的指针 -> 加锁-复制技术, 或使用可重入版本
  • 调用线程不安全函数 -> 加锁或重写
• 可重入函数是线程安全函数的一个真子集
  • 不引入任何共享数据
  • 参数传值或保证单一持有权