第1章系统漫游

源程序

hello程序的生命周期是从一个源程序(或者说源文件)开始的，即程序员通过编辑器创建并保存的文本文件，文件名是hello.c。
源程序：由值0和1组成的位(又称为比特)序列。
字节：8个位被组织成一组。
每个字节表示程序中的某些文本字符。

编译系统的阶段和用处

编译系统的阶段

预处理阶段：预处理器(cpp)根据以字符#开头的命令，修改原始的C程序。

比如hello.c中第1行的#include<stdio.h>命令告诉预处理器读取系统头文件stdio.h的内容，并把它直接插入程序文本中。结果就得到了另一个C程序，通常是以.i作为文件扩展名。

编译阶段：编译器(cc1)将文本文件 he11o.i翻译成文本文件 hello.s，它包含一个汇编语言程序。

汇编阶段：接下来，汇编器(as)将he11o.s翻译成机器语言指令，把这些指令打包成一种叫做可重定位目标程序(relocatableobject program)的格式，并将结果保存在目标文件 hello.o中。

链接阶段：printf函数存在于一个名为printf.o的单独的预编译好了的目标文件中，而这个文件必须以某种方式合并到我们的he1lo.o程序中。链接器(ld)就负责处理这种合并。结果就得到hello文件，它是一个可执行目标文件(或者简称为可执行文件)，可以被加载到内存中，由系统执行。

编译系统的用处

优化程序性能

现代编译器通常生成很好的代码。
需要理解机器代码和编译器将不同的C语句转换成机器代码的方式。
理解链接时出现的错误
一些令人困惑的编程错误都与链接器操作有关，特别是构建大型软件。
避免安全漏洞
缓冲区溢出漏洞是造成大多数网络和互联网服务器上安全漏洞的主要原因。

处理器硬件组成与运行过程

处理器的硬件组成

系统硬件组成图：硬件组成图提取码7568

总线

贯穿整个系统的是一组电子管道。
携带信息字节并负责在各个部件间传递。
通常总线被设计成传送定长的字节块，也就是字(word)。

I/0设备

I/O(输入/输出)设备是系统与外部世界的联系通道。
四个I/O设备:
- 作为用户输人的键盘和鼠标
- 作为用户输出的显示器
- 用于长期存储数据和程序的磁盘驱动器(简单地说就是磁盘).
每个I/O设备都通过一个控制器或适配器与I/O总线相连。控制器和适配器之间的区别主要在于它们的封装方式。
- 控制器是I/O设备本身或者系统的主印制电路板(通常称作主板)上的芯片组。
- 适配器则是一块插在主板插槽上的卡。

主存

临时存储设备，在处理器执行程序时，用来存放程序和程序处理的数据。
从物理上来说，主存是由一组动态随机存取存储器(DRAM)芯片组成的。
从逻辑上来说，存储器是一个线性的字节数组，每个字节都有其唯一的地址(数组索引)，这些地址是从零开始的。

处理器

解释(或执行)存储在主存中指令的引擎。处理器的核心是一个大小为一个字的存储设备(或寄存器)，称为程序计数器(PC)。
PC指向主存中的某条机器语言指令(即含有该条指令的地址)。
这类操作围绕着主存、寄存器文件(register file)和算术/逻辑单元(ALU)进行。
一些简单操作的例子CPU在指令的要求下可能会执行这些操作。
- 加载:从主存复制一个字节或者一个字到寄存器，以覆盖寄存器原来的内容
- 存储:从寄存器复制一个字节或者一个字到主存的某个位置，以覆盖这个位置上原来的内容。
- 操作:把两个寄存器的内容复制到ALU，ALU对这两个字做算术运算，并将结果存放到一个寄存器中，以覆盖该寄存器中原来的内容。
- 跳转:从指令本身中抽取一个字，并将这个字复制到程序计数器(PC)中，以覆盖PC中原来的值。

运行过程

初始时，shell程序执行它的指令，等待我们输入一个命令。当我们在键盘上输人字符串/hello”后，shell程序将字符逐一读入寄存器，再把它存放到内存中。
键盘上敲回车键，shell程序就知道我们已经结束了命令的输人。然后执行一系列指令来加载可执行的 he1lo文件，这些指令将he11o目标文件中的代码和数据从磁盘复制到主存。
之后，处理器就开始执行 hello程序的 main 程序中的机器语言指令。这些指令将“hello，world\n”字符串中的字节从主存复制到寄存器文件，再从寄存器文件中复制到显示设备，最终显示在屏幕上。

高速缓存

高速缓存存储器(cache memory，简称为 cache或高速缓存)，作为暂时的集结区域，存放处理器近期可能会需要的信息。

