深入理解计算机系统：CSAPP

一. 信息的表示和处理

1. 存储单位

1. 位(bit)：计算机的最小数据单位，每一位的值只可能是0或1.
2. 字节(byte)：由8个位构成，是大多数计算机最小的可寻址的内存单位。
3. 字(word)：由若干字节组成，字的位数也叫字长。比如IA-32下，一个字表示4字节即32位；在x86-64下，一个字表示8字节即64位。
4. 关系运算：，，，

2. 二进制与十六进制表示法

2.1：十进制、二进制与十六进制之间的关系

2.2：进制转换

2.2.1：二进制转为十进制

_2%20%3D%201%5Ctimes2%5E3%2B0%5Ctimes2%5E2%2B1%5Ctimes2%5E1%2B1%5Ctimes2%5E0%3D11#card=math&code=%281011%29_2%20%3D%201%5Ctimes2%5E3%2B0%5Ctimes2%5E2%2B1%5Ctimes2%5E1%2B1%5Ctimes2%5E0%3D11&id=l2puu)，二进制的每一位都有一个权重，从右往左编号，则每一位的权重为.

2.2.2：二进制转十六进制

，从右往左，每四位一分，最后一次分若不足4位用0补足得：0010 0100 1010 1111，然后把每个部分的十进制算出来对应到十六进制即可：2 4 A F

2.2.3：十六进制转二进制

，把十六进制的每一位对应拆分成二进制即可：1111 1000 1011 0110

2.2.4：十进制转二进制

1. 整数部分用短除法，每次除以2得到商和余数，把商作为被除数继续除以2得到商和余数，循环直至商为0，把余数倒着写即为结果，如下展示：%7B10%7D%3D(11010)_2#card=math&code=%2826%29%7B10%7D%3D%2811010%29_2&id=n8Pzl) | 过程 | 商 | 余数 | | —- | —- | —- | | 26 = 2 13 + 0 | 13 | 0 | | 13 = 2 6 + 1 | 6 | 1 | | 6 = 2 3 + 0 | 3 | 0 | | 3 = 2 1 + 1 | 1 | 1 | | 1 = 2 0 + 1（*商为0结束） | 0 | 1 |

也可以采用以下方法：牢记的值，快速解决

由可见，这个数的二进制有5位，计算过程中出现的位为1，否则为0，则结果为1 1 0 1 0

1. 小数部分采用乘法去整法：把这个小数乘以2得到一个结果，若这个结果大于1则减去1，把剩下小数部分继续做乘以2的操作，循环执行，直至乘法的结果等于1或者出现循环节或者无限不循环，然后把每次的结果的整数部分顺着写就是二进制。如0.35的转换过程如下：%7B10%7D%3D(01011001…)_2#card=math&code=%280.35%29%7B10%7D%3D%2801011001…%292&id=x6sAB) | 过程 | 整数部分 | | —- | —- | | 0.35 2 = 0.7 | 0 | | 0.7 2 = 1.4（超过1，下次使用减去1） | 1 | | 0.4 2 = 0.8 | 0 | | *0.8 2 = 1.6（超过1，下次使用减去1） | 1 | | 0.6 2 = 1.2（超过1，下次使用减去1） | 1 | | 0.2 2 = 0.4 | 0 | | 0.4 2 = 0.8 | 0 | | *0.8 2 = 1.6_（出现循环） | 1 |

这说明，二进制不能精确表示0.35这个数.

2.2.5：十进制转16进制

先把十进制转为二进制，再把二进制转为十六进制。

3：信息存储

3.1：最小的可寻址的内存单位

大多数计算机将8位视为一个块或者说字节并把它当做最小的可寻址的内存单位，然后每一个块用一个地址编码。

3.2：虚拟地址空间大小

计算机的字长限定了虚拟地址空间的大小：如IA-32架构的计算机的字长为32位，那么32位二进制数可以有种编码。因为每一位可以是0或1两种可能，那么32位可以表示个不同的数。

按照上面说的，1个地址对应一个块，而一个块的大小为1字节，所以共能编码个块，总大小为byte = 4GB

4：大小端模式

3.1：小端模式

数据的高字节保存在内存的高地址，低字节保存在内存的低地址。（高对高，低对低）

3.2：大端模式

数据的高字节保存在内存的低地址，低字节保存在内存的高地址。（高对低，低对高）

如数据0x12345678分别采用两种方式的存储结果如下：

5：布尔代数运算

5.1：布尔运算种类

5.2：布尔运算规则

举例说明：

5.3：C语言中的位级运算与逻辑运算

位级运算：即上述的4种布尔运算。

逻辑运算：

1. 非常容易与位级运算混淆。
2. 所谓逻辑运算就是真与假之间的运算，C语言中，用0表示假，1表示真；对于所有数字，C语言认为只有0为假其他都为真。 | 名称 | 与 | 或 | 非 | | —- | —- | —- | —- | | 符号 | && | || | ！ | | 运算规则简记 | 都为真才为真 | 只要有一个真就为真 | 真假相反 |

举例说明：

5.4：C语言中的移位运算

所谓移位运算，就是就数据的二进制数左移或者右移后加上特殊处理。

名称	算术左移	逻辑左移	算术右移	逻辑右移
符号
汇编符号	sal	shl	sar	shr
运算规则简记	低位补0	低位补0	高位补符号位	高位补0

Arithmetic：算术的

Logical：逻辑的

算术左移：Shift Arithmetic Left

逻辑左移：Shift Logical Left

算术右移：Shift Arithmetic Right

逻辑右移：Shift Logical Right

事实上：左移的两种方式结果一样，只有右移有区分。

举例说明：

对于二进制数：x = 1001 0011，最高位表示符号位为1。

x << 4：0011 0000；x >>(Loigical) 4：0000 1001；x >>(Arithmetic) 4：1111 1001（黑体表示补的位）

6：字符串的表示方法

采用ASCII编码和Unicode编码对每个字符编码。

7：整数的表示方法

7.1：原码、反码与补码

把一个十进制数转为二进制数就得到原码，对这个二进制数按位取反就得到反码，对反码加1就得到补码。

示例：如用8位二进制表示7，则原码为0000 0111，反码为1111 1000，补码为1111 1001

7.2：无符号整数

按照十进制转为二进制的规则即可。

7.3：无符号数的补码

按位取反加1即可。

示例：无符号数24的二进制为11000，对应的补码为 01000

7.4：有符号整数

最高位作为符号位，0表示正数，1表示负数。其余位按照十进制转为二进制的规则即可。

7.5：有符号数的补码

正数的补码就是原码；

负数的补码：符号位不变，剩余位按位取反加1.

示例：有符号数19的二进制为：0 10011，对应的补码为： 0 10011

        有符号数-21的二进制为：1  10101，对应的补码为：1 01011

7.6：C语言中整数的表示

数据类型	占字节数	范围
char	1
unsigned char	1
short	2
unsigned short	2
int	4
unsigned int	4
long	4
unsigned long	4
long long	8
unsigned long long	8

以int和unsigned int演示如何计算范围：

int占4字节即32位，第1位用作符号位，那么能表示的最大正数为：0 11…11(31个1)即231-1，能表示的最小负数为1 00…00即231，为什么负数比正数多1个(如char的范围是)，因为00…00(全零)被用来表示0这个整数剥夺了一个正数位置，而1 00…00却用来表示了最小负数(补码的缘故)，把0也算作正数就平衡了。

unsigned int占4占4字节即32位，由于无符号只表示非负数，那么能那么能表示的最大正数为：111…11(32个1)即232-1.

7.7：自动类型转换

当一个表达式同时包含无符号数和有符号数时，自动全部转化为无符号数再计算，这会产生意向不到的结果。

比如说计算：int(-1) < unsigned int(0)的结果，表明上是-1 < 0，结果为1。但实际上-1的机器表示为1 11…11(32个1)，自动转换为无符号数后表示232-1，比0大了不知道多少！因此计算结果反而为0.

7.8：扩展与截断

7.8.1：扩展

当小数据类型转换为大数据类型时，就会出现符号位扩展，如short转为int.

如果short转化为unsigned int呢？规则，先改变大小，再扩展符号位

short s = -1;
unsigned int ui = s;
printf("%x",ui);    // 以十六进制打印
// 输出：ffffffff
// 先改变大小，unsigned int足够表示-1
// 扩展符号位1，因此全为f

7.8.2：截断

大数据类型转换为小数据类型，规则：把二进制串从低位照搬填满小数据类型。变化会很大！

int x = 53191;
short sx = x;
printf("%d",sx);
// 输出-12345
// x的二进制串为0000 0000 0000 0000 1100 1111 1100 0111
// 而short只有16位，照搬低16位得：1100 1111 1100 0111
// 这个数变成了有符号数短整型，按照补码规则，这是个负数

7.9：C语言整数运算

7.9.1：无符号数加法

直接相加，若最高位有进位，丢弃即可。

7.9.2：补码加法（有符号数加法）

有符号数的加法采用补码运算，公式：%7B%E8%A1%A5%E7%A0%81%7D#card=math&code=A%7B%E8%A1%A5%E7%A0%81%7D%2B%20B%7B%E8%A1%A5%E7%A0%81%7D%20%3D%20%28A%2BB%29%7B%E8%A1%A5%E7%A0%81%7D&id=Em3gj)，如果最高位出现进位，丢弃即可，答案也正确！

7.9.3：无符号数和有符号数的乘法

先相乘得到二进制串然后直接截断，如w位乘w位可能得到2*w位的结果，那么照搬结果的低w位，其他高位丢弃，所以乘法溢出时会出错，得到错误结果！

7.9.4：左移操作替代乘法

原理：等价于：x乘2的k次幂等价于x左移k位。

无符号数和有符号数通用。

C语言中，由于移位操作比乘法快很多，所以乘一个常数时，C语言会自动优化为移位和加法，如下

7.9.5：右移操作替代除法

向下舍入：舍入到最近的比结果小的整数，比如6.5舍入为6，-6.5舍入为-7（为什么不是-6？根据定义应舍入到最近的比-6.5小的整数）

向上舍入：舍入到最近的比结果大的整数，比如6.5舍入为7，-6.5舍入为-6.

无符号数除法：原理：等价于，向下舍入的意思。

注意：采用的是逻辑右移，高位补0.

有符号数除法：原理：等价于，向下舍入的意思。

注意：采用的是算术右移，高位补符号位。

重点：对于向下舍入，如果是同号数（同正或同负）之间的除法问题不大，比如按照以上方法26 / 4 = 6.5经过向下舍入为6.

但是如果两数异号，比如-26 / 4 = - 6.5，按照向下舍入得到-7，而-6更加符合我们的期盼，此时就应该采用向上舍入，但是C语言默认采用向下舍入，怎么办？偏置技术！

偏置技术可以实现除法向上舍入：对于整数和#card=math&code=y%28y%20%3E%200%29&id=HXBjn)，原理是：%2Fy%20%5Crfloor#card=math&code=%5Clceil%20x%2Fy%20%5Crceil%20%3D%20%5Clfloor%20%28x%2By-1%29%2Fy%20%5Crfloor&id=TTRQH)，所以如果我们想要实现向上舍入，只需要给加上偏置值然后正常计算让计算机向下取整即可。

7.9.6：总结

不要轻易使用无符号数，否则会出现意想不到的错误！

但是并不是说不要用，无符号数还是用很多有用的地方滴，自己查有哪些。

7.10：整数补码运算规则

编码：

二进制数的补码从左向右依次编号：

公式：

%E8%A1%A5#card=math&code=A%E8%A1%A5%20%2B%20B%E8%A1%A5%20%3D%28A%20%2B%20B%29%E8%A1%A5&id=can3c)

%E8%A1%A5%20%3D%20(A%20-%20B)%E8%A1%A5#card=math&code=A%E8%A1%A5%20-%20B%E8%A1%A5%20%3D%20A%E8%A1%A5%20%2B%20%28-B%29%E8%A1%A5%20%3D%20%28A%20-%20B%29_%E8%A1%A5&id=OUh0m)

溢出：运算结果的位数超过了计算机设定的位数。同号相加可能产生溢出，结果出错！

溢出判断：设表示第位的进位。若则说明结果溢出，否则没有溢出。即若最高位和次高位同时产生进位或同时不产生进位不会溢出，异或结果为0；若其中只有一位产生进位就溢出了，异或结果为1.

注意：补码的运算结果仍然是补码，要知道是十进制的值请先把补码转换为原码！！！

当最高位产生进位时，直接丢弃进位作为结果。如果没有产生溢出，这个结果就是对的！！！

举例说明：

假设某计算机用5位表示整数。分别计算9+3，-9-3，9+12，-9-12

8：浮点数

如2.2.4所示，二进制表示小数有限制，只能精确表示的小数，其他的不能精确表示，而且单纯用二进制表示小数要用的位数太多。

其实对于二进制0.111111111…1，小数点后每一位的值分别是，极限收敛于1。

IEEE标准浮点数表示法：支持所有主流CPU；支持舍入和溢出等操作；简单优雅。

8.1：数学形式

%5Es#card=math&code=%28-1%29%5Es&id=A3h5A)
符号位，表示浮点数正负，0特殊处理	二进制尾数，一般在#card=math&code=%5B1%2C2%29&id=dEkyL)之间	阶码，表示2的幂

8.2：C语言中浮点数的类型

C语言中，小数能用float和double表示，各部分分配的位数如下：

float占4字节即32位，double占8字节即64位

8.3：规格化值、非规格化值与特殊值（由exp区分）

8.3.1：规格化值

1. 条件：exp≠00…00且exp≠11…11
2. 阶码E = exp - bias
3. 其中，为阶码exp的位数，则float的bias=127，double的bias=1023
4. 尾数M：1.xxxxxx（默认有1开头），则frac就是小数点后的xxxxxx，最大为全1，最小为全1

把小数转换为IEEE标准浮点数的例子：

%7B10%7D%3D(1110%201101%201011%2001.11)_2%3D1.110%201101%201011%2001%2011%20%5Ctimes%202%5E%7B13%7D#card=math&code=%2815213.75%29%7B10%7D%3D%281110%201101%201011%2001.11%29_2%3D1.110%201101%201011%2001%2011%20%5Ctimes%202%5E%7B13%7D&id=N44mj)，手动转换；
由此可知；
若用表示，则，因此_2#card=math&code=exp%20%3D%20E%20%2B%20bias%20%3D%20140%20%3D%20%281000%201100%29_2&id=F0Lpy)，既不是全0也不是全1，所以是规格化值；
则

因此这个10进制数在计算机中的表示为：

如果是逆向过程：给出IEEE表示的浮点数，要计算它的十进制。首先根据exp判断类型，再根据s确定正负，然后根据bias和exp计算阶码E，然后补足M即可得到二进制串，再转为十进制即可。

8.3.2：非规格化值

1. 条件：exp=00…00，即exp全0，但是0既不是规格化值也不是非规格化值。
2. 阶码：E = -bias + 1（bias的计算是一致的）
3. 尾数：M = 0.xxxxxxxxx2（默认0开头）
4. 例子：
   • exp = 00…00且frac = 00..00表示0（+0与-0有区别）；
   • exp = 00…00且frac ≠ 00..00；
   • 非常接近0.0的数字

