【学习笔记】深入理解计算机系统

发表于 2024-01-05 更新于 2024-02-26 分类于笔记阅读次数：

这是清华大学计算机系秋季课程《计算机系统概论》期末考试复习笔记，教材为《深入理解计算机系统（原书第3版）》。

整数

字数据大小

$1 \,\mathrm{Byte} = 8 \,\mathrm{bits}$，字节是最小的可寻址的内存单位。

字长为 $w$ 的机器，虚拟地址的范围为 $[0, 2^{w} - 1]$。

大多数 $64$ 位机器也可以运行 $32$ 位机器编译的程序，向后兼容。

$32$ 位程序和 $64$ 位程序的区别是该程序是 如何编译的，而不是 如何运行 的。

char 并没有规定是有符号还是无符号。

Is char signed or unsigned by default?

Why don't the C or C++ standards explicitly define char as signed or unsigned?

C 声明	C 声明	字节数	字节数
有符号	无符号	$32$ 位	$64$ 位
`[signed] char`	`unsigned char`	$1$	$1$
`short`	`unsigned short`	$2$	$2$
`int`	`unsigned`	$4$	$4$
`long`	`unsigned long`	$4$	$8$
`int32_t`	`uint32_t`	$4$	$4$
`int64_t`	`uint64_t`	$8$	$8$
`char*`		$4$	$8$
`float`		$4$	$4$
`double`		$8$	$8$

字节顺序

小端法还是大端法。地址从低到高，是权重小的数在前（小端）还是权重大的在前。

在 C 语言中，sizeof(T) 返回变量 T 的字节数。如果 T 是数组：

此次调用在 T 的生命周期内，则返回数组的大小。
否则，按照指针处理，返回 $8$（$64$ 位机器）或 $4$（$32$ 位机器）。

整数运算

逻辑右移与算术右移的区别：前者在最高位补 $0$，后者在最高位补符号位。

Two's Complement 和 Ones' Complement 的来源。

补码表示法里的加法逆元：-x == (~x) + 1。

整数除法总是 舍入到 $0$。当 $x < 0$ 时，需要用 (x + (1 << k) - 1) >> k 来计算 $\left\lfloor\dfrac{x}{2^k}\right\rfloor$。

类型转换

有符号数和无符号数的比较：强制转换为无符号数，然后运算，再强制转化回去。比如 (-1 < 0u) == false，int x = -1 + 1u; 则 (x == 0) == true。

为什么 INT_MIN 被定义为 (-INT_MAX - 1)？ - 参考资料 1 - 参考资料 2 - 用一句话来解释 C 语言中 $TMin_{32}$ 的古怪写法的原因：虽然 $-2147483648$ 这个数值能够用 int 类型来表示，但在 C 语言中却没法写出对应这个数值的 int 类型常量。

short 转为 unsigned 的时候，先改变大小，再完成从有符号到无符号的转换。也就是说，

1 2	short x; //... using (unsigned)x

等价于 (unsigned)(int)x，而不是 (unsigned)(unsigned short)x。

溢出

无符号加法溢出：$s = x + y$，溢出则 $s < x$ 或等价地，$s < y$。

有符号加法溢出：$s = x + y$，溢出当且仅当：$x, y > 0$ 且 $s \le 0$；或 $x, y < 0$ 且 $s \ge 0$。

浮点数

表示方法

IEEE 754 表示浮点数：$V = (-1)^s \times M \times 2^E$。按以下形式存储：存储：s | exp | frac。

类型	表示
规格化的	`s \| 非全 0, 非全 1 \| frac`
非规格化的	`s \| 0000 ... 0000 \| frac`
无穷大	`s \| 1111 ... 1111 \| 全 0`
`NaN`	`s \| 1111 ... 1111 \| 非全 0`

规格化的：认为 exp 从 0111...1111 开始编码 $0$。认为 frac 是 1.[frac]。
非规格化的：认为 exp 为 $2 - 2^{|E| - 1}$。认为 frac 是 0.[frac]。$0$ 是非规格化数。

最小的正非规格化数：0 | 0000 | 001 即 \[ 2^{2 - 2^{|E| - 1}} \cdot 2^{-|F|} \] 最大的正非规格化数：0 | 0000 | 111 即 \[ 2^{2 - 2^{|E|-1}} \cdot (1 - 2^{-|F|}) \] 最小的正规格化数：0 | 0001 | 000 即 \[ 2^{2 - 2^{|E|-1}} \] 最大的正规格化数：0 | 1110 | 111 即 \[ 2^{2^{|E| - 1} - 1}\cdot(2 - 2^{-|F|}) \]

运算与类型转换

向偶数舍入：四舍六入五成双。

浮点加法不具有结合性，但有单调性。$\forall x \neq \mathrm{NaN}, a \ge b \implies a + x \ge b +x$。

原始类型	转化为	溢出	舍入
`int`	`float`	否	有可能
`int` / `float`	`double`	否	否
`double`	`float`	是	是
`float/double`	`int`	有可能	向零舍入

