比特，字节和整数 Bits, Bytes, and Integers

布尔代数

位移操作：

左移 x << y：丢弃左边多余的位，右边补 0
右移 x >> y：
- 逻辑右移：左边补 0
- 算术右移：左边重复最高位
- c 语言默认为算术右移，Java 用 >>> 区分出逻辑右移
当位移长度 < 0 或 > 字长时，为定义

数字范围：

无符号：UMin = $0 = 000…0$ ，UMax = $2^w - 1 = 111...1$
补码：TMin = $-2^{w-1} = 100...0$ ，TMax = $2^{w-1}-1 = 011...1$

其它值： $-1 = 111...1$

编码整数：

无符号： $B2U(X) = \sum_{i=0}^{w-1} x_i 2^i$
补码： $B2T(X) = -x_{w-1} 2^{w-1} + \sum_{i=0}^{w-2} x_i 2^i$ ，其中 $x_{w-1}$ 表示的是符号位，0 是非负数，1 是负数

观察可以发现：

|TMin| = TMax + 1
UMax = 2 * TMAX + 1

两者之间转换时二进制表示不变，而是更换了解码方式，故

在无符号和有符号整数同时出现在一个表达式（包括比较操作）时，有符号值隐式转化为无符号值

扩展：将 w 位的整数保持大小不变，扩展到 w + k 位

无符号：加 0
有符号：重复 k 次符号位

截断：

无符号：模运算
有符号：类似于模运算

无符号加法：忽略溢出，相当于 mod $2^w$

有符号加法溢出会由正数变成负数，负数变成正数

乘法同样只留下了 w 位，忽略多余的位

无符号：

2 的次方乘法和位移：u << k 相当于 $u * 2^k$
2 的次方除法和位移：u >> k 相当于 $⌊ u / 2^k \rfloor$ ，使用逻辑位移

每个机器都有一个给定的字长 word size，表示处理的最大内存范围，现在多为 64 位

多字节的单词在内存中的存放顺序分为大端 Big endian 和小端，名称来自格列佛游记

大端（Sun，Internet）：最低位内存地址最大
小端（x86，ARM）：最低位内存地址最小

浮点 Floating Point

浮点右边的部分表示 2 的分数次幂

可以发现，只有形式为 $x/2^k$ 的数字可以精确表示

数字形式：

(-1)^sM2^E

$s$ 决定数字是正数还是负数（所以会区分 +0 和 -0），且溢出不会变化符号
$M$ 是尾码 significand，通常是表示 $[1.0,2.0]$ 的分数值
$E$ 是二的幂次的值

编码：

注意：

exp 编码 E，但与 E 有一些不同
frac 编码 M，但与 M 有一些不同

单精度各部分的长度为：1 - 8 - 23，双精度：1 - 11 - 52

正常值（exp != 000…0 且 exp != 111…1）：

阶码部分：E = exp - Bias，其中 Bias = $2^{k-1} - 1$ ，其中 k 是指数位数（单精度 bias 为 127）
尾码部分有隐藏的 1：M = 1.xxx…x，相当于白嫖了一个位

非规格化：（exp = 000…0）

指数：E = 1 - Bias
尾码部分有隐藏的 0：M = 0.xxx…x
exp = 000…0，frac != 000…0 时表示接近 0 的数字，等间距

特殊的值（exp = 111…1）

exp = 111…1，frac = 000…0：无穷大或操作溢出，可正可负
exp = 111…1，frac = 000…0：没有数字 NaN

数轴上的浮点

从这张表中可以看出为什么这么设计，实际上规格化和非规格化之间既实现了平滑过渡，又充分利用了每一位

结合两张图，不难看出浮点数的分布

在比较浮点时

先比较符号位
考虑 -0 = +0
考虑 NaN
其余同无符号整数

浮点计算：

先计算确切值
将其化为要求的精度

圆整 rounding：默认为向最近的偶数取整，这样做没有偏向

浮点的乘法：

符号：s1 ^ s2
尾码：M1 * M2
指数：E1 + E2
如果 M >= 2，右移 M，增加 E
溢出
round M 以填入 frac 精度

FP 加法/乘法的性质：

可交换，但不可结合（尤其是大数和小数之间的运算）
几乎可以单调（除了溢出和 NaN）

机器层次编程 I：基础 Machine-Level Programming I: Basics

反汇编：objdump -d sum

x86-64 有 16 个寄存器

%rax	%rbx	%rcx	%rdx
%rsi	%rdi	%rsp	%rbp
%r8	%r9	%r10	%r11
%r12	%r13	%r14	%r15

因为历史原因，r 代表 64 位，e 代表 32 位，如 %rax 的另一个名字是 %eax，其只使用 %rax 的低 32 位

移动数据：movq Source, Dest:

立即：整数常数，如 $0x400、$-533
寄存器：如 %rax
内存：用括号包围寄存器，如 (%rax)，表示 Mem[%rax]
不能操作两个内存

内存寻址的一般模式：D(Rb, Ri, S) 表示 Mem[Reg[Rb] + S*Reg[Ri] + D]

D：偏移常数字节
Rb：基本寄存器
Ri：索引寄存器
S：缩放 1，2，4，8 倍

leaq 指令可以提供一个简单的计算方式，如 leaq (%rdi, %rdi, 2), %rax 计算了 3 * %rdi 并保存到 %rax 中

还有一些算术操作，注意操作 op 是 dest = dest op src，这种写法是 ATT 写法，而微软和 Intel 的写法是相反的

二元指令：

名字	表示	名字	表示
`addq`	+	`subq`	-
`imulq`	*	`salq` / `shlq`	<<
`sarq`	算术 >>	`shrq`	逻辑 >>
`xorq`	^	`andq`	&
`orq`	\|

一元指令：

名字	表示	名字	表示
`incq`	+1	`decq`	-1
`negq`	-	`notq`	~

机器层次编程 II：控制 Machine-Level Programming II: Control

当前执行的程序的信息：