8.3.3：规格化值与非规格化值的区别

1. 阶码计算方式不同
2. 尾数整数部分默认不同。

8.3.4：特殊值:

1. 条件：exp=11…11，即exp全1
2. 例子：
   • exp=11…11且frac = 00…00表示无穷。s=1表示负无穷，s=0表示正无穷；
   • 因此可以表示溢出结果，用+表示正溢出，用-表示负溢出；
   • exp=11…11且frac ≠ 00…00表示NaN，意为不是一个数(Not a Number)，如负数开平方，无穷加减，无穷与0运算

8.3.5：IEEE标准浮点表示法的范围

由图可以看出，非规格化都是一些非常小的值，这么做是为了更精确表示一些不能精确表示的数。

以float为例，exp = E + bias = E + 127，若exp < 0即E + 127 < 0即E < -127，就说明这些数都是小于1的，exp就没必要表示负那么多次方，直接靠尾数表示即可，因为上面说过，对于二进制0.111111111…1，小数点后每一位的值分别是，极限收敛于1。

以下图说明IEEE标准的简单优雅

图中只给出了正数部分，负数部分只要把s改为1

（0既不是规格化值也不是非规格化值）

1. 非规格化的最大与最小

• 最小的非规格化数：s = 1,exp=00…00,frac = 11…111（负的）
• 最小的正非规格化数：s = 0,exp=00…00,frac = 00.001
• 最大的非规格化数：s = 0,exp=00…00,frac = 11…111（正的）
• 最大的负非规格化数：s = 1,exp=00…00,frac = 00…001

1. 规格化的最大与最小

• 最小的规格化数：s = 1,exp=11…110,frac = 11…111（负的）
• 最小的正规格化数：s = 0,exp=00…01,frac = 00.000
• 最大的规格化数：s = 0,exp=11…110,frac = 11…111（正的）
• 最大的负规格化数：s = 1,exp=00…001,frac = 00…000

8.4：浮点数舍入问题

8.4.1：十进制舍入方式

向0舍入：往靠近0的方向舍入到整数

向下舍入：舍入到最小的不大于本身的整数

向上舍入：舍入到最大的不小于本身的整数

最近舍入：舍入到距离最近的整数

8.4.2：二进制舍入方式

二进制四舍五入：大于或等于中间值则入，小于则舍，中间值的形式为

如中的中间值为

举例说明：舍入到1/4，即小数点后的第二位

8.5：浮点数乘法

原则：先计算精确结果，再考虑舍入和溢出问题。

数1	数2
%5E%7Bs1%7D%20%5Cspace%20M1%20%5Cspace%202%5E%7BE1%7D#card=math&code=%28-1%29%5E%7Bs1%7D%20%5Cspace%20M1%20%5Cspace%202%5E%7BE1%7D&id=w10IG)	%5E%7Bs2%7D%20%5Cspace%20M2%20%5Cspace%202%5E%7BE2%7D#card=math&code=%28-1%29%5E%7Bs2%7D%20%5Cspace%20M2%20%5Cspace%202%5E%7BE2%7D&id=p5Gj4)

1. 计算精确结果：%5E%7Bs%7D%20%5Cspace%20M%20%5Cspace%202%5E%7BE%7D#card=math&code=%28-1%29%5E%7Bs%7D%20%5Cspace%20M%20%5Cspace%202%5E%7BE%7D&id=MfHdp)
   • s = s1 ^ s2
   • 
   • 
2. 调整
   • 若，则右移一位，.
   • 若此时超出表示范围，溢出
   • 将舍入到的位数范围

8.6：浮点数加法（使用补码运算）

1. 对阶：小阶向大阶对齐。将小阶的数的阶码加上阶差，并把尾数右移阶差位。（右移丢失的位至关重要，保留着！！！）
2. 尾数求和：带上数符一同求和。
3. 尾数求和结果规格化：
   • 左规：当尾数求和的结果中，数符和尾数的最高位值相同时，形式上为00 0.xxx或11 1.xxx，需要左规，方法：尾数左移1位，阶码+1.
   • 右规：当尾数求和的结果中，数符的两位不相等时，形式上为 01 x.xxx或10 x.xxx，需要右规，方法：尾数右移1位，阶码-1.
4. 舍入处理：0舍1入法；截断法；恒1法；
5. 判断溢出：根据最终阶符判断，阶符两位异或为1说明溢出。若溢出，进行一次右规，判断是否上溢出。下溢置0，上溢置溢出标志。

举例说明：

它们的浮点表示为：

阶码和尾数都用补码表示！！！（重点）

	阶符	阶码E	数符	尾数M
	00	010	00	1101 1011
	00	100	11	0101 0100

1. 对阶：求阶差：=00 010 - 00 100 = 00 010 + 11 100 = 11 110（补码运算结果） = -2
   说明x的阶码小，将x的尾数右移2位，阶码加2得x的浮点表示为 | | 阶符 | 阶码E | 数符 | 尾数M | | —- | —- | —- | —- | —- | | | 00 | 100 | 00 | 0011 0110 (11这两位在左规、右规和舍入中还有用！！！) |

2. 尾数求和：00 00110110 + 11 01010100 = 11 10001010

3. 规格化处理：结果的符号位1与最高数值位1相同，对11 1000 1010 11进行左规（补上了上面两个1，用处在这呢）得11 0001 0101 1，阶码变为00 011. 已经不满足左规和右规条件，规格化完毕。
4. 舍入处理：采用0舍1入法，尾数最后多出了一个1，应该入。11 0001 0101 + 1 = 11 0001 0110
5. 溢出判断：阶符为00，异或结果为0，没有溢出。
6. 结果：现在尾数是补码表示，先转成原码1110 1010，结果

8.7：C语言浮点运算特性

8.7.1：浮点加法特性

• 具有简单交换性：仅限于两个浮点数
• 不具有结合性：#card=math&code=x%2By%2Bz%20%5Cneq%20x%2B%28y%2Bz%29&id=wAD7c)，原因：溢出，0，NaN
• 不具有单调性：$a \ge b a + c \geq b + c\infty,NaN$

8.7.2：浮点乘法特性

具有简单交换性：仅限于两个浮点数

不具有结合性：#card=math&code=x%20%5Ctimes%20y%20%5Ctimes%20z%20%5Cneq%20x%20%5Ctimes%20%28y%20%5Ctimes%20z%29&id=Y4IRC)，原因：溢出，0，NaN

不具有单调性：$a \ge b a \times c \geq b \times c\infty,NaN$

8.8：int, float与double之间的转换

8.8.1：int转float

不会溢出，但可能被舍入。

8.8.1：int转double

能够精确表示。

8.8.1：float/double转int

值向0舍入，对于无法表示或超出范围的值没有定义int如何表示它们。

二. 程序的机器级表示

1. 基本

1.1：机器语言、汇编与高级语言

机器语言很基础、底层的，机器执行起来很有效率。但是直接用机器语言写程序对程序员的要求很高也很不方便。说白了机器语言就是01两个数字按照一定规则组合而成的特定序列。

因为满屏都是01,看起来都要疯掉。所以为了改善可读性，用一些单词或词组来表示机器指令：MOV, ADD, SUB等等。即把具有某一功能的01序列封装起来用一个名字来代表它，比如把加法的01序列封装起来用ADD表示它。这些符号就是汇编符号。

由于汇编代码也起来也很不方便，对专业知识要求很高，对计算机也要有较深入的理解，普及不起来。因此出现了高级语言java, C, C++, python等，掌握基本语法后可以按照人类的逻辑写程序。

1.2：计算机系统组成

寄存器就在CPU内部，而主存离CPU有一定距离。因此，CPU从寄存器获得数据比从主存获得数据要快的多（很多很多很多那种）。但是寄存器数量有限，价格也昂贵。

1.3：寄存器

只介绍IA-32的寄存器

以%eax为例，32位大小部分命名为%eax，低16位命名为%ax，低16位中的高8位命名为%ah、低8位命名为%al

1.4：C语言源程序的编译过程

以hello.c为例

1. 预处理：把包含的头文件加入源程序。预处理器cpp根据字符#开头的命令，修改源程序，简单地把包含的内容插入源程序中。文件变化：hello.c —> hello.i
2. 编译：检查代码的规范性、是否具有语法错误。文件变化：hello.i —> hello.s，.s文件就是汇编语言文件，还是可读的。
3. 汇编：把汇编语言转成机器语言。文件变化：hello.s —> hello.o，.o已经是二进制文件，基本不可读的。
4. 链接：把所有需要的文件链接起来，比如你可能需要链接printf.o这个基本的输出文件。

1.5：mov数据传送指令

1.5.1：指令格式如下

mov 源操作数 目的操作数

如图的功能就是把十进制8传送到寄存器%eax中。

1.5.2：源操作数类型

1. 立即数：也就是常数。如movl $10 %eax，十进制就写$10，十六进制就写$0xa.
2. 寄存器：可以把一个寄存器中的内容传送到另一个寄存器。如movl %ebx %eax把%ebx中的内容传送到%eax中。
3. 内存引用：把内存中的内容传送到寄存器中。如movl 0x12345678 %eax，注意0x12345678前面没有$符号，因此它不是立即数而是一个内存地址！把内存地址0x12345678中的内容传送到%eax中。

1.5.3：目的操作数类型

1. 寄存器：用寄存器接收传送的内容。如movl %ebx %eax表示用%eax接收%eax的内容。
2. 内存引用：用内存空间接收传送的内容。如movl %eax 0x12345678表示用0x12345678指向的内存空间接收%eax的内容。

特别注意：源操作数和目的操作数不能同时为内存引用，如movl 0x100 0x101是不允许的，它必须分步进行。

1.5.4：指令类型

1.5.4.1：大小系列:

由于movq是64位机器独有的，IA-32没有，因此后续的系列不考虑它。

1.5.4.2：零扩展系列

记忆：出去mov，看剩下3个英文字母，第1个代表扩展类型，第2个代表源操作数的大小，第3个代表目的操作数大小。如movzbw指令，z代表zero做零扩展，b代表源操作数大小为一个字节即8位，w代码目的操作数大小为双字节即16位。

注意：目的操作数一定不能比源操作数小

1.5.4.3：符号拓展系列:

记忆：出去mov，看剩下3个英文字母，第1个代表扩展类型，第2个代表源操作数的大小，第3个代表目的操作数大小。如movsbw指令，s代表sign做符号扩展（扩展源操作数的符号！），b代表源操作数大小为一个字节即8位，w代码目的操作数大小为双字节即16位。

注意：目的操作数一定不能比源操作数小

1.5.5.4：寻址方式

M代表内存memory，R代表寄存器register，s是比例因子且只能为1,2,4或8

其实movl 0x8(%ecx, %ebx, s ) %eax是最齐全的了，遇到其他的，缺哪部分就把那部分当0即可。

其实像这样类型的作用大致如下：

• 计算一个值，
• 然后把这个值当做内存地址去访问内存对应地方的内容。
• 把访问到的内容送往目的操作数

1.6：lea指令

说明：Load Effective Address，加载有效地址。是mov的变种，比mov少一个步骤，即上面的第2个黑色小点。它算到一个值，并不根据这个值去访问内存，而是直接把这个值送往目的操作数。

规定：lea指令的目的操作数必须是寄存器。

示例：leal 0x8(%ecx, %ebx, 4) %eax 的效果为%eax = %ebx × 4 + %ecx + 0x8，根本没去访问内存。

1.7：add加法和sub减法指令等其他双操作数指令

比较简单，就是注意方向问题即可。

1.8：单操作数指令

2. 控制

到此，利用以上指令我们可以实现了直线代码行为，就是按照代码从上往下一行一行地执行。但还没有实现跳转，循环等需要条件才执行的结构。

2.1：条件码

2.2：cmp条件指令