float / double 转为 int 的时候，如果溢出，则没有规定的结果。一个典型的固定值是 INT_MIN。

汇编

数据格式

%rip：PC，程序计数器，给出将要执行的 下一条指令 在内存中的地址。

nop 对程序没有影响，只是为了使函数代码按照 $16$ 字节对齐。

按照 %rdi %rsi %rdx %rcx %r8 %r9 的顺序接收参数，剩下的全部放栈里。

$16$ 位数据类型称为“字（word）”，$32$ 位数为“双字（double words）”，$64$ 位数为“四字（quad words）”。

C 声明	Intel 数据类型	汇编代码后缀	大小（x86-64，字节）
`char`	字节	`b`	$1$
`short`	字	`w`	$2$
`int`	双字	`l`	$4$
`long`	四字	`q`	$8$
`char*`	四字	`q`	$8$
`float`	单精度	`s`	$4$
`double`	双精度	`l`	$8$

注意，int 和 double 的汇编代码后缀都是 l，但这不会有歧义，因为浮点数使用的是一组完全不同的指令和寄存器。

被调用者保存寄存器（callee-saved）：%rbx，%rbp，%r12~%r15

调用者保存寄存器（caller-saved）：所有其他的寄存器，除了 %rsp。

复制和生成 小于 $8$ 字节 结果的指令：

生成 $1$ 字节和 $2$ 字节的指令会 保持剩下的字节不变
生成 $4$ 字节的指令会 把高位 $4$ 个字节置为 $0$

算术指令

寻址模式：Imm(rb, ri, s) == Mem[Imm + Reg[rb] + Reg[ri] * s]，s 只能取 $1, 2, 4, 8$。

mov a b 的意思是 move a to b。两个操作数 不能都指向内存，所以要先将源内存中的值加载到寄存器，再复制到目标内存。寄存器大小必须和指令后缀（b, w, l, q）指定的大小匹配。movl 会把寄存器高位 $4$ 字节设置为 $0$。

movabsq $0x0011223344556677, %rax	# %rax = 0011223344556677
movb	$-1, %al					# %rax = 00112233445566FF
movw	$-1, %ax					# %rax = 001122334455FFFF
movl	$-1, %eax					# %rax = 00000000FFFFFFFF
movq	$-1, %rax					# %rax = FFFFFFFFFFFFFFFF

压入栈是 subq $8, %rsp。栈往低地址生长。

sub S, D 是 D <- D - S。

leaq S, D 是 D <- &S。注意这个取地址符，这直接导致 leaq 在算术运算中的潜力。D 必须是一个寄存器。

移位操作 sal, shl, sar, shr，格式：sal k, D。其中 k 要么是个立即数，要么放在 %cl 里。移位量是由 %c1 寄存器的低 $m$ 位决定的，这里 $2^m=w$。高位会被忽略。所以，例如当寄存器 %cl 的十六进制值为 0xFF 时，指令 salb 会移 $7$ 位，salw 会移 $15$ 位，sall 会移 $31$ 位，而 salq 会移 $63$ 位。

$128$ 位整数算术操作：

目标寄存器的选择是固定的。注意这里固定使用 %rdx 和 %rax 作为 $128$ 位数的高 $64$ 位和低 $64$ 位。除法的时候商存在 %rax 里，余数存在 %rdx 里。

比较和测试指令 不修改任何寄存器的值，只设置关键码。注意比较指令的操作数顺序。这两个指令的第二个操作数（即 $S_2$）不能为立即数。

指令	基于	描述
$\text{CMP} \quad S_1, S_2$	$S_2 - S_1$	比较
`cmpb`		比较字节
`cmpw`		比较字
`cmpl`		比较双字
`cmpq`		比较四字
$\text{TEST} \quad S_1, S_2$	$S_1 \& S_2$	测试
`testb`		测试字节
`testw`		测试字
`testl`		测试双字
`testq`		测试四字

set 的类型限制了操作数的类型，包括是有符号（setg 等）还是无符号类型（seta 等），还是指针（只能进行 sete 和 setne）。

注意 jmp %rax、jmp *%rax 和 jmp *(%rax) 的区别。

当执行 PC 相对寻址时，程序计数器的值是 跳转指令后面的那条指令的地址，而不是跳转指令本身的地址。

逻辑指令

条件传送

使用控制的条件转移：更改程序的执行路径有可能很低效
使用数据的条件转移：将两个分支的结果都计算出来，再根据条件从中选取一个不能用于错误条件（空指针访问）或副作用（修改全局变量）的情况。

循环

跳转到中间策略：执行一个无跳转跳到循环结尾处的测试。

	goto test;
loop:
	body-statement
test:
	t = test-expr;
	if (t)
		goto loop;

guarded-do 策略：首先用条件分支判断首次是否执行，把代码变为 do-while。

t = test-expr;
if (!t)
	goto done;
loop:
	body-statement
	t = test-expr
	if (t)
		goto loop;
done:

多分支

开关情况数量比较多（例如 $4$ 个以上），并且 值的范围跨度比较小 时，就会使用跳转表。

