Lecture 1: 课程概述与计算机系统漫游 (Course Overview; A Tour of Computer Systems)

目录 · ← l0 · l2 →

第二部分 · 分讲学习笔记

Lecture 1: 课程概述与计算机系统漫游 (Course Overview; A Tour of Computer Systems)

讲义对应：CMU 15-213 Lecture 1 — Course Overview（素材：F25-01-overview.txt） 教材对应：CS:APP3e 第 1 章（1.1–1.10） 关联 Lab：无直接关联（但为 L0 C Programming Lab 及全部 lab 建立环境认知）

1.1 概述

本讲回答两个问题：这门课是干什么的，以及一个 C 程序从磁盘上的文本到屏幕上的一行输出，中间发生了什么。课程主题是”系统知识就是力量”：理解硬件与软件（操作系统、编译器、库、网络协议）如何协同支撑应用程序的执行。本讲先给出五大现实，再用 hello 程序的生命周期把后续 24 讲串成一条线。承接先修课 15-122，通向 Lecture 2 的信息表示与 Lecture 3 起的机器级编程。

1.2 核心概念与底层机制图解

1.2.1 课程定位与五大现实（Course Theme & Five Realities）

• 定义与目的：这是一门 programmer-centric（程序员视角） 的系统课，而非 builder-centric（构建者视角）。体系结构课让你用 Verilog 设计流水线处理器，操作系统课让你实现 OS 的一部分，编译器课让你写一个简单语言的编译器——它们都在”造”系统。15-213 回答的是：我写的这行 C 代码，在真实机器上会变成什么、跑多快、什么时候会错。

• 直观解释（”它是什么？”）：多数 CS/CE 课程强调抽象——抽象数据类型、渐近分析。抽象是好的，但别忘了抽象下面的现实。像开车不必懂发动机原理，但车在高速上抛锚时，你会希望自己知道”仪表盘亮红灯”意味着什么。

• 五大现实（Great Realities），它们同时是本课程五大板块的动机：

• 现实 #4 的量化证据：同一台 2.0 GHz Intel Core i7 Haswell 上，把 $2048\times2048$ 的 int 矩阵从 src 复制到 dst，仅循环顺序不同就差近 19 倍：

  for (i...) for (j...) dst[i][j] = src[i][j];   /* copyij: 按行遍历 */   4.3 ms
  for (j...) for (i...) dst[i][j] = src[i][j];   /* copyji: 按列遍历 */  81.8 ms

两者指令条数与渐近复杂度（同为 $O(n^2)$）几乎一样，但 copyji 每次访存跨过一整行（$2048\times4 = 8192$ 字节），空间局部性极差，几乎每次都缓存不命中（cache miss）。与硬件的对应：dst[i][j] 编译后是带比例变址寻址的 movl（如 movl (%rdi,%rax,4), %ecx），硬件对每次访存都向缓存层次发起请求，命中与否决定这条指令花 4 个周期还是 200 个周期。详见 Lecture 9、Lecture 10。

1.2.2 计算机系统漫游：hello 程序的完整生命周期（A Tour of Computer Systems）

• 直观解释（”它是什么？”）：把一个 C 程序想象成一份多语言交接的快递包裹：写于中文（C 源程序），译成英文（汇编程序），打包成二进制（机器码），拼在一起（链接），装上卡车（加载）。

• 底层机制图解：hello.c 是只由 ASCII 字符组成的文本文件，必须被翻译成二进制机器码才能执行。这条流水线叫编译系统（compilation system）：

  hello.c  (源程序, 文本)
          |
          v
       +----------------------------------+
       | 预处理器 (Preprocessor)          |
       | cpp: 展开 #include / #define     |
       +----------------------------------+
  hello.i  (修改后的 C 源程序, 文本)
          |
          v
       +----------------------------------+
       | 编译器 (Compiler)                |
       | cc1: C 源程序 -> 汇编程序        |
       +----------------------------------+
  hello.s  (汇编程序, 文本)
          |
          v
       +----------------------------------+
       | 汇编器 (Assembler)               |
       | as: 汇编程序 -> 可重定位目标文件 |
       +----------------------------------+
  hello.o  (可重定位目标程序, 二进制)
          |
          v
       +----------------------------------+
       | 链接器 (Linker)                  |
       | ld: 符号解析 + 重定位            |
       +----------------------------------+
  hello    (可执行目标程序, 二进制)

• 四个阶段的职责：
  1. 预处理阶段（preprocessing phase）：预处理器（cpp）根据 # 命令修改源程序：#include <stdio.h> 把系统头文件内容直接插入，#define 做宏替换，得到另一个 C 程序 hello.i。
  2. 编译阶段（compilation phase）：编译器（cc1）把 hello.i 翻译成汇编程序 hello.s，高级语言的控制结构在此展开为跳转与调用。
  3. 汇编阶段（assembly phase）：汇编器（as）把 hello.s 翻译成机器语言指令，打包成可重定位目标程序（relocatable object program） hello.o；其中的机器码还不知道自己最终会被放在哪个地址。
  4. 链接阶段（linking phase）：链接器（ld）把自己的 hello.o 与标准库中所需的目标文件（如 printf.o）合并，完成符号解析（symbol resolution）与重定位（relocation），得到可执行目标程序 hello。详见 Lecture 7。
• 与机器码/硬件的对应：hello.i、hello.s 仍是文本，只有 hello.o 与 hello 是二进制。运行时 CPU 从程序计数器（PC, Program Counter）指出的地址取指令、译码、执行，再更新 PC——”运行程序”就是硬件不断重复”取指—译码—执行”。