注意计算方向即可。
![](https://gitee.com/zwjason/pictureBed/raw/master/image-20200814165129047.png#height=372&id=WoFYg&originHeight=496&originWidth=891&originalType=binary&ratio=1&status=done&style=none&width=668)

2.3：test条件指令

注意是位级的与运算！

2.4：条件码设置

除去set看字母代表的意思，g代表greater than，e代表equal，a代表above用于无符号数，b代表below用于无符号数。

举例说明：

2.5：跳转指令

除去j看字母代表的意思，g代表greater than，e代表equal，l代表用于less than，a代表above，b代表below.

2.6：跳转指令的编码（重点）

跳转指令的编码方式有多种。常用的有PC相对编码和PC绝对编码。

PC相对编码规则：跳转指令编码 目标指令的编码 紧跟跳转指令的后一条指令的地址。

看到如下关系：

汇编版本中：跳转指令编码0x3 目标指令的编码0x8 紧跟跳转指令的后一条指令的地址0x5

反汇编中：

看几道题练习一下：

可以看到，跳转指令的下一条指令的地址是4005ed

跳转指令编码是73 ff ff ff，按小端法存储得正确顺序是ff ff ff 73，对应二进制为1 0111 0011，但这只是补码，原码为1 1000 1101，即 -8d

则跳转目标的编码xxx = 4005ed + (-8d) = 400560

2.7：条件跳转到条件传送

条件跳转版本：符合条件跳转到相应地方才计算，计算后传送

分支跳转版本：

典型语句return x > y ? x - y : y - x;

条件传送版本：先全部计算，符合条件才传送

优点：

• 避免跳转。CPU无需做分支预测，避免预测错误代价，流水线效率更高。

缺点：

1. 额外的计算代价：要计算两种情况的结果，如果有一种不太可能会用到而且又复杂的，计算了反而影响效率。
2. 导致非法操作：如语句p ? p : 0; 当p为0时仍然会计算p

2.8：循环

分do-while, while和for三种，麻烦得很，看得懂汇编代码和反汇编代码就可以了。如图

不满足跳出循环的条件就跳回去循环执行就可以了。

2.9 ：switch语句（重点）

当分支较多时，使用大量If, else if ……导致代码可读性和效率降低，此时如果能用switch替换就能提高可读性和效率。

优点：执行开关语句的时间与开关情况的数量无关。

跳转表：switch会有多种情况，编译器为每一种情况生成了相应的汇编代码块，跳转表就依次存储这些代码块的首地址。

注意：汇编代码可能会根据索引和情况种类对索引进行改动。比如说索引是整数x，情况有100,101,102,103,104,105,106，那么汇编可能会先对 x 减100，把范围变成0-6；再比如说有情况-1到7，那么汇编可能会先对 x 加1，把范围变成0-8. 这只是一些调整，知道就好，不必知道为何如此做！

举例说明跳转表的特征

1. 跳转表跳转指令有明显特征，地址运算前面加了符号 *
2. 跳转表从上到下按顺序依次对应每一个case
3. 对于缺省的情况，跳转表默认跳转得到default
4. 第5行比例因子为8是因为这是x86-64的教材，一个地址占8个字节。如果是IA-32，比例因子就会是4.

3. 过程

过程从高级语言层面来说就是函数调用。

为了方便起见，以函数P调用函数Q为例，则函数P被称为调用者，函数Q被称为被调用者。

3.1：过程一般包括以下3个动作

1. 传递控制。比如函数P调用函数Q，那么调用后控制权就要从函数P交到函数Q，即此时程序计数器被设置为函数Q的起始地址。当函数Q执行完之后，程序计数器又要被设置回函数P调用函数Q的后面那条指令的地址。（绕口、不理解不要紧）
2. 传递数据：函数P必须为函数Q传递参数，Q必须要给P返回一个值（其实void函数也有返回值）
3. 分配和释放内存：函数P调用函数Q时，内存要分出一段连续空间给函数Q，因为函数Q可能需要给一些局部变量分配空间。当函数Q执行完毕后，这些空间又必须释放回收。

3.2：过程的优点

1. 使程序简短清晰
2. 提高开发效率
3. 有利于程序维护
4. 提高代码复用性

3.3：栈帧

过程要离得开回得来！比如说函数P调用了函数Q，当函数Q执行完，要回得来继续执行函数P.

因此使用栈来实现

3.4：IA-32的特殊栈帧(stack frame)

说明：

1. 倒置的，栈底在上，栈顶在下。而且栈底的地址高，栈顶的地址低。
2. %ebp是当前函数或过程的栈底指针，%esp是当前函数或过程的栈顶指针。
3. 栈的增长方向是向下的，向地址0x0增长。因此%ebp的地址永远不会小于%esp的地址。
4. 栈帧是内存中的一段连续空间。
5. 被调用者的栈帧一定紧挨着调用者的栈帧。

举例函数调用的栈帧变化，太多了，详见pdf第10讲。

3.5：总结

1. 参数传递之前，一般先把参数放在离%esp较远的地方，然后再根据参数类型把参数的某属性移到%esp附近。比如说main函数要向sum函数传递两个整型参数3,4,，那么main函数会先把3,4放在离%esp较远的地方，然后再放到靠近%esp的地方。为什么？编译器的默认行为。如果传递的参数是3,4的地址呢？如果你先把整型3,4放在了靠近%esp的地方，那么就没地方放参数是3,4的地址了
2. 被调用者的栈帧一定紧挨着调用者的栈帧。因此返回地址和old ebp的相对位置是固定的，返回地址一定在old ebp的上面一个空间。

4. 数据

4.1：数组

4.1.1：一维数组

形式定义：Type array[length]

内存分配：一般会在内存里连续分配%20%5Ctimes%20length#card=math&code=sizeof%28type%29%20%5Ctimes%20length&id=mz4js)个字节。比如int nums[5]就会在内存分配%20%5Ctimes%20length%20%3D%204%20%5Ctimes%205%20%3D%2020#card=math&code=sizeof%28type%29%20%5Ctimes%20length%20%3D%204%20%5Ctimes%205%20%3D%2020&id=LixoT)个字节空间

元素访问：规定数组名是第一个元素在内存的首地址。以int nums[5] = {1,2,3,4,5}为例

访问类型：

其实nums + 1是指从nums开始往后一个元素，在这里int占4字节，所以是x + 4，如果是double类型，那就是x + 8，加多少是个这个类型占的字节数决定的。

内存访问形式：

假设寄存器%edx中存储了数组的其实地址，寄存器%eax中存储了数组元素下标，那么内存寻址方式为$ (%edx, %eax, 4) = 4 \times %eax + %edx$，得到这个元素的地址，那么只要 *address就可以访问元素的值了。

4.1.2：二维数组

形式定义：Type array[row] [column]，数据类型是Type，有row行column列

内存分配：一般会在内存里连续分配%20%5Ctimes%20row%20%5Ctimes%20column#card=math&code=sizeof%28type%29%20%5Ctimes%20row%20%5Ctimes%20column&id=YuZDT)个字节。比如int matrix[4] [5]就会在内存分配%20%5Ctimes%204%20%5Ctimes%205%20%3D%204%20%5Ctimes%204%20%5Ctimes%205%20%3D%2080#card=math&code=sizeof%28type%29%20%5Ctimes%204%20%5Ctimes%205%20%3D%204%20%5Ctimes%204%20%5Ctimes%205%20%3D%2080&id=oYDS8)个字节空间

在内存中的排列方式：以行为主序，一行一行地存在内存，形式大致如下

先存完第一行，再存第二行…….

元素访问：规定数组名是第一个元素在内存的首地址

先根据行位置 i 定位到行 A + i c k，然后套用一维数组的访问方式即可。

比如访问A[i] [j]的方式：定位行：A + i c k，再定位列，(A + i c k) + j * k

需要访问两次内存：

1. 第一次取得行的首地址
2. 第二次根据行的首地址访问这一行的某个元素

一般C语言定义定长数组比较好，因为定长数组的访问可以优化。

4.2：结构

结构即C语言中用关键字struct定义的一种数据类型。比如说：

struct people {
    String name = "";    // 姓名
    char 
    int year = 0;        // 年龄
    int id = 0;            // 身份证
};

形式定义：people person[length]

内存分配：连续的，但确定大小前先要先进行格式对齐，详见后文。

数据访问：规定结构名是首地址。在内存访问上表现为通过字节偏移量访问。

数据对齐：规定数据地址必须是K的整数倍（K一般为4或8）

个人猜测定下这个规定的原因是为了提高访问速度，因为比例因子只能是1,2,4,8.

由于这个规定，结构的占字节大小一般不是其中所有类型的字节总和，有多余的空白填充字节。比如说，

原本的结构大小为：1 + 4 * 2 + 8 = 17字节

填充空白字节后：17 + 3 + 4 = 24个字节

IA-32的对其规则

对齐方式

1. 结构内部，必须满足每一种数据类型的对齐方式
2. 整体上，首地址必须是K的整数倍，即上面图中的P是K的整数倍（这个是编译器解决的问题）
3. 不同计算机架构方式不同，对齐方式也不同，如

x86-64下，由于double类型，最高可出现向8的倍数对齐， K = 8

而IA-32下，把实际上占8字节的double当做4字节处理，没有填充，K = 4

因此，由于存在数据对齐规则，在定义结构体的时候，如果人为事先对各种数据类型的排列方式进行研究，寻找一种被填充空白字节最少的方案，可减少对内存的使用。

但是这样做有时候确实减少了内存使用，但又会使得逻辑不顺畅，比如定义一个people结构，出现“身高，体重，性别，姓名，身份证”这样的定义顺序，一般来说，我们都习惯姓名，身份证在前面。

也正是存在这样的对其规则，当内存访问结构中的某一个元素时，偏移量可能不是表面上算出来的那么简单。比如

表面上，访问到 j 的偏移量应该是 2 + 4 = 6，但由于填充，变成了8.

三. 程序性能优化

1. 编译器优化能力的缺陷

1.1：编译器优化的基本原则：确保正确性！因此编译器优化处理是保守的、悲观的、安全的。

1.2：存储器别名问题：对于以下函数

void twiddle1(int* xp, int* yp) 
{
    *xp += *yp;
    *xp += *yp;
}
void twiddle2(int* xp, int* yp) 
{
    *xp += 2 * (*yp);
}

这两个代码看起来功能是一样的，那么编译器是否会将twiddle1优化为twiddle2呢？不会！

twiddle1要求6次存储器引用。2次读xp，2次读yp，2次写*xp

twiddle2要求3次存储器引用。1次读yp，1次读xp，1次写*xp

twiddle2的效率明显高于twiddle1，编译器这都不优化吗？不！

因为编译器要考虑所有可能的情况！假设xp和yp指针相同即两者指向同一内存地址会发生什么？

那么执行twiddle1之后，xp扩大了4倍；而执行twiddle2之后，xp只扩大了3倍；出现不同结果！

由于编译器考虑所有情况时发现了这种情况，所以选择不把twiddle1优化为twiddle2.

1.3：涉及全局变量的函数调用

int f();
int func1()
{
    return f() + f() + f() + f();
}
int func2()
{
    return f() * 4;
}

如果你看到func1的写法是不是立刻想改成func2呢？我觉得是，因为我也想这么做！

看起来功能相同，func1调用了4次f，而func2只调用1次，明显func2的效率更高。

但是编译器会这么做吗？不会！

假如f函数如下实现呢？

int count = 0;    // 全局变量
int f()
{
    return ++count;
}

那么执行func1的结果就是1 + 2 + 3 + 4 = 10，而执行func2的结果是1 * 4 = 4

2. 从高级语言的角度优化

2.1：减少函数调用，消除循环的低效率

比如说，我们使用了 vector 容器存储数组元素，当我们需要访问数组元素时，可能会写出如下代码：

int main()
{
    vector<int> vec;
    vec.push_back(1);
    vec.push_back(2);
    vec.push_back(3);
    for (int i = 0; i < vec.size(); i++)
    {
        cout << vec[i] << endl;
    }
}

很显然，我们在for循环内部的输出操作不会影响vec的大小，但每次循环都要调用 vec.size() 来获得大小，当 vec 中元素很多的时候，这是比较低效率的操作。因为函数调用涉及状态保存，开辟栈帧，计算并返回结果，销毁栈帧等操作。

此时，如果我们能利用局部变量 size = vec.size()来保存 vec 的大小，就只需要调用一次函数。

int main()
{
    vector<int> vec;
    vec.push_back(1);
    vec.push_back(2);
    vec.push_back(3);
    int size = vec.size();
    for (int i = 0; i < size; i++)
    {
        cout << vec[i] << endl;
    }
}

总结：

循环中，如果循环内的操作与一些循环内的函数的调用结果互不影响，那么可以考虑把这些函数移到循环外面。

2.2：减少内存引用

假如需要把内存中的某个整数依次加上数组 nums = [1, 2, 3, 4]中的所有元素，可能会写出以下代码：

int addArray(int* dest, int nums[], int length) 
{
    for (int i = 0; i < length; i++)
    {
        // *dest += nums[i];
        *dest = *dest + nums[i];
    }
}

在这里，每加一个数，都涉及 1 次读内存和 1 次写内存，当数组元素很多的时候，需要花费大量时间从内存中读取数据，而读写内存的效率是很低的，远不如读寄存器来得快。

如果我们使用局部变量先保存数组求和结果，最后在加到结果上，就可以减少大量内存引用。

int addArray(int* dest, int nums[], int length) 
{
    int sum = 0;
    for (int i = 0; i < length; i++)
    {
        // sum += nums[i];
        sum = sum + nums[i];
    }
    // *dest += sum;
    *dest = *dest + sum;
}

这样局部变量 sum 就保存在离 CPU 很近的寄存器中，访问起来非常快！

同时利用局部变量，只需要两次内存引用！

2.3：条件跳转变为条件传送

如果我们需要计算两个整数 x, y 的绝对值差，可能会写出如下代码：

int twoIntAbs(int x, int y) 
{
    if (x >= y) {
        return x - y;
    } else {
        return y - x;
    }
}

但其实这个 else 是多余的，去掉它。

int twoIntAbs(int x, int y) 
{
    if (x >= y) {
        return x - y;
    } 
    return y - x;
}

版本 1 涉及条件跳转，可能会出现分支预测，而预测错误的代价较大；而版本 2 只是符合条件传送，没用分支预测失败的风险。

但是并不是说条件传送一定就比条件跳转好，具体详见 二.程序的机器级表示的2.7

3. 从机器级的角度优化

3.1：指令流水基础

取指令：根据程序计数器PC从存储器中取出指令；

指令译码：指令译码器根据指令产生执行所需的控制信号；

取操作数：CPU根据控制信号读取存储器或寄存器操作数；

执行指令：CPU对操作数完成指定操作；

返回结果：将操作结果写入存储器或寄存器。

3.2：并发与并行

并发指给每个任务分配执行时间（称为时间片），时间到了去执行另一个任务，由于时间片较短，造成宏观上任务是同时执行的错觉。

并行指同时执行几个任务。

区别：并发在微观上不同时宏观上同时，并行在微观上和宏观上都是同时的。

3.2：指令相关性

如果指令之间不存在相关性，那么它们在流水线中是可以并行执行的，这种重叠成为指令级并行。

3.2.1：结构相关性

不同指令同时争夺同一寄存器或存储器（资源冲突），但这些指令之间不存在数据流。

解决办法：前一个指令访存时，后一个指令暂停一个时钟周期再执行。

3.2.2：数据相关

后续的指令需要的操作数，要等到前面的指令执行完并保存了结果后才能获得。

• 写后读相关

A = B + C;
D = 3 * A;

在数据A上写后读。

• 读后写相关

A = B + C;
B = D * 2;

在数据B上读后写。

• 写后写相关

A = B + C;
A = D * 2;

在数据A上写后写。

• 冲突实例 | | 1 | 2 | 3 | 4 | 5 | | —- | —- | —- | —- | —- | —- | | 指令1 | 取指令 | 计算地址 | 取操作数 | 算存结果 | | | 指令2 | | 指令 | 计算地址 | 取操作数 | 算存结果 |

可以看到在第4个周期发生了冲突，前一条指令要写完，后一条指令才能取。

解决方法就是：指令2暂停几个周期等指令1存完再取操作数。

3.2.3：控制相关

3.4：寄存器分类

只读寄存器：只能从中读取数据的源寄存器；

只写寄存器：只能往其中写数据的目的寄存器；

局部寄存器：非源、非目的寄存器，仅用于临时辅助，例如保存cmp指令的值；

循环寄存器：既是源寄存器也是目的寄存器，在第n-1次循环往里面写数据充当目的寄存器，在第n次又从中读取数据充当源寄存器。

重点：因此，在分析循环效率时，循环寄存器就是数据相关链上的数据流，很有可能就是数据流的关键路径，改善关键路径可以达到改善程序效率的效果。

3.5：程序性能表示

度量标准CPE：每元素的周期数（Cycles Per Element, CPE）

公式：CPE = 运行时间 / 时钟周期（每一个元素完成的运行时间）、

时钟周期T：CPU完成一个基本动作的时间。

时钟周期长度公式：T = 1 / f，f是处理器的频率

一个标有“4GHz”的处理器，表示处理器每秒运行个时钟周期，那么时钟周期长度为它的倒数秒，即0.25纳秒。

3.6：功能单元的性能

延迟：表示完成运算所需时间的总时间。

发射时间：表示两个连续的同类型运算之间需要的最小时钟周期数。

容量：表示能够执行该运算的功能单元数量。

完全流水线化：发射时间为1个时钟周期的功能单元。

吞吐量：发射时间的倒数。对于一个容量为C，发射时间为I的操作来说，处理器可能获得的吞吐量为每时钟周期C / I个。

延迟界限：任何必须按照严格顺序完成合并运算的函数所需要的最小CPE值。

吞吐量界限：操作数 / 功能单元数量。可以给出CPE的最小界限。

3.7：数据流图

拿出书本的例子：

// 向量的抽象数据结构定义
typedef struct {
    long len;    
    data_t *data;    // data_t可以表示int,float,double等数据类型
} vec_rec, *vec_ptr;
// 定义常数
// 对所有向量的元素求和
#define IDENT 0
#define OP +
// // 对所有向量的元素求积
#define IDENT 1
#define OP *

从以下函数出发：

void combine4(vec_ptr v, data_t *dest)
{
    long int i;
    long int length = vec_length(v);    // 获取向量长度
    data_t *data = get_vec_start(v);    // 获取头指针
    data_t acc = INDENT;
    for (i = 0; i < length; i++) {
        acc = acc OP data[i];
    }
    *dest = acc;
}

从高级语言的角度，已经减少了函数调用，减少了内存引用，没有条件跳转，好像已经无法优化。但是实际上**for**循环每次都有条件跳转！

所以这段代码的效率瓶颈就在for循环部分，循环部分汇编代码如下

3.5.1：程序的数据流

定义：用图形化的方法，展现不同操作之间的数据相关是如何限制它们的执行顺序的。

这些限制形成了图中的关键路径，这是执行一组机器指令所需时钟周期数的一个下界。

如combine4的数据流图如下

在这里，%rax总是只读其中的length，属于只读寄存器；%rdx和%xmm0总是先读后写，属于循环寄存器。

图中错了，不是得到关键路径，是得到关键数据链。

本题的假设中，data_t是double类型，OP是乘法*（见汇编代码注释）。那么如果假设浮点乘法的延迟为5个周期，而整数加法的延迟为1个周期，那么关键路径就会是下图左边的乘法路径。

因此，我们可以得到CPE的下界为5.

而如果执行的是int的加法，两条链的延迟周期都是1，那么CPE的下界应该是1，而实际测量值可能会比1大，比如1.27，这说明关键路径只能给出CPE的下界，而不是准确值。

可能还有其他因素制约性能，比如可能的功能单元数量等。

3.8：循环展开（无法突破延迟界限）

定义：通过增加每次迭代计算的元素的数量，减少循环的迭代次数。

循环展开：一次循环计算k个元素。

对combine4进行循环展开，即每次循环计算2个元素。

void combine5(vec_ptr v, data_t *dest)
{
    long int i;
    long int length = vec_length(v);    // 获取向量长度
    long limit = length - 1;
    data_t *data = get_vec_start(v);    // 获取头指针
    data_t acc = INDENT;
    // 一次算两个元素
    for (i = 0; i < limit; i += 2) {
        acc = (acc OP data[i]) OP data[i + 1];
    }
    // 当元素个数为奇数时，还剩 1 个没有计算在内
    for (; i < length; i++) {
        acc = acc OP data[i];
    }
    *dest = acc;
}

变化1：for循环一次处理2个元素，因此定义limit = length - 1避免越界。

变化2：额外假如一个for循环处理剩下的元素。假如元素个数为n，采用循环展开，那么剩下n % k个元素需要处理。

性能变化：

可以看到，对于整数加法的CPE有所改进，但对整数乘法和浮点数加法与乘法都没有改进。

原因：

GCC对整数加法有特殊优化；

整数乘法、浮点数的加法和乘法无法优化，必须从到到尾按顺序执行。以浮点乘法为例，对于长度为n的向量，没有循环展开，1次循环算1个元素则有一个mul操作，则共有n个mul操作；你采用循环展开，1次循环算2个则有2个mul操作，总共还是n个mul操作。总而言之，就是关键路径没变！

第二个mul要等第一个mul执行完才能执行！正是由于这种延迟界限的存在（后一个操作要等前一个操作完成），所以无论你循环展开多少次，都无法打破延迟界限！

3.9：循环展开 + K路并行（可突破延迟界限）

前提：有些运算具有可结合和可交换的性质，在不考虑溢出，无穷和NaN的情况下，如整数加法和乘法。

展开，一次计算k个元素，并进行k路并行。

既然 1 个局部变量连乘要按顺序执行，后面的操作要等前面的操作，那么我们就试着多用一个局部变量分开乘。

以下是采用2路并行的代码：

void combine6(vec_ptr v, data_t *dest)
{
    long int i;
    long int length = vec_length(v);    // 获取向量长度
    long limit = length - 1;
    data_t *data = get_vec_start(v);    // 获取头指针
    data_t acc0 = INDENT;
    data_t acc1 = INDENT;
    // 一次算两个元素
    for (i = 0; i < limit; i += 2) {
        acc0 = acc0 OP data[i]
        acc1 = acc1 OP data[i + 1];
    }
    // 当元素个数为奇数时，还剩 1 个没有计算在内
    for (; i < length; i++) {
        acc0 = acc0 OP data[i];
    }
    *dest = (acc0 OP acc1);
}

性能：

可以看到2路并行把整数乘，浮点加和浮点乘的CPE改进了约2倍，并且打破了延迟界限的制约！处理器不再需要延迟一个加法或乘法操作来等待前一个操作完成。

简化后的抽象数据流图：

虽然浮点加法和乘法由于涉及舍入问题，不具有可交换和可结合的性质，但这里仍然强行这样做了，为什么？谁能说 按顺序加或乘 就一定会比 分开加或乘最后结合 的结果更准确呢？具体问题具体分析！

3.10：重新结合变换（可突破延迟界限）

改变计算的结合顺序

void combine7(vec_ptr v, data_t *dest)
{
    long int i;
    long int length = vec_length(v);    // 获取向量长度
    long limit = length - 1;
    data_t *data = get_vec_start(v);    // 获取头指针
    data_t acc = INDENT;
    // 一次算两个元素
    for (i = 0; i < limit; i += 2) {
        acc = acc OP (data[i] OP data[i + 1]);
    }
    // 当元素个数为奇数时，还剩 1 个没有计算在内
    for (; i < length; i++) {
        acc = acc OP data[i];
    }
    *dest = acc;
}

和combine5相比，只是第11行

从

 acc = (acc OP data[i]) OP data[i + 1]);