利用了高速缓存的局部性原理，即程序具有访问局部区域里的数据和代码的趋势。
通过让高速缓存里存放可能经常访问的数据，大部分的内存操作都能在快速的高速缓存中完成。

操作系统管理视图

计算机系统分层视图：计算机系统分层视图提取码7568

进程

进程是操作系统对一个正在运行的程序的一种抽象。

在一个系统上可以同时运行多个进程，而每个进程都好像在独占地使用硬件。
并发运行，则是说一个进程的指令和另一个进程的指令是交错执行的。在大多数系统中，需要运行的进程数是多于可以运行它们的CPU个数的。

线程

一个进程实际上可以由多个称为线程的执行单元组成。
每个线程都运行在进程的上下文中，并共享同样的代码和全局数据。

虚拟内存

虚拟内存为每个进程提供了一个假象，即每个进程都在独占地使用主存。
虚拟地址空间：每个进程看到的内存都是一致的。
进程的虚拟地址空间：进程的虚拟地址空间提取码：7568
- 程序代码和数据：对所有的进程来说，代码是从同一固定地址开始，紧接着的是和C全局变量相对应的数据位置。代码和数据区是直接按照可执行目标文件的内容初始化的，在示例中就是可执行文件hello。
- 堆：代码和数据区后紧随着的是运行时堆。代码和数据区在进程一开始运行时就被指定了大小，与此不同，当调用像mal1oc和free这样的C标准库函数时，堆可以在运行时动态地扩展和收缩。
- 共享库：大约在地址空间的中间部分是一块用来存放像C标准库和数学库这样的共享库的代码和数据的区域。
- 栈：位于用户虚拟地址空间顶部的是用户栈，编译器用它来实现函数调用。
- 内核虚拟内存：地址空间顶部的区域是为内核保留的。

文件

文件就是字节序列，仅此而已。
每个I/0设备，包括磁盘、键盘、显示器，甚至网络，都可以看成是文件。
系统中的所有输入输出都是通过使用一小组称为UnixI/O的系统函数调用读写文件来实现的。

并发与系统层次抽象表示

并发与并行

并发：同时具有多个活动的系统。
并行：用并发使系统运行更快。
- 并行可以在计算机系统的多个抽象层次上运用。
- 三个层次，在系统层次结构中从最高到最低级。
线程级并发：
- 在进程抽象基础上，多个程序同时执行，导致并发；
- 使用线程可以在单一进程中有多个控制流。

系统层次抽象表示

计算机系统抽象分层图：计算机系统抽象分层图提取码7568

文件是对I/0设备的抽象，虚拟内存是对程序存储器的抽象，而进程是对一个正在运行的程序的抽象。
虚拟机提供对整个计算机的抽象，包括操作系统、处理器和程序。

第2章信息的表示和处理

信息位级表示与存储

十六进制表示法
- 从0到9，以及A到F。
- C语言，以0x或0X开头的数字常量被认为是十六进制的值。
- 参见课本练习2.1-2.3。
字数据大小
- 字长：指针数据的标称大小。
寻址和字节顺序
- 小端法：最低有效字节在最前面的方式；大端法：最高有效字节在最前面的方式。
- 参加课本练习2.5-2.6。
布尔代数
- 与、或、非、异或
- 参见课本练习2.8。

位级运算（C语言）

掩码运算
- 举例：掩码0xFF(最低的8位为1)表示一个字的低位字节。位级运算x&0xFF生成一个由x的最低有效字节组成的值，而其他的字节就被置为0。
- 参见课本练习2.12-2.13，第74页；答案参见第135-136页。
逻辑运算
- 逻辑或、与、非。
- 与位级运算的区别：
  - 按位运算只有在特殊情况下，也就是参数被限制为0或者1时，才和与其对应的逻辑运算有相同的行为。
  - 如果对第一个参数求值就能确定表达式的结果，那么逻辑运算符就不会对第二个参数求值。
  - 举例：表达式 a&&5/a将不会造成被零除，而表达式 p&&*p++也不会导致间接引用空指针。
- 参见课本练习2.14-2.15，第76页；答案参见第136页。
移位运算
- 左移: x << y
  - 位向量x左移y位：丢弃左边多余比特。
  - 右边填0。
- 右移：x >> y
  - 位向量x右移y位:丢弃右边多余的比特。
  - 逻辑移位：左边填0。
  - 算术移位：左边复制最高有效位。
- 未定义行为：移位量小于零或大于等于字长。
- 参见课本练习2.16，第77页；答案参见第136页

无符号整数编码与运算

编码表示、扩展和截断

整型数据类型：关键字包括char,short,long,unsigned
无符号数的编码
- 假设有一个整数数据类型有w位，对于向量$$\vec{x} = [x_{w-1}, x_{w-2}, \cdots, x_0]$$:$$B2U_{w}(\vec{x}) \doteq \sum_{i=0}^{w-1} x_i \cdot 2^i\quad \quad \quad \quad \quad \quad$$
  -注意，无符号数编码具有唯一性