1.2.3 计算机硬件组成（Hardware Organization）

• 直观解释（”它是什么？”）：把计算机看成一座图书馆：总线是走廊，I/O 设备是收发室和复印机，主存是书架，CPU 是那位跑得飞快但记性只有巴掌大的馆员——他必须不断往返书架取书。

• 底层机制图解：

+------------------------------------+
| CPU 处理器                         |
|    PC  程序计数器                  |
|    寄存器文件 (register file)      |
|    ALU 算术/逻辑单元               |
+------------------------------------+
      ^   load/store: 寄存器 <-> 主存
      |
+------------------------------------+
| 系统总线 (System Bus)              |
|    地址总线 / 数据总线 / 控制总线  |
+------------------------------------+
      |
      v   DMA: 磁盘 <-> 主存 (不经 CPU)
+------------------------------------+
| I/O 设备与控制器                   |
|    键盘/鼠标   显示器              |
|    磁盘控制器   网络适配器         |
+------------------------------------+

• 四大部件：
  • 总线（Bus）：贯穿系统的电子管道，在部件之间传送定长的字节块（字，word）。x86-64 上字长 8 字节。
  • I/O 设备（I/O Devices）：系统与外部世界的通道（键盘、鼠标、显示器、磁盘、网卡）。每个设备经由控制器（controller）或适配器（adapter）接到总线。所有 I/O 设备都通过文件（file）这一抽象被访问。
  • 主存（Main Memory）：执行程序时存放程序与数据的临时设备。物理上由一组 DRAM（Dynamic Random Access Memory）芯片组成，逻辑上是一个线性字节数组，每个字节有唯一地址。
  • 处理器（CPU, Central Processing Unit）：解释（执行）主存中指令的引擎。核心是程序计数器（PC），任何时刻指向主存中某条机器语言指令；另有寄存器文件（register file）——少量定长寄存器组成的、小而快的存储设备，以及 ALU（算术/逻辑单元）。CPU 反复执行加载、存储、操作、跳转这几类动作。
• hello 的读写路径：shell 执行 linux> ./hello 后发生两件事，注意两条路径的发起者不同：

步骤 A: 加载 —— DMA 直接存储器访问, 不经 CPU 寄存器
   +------------------------------+
   | 磁盘 (Disk)                  |
   |   hello 可执行文件           |
   +------------------------------+
        |  DMA 读
        v
   +------------------------------+
   | 总线 (Bus)                   |
   +------------------------------+
        |
        v
   +------------------------------+
   | 主存 (Main Memory)           |
   |   hello 的机器码与数据       |
   +------------------------------+

步骤 B: 写出 —— CPU 执行 hello, 把字节送到显示器
   +------------------------------+
   | 主存 (Main Memory)           |
   |   "hello, world" 字节        |
   +------------------------------+
        |  寄存器 <- 主存 (load)
        v
   +------------------------------+
   | 总线 (Bus)                   |
   +------------------------------+
        |
        v
   +------------------------------+
   | 显示适配器 -> 显示器         |
   |   输出 hello, world          |
   +------------------------------+

加载时 shell 调用加载器（loader） 把 hello 的代码和数据从磁盘直接复制到主存，由 DMA（Direct Memory Access，直接存储器访问）完成，不经 CPU 寄存器。随后 CPU 执行 main 的机器码，把字符串从主存加载（load）到寄存器，再存储（store）到显示适配器。

1.2.4 存储层次结构（The Memory Hierarchy）

• 定义与目的：存储层次结构用层次化的组织弥合 CPU 与主存之间不断扩大的速度差距——越靠近 CPU 越小、越快、每字节越贵；越远则越大、越慢、越便宜。

• 直观解释（”它是什么？”）：像一位作家的书桌：便利贴是寄存器，桌面摊开的是 L1/L2/L3 缓存，书架是主存，图书馆书库是本地磁盘，网上图书馆是远程存储。每一层都是下一层的缓存（cache）——书架上放的就是书库里你以为会用到的一小部分。

• 底层机制图解（数值取教材 Figure 6.23 口径）：

                              +-----------------------------------------------------------------------+
                              | L0  寄存器 (Registers)          < 1 KB / 0 周期            4-8 字节字 |
                              +-----------------------------------------------------------------------+
                         +-----------------------------------------------------------------------+
                         | L1  L1 d-cache (SRAM, 片内)     32 KB / 4 周期             64 字节块  |
                         +-----------------------------------------------------------------------+
                    +-----------------------------------------------------------------------+
                    | L2  L2 cache (SRAM, 片内)       256 KB / 10 周期           64 字节块  |
                    +-----------------------------------------------------------------------+
               +-----------------------------------------------------------------------+
               | L3  L3 cache (SRAM, 片内共享)   8 MB / 40 周期             64 字节块  |
               +-----------------------------------------------------------------------+
          +-----------------------------------------------------------------------+
          | L4  主存 (Main Memory, DRAM)    8 GB / 100 周期            4-KB 页    |
          +-----------------------------------------------------------------------+
     +-----------------------------------------------------------------------+
     | L5  本地磁盘 (Local Disk)       1 TB / 10,000,000 周期     文件块     |
     +-----------------------------------------------------------------------+
+-----------------------------------------------------------------------+
| L6  远程存储 (Remote Storage)   inf / 1,000,000,000 周期   网页/文件  |
+-----------------------------------------------------------------------+