变成了

acc = acc OP (data[i] OP data[i + 1]);

这种变换称为循环展开2次，1路并行，重新结合

但是性能：

整数加法和combine5一样，但是整数乘、浮点加、浮点乘和combine6一样！

重新结合变换也突破了延迟界限！

总结：

• 通过重新结合变换，有时候可以减少关键路径上的操作数量，但并不是总有效！
• 循环展开和多路并行才是更可靠的方法！

3.11：其他制约程序性能的因素

3.11.1：寄存器溢出

当并行度超过了寄存器数量，编译器会把某些临时值存放在内存（通常是在运行栈），届时CPU将要从内存中读取数据，性能反而更低！

20路并行的CPE反而比10路的低！

3.11.2：分支预测和预测错误处罚

原则：不过分关心可预测的分支；条件跳转变为条件传送

3.11.3：加载的性能

加载的意思是从内存中获取数据。

依赖于流水线的能力和加载单元的延迟。

看代码：

它的汇编代码如下：

3.11.4：存储的性能

存储的意思是往内存中写数据。

一般来说“读写不相关”的性能比“读写相关”的性能好！

原因：理解加载单元与存储单元的关系

注意到存储单元里有一个“存储缓冲区”，它的作用是存放加载单元已经发射到存储单元但是却没有完成存储操作的的数据和地址（也就是加载单元已经写完了要存起来，但是先放在了这，没有放到存储单元和更新高速缓存）。

当有加载操作时，先检查“存储缓冲区”有无需要的数据（地址匹配说明有，否则无），若有直接作为加载结果；若无则去存储单元找。

观察汇编代码：

数据流图：

(1)表示，要往dst地址里写val，要先等我计算出存储地址，才能根据地址存val.

(2)表示，你下面又要加载一次src，我要先看看“存储缓冲区”有没有（读写相关就有，不相关就没有）

(3)表示，如果读写相关，这个数据直接可以作为加载结果。

展示“读写不相关”和“读写相关”的关键路径

读写不相关时，关键路径只是sub操作即cnt--，CPE为减法操作的延迟1；读写相关时，关键路径不是sub操作了，而是加载和存储操作，下一次迭代加载前必须等上一次迭代存储完毕！

3.12：程序性能优化总结

3.12.1：高级语言角度

• 选择合适的数据结构和算法；
• 消除连续的函数调用；
• 消除不必要的内存引用；
• 选择好条件跳转和条件传送

3.12.2：从机器角度

• 适当地循环展开 + 多路并行；
• 慎重使用重新结合变换！

3.13：Amadahl定律与

主要描述的是，对占整个系统耗时比例为的某部分进行k倍加速后，即使的比例已经相当高了，而整体的性能提升S却比k小得多。

比如上述红框所述。

当k趋向于无穷时，

也就是说我们人类尽最大努力提升了某部分的速度，k趋向于无穷，即执行这部分需要的时间几乎为0.

当时，S = 5，也就是说，即使你把80%的系统能够加速到不花时间的程度，整体的性能也只有原先的5倍。

四. 存储的层次结构

现代计算机的储存都是分层次的，原因是省钱和局部性。如何省钱？什么是局部性？慢慢来看！

1. 随机访问存储器

随机访问存储器RAM(Random Acess Memory)分为两类：静态的SRAM和动态的DRAM.

SRAM和DRAM把每一位存储在一个双稳态的存储单元里，存储单元由晶体管电路构成，那么谁用的晶体管多，技术复杂，谁就贵咯！

从图中可以看到，明显SRAM更贵，因此应用在比较小的高速缓存中。而较便宜的DRAM就应用在比较大的主存中。

2. 传统的DRAM访问

访问顺序：行优先，先行后列。

以图中访问超单元(2,1)为例，过程如下

3. 易失性存储器和非易失性存储器

3.1：易失性存储器

定义：断电后，保存的信息立即消失的存储器。

实例：上面所说的SRAM和DRAM都是易失性存储器。

3.2：非易失性存储器

定义：断电后，保存的信息能够保留下来存储器。

实例：只读存储器ROM(Read Only Memory)，根据它可以重新被写的次数分类

举个例子：关电脑，保存在高速缓存和内存上的数据都立刻消失；而磁盘上的不会消失，你今晚关机前下完的片儿，明天开机不会不见了吧？这说明，高速缓存和内存都是易失性存储器而磁盘是非易失性的。

4. 磁盘

磁盘由盘片组成；盘片上分同心圆磁道；每一圈磁道又分扇区。

多盘片的同一磁道构成柱面。

容量：由记录密度，磁道密度和面密度决定。

寻道（访问数据）：先找磁道，再找扇区。

5. 内存访问

CPU与内存的连接：CPU和内存通过共享的总线相连接，数据就在总线中流动。为了准确访问，总线是一组并行的导线，能携带地址，数据和控制信号。

5.1：总线事务

完成CPU与内存之间的数据传输的一系列操作。

5.2：读事物

CPU从内存中读取数据。

5.3：写事物

CPU写数据到内存。步骤：CPU将地址放在总线；内存接收地址做好存储准备；CPU把数据放在总线上；内存读取数据存起来。

6. 局部性

6.1：局部性原理

一个编写良好的计算机程序，倾向于引用最近已经引用过的数据项或者其附近的数据项。

6.2：时间局部性

一个具有良好时间局部性的计算机程序，被引用过的一次内存位置在不久的将来很可能再次被引用。

6.3：空间局部性

一个具有良好空间局部性的计算机程序，如果一个内存位置被引用过，那么在不久的将来很可能引用它附近的内存位置。

6.4：示例

示例1：向量求和

int sumVector(int vec[n]) 
{
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += vec[i];
    }
    return sum;
}

在这个向量求和的函数中，

sum每次迭代都被重复引用，具有良好的时间局部性；

引用过vec[0]，下一次就引用vec[1]，步长为1，对vec向量的引用，每次都是引用已经引用过的数据项的邻近数据项，具有良好的空间局部性；

综上所述，sumVector函数有良好的局部性。

顺序引用模式：函数对向量的引用采取步长为1的引用方式。

步长为k的引用模式：函数对向量的引用采取步长为k的引用方式。

示例2：二维矩阵求和

int sumMatrix(int a[m][n]) 
{
    int sum = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0 ; j < n; j++) {
            sum += a[i][j];
        }
    }
    return sum;
}

分析：可以看到sum每次迭代都被重复引用，具有良好的时间局部性；

而这个双重for循环的访问顺序正好契合了二维数组的行优先储存模式，具有良好的空间局部性；

因此，这个函数具有良好的局部性。

假设：按列优先访问二维数组元素

int sumMatrix(int a[m][n]) 
{
    int sum = 0;
    for (int j = 0; j < n; j++) {
        for (int i = 0 ; i < m; i++) {
            sum += a[i][j];
        }
    }
    return sum;
}

分析：可以看到sum每次迭代都被重复引用，具有良好的时间局部性；

而这个双重for循环的访问顺序是列优先的，先加一列再加一列，这与二维数组的行优先储存模式不相容，导致出现步长为n的饮用模式，不具有良好的空间局部性；

因此，这个函数的局部性较差。

现在回过头来看存储的层次结构

首先明确一点：寄存器组是最小的高速缓存，CPU从寄存器中取数据最快，从L1中取次之，依此类推。

为什么要在寄存器和主存中加入3个高速缓存呢？

1. 为了速度：根据局部性原理，把经常被使用的数据放在高速缓存，而CPU从高速缓存中取数据的速度远比从主存中取来得快。
2. 为了省钱：那为什么不直接把主存放得离CPU近一点以提高速度呢？那么大，放不下；即使放得下，造价昂贵。

使用这种层次结构，找到速度、容量和价钱的平衡点：用较少的钱，获得较大的存储容量和较快的访存速度。常用的不会很多，放在容量小的高速缓存；不常用的很多，放在容量大的磁盘。

7. 高速缓存介绍

7.1：高速缓存

Cache，小而快速的存储设备，作为大而慢的存储设备的高速缓冲。

7.2：存储层次的中心思想

假设按照上图的编号方式，最高级缓存为L0，最低为Ln。那么把第k层的存储设备作为第k+1层的高速缓存。从第k层存储设备获取数据的速度比从第k+1层快！

7.3：传输单位

块。大小不定。

要点：

• 由于第k层较小，那么任何时候它都只能包含第k+1层所有块的一个子集。
• 相邻两层之间的块大小一般是相同的。但是，书中有一段神奇的说法

这说的不详细，产生矛盾。

前提：相邻层的块大小一样；相邻层总是以块大小传输。

结论：所有层的块大小都是一样的！

证明：根据“相邻层的块大小一样”，假设L0和L1使用的块大小为B字节；那么由于L1的块大小为B字节，则L2的块大小也为B字节！依次类推所有层次的块大小是一样的，和书中描述不符合！

因此我认为块有传输块和存储块之分。

7.4：缓存命中与缓存不命中

需要内存中的块B，会先查找内存的高速缓存Cache中是否有块B。

若有则直接从取走，称为缓存命中！

若没有，则称为缓存不命中！

这时就要去内存中找块B，找到之后要更新到Cache。

如果此时Cache有空位，则直接放到空位上；

若没有空位，就要采取替换策略，替换掉某个块。

7.5：放置策略和替换策略

放置策略：没有介绍。

牺牲块：被替换策略选中替换掉的块。

7.6：缓存不命中分类

8. 高速缓存—通用结构

早期计算机存储层次结构只有3层：CPU寄存器组，DRAM主存和磁盘。

随着发展，为了速度，在CPU寄存器组和DRAM主存中插入了一个SRAM高速缓存存储设备L1， 后来又多插入了L2和L3。CPU从中取数据大概分别需要4,10,50个周期。

8.1：大前提

现在假设寄存器组和主存中只有一个高速缓存设备Cache！下图是典型的高速缓存存储器的总线结构。