无符号数的位扩展
- 如果将一个无符号数转换为更大的数据类型，只需要在开头添加0，也就是”零扩展”。原理：定义宽度为 $$w$$ 的位向量 $$\vec{u} = [u_{w-1}, \ u_{w-2}, \ \cdots, \ u_0]$$ 和宽度为 $$w’$$ 的位向量 $$\vec{u’} = [0, \ \cdots, \ 0, \ u_{w-1}, \ u_{w-2}, \ \cdots, \ u_0]$$，其中 $$w’ > w$$。则 $$B2U_w(\vec{u}) = B2U_{w’}(\vec{u’})$$。
截断无符号数
- 对于无符号数的截断，取模即可。原理：令 $$\vec{x}$$ 等于位向量 $$[x_{w-1}, \ x_{w-2}, \ \cdots, \ x_0]$$，而 $$\vec{x’}$$ 是将其截断为 $$k$$ 位的结果：$$\vec{x’} = [x_{k-1}, \ \cdots, \ x_0]$$。令 $$x = B2U_w (\vec{x})$$，$$x’ = B2U_k (\vec{x’})$$。则 $$x’ = x \mod 2^k$$。

加法、乘法、除以2的幂

无符号数加法
- 原理如图所示：无符号数加法原理提取码7568
- 检测移除的原理如下：对在范围 $$0 \le x, y \le UMax_w$$ 中的 $$x$$ 和 $$y$$，令 $$s = x +^u_w y$$。则对计算 $$s$$，当且仅当 $$s < x$$ （或者等价地 $$s < y$$）时，发生了溢出。
- 参考课本习题2.27，第98页；答案见第138页。
无符号数求反
- 原理如图所示：无符号数求反提取码7568
无符号乘法
- 原理：对满足 $$0 \le x, y \le UMax_w$$ 的 $$x$$ 和 $$y$$ 有：$$x *^u_w y = (x \cdot y) \mod 2^w$$
与2的幂相乘的无符号乘法
- 原理：C变量 $$x$$ 和 $$k$$ 有无符号数值 $$x$$ 和 $$k$$，且 $$0 \le k < w$$，则 C 表达式 $$x << k$$ 产生数值 $$x *^u 2^k$$。
除以2的幂的无符号除法
- 原理：C变量$$x$$和$$k$$有无符号数值$$x$$和$$k$$，且$$0 \le k < w$$，则C表达式$$x >> k$$产生数值$$x / 2^k$$。

补码整数编码与运算

编码表示、扩展和截断

补码编码
- 对于向量$$\vec{x} = [x_{w-1}, \ x_{w-2}, \ \cdots, \ x_0]$$：$$B2T_w (\vec{x}) \overset{\underset{\mathrm{def}}{}}{=} -x_{w-1} 2^{w-1} + \sum_{i=0}^{w-2} x_i 2^i \tag$$
- 注意，补码编码也具有唯一性。
补码的符号扩展
- 如果将一个补码数字转换为一个更大的数据类型，可以执行符号扩展，在表示中添加最高有效位的值，原理：定义宽度为 $$w$$ 的位向量 $$\vec{x} = [x_{w-1}, \ x_{w-2}, \ \cdots, \ x_0]$$ 和宽度为 $$w’$$ 的位向量 $$\vec{x’} = [x_{w-1}, \ \cdots, \ x_{w-1}, \ x_{w-2}, \ \cdots, \ x_0]$$，其中 $$w’ > w$$。则 $$B2T_w (\vec{x}) = B2T_{w’} (\vec{x’})$$。
- 参考课本练习2.22、2.23，第91-92页，答案见第138页。
补码的数值截断
- 截断补码数值，但需要把最高位变为符号位。原理如下：令 $$\vec{x}$$ 等于位向量$$[x_{w-1}, \ x_{w-2}, \ \cdots, \ x_0]$$，而 $$\vec{x’}$$ 是将其截断为 $$k$$ 位的结果：$$\vec{x’} = [x_{k-1}, \ \cdots, \ x_0]$$。令 $$x = B2U_w (\vec{x})$$，$$x’ = B2T_k (\vec{x’})$$。则 $$x’ = U2T_k (x \mod 2^k)$$。
- 参考课本练习2.24，第93页，答案见第138页

加法、乘法、除以2的幂