注意，这里没有使用哈希，而是单纯地用数组第 $i$ 个来表示跳转到基址 $+i$，所以要求范围跨度比较小。

控制转移

从 P 转移到 Q，直接将 PC 设置为 Q 的首地址。返回地址需要压入栈。

多余 $6$ 个的参数，从右往左压入栈。所有的数大小都向 $8$ 的倍数对齐。

什么时候会使用栈上的局部存储：

寄存器不够放
对一个局部变量使用了取地址符 &
某些局部变量是数组或结构

数组

访问数组中元素的时候记得 乘上类型大小。

1	int A[5][3];

等价于

1 2	typedef int row3_t[3]; row3_t A[5];

对于 T D[R][C]; 的数组而言，D[i][j] 的内存地址为 \[ \& D[i][j] = x_D + \,\mathrm{sizeof}(T) \cdot (C\cdot i + j) \] $C$ 为列大小，$x_D$ 是数组基址，即 &D[0][0]。

定长数组可以优化。变长数组也可以优化。本质上是识别出多维数组的元素的步长。

结构与联合

用联合来获取位表示：

unsigned long double2bits(double d) {
    union {
        double d;
        unsigned long u;
    } temp;
    temp.d = d;
    return temp.u;
}

数据对齐：

任何 $K$ 字节的基本对象的地址都必须是 $K$ 的倍数。

结构体的末尾会填充空格，使得结构体数组内的每个元素的每个字段都满足对齐要求。

例如：

struct S2 {
    int i;
    int j;
    char c;
};

如果定义 S2 d[4]; 那它的大小就不能为 $9$。因为 d[1].i 就不满足对齐要求。

大多数函数的栈帧的边界都必须是 $16$ 字节的倍数。

任何内存分配函数（alloca、malloc、calloc 或 realloc）生成的块的起始地址都必须是 $16$ 的倍数。

函数指针的值是该函数机器代码表示中第一条指令的地址。

缓冲区溢出攻击

对抗缓冲区溢出攻击：

栈随机化 程序开始的时候先随机分配一段空间。
栈破坏检测 设置金丝雀值。
限制可执行代码区域

ROP 攻击能够绕开“限制可执行代码区域”这种保护方法，但绕不开“栈破坏检测”这种保护方法。

链接

链接器的两个任务：符号解析，以及重定位。

符号解析符号是指：函数名称，全局变量名称，或者是静态变量名称。
重定位代码和数据的节，重新修改符号的引用，让它们指向应该指向的位置。

链接器将块（有的包含程序代码，有的包含程序数据，其他则包含引导链接器和加载器的数据结构）连接起来，确定被连接块的运行时位置，并且修改代码和数据块中的各种位置。

目标文件：

可重定位目标文件（编译器和汇编器生成）
- （普通的）
- （特殊的）共享目标文件
可执行目标文件（链接器生成）

可重定位目标文件

类型	条目	位置
节	ELF 头	$0$
节	`.text`
节	`.rodata`
节	`.data`
节	`.bss`
节	`.symtab`
节	`.rel.text`
节	`.rel.data`
节	`.debug`
节	`.line`
节	`.strtab`
描述目标文件的节	节头部表

条目	内容
`.text`	已编译程序的机器代码
`.rodata`	只读数据，包括 `printf` 里的格式串和开关语句的跳转表
`.data`	已初始化的全局和静态 C 变量
`.bss`	未初始化的全局和静态 C 变量，以及所有被初始化为 $0$ 的全局或静态变量
`.symtab`	定义和引用的函数和全局变量的信息，不包含局部变量
`.rel.text`	`.text` 中，当链接器把当前目标文件和其他文件组合时，要修改的位置。包含任何调用外部函数或者引用全局变量的指令；调用本地函数的指令则不需要修改。
`.rel.data`	被模块引用或定义的所有全局变量的重定位信息。任何已初始化的全局变量，如果它的初始值是一个全局变量地址或者外部定义函数的地址，都需要被修改。
`.debug`	程序里的局部变量和类型定义（需要 `-Og` 生成）

符号和符号表

符号类型	定义
全局符号	由模块 $m$ 定义并能被其他模块引用
外部符号	由其他模块定义并被模块 $m$ 引用
局部符号	只被模块 $m$ 定义和引用（例如静态函数、静态全局变量）

任何带有 static 属性声明的全局变量或者函数都是模块私有的。

形参属于局部变量，链接器对局部变量一无所知。

强符号和弱符号：

强符号：函数或已初始化的全局变量。

弱符号：未初始化的全局变量。

不允许有多个同名强符号
如果有一个强符号和多个弱符号同名，那么选择强符号
如果有多个弱符号同名，那么从这些弱符号中任意选择一个

静态库文件：

将多个相关的重定位对象文件集成为一个单一的带索引的文件 (称为归档文件，archive file)
增强链接器的功能使之能够在归档文件中解析外部符号
如果归档文件中的某个成员解析了外部符号，就将其链接入执行文件

静态库文件的劣势：

执行文件中会重复包含有所需的库文件函数或者数据
运行时内存中也会有重复部分
库文件的细微变动需要所有相关执行文件进行重链接