8.2：通用的高速缓存存储器的组织结构

假设某个计算机系统，它的每个存储器有m位地址，则能形成个地址。

这样的计算机，它的高速缓存被组织如下：

8.2.1：组织结构

1. 特点：

高速缓存被分为个组；

每组中有行；

每行由1个有效位，t个标记位，大小为字节的数据块组成。

1. 有效位：指明当前行的信息是否有意义。
2. 标记位：当前块的内存地址的子集。
3. 高速缓存结构的表示：(S, E, B, m)

8.3：高速缓存的大小

不包含有效位和标记位。大小.

8.4：高速缓存如何工作（重点）

m位的地址被参数S和B划分成三部分。

计算顺序：

一般先计算出和，然后.#card=math&code=t%20%3D%20m%20-%20%28s%20%2B%20b%29.&id=EyFFL)

8.5：高速缓存—映射规则（重点）

8.5.1：映射规则分类原则

根据高速缓存组中的行数分类。

8.5.2：直接映射（每组一行）

响应请求：给出一个m位的地址，向高速缓存请求字的过程分三步：组选择，行匹配，字抽取。

1. 组选择：从m位地址中抽取出s位的组索引，解释为无符号数。下图中

1. 行匹配：在定位了组号的前提下，由于直接映射只有每组只有一行，先检查有效位（一般1有效0无效）。

若无效，说明数据块里没有需要的信息，发生缓存不命中；

若有效，再检查t位行标记是否匹配，若不匹配，发生缓存不命中。

若匹配，说明说明数据块有信息的副本（原本在内存中），则进行下一步字选择。

1. 字选择：定位了组和行，接下来只需要根据b位块偏移定位块的起始位置即可。

1. 不命中的替换策略

从下一层存储结构中取出被请求的块。由于直接映射每组只有一行，根据组号替换掉那一行即可。

如果一组有多行，还需要新的策略决定替换掉哪一行。

1. 示例：第三版p429-432（比较重要）

展示了直接映射的高速缓存如何工作，介绍了抖动，阐述了为什么用地址的中间位做组索引而不用高位。

抖动：高速缓存反复地驱逐和加载相同的高速缓存块的组。

8.5.3：组相联映射（每组多行）

E路组相联高速缓存：一组中有#card=math&code=E%281%20%5Cle%20E%20%5Cle%20C%2FB%29&id=O2G1R)行。

放置策略和替换策略的选择：由于一组有多行，任何映射到这一组的行都可以放在这一组中的任意行，那么应该放在哪一行呢？当发生缓存不命中时，如果这组有空行直接放置即可，如果没有空位，要替换哪一行呢？如何制定放置策略和替换策略使得后续访问发生不命中的概率尽可能低呢？

响应请求：给出一个m位的地址，向高速缓存请求字的过程分三步：组选择，行匹配，字抽取。

1. 组选择：和直接映射一样，把s位的组索引解释为无符号整数得到组号即可。
2. 行匹配与字抽取：由于一组有多行，因此根据t位行标记检测每一行，如果全都不匹配，发生缓存不命中。如果匹配，检查有效位，如果无效，发生缓存不命中；如果有效。根据b位块偏移定位起始块的位置。

8.5.4：全相联映射（只有一组）

全相联高速缓存：只有一组，这一组包含了所有行。

响应请求：给出一个m位的地址，向高速缓存请求字的过程分三步：组选择，行匹配，字抽取。

1. 组选择：只有一组，默认组索引为0，所以m位地址中没有组索引位！

1. 行匹配与字抽取：与组相联相同。区别是规模不同罢了。

应用：由于每次都要花费大量时间匹配所有行，而且构建起来花费昂贵，所以全相联高速缓存只适合做小的高速缓存，如：虚拟内存系统中的翻译备用缓冲器TLB.

8.5.5：为什么用地址的中间位做组索引而不用高位

这是一个高速缓存利用率的问题！为什么？请看下文，

图中左侧是一个4位地址的、有4个组的高速缓存。右侧表示一个简化内存，地址用4位表示，所以有16个块。假设每一个块存储一个数组元素（元素下标刚好和地址的十进制对应起来，第0个元素在地址0000的块中），然后一个程序为了得到良好的局部性，采取顺序访问数组元素的方式。

• 如果用高位作为组索引：
  访问第0个元素时，发生冷不命中，连同第1,2,3个元素都被放到了第0组中，后续引用1,2,3命中。
  访问第4个元素时，发生冷不命中，连同第5,6,7个元素都被放到了第1组中，后续引用5,6,7命中。
  访问第8个元素时，发生冷不命中，连同第9,10,11个元素都被放到了第2组中，后续引用9,10,11命中。
  访问第12个元素时，发生冷不命中，连同第13,14,15个元素都被放到了第3组中，后续引用13,14,15命中。
  可以注意到，当访问第x组高速缓存时，就一直再访问这一组，其他组都没有利用，这使得高速缓存的空间利用率很低！
• 如果用中间位最为组索引
  访问第0个元素时，发生冷不命中，连同第4,8,12个元素都被放到了第0组中，(为什么是这几个在同一组？你看他们组号相同啊！)
  访问第1个元素时，发生冷不命中，连同第5,9,13个元素都被放到了第1组中，
  访问第2个元素时，发生冷不命中，连同第6,10,14个元素都被放到了第2组中，
  访问第3个元素时，发生冷不命中，连同第7,11,15个元素都被放到了第3组中。
  可以注意到，当顺序引用4个元素后，高速缓存被充满了，之后顺序引用数组元素时，总在不同组中引用。这就是所谓的缓存预热！

8.6：高速缓存—写入

CPU发出写事物，想要往内存写入字w，那么先写到高速缓存中！

8.6.1：写命中

定义：要写入内存的字w已经存在高速缓存中，根据何时更新紧挨着的低一层存储结构（这里是Cache和内存）分为直写和写回。

8.6.2：写不命中

定义：要写入的字w不在高速缓存中，根据写入的地方不同分为写分配和非写分配。

8.6.3：搭配方式

直写+非写分配，写回+写分配。

直写+写分配更能保持Cache和内存的数据一致性！

9. 高速缓存性能指标

9.1：命中率和不命中率

不命中率：内存引用的不命中比率，公式：不命中数量 / 引用数量

命中率：1 - 不命中率

9.2：命中时间

命中后，从高速缓存传送一个字到CPU所需的时间，包括组选择，行匹配和字抽取的时间。

9.3：不命中处罚

由于不命中所需要的额外时间。L1不命中需要从L2得到服务，10个周期；从L3得到服务，50个周期；从主存得到服务50-100个周期。

其他因素还有：高速缓存大小，块大小，相联度，写策略。

10. 编写高速缓存友好的代码

追求目标：使程序有良好的的局部性，尽量提高程序内的所有循环缓存命中率！

以下示例，均假设高速缓存块为4个字，一个字4字节，那么一个块就16字节，能放4个int型数，且初始高速缓存为空。

示例1：

int sumVector(int vec[n]) 
{
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += vec[i];
    }
    return sum;
}

1. 分析局部性
   sum每次迭代都被重复引用，具有良好的时间局部性；
   引用过vec[0]，下一次就引用vec[1]，步长为1，对vec向量的引用，每次都是引用已经引用过的数据项的邻近数据项，具有良好的空间局部性；
   综上所述，sumVector函数有良好的局部性。
2. 分析缓存命中率
   根据以上对高速缓存的假设，无论它是什么结构；
   无论数组比高速缓存大还是比高速缓存小；
   对v的引用都会得到下面的命中和不命中模式
   
   这里的1[m]，2[h]前面的数字并不是代表第几个元素，而是代表引用的次序，1[m]表示第一次引用不命中。
   对v[0]的引用不命中，然后包含v[0]~v[3]的块会被传送到高速缓存中，然后对v[1]~v[3]的引用都命中。
   因此我们可以看到，每引用4个元素都会在首次产生1次冷不命中，命中率为，这已经是所能得到的最好情况了。

以上示例说明：

那么我们之前说的循环展开和多路并行，随着展开的幅度增加，步长也会增加，和这里步长为1的引用模式冲突吗？

示例2：

int sumMatrix(int a[m][n]) 
{
    int sum = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0 ; j < n; j++) {
            sum += a[i][j];
        }
    }
    return sum;
}

1. 分析局部性
   可以看到sum每次迭代都被重复引用，具有良好的时间局部性；
   而这个双重for循环的访问顺序正好契合了二维数组的行优先储存模式，具有良好的空间局部性；
   因此，这个函数具有良好的局部性。
   假设：按列优先访问二维数组元素
2. 分析缓存命中率
   因为C语言的二维数组是以行优先存储的，而双重for循环也是一行一行地引用，因此，内层for循环具有和示例1一样的命中率。
   对a[i][j]引用会得到下面的命中和不命中模式
   
   因此命中率还是
   1. 如果我们按列访问，会发生什么？

      int sumMatrix(int a[m][n]) 
      {
      int sum = 0;
      for (int j = 0; j < n; j++) {
        for (int i = 0 ; i < m; i++) {
            sum += a[i][j];
        }
      }
      return sum;
      }

      
      

11. 存储器山

首先明确一个概念，

读吞吐量（也称为读带宽）：一个程序冲存储系统中读数据的速率，一般单位是Mb / s. 如果一个程序m秒内读了n个字节，那么读吞吐量为，转换一下单位即可。

我们以读带宽表示一个计算机的存储系统的性能！

那么存储器山是个什么玩意儿呢？它是一个二元函数的图像！

函数的自变量是：时间局部性和空间局部性；

函数的因变量是：读带宽；

即：读带宽 = (时间局部性，空间局部性)

我们直接看Intel Core i7系统的存储器山。

z轴是读带宽的变化，x轴是时间局部性的变化，y轴是空间局部性的变化。

控制变量法观察时间局部性和空间局部性对读带宽的影响！

1. 固定时间局部性，当空间局部性变差（即步长增加）时，读带宽变小。
2. 固定空间局部性，当时间局部性变差（局部变量太多了，沿x轴正方向增加）时，读带宽也变小。

此外，我们可以看到，主存山脊的最高点比它的最低点高8倍，即当时间局部性很差时，空间局部性仍能补救性能，这很重要！

五. 链接

5.1：写在前面

链接是什么？还记得C语言源文件要经过哪些步骤才能执行吗？它们分别是：预处理，编译，汇编和链接！

链接要做的事情是什么？简单一句话：把多份可重定位目标文件拼凑起来成为一份可执行文件。

这么做的意义是什么？先学完才能说清楚！

链接分类：静态链接和动态链接。

接下来的内容都基于这样的环境：Linux的x86-64系统和ELF目标文件格式！

5.2：从源文件到可执行文件的过程

接下来都以这两份代码（main.c和sum.c）作为示例说明一些概念。

// 文件名：main.c
int sum(int* a, int n);        // 函数声明
int array[2] = {1, 2};
int main()
{    
    int value = sum(array, 2);
    return value;
}

// 文件名：main.c
int sum(int* a, int n) 
{
    int s = 0;
    for (int i = 0; i < n; i++) {
        s += a[i];
    }
    return s;
}

有人问：为什么这么短的代码要分开写成两份.c源文件，写在一起不好吗？

答：这里只是为了说明链接的工作原理的举的简单例子，如果有多人协作，出现几十份.c源文件都不奇怪！

这里不讲如何在Linux的x86-64系统用什么命令完成编译到运行，有需要再举例。

只关注实现的过程

看图，一份.c文件产生一份.o文件，静态链接就是把这些.o文件“整合”起来称成为一份可执行文件prog.

具体如何“整合”，首先要明白一些概念。

5.3：目标文件

目标文件分3类

目标文件的3种格式

虽然操作系统很多，采用的格式也不同，但链接的概念基本都是相同的，只是有些细节不同。

这里采用ELF的目标文件格式！

5.4：静态链接

Linux的静态链接器：以一组可重定位目标文件和命令行参数作为输入，输出一个完全链接的、可以加载和运行的可执行目标文件。

链接的两大主要任务：符号解析和重定位

符号解析：

解析在目标文件中定义和引用的符号。符号类型：函数名，全局变量和静态变量。（具体见符号和符号表介绍）

符号解析的目的就是把每一个符号引用和一个符号定义关联起来。（比如main.c中引用的sum，而sum却在sum.c里面定义的，解析main.c中的sum符号时需要sum.c文件）

重定位：回想编译过程，生成的.o文件的地址都是从0开始的，这样是不能直接加载到内存运行的。

因此链接器把每个符号都关联一个内存地址，那么访问这些地址的内容就能实现访问符号。

符号的地址变了，符号引用也要跟着变啊！修改符号引用使它们指向正确的内存地址。

（比如原本sum符号的地址为0，现在符号sum的关联到了内存地址0x12345678，那么sum的符号引用也要跟着变成0x1234578）

5.5：可重定位目标文件

结构：

注意：局部变量不在.data、.bss和COMMON中，它们在运行时被保存在栈中！

5.5：符号和符号表

每一个可重定位模块m都有一个符号表（如main.c和sum.c各自拥有一个符号表），它包含了定义和引用的符号的信息。在链接器的上下文中，有3种符号类型：

再次强调：局部符号不是局部变量，链接器不关心局部变量，因为它们只能被定义它们的模块引用，运行时保存在栈中即可。

符号表结构：

举例子说明

看两份.c文件，

针对swap.o模块，填写以下表格！

buf是在m.o中定义的，没有static修饰，因此是外部符号，已经被初始化，所以在.data节中；

bufp0是在swap.o中定义的，没有static修饰，因此是全局符号，已经被初始化，所以在.data节中；

bufp1是在swap.o中定义的，没有static修饰，因此是全局符号，未被初始化，所以在COMMON节中；

swap是在swap.o中定义的，没有static修饰，因此是全局符号，属于程序代码，所以在.text节中；

temp属于swap.c的局部变量，不在符号表中。如果static int* bufp1，那么bufp1就是局部符号！

5.6：符号解析

众所周知，同一份.c文件，一种符号只能有一个定义，没有异议吧？同名函数？编译器根据参数不同修改成了不同的名字！

目的：为每个符号引用找到它的定义。所有可重定位目标文件基本上都包含了符号的定义。因此找定义的时候就有区别。

假设某个模块m引用了符号s

• 若这个符号恰好就在模块m中定义的，那么链接器对这个引用的解析就非常简单。（局部符号和部分全局符号非常好解析）
• 若这个符号不是在模块m中定义的，链接器就假设它是在其他模块定义的，生成一个链接器符号表条目，让链接器去找。如果在任何模块都不能找到定义，就会输出一条非常难读懂的错误信息。（部分全局符号不好解析）
  比如说，尝试编译和链接以下源文件，链接器找遍了所有模块都找不到func的定义，无法完成对func的解析！

// 文件：test.c
void func(void);    // 函数声明
int main()
{
    func();
    return 0;
}

再者，不同模块可以定义相同的符号，比如main.c定义了int x，而sum.c也定义了int x，那么链接器如何解析多重定义的全局符号呢？

5.6.1：链接器解析多重定义的全局符号

Linux系统采用以下规则：以强弱区别同名符号。已初始化的全局变量是强符号，未初始化的全局变量是弱符号。