补码加法
- 原理如图：补码加法提取码7568
- 参见课本习题2.29、2.30、2.31、2.32，第101页；答案见139-140页。
补码的非
- 原理如图：补码的非提取码7568
补码乘法
- 原理：对满足 $$TMin_w \le x, y \le TMax_w$$ 的 $$x$$ 和 $$y$$ 有：$$x *^t_w y = U2T_w((x \cdot y) \mod 2^w)$$
无符号和补码乘法位级等价性
- 原理：给定长度为 $w$ 的位向量 $x$ 和 $y$，用补码形式的位向量来定义整数 $x$ 和 $y$：$x = B2T_w(x’)$，$y = B2T_w(y’)$。用无符号形式的位向量表示来定义非负整数 $x’$ 和 $y’$：$x’ = B2U_w(x)$，$y’ = B2U_w(y)$。则$$T2B_w(x *^t_w y) = U2B_w(x’ *^u_w y’)$$
- 参考课本习题2.35、2.36，第104页；答案见第140页。
与2的幂相乘的补码乘法
- C 变量 $$x$$ 和 $$k$$ 有补码值 $$x$$ 和无符号数值 $$k$$，且 $$0 \le k < w$$，则 C 表达式 $$x << k$$ 产生数值 $$x *^t 2^k$$。
除以2的幂的补码除法，向下舍入
- 原理：C变量$$x$$和$$k$$分别有补码值$$x$$和无符号数值$$k$$，且$$0 \le k < w$$，则当执行算术移位时，C表达式$$x >> k$$ 产生数值$$[x / 2^k]$$。
除以2的幂的补码出发，向上舍入
- 原理：C变量$$x$$和$$k$$分别有补码值$$x$$和无符号数值$$k$$，且$$0 \le k < w$$，则当执行算术移位时C表达式$$(x + (1 << k) - 1) >> k产生数值$$[ x / 2^k ]$$。

无符号与补码的转换

有符号数和无符号数之间的转换
- 规律：数值可能改变，但是位模式不变。
- 规则：如果在最值范围内，可以有相同的无符号和补码表示，而如果超过了这个范围之外，那么对其取最高位处的模。
补码转换为无符号数
- 原理如图：补码转换为无符号数提取码7568
无符号数转换为补码
- 原理如图：无符号数转换为补码提取码7568
有符号数与无符号数
- 参见课本习题2.21，第89页，答案见第137页。
有符号数和无符号数的建议
- 由于隐式强制类型转换和无符号数数据类型造成的细微错误。
- 典型的例子是两个无符号数相减为负数，会被转换为一个很大的无符号数造成非法。
- 参见课本习题2.25、2.26，第94页，答案见第138页。

浮点数表示与运算

二进制小数

表示	值	十进制
$$0.0_2$$	$$\frac{0}{2}$$	$$0.0_{10}$$
$$0.01_2$$	$\frac{1}{4}$$	$0.25_{10}$$
$$0.010_2$$	$\frac{2}{8}$$	$0.25_{10}$$
$$0.0011_2$$	$\frac{3}{16}$$	$0.1875_{10}$$
$$0.00110_2$$	$\frac{6}{32}$$	$0.1875_{10}$$
$$0.001101_2$$	$\frac{13}{64}$$	$0.203125_{10}$$
$$0.0011010_2$$	$\frac{26}{128}$$	$0.203125_{10}$$
$$0.00110111_2$$	$\frac{51}{256}$$	$0.19921875_{10}$$

IEEE浮点表示

IEEE 浮点标准用 $$V = (-1)^s \times M \times 2^E$$ 的形式来表示一个数：

符号 $$s$$ 决定该数是负数 ($$s = 1$$) 还是正数 ($$s = 0$$)，而对其数值 $$0$$ 的符号位解释作为特殊情况处理。
尾数 $$M$$ 是一个二进制小数，它的范围是 $$1 \sim 2 - \epsilon$$，或者是 $$0 \sim 1 - \epsilon$$。
阶码 $$E$$ 的作用是对浮点数放大权，这个权重是 $$2$$ 的 $$E$$ 次幂（可能是负数）。将浮点数的位表示刻分为三个字段，分别对这些值进行编码：
一个单独的符号位 $$s$$ 直接编码符号 $$s$$。
$$k$$ 位的阶码字段 $$\text{exp} = e_{k-1} \cdots e_1 e_0$$ 编码阶码 $$E$$。
$$n$$ 位小数字段 $$\text{frac} = f_{n-1} \cdots f_1 f_0$$ 编码尾数 $$M$$，但是编码出来的值也依赖于阶码字段的值是否等于 $$0$$。

标准浮点格式：标准浮点格式示意图提取码7568
单精度浮点数值分类：单精度浮点数值分类示意图提取码7568

数字示例

参考课本习题2.47，第117页；答案在第143页。

舍入

方式	1.40	1.60	1.50	2.50	-1.50
向偶数舍入	1	2	2	2	-2
向零舍入	1	1	1	2	-1
向下舍入	1	1	1	2	-2
向上舍入	2	2	2	3	-1