更好的方案：

共享库文件，特殊类型的重定向对象文件，可以被装载入内存后进行动态链接；链接可以在装载时或者运行时完成。即 Windows 系统下的 DLL 文件。

重定位

重定位：节和符号定义

合并所有的 .data 节为一个节，等。这一步完成时，程序中的每条指令和全局变量都有唯一的运行时地址了。

重定位：节中的符号引用

修改代码节和数据节中对每个符号的引用，使得它们指向正确的运行时地址。

共享库中的全局变量寻址

代码段中的任意指令与数据段中的任意变量之间的“距离”在运行时是一个常量，与代码和数据加载的绝对内存位置无关。

全局偏移量表（GOT）

虚存

在有限物理内存前提下设计出连续的、相互独立的虚拟内存。

虚拟寻址：

地址空间

虚拟地址空间：$[0, N - 1]$，其中 $N = 2^n$。

物理地址空间：$[0, M - 1]$，其中 $M = 2^m$。对应于系统中物理内存的 $M$ 个字节。

物理内存是虚拟内存的缓存

虚拟页：虚拟内存中大小固定的块。每个虚拟页的大小为 $P = 2^p$ 字节。

物理页（页帧）：物理内存中大小固定的块。每个物理页的大小为 $P = 2^p$ 字节。

虚拟页面状态	意思
未分配的	VM 系统还未分配（创建）的页，不占用任何空间
缓存的	已缓存在物理内存中的已分配页
未缓存的	未缓存在物理内存中的已分配页

页表

将虚拟页映射到物理页的页表项数组。

有效位：表示该虚拟页当前是否被缓存到在 DRAM 中。

页缺失：

触发缺页异常
页缺失处理程序选择要被替换的页面由操作系统（通过异常处理代码）将所需数据从硬盘读入内存。若被替换页面是写入过的，则内存页面写入外部存储。
触发页缺失的指令重新执行，这次可以确保命中（page hit）

局部性

数据/指令的访问具有局部性

在任何时刻，运行的程序都倾向于访问一组“活跃”的虚拟页，活跃页面的集合称为工作集

具有较好的时间局部性的程序将具有较小的工作集

虚拟内存：内存管理

操作系统为每个进程都提供了一个单独的页表。多个虚拟页面可以映射到同一个共享物理页面上。

虚拟内存：内存保护

扩展页表项，增加使用权限位；违反许可条件则会触发 SIGSEGV（段错误）

地址翻译

基本参数

符号	描述
$N = 2^n$	虚拟地址空间中的地址数量
$M = 2^m$	物理地址空间中的地址数量
$P = 2^p$	页的大小（字节）

虚拟地址（VA）的组成部分

符号	描述
VPO（$p$ 位）	虚拟页面偏移量（字节）
VPN（$n - p$ 位）	虚拟页号
TLBI	快表（TLB）索引
TLBT	快表（TLB）标记

物理地址（PA）的组成部分

符号	描述
PPO（$p$ 位）	物理页面偏移量（字节）
PPN（$m - p$ 位）	物理页号

具体过程

页命中：

第 1 步：处理器生成一个虚拟地址，并把它传送给 MMU。
第 2 步：MMU 生成 PTE 地址，并从高速缓存/主存请求得到它。
第 3 步：高速缓存/主存向 MMU 返回 PTE。
第 4 步：MMU 构造物理地址，并把它传送给高速缓存/主存。
第 5 步：高速缓存/主存返回所请求的数据字给处理器。

页缺失：

第 1 步到第 3 步：和图 9-13a 中的第 1 步到第 3 步相同。
第 4 步：PTE 中的有效位是零，所以 MMU 触发了一次异常，传递 CPU 中的控制到操作系统内核中的缺页异常处理程序。
第 5 步：缺页处理程序确定出物理内存中的牺牲页，如果这个页面已经被修改了，则把它换出到磁盘。
第 6 步：缺页处理程序页面调入新的页面，并更新内存中的 PTE。
第 7 步：缺页处理程序返回到原来的进程，再次执行导致缺页的指令。CPU 将引起缺页的虚拟地址重新发送给 MMU。因为虚拟页面现在缓存在物理内存中，所以就会命中，在 MMU 执行了图 9-13b 中的步骤之后，主存就会将所请求字返回给处理器。

快表（TLB）

快表项：

快表命中：

TLB 命中消除了⼀次内存访问。

快表不命中：

当 TLB 不命中时，MMU 必须从 L1 缓存中取出相应的 PTE。新取出的 PTE 存放在 TLB 中，可能会覆盖一个已经存在的条目。

Linux 虚拟内存系统

Linux 虚拟内存区域

内核为系统中的每个进程维护一个单独的任务结构（源代码中的 task_struct）。

task_struct 里包含：PID、指向用户栈的指针、可执行目标文件的名字，以及程序计数器。

mm_struct 述了虚拟内存的当前状态：pgd 指向第一级页表（页全局目录）的基址，而 mmap 指向一个 vm_area_structs（区域结构）的链表。