临时数据：%rax…
运行栈的位置：%rsp
当前代码控制点的位置：%rip…
最近 test 的状态：CF，ZF，SF，OF

单 bit 寄存器：

CF：进位（无符号）
SF：符号
ZF：零
OF：溢出（有符号）

显示设置这些位：testq src2, src1，相当于计算 a & b 但没有指定目的地

setX 指令：基于条件代码设置目标的最低字节是 0 还是 1，不改变其它 7 个字节

包括 sete，setg，…，注意 seta 是无符号整数的 >，setb 是无符号整数的 <，而 setg 是有符号整数的 >

movzbl 将 32 位的数复制到 64 位的 dest 中，并将剩余 32 位用 0 补齐，当然还有其他字节之间的数据移动 + 填充的指令

jX 指令：基于条件代码跳转到代码的不同地方，包括 jmp，jge 等

条件表达式翻译（使用分支）：val = Test ? Then_Expr : Else_Expr 转为

	ntest = !Test;
	if (ntest) goto Else;
	val = Then_Expr;
    goto Done;
Else:
	val = Else_Expr;
Done:
	...

流水线：预测两个分支哪个更有可能发生，在判断条件时提前计算出该分支的结果

do-while 比较简单：

loop:
	body
    if (Test)
        goto loop

while 有两种方式实现：

// 方法 1：跳转到中间的方法
	goto test;
loop:
	Body
test:
	if (Test)
        goto loop;
done:

// 方法 2：转化为 do-while
	if (!Test)
        goto done;
loop:
	Body
    if (Test)
        goto loop;
done:

for 转化为 while

Init;
while (Test) {
    Body
    Update;
}

switch 语句相对于多重 if 的好处是创建了一张 Jump 表，能够快速定位到对应的代码块中，而不是依次遍历，这张表由编译器生成

.L4
	.quad	.L8	# x = 0
	.quad	.L3	# x = 1
	.quad	.L5	# x = 2
	.quad	.L9	# x = 3
	.quad	.L8	# x = 4
	.quad	.L7	# x = 5
	.quad	.L7	# x = 6

switch_eg:
	movq	%rdx, %rcx
	cmpq	$6, %rdi	# x: 6
	ja		.L8			# 使用默认
	jmp		* .L4(, %rdi, 8) # goto *JTab[x]

如果 switch 的分支范围特别大，如只有 0 和 1000，则会建立一个 if-else 树

机器层次编程 III：程序 Machine-Level Programming III: Procedures

x86的栈

注意这里的栈口朝下，添加元素时栈顶的地址减小

pushq Src

获取 Src 处的操作数
将 %rsp 减少 8
在 %rsp 的地址处写操作数

popq Dest

读 %rsp 所给地址处的值
将 %rsp 增加 8
在 Dest（必须是寄存器）处存放值

过程控制流：

调用：call label
- 将返回地址放入栈中
- 跳转到 label
返回：ret
- 从栈中 pop 地址
- 跳到该地址

数据流：

前 6 个参数放到 %rdi、%rsi、rdx、rcx、r8、r9，多出来的放到栈中
返回值在 %rax 中

本地数据管理：栈在栈帧 frame 中分配

frame 内容：

返回信息
本地存储
临时存储

当进入程序时建立，返回时释放

寄存器保存惯例：

caller：在 call 之前在它的 frame 中保存临时变量
callee：在使用之前它的 frame 中保存临时变量，在返回 caller 之前恢复

该方法对于递归和相互调用都有效

机器层次编程 IV：数据 Machine-Level Programming IV: Data

数组 T A[L]：在内存中连续分配 L * sizeof(T) 个字节的区域

索引数组 (%rdi, %rsi, 4)

%rdi 是数组名地址
%rsi 是索引
4 是每个基本元素的字节数

多维数组 A[i][j] 的类型是 T，该类型需要 K 字节，故地址 A + (i * C + j) * K

注意对于一个已知大小的矩阵数组（如 16 x 16），则只需通过 salq $6, %rsi 移动获得索引，而如果编译时未知维度（如 n x n），则使用乘法 imulq %rdx, %rdi 获得索引

结构体要对齐数据：

原始数据类型需要 K 字节，则其地址必须是 K 的整数倍

最大的对齐需要 K，则整个结构体必须是 K 的整数倍

为了节省空间，可以把大的数据类型放前面，这种贪心策略是最优的

对于浮点数，用 XMM0-15 的寄存器存储和传递参数，有专门的浮点运算指令

机器层次编程 V：进阶主题 Machine-Level Programming V: Advanced Topics

内存布局

当堆中需求的内存过大时，会从上面往下开辟堆空间

缓冲区溢出，如 gets，可能覆盖下面的 ret 命令，使其跳转到自己想要执行的程序

蠕虫 Worm：

可以自己运行
可以向其它电脑复制一份完全工作的自己

病毒 Virus：

把自己添加到其它程序中
不能独立运行

解决方法：

避免代码中的溢出问题，如使用 fgets 代替 gets
系统级别的防护，如随机化栈的偏移，给不同的段加上可读、可写、可执行的权限
使用金丝雀，即在缓冲区中放上一个随机的数，检查执行完函数后改数字是否改变

联合体 Union 是将不同的类型合并占用

程序优化 Program Optimization

通用方法：

代码移动：减少计算次数，尤其是在循环中

long j;
for (j = 0; j < n; j++)
    a[n*i+j] = b[j];

// 改为
long j;
int ni = n * i;
for (j = 0; j < n; j++)
    a[ni+j] = b[j];

事实上，如果使用了 -O1 优化，则编译生成了代码就使用了类似的原理

将花费多的操作换成更简单的，如将 *4 换成 <<2

共享共同的子表达式，如

(i-1)*n + j;
(i+1)*n + j;
i*n + j-1;
i*n + j+1;

// 改成
long inj = i*n + j;
inj - n;
inj + n;
inj - 1;
inj + 1;

过程调用：