上述例子为四种舍入的方式。
参考课本上的习题2.50-2.52，第120页；答案在第143页。

浮点运算

浮点加法：浮点加法PPT讲解提取码7568
浮点乘法：浮点乘法PPT讲解提取码7568
C语言中的浮点数：C语言中的浮点数提取码7568
浮点数难题浮点数难题提取码7568
- 错误项解释：
  - x == (int)(float)：对于足够大的 int 类型值，转换为 float 后再转换回 int 可能会因为浮点数精度不够而失去精度，导致最终的 int 值与原始的 int 值不同。这是因为 float 只能精确表示有限大小的整数，当整数超过一定大小，其低位将无法完全被 float 类型表示。
  - d == (double)(float) ddouble 类型有更高的精度和范围，而 float 类型精度较低。当将一个 double 值转换为 float 时，如果该 double 值的精度超过 float 可以表示的范围，那么在转换为 float 时会发生精度丢失，再转换回 double 之后可能会由于精度丢失而使其值与原始的 double 值不同。
  - 2/3 == 2/3.0 ：2/3 在C语言中是整数除法，结果为0，而 2/3.0 是浮点除法，结果为0.6667。因此，整数除法的结果与浮点数除法的结果不同。
  - (d + f) - d == f：在浮点运算中，由于舍入误差的存在，(d + f) - d 不一定完全等于 f。这是因为在 d + f 运算过程中可能会产生舍入误差，然后再减去 d 时误差可能会累积，导致结果与预计的 f 不同。

第3章程序的机器级表示

机器级代码

▪ 机器指令、寄存器、操作数与寻址

PC程序计数器：下条指令地址，称为RIP。
寄存器堆：程序频繁使用的数据。
条件码：存储有关最近的算数和逻辑运算的状态信息。
内存：字节可寻址的数组、代码和用户数据、支持过程的栈。

整数寄存器：

Register	32-bit Register	Register	32-bit Register
%rax	%eax	%r8	%r8d
%rbx	%ebx	%r9	%r9d
%rcx	%ecx	%r10	%r10d
%rdx	%edx	%r11	%r11d
%rsi	%esi	%r12	%r12d
%rdi	%edi	%r13	%r13d
%rsp	%esp	%r14	%r14d
%rbp	%ebp	%r15	%r15d

可以引用低4字节（也可以引用低1或2字节）
不是内存（或cache）的一部分Not part of memory (or cache)

操作数：指示出执行一个操作中要使用的源数据值，以及放置结果的目的位置。
- 立即数：表示常数值。
- 寄存器：表示某个寄存器堆类型
- 内存引用：根据计算出来的地址（有效地址）访问某个内存位置。

寻址模式：四个部分：立即数偏移、基址寄存器、变址寄存器、比例因子。

操作数可以表示立即数（常数）值、寄存器值或是来自内存的值。比例因子s必须是1、2、4或者8。
寻址的规则：寻址提取码7568
参考课本上习题3.1，第158页；答案见第262页。

一般指令操作

数据传送指令

简单的数据传送指令

movb:传送字节
movw：传送字
movl：传送双字
movq：传送四字
movabsq：传送绝对的四字

零扩展数据传送指令：将上一部分的mov替换为movz
符号扩展数据传送指令：将上一部分的mov替换为movs，然后跟两个字母，表示某一类字（字节）传给另一类字（字节）

b字节，w字，l双字，q四字。
参考课本习题3.2-3,5，第160页；答案在第262页。

压入和弹出栈数据

pushq S 将四字压入栈
popq D 将四字弹出栈

算数和逻辑操作

leaq S,D 加载有效地址
INC D 加1
DEC D 减1
NEG D 取负
NOT D 取补
ADD S,D 加
SUB S,D 减
IMUL S,D 乘法
XOR S,D 异或
OR S,D 或
AND S,D 与
SAL k,D 左移
SHL k,D 左移
SAR k,D 算术右移
SHR k,D 逻辑右移
imulq S 有符号全乘法
mulq S 无符号全乘法
clto 转换为八字
idivq S 有符号除法
divq 无符号除法

控制

条件码
- CF:进位标志
- ZF:零标志
- SF:符号标志
- OF:溢出标志
- cmp:加上了b、w、l、q，表示比较字节、字、双字、四字。
- test:加上了b、w、l、q，表示测试字节、字、双字、四字。
访问条件码
- set:加n表示不，加s表示负，加g表示大，加l表示小，加a表示超过，加b表示低于。

跳转

jmp:没有*是直接跳转，有 *是间接跳转。
j后面添加到字母和条件码中的类似。
cmov:条件传送指令。
comv后面添加到字母和条件码中的类似。
quad:相当于case这个功能

过程调用