从规则2和3可以看出，如果一个程序的所有模块中，存在多重定义的全局符号，可能会潜藏着危险！

举例子说明：

5.7：与静态库链接

5.7.1：什么是静态库

静态库：把所有目标模块打包成为一个单独文件，称为静态库。

作用：可以用作链接器的输入，当链接器构造一个输出的可执行文件时，它只复制静态库里被应用程序引用的目标模块！

为什么要用静态库？如果不用静态库会出现什么不好情况呢？

1. 编译器要认出开发人员对标准函数的调用，从来直接生成代码。但是C语言有大量的标准函数，采用这种方法，链接器的负担很重！
2. 把所有标准C函数都放在一个可重定位目标文件中，比如放在libc.o中。开发人员要引用其中的模块时，需要在命令行中加入这个文件：gcc main.c /usr/lib/libc.o。优点是开发人员负担轻，缺点是一旦要修改其中任何一个模块，修改后要重新编译整个源文件，由于很庞大，所以很耗时。另外一个缺点是系统中每个可执行文件都包含着这一份标准函数的副本，对磁盘空间浪费很大。此外，当可执行文件加载到内存运行时，这个副本跟着放在内存，对内存浪费也很大！（libc.a大约5MB，libm.a大约2MB）

而使用静态库呢，每个可执行文件都只需要从静态库复制引用到的模块，没有引用的模块不复制！

5.7.2：构建静态库

5.8：链接器解析静态库引用

1. 符号解析阶段：按照命令行从左到右的顺序扫描可重定位文件和存档文件。
2. 维护3个结集合：
   • 可重定位目标文件的集合E（这些文件会被合并成为可执行文件）
   • 未解析的符号集合U（引用了尚未找到定义的符号）
   • 已经定义的符号集合D
3. 按从左到右的顺序扫描命令行中的文件，根据文件类型，修改以上3个集合
   • 若文件f是目标文件，那么链接器把f添加到E，修改U和D反映f中的符号定义和引用。
   • 若文件f是存档文件，那么链接器就尝试匹配U中未解析的符号。若存档文件的某个模块m定义了U中未解析的符号，那么这个模块就被加到E中，并且修改U和D来反映m中的符号定义和引用。
   • 重复以上两个步骤，直至所有文件都扫描完毕。若此时U是非空的，说明还有符号未解析，链接器输出错误信息。否则合并和重定位E中的目标文件构成可执行文件。
4. 注意命令行上的库和目标文件的顺序
   • 假设某个库定义了某个符号s，而某个目标文件引用了s。在命令行中，若把库文件放在了目标文件的前面，那么根据上面的步骤，符号s将不会被解析！
5. 关于库文件的一般准则是放在命令行末尾
   1. 若各个库成员是相互独立的，顺序任意
   2. 若不是独立的，必须要对库文件排序，被引用的在前，定义的在后。

5.9：重定位

5.9.1：写在前面

当完成了符号解析，我们已经为每个符号引用正好关联一个符号定义，链接器知道了这个符号所在的模块（称为输入目标模块）的数据节和代码节的确切大小，那么如果将所有输入目标模块合并起来，并给每个符号分配运行时内存地址，就可以得到可执行目标文件了。

“将所有输入目标模块合并起来，并给每个符号分配运行时内存地址”这一步就称为重定位。

重定位分两个步骤：重定位节和符号定义、重定位节中的符号引用

5.9.2：重定位节和符号定义

• 链接器合并所有相同类型的节称为聚合节，并赋予这些聚合节运行时内存地址（之所以这么说，是因为它是虚拟地址，不是物理地址），包括给其中的每个符号赋予运行时内存地址。
• 比如合并所有输入模块中的.data节成为新的聚合节作为可执行文件的,data节；合并所有输入模块中的.text节成为新的聚合节作为可执行文件的,text节；
• 完成这一步，程序中的每条指令和全局变量都有唯一的运行时内存地址了。

5.9.3：重定位节中的符号引用

• 链接器修改代码节（.text节）和数据节（.data节）中对每个符号的引用，使它们指向正确的运行时内存地址。
• 这是由于汇编器生成目标模块（即.o文件）时，不知道这个模块引用的外部符号和具体位置，因此生成一个重定位条目，告诉链接器应该在合并成可执行文件时，应该怎么修改这些引用。
• 因此我们首先要了解重定位条目！

5.9.4：重定位条目

写在前面：

CSAPP黑皮书第三版采用的环境是Linux下x86-64系统，而考试用的是IA-32系统，功利心一下，这里只写IA-32的，如果想知道x86-64的，请看P479-482.

重定位条目的位置：

代码的重定位条目在.rel.text节中，已初始化数据的重定位条目在.rel.data中。

IA-32的ELF格式的重定位条目格式：

typedef struct {
    int offset;        // 需要重定位的引用的节偏移
    int symbol:24,    // 需要重定位的引用指向的符号
        type:8;        // 重定位类型
}Elf32_Rel;

重定位类型:

IA-32系统有11种重定位类型，我们只需要了解最基本的两种。

这两种重定位类型支持IA-32小型代码模型（可执行目标文件中的代码和数据的总体大小不超过2GB）// revise

5.9.5：重定位相对引用

重定位算法伪代码：

for each section s {    // 对每一个节s
    for each relocation entry r {    // 对节s中的重定位条目r
        refptr = s + r.offset;        //  需要被重定位的4字节引用在数组s中的地址
        // relocate a pc-relative reference        // 重定位一个32位PC相对地址引用
        if (r.type == R_386_PC32) {
            refaddr = ADDR(s) + r.offset;        // 引用的运行时地址
            *refptr = (unsigned)(ADDR(r.symbol) + *refptr - refaddr);    // 
        }
        // relocate an absolute reference
        if (r.type == R_386_32) {
            *refptr = (unsigned)(ADDR(r.symbol) + *refptr);
        }
    }
}

假设每个节s是一个字节数组；

refptr = s + r.offset;表示计算 需要被重定位的4字节引用 在数组s中的地址。

假设当算法运行时，链接器已经赋予了每个节和每个符号运行时内存地址；

ADDR(s)表示节s的运行时内存地址；

ADDR(r.symbol)表示引用的符号的运行时内存地址。

我们以下面两个程序说明这个算法的计算过程

根据反汇编代码行，这里是.o文件的的反汇编

可以看到call指令开始于节偏移0x6处，由一个字节的操作码0xe8和随后的32位引用0xfffffffc（十进制-4）组成。

同时我们还可以看到这个引用的重定位条目

这3个字段告诉我们链接器修改开始于偏移量0x7（0x6 + 0x1，有一个操作码在引用前面）处的32位PC相对引用，使得在运行时这个引用指向swap程序。

假设链接器已经确定：

ADDR(s) = ADDR(.text) = 0x80483b4（因为符号swap在.text节中）
ADDR(r.symbol) = ADDR(swap) = 0x80483c8（swap的运行时地址，链接器分配的）

根据算法，链接器先计算引用的运行时地址

refaddr = ADDR(s) + r.offset
        = 0x90483b4 + 0x7
        = 0x80483bb

然后，再将引用从当前的-4修改为0x9，使得它在运行时指向swap程序

*refptr = (unsigned)(ADDR(r.symbol) + *refptr - refaddr)
        = (unsigned)(0x80483c8 + (-4) - 0x80483bb)
        = (unsigned)0x9

在得到可执行目标文件中，call指令有如下的重定位形式

在运行时，我们可以看到call指令的地址为0x80483ba，之前讲过遇到call指令说明要调用函数，要给这个函数开辟栈帧，执行完这个函数再回过头来执行当前程序，所以我们必须把call指令的下一条指令的地址-0x80483bf（为什么是这个，你自己数嘛，call指令的地址为0x80483ba，有5个字节码e8 09 00 00 00，那0x80483ba + 0x5 = 0x80483bf）压栈。

而我们又说过，一般情况下程序计数器(PC,Program Counter)一般保存着下一条要执行的指令的地址，所以当程序运行到call指令时，PC保存的地址是0x80483bf！

那突然遇到一个call，要跳转执行swap了，PC中的值必须发生改变，考虑到又要借助这个地址回来，所以先把这个地址压栈，然后再作改变！

因此，PC按顺序执行以下两个操作：

而0x80483c8正好是swap函数的起始地址！

你可能回想，链接器为什么要在.o文件中设置这个引用的初始值为ff ff ff fc即-4

我看不懂，自己看吧，这个-4应该是算法伪代码第3行计算的结果？

我觉得吧，如果你还记得之前讲跳转指令jmp的跳转地址如何计算的话，那么这个就比较容易理解。

跳转地址就是swap符号的地址0x80483c8，而要计算出这个引用的4位字节码，我们还要知道call指令的下一条指令的地址。

而链接器只知道引用的运行时地址0x80483bb，

而由于引用占4个字节，所以call指令的下一条指令的地址与引用的运行地址刚好差4个字节。

链接器只知道引用的运行时地址，所以设置初始偏移值为-4来达到目的。

5.9.6：重定位绝对引用

5.10：可执行目标文件

5.10.1：写在前面

让我们回到大环境采用x86-64架构的Linux系统

5.10.2：格式

我们可以看到多了一个.init节和一个段头表，而少了所有的.rel节（因为不需要重定位了）

ELF头中的一个字段e_entry给出了执行程序时第一条指令的地址，而在可重定位文件中，该字段为0.

.init节是用于定义init函数的，该函数用于进行可执行文件开始执行时的初始化工作。

段头表是一个结构数组，包含页大小，虚拟地址内存段，段大小。描述了将连续的文件节映射到运行时的存储器段的映射关系。

5.10.3：映射关系

知道两个粉红框的映射关系即可。

5.11：现代动态链接共享库

5.11.:1：为什么需要共享库

这个问题我会，我挑一下静态库的毛病，如果我共享库能纠正这么毛病，那这就是我动态库的优势和存在的意义！

5.11.2：静态库的缺陷

采用静态库进行链接得到的可执行目标文件加载到内存运行时成为程序。

• 由于C语言标准函数库巨大，程序可能存在把某些公共代码复制了多份！比如scanf和printf。这很浪费内存空间。
• 对标准库的一点点小修改如BUG修复，都将需要把所有用到这个库的应用程序进行重新连接。
• 多个进程的虚拟存储空间可能有同一段代码的多个副本！

5.12：链接的意义

终于到了这一步！但是我决定贴图，哈哈。

六.异常控制流

6.1：控制流

众所周知，程序要执行的下一条指令的地址在程序计数器PC中。处理器上电，假设程序计数器有以下地址序列

每次从到的过渡称为控制转移。

像这样的控制转移序列叫做处理器的控制流。

6.2：改变控制流

1. 程序状态方面有两种方法，称为平滑流突变
   分支和跳转，jump and branches
   调用和返回，call and return
2. 系统状态变化不能由程序捕获。如硬件定时产生的信号、来自硬盘或网络的数据已经到达、试图除以零的指令等。
   系统通过使控制流发生突变来应对这些情况。我们把这样的突变称为异常控制流！

6.3：异常控制流 (Exceptional Control Flow, ECF)

6.3.1：ECF可以发生在系统的各个层面

在硬件层，响应系统事件而导致控制流变化；

在操作系统层，内核通过上下文切换将控制从一个用户进程转移到另一个用户进程；

在应用层，进程发送信号和进程接收信号。

6.4：异常

6.4.1：异常定义

异常指的是控制流中发生的突变。

如下图，程序执行到指令时，控制突然转移到异常处理程序而不是下条指令.

触发异常的可能情况：除以零，计算溢出，缺页，Ctrl+C组合键

在处理器中，状态被编码为不同的位和信号。

事件：状态变化称为事件。

中断程序：发生异常的程序。

6.4.2：异常表

1. 每一种类型的事件都对应一个独一无二的异常号k，异常号为非负整数；
2. 条目k包含异常k的处理程序的地址。
3. 异常表由这些异常号组成。
4. 异常表的起始地址在异常表基址寄存器中，通过异常号可以计算出相应的处理程序地址。
5. 系统启动时，操作系统就分配和初始化了一张异常表。

出现异常说明处理器的状态发生变化，此时处理器会通过异常表跳转到异常处理程序。

异常处理程序完成后，根据引起异常的事件类型，会发生以下3种情况之一

• 异常处理程序把控制返回给当前指令；
• 异常处理程序把控制返回给下一条指令；
• 异常处理程序终止被中断的程序。

6.4：异常的四种类型

后面3个同步的指令统称故障指令。

同步：异常是执行当前指令造成的。

异步：异常不是执行当前指令造成的。

6.4.1：中断

来自来自 I/O 设备的信号，不是指令造成的，因此它是异步的！

硬件中断的处理程序称为中断处理程序。

因为中断处理程序总是把控制返回给下一条指令，所以看起来应用程序似乎并没有中断过。

6.4.2：陷阱和系统调用

陷阱是人为有意使它产生的异常。

最重要的用途：在用户程序和内核之间提供一个像过程一样的接口，称为系统调用。

如：读文件，创建进程，加载进程，终止进程

人们有意在程序中执行系统调用，就是一个陷阱。

6.4.3：故障

故障处理过程

引起故障的情况：缺页异常等

6.4.4：终止

致命错误，不可恢复，直接调用abort程序终止。

触发情况：通常是硬件错误，比如DRAM或者SRAM位被损坏时发生的奇偶错误。

6.5：进程（习题过多自己看书上练习题）

6.5.1：经典定义

一个执行中程序的实例。

• 计算机科学最深刻、最成功的概念之一！
• 和程序是不同概念！

6.5.2：进程为程序提供的两个抽象

• 逻辑控制流 (Logical Control Flow)：使得看起来每个程序独占处理器！
• 私有地址空间 (Private Virtual Address Space)：使得看起来每个程序独占主存！

计算机如何给人早成这样的错觉？（详见下一大节，虚拟内存）

6.5.3：逻辑控制流

我认为的定义：单步执行程序时，程序计数器PC保存的一系列值。

当多个程序在运行时，为了看起来像多个程序同时在运行，系统设置了一个时间片。程序获得处理器控制后运行一个时间片，处理器控制就交给了另一个程序，由于时间片较短，使得在宏观上看起来所有程序都是同时运行的。

计数器PC中保存了这几个程序的要执行的指令序列，这个序列就是逻辑控制流！

并发流：逻辑流在执行时间上重叠。如多个程序同时执行，那么他们的逻辑流就会发生重叠。

并发：多个逻辑流并发地执行的现象。

多任务：一个或多个进程轮转运行。

时间片：一个进程执行它的控制流的一部分的每一段时间。

并行流：多个逻辑流分别在不同处理器上运行，微观上和宏观上都是同时的！

6.5.4：私有地址空间

一台n位的机器，地址可能有个。

进程为每个程序提供它的私有地址空间，这个空间是不允许其他进程读或写的。

6.5.5：用户模式和内核模式

处理器为了安全，有必要限制一个应用程序可以执行的指令和可以访问的地址空间范围。

通过某个控制寄存器中的一个模式位来实现！

特权指令：比如停止处理器，发起一个 I/O 操作，改变模式位等

进程从用户模式进入内核模式的唯一方法：通过像中断、故障、陷阱这样的异常。