size_t i;
for (int i = 0; i < strlen(s); i++)
    if (s[i] >= 'A' && s[i] <= 'Z')
        s[i] -= ('A' - 'a');

该算法是二次的，因为重复调用了 strlen(s)，这个方法是线性的，所以应该改成

size_t i;
size_t len = strlen(s);
for (int i = 0; i < len; i++)
    if (s[i] >= 'A' && s[i] <= 'Z')
        s[i] -= ('A' - 'a');

而编译器一般不会优化这点，是因为

过程可能有副作用
函数可能会对给定参数返回不同的值（修改了 s[i]）

解决方法：

使用内联 inline 函数（gcc -O1 会这么做）（只能在单个文件中）
手动移动代码

内存很重要：

for (i = 0; i < n; i++) {
    b[i] = 0;
    for (j = 0; j < n; j++)
        b[i] += a[i*n + j];
}

从汇编代码中可以看出，编译器在每次循环中都从内存中取出 b[i] 放到寄存器中，计算完再放回去，因为其无法确定修改了 b[i] 会不会影响 a[i]，即两个数组使用了相同的内存。故应修改为：

for (i = 0; i < n; i++) {
    double val = 0;
    for (j = 0; j < n; j++)
        val += a[i*n + j];
    b[i] = val;
}

每个元素的循环 Cycles Per Element(CPE)：用来表达对 list 的效率

T = CPE*n + Overhead

void combine1(vec_ptr v, data_t *dest) {
    long int i;
    *dest = IDENT;
    for (i = 0; i < vec_length(v); i++) {
        data_t val;
        get_vec_element(v, i, &val);
        *dest = *dest OP val;
    }
}

基础的优化：

减少对 vec_length(v) 的调用
避免在每轮循环中 get_vec_element 检查越界
临时计算

void combine4(vec_ptr v, data_t *dest) {
    long i;
    long length = vec_length(v);
    data_t *d = get_vec_start(v);
    data_t t = IDENT;
    for (i = 0; i < length; i++)
        t = t OP d[i];
    *dest = t;
}

该优化立刻提升了许多倍速度，但似乎受到了一些限制，原因是 CPU 在执行每个操作时都有“读取-计算-存入”的操作，每个阶段都会花费一些时间

很多现代的 CPU 都支持流水线 pipeline，即在一个循环中同时处理多条指令，基本思想是在某计算执行到 stage2 时，执行下一个不依赖于该指令结果的指令于 stage1，以此类推

combine4

效率由延迟决定

循环展开（2*1）

long limit = length - 1;
for (i = 0; i < limit; i += 2)
    x = x (d[i] OP d[i+1]);
for (; i < length; i++)
    x = x OP d[i];
*dest = x;

循环展开（2x1）

可以发现延迟短了一半

另一种展开方式：

data_t x0 = IDENT;
data_t x1 = IDENT;
for (i = 0; i < limit; i += 2) {
    x0 = x0 OP d[i];
    x1 = x1 OP d[i+1];
}
for (; i < length; i++)
    x0 = x0 OP d[i];
*dest = x0 OP x1;

如果使用计算浮点数的硬件，可以一次计算多个整数的加法或乘法，且 ymm 寄存器通常并不在使用

SIMD操作

对于分支，会猜测执行哪个分支，并优先执行该分支的内容，正确率 >90%

内存层次结构 The Memory Hierarchy

内存有两类：

SRAM（较快、贵，通常用于 cache）
DRAM（比 SRAM 慢、便宜，用于主要的内存、frame buffer）

这两者断点都会丢失消息

非易失性 memory：

ROM：只读存储器
PROM：可编程 ROM
EPROM：可大容量擦除 PROM
EEPROM：电子 EPROM
闪存 EEPROMs：部分（block 级）可删除
通常用于磁盘

总线 bus 是一堆能传递地址、数据、控制信号的线，被多个设备共用

磁盘 disk 由盘片 platters 组成，每个有两个表面 surfaces
每个 surface 由多个叫磁道 tracks 的同心圆组成
每个 track 由被空隙 gaps 分割的扇区 sectors

磁盘几何结构

从多个 platter 来看，多个对齐的 track 形成一个圆柱