• 基本思想：对每个 $k$，第 $k$ 层更快更小的设备充当第 $k+1$ 层更大更慢设备的缓存。它之所以有效，是因为局部性（locality）：程序倾向访问最近用过的数据（时间局部性，temporal locality）及其邻近地址（空间局部性，spatial locality），故访问第 $k$ 层的频率远高于第 $k+1$ 层。
• 理想中的”大创意”：存储层次创造出一个巨大存储池，价格接近底部最便宜的存储，却以顶部最快存储的速度向程序提供数据。
• 量级感：从 L1 的 4 周期到磁盘的 10,000,000 周期跨越 6 个数量级。若把一次 L1 命中比作 1 秒，一次磁盘访问相当于 29 天。缓存组织（$C=S\times E\times B$、$s=\log_2 S$、$b=\log_2 B$、$t=m-s-b$）与局部性利用详见 Lecture 9、Lecture 10。

1.2.5 操作系统：硬件与应用的中间层（Operating System as Intermediary）

• 定义与目的：应用程序不直接操作硬件，而通过操作系统（Operating System）使用硬件。OS 有两个基本功能：防止硬件被失控的应用程序滥用，以及向应用程序提供简单一致的机制来控制复杂而大相径庭的低级硬件设备。

• 直观解释（”它是什么？”）：OS 像酒店前台。你不必知道锅炉房怎么烧水，只要说”我要一间房”“我要洗衣服”。前台既保证其他客人不闯进你的房间（保护），也把五花八门的后台流程统一成几个简单服务（抽象）。

• 底层机制图解：

+--------------------------------------------------------------+
| 应用程序 (Application Programs):  hello, shell, browser, ... |
|--------------------------------------------------------------|
| 操作系统 (Operating System)                                  |
|    文件 (file)          : 对 I/O 设备的抽象                  |
|    虚拟内存 (virtual memory) : 对主存 + 磁盘的抽象           |
|    进程 (process)       : 对处理器/主存/I/O 的抽象           |
|--------------------------------------------------------------|
| 处理器  主存  I/O 设备  网络                                 |
+--------------------------------------------------------------+

• 三大抽象：
  • 文件（file）：对 I/O 设备的抽象。每个 I/O 设备都被模型化为一个文件，所有输入输出都可通过读写文件完成。详见 Lecture 18。
  • 虚拟内存（virtual memory）：对主存和磁盘的抽象，为每个进程制造”独占使用主存”的假象；虚拟地址由硬件地址翻译机制映射到物理内存，未使用的部分可暂存在磁盘。详见 Lecture 11、Lecture 12。
  • 进程（process）：对处理器、主存和 I/O 设备的抽象，即”一个正在运行的程序”；一个系统可同时运行多个进程，每个都好像独占硬件。并发运行指两个进程的指令交错执行，需要上下文切换（context switch）。详见 Lecture 16、Lecture 17。
• 与机器码/硬件的对应：hello 调用 printf 最终落到 write 系统调用——一条把控制权从用户态交给内核态的指令；内核再通过设备驱动与 I/O 控制器打交道。

1.2.6 抽象：ISA 与并行的三个层次（Abstraction; Concurrency & Parallelism）

• ISA（Instruction Set Architecture，指令集架构）：对实际处理器硬件的抽象，规定指令、寄存器、寻址方式与行为语义，而把流水线级数、乱序执行、分支预测等微架构细节隐藏起来。直观解释：ISA 就像汽车的驾驶接口——方向盘、油门、刹车；不同厂家、不同排量的车共用同一接口，会开车的人能开任何一辆。只要遵循同一 ISA，同一份机器码就能在不同微架构的 Intel/AMD 处理器上正确运行。虚拟机（virtual machine）进一步把整台计算机（含操作系统）抽象成软件对象。并行有三个层次：
  1. 线程级并发（thread-level concurrency）：在进程抽象之上构建线程（thread）抽象。单处理器系统上的并发是模拟出来的（快速切换，任一时刻只执行一个线程，这种交错叫并发 concurrency）；多处理器系统（multiprocessor）中一个 OS 内核控制多个 CPU，各 CPU 有独立的 PC、寄存器文件与 L1/L2 缓存（共享 L3 与主存），可真正并行（parallel）；超线程（hyperthreading）在单个物理核上运行多个逻辑控制流，硬件复制指令控制单元（PC、寄存器文件、操作队列）但共享功能单元（整数/浮点运算单元、load/store 单元、数据缓存），典型 $K=2$。讲义的 shark 机器是 Intel Xeon E5520（Nehalem，约 2010 年），8 核 × 2 路超线程可同时执行 16 个线程，理论上限 16 倍加速比，但从未在实测中达到。
  2. 指令级并行（ILP, Instruction-Level Parallelism）：处理器可同时执行多条指令，通过流水线（pipelining）让不同指令的不同阶段重叠。乱序（out-of-order）处理器把程序动态转换成操作流，再映射到多个功能单元上并行执行。讲义指出：写操作耗时长，处理器会先缓存写、让读操作先走——这正是多核内存一致性问题的来源之一。
  3. 单指令多数据并行（SIMD, Single Instruction Multiple Data）：一条指令对向量的多个数据元素同时做同一运算，适用于图像/音频/科学计算等向量化场景。详见 Lecture 24。

1.2.7 Amdahl 定律（Amdahl’s Law）