vm_area_struct 中的每个结构都描述了当前虚拟地址空间的一个区域。

vm_start：指向这个区域的起始处。
vm_end：指向这个区域的结束处。
vm_prot：描述这个区域内包含的所有页的读写许可权限。
vm_flags：描述这个区域内的页面是与其他进程共享的，还是这个进程私有的（还描述了其他一些信息）。
vm_next：指向链表中下—区域结构。

Linux 缺页异常处理

虚拟地址 A 是合法的吗（是否存在）？
试图进行的内存访问是否合法（有没有权限）？
否则，这个访问是可以处理的缺页（只是没放缓存而已）。
- 选择一个牺牲页面，如果这个牺牲页面被修改过，那么就将它交换出去，换入新的页面并更新页表。
- 然后 CPU 重新启动引起缺页的指令，此时不会再缺页了。

内存映射

通过关联硬盘上存储的各类对象来初始化虚存的各个区域。

虚拟内存区域可以映射到：

Linux 文件系统中的普通文件
匿名文件由内核创建，全是 $0$。与进程虚存空间里的运行时栈、堆、未初始化的全局数据 对应。

建立映射关系并不一定分配空间。只是修改了元数据。

共享对象的物理内存相同，但是两进程里对应的虚拟内存不一定相同。

私有写时复制

直到进程修改私有区域内的某个页面时，才会在物理内存中创建这个页面的一个新副本，更新页表条目指向这个新的副本，然后恢复这个页面的可写权限。尽可能地延迟复制。

内存分配基础

基本概念

brk 指向堆顶。

动态内存分配器将堆视作不同大小的内存块的集合——这些块要么是 已分配的，要么是 空闲的。

处理任意请求序列
立即响应请求
只使用堆
对齐块（对齐要求）
不修改已分配的块

吞吐率：单位时间内完成的请求数。

峰值利用率： \[ U_k = \dfrac{\max\limits_{i \le k}P_i}{H_k} \] $P_i$：第 $i$ 步时，当前已分配的块的有效载荷之和。$H_i$：第 $i$ 步时，堆的大小。

内部碎片与外部碎片

内部碎片

维护堆结构的开销
地址对齐用的数据填充
与分配策略相关的额外开销例如，返回一个大块来满足一个小请求

外部碎片

当堆内有足够多的空闲内存总和，但没有一个单一的足够大的空闲块

隐式空闲链表

结构

很多个这样的堆块连接起来的链表。

分配：选择空闲块

First fit：从头开始搜索
- 会在链表的起始处附近引起碎片化
Next fit：从上一次搜索结束的地方开始搜索
- 比 first fit 快
- 但有研究表明，碎片化更糟糕
Best fit：选择最合适的空闲块，使得剩余字节最少
- 会产生大量的难以利用的“小外部碎片”
- 比 first fit 要慢

释放：合并块

双向合并。

异常控制流

异常类型

异步异常 是由处理器外部的 I/O 设备中的时间产生的。

同步异常 是执行一条指令的直接产物。

类别	原因	异步/同步	返回行为
中断	来自 I/O 设备的信号	异步	总是返回到下一条指令
陷阱	有意的异常	同步	总是返回到下一条指令
故障	潜在可恢复的错误	同步	可能返回到当前指令
终止	不可恢复的错误	同步	不会返回

陷阱是一条系统调用，它可以是故障，也可以是用户程序通过 syscall 向内核请求服务。

进程控制

函数	作用
`pid_t getpid(void);`	返回当前进程的 PID
`pid_t getppid(void);`	返回父进程的 PID
`void exit(int status);`	以 `status` 退出状态来终止进程
`pid_t fork(void);`	子进程返回 $0$，父进程返回子进程的 PID；如果出错，返回 $-1$
`pid_t waitpid(pid_t pid, int *statusp, int options);`	如果成功，返回子进程 PID；如果 WNOHANG，则为 $0$；如果其他错误，则为 $-1$
`pid_wait(int *status sp);`	等价于 `waitpid(-1, statusp, 0);`
`int execve(const char filename, const charargv[], const char *envp[])`	在当前进程的上下文中加载并运行一个新程序

fork 函数：

调用一次，返回两次。
并发执行：不能确定执行顺序。
相同但是独立的地址空间：相同的用户栈、相同的本地变量值、相同的堆、相同的全局变量值、相同的代码，但是是独立的。
共享文件。

waitpid 函数：等待它的子进程终止或者停止。