运行时栈：运行时栈提取码7568
转移控制：
- 使用栈支持过程调用和返回
- 过程调用
  - 将返回地址压入栈
  - 跳转到标号处
- 返回地址
  - 调用指令之后那条指令的地址
  - 反汇编的示例
- 过程返回
  - 从栈弹出地址
  - 跳转到该地址

递归过程

参考课本习题即可。

数组分配和访问

注意元素大小、总大小、起始地址、元素i的位置等等。
指针运算
嵌套数组
变长数组

异质的数据结构

结构：struct
整体结构长度是K的整数倍
满足每个元素的对齐需求
结构体的对其要求
- 结构内部
  - 必须满足每个元素的对齐需求
- 整个结构的排放
  - 每个结构有对齐需求K
    - K为任何元素对齐要求的最大值
  - 起始地址和结构长度必须为K的整数倍

内存越界引用

对抗缓冲区溢出攻击

栈随机化
栈破坏检测
限制可执行代码区域

浮点操作指令

浮点传送指令：vmov，后面接：s单精度，d双精度，ap表示封装好的
双操作数浮点转换指令：vcvt，表示截断相关的转换，其余类似
浮点运算：前面加上的是v，但注意sqrtss表示浮点数平方根
定义使用浮点函数：通过.long,找出指数字段，减去偏移1023找到指数。
位级操作：
- vwxrps:位级异或
- vandps:位级与
浮点比较操作：
- ucomiss S1,S2 比较单精度值
- ucomisd S1,S2 比较双精度值
条件码设定：
- CF进位标志位
- ZF零标志位
- PF奇偶标志位

处理器体系结构

Y86-64指令集体系结构

寄存器、内存、控制码、PC、状态：

寄存器：15个寄存器，%rax %rcx %rdx %rbx %rsp %rbp %rsi %rdi %r8 %r9 %r10 %r11 %r12 %r13 %r14
内存：很大的字节数组，字节寻址存储数组，字采用小端字节顺序存储
控制码：ZF、SF、OF
PC：程序计数器，指明下一条指令地址

指令组成与编码

指令集：重要指令集提取码7586
非法代码：f0

状态异常、常用指令详情

逻辑电路与硬件控制语言HCL

按照返回值类型来分类

布尔表达式
- 逻辑操作:a && b, a || b, !a
- 字比较:A == B, A != B, A < B, A <= B, A >= B, A > B
- 集合成员关系:A in { B, C, D }
字表达式
- Case表达式
  - [ a : A; b : B; c : C ]
  - 按顺序评估测试表达式
  - 返回第一个成功测试的字表达式

Y86-64实现

SEQ的硬件结构:取值、译码、执行、访存、写回、更新PC
- 状态设置按照第二条irmovq指令，组合逻辑开始反应状态改变。
SEQ的时序：状态方面更新都在时钟上升沿。zai
阶段计算：阶段计算提取码7568

流水线实现SEQ+、PIPE-、PIPE的阶段寄存器信号

流水线
- 非流水线：在上一个操作完成前不能开始新的操作。
- 3级流水线：最多3个操作在同时处理。
SEQ+:移动PC阶段，使得它的逻辑在时钟周期开始时运动，计算当前指令的PC值。
- 新PC计算：icode、Cnd、valC、valM、valP
- 也叫做电路重定时。
pipe-硬件：
- 流水线寄存器存储指令执行中的中间值。
- 转法（向前）路径：从一个阶段到下一个阶段传递的值，不能回跳到过去的阶段
SEQ+和PIPE-都产生dstE和dstM，指明值valE和valM的目的寄存器。

流水线PIPE对数据冒险、控制冒险、异常的触

数据冒险
- 以寄存器R 作为源的指令紧跟在以寄存器R 作为目的的指令之后；
- 常见情况，不想减慢流水线。
- 用暂停避免数据冒险：处理器停止流水线中的一条或多条指令，直到冒险条件不再满足，使之在取值和译码阶段。
- 用转发来避免数据冒险：将结果值直接从一个流水线阶段传到较早阶段。
- 加载/使用数据冒险：加载互锁，将addq指令在译码阶段暂停一个周期，将valB的值从方寸阶段中的mrmovq指令转发到译码阶段的addq指令。
控制冒险
- 错误预测条件分支
  - 我们的设计预测所有分支为选择分支
  - 朴素流水线执行两条额外指令
- 获得ret指令的返回地址
  - 朴素流水线执行三条额外指令N
异常处理
特殊控制情况
- 检测：
  - 处理ret:IRET in { D_icode,E_icode,M_icode}
  - 装载/使用冒险：E_icode in { IMRMOVQ,IPOPQ } && E_dstM in { d_srcA,d_srcB }
  - 分支预测错误：E_icode = IJXX & !e_Cnd