• 定义与目的：把系统某一部分加速 $k$ 倍后，整体能快多少？Amdahl 定律给出严格上限，并揭示一条残酷结论：串行部分是性能改善的天花板。

• 直观解释（”它是什么？”）：讲义的旅行类比很清晰。从匹兹堡（PIT）直飞伦敦（LHR）要 7.5 小时。若先坐喷气机到纽约（JFK）花 1.5 小时，再坐协和式客机（SST）飞伦敦花 3.5 小时，共 5 小时，加速比 1.5 倍。若改用超光速飞船（FTL）飞越大西洋只需 0.01 小时，总时间仍是 $1.5+0.01=1.51$ 小时，加速比约 5 倍——即使大西洋段无限快，你也必须先花 1.5 小时到纽约。

• 公式：设 $T$ 为问题所需的总顺序执行时间，$p$ 为可被加速部分所占比例（$0 \le p \le 1$），$k$ 为该部分的加速倍数（$k>0$），则加速后总时间为

  \[T_k = \frac{pT}{k} + (1-p)T\]

  即”可加速的部分快 $k$ 倍，不可加速的部分原封不动”。整体加速比为

  \[S(p,k) = \frac{T}{T_k} = \frac{1}{(1-p) + \dfrac{p}{k}}\]

  令 $k \to \infty$ 得到最大可能加速比 $S_{\max} = S(p,\infty) = \dfrac{1}{1-p}$，此时 $T_\infty = (1-p)T$。该上限与并行资源多少无关，反映的是算法本身的局限性。

• 讲义原例：$T=10$，$p=0.9$，$k=9$。$T_9 = 0.9\times10/9 + 0.1\times10 = 1.0+1.0 = 2.0$，即5 倍加速比（注意不是 9 倍！）。最大加速比 $T_\infty = 0.1\times10.0 = 1.0$，即 10 倍——使用无穷多并行资源也只能到 10 倍。
• 推论与陷阱：
  • 加速比对 $k$ 的边际收益递减：$p=0.9$ 时 $k$ 从 4 提到 16，$S$ 只从 3.08 涨到 6.40。
  • $p$ 比 $k$ 更重要：同样 $k=16$，$p=0.99$ 时 $S=13.91$，$p=0.50$ 时 $S=1.88$。
  • 并行 quicksort 的教训：顶层划分（partition）无法并行，第二层最多 2 倍，第 $k$ 层最多 $2^{k-1}$ 倍；要大规模并行，必须先把划分步骤并行化。详见 Lecture 24。
  • 与硬件的对应：$p$ 由必须串行执行的部分决定——I/O、同步（synchronization）、内存分配、依赖链。shark 机器的理论 16 倍从未达到，原因正是这些串行开销。

1.3 代码示例与底层机制分析

1.3.1 用 C 计算 Amdahl 加速比并观察程序地址空间

代码 (C)：

/* amdahl.c — 演示 Amdahl 定律与程序地址空间布局
 * 编译: gcc -g -Wall -std=c11 amdahl.c -o amdahl
 */
#include <stdio.h>
#include <stdlib.h>

static int        g_init = 42;      /* 已初始化数据段 .data */
static int        g_zero;           /* 未初始化数据段 .bss  */
static const char *g_msg = "hello"; /* 指针本身在 .data     */

/* Amdahl 定律: p 为可加速比例, k 为加速倍数 (k > 0) */
static double amdahl_speedup(double p, double k)
{
    return 1.0 / ((1.0 - p) + p / k);
}

int main(void)
{
    int  stack_var = 0;         /* 栈 */
    int *heap_var  = malloc(sizeof(int));  /* 堆 */
    if (heap_var == NULL) {
        fprintf(stderr, "malloc failed\n");
        return 1;
    }
    *heap_var = 7;

    printf("=== Amdahl 定律: S(p,k) = 1/((1-p) + p/k) ===\n");
    printf("%6s %8s %8s %8s\n", "p", "k=4", "k=16", "k=inf");
    const double pset[] = {0.50, 0.90, 0.95, 0.99};
    for (size_t i = 0; i < sizeof(pset) / sizeof(pset[0]); i++) {
        double p = pset[i];
        printf("%6.2f %8.2f %8.2f %8.2f\n",
               p, amdahl_speedup(p, 4.0), amdahl_speedup(p, 16.0),
               1.0 / (1.0 - p));   /* k -> inf 时 T∞ = (1-p)T */
    }

    printf("\n=== 数据宽度 (LP64) ===\n");
    printf("sizeof(char)   = %zu\n", sizeof(char));
    printf("sizeof(int)    = %zu\n", sizeof(int));
    printf("sizeof(long)   = %zu\n", sizeof(long));
    printf("sizeof(void*)  = %zu\n", sizeof(void *));
    printf("sizeof(double) = %zu\n", sizeof(double));

    printf("\n=== 地址空间布局 (地址随 ASLR 变化) ===\n");
    printf("代码 (main)      = %p\n", (void *)(size_t)main);
    printf(".data (&g_init)  = %p\n", (void *)&g_init);
    printf(".bss  (&g_zero)  = %p\n", (void *)&g_zero);
    printf("堆   (heap_var)  = %p\n", (void *)heap_var);
    printf("栈   (&stack_var)= %p\n", (void *)&stack_var);

    printf("\ng_init=%d g_zero=%d *heap_var=%d msg=%s\n",
           g_init, g_zero, *heap_var, g_msg);

    free(heap_var);
    return 0;
}