6.5.6：上下文切换

上下文：进程运行的环境。包括通用寄存器，浮点寄存器，程序计数器，用户占，状态寄存器，内核栈，内核数据结构等

内核为每个进程维护一个上下文。

通过上下文切换，控制流从一个进程切换到另一个进程。

切换发生在内核模式下！

6.5.7：创建进程

使用fork函数，函数原型为：int fork(void)

• 特点：调用1次，返回2次。返回0到子进程，返回子进程的pid到父进程。
• 子进程与父进程的最大区别是，他们的进程号PID不同，子进程的PID总是非零的！
• 并发执行，对于某条指令的执行，我们不能确定是父进程先执行还是子进程先执行。
• 拥有相同的但时独立的地址空间。
• 共享文件。子进程继承了父进程的所有打开文件，如printf。

画进程图分析fork函数

示例1：一个fork函数的进程图

我们可以看到，子进程和父进程拥有不同的地址空间，两个进程对x的修改互不影响。

示例2：多个fork函数的进程图，子进程也可以调用fork函数

可以看到，子进程不是从头开始执行的，而是从它父进程执行后进入它的地方开始继续执行的。

6.5.8：结束进程

使用exit函数，函数原型：void exit(int status)

6.5.9：僵死进程

定义：当进程终止时（exit），依然会消耗系统资源，比如操作系统那个保留多个不同的数据表。

回收：由父进程回收已终止的子进程。内核给父进程提供相关终止状态信息，父进程丢弃子进程。

若父进程没有完成回收就终止了，则由Init进程来回收子进程。

6.5.10：回收子进程

使用waitpid函数

原理：父进程调用该函数，等待子进程运行结束。只有当所有子进程都运行结束，这个函数才会立刻返回。否则，父进程被阻塞暂停运行。

成功则返回子进程PID，WNOHANG则返回0，其他错误返回-1

使用wait函数，简化版的waitpid函数。

原理一致，返回值是被终止子进程的pid.

6.5.10：加载并运行程序

使用execve函数。

6.5.11：进程与程序的区别

6.6：信号

6.6.1：什么是信号

更高层的软件形式的异常，也称为Linux信号，允许进程和内核中断其他进程。信号就是一条消息，它通知进程系统中发生了一个某种类型的时间。

6.6.2：软件层异常和硬件层异常

6.6.3：信号的类型

Linux系统支持的30种不同类型的信号。

6.6.4：信号的处理流程

和中断与陷阱类似，但发送对象和处理程序不同！

1. 内核发送一个信号到当前进程，当前进程接收该信号。
2. 当前进程把控制传递给信号处理程序（用户层函数）。
3. 信号处理程序处理该信号。
4. 信号处理程序将控制返回给下一条指令。

6.6.5：内核发送信号的动机

内核为什么发送信号给当前进程？

1. 当前进程犯错，内核要阻止你，被动接收来自内核的信号
2. 主动请求内核帮忙发送信号完成一些操作，如父进程请求终止子进程 | 接收类型 | | | —- | —- | | 被动接收 | 当前进程执行了非法指令，内核发送SIGILL；
   当前进程执行除以零的指令，内核发送SIGFPE
   当前进程进行非法存储器引用，内核发送SIGSEGV | | 主动请求 | 用户按键触发如Ctrl + C，发送SIGNIT
   父进程希望终止它的子进程，内核代父进程发送SIGKILL信号到子进程
   子进程被终止后，内核代子进程发送SIGCHLD到父进程 |

6.6.6：信号术语

1. 发送信号：内核发送信号给（目的进程）当前进程。
2. 接收信号：目的进程被强迫接收或选择接收或忽略信号。
3. 待处理信号：信号已经发送给当前进程，当前进程暂不接收，信号都到了，却被堵在门外了。
4. 待处理信号集：多种类型信号等待被处理。一种类型的信号只能有一个被留在待处理信号集中，后来的同类型信号只会被丢弃。
5. 信号阻塞：当前进程不愿意接收某类信号，但当它愿意的时候也可以接收

6.6.7：信号发送

一. 使用/bin/kill程序发送

/bin/kill -9 6279

发送信号SIGKILL给进程6279，终止该进程。

二. 使用kill函数发送信号

函数原型

    示例：