- 动作（下一个周期）
  - 处理ret：F暂停 D气泡 E正常 M正常 W正常
  - 装载/使用冒险：F暂停 D暂停 E气泡 M正常 W正常
  - 分支预测错误：FMW正常，DE气泡
- 控制条件的组合
  - 组合A：分支不选择，Ret指令在分支目标处
  - 组合B：指令从内存读到%rsp，后跟ret指令
状态改变的控制逻辑
- 设置条件码
- 阶段控制：也控制内存更新

性能分析

CPI约等于1.0
- 每个时钟周期取一条指令
- 几乎每个周期有效处理一条新指令
  - 尽管每条单独指令都有5个周期的时延
CPI>1.0
- 有时必须暂停或取消分支
计算CPI
- C是时钟周期数
- I是执行完成的指令数
- B是注入的气泡气泡数
  - CPI = C/I = (I+B)/I = 1.0 + B/I– 153
- 因子B/I表示气泡的平均惩罚

优化程序性能

编译器的优化与局限性

参考课本习题5.1

过程调用：不自动把strlen外提的原因
- 过程可能会有副作用
- 对于同样的参数每次返回结果可能不同
  - 依赖于全局状态
  - 过程lower可能与strlen互相作用
- 注意：
  - 编译器将过程调用看做黑盒
  - 很少做优化
内存别名：
- 别名
  - 两个不同的指针指向/引用同一个位置
  - C语言里面很常见
    - 允许地址计算
    - 直接访问存储结构
  - 尽可能使用局部变量
    - 随着循环累积
    - 以这种方式告知编译器不需要做别名

基本优化

将vec_length移出循环
每个迭代避免边界检查
使用临时变量进行累积

循环展开

每个迭代做2倍更有用的工作
循环展开与单独累加器
- 与association不同

SIMD操作：

SIMD操作提取码7568

存储器的层级结构

存储器的类型与特点

类型
- SRAM 静态RAM：双稳态存储器单元
- DRAM 动态RAM：将每个位存储为对一个点容的充电
特点
- RAM通常封装为一个芯片
- 基本存储单元是一个cell（每个cell是一个bit）
- 多个RAM芯片构成一个内存
传统CPU和内存之间的互连结构
总线是一组并行的用于传输地址、数据和控制信号的导线
总线通常是多个设备共享的
磁盘
- 磁盘构造：磁道、盘面、磁道、扇区
- 磁盘容量公式：磁盘容量=(字节数/扇区)* (平均扇区数/磁道) * (磁道数/表面) * (表面数/盘片) * (盘片数/磁盘)
- 寻道时间：通常3-9ms，最大20ms
- 最大旋转延迟=1/RPM
- 传送时间=1/RPM*1/(平均扇区数/磁道)
总线结构示例：总线示例图提取码7568

数据局部性与指令局部性

局域性原理: 程序更倾向于使用临近或者最近使用过的数据和指令
- 时间局域性:
  - 最近使用的数据在不远的将来会继续使用
- 空间局域性:
  - 相邻的数据会在一段时间内一起访问
对程序数据引用的局部性：步长小，空间局部性好
取指令的局部性：循环体越小，循环迭代次数越多，局部性越好。

存储器层次结构

寄存器
高速缓存
高速缓存
高速缓存
主存（保存本地磁盘取出的磁盘块）
本地二级存储（本地磁盘）
远程二级存储（分布式文件系统、web服务器）

缓存结构与地址编码

Cache基本概念：更小、更快、更贵，缓存了一部分块。
Cache命中：需要访问块b中的数据。
Cache丢失：块b不再cache中：丢失
- 放置策略：决定b放在哪里
- 替换策略：决定把哪个块换出

缓存命中、不命中机制

缓存命中：当程序需要第k+1层的某个数据对象d时，它首先在当前存储在第k层的一个块中查找d。如果d刚好缓存在第k层中，那么就是我们所说的缓存命中。
缓存不命中：如果第k层中没有缓存数据对象d，那么就是我们所说的缓存不命中。
缓存不命中种类：
冷启动丢失
- 冷启动丢失是因为刚开始Cache是空的
冲突丢失
- 大多数Cache将k+1层的数据块映射到k层更小的一个或者多个块位置
  - 例如k+1层的块被映射到k层（i mod 4）的位置
- 当多个块被映射到k层的同一个位置时就会出现冲突
  - 例如访问0,8,0,8,0,8就会每次导致Cache丢失
容量丢失
- 当活跃使用的Cache块大小大于Cache容量时就会导致丢失
Cache大小=S * E * B

Cache写操作

多数据副本
- L1, L2, L3, Main Memory, Disk
写命中时如何处理？
- 写透（直接写入内存）
- 写回（替换式写回）
  - 需要脏比特位标识