【代码做什么？】

1. 定义三个全局对象：g_init（有初值，进 .data）、g_zero（无初值，进 .bss）、g_msg（指针变量本身进 .data，所指字符串 "hello" 进 .rodata）。
2. amdahl_speedup(p,k) 直接实现 $S = 1/((1-p)+p/k)$。
3. main 在栈上定义 stack_var，在堆上 malloc 出 heap_var，分别代表地址空间的两个动态区域。
4. 对 $p \in \{0.50,0.90,0.95,0.99\}$ 打印 $k=4,16,\infty$ 三种加速比，把”串行部分是上限”变成可读数字。
5. 打印 LP64 下各类型宽度，再用 & 与 %p 打印五个不同区域对象的地址。

• 底层机制透视
  1. g_init 与 g_zero 的区别不在语义而在目标文件的存储方式：.data 在 ELF 中占实际字节（初值 42 必须被存下来），.bss 段类型是 NOBITS，只记录”大小 8 字节”，不占文件空间，加载时由内核清零。这就是”把巨大数组初始化为 0”比”初始化为非 0”生成的二进制小得多的原因。
  2. 局部变量 stack_var 在 main 的栈帧（stack frame）里。x86-64 的栈向低地址增长，%rsp 指向栈顶，call 会把返回地址压栈。
  3. malloc 返回的地址来自堆，堆向高地址增长。free 之后内存交还分配器，但 heap_var 指针本身的值不变（悬空指针由此而来）。
  4. %p 打印的代码段/数据段地址（如 0x401126、0x404050）在 ASLR（地址空间布局随机化） 下基本固定，因为这是非 PIE 可执行文件，被链接到固定的 0x400000 起始地址；而堆与栈地址每次运行都不同。

【内存布局 / 数据结构图解】（地址为实测值）

  高地址 0x7fff...
+---------------------------------------------------------------------------------------+
| 0x00007fffffffffff  | 内核/用户边界 (不可访问) | -              | -                   |
+---------------------------------------------------------------------------------------+
| 0x00007ffdfc884d44  | 栈 stack (&stack_var)    | ↓ 向低地址增长 | main 局部变量       |
+---------------------------------------------------------------------------------------+
|         ...         | (空洞)                   |                |                     |
+---------------------------------------------------------------------------------------+
| 0x0000000000bce2a0  | 堆 heap (malloc 分配)    | ↑ 向高地址增长 | heap_var            |
+---------------------------------------------------------------------------------------+
|         ...         | (空洞)                   |                |                     |
+---------------------------------------------------------------------------------------+
| 0x0000000000402000  | .rodata 只读数据         | 只读           | "hello, world"      |
+---------------------------------------------------------------------------------------+
| 0x0000000000404000  | .data / .bss 全局变量    | 可读写         | 0x404050 / 0x40406c |
+---------------------------------------------------------------------------------------+
| 0x0000000000401000  | 代码段 .text             | 只读/可执行    | main = 0x401126     |
+---------------------------------------------------------------------------------------+
  低地址 0x0000...

【实测验证】

$ gcc -g -Wall -std=c11 amdahl.c -o amdahl && ./amdahl
=== Amdahl 定律: S(p,k) = 1/((1-p) + p/k) ===
     p      k=4     k=16    k=inf
  0.50     1.60     1.88     2.00
  0.90     3.08     6.40    10.00
  0.95     3.48     9.14    20.00
  0.99     3.88    13.91   100.00

=== 数据宽度 (LP64) ===
sizeof(char)   = 1
sizeof(int)    = 4
sizeof(long)   = 8
sizeof(void*)  = 8
sizeof(double) = 8

=== 地址空间布局 (地址随 ASLR 变化) ===
代码 (main)      = 0x4011ab
.data (&g_init)  = 0x404050
.bss  (&g_zero)  = 0x40406c
堆   (heap_var)  = 0xbce2a0
栈   (&stack_var)= 0x7ffdfc884d44

$ size hello                      # 观察三段大小
   text    data     bss     dec     hex filename
    976     560       8    1544     608 hello

$ readelf -S hello | grep -E '\.text|\.data|\.bss'
  [14] .text    PROGBITS  0000000000401040 ...
  [24] .data    PROGBITS  0000000000404020 ...
  [25] .bss     NOBITS    0000000000404030 ...

注意 .bss 的类型是 NOBITS——这正是它不占文件空间的原因。

1.3.2 hello 的机器级实现（真实 x86-64 AT&T 汇编）

代码 (C)：

#include <stdio.h>
int main(void)
{
    printf("hello, world\n");
    return 0;
}

用 gcc -O0 -S -std=c11 hello.c -o hello.s 生成的汇编（已删除 .cfi_* 调试伪指令）：

	.file	"hello.c"
	.text
	.section	.rodata
.LC0:
	.string	"hello, world"
	.text
	.globl	main
	.type	main, @function
main:
	pushq	%rbp                # 保存调用者的帧指针
	movq	%rsp, %rbp          # 建立本函数的栈帧
	movl	$.LC0, %edi         # 第 1 个参数: 字符串地址 -> %edi
	call	puts                # 调用 puts (编译器把 printf 优化成 puts)
	movl	$0, %eax            # 返回值 0 -> %eax
	popq	%rbp                # 恢复 %rbp
	ret                         # 返回
	.ident	"GCC: (GNU) 12.2.0"