pid：如果 pid 大于 $0$，则等待集合就是单独的子进程，它的 PID 是 pid；如果 pid 等于 $-1$，则等待集合由父进程的所有子进程组成的。
options： WNOHANG：如果等待集合中的任何子进程都还没有终止，那么就立即返回（返回值为 $0$）。默认的行为是挂起调用进程，直到有子进程终止。在等待子进程终止的同时，如果还想做些有用的工作，这个选项会有用。 WUNTRACED：挂起调用进程的执行，直到等待集合中的一个进程变成已终止或者被停止，返回的 PID 为导致返回的已终止或被停止子进程的 PID。默认的行为是只返回已终止的子进程。当你想要检査已终止和被停止的子进程时，这个选项会有用。 WCONTINUED：挂起调用进程的执行，直到等待集合中一个正在运行的进程终止或等待集合中一个被停止的进程收到 SIGCONT 信号重新开始执行。 WNOHANG | WUNTRACED：立即返回，如果等待集合中的子进程都没有被停止或终止，则返回值为 $0$；如果有一个停止或终止，则返回值为该子进程的 PID。
statusp：检查已回收子进程的退出状态，假设 statusp = &status。 WIFEXITED：如果于进程通过调用 exit 或者 return 正常终止，就返回真。 WEXITSTATUS：返回一令正常终止的子进程的退出状态。只有在 WIFEXITED() 返回为真时，才会定义这个状态。 WIFSIGNALED：如果子进程是因为一个未被捕获的信号终止的，那么就返回真。 WTERMSIG：返回导致子进程终止的信号的编号。只有在 WIFSIGNALED() 返回为真时，才定义这个状态。 WIFSTOPPED：如果引起返回的子进程当前是停止的，那么就返回真。 WSTOPSIG：返回引起子进程停止的信号的编号。只有在 WIFSTOPPED() 返回为真时，才定义这个状态。 WIFCONTINUED：如果子进程收到 SIGCONT 信号重新启动，则返回真。

如果没有子进程，则返回 $-1$ 并设置 errno 为 ECHILD；如果 waitpid 函数被一个信号中断，则返回 $-1$ 并设置 errno 为 EINTR。

execve 函数：

保持进程号（PID）、打开的文件描述符和信号上下文不变
正常情况下 不返回

信号处理

待处理信号（pending signal）：在任何时刻，一种类型的信号 至多只会有一个 待处理信号。

发送信号

函数	作用
`pid_t getpgrp(void);`	返回调用进程的进程组 ID
`int setpgid(pid_t pid, pid_t pgid);`	改变 `pid` 的进程组；成功返回 $0$，失败返回 $-1$
`int kill(pid_t pid, int sig);`	发送信号给 `pid` 的进程；成功返回 $0$，失败返回 $-1$
`unsigned int alarm(unsigned int secs);`	返回前一次闹钟剩余的秒数；如果以前没有设定过，则返回 $0$

setpgid 函数：

如果 pid 为 $0$，则用当前进程作为 PID；如果 pgid 为 $0$，则用 pid 指定的进程的进程组 ID 作为进程组 ID。

一般而言，进程组 ID 通常取自作业中父进程中的一个。

输入 Ctrl+C 会导致内核发送一个 SIGINT 信号到 前台进程组的每个进程。

输入 Ctrl+Z 会发送一个 SIGTSTP 信号到 前台进程组的每个进程。默认情况下，结果是停止（挂起）前台作业。

alarm 函数：

内核在 secs 秒后发送一个 SIGALRM 信号给调用这个函数的进程。如果 secs 是 $0$，则啥事儿也不干。在任何情况下，alarm 都会取消之前所有待处理的闹钟，并且返回任何待处理的闹钟在被发送前还剩下的秒数。

接收信号

内核将 $p$ 从内核态切到用户态的时候，会检查 $p$ 的未被阻塞的待处理信号的集合。从小到大，强制 $p$ 接收某一信号 $k$。

默认行为：

进程终止
进程终止并转储内存
进程停止（挂起）直到被 SIGCONT 信号重启
进程忽略该信号

1 2	typedef void (*sighandler_t)(int); sighandler_t signal(int signum, sighandler_t handler);

关于 handler 的值：

如果 handler 是 SIG_IGN，那么忽略类型为 signum 的信号
如果 handler 是 SIG_DFL，那么类型为 signum 的信号行为恢复为默认行为
否则，handler 就是用户定义的函数的地址，作为信号处理程序
- 调用信号处理程序被称为 捕获信号
- 执行信号处理程序被称为 处理信号

非本地跳转

1 2	int setjmp(jmp_buf env); int sigsetjmp(sigjmp_buf env, int savesigs);

setjmp 函数在 env 缓冲区保存当前环境，以供后面的 longjmp 使用，并返回 0。

调用一次，返回多次。

调用环境包括程序计数器、栈指针和通用目的寄存器。

setjmp 函数的返回值不能作为右值。

1 2	void longjmp(jmp_buf env, int retval); void siglongjmp(sigjmp_buf, int retval);

longjmp 函数从 env 缓冲区恢复调用函数，然后出发一个从最近一次初始化 env 的 setjmp 调用的返回。然后 setjmp 返回，并带有非零的返回值 retval。

调用一次，从不返回。

非本地跳转的一个重要应用就是允许从一个深层嵌套的函数调用中立即返回，通常是由检测到某个错误情况引起的。如果在一个深层嵌套的函数调用中发现了一个错误情况，我们可以使用非本地跳转 直接返回 到一个普通的本地化的错误处理程序，而不是费力地解开调用栈。

由于在信号处理期间自动屏蔽了正在被处理的信号，而使用 setjmp/longjmp 跳出信号处理程序时又不会自动将信号屏蔽码修改会原来的屏蔽码，从而引起该信号被永久屏蔽。