- 写丢失时如何处理？
  - 写分配（装载进Cache后进行更新）
    - 如果后续还有写操作时比较好
  - 非写分配（直接写入内存，不装载）
- 通常策略Typical
  - 写透+ 非写分配Write-through + No-write-allocate
  - 写回+ 写分配 Write-back + Write-allocat

高速缓存的性能影响

丢失率
- 内存引用没有在Cache中找到的比率
- 通常的Cache丢失率：
  - 3-10% for L1
  - L2也可能很小，依赖Cache大小
- 命中时间
  - 从Cache行到处理器的时间
    - 包括判断Cache是否命中的时间
  - 通常的时间
    - L1 Cache 4个时钟周期
    - L2 Cache 10个时钟周期10 clock cycles for L2
  - 丢失开销
    - 丢失需要额外的时间
    - 主存的访问周期50~200

链接

编译器与可执行文件格式

三类不同的目标文件
- 可重定位目标文件、可执行目标文件、共享目标文件
ELF目标文件格式
- ELF头
  - 字大小、字节顺序、文件类型、机器类型等
- 段头表
  - 页大小、虚拟地址内存段(节)、段大小
- .text节
  -代码
- .rodata节
  - 只读数据：跳转表,…
- .data节
  - 初始化的全局数据
- .bss节
  - 未初始化的全局变量
  - 不占内存空间

静态链接的符号解析与重定向

规则1：不允许有多个强符号
- 每个符号只允许被定义一次
- 否则会出现链接错误
规则2：当有一个强符号和多个弱符号时，选择强符号
- 对弱符号的引用改为对强符号的引用
规则3：当有多个弱符号时，选择其中任意一个
- 可以通过gcc –fno-common指定

动态链接及共享库

加载时链接
运行时链接
示意图：动态链接提取码7568

库打桩

编译时
- 对 malloc/free 的显式调用被宏展开为对 mymalloc/myfree 的调用。
链接时
- 使用链接器技巧来实现特殊名称解析。
- malloc → __wrap_malloc
- __real_malloc → malloc
加载/运行时
- 实现自定义版本的 malloc/free，通过动态链接以不同的名称加载库中的 malloc/free。

异常控制流

异常与异常处理

存在系统的每个层次
低层次机制
- 异常/ Exceptions
  - 为响应系统事件改变控制流（例如，系统状态改变）
  - 硬件和OS软件组合实现
- 高层次机制
  - 进程上下文切换
    - 硬件时钟和OS软件实现
  - 信号
    - OS软件实现
  - 非局部跳转
    - C运行时库实现
异步异常
- 由处理器外部事件引起
  - 通过处理器的中断管脚给出
  - 中断处理程序返回后执行下一条指令
- 举例：时钟中断（大约几毫秒，外部时钟芯片触发；将控制权从用户切换到内核）；外部设备的I/O中断（键盘输入；网络数据包到达；磁盘数据到达）

（剩余部分加速手抄笔记）

第1章 系统漫游

源程序

编译系统的阶段和用处

编译系统的阶段

编译系统的用处

处理器硬件组成与运行过程

处理器的硬件组成

运行过程

高速缓存

操作系统管理视图

进程

线程

虚拟内存

文件

并发与系统层次抽象表示

并发与并行

系统层次抽象表示

第2章 信息的表示和处理

信息位级表示与存储

位级运算（C语言）

无符号整数编码与运算

编码表示、扩展和截断

加法、乘法、除以2的幂

补码整数编码与运算

编码表示、扩展和截断

加法、乘法、除以2的幂

无符号与补码的转换

浮点数表示与运算

二进制小数

IEEE浮点表示

数字示例

舍入

浮点运算

第3章 程序的机器级表示

机器级代码

一般指令操作

数据传送指令

算数和逻辑操作

控制

跳转

过程调用

递归过程

数组分配和访问

异质的数据结构

内存越界引用

对抗缓冲区溢出攻击

浮点操作指令

处理器体系结构

Y86-64指令集体系结构

寄存器、内存、控制码、PC、状态：

指令组成与编码

状态异常、常用指令详情

逻辑电路与硬件控制语言HCL

Y86-64实现

流水线实现SEQ+、PIPE-、PIPE的阶段寄存器信号

流水线PIPE对数据冒险、控制冒险、异常的触

性能分析

优化程序性能

编译器的优化与局限性

基本优化

循环展开

SIMD操作：

存储器的层级结构

存储器的类型与特点

数据局部性与指令局部性

存储器层次结构

缓存结构与地址编码

缓存命中、不命中机制

Cache写操作

高速缓存的性能影响

链接

编译器与可执行文件格式

静态链接的符号解析与重定向

动态链接及共享库

库打桩

异常控制流

异常与异常处理

第1章系统漫游

第2章信息的表示和处理

第3章程序的机器级表示