【代码做什么？】 main 是链接器指定的 C 入口（真正的入口 _start 在 C 运行时里，它调用 __libc_start_main，再由后者调用 main）。printf("hello, world\n") 只有一个参数且以换行结尾，GCC 把它优化成 puts，省掉格式串解析。

• 底层机制透视
  1. 调用约定：x86-64 System V ABI 规定整数参数依次放入 %rdi, %rsi, %rdx, %rcx, %r8, %r9，返回值在 %rax；浮点参数用 %xmm0-%xmm7。字符串地址是第 1 个参数，故进 %edi（movl 写 32 位会把 %rdi 高 32 位清零）。
  2. call 做了什么：把返回地址压栈（%rsp -= 8），再把 PC 设为 puts 入口；puts 执行完用 ret 从栈上弹出返回地址。
  3. 栈帧：pushq %rbp; movq %rsp,%rbp 是未优化代码的标志性开头——保留帧指针便于调试器做栈回溯。-O2 下 GCC 改用 subq $8, %rsp 对齐栈，甚至省掉 push。

【实测验证】 用 gdb 与 strace 观察真实行为：

$ gdb -q -batch -ex 'break main' -ex run -ex 'info registers rip rsp rbp' \
      -ex 'disas /r main' ./hello
Breakpoint 1, main () at hello.c:3
rip            0x40112a            0x40112a <main+4>
rsp            0x7fffffffb6e0      0x7fffffffb6e0
rbp            0x7fffffffb6e0      0x7fffffffb6e0
Dump of assembler code for function main:
   0x0000000000401126 <+0>:	55	push   %rbp
   0x0000000000401127 <+1>:	48 89 e5	mov    %rsp,%rbp
   0x000000000040112a <+4>:	bf 04 20 40 00	mov    $0x402004,%edi
   0x000000000040112f <+9>:	e8 fc fe ff ff	call   0x401030 <puts@plt>
   0x0000000000401134 <+14>:	b8 00 00 00 00	mov    $0x0,%eax
   0x0000000000401139 <+19>:	5d	pop    %rbp
   0x000000000040113a <+20>:	c3	ret

$ strace -e trace=write,exit_group ./hello
write(1, "hello, world\n", 13)          = 13
exit_group(0)                           = ?

write(1, ...) 中的 1 就是标准输出（stdout）文件描述符——这正是”文件是对 I/O 设备的抽象”在系统调用层面的落点。mov $0x402004,%edi 里的 0x402004 是 .rodata 中 "hello, world" 的地址，与上面的地址布局图完全对应。

1.3.3 五大现实的算术验证

代码 (C)：

#include <stdio.h>
int main(void)
{
    int x = 50000;
    int y = x * x;              /* ⚠️ UB: 有符号溢出, 实际按补码回绕 */
    printf("50000*50000   = %d\n", y);
    unsigned u = 50000u, v = u * u;
    printf("50000u*50000u = %u\n", v);
    printf("(1e20 + -1e20) + 3.14 = %.17g\n", (1e20 + -1e20) + 3.14);
    printf("1e20 + (-1e20 + 3.14) = %.17g\n", 1e20 + (-1e20 + 3.14));
    return 0;
}

【实测验证】（GCC 12.2.0，x86-64）

50000*50000   = -1794967296
50000u*50000u = 2500000000
(1e20 + -1e20) + 3.14 = 3.1400000000000001
1e20 + (-1e20 + 3.14) = 0

【底层机制透视】 这就是”ints are not integers, floats are not reals”的实证。

• $50000\times50000 = 2.5\times10^9$ 超出 int 范围 $[-2^{31}, 2^{31}-1] = [-2147483648, 2147483647]$，结果按 2 的补码（two’s complement）回绕得 $-1794967296$。有符号溢出在 C 中是未定义行为（UB, Undefined Behavior），实际结果依编译器与机器而异；无符号则严格按模 $2^{32}$ 定义，故正确打印。
• 浮点加法不满足结合律：1e20 + 3.14 的精确结果需约 67 位有效数字，而 double 只有 52 位尾数，3.14 被完全舍入掉，故 1e20 + (-1e20 + 3.14) = 0。详见 Lecture 2。

1.3.4 内存引用 bug 的”远距离作用”（⚠️ 仅供演示，请勿模仿）

代码 (C)：以下代码故意制造数组越界写。

/* ⚠️ 仅供演示，请勿模仿: s.a[i] 越界写会破坏同结构的 s.d */
#include <stdio.h>
typedef struct { int a[2]; double d; } struct_t;   /* sizeof=16, a 在 +0, d 在 +8 */

double fun(int i) {
    volatile struct_t s;
    s.d = 3.14;
    s.a[i] = 1073741824;   /* ⚠️ UB: i >= 2 时越界 */
    return s.d;
}
int main(void) {
    int i;
    for (i = 0; i <= 6; i++) {
        printf("fun(%d) --> ", i);
        fflush(stdout);
        printf("%.14g\n", fun(i));
    }
    return 0;
}

【实测验证】（本机 GCC 12.2.0；结果依赖系统与编译器）

fun(0) --> 3.14
fun(1) --> 3.14
fun(2) --> 3.1399998664856
fun(3) --> 2.0000006103516
fun(4) --> Segmentation fault   (shell 报告 exit=139)

【底层机制透视】 下标 $i$ 超出数组长度 2，但编译器不做边界检查（C/C++ 不提供内存保护）。struct_t 布局是 a[0] 在偏移 0、a[1] 在偏移 4、d 在偏移 8。写入常量 1073741824 = 0x40000000 会改写 s.d 的字节：