磁盘容量 = (# bytes/sector) _ (avg. # sectors/tracks) _ (# tracks/surfaces) _ (# surfaces/platter) _ (platters/disk)

磁盘操作

磁盘访问

Taccess = Tavg seek + Tavg rotation + Tavg transfer

其中 Tavg seek 被物理因素限制，无法提升，其余两个可以通过磁盘转速提升

逻辑硬盘块：

硬件设备硬盘控制器将逻辑块（0,1,2…）映射到实际扇区中
有一些备用圆柱面，当一些扇区损坏时，可以将损坏扇区的逻辑块映射给备用柱面，实现硬盘坏了但没有完全坏

IO总线

固态硬盘 Solid State Disk(SSDs)

固态硬盘

页：512KB 到 4KB，块：32 到 128 页
必须以页为单位读写数据
只有在整个块被擦除时，页才能被写入
一个块在大约 100000 次写入后失效

所以顺序读写会比随机读写快很多

我们可以观察到，SRAM,DRAM,SSD,Disk 的速度有显著的差距（价格也是），为了以更低的价格获得更快的速度，需要架起桥梁

局部性 locality：程序倾向使用靠近或等于最近使用的数据或指令

时间：最近引用的物品更可能在不久的将来再次引用
空间：地址相近的物品倾向于一起被引用

for (i = 0; i < M; i++)
    for (j = 0; j < N; j++)
        sum += a[i][j];

该程序有良好的局部性，若将 i，j 的循环顺序颠倒，则速度大幅下降

内存层次结构

缓存 cache：一个更小、更快的存储设备，充当暂存

程序倾向于使用 k 层中的数据，而不是 k+1 层的数据

如果成功使用了 cache 中的内容，则称为缓存命中 cache hit；反之，则为 miss

缓存内存 Cache Memories

一般缓存组织

字地址

读操作：靠索引获取 set 位置，比较 tag，若不同，则 miss，查找下一级内存；若相同，则 hit，使用该 cache 中的内容

写：

hit：将写回内存的时间推迟到这里的内容被覆盖（需要一个脏位 dirty bit），类似于线段树的 tag 标记
miss：载入到 cache 中，更新 cache 的内容

所以

对变量的重复引用是好的（temporal locality）
步伐为 1 的模式是好的（spatial locality）

内存山：考虑到 spatial 和 temporal locality 的内容 read through

内存山

对于矩阵乘法，分别计算三种循环方式

ijk 每次迭代的 miss 为 1.25
kij 为 0.5
ikj 为 2.0

故以下代码是最优的：

for (k = 0; k < n; k++)
    for (i = 0; i < n; i++) {
        r = a[i][k];
        for (j = 0; j < n; j++)
            c[i][j] += r * b[k][j];
    }

分块矩阵乘法：

int i, j, k;
for(i=0;i<n;i+=B)
	for (j=0;j<n;j+=B)
		for(k=0;k<n;k+=B)
			/* B x B mini matrix multiplications */
			for (il=i;il<i+B;i++)
				for (jl = j; jl < j+B; j++)
					for (k1=k;k1<k+B;k++)
						c[il*n + j1] += a[il*n + k1] * b[k1*n + j1];

通过计算可以得到

不使用分块 $(9/8)*n^3$
使用分块 $1/(4B) * n^3$

似乎 B 越大越好，但有限制 $3B^2 < C$

因为矩阵乘法有固有的局部性，输入 $3n^2$ ，输出 $2n^2$ ，必然有数据重复使用

链接 Linking

多个 .o 文件通过链接器 linker 链接在一起

链接器的优点：

模块化
高效。时间上：无需重新编译其他文件；空间上：常用函数不必包含于每个文件中

链接器的用途：

符号解析 symbol resolution：将每个符号引用与一个符号定义关联
重定向 relocation：将数据和代码分割到不同的段中，重定向符号的关联位置，更新所有对符号的引用

三种对象文件：

重定向对象文件（.o 文件）
可执行对象文件（a.out 文件）
共享对象文件（.so 文件），Windows 中的 DLL 文件

这三者都使用了 ELF (Executable and Linkable) 格式

头
段头表 segment header table
.text 段：代码
.rodata 段：只读数据，如 jump table
.data 段：初始化全局变量
.bss 段：未初始化的全局变量，理由是 “better save space”
.symtab 段：符号表，过程和静态变量名，段名和位置
.rel.text 段：.text 段的重定位消息，需要被修改的指令地址
.rel.data 段：.data 段的重定位消息
.debug 段：符号调试的信息，gcc -g
段头表 section header table：每个段的偏移和大小

ELF结构

链接器符号：

全局符号，如非 static 函数和非 static 全局变量
外部符号，定义在其他模块，被模块 m 引用的全局变量
局部符号，被模块 m 定义和引用的符号，如使用 static 的函数和全局变量，注意局部链接器符号不是局部程序变量

程序符号有 strong 和 weak 之分：

strong：过程和初始化的全局变量
weak：未初始化的全局

符号规则：

不允许多个强符号
如果有一个强符号和多个弱符号，使用强符号
如果有多个弱符号，任选一个

所以为了防止这种冲突覆盖发生，可以：

使用 static
定义全局变量时初始化
引用外部全局变量时使用 extern

链接时多个可重定位对象文件的各个段组合到一个可执行对象文件的一个段中：

重定位

静态库：(.a archive files)使用索引将相关的可重定位文件合并到一个文件中

这样做允许增量更新，只需要重新编译 archive 中改变和替换 .o 文件

静态库

静态链接

共享库（DLL，.so 文件）：可以动态将代码和数据装载并链接到应用程序中，装载时间和运行时间都可以

装载时动态链接

运行时动态链接：

int main() {
    void  *handle;
    void (*addvec)(int *, int *, int *, int);
    char *error;
    /* 动态装载包含 addvec 的共享库 */
    handle = dlopen("./libvector.so", RTLD_LAZY);
    if (!handle) {
        fprintf(stderr, "%s\n", dlerror());
        exit(1);
    }

    /* 获取指向 addvec() 函数的指针 */
    addvec = dlsym(handle, "addvec");
    if ((error = dlerror()) != NULL) {
        exit(1);
    }

    /* 调用 addvec() */
    addvec(x, y, z, 2);
    /* 卸载共享库 */
    if (dlclose(handle) < 0) {
        exit(1);
    }
    return 0;
}

库插入 Library Interpositioning：拦截对任意函数的调用，同样可以发生在编译、链接、装载、运行时

可用于安全、调试、监视和追踪等

编译时拦截：

gcc -Wall -DCOMPILETIME -c mymalloc.c
gcc -Wall -I. -o intc int.c mymallo.c

链接时拦截：

gcc -Wall -DLINKTIME -c mymalloc.c
gcc -Wall -c int.c
gcc -Wall -Wl,--wrap,malloc -Wl,--wrap,free -o intl

-Wl 向链接器传递参数
--wrap,malloc 表示对 malloc 的引用替换为 __wrap_malloc，对 __real_malloc 的引用替换为 malloc

运行时拦截：

gcc -Wall -DRUNTIME -shared -fpic -o mymalloc.so mymalloc.c -ldl
gcc -Wall -o intr int.c
(LD_PRELOAD="./mymalloc.so" ./intr)

LD_PRELOAD 环境变量告诉动态链接器先查看 mymalloc.so 寻找未解决的引用，如 malloc

异常控制流：异常和进程 Exceptional Control Flow: Exceptions and Processes

一般来说，CPU 按顺序依次执行指令

有两种改变控制流的方法：

程序状态：
- 跳跃和分支
- 调用和返回
但还有系统状态：
- Ctrl - C
- 除零

即异常控制流 Exceptional Control Flow（ECF）

其存在于计算机系统的所有层次：

低层次：
- 异常 Exception
高层次：
- 过程上下文切换 Process context switch
- 信号 Signal
- 非本地跳跃 Nonlocal jumps

异常是为了响应一些事件，将控制转移给操作系统内核 OS kernel

异常表 Exception Tables：每个事件都有一个独有的异常号 k

异常分类：

异步异常 asynchronous
- 打断 interrupt
  - 由处理器的 interrupt pin 指示
  - 返回到 next 指令
  - 计时器中断/外部设备 IO
同步异常 synchronous
- 陷阱 trap
  - 返回到 next
  - system call
- 错误 fault
  - 可能重新执行或终止
  - 页错误 page fault（可恢复），保护错误 protection fault（不可恢复）
- 终止 abort
  - 终止当前程序
  - 错误指令

进程 process：一个运行着的程序的实例*（注意不同于程序 program 和处理器 processor）*

进程为每个程序提供了两个关键的抽象：

逻辑控制流
- 每个程序似乎可以利用整个 CPU
- 由上下文切换 context switch 实现
私有地址空间
- 每个程序似乎可以利用整个内存
- 由虚拟内存 virtual memory 提供

并发过程 concurrent process：两个过程的流在时间上有重叠

否则称为顺序 sequential

过程由内存中的 OS 代码叫做内核 kernel 的东西管理

内核不是一个单独的进程，而是作为某个存在的进程运行

从一个过程到另一个的控制流切换通过上下文切换 context switch

系统调用：Linux 系统函数如果出错，通常返回 -1 并设置全局变量 errno 来指示原因

法则：对于每个系统级函数都必须检查返回值，如

if ((pid = fork()) < 0) {
    fprintf(stderr, "fork error: %s\n", strerror(errno));
    exit(0);
}

为了简化代码，可以使用 Stevens 风格的错误处理包装函数，如：

pid_t Fork(void) {
    pid_t pid;

    if ((pid = fork()) < 0)
        unix_error("Fork error");
    return pid;
}

pid = Fork();

获取进程 ID：

pid_t getpid(void) 返回当前进程 PID
pid_t getppid(void) 返回父进程 PID

进程有三种状态：

运行中 running：在执行、等待执行、将会被安排 schedule
停止 stopped：被暂停 suspended，直到信号到来不会被安排
终止 terminated

进程终止的原因：

结束到信号
从 main 过程返回
调用 exit 函数（调用一次，不返回）

创建进程：int fork(void)

对于子进程返回 0，对于父进程返回子进程的 PID（调用一次，返回两次）
子进程和父进程几乎相同：
- 复制了虚拟内存地址
- 复制了打开的文件描述符
- 和父进程的 PID 不同

fork：

并发执行
重复但独立的地址空间
共享打开的文件

进程图

每个进程图的拓扑序都是一个可行的顺序

收割子进程：当进程终止时，仍消耗系统资源，被称作僵尸

由父进程对终止的子进程使用（用 wait 和 waitpid）
父进程被提供退出状态信息
内核删除僵尸子进程

如果有父进程在没有收割子进程就终止了，则该子进程会被 init （pid = 1）的进程收割。但在长时间运行的进程还是需要显示收割

int wait(int *child_status)

暂停直到一个它的子进程终止
返回终止的子进程的 PID
child_status 指向的整数会被设为一个值指示子进程终止的原因和退出状态
- 可以使用 wait.h 中定义的宏检查，包括 WIFEXITED、WEXITSTATIS等

pid_t waitpid(pid_t pid, int &status, int options) 等待一个指定的进程

int execve(char *filename, char *argv[], char *envp[])

装载并在当前进程中执行
argv[0] == filename
调用一次，无返回

新程序开始的栈

异常控制流：信号和非本地跳转 Exceptional Control Flow: Signals and Nonlocal Jumps

信号 signal 是通知一个进程某事件发生了的小信息

由小整数 ID（1-30）识别
唯一的信息是它的 ID 和它抵达的事实

ID	名字	默认动作	对应事件
2	SIGINT	终止	键入 ctrl-c
9	SIGKILL	终止	杀死程序（不可重载或忽略）
17	SIGCHLD	忽略	子进程停止或终止了

一些对信号的反应：

忽略 ignore
终止进程
用执行用户级别的信号处理器 signal handler 捕捉信号（类似与硬件级别的）

如果一个信号被发送了但还没有被接收，则称为待定 pending

注意：信号不会排队，即有一个待定的类型 k 的信号，则接下来的所有类型为 k 的信号都被忽略

进程可以阻塞 block 特定信号的接收

被阻塞的信号可以发送，但直到被解除阻塞前都不会被接收

内核在每个进程的上下文中维持了 pending 和 blocked 位向量，用第 k 位表示

每个进程属于一个进程组

getpgrp() 返回当前进程组
setpgid() 改变当前进程组 ID

正数表示对某个进程操作，负数表示对某个进程组操作

键入 Ctrl + C 表示对每个前台的进程组发送 SIGINT 信号

内核计算 pnb = pending & ~blocked

如果 pnb == 0 则执行下一条指令
反之选择 pnb 中最小的非零位，并执行相关的信号开关

handler_t *signal(int signum, handler_t *handler) 修改信号 signum 的默认接收行为

信号处理器的控制流

隐式阻塞信号：内核阻塞任何当前处理的同类型的信号

显式阻塞：sigprocmask 函数

系统层次输入/输出 System-Level I/O

文件 file 是字节序列

所有的 I/O 设备都被表示为文件
内核也被表示为文件

Unix I/O 接口：

打开和关闭文件：open() 和 close()
读和写文件：read() 和 write
改变当前文件位置（seek）：lseek()

文件类型：

一般文件 regular file
目录 directory
套接字 socket

一般文件：

应用程序往往区分为文本文件和二进制文件，但内核不区分
文本文件由文本行组成，EOL 在 Windows 和 Internet 协议中使用 ‘\r\n’(0xd 0xa)(CRLF)，在 Linux 和 Mac OS 中使用 ‘\n’(0xa)(LF)

目录：由许多链接 link 组成

. 指向它自己的链接
.. 父目录的链接

打开文件：fd = open("/etc/hosts", O_RDONLY)

返回一个文件描述符 file descriptor

若为 -1，则出错
0：stdin
1：stdout
2：stderr

关闭文件：retval = close(fd)

在多线程程序中关闭一个已经关闭的文件会出错

读文件：nbytes = write(fd, buf, sizeof(buf))

返回写入 buf 的字节数

短计数 short count 通常出现在

遇到 EOF
从终端读文本行
读写网络套接字

RIO 是更健壮 robust 的 I/O 包装，用于网络程序，提供两种类型的函数：

无缓冲的二进制数据：rio_readn 和 rio_writen
有缓冲的文本和二进制数据：rio_readlineb 和 rio_readnb
- 线程安全，可以在相同文件上任意交错

有缓冲的IO实现

元数据 metadata 是数据的数据，通过 stat 和 fstat 函数访问

文件打开

文件共享

文件fork

I/O 重定向：ls > foo.txt 使用了函数 dup2(oldfd, newfd)

IO重定向

C 语言提供了标准 I/O 函数：

打开和关闭文件：fopen 和 fclose
读和写二进制文件：fread 和 fwrite
读和写文本文件：fgets和fputs`
格式化读和写：fscanf 和 fprintf

其中使用了 buffer，一般遇到 \n 时自动刷新 flush，也可以使用 fflush(fd) 手动 flush

三种IO方式

一般来说使用标准 IO 即可，在使用网络时使用 RIO，在信号处理器中使用 Unix IO

虚拟内存：概念 Virtual Memory: Concepts

使用内存管理单元 memory manage unit 将虚拟地址转化为物理地址

虚拟内存

虚拟内存优点：

主内存的效率更高
简化内存管理
隔离地址空间

内存页 page 的大小一般为 4KB，有的是 4MB

页表 page table 是**页表项 page table entries（PTE）**的数组，其将虚拟页映射到物理页

当对虚拟内存的引用没有出现在物理内存中时，出现页错误 page fault，处理器选择一个受害者逐出，然后将需要的虚拟内存地址指向物理内存，并重新执行上一条指令

虚拟内存看似低效，但因为局部性，效率不错

程序倾向于访问活跃的虚拟内存页的集合叫工作集合 working set，时间局部性较好的程序 working set 较小

虚拟内存对内存管理很有用：

简化内存分配
在进程间共享代码和数据

虚拟内存也有利于保护内存：

PTE 有许可位
MMU 在每次访问时检查这些位

地址转换的符号：

参数
- $N = 2^n$ ：虚拟地址空间的地址数
- $M = 2^m$ ：物理地址空间的地址数
- $P = 2^p$ ：页大小
虚拟内存 VA
- TLBI：TLB 索引
- TLBT：TLB 标签
- VPO：虚拟页偏移
- VPN：虚拟页数字
物理地址 PA
- PPO：物理页偏移
- PPN：物理页数字

地址翻译

地址翻译：页命中

地址翻译：页错误

使用的缓存是转译后备缓冲器 translation lookaside buffer(TLB)

多级页表：解决使用过多空间的问题

二级页表层次结构

k级页表

虚拟内存：系统 Virtual Memory: Systems

酷睿i7内存系统

酷睿i7地址翻译

加快 L1 访问的技巧：因为物理地址和虚拟地址的偏移是相等的，所以可以直接将其加入到缓存中

Linux 将地址组成叫做 area 的集合，即一个个的内存段

Linux内存

页错误处理

**写时复制 copy-on-write（COW）**的策略：两个进程先共享同样的内存，若想要修改该内存，则需复制一份

fork 就使用了这种策略，故速度很快，只有在需要是才会复制

页错误处理

写时复制

void *mmap(void *start, size_t length, int prot, int flags, int fd, off_t offset) 可以对指定文件创建一个虚拟内存地址，这样就做到了只有在需要读的时候才会写入内存

动态内存分配：基本概念 Dynamic Memory Allocation: Basic Concepts

程序员在运行时使用动态内存分配器 Dynamic Memory Allocators（例如 malloc）获取 VM，因为一些数据结构只有在运行时才能得知其大小

动态内存分配器维护的 VM 区域叫堆 heap

分配器把堆作为大小为块 blocks 的变量，其只有已分配 allocated 和释放了 free

分配器的类型：

显式分配器：应用分配空间和释放空间，如 malloc 和 free
隐式分配器：应用分配空间，但不释放空间，如 garbage collector

void *malloc(size_t size)：

成功时返回一个至少为 size 对齐于 8 byte（x86）或 16 byte（x86-64）的内存块的边界的指针
未成功：返回 NULL 并设置 errno

void free(void *p)：

返回被 p 指向的可用区域的块
p 必须从 malloc 或 realloc 得来

其它函数：

calloc：初始化变量为 0 的 malloc
realloc：改变之前分配的块的大小
sbrk：被分配器在其内部使用以增大或减小堆的大小

约束：

对于应用：

可以发出任意 malloc 和 free 的请求序列
free 请求必须对应 malloc 块

对于分配器：

无法控制已分配的块的数量和大小
必须立刻回应 malloc 请求
必须从空闲的内存中分配块
必须返回的块对齐
可以操作或修改空隙内存，但不能移动已分配块

表现目标：

吞吐量 throughput：每单位时间完成的请求数量
峰值内存使用 peak memory utilization：在 k + 1 次请求后， $U_k = (\max_{i<=k} P_i) / H_k$ ，其中 $P_k$ 表示负载 payload， $H_k$ 表示当前堆大小

内部碎片 internal fragmentation：负载小于块大小，主要由维护堆的数据结构的开销和对齐造成

外部碎片 external fragmentation：有足够的内存，但没有空闲的块足够大

跟踪空闲块：

使用长度隐式列表（链接所有的块）
使用指针对所有空闲块显式列表
分开空闲列表，如把不同大小的类分成不同的列表
通过大小排序块，如使用平衡树用指针指向空闲块，长度作为键使用

方法一：隐式列表

因为块是对齐的，所以一些地位地址总是 0，所以可以用其当作分配的状态位

找到一个空闲块：

第一次合适：从开头搜索，选择第一个合适的块
下一个合适：从上一次结束的地方开始搜索，其余和第一次合适一样
最优匹配：选择最优的空闲列表

在空闲块中分配：分裂 split

释放块：需要合并 coalesce 之前的和下一个空闲的块

查找前一个块的方法是边界标签，即在块的尾部添加和头部一样的标签，同时只有分配的才需要

边界标记

合并策略：

立即合并
推迟合并

动态内存分配：进阶概念 Dynamic Memory Allocation: Advanced Concepts

显式列表：类似于一个链表

显式列表结构

释放：插入策略：

LIFO
地址顺序

分开列表 segregated list

垃圾回收 garbage collection：C 语言中是保守的 conservative，因为无法区分指针和非指针

把内存视为一个有向图：

块是节点
指针是边
不在堆中的包括指向堆的指针叫 root 节点

标记和清扫 Mark and Sweep：使用 malloc 直到用尽空间

在每个块的头部使用标记位
标记：从根开始标记每个可到达的块
清扫：搜索所有的块并释放没有标记的块

对于指针，注意运算符优先级

常见错误：

scanf 没有使用 &
假设堆的数据已经初始化
分配错误大小的对象
数组索引多了 1
没有检查最大 string 大小
误解指针算术
引用不存在的变量，如局部变量
多次释放块
引用释放的块
忘了释放块

网络编程 Network Programming

客户端-服务器交易 Client-Server Transaction：

一个服务器进程和一个或多个客户端进程
服务器管理一些资源 resource
服务器通过操作资源为客户端提供服务 service
服务器被客户端的请求激活

将网络抽象为一个文件

网络 network 是主机的系统的集合，包括 SAN，LAN，WAN

internet 是相互连接的网络的集合

最低层级：以太网段 Ethernet segment 由主机 hosts 由线连接为一个 hub 组成

下一个层级：桥接的以太网

下一个层次：internet，通过路由器 routers 连接多重不兼容的 LAN

协议 protocol：

提供命名方案：主机地址
提供分发机制：定义了转移单位包 packet，包由 header 和 payload 组成

全局 IP Internet，基于 TCP/IP 协议：

IP（Internet Protocol）：提供基本命名方案和不可靠的从主机到主机的包的分发兼容性
UDP（Unreliable Datagram Protocol）：使用 IP 提供不可靠的从进程到进程的数据分发
TCP（Transmission Control Protocol）：使用 IP 提供可靠的通过连接的从进程到进程的字节流

通过 Unix 文件 I/O 和套接字接口 socket interface 中的函数访问

主机被映射为一个 32 位的 IP 地址 IP address
IP 地址集合被映射为一个标识符集合叫做 Internet 域名 domain names
一个 Internet 主机上的进程可以通过连接 connection 和另一个主机上的进程交流

IPv4 和 IPv6

IP 地址：被储存在一个 IP 地址结构中，为大端序

struct in_addr {
    uint32_t s_addr;
}

使用这个 struct 可以不用手动转换大端序和小端序

转换二进制 IP 地址和用点分割的十进制字符串的函数：（“n” 表示 network，“p” 表示 presentation）

inet_pton：string -> IP address
inet_ntop：IP address -> string

Internet 使用域名系统 Domain Naming System（DNS） 维护从 IP 地址和域名的映射，使用的是一个巨大的全世界范围的分布式数据库，可以将其视为许多条主机项的集合，主机项定义了域名集合与 IP 地址的映射

多个域名被映射到多个 IP 地址，有些有效的域名没有被映射到任何 IP 地址

每个连接是：

点对点的
完全双重的 full-deplex
可靠的

套接字 socket 是一个连接的终点

端口 port 是一个 16 位整数，其识别一个进程：

短暂的 ephemeral，当客户端发起一个连接请求时，客户端内核自动分配
众所周知的 well-know，如 80 端口被用于 web

一些常见的服务和对应的端口：

echo：7/echo
ssh：22/ssh
email：25/smtp
web：80/http

端口-服务名的映射别储存在 Linux 的 /etc/services

套接字：

对内核来说，socket 是通信的终点
对应用来说，socket 是一个让应用读写网络的文件描述符

客户端和服务器通过读写 socket 描述符通信

Internet 的 socket 地址：

struct sockaddr_in {
    uint16_t sin_family; // 通常是 AF_INET
    uint16_t sin_port;
    struct in_addr sin_addr;
    unsigned char sin_zero[8]; // 填充
}

socket 接口：

socket：int socket(int domain, int type, int protocol);，一般使用 getaddrinfo自动生成参数，则无关协议
bind：int bind(int sockfd, SA *addr, socklen_t addrlen);，将 socket 地址和 socket 描述符联系到一起
listen：int listen(int sockfd, int backlog);，用于告诉内核一个描述符会被用于服务网而不是客户端
accept：int accept(int listenfd, SA *addr, int *addrlen); 等待连接请求到达该连接，并在 addr 中填充客户端的 socket 地址和大小，返回用于交流的描述符
connect：int connect(int clientfd, SA *addr, socklen_t addrlen);，建立连接

getaddrinfo 是转换字符串表示的主机名，主机地址，端口和服务名为 socket 地址的方法：

int getaddrinfo(const char *host, // 主机名或地址
                const char *service, // 服务名或端口
                const struct addrinfo *hints,
                struct addrinfo **result); // 输出一个链表
void freeaddrinfo(struct addrinfo *result); // 释放链表
const char *gai_strerror(int errcode); // 返回错误信息

getnameinfo 是 getaddrinfo 的逆，将 socket 地址转为主机和服务：

int getnameinfo(const SA *sa, socklen_t salen, // 输入：socket 地址
                char *host, size_t hostlen,		// 输出：host
                char *serv, size_t servlen,		// 输出：service
                int flags);

Web 服务：

使用超文本传输协议 HyperText Transfer Protocol(HTTP) 通信，当前版本是 HTTP 2.0

Web 服务返回内容 content 给客户端，内容是一个 MIME（Multipurpose Internet Mail Extensions） 类型的字节序列

返回的内容可以是静态的，也可以是动态的

每个文件专有的名字：URL（Universal Resource Locator)

对于 URL：https://old-driver-zero.github.io:443/index.html

客户端使用前缀 https://old-driver-zero.github.io:443 推断：
- 使用何种协议（HTTPS）
- 那个服务器（old-driver-zero.github.io）
- 哪个端口（443）
服务器使用后缀（/index.html）来：
- 确定是静态的还是动态的内容（没有硬性规定，但一个惯例是：可执行文件储存在 cgi-bin 目录下）
- 在文件系统上找到文件：
  - 使用 / 分割
  - 最小前缀是 /，服务器将其扩展为配置好的文件名（一般是 index.html）

HTTP 请求是一个请求行 request line，跟着零或更多请求头 request headers

请求行：<method> <uri> <version>
- <method> 是 GET, POST, OPTIONS, HEAD, PUT, DELETE, TRACE 之一
- <uri> 是代理的 URL，URL 是 URI 的一个类型
- <version> 是 HTTP 版本
请求头：<header name>: <header data>

HTTP 回应是一个回应行，跟着零或更多回应头 request headers，空行用 \r\n 分割

回应行：<version> <status code> <status msg>
- <version> 是 HTTP 版本
- <status code> 是数字状态，如 404
- <status msg> 是相关的英语文本
回应头：<header name>: <header data>

并发编程 Concurrent Programming

并发编程很难，因为

人类的头脑倾向于顺序
时间经常被忽略
考虑所有可能的事件顺序很难

并发程序的问题分类：

竞争 race：结果取决于任意调度
死锁 deadlock：阻碍继续前进
饿死 starvation：轮不到你

迭代式服务器：一次处理一个请求

写并发服务器的方法：

基于进程：
- 内核自动交错多个逻辑流
- 每个流有它自己的私有地址空间
基于事件：
- 程序员手动交错多重逻辑流
- 所有流共享相同的地址空间
- 使用被称作 I/O 多路复用的技术
基于线程：
- 内核自动交错多重逻辑流
- 每个流共享相同的地址空间
- 算是前两者的杂交

基于进程的服务器：

基于进程的服务器

因为父和子进程都有 listenfd 和 connectfd 的复制，所以

父必须关闭 connfd
子应该关闭 listenfd

且必须收割僵尸子进程

基于事件的服务器：决定哪个描述符有待定的输入，例如使用 select 或 epoll 函数，待定的输入的到达是一个事件

进程 = 进程上下文 + 代码，数据和栈

线程 = 线程 + 代码，数据和内核上下文

一个有多线程的进程

线程和线程形成一个 peer 池，而进程形成树层次结构

逻辑视角

线程的花费比进程小

POSIX 线程（Pthread）接口：

创建和收割线程：pthread_create(), pthread_join()
确定自己的线程 ID：pthread_self()
终止线程：pthread_cancel(), pthread_exit()

线程在 detached 模式中运行：

一个线程要么是可连接 joinable，要么是脱离的 detached
一个可连接的线程可以被其他线程收割或杀死，必须使用 pthread_join 释放内存资源
脱离的线程不可以被被其他线程收割或杀死，终止时资源自动被内核收割
默认状态是可连接的，使用 pthread_detach(pthread_self()) 脱离

同步：基础 synchronization：Basics

定义：当且仅当多个线程引用某个 x 的实例，则称变量 x 是共享的 shared

全局变量：

在函数外声明
虚拟内存包括一个全局变量实例

局部变量：

在函数内部声明，没有 static
每个线程栈包括每个局部变量的一个实例

局部静态变量：

在函数内声明，有 static
虚拟内存包括一个局部静态变量实例

并发执行：一般来说，任何顺序一致的交错都是可能的，但是有些给出意料之外的结果

过程图 progress graph 描绘了并发线程的离散的执行状态空间 execution state space

每个轴代表一个线程顺序执行指令
每个点关系到一个可能的执行状态
轨迹 trajectory 合法转移序列，其描述了一个并发线程可能的执行
L，U，S 形成了对变量 cnt 的临界段 critical section
临界段中的指令不能交错，这种交错出现的状态集合形成了不安全区域 unsafe regions

所以当且仅当一个没有进入任何不安全区域时，这个轨迹是安全的

过程图

为了确保安全的轨迹，必须同步 synchronize 线程的执行，即保证对临界段的互斥访问 mutually exclusive access

信号量 Semaphore：由 P 和 V 操作控制的非负全局整数同步变量

P(s)：

如果 s 非 0，则 s - 1 并立即返回
如果 s 为 0，则暂停直到 s 变成 0 且该线程由 V 操作重启
在重启后，P 操作减小 s 并返回控制权给 callee

V(s)：

s + 1
如果有线程被等待 s 变成非 0 的 P 操作阻塞了，则重启其中一个线程

这两个操作共同形成了不变量：s >= 0

Pthreads 提供的函数：

#include <semaphore.h>
int sem_init(sem_t *s, 0, unsigned int val); /* s = val */
int sem_wait(sem_t *s); /* P(s) */
int sem_post(sem_t *s); /* V(s) */

使用信号量的互斥：

基本思想：

将一个初始为 1 的唯一信号量 mutex 与每个共享的变量关联
在临界段周围加上 P(mutex) 和 V(mutex) 操作

术语：

二进制信号量 Binary semaphore：值总是 0 或 1 的信号量
Mutex：用于互斥的二进制信号量
- P 操作：锁上 locking mutex
- V 操作：解锁 unlocking 或释放 releasing mutex
- 保持 holding mutex：锁上但没有解锁
计数信号量 counting semaphore：用于可获得的资源的集合的计数器