可以使用 sigsetjmp/siglongjmp 来解决这一问题。sigsetjmp 在 savesigs 非 $0$ 的时候会储存。

IO 处理

普通文件
- 文本文件：只含有 ASCII 或 Unicode 字符的文件
- 二进制文件：其他文件对于内核而言，二者并没有区别。
目录：包含一组链接的文件，每个链接将一个文件名映射到一个文件。
套接字

打开和关闭文件

// 成功返回新文件描述符，出错返回 -1
int open(char *filename, int flags, mode_t mode);
// 成功返回 0，出错返回 -1
int close(int fd);

open 函数将 filename 转换为一个 文件描述符 （file descriptor），并且返回描述符数字。

关闭一个已关闭的描述符会出错。

`flags` 参数	意义
`O_RDONLY`	只读
`O_WRONLY`	只写
`O_RDWR`	可读可写
`O_CREAT`	如果文件不存在，就创建一个空文件
`O_TRUNC`	如果文件已经存在，就截断它（重头开始写）
`O_APPEND`	每次写操作前，设置文件位置到文件末尾（每次添加）

mode 参数是设置访问权限用的。

读和写文件

// 若成功，返回读的字节数；出错返回 -1
ssize_t read(int fd, void *buf, size_t n);
// 若成功，返回写的字节数；出错返回 -1
ssize_t write(int fd, const void *buf, size_t n);

$n$ 是最多读取/写入的字节数。read 返回 0 表示 EOF。

ssize_t 是有符号的 size_t，因为出错要返回 $-1$。这也使 read/write 的返回值能够达到的返回缩小了一半。

可能返回值小于 $n$，此时返回值被称为 不足值：

读时遇到 EOF
从终端读文本行一次 read 将传送一个文本行，返回的不足值等于文本行的大小。
读和写网络套接字

共享文件

描述符表
- 每个进程一张表
- 特殊的 file descriptor | 文件描述符(fd) | 默认打开 | | :------------: | :------: | | 0 | stdin | | 1 | stdout | | 2 | stderr |
打开文件表
- 由所有进程共享
- refcnt 存指向该文件的描述符的个数
v-node 表
- 由所有进程共享
- 多个描述符可以通过不同的文件表项来引用同一个文件

fork 函数对于共享文件的影响：复制一份一模一样的描述符表。打开文件表的 refcnt += 1。

IO 重定向

1 2	int dup(int oldfd); int dup2(int oldfd, int newfd);

成功：dup 函数返回当前系统可用的最小整数值，并让这个值代表的 fd 指向 oldfd。dup2 函数返回第一个不小于 newfd 的整数值。也就是分为两种情况：

如果 newfd 已经打开，则先将其关闭，再复制文件描述符。
如果 newfd 等于 oldfd，则 dup2 返回 newfd，而不关闭它。

失败：均返回 $-1$，并设置 errno。

本质上是修改了描述符表中表项指向的打开文件表的位置。dup2 以后，可能会导致某个文件被关闭，导致打开文件表和 v-node 表被删除。

UNIX IO

优点：

Unix IO 是最通用而且额外开销最小的 IO 形式
所有其他 IO 包都是使用 UNIX IO 来实现的
Unix IO 提供了访问文件元数据的功能

缺点：

对不足值的处理不够，容易出错
有效读取文本行需要某种形式的缓冲，容易出错
这些问题在标准 IO 和 RIO 包中都得到解决

标准 I/O

标准 I/O 函数在实现过程中使用了缓存，在写入 \n 时或者显式调用 fflush() 时讲缓存内容刷入到输出文件。

优点：

通过减小 read 和 write 调用的数目，缓冲增加了效率
不足值可以自动处理

缺点：

没有提供访问文件元数据的功能
标准 IO 程序并非同步信号安全的，也不适合在信号处理程序中采用
标准 IO 不适合于对网络 socket 的输入输出进行处理

选择 I/O 函数

通用规则：使用能用的最高级别的 IO 函数。

什么时候使用标准 IO：
- 当处理磁盘和终端文件的时候。
什么时候使用裸 UNIX IO：
- 信号处理程序，因为只有它是同步信号安全的
- 在很少的情况下，当你需要高性能的时候
什么时候用 RIO：
- 读写网络套接字的时候
- 避免对 socket 使用标准 IO

线程与线程同步基础

线程是运行在一个单一进程上下文中的逻辑流，由内核进行调度。

每个线程都有它自己的线程上下文（thread context），包括以个唯一的整数线程 ID（Thread ID，TID）、栈、栈指针、程序计数器、通用目的寄存器和条件码。所有的运行在一个进程里的线程共享该进程的整个虚拟地址空间。

线程执行模型

线程之间是并列的关系，而不是像进程那样的父子关系。

主线程和其他线程的区别仅在于它总是进程中第一个运行的线程。对等线程池概念的主要影响是，一个线程可以杀死它的任何对等线程，或者等待它的任意对等线程终止。另外，每个对等线程都能读写相同的共享数据。