• $i=2$ 写偏移 8，覆盖 d 的低 4 字节：位模式 0x40091eb851eb851f → 0x40091eb840000000，值恰为 3.1399998664856。
• $i=3$ 写偏移 12，覆盖 d 的高 4 字节：位模式 → 0x4000000051eb851f，值为 2.0000006103516。
• $i\ge4$ 越过整个 struct_t，开始破坏栈上其它数据（返回地址等），于是段错误。

这正是讲义所说的 action at a distance（远距离作用）：被破坏的对象（s.d）与被访问的对象（s.a）逻辑上毫无关系，而 bug 的影响可能在很久以后、很远的地方才第一次被观察到。

1.4 实验关联

本讲无直接关联 lab，但它是 L0 C Programming Lab 与全部 8 个 lab 的环境认知前提：

• L0（C Programming，可立即开始）：讲义说 L0”应该全是复习”——C 控制流与语法、显式内存管理、基于指针的数据结构、在收到非法参数（含 NULL 指针）时仍正确运行的健壮代码、Makefile 规则。1.3.1 的 malloc/free 与 1.3.4 的越界写，正是”健壮性”要求的痛点。讲义建议：若 L0 花掉你超过 10 小时，请认真考虑是否该选这门课。
• 环境：所有 lab 在 Intel Computer Systems Cluster（”shark machines”，ssh shark.ics.cs.cmu.edu）上完成。讲义明确说不要用通用 Andrew 集群（没有正确的编译器），本地机器通常也没有，且 make submit 一定不工作。Lab 全部通过 Autolab（https://autolab.andrew.cmu.edu）提交，Autolab 上的分数就是你的 lab 成绩。
• 依赖链：L1 Data ← Lecture 2；L2 Bomb ← Lecture 3–5；L3 Attack ← Lecture 5–6；L4 Cache ← Lecture 9–10；L5 Malloc ← Lecture 11–14；L6 Shell ← Lecture 16–18；L7 Proxy ← Lecture 18–21；L8 SFS ← Lecture 21–24。
• 版本控制：从 L4 Cache Lab 开始，lab 通过 GitHub Classroom 分发，要早提交、勤提交；被指控抄袭时课程组会查阅 git 服务器，缺失 git 历史对你不利。应使用 git commit <file-list> 而非 git add .。把作业发到公开 git 仓库属于 AIV（学术诚信违规）。
• 坑：必须独立完成；全学期 5 个 grace day，每个 lab 最多自动使用 0/1/2 个，用完后每天扣 15%，且晚交不得超过 3 天。部分 lab（L4、L5a、L5b、L6、L7）有代码风格分（与 TA 1:1 评审），部分 lab（L1、L4、L5b、L6、L7）约 10% 分数来自现场 Parsons Puzzle（把乱序代码行重排成可运行片段）。

1.5 常见错误与调试技巧

• 把 gcc hello.c -o hello 当成一步：四个阶段的问题混在一起，报错时不知是哪一步。调试：拆开执行 gcc -E hello.c -o hello.i、gcc -S hello.i、gcc -c hello.s、gcc hello.o -o hello，用 file 确认产物类型（文本还是 ELF 二进制）。
• 以为栈向高地址增长：推演栈帧偏移时全部算反。调试：gdb 里 p &a、p &b 比较两个局部变量地址；info registers rsp rbp 看 %rsp 在 call 前后是否减小 8 字节（x/2gx $rsp 看返回地址）。
• 把有符号溢出当成”会得到一个很大的数”：现象是 50000*50000 打印出负数。调试：这是 UB。gcc -g -fsanitize=undefined -Wall -std=c11 x.c 会打印 runtime error: signed integer overflow；或用 -ftrapv 触发陷阱。
• 浮点比较用 == / 假定加法结合律：1e20 + (-1e20 + 3.14) 得到 0 而非 3.14。调试：打印要足够精度 printf("%.17g\n", x)；比较用 fabs(a-b) < 1e-9；-Wfloat-equal 会对浮点 == 报警。
• 不初始化就使用：.bss 里的全局变量恰为 0（规范保证），但栈上的局部变量是垃圾值，行为随机。调试：gcc -Wall -Wextra（-Wuninitialized 在 -O2 下更有效）；valgrind --track-origins=yes ./a.out 会报 “Conditional jump depends on uninitialised value” 并指出来源。
• 越界写与内存泄漏：程序在完全无关的地方崩溃，或长时间运行后内存耗尽。调试：valgrind --leak-check=full --show-leak-kinds=all ./a.out；对栈越界（如 1.3.4 的例子）首选 gcc -g -fsanitize=address -fsanitize=undefined（ASan 的栈越界检测远好于 Valgrind，后者最擅长堆越界与泄漏）；gdb -tui 配合 x/8xb ptr、p *ptr 亲手核对被破坏的字节。
• printf 格式串与参数类型不匹配：printf("%d\n", ptr) 打印出截断的地址。调试：gcc -Wall -Wformat=2 直接指出；打印指针统一写 printf("%p\n", (void *)ptr)。

1.6 关键要点