![](https://gitee.com/zwjason/pictureBed/raw/master/image-20200826145914901.png#height=374&id=VUNf6&originHeight=498&originWidth=765&originalType=binary&ratio=1&status=done&style=none&width=574)

三. 使用alarm函数

函数原型

作用：让内核在secs秒后发送一个SIGALRM信号给调用alarm函数的进程。

示例：

第18行用Signal函数把SIGALRM信号和handler函数绑定，接收到该信号就会去handler函数执行！

第19行调用alarm函数发送一个SIGALRM信号给当前进程。当前进程接收到信号去handler函数执行，打印一个BEEP后又发送一个SIGALRAM信号给当前进程，根据分析，总共应该打印5个BEEP和1个BOOM！

6.6.8：信号处理

每个信号都有一个预定义的默认行为，为以下4种之一。

一. 设置信号处理程序

程序员要自定义信号处理程序来实现自己想要的处理。

使用库函数signal把信号和处理程序绑定起来，当进程接收到该信号时，就会进入处理程序执行。

第12行main函数用signal函数把信号SIGINT和处理程序handler绑定，如果接收到了该信号就执行handler函数，输出”Caught SIGINT”

SIGINT信号由键盘组合Ctrl + C发出。

二. 多信号处理—信号接收问题

假设handler函数和信号X绑定了。

接收原则1：丢入待处理信号集。当handler正在处理信号X时，如果又捕获了一个信号X，这时不会停止handler函数，而是把这个信号放入待处理信号集，知道handler函数执行完毕才接收这个信号。

接受原则2：丢弃重复的信号。两个信号X被发送到当前进程，进程接收第一个，若第一个还没被处理，则直接丢弃第二个！（同种类型的信号只会保留一个）；若第一个信号正在处理，参考接受原则1.

父进程实时回收子进程—循序渐进改良

初版：

解释：

每个子进程正常终止，都会由内核代发一个SIGCHLD信号给父进程。

第19行把SIGCHLD信号和handler1函数绑定，当某个子进程结束时，进入handler1函数执行waitpid函数回收子进程，回收大概2秒。

第23行创建了3个子进程，每个子进程大概执行1秒。

第32行read等待读取字符串到buf数组，但是会被SIGCHLD信号中断，处理返回后read不再继续读，返回错误！

缺陷：

根据信号接收原则，当第一个子进程结束时，父进程正常接收来自内核发送的SIGCHLD信号并回收子进程；当第二个进程结束时，父进程正在回收第一个子进程（时间差），那么就把第二个SIGCHLD信号丢入待处理信号集；当第三个子进程结束时（父进程刚回收完第一个子进程），由于待处理信号集已经存在一个SIGCHLD信号，那么第三个SIGCHLD信号被丢弃了。

也就是说，父进程只回收了第1,2个子进程，第3个进程称为了僵死进程。

改良版

解释：

只是信号处理程序由handler1改成了handler2，第7行的if变成了while.

这样handler2只根据第一个子进程结束时，内核发送的SIGCHLD信号就一次性循环回收了3个子进程！

虽然接收信号的缺陷仍然和初版一模一样（第二个信号被加入待处理信号集，第三个信号被丢弃），但是却回收了所有子进程！

当父进程处理第二个SIGCHLD时，发现已经没有子进程可以回收了。

缺陷：

read函数还是被中断了！

再改良版

你懂我意思吧，还是if改成while

我循环读，总有一次能够重启并完成读取字符串。

子进程也是可以接收信号的！

SIGUSR1是用户定义的信号。

父进程打印2，然后创建子进程，子进程进入无限循环。

父进程请求内核发送SIGUSR1信号给子进程使其终止。

然后子进程从无限循环中跳出处理SIGUSR1信号，输出1.

父进程回收子进程后，输出3.

6.6.9：同步错误问题

问题解释：

1. Fork函数执行后，内核同时调度子进程和父进程。
2. 若先调度父进程。父进程马上执行addjob函数把子进程加入工作列表，子进程执行完内核发送SIGCHLD给父进程，父进程捕获进入handler函数deletejiob，顺序正常！
3. 若先调度子进程。子进程调用execve函数立刻结束，父进程捕获到内核发送的SIGCHAL信号，父进程先进入handler函数deletejob，再回到循环addjob，顺序错误！

解决方法：

确保父进程先addjob，通过互斥锁来实现（操作系统有更详细的关于同步问题的讲解，大致上是利用互斥锁和信号量解决的），当内核给父进程发送SIGCHLD信号时，先上锁阻塞该信号不接收，addjob后开锁接收。

6.6.10：非本地跳转

C语言提供的一种用户级异常控制流，称为非本地跳转。

作用：将控制直接从一个函数传递到另一个函数，没有正常的调用-返回模式。

实现：通过setjmp和longjump两个函数实现

setjmp函数调用一次，返回多次；longjmp调用一次，从不返回！

应用

1. 允许从一个深层嵌套的函数调用中立即返回。通常是检测到某个错误才返回，不用费力解开调用栈。
   

先是setjmp返回0，执行foo函数，foo函数if不成立调用bar函数，bar函数的if成立，跳回回跳点并且rc被重置为2，执行第二个else if

1. 使信号处理程序跳回一个指定位置，而不是默认的被信号到达所中断指令的位置。

当执行这个程序时，用户输入Ctrl + C，会有以下输出结果

七. 虚拟内存

7.1：写在前面

我们的大环境是基于IA-32架构的Linux系统

7.2：什么是虚拟内存

我认为，利用磁盘空间构建出来的看似内存空间的存储空间。

7.3：为什么需要虚拟内存

设计到虚拟内存的意义，要先了解后才懂得透彻。

简单地说，包括解决内存空间不足的问题、保护内存空间、实现一些更好的东西。

32位的系统，按字节编码，可以编码个字节空间，即空间，这就是主存的大小。

7.4：物理寻址和虚拟寻址

7.4.1：物理寻址

计算机系统的主存被组织成一个由M个连续的字节大小的单元组成的数组，每个字节空间都有唯一的物理地址 (Physical Address, PA) 。

那么CPU直接使用物理地址去主存找数据，就成了最自然朴素的方式了。

图中展示了一条读取4字节数据的指令工作流程

CPU执行该指令时生成一个物理地址，通过总线传给主存；

主存从物理地址开始处连续访问4个字节的数据通过总线传回给CPU；

CPU把该数据放在某个寄存器中。

7.4.2：虚拟寻址

图中展示了一条读取4字节数据的指令工作流程

CPU执行该指令时生成一个虚拟地址，通过总线传给地址翻译单元MMU；

MMU把虚拟地址翻译成物理地址通过总线传给主存；

主存从物理地址开始处连续访问4个字节的数据通过总线传回给CPU；

CPU把该数据放在某个寄存器中。

内存管理单元 (Memory Management Unit, MMU)：在CPU芯片上与硬件通过存储在主存中的查询表来翻译虚拟地址的一个硬件。

7.5：地址空间

定义：一个非负整数的集合

线性地址空间：地址空间中国的整数是连续的。

一个32位的系统有个地址，按一个地址对应一个字节，则

7.6：虚拟内存的基本思想

主存中的每个字节都有一个选自虚拟地址空间的虚拟地址和选择物理地址空间的物理地址。

7.7：虚拟内存作为缓存的工具 (主存作为虚拟内存的高速缓存)

虚拟内存被组织为一个 由存放在磁盘上的N个连续的字节大小的单元组成的 数组。

说人话就是那某部分磁盘空间划分出来，再把这部分划分成N个大小相同的连续单元，然后把这部分看成一个数组。

VM (Virtual Machine) 系统中的一些概念

虚拟页 (Virtual Page, VP)

大小固定的块，块大小为字节。

物理页 (Physical Page, PP)

从主存分割出的块，大小也是字节。有时也被称为页帧 (Page Frame)。

虚拟页分类

任何时候，虚拟页分为3种不相交的状态

VM系统划分某个块出来作为虚拟页，称该页为已分配页。

虚拟内存有8个虚拟页，编号0-7.

可以看到虚拟页1,4,6已经缓存到物理内存；

虚拟页0,3还未分配，不占磁盘空间；

虚拟页2,5,7已分配，但还没缓存带物理内存中。

7.8: 页表

7.8.1: 为什么需要页表

前面谈到的Cache作为主内的高速缓存，当CPU要取主存中的数据时，首先会去Cache找这个数据是否存在。如果在直接取回去，否则才去主存找。

而在这，当CPU需要某个磁盘上的数据时，CPU要先去主存中找，但是主存采用的是全相联映射，行匹配非常慢。因此，CPU需要一个辅助工具告诉它，它要找的东西在不在主存，这个东西就是页表。

7.8.2: 理解式定义

页表是记录虚拟页与物理页之间映射关系的一种数据结构。页表是页表条目 (Page Table Entry, PTE) 的数组。页表存储在主存中！

页表条目：有效位 + 物理地址的相关信息。有效位用于标识虚拟页是否已经缓存到主存中。

现假设页表条目是由1位有效位和n位地址字段组成的。

7.8.3: 页命中

假设现在CPU要读包含在VP2中的某个字。

1. 地址翻译硬件根据虚拟地址定位到PTE2。
2. PTE2的有效位为1，说明该虚拟页已经缓存到主存中。
3. 根据这个页表条目后面的物理地址相关信息去主存找这个虚拟页的起始位置，然后读取数据。

7.8.4: 缺页 (页不命中)

假设现在CPU要读取包含在VP3中的某个字

1. 地址翻译硬件根据虚拟地址定位到PTE3。
2. PTE3的有效位为0，说明该虚拟页没有缓存到主存中。
3. 触发缺页异常，调用内核的缺页异常处理程序。
4. 如果主存有空位，缺页异常处理程序把VP3放在空位即可；但是这里主存已经满了，缺页异常处理程序必须选择一个牺牲页，这里选择了PP3中的VP4作为牺牲页。
5. 内核直接把VP3复制到PP3的位置替换了VP4. 同时更新PTE3和PTE4 (更新成什么不用详细说了吧).
6. 异常处理程序返回，重启这一条读指令，然后正常页命中。

7.8.5: 页面调度 (交换)

在磁盘和主存中传送页面的过程。

7.8.6: 页面调入 (换入)

页面从磁盘换入主存。

7.8.7: 页面调出 (换出)

页面从主存换出磁盘。

7.8.9: 按需页面调度

直到发生页不命中才把页面调入主存的调度策略。现在系统都是用该策略。

7.9: 局部性之于虚拟内存

从上面可以看到，触发缺页异常时，还是要从磁盘调入页到主存，这速度是极慢的，但这会在很大程度上影响性能吗？

Actually，virtual memory works very well thanks ti locality !

实际上，多亏了局部性，虚拟内存工作的非常好！

程序趋向于在一个较小的活动页面集合上工作，这个集合称为工作集或常驻集合。

所以除了初始的冷不命中导致的磁盘流量 (页面调入) 之外，后面程序对这个工作集的引用一般都能够命中。

如果程序具有良好的时间局部性，那么虚拟内存就能工作的很好。

但是并不是所有程序都会具有良好的时间局部性，如果工作集超出了主存大小，这时候就会出现频繁的页面调度，这种情况称为抖动！

程序员如果发现程序性能很差时，可能需要考虑是否出现了抖动！

7.10: 虚拟内存的作用

我们之前都假设只有一个页表，实际上，操作系统 (Operating System, OS) 为每个进程都维护了一个页表，也就是说为每个进程都维护了一个虚拟地址空间。

7.10.1: 简化共享

当不同进程有相同的VP时，能够共享一个PP.

7.10.2: 简化链接

虚拟内存使得每个进程都可以使用相同的内存映射格式。借助页表的映射关系，不需要关心进程的每个VP映射到了哪个PP.

7.10.3: 简化加载

根据按需页面调度，不需要一次把可执行文件都加载到主存。

7.10.4: 简化内存分配

虚拟内存可以给一个用户进程提供一个简单的分配额外内存的机制。当用户进程申请额外内存空间时，OS分配k个连续的VP给它，借助页表的映射关系，可以随意分配k个PP，不要求连续的！

7.10.5: 简化内存保护

问题：避免一个进程访问其他进程除了共享页面的页面；多个进程共享同一个页面时，某个进程不能修改共享页面，除非所有进程都允许修改；防止用户进程访问属于内核的数据。

解决：利用页表，多设几个标志位。

7.11: 地址翻译 (重点)

7.11.1: 翻译硬件

内存管理单元 (Memory Control Unit, MMU)

7.11.2: 地址翻译使用的符号

建议熟悉了符号再往下看！

基本参数

符号	描述
	虚拟地址空间中的地址数量，虚拟地址有n位
	物理地址空间中的地址数量，物理地址有m位
	页大小 (字节)

注：由于物理页和虚拟页大小相同，因此都称为页。

虚拟地址的组成部分

TLB：Translation Lookaside Buffer，翻译后备缓冲器。

物理地址的组成部分

7.11.3: 地址翻译的基础流程

概念明确

1. 页表基址寄存器 (Page Table Base Register, PTBR) ：始终指向页表的起始位置。
2. 虚拟地址组成：p位VPO和n-p位VPN
3. 物理地址狗能：p位PPO和m-p位PPN

流程

1. 根据虚拟页号VPN定位PTE条目，如VPN0选择PTE0，VPN1选择PTE1.
2. 检查有效位，若为1有效，把后面的位作为物理页号PPN. 然后直接虚拟页偏移VPO当做物理页偏移PPO. 得到一个完整的物理地址。若无效，触发缺页异常。

7.11.4: CPU执行时页命中流程

疯狂使用”中文全称+英文缩写“来强化记忆，啰嗦了点

1. CPU生成虚拟地址VA传给内存管理单元MMU
2. 内存管理单元MMU根据虚拟地址VA生成页表条目地址PTEA传给主存
3. 主存根据页表条目地址PTEA返回页表条目PTE给内存管理单元MMU
4. 内存管理单元MMU检测到页表条目PTE的有效位为1，生成物理地址PA并传给主存
5. 主存根据物理地址PA取得数据传回给CPU

7.11.5: CPU执行时缺页流程

1. CPU生成虚拟地址VA传给内存管理单元MMU
2. 内存管理单元MMU根据虚拟地址VA生成页表条目地址PTEA传给主存
3. 主存根据页表条目地址PTEA返回页表条目PTE给内存管理单元MMU
4. 内存管理单元MMU检测到页表条目PTE的有效位为0，触发缺页异常
5. 缺页异常处理程序选择牺牲页，如果该页被修改过，则换出到磁盘，否则直接覆盖！
6. 磁盘将新页换入到主存，同时更新PTE (5,6步造成的)
7. 缺页异常程序返回控制给进程，进程再次执行导致缺页异常的指令

7.12: 结合高速缓存和虚拟内存

系统访问高速缓存用虚拟地址还是物理地址？

答：物理地址，所以要先进行地址翻译

翻译的过程和上面说的基础流程有所不同，因为页表条目也是可以被高速缓存缓存的！

若恰好地址翻译时所需的页表条目被缓存了，就不需要到主存取了！

得到了物理地址后，如何访问高速缓存取数据，在之前介绍过的高速缓存部分有详细说明。

7.13: 利用TLB加速地址翻译

翻译后备缓冲器TLB：Translation Lookaside Buffer.

作为页表的高速缓存。

7.13.1: 为什么需要 (如果没有TLB会怎么样)

1. 即使是页命中，得到PTE也要访问一次主存，时间是10-100周期
2. 如果缺页，经过缺页异常处理程序进行页面调度后 (不管有无TLB，缺了就是缺了，任何骚操作都不能避免访问磁盘)，重启指令虽然一定页命中，但还是访问主存，也就是说缺页将需要访问两次主存，时间是20-200周期
3. 运气好，需要的PTE在高速缓存L1中，时间周期是1-2周期
4. 贪！1-2周期虽然短，但还是不够快，你懂我意思吧，不够快！

7.13.2: TLB特点

1. 比较小的高速缓存，相联度高 (即组数少)，放在内存管理单元MMU里面。
2. TLB缓存的页表条目的一个子集。
3. TLB是虚拟寻址的。说人话就是，你要用虚拟地址去它哪里查找数据。

7.13.3: 虚拟地址用于访问TLB时的新划分方法

假设TLB有个组

虚拟页偏移VPO不变，虚拟页号VPN的低t位的TLB索引，剩余的位作为TLB标记。

使用VPN去访问TLB获得PTE的过程和一般的高速缓存访问类似，参悟下图吧= - =

7.14: 多级页表

7.14.1: 为什么要用多级页表

就以我们使用的IA-32的Linux系统为例，假设地址空间是32位的、页大小为4KB、一个PTE占4字节。

那么，所以虚拟页偏移VPO占12位，物理页偏移也占12位。

因此虚拟页号VPN和物理页号都占32 - 12 = 20位。

因此虚拟空间可以有个页面，那么就需要 个PTE

一个PTE占4字节，那么页表大小就是.

需要这么大的页表留驻在内存中！难过吗，这么大的页表= =

7.14.2: 什么是多级页表

我的理解是：将一级页表分层次，使得常驻在内存的最低级的页表尽量小

7.14.3: 二级页表举例

我们仍然采用上述的地址空间假设

此时若我们采用二级页表结构，一级页表的一个条目就映射虚拟空间中一个4MB大小的片

那么32位的虚拟空间，大小，我只需要个条目就映射完了

而1024个条目的大小才，也就是说常驻内存的页表大小只有4KB了！

那么如何做到一级页表的一个条目就映射虚拟空间中一个4MB大小的片呢？

答：页表没分层时不是已经有一个页表把虚拟空间都映射完了吗？

该页表的一个PTE映射一个大小为4KB的虚拟页，那么1024个PTE不就映射了4MB大小的片了吗！

此时，如果我们把这1024个PTE看成一个块 (那么此块大小，让一级页表的一个PTE映射到这个块的首地址，不就实现问题的要求了吗！

这时，我们把被一级页表映射的页表称为二级页表。

也就是说，一级页表的PTE不再直接映射虚拟页，而是映射二级页表的一个块！我映射不了4MB大小的片，我还不能借助别人帮忙吗= =

可以看到，无论如何，4KB大小的一级页表要常驻内存是无可避免的。

当VM系统在片i中分配了一个页，那么二级页表就要产生一个4KB大小的片，同时一级页表的第i个PTE指向这个片，如0,1,8

若某个片的都没分配页，则相应的PTE为空，如2,3,4,5,6,7

二级页表的大小就由这被分配了页的片的大小决定。

这样，只有当所有片中都被分配了页，才会出现4MB大小的二级页表，退化为页表未分级的情况！

然而，由于局部性，通常不会出现这样的情况。

就这样，利用了未分配则不存在的性质，使得常驻内存的页表大小变小了一个量级

其实可以看到，二级页表结构就是把原本一级页表结构拆分，然后多用一个页表完成映射。那么此时如果你需要三级页表，你就再把上图的一级页表拆分成片，然后造一个页表映射到这些片。套娃骚操作= =！

7.15: 综合：端到端的地址翻译 (重点)

根据题设，我们需要弄明白两个结构：TLB和L1

1. 切入点：页大小，因此 VPO 和 PPO 都是 6 位，则 VPN 为 14 - 6 = 8 位，PPN 为 12 - 6 = 6 位，因此得到如图所示的虚拟地址和物理地址的格式。
2. 由于TLB有组，因此 TLB 索引 TLBI 有 2 位即 VPN 的低 2 位，则剩下高 6 位为 TLB 标记 TLBT。

1. 由题知，L1 有 个组，直接映射 ，块大小为 ，因此 s = 4, b = 2, t = 12 - 4 - 2 = 6

这里 t,s,b分别是CT,CI,CO

给出下面的TLB、页表和L1

现在给出加载指令要读虚拟地址VA = 0x3d4的数据，怎么找？

1. 先去TLB找，看所需PTE是否被缓存到了TLB。根据以上分析，我们很快能知道TLBI和TLBT

1. 定位到TLB的第3组，标记为0x03，发现有标记匹配且有效，得到PPN = 0xd
2. 由此复制VPO为PPO后，可以拼出物理地址，再划分CT,CI,CO去L1查找数据

1. 定位到第5组，标记为0x0d，块偏移为0x0，发现行标记匹配且有效，得到数据0x36.

这是最简单的流程了，因为很幸运，TLB命中且L1命中。

复杂的情况有很多，大概理一理，

TLB有命中和不命中。

页表有页命中和缺页

高速缓存有命中和不命中

根据排列组合，有8种情况，还没考虑去主存和磁盘能否找到，一一举例要傻掉，所以明白每一步的流程 (都在前文说了，哪里不清楚跳到哪里看) 非常重要。

这是Intel Core i7的Linux系统的地址翻译大概流程，为了简化，省略的很多步骤，如缺页处理

7.16：Core i7系统对地址翻译的优化

页大小为4KB，这样我们可以知道VPO和PPO有12位

物理寻址的、八路组相联的L1有64个组，块大小为64字节，因此t,s,b分别是20,6,6

可以看到s和b加起来恰好有12位。

因此当CPU把虚拟地址传给内存管理单元获取PPN时，系统不管能不能找到，先利用VPO直接去L1进行组选择，得到这一组的8行，等MMU返回PPN时，直接开始在这8行里匹配。

这样，不需要等MMU返回物理地址再去L1找数据。

7.16：Linux虚拟内存系统

7.16.1：Linux的内核为每一个进程维护一个私有的虚拟地址空间。

7.16.2：Linux虚拟内存区域

1. 区域：Linux将虚拟内存组织成一些区域的集合。一个区域就是已分配的虚拟内存的连续片，连续片中的页以某种方式关联起来。
2. 间隙：区域的存在，允许虚拟地址空间有间隙。

mm_struct：任务结构，指向内核运行该程序所需的所有信息。

pgd指向第一级页表的基址，mmap指向一个叫做区域结构vm_area_struct的链表。

7.16.3：Linux缺页异常处理

假设内存管理单元MMU试图翻译一个虚拟地址A，触发了缺页异常。

步骤1：检查地址合法性。A在区域结构定义的某个区域内吗？不在，则触发段错误！在则进入步骤2.

步骤2：检查访问合法性。如对只读页面进行写操作，用户模式的进程尝试读取只有内核模式才能读取的数据等都是不合法的访问。不合法的访问触发触发保护异常，终止该进程！如果合法，进入步骤3.

步骤3：采取页面调度策略。经过前面两个步骤，确定了该地址的合法性，那么将根据页面调度策略选择一个牺牲页。若牺牲页被修改过，要换出到磁盘，然后换入新页，同时更新PTE；否则新页直接覆盖牺牲页。然后CPU重启引起缺页的指令，就可以正常访问数据了。

7.17：内存映射

7.17.1：内存映射

Linux通过将一个虚拟内存区域与一个磁盘上的对象关联起来，以初始化这个虚拟内存区域的内容的过程。

7.17.2：磁盘对象的分类

7.17.3：共享对象

为什么要共享对象

每个进程拥有私有的虚拟地址空间可以避免其他进程的错误读写。但是许多进程拥有相同的只读代码区域，比如每个C程序几乎都会用到printf. 如果每个进程都在主存中保留一份副本，是对主存的浪费。但是如果所有进程共同使用一份副本就可以节省大量主存空间。

虚拟内存中对象的分类

当一个磁盘对象被映射到虚拟内存的一个区域的时候，它要么是共享对象，要么是私有对象。

关注问题

共享对象和私有对象的写问题

1. 共享对象是属于系统的，一般只可读，不可写。如果写了，修改将会反映到磁盘的原始对象。
2. 再主存中只保留一份共享对象的副本。
3. 一个进程对共享对象的写操作，对于所有共享这个对象的进程都是可见的。
4. 考虑到对象是共享的，当一个进程对共享对象进行写操作时，不会修改主存中的共享对象副本，而是把修改后的结果反映到磁盘上的原始对象。
5. 注意图只是为了方便表示，一般物理页面不会是连续的。两个进程映射共享对象的虚拟内存区域也不一定相同。

1. 私有对象是属于进程的，所以对它的写不会反映到磁盘，反映到进程本身即可。
2. 在主存中只保留一份私有对象的副本。
3. 页表条目标记为只读，区域结构被标记为私有的写时复制
4. 私有对象也可以共享，只要两个进程的两个私有对象的初始内容相同。
5. 对私有对象的写，对于其他共享这个对象的进程是不可见的。
6. 私有对象的写采用一种称为写时复制的技术，当进程进行写操作时，触发一个保护故障，故障处理程序在主存中把相应页复制一份，更新PTE指向该页，并标识复制页是可写的。当故障处理程序返回时，CPU重启写指令，然后正常写，写完反映到进程相应的虚拟页即可。

7.19：从虚拟内存的角度看fork函数

从虚拟内存的角度描述fork函数创建进程的过程。

1. 当前进程调用fork函数时，内核为新进程创建各种数据结构，并分配一个唯一的PID.
2. 为新进程创建虚拟内存，把当前进程的任务结构mm_struct、区域结构和页表都复制了一份。同时把两个进程的每个页面标识为只读，每个区域结构都标识为私有的写时复制。
3. 当fork在新进程中返回时，新进程的虚拟内存和当前进程的虚拟内存相同。

7.20：从虚拟内存的角度看execve函数

从虚拟内存的角度描述execve函数加载和执行程序的过程。

假设运行在当前进程中的程序执行了 execve(a.out, NULL, NULL) 调用

那么execve便加载并运行包含在可执行目标文件a.out中的程序，用a,out程序替代当前程序，分以下四个步骤

1. 删除已存在的用户区域：删除当前进程虚拟地址的用户部分中的已存在的区域结构。
2. 映射私有区域：为新程序的代码，数据，bss和栈区域创建新的区域结构。所有的新区域都是私有的，写时复制的。
3. 映射共享区域：如果a.out程序与共享对象链接，比如标准C库的libc.so，那么这些对象都是动态链接到这个程序的，然后再映射到用户虚拟地址空间中的共享区域内。
4. 设置程序计数器PC：设置当前进程的上下文中的程序计数器，使它指向代码区域的入口点。