共享变量

一个变量 x 被共享，当且仅当多个线程引用 x 的（至少）一个实例。

线程内存模型

独有的：线程号、栈、栈指针、PC、条件码，以及通用寄存器寄存器值是严格隔离和受到保护的；但不同线程的栈互相间 不设防，也就是说，可以强行通过地址偏移来访问。
共有的：代码、数据（内存）、堆、共享库、打开的文件，以及设置好的信号处理函数（handler）

将变量实例映射到内存

变量类型	定义	内存中的实例
全局变量	定义在所有函数外面	虚拟内存包含全局变量的唯一实例
本地自动变量	定义在函数内部，无 `static` 属性	每个线程栈包含每个局部变量的一个实例
本地静态变量	定义在函数内部，有 `static` 属性	虚拟内存包含局部静态变量的唯一实例

临界区与不安全区

Head-(Load-Update-Store)-Tail

每个线程的 L-U-S 段被称为 临界区，两个线程临界区的“笛卡尔积”围城的区域称为 不安全区。

安全轨迹线与不安全轨迹线

需要保证两个线程对临界区的互斥访问。

信号量

void P(T s) {
    while (s == 0)
       	wait();
   	s--;
}

1
2
3

void V(T s) {
    s++;
}

信号量不变性：当初始 $s$ 非负时，之后的过程中 $s \ge 0$ 恒成立。

使用信号量来实现互斥

二元信号量：$0$ / $1$

互斥锁（mutex）：P “锁定”互斥锁，V “释放”互斥锁。

定义：

1 2	volatile long cnt = 0; /* Counter / sem_t mutex; / 一个保护 Counter 的信号量 */

初始化：

1	Sem_init(&mutex, 0, 1); /* mutex = 1 */

操作：

for (int i = 0; i < niters; i++) {
    P(&mutex);
    // do something...
    // 将临界区域用 P 和 V 操作包围
    V(&mutex);
}

生产者-消费者问题

$n$ 个槽的有限缓冲区，生产者线程反复生成新的项目，消费者线程不断地从缓冲区取出这些项目。

如果缓冲区是满的，那么生产者必须等待直到有一个槽位变为可用；
如果缓冲区是空的，那么消费者必须等待直到有一个项目变为可用。

用一个循环队列作为缓冲区。除了需要一个互斥锁来管理 buffer 是否可用之外，还要有两个互斥锁管理可用槽位数量和可用项目数量：不仅要有 slots，还要有 items。insert 的时候要等 slots 开锁；remove 的时候要等 items 开锁。

竞争

程序的正确性依赖于部分线程的执行顺序。

解决办法：为每个 ID 分配独立的块。

死锁

一组线程被阻塞了，等待一个永远也不会为真的条件。

死锁状态禁止向上或向右的拓展，这导致这个程序无法继续进行。

解决办法：

执行轨迹不要进入死锁区域
不同进程以相同的顺序获得锁
释放锁的顺序不重要

C 声明	C 声明	字节数	字节数
有符号	无符号	\(32\) 位	\(64\) 位
`[signed] char`	`unsigned char`	\(1\)	\(1\)
`short`	`unsigned short`	\(2\)	\(2\)
`int`	`unsigned`	\(4\)	\(4\)
`long`	`unsigned long`	\(4\)	\(8\)
`int32_t`	`uint32_t`	\(4\)	\(4\)
`int64_t`	`uint64_t`	\(8\)	\(8\)
`char*`		\(4\)	\(8\)
`float`		\(4\)	\(4\)
`double`		\(8\)	\(8\)

指令	基于	描述
\(\text{CMP} \quad S_1, S_2\)	\(S_2 - S_1\)	比较
`cmpb`		比较字节
`cmpw`		比较字
`cmpl`		比较双字
`cmpq`		比较四字
\(\text{TEST} \quad S_1, S_2\)	\(S_1 \& S_2\)	测试
`testb`		测试字节
`testw`		测试字
`testl`		测试双字
`testq`		测试四字

类型	条目	位置
节	ELF 头	\(0\)
节	`.text`
节	`.rodata`
节	`.data`
节	`.bss`
节	`.symtab`
节	`.rel.text`
节	`.rel.data`
节	`.debug`
节	`.line`
节	`.strtab`
描述目标文件的节	节头部表

符号类型	定义
全局符号	由模块 \(m\) 定义并能被其他模块引用
外部符号	由其他模块定义并被模块 \(m\) 引用
局部符号	只被模块 \(m\) 定义和引用（例如静态函数、静态全局变量）

符号	描述
\(N = 2^n\)	虚拟地址空间中的地址数量
\(M = 2^m\)	物理地址空间中的地址数量
\(P = 2^p\)	页的大小（字节）

符号	描述
VPO（\(p\) 位）	虚拟页面偏移量（字节）
VPN（\(n - p\) 位）	虚拟页号
TLBI	快表（TLB）索引
TLBT	快表（TLB）标记

符号	描述
PPO（\(p\) 位）	物理页面偏移量（字节）
PPN（\(m - p\) 位）	物理页号

整数