• 抽象很好，但要知道它建立在什么之上、边界在哪里：ISA、虚拟内存、进程、虚拟机这些分层抽象让复杂系统可被驾驭，但当程序出 bug、性能不达标时，只有下探到实现细节才能解决。
• 一个 C 程序要变成可执行程序，必须经过预处理 → 编译 → 汇编 → 链接四步；前两步产物是文本，后两步是二进制，链接阶段才完成符号解析与重定位。
• 存储层次之所以有效，全靠程序的局部性（时间与空间局部性）；每一层都是下一层的缓存，由此得到”价格便宜、速度飞快”的错觉。
• 操作系统用三个抽象包装硬件：文件（对 I/O 设备）、虚拟内存（对主存+磁盘）、进程（对处理器/主存/I/O）；应用程序从不直接操作硬件。
• Amdahl 定律是不可绕过的天花板：$S = 1/((1-p)+p/k)$，$S_{\max} = 1/(1-p)$。加速比由串行部分 $1-p$ 决定，而不是由你堆了多少并行资源决定。

1.7 思考题（带答案）

Q1（计算题） 某程序在单处理器上运行需 $T = 100$ 秒，其中 80 秒可完美并行化（$p = 0.8$），剩余 20 秒严格串行。

（a）使用 $k = 16$ 台处理器，$T_{16}$ 与 $S_{16}$ 各是多少？ （b）使用无限多处理器，$S_{\max}$ 是多少？ （c）若通过重构算法把可并行部分从 $p = 0.8$ 提高到 $p = 0.95$（$k = 16$ 不变），加速比变成多少？从（a）到（c）的改善说明优化应优先投向哪里？

答案： （a）$T_{16} = \dfrac{pT}{k} + (1-p)T = \dfrac{0.8\times100}{16} + 0.2\times100 = 5 + 20 = 25$ 秒；$S_{16} = \dfrac{100}{25} = 4$。 （b）$S_{\max} = \dfrac{1}{1-p} = 5$（$T_\infty = 20$ 秒）。用 16 台已拿到 4 倍，而无论再加多少处理器，最多也只有 5 倍。 （c）$T_{16}^{\prime} = \dfrac{0.95\times100}{16} + 0.05\times100 = 5.9375 + 5 = 10.9375$ 秒；$S_{16}^{\prime} \approx 9.14$。 处理器一个没加，只是把串行部分从 20 秒压到 5 秒，加速比就从 4 倍升到 9.14 倍。结论：优先削减串行部分（同步、I/O、分配、依赖链）的收益远大于堆更多并行资源。 另外注意 $T_{16}^{\prime}$ 中并行部分（5.9375 秒）已与串行部分相当——继续增大 $k$ 的边际收益会迅速衰减。

Q2（推演题） 已知 L1 d-cache 命中约 4 周期、主存约 100 周期、本地磁盘约 10,000,000 周期。若把”一次 L1 命中”放大为 1 秒，请把主存与磁盘访问换算成人类可感知的时间，并解释为什么说”内存性能不是均匀的”。

答案：放大倍数 $= 10^9/4 = 2.5\times10^8$。主存 $= 100\times2.5\times10^8$ 秒 $\approx 792$ 年；磁盘 $= 10^7\times2.5\times10^8$ 秒 $\approx 7900$ 万年。也就是说，如果每次 L1 命中让你等 1 秒，一次主存访问要等近 800 年，一次磁盘访问要等几千万年。这正是”内存性能不均匀（memory performance is not uniform）”的量化含义：同一条 movq 指令可能花 4 个周期，也可能花 10,000,000 个周期，取决于数据在哪一层。据此也就理解了 copyij 4.3 ms 与 copyji 81.8 ms 的差距。

Q3（错误直觉题） “这台机器有 16 个硬件线程（8 核 × 2 路超线程），所以程序只要写成多线程就应该快 16 倍。”错在哪里？

答案：错在三层。 （1）Amdahl 定律：程序中必然存在不可并行化的串行部分 $1-p$，它构成上限 $1/(1-p)$。讲义指出 shark 机器”理论上限 16 倍，但在我们的基准测试中从未达到“。 （2）超线程不是第二个核：它只复制指令控制单元（PC、寄存器文件、操作队列），而共享功能单元（整数/浮点运算单元、load/store 单元、数据缓存）。两线程争用同一批功能单元或缓存时，收益远低于 2 倍；只有当一个线程在等待（如缓存不命中）时，另一个才能填满空闲执行槽。 （3）同步与内存一致性开销：访问共享状态必须同步，而讲义强调”同步操作非常昂贵”；缓存一致性协议还带来额外流量，并可能出现伪共享（false sharing）等硬件假象。正确期待是：并行化通常只带来”适度（modest）”的加速。

Q4（错误直觉题） “既然编译器比人聪明得多，而且我永远不会手写汇编，那么学机器级编程完全是浪费时间。”请指出这个推理的漏洞。

答案：漏洞在于把”编写汇编”与”理解机器级执行模型”混为一谈。讲义承认”你大概永远不会用汇编写程序——编译器比你更好、更有耐心”，但随即给出四条必须懂汇编的理由： （1）有 bug 时高级语言模型会崩溃——1.3.4 节那个越界写在 C 的语义层面毫无信号，只有理解 struct_t 的字节布局才能解释 fun(2) 为何打印 3.1399998664856； （2）调优性能必须知道编译器做了/没做哪些优化（如把 printf 换成 puts）； （3）实现系统软件：编译器的目标是机器码，操作系统必须管理进程状态； （4）对抗恶意代码：代码注入攻击（L3 Attack Lab）完全建立在栈帧布局与返回地址的知识上。 一句话：汇编不是用来写的，是用来读的；不会读，你在 bug 与性能面前就只能猜。