快捷键

窗口操作

切换窗口：Alt+Tab
窗口移动：Win+↑/↓/←/→

文件操作

保存：Ctrl+S
关闭文件：Ctrl+W
撤销：Ctrl+Z
恢复：Ctrl+Shift+Z
复制/粘贴：Ctrl+C/V
向上/向下翻页：PageUp/PageDown
切换到左/右边的文件：Ctrl+PageUp/PageDown

选择操作

全选：Ctrl+A
选中：Shift+各种移动/跳转

光标操作

上/下/左/右移动光标：↑/↓/←/→
向上/下插入光标：Ctrl+Alt+↑/↓
在下一个匹配项处插入光标：Ctrl+D
查找/替换匹配项：Ctrl+F/H
全局查找/替换匹配项：Ctrl+Shift+F/H

更改操作

行删除：Shift+Delete
行上/下交换：Alt+↑/↓

跳转操作

跳转到上/下个光标位置：Alt+←/→
跳转到词首/尾：Ctrl+←/→
跳转到行首/尾：Home/End
跳转到列首/尾：Ctrl+Home/End
跳转到行：Ctrl+G
跳转到括号：Ctrl+Shift+\
跳到定义：F12
查看定义：Alt+F12

VSCode 其他操作

向右拆分编辑器：Ctrl+\
行注释：Ctrl+/
命令面板：F1 或 ctrl+shift+p
打开文件：F1，然后 Backspace
打开/关闭活动栏：Ctrl+B
打开/关闭面板：Ctrl+J
打开/关闭终端：Ctrl+`
查找活动栏/面板：Ctrl+Q

1. ALT+Esc 可以使当前窗口最小化。
2. Win+D 最小化所有窗口，再按一下就可以还原窗口。
3. Windows+M：最小化所有窗口 。
4. Windows+Shift+M：还原最小化的窗口。
5. Alt+空格+N 最小化当前窗口（和浏览器的最小化一样）
6. ALT+TAB 这个是切换窗口的按钮，切换到另外一个窗口，这个窗口自然也可以最小化
7. crtl+tab 软件内切换窗口
8. ctrl+shift+c 在当前文件夹打开终端

---

深入理解计算机系统

第一章 计算机系统漫游

1.1

编译器的处理过程

1. 预处理 (cpp) Pre-processor

预处理器根据 # 开头的代码处理源文件，处理后能把源文件中引用的 .h 头文件插入源文件中，得到一个以 .i 结尾的文件。

2. 编译 (ccl) compiler

编译器把 .i 文件翻译为 .s 文件
包括：词法分析，语法分析，语义分析，中间代码生成，优化等

3. 汇编 (as) Assembler

汇编器根据指令集将会变程序 .s 翻译为机器指令，也就是机器语言，生成可重定位 .o 文件

4. 链接 (Id) Linker

链接器把多个 .o 文件按照一定的规则进行调整,最后得到可执行的文件

1.2

cpu 的结构

programe count (pc)

真实含义是一个字大小的存储区域
32-bits 4 byte 64-bits 8 byte
存放的是某一条指令的地址，处理时cpu执行pc上的指令，并且更新pc使其指向下一条要执行的指令

寄存器文件 register file

cpu内部的一个存储设备，是由一些单字长的寄存器构成，每一个都有自己唯一的名字，一个临时存放变量的空间

ALU

例如计算 a+b 的值，会先把a，b的值存入寄存器，这将会覆盖寄存器原来的数值，然后再传入 ALU 中计算，最后返回值存入寄存器中，并且会把原来的值覆盖

主存 (内存)

主要存放程序指令以及数据，是由随机动态存储器的芯片组成，可以看成从 0 开始的大数组每个字节都有相应的地址

总线 I/O

内存和处理器之间通过总线来进行数据传输，总线贯穿了整个计算机系统，负责将信息从一个部件传到另一个部件，通常被设计成传送固定长度的字节块(word)
还包括键盘，磁盘，鼠标，每个输入输出设备都通过一个控制器或者适配器都与I/O总线相连，控制器与适配器的主要区别主要是在于它们的封装方式，但是都是在I/O的设备之间传输数据的

处理器

一般来讲，内存大的存储器存取数据较慢

存储数据数量

寄存器文件 100～1000B
L1 cache L1与访问寄存器一样快
L2 cache L2访问时间是L1的5倍
L3 cache L3比L2还慢
内存 1～100GB
磁盘 1～1000TB

在寄存器和内存之间引入了高速缓存，一般有三级

L1 cache L1与访问寄存器一样快
L2 cache L2访问时间是L1的5倍
L3 cache L3比L2还慢

1.3

操作系统

操作系统可操控硬件，操作系统是应用程序与硬件之间的中间层，所有应用程序必须通过操作系统来对硬件进行操纵
目的：1. 防止硬件被失控的应用程序滥用

1. 操作系统提供统一的机制来控制这些底层的硬件
   引入了几种抽象：

2. 文件是对I/O设备的抽象

3. 虚拟内存是对内存和I/O设备的抽象
4. 进程是对处理器，内存，I/O设备的抽象
5. 虚拟机是对整个计算机系统的抽象，包括操作系统及以上

上下文

操作系统跟踪进程运行中所需要的所有状态信息，例如当前PC和寄存器的值，以及内存中的内容等

虚拟地址空间

从底到高，堆，最顶部区域是为内核保留的区域，对应用程序代码不可见

1.4

在远程主机上运行程序

客户端的软件通过网络将字符串发送到ssh服务端，ssh服务端接受到之后传递给远程主机上的shell程序，在运行

阿姆达尔定律

当我们对系统的某一部分进行加速时，倍加速部分的重要性，和加速成都是影响整体系统性能的关键因素，如果我们想把计算机程序提升2倍甚至更多的速度，需要优化大部分组件
三种途径提高速度：

1. 线程级并发
2. 指令级并行
3. 单指令多数据并行

cpu核心

处理器芯片中有多个CPU核心，每个CPU核心都有自己的L1 cache和L2 cache，所有的核心共享L3 cache，集成在同一芯片上
单颗芯片集成的CPU数量高达几十个，甚至上百个
通过增加CPU核心数可增加计算机性能

超线程(同时多线程)

如果每个CPU可以执行两个线程，那4个就可以执行8个线程，
在CPU内部，程序计数器和寄存器文件有多个备份，浮点运算部件只有一份
常规单线程处理器在做线程切换时，大概需要20000个时钟周期，超线程处理器可以在单周期的基础上决定执行哪一个线程，在一个线程等待时，进行另一个程序

指令级并行

处理器可以同时执行多条指令的属性称为指令级并行，每条指令从开始到结束需要20个时钟周期或者更多，处理器可以从同时处理多达100条指令，可以保持每个周期2～4条指令的执行速率

单指令多数据并行

现代处理器允许一条指令产生多个并行的操作
SIMD的指令多是为了提高处理视频，以及声音这类数据的执行速度

第二章

2.1 信息的存贮

虚拟空间地址

在计算机中所有的地址按从0开始从大到小依次排序，所有的地址总和成为虚拟空间地址

byte

字节，一个字节有8位，采取二进制计数方式，取值范围在0~255之间
用16进制数来表示位模式 0~9+A~F，以0x开头
A: 10, 1010
C: 12, 1100
F: 15, 1111
16进制转2进制只需要每位展开为四位的二进制数就可以
二进制转化为十六进制，位数不足的补零

Word

字长，w位字长的虚拟地址空间就是(2^w-1)，
K = 2^10
M = 2^20
G = 2^30
T = 2^40
P = 2^50
E = 2^60
32位机器，最大为4GB，使用4字节的地址
64位机器，最大为16EB，使用8字节的地址
64位机器上可以生成32位机器上运行的程序:linux>gcc -m32 -o hello32/64 hello.c
64位的程序只能在64位机器上，两种程序主要区别是两种程序是如何编译的

Signed	Unsigned	32-bit	64-bit
char	unsigned char	1	1
short	unsigned short	2	2
int	unsigned	4	4
long	unsigned long	4	8
int32_t	int32_t	4	4
int64_t	int64_t	8	8
char*		4	8
float		4	4
double		8	8

字符串的存储

字符串以 null 结尾
逻辑移动和移动运算：算数右移：当最右端为0，右移补0，为1，右移补1。

布尔运算

NOT(非)

取反，就是0变为1，1变为0

AND(与)

两个参数只有两个都为1时，与的结果才是1

OR(或)

只有当两个参数都为0时，结果才是0

EXCLUSIZE-OR(异或)

只有当两个参数不同时，运算的结果才是1

按位运算

• 按位与
  就是转化为二进制数，每一个对应的位上进行与运算，每一位上得到的结果就是与运算的结果
• 按位或
  就是转化为二进制数，每一个对应的位上进行或运算，每一位上得到的结果就是或运算的结果

逻辑运算

• !(非)
  1变为0，0变为1
• !!(就是两次非运算)
• &&(逻辑与)
  就是逻辑运算并且
• ||(逻辑或)
  逻辑运算或者

移位运算

• 左移 <<
• 右移 >>

左移和右移，一般对有符号数进行算数右移，无符号数一定进行逻辑右移

• 左移( SAL k,D D<< k SHL k,D D<< k )
  就是丢弃最左端的一位，然后右端补零
• 逻辑右移( SHR k,D D>>k )
  就是丢弃最右端的一位，然后左端补零
• 算数右移( SAR k,D D>>k )

当最高位为1时，算数右移后，左端补1，最高位为0，和逻辑右移一样，算数右移保持了数据的正负不变
无符号数一定进行逻辑右移，有符号数进行算术右移

数据存储排布方式

arm架构的系统，双端法，可以配置为大端法或者小端法
大端法，最高有效字节存储在低地址 intel兼容机
小端法，最高有效字节存储在高地址 windows,ios

2.2 整数的表示

整数的编码

无符号数的编码

8位的无符号数编码范围是0~255
无符号数的最大值:
w位时，最大值为 2^w-1

有符号数的编码

采用补码的形式
有符号数用最高位来表示正负，最高位是1表示负数，最高位为0表示正数，用补码来表示有符号数，例如-1：1111， -8：1000
例如-1:1111，其实就是(-1) 2^3 + 1 2^2 + 1 2^1 + 1 2^0;
8位可以表示的无符号数的范围是-128~127
无符号数的范围:
w位时，最大 2^(w-1)-1，最小 2^(w-1)
16位数:
无符号12345: 0011000000111001
有符号-12345: 1100111111000111
无符号53191: 1100111111000111
其实就是 53191 + 12345 = 2^16

有符号数与无符号数的转换

有符号数强制转换为无符号数:位模式不变，但是解释这些位的方式变了
有符号数—>无符号数:(w位)
x < 0 : 2^w+x
x > 0 : x
无符号数->有符号数:
最高位 = 0 : x
最低位 = 1 : x-2^w
C语言执行运算时，两个数字一个是有符号数，另一个数是无符号数，C语言就会把两数都转化为无符号数，就有可能出现 —1>0 的现象

在不同字长的整数之间的转换

• 较大的数据类型转换为较小的数据类型:
  保持数值不变是不可能的，在转换时，只会保留低位的数字，所以可能会改变它原来的数值
  例如将w位截断为k位时，将会丢弃最高的w-k位，可以通过取模运算，其实就是原数除以2^k取余
  有符号数的转换，也是先截断最低的k位，然后再转化为无符号数
• 较小的数据类型转换为较大的数据类型:
  保持数值不变是可以的，
  当无符号数在转换时，就需要补高位零扩展，就是高位补零。
  0123->0000 0123
  当有符号数的转换时，就需要符号位扩展，如果符号位是0，那么就高位补零，如果符号位是1，那就高位补1
  1123->1111 1123 0123->0000 0123

2.3 整数的运算

加法

无符号数加法的原理

例如 无符号数x，无符号数y
x+ymax : x+y-2^w (发生溢出)
例如:1111 + 0001 = 1 0000 -> 结果: 0000 (去掉最高位)
判断是否溢出: return sum>=x 如果发生溢出，那就返回0，为发生溢出，返回1.发生溢出时，得到的数小于两者任意一个数

有符号数加法

例如 w位的x，y
x+y > 2^(w-1)(正溢出) : x+y-2^w
-2^(w-1) < x+y < 2^(w-1) : x+y
x+y < -2^(w-1) : x+y+2^w
例如: 0111 1111 + 0000 0001 = 1111 1111 (-128)
判断是否发生溢出:
x>0,y>0 x+y<0 (正溢出) x<0,y<0 x+y>0 (负溢出)

减法

实际上就是加上相反数

加法逆元

对于x，存在x1，使得 x+x1 = 0，x1为x的加法逆元，实际上x与x1互为相反数
对于无符号数x来说: x = 0, x1 = 0; x>0, x1 = 2^w-x (实际上就是x+x1溢出)
对于有符号数x来说: x>min, x1 =-x; x =min, x1 = x
例如:1000 0000 + 1000 0000 = 1 0000 0000 (截取低八位为0)

乘法

无符号数的乘法

例如 w位的x，y
xy可能会超出w位，那么结果就是取截低w位
x y = x * y mode 2^w (取模)

有符号数的乘法

无论是无符号数的乘法，还是有符号数的乘法，运算结果的位级表示都是一样的
x y = U->T(x y mode 2^w) (取模之后再转化为有符号数)
对于位模式相同的数相乘，乘积结果的位级表示可能不同，但是最后截断的结果的位级表示是相同的
例如 101(5) 011(3) = 001 111 -> 111(7)
101(-3) 011(3) = 110 111 -> 111(-1)
对于C语言来说，乘法可以转化为移位运算
乘以2的幂: 111 2^2 = 11100 相当于左移了两位, x2^k => x << k
乘以14: 14(0000 1110) x = (2^3 +2^2 +2^1) x => (x<<3) + (x<<2) (x<<1) 或者>(16-2)*x = (x<<4)-(x<<1)

除法

无符号数除法就是对应的右移操作，对于有符号数采用算数右移，无符号数采用逻辑右移，除法得到的结果总是向0舍入
有符号数(补码)的除法,当补码的最高位为1时，右移结果就和无符号数一样的，对于负数来讲:
例如:-12340 右移不同位数:

k位	-12340	浮点数结果	整数jieguo
0位	1100 1111 1100 1100	-12340.0	-12340
1位	1110 0111 1110 0110	-6170.0	-6170
4位	1111 1100 1111 1100	-771.25	-772(向下舍入)/-771(期望)
8位	1111 1111 1100 1111	-48.203125	-49(向下舍入)/-48(期望)
需要加入偏置来修正不合适舍入
偏置(2^k-1)，只有负数有偏置
对于x/2^k:
x < 0 : x = x + 2^k - 1, x >> k
x > 0 : x >> k

2.4 浮点数

总的浮点数表示方法是

$float=(1+\frac{M}{2^{23}}）2^{E-127}$

$double=(1+\frac{M}{2^{52}}）2^{E-1023}$

含有小数值的二进制数

小数点左边的是2的正幂，右边是2的负幂
$2^{-1}, 2^{-2}……$
单精度float 一般是32位:最高一位s表示符号，23~30位这八个二进制位与阶码的值是相关的，剩下0~22位与尾数m是相关的
双精度double 64位: 最高位表是符号，52~62位是阶码，阶码共有11位，剩下的0~51位为小数字段

浮点数的数值

可分为三类，阶码的值决定了这个数属于哪一类

规格化的值：当阶码的值不全为0也不全为1

• 阶码部分
  最小值为1，最大值为254，用e来表示阶码的这几个二进制数，E表示阶码的值
  但是阶码的值不等于e的值，而是e的值减去一个偏置量，偏置量的值与阶码的位数相关 E = $e - bias$
  $bias(float) = 2^{8-1}-1$
  $bias(double) = 2^{11-1}-1$
  $-126 < E(float) < 127$
  $-1022 < E(double) < 1023$
• 小数部分
  小数部分的值用f表示(小数值)
  整个数字的值就是: M*2^E

	符号	阶码	小数	e	bias	E	2^E	f	M	Value
最小	0	0001	000	1	127	-6	1/64	0	8/8	8/512
	0	0001	001	1	127	-6	1/64	1/8	9/8	9/512
1	0	0111	000	7	127	0	1	0/8	8/8	1
最大	0	1110	111	14	127	7	128	7/8	15/8	240
尾数M被定义为(1+f)

非规格化的值：当阶码全为0时为非规格化

• 提供了表示0的方法
  当符号位为0，阶码字段，小数字段全为0时，此时表示正0
  当符号位为1，阶码字段，小数字断全为0时，此时表示负0
• 可以表示非常接近0的数
  当阶码字段全为0时，阶码E = 1-bias(偏置)，尾数 M = f
  整个数字的值就是: $M * 2^E$

	符号	阶码	小数	e	bias	E	2^E	f	M	Value
0	0	0000	000	0	127	-6	1/64	0	0	0
最小	0	0000	001	0	127	-6	1/64	1/8	1/8	1/512
	0	0000	011	0	127	-6	1/64	3/8	3/8	3/512
最大	0	0000	111	0	127	-6	1/64	7/8	7/8	7/512

特殊值：当阶码全为1时，可分为两类：一类表示无穷大或者无穷小，另一类表示不是一个数

阶码字段全为1，小数字段为0时，是无穷大，符号位为1时为正无穷大，符号为0时为负无穷大
阶码全为1，小数字段不为0时，不是一个数(非实数)

int 12345 0x00003039 0000 0000 0000 0000 0011 0000 0011 1001
float 12345.0 0x00e44046 0100 0110 0100 0000 1110 0100 0000 0000
两者有一段是相同的
整形转化为浮点型

int 12345 = 1100 0000 0011 1001 = 1.1 0000 0011 1001 * 2^{13}

则小数部分f为 1 0000 0011 1001

位数不够右端补零得到 1 0000 0011 1001 0000 0000 00 (float 23位，double 52位)

E = e - bias = 13 得 e = 140 = 1000 1100

浮点数为: 0100 0110 1000 0000 1110 0100 0000 0000
由于表示方法的原因，限制了浮点数的范围和精度，浮点运算只能近似的表示实数运算
对于一个浮点数，无法完全表示其精度，只能舍入到最接近的那一个
四种舍入方式:

• 向偶数舍入: 总是朝向最接近的方向舍入，对于1.5和2.5这样的，就是朝向偶数，所以结果是2。还有就是看最低有效位，如果最低有效位为偶数，则向下舍入，如果最低有效位是基数，则向上计数。
• 向0舍入: 总是朝向0的方向
• 向下舍入: 总是朝向小的方向
• 向上舍入: 总是朝向大的方向
  浮点数的加法是不具有结合性的
  例: (3.14 + 1e10) - 1e10 = 0.0 再加上1e10时对结果舍入，3.14丢失
  3.14 + (1e10 - 1e10) = 3.14
  浮点数的乘法也不具有结合性
  由于计算结果的溢出，会导致失去精度
  浮点数乘法也不具有分配律
  由于计算结果溢出

浮点数与整形之间的转换

1. int -> float 数字不会发生溢出，但是可能会被舍入，由于float小数字段为23位，可能出现无法保留精度
2. int/float -> double 由于double范围大，可以保留数值
3. double -> float (1)发生数字溢出 (2)而且float的精度较小，可能会被舍入
4. float/double -> int (1)值会向零舍入 (2)发生溢出

第三章

3.1 程序的机器级表示

gcc -Og -o prog main.c mstore.c

• gcc是linux上的默认的编译器
• Og就是告诉编译器生成符合原始c代码整体结构的机器代码,有时侯为了获取更高的性能，会使用-O1或者-O2，甚至更高的编译优化项，但是高级别优化产生的代码会严重变形
• o后面的参数prog表示可以生成的可执行文件的文件名
  在Intel x86-64的处理器中包含了16个通用目的寄存器，用于存放整数数据和指针
  %rax %rbx %rcx %rdx %rsi %rdi %rbp %rsp %r8 %r9 %r10 %r11 %r12 %r13 %r14 %r16

Callee-saved register (被调用者保存寄存器) & Caller-saved register (调用者保存寄存器)

例如，在程序A中调用了B，B被称为被调用者，A为调用者，逻辑上寄存器上的值在调用B前后应该保持一致

• 有两个策略:

1. 调用者保存，寄存器的值在调用函数中提前先保留原值，执行完函数B后，在恢复到原值
2. 被调用者保存，寄存器的值在被调用函数中先保留原值，运行程序到结束时再恢复到原值
   Callee saved: %rbx %rbp %rb12 %rb13 %rb14 %rb15
   Caller saved: %rax %r10 %r11 %rsi %rdi %rdx %rcx %r8 %r9
   这些策略都是为了提高性能

汇编后缀

表示操作数的大小

类型	汇编后缀	大小
char:	b	1
short:	w	2
int:	l	4
long:	q	8
char*:	q	8
float:	s	4
double:	l	8

• 数据传送指令
  movb: move byte
  movw: move word
  movl: move double word
  movq: move quaty word
  gcc -Og -c prog main.c mstore.c
  编译生成机器代码 (.o文件)
  objdump -d xx.o
  反汇编代码，通过命令可以查看xx.o中的相关信息，反汇编代码省略了汇编后缀，但在有些指令后面添加了汇编后缀

3.2 寄存器与数据传送指令

一般的程序中，不同的寄存器扮演着不同的角色
大部分代码包含两个部分，操作码(决定CPU执行的操做类型)和操作数(大多数指令都具有一个或者多个操作数)

符号扩展位传送指令

s是sign的缩写,最后两个字符也是大小指示符
movsbw movsbl movswl movsbq movswq movslq cltq = moveslq
一般的内存引用包括 4 个部分

1. 立即数
2. 基址寄存器
3. 变址寄存器
4. 比例因子，也就是申请的数组的元素大小

有效地址就是 $立即数 + 基址寄存器 + 变址寄存器 * 比例因子$

3.3

%rax 64
%eax 32
%ax 16
%al 8
其实是同一寄存器对不同数位的元素处理的操作

3.4

一元操作指令
只有一个操作数，既是源操作数，也是目的操作数
inc D D+1 increment(加1)
dec D D-1 decrement(减1)
neg D -D Negate(取负)
not D ~D Complement(取补)

二元操作指令
第一个操作数是源操作数，可以是立即数，寄存器，内存地址
第二个操作数既是源操作数，也是目的操作数，可以是寄存器，内存地址
ADD S,D D+S 加
SUB S,D D-S 减
IMUL S,D D*S 乘
XOR S,D D^S 异或
OR S,D D|S 或
AND S,D S&D 与

其他操作指令
imulq s 有符号全乘法
mulq s 无符号全乘法
cqto 转换为八字
idivq s 有符号除法
divq s 无符号除法

3.5

条件码寄存器
条件码寄存器是由CPU来维护的，长度是 单个比特位，描述了最近执行操作的结果的属性，会被下一条指令覆盖
常用的条件码
CF Carry Flag (进位标志) 可以检查无符号数操作的溢出
ZF Zero Flag (零标志) 当最近操作结果为0时，会被置1
SF Sign Flag (符号标志) 当最近操作结果小于零时，会被置1
OF Overflow Flag (溢出标志) 针对有符号数，出现正溢出和负溢出都会被置1

条件码寄存器的值是由ALU在执行算数和运算指令时写入的，上面操作指令都会改变条件码寄存器的值，ALU运算结束后会改变目的寄存器的值
cmp 和 test 指令都会设置条件码寄存器
cmp 根据两个操作数的差来设置条件码寄存器，但是只能设置条件码寄存器，不会更改目的寄存器的值
test 和 and 指令类似，只设置条件码寄存器，不改变目的寄存器的值
条件码的使用
例如:
判断 a < b -条件> SF ^ OF (异或)
case a < b t < 0 SF = 1 SF ^ OF = 1
case a > b t > 0 SF = 0 SF ^ OF = 0
case a < b t < 0 a = -2 b = 127 SF = 0 OF = 1 SF ^ OF = 1
case a > b t > 0 a = 1 b = -128 SF = 1 OF = 1 SF ^ OF = 0

其他比较运算也能通过条件码表示

$$> D <- ~(SF^OF)&~ZF = D <- ~(SF^OF) < D <- SF^OF <= D <- (SF^OF)|ZF >$$

3.6

在执行 if-else 和 while ,for ,switch 语句时，都会执行跳转，跳转指令比传送指令要快一点
while 和 for 循环语句只是在跳转指令不同，其他地方都一致
switch 跳转时，会生成一个链表，会把多种跳转形成一个表，把跳转表声明为长度为情况数量的数组，而且执行时间与 case 的数量无关

3.7

例如，函数P调用函数Q，函数Q执行完之后返回函数P
当函数Q正在执行时，函数P以及相关调用链上的函数都会被暂时挂起
栈帧
当函数执行所需要的存储空间超出寄存器所能存放的大小时，就会借助栈上的存储空间，这部分空间就是 栈帧，
当函数P调用函数Q时，会把返回地址压入栈中，该地址就是当函数P执行完之后，返回P函数该从那个位置开始执行，
这个操作不是由 push 执行的，而是函数调用指令 call 来执行的
参数传递 : 当一个函数的参数 (形参) 数量大于 6 时，超出的部分就要通过栈来传递，前 6 个参数的传递可以使用对应的寄存器来传递
当n非常大时，不建议使用递归调用函数

3.8

指针就是地址的抽象表述
不同类型的指针在进行加法运算时，运动的内存字节数也是不同的，运算时，会对指针相应的类型进行伸缩
嵌套数组
对于二维数组，在内存中存放是按照行优先的规则的
$\&D[i][j] = D + L(c*i+j)$
L 就是数组元素类型的大小
可以申请变长度数组:

long var_ele(long n, int A[n][n],long i,long j )
{
    return A[i][j];
}

3.9

结构体中的元素的存储顺序是从上到下的，按声明的顺序
为了提高内存系统的性能，系统对于数据存储的合法地址做出了一些限制，例如 int 类型是4个字节，那么它的起始地址必须为4的整数倍，会对之前空缺的进行补齐
数据存储的原则: 对于任何 k 字节的数据，它的存储起始地址必须是 k 的倍数
结构体中的对齐要求: 结构体需要补充为字节数最多的元素类型的整数倍
在结构体的末端也可能需要对齐操作来填充

联合体
两个字段的使用是互斥的，就可以把这两个字段声明为一个联合体
联合体的大小就是联合体中最大元素的大小

在声明二叉树的时候，可以使用联合体，因为不会同时使用两个树叶，可以节省一半的空间，把同一树枝上的树叶声明为一个联合体
但是不能分清楚一个结点时叶子结点还是内部节点，
解决: 引入一个枚举类型，然后创建一个结构体，结构体包含一个标签和一个联合体

typedef enmu{N_LEAF, N_INTERNAL} nodetype_t;
struct node_t
{
    nodetype_t type;
    union
    {
        struct
        {
            struct node_t *left;
            struct node_t *right;
        }internal;
        double data[2];
    }info;
}

3.10

缓冲区溢出，就是后面输入的元素数量太多而把栈中后面的数据覆盖，导致程序运行错误，甚至会把 return 函数的返回内容覆盖
应对缓冲区溢出的方法

1. 栈随机化
   栈的位置在程序每次运行时都会有变化，地址空间分布随机化， ASLR
   每次运行时，程序的不同部分会被加载到不同的区域
2. 栈破坏检测
   编译器会在产生的汇编代码中加入一个栈保护者的机制来检测缓冲区越界，就是在缓冲区与栈保存的状态值之间存储一个特殊值，这个特殊值是程序运行时随机产生的，在函数返回之前检测特殊值是否被修改来判断是否遭受攻击，而且特殊值声明的时候被定义为只读
3. 限制可执行代码区域
   可以把栈标记为 可读可写但是不可执行 来防止外来插入的代码执行

第四章

4.1

指令系统结构
是计算机软件和硬件的交互接口
一个简单的指令系统 Y86

• 各种状态单元
• 指令集及它们的编码
• 编程规范
• 异常事件处理

程序员的可见状态
这里的程序员不仅包括写程序的人，也包括编译器，可见状态就是指每条指令都会区读取或者修改处理器的某些部分
寄存器 %rsp 定义为栈指针，其他的寄存器没有固定的含义
程序计数器 PC 就是用来存放当前正在执行指令的地址
状态码 stat 程序的执行状态

4.2

硬件描述语言

• Verilog
  Verilog 语言是并行执行的
  C语言程序是串行执行的

1. assign 用于描述组合逻辑
2. always @(posedge clock) 用于描述时序逻辑， posedge clock 表示在始终上升沿的时候变化
3. 模块调用语句

• VHDL
  VHDL主要用于描述数字系统的结构，行为，功能和接口。

4.3

实现所有 Y86-64 指令所需要的计算可以被组织为 6 个基本阶段

1. 取指阶段
2. 译码阶段
3. 执行阶段
4. 访存阶段
5. 写回阶段
6. 更新PC

4.5 流水线

延迟就是一条指令从开始执行到结束所需要的时间，通常单位是 ps(皮秒)
单位时间内执行的指令数目被称为吞吐量
在使用流水线之前，程序是按照一条接着一条执行的
使用流水线之后可以使程序在执行某一条指令的中途执行下一条指令，原理是调用多个寄存器共同工作，会提高系统的吞吐量，但是会轻微增加延迟
把计算过程分成更多的阶段时，系统的吞吐量也就提高了，但是会导致系统性能的下降

4.6 流水线的硬件结构

1. 取指阶段，将程序计数器PC的值作为地址，从指令内存中读取指令字节，第一个字节分成两部分，分别是指令代码icode和指令功能ifun，指明一个或者两个寄存器指示符(rA,rB)，还可能含有一个8字节的常数valc，pc增加器用来计算下一条指令的地址valp
2. 译码阶段，一次译码可以同时读出两个寄存器的值，寄存器文件的读出端口与算术逻辑单元ALU的输入相连接
3. 执行阶段，ALU会根据指令功能来执行指定的运算，从而得到运算结果valE，同时设置条件码寄存器CC，对于跳转指令，在执行阶段会根据条件码和跳转条件来产生信号Cnd
   在这些阶段中，ALU不仅要实行算数逻辑指令，还要计算访存的有效地址以及针对栈指针的运算(加8和减8操作)，因此ALU的输出端口会与数据内存的地址逻辑单元相连
4. 对于访存阶段，可以将数据写入内存或者从内存中读取数据，写入的数据可以是寄存器文件，也可以是指令中的常数字段
5. 写回阶段，ALU的计算结果可以通过E端口写回到寄存器文件，端口M与数据内存的输入端相连，从内存中读取的数据可以从M端口写回到寄存器文件

6. 更新PC的值，需要根据当前执行的指令和执行的状态来判断，如果是跳转指令，需要根据条件判断是否跳转，还有返回指令，是否产生异常信号

   

电路重定时改造，只改变系统的状态表示，并没有改变系统的逻辑行为

电路重定时retiming：一种时序优化技术，用在不影响电路输入/输出行为的情况下跨组合逻辑寄存器从而提高设计性能。

目的：Retiming就是重新调整时序，例如电路中遇到复杂的组合逻辑，延迟过大，电路时序不满足，这个时候采用流水线技术，在组合逻辑中插入寄存器加流水线，进行操作，面积换速度思想。

原理：任何的数字电路都可以等效成组合逻辑加D触发器打拍，两个D触发器之间的组合逻辑路径决定了，系统的工作频率，决定芯片的性能。所以为了提高芯片的工作频率，使用流水线技术在组合逻辑中插入寄存器。插入寄存器的位置需要慎重选择，不同的位置数据的打拍所消耗的寄存器的数量也不同

改造步骤，只需要在顺序阶段中的各个阶段之间插入流水线寄存器，然后对信号进行重新排列，就可以得到流水结构

4.7 数据冒险

对于流水线中，比如下面的栗子，流水线中的指令执行顺序必须按照FDEMW顺序执行，所以会出现数据冒险和控制冒险等问题

对于这些指令不具有相干性的，可以按照这样的顺寻执行

但是对于指令存在相关性的，按照这样的顺序执行的话，就会出现错误，原因是，寄存器内的数值改变在写回阶段才会赋值，而提前取指的话，就会得到寄存器的默认值0，出现错误的计算结果，这被称为冒险/冲突

为了解决这种问题，就需要比较后面指令的源寄存器ID与先前指令的目的寄存器ID是否匹配，不匹配的话就可以继续执行，否则需要执行以下方法

1. 解决数据冲突的方法就是在addq的指令执行阶段延迟，可以在decode译码阶段插入几段气泡来延迟后面的执行，一直到irmovq指令完成写回操作。但是这种暂停会导致流水线的执行效率降低。频繁暂停指令的执行会降低流水线的吞吐量
2. 数据转发/旁路，例如上面的例子，可以把movq的执行结果直接转发到addq的译码阶段，需要在计算机的硬件部分增加一些额外的数据连接和控制逻辑，只能在译码阶段读取到转发的数据

但是对于内存的操作，需要从内存中读取数据，就是在memory（访存阶段）的时候才能把数据转发到下一条指令中，所以下一条指令就必须暂停一下，来获得转发的数据

4.8 控制冒险

出现原因

1. 对于流水线，每一个时钟周期内，都要保证每一个阶段都有指令执行，所以就必须在下一条指令执行之前找到该指令的地址，一般来说都是满足情况的，但是对于 ret 指令，必须在访存操作结束之后才能确定下一条指令的地址
2. 当取到的条件是分支条件指令的时候，流水线无法立即判断是否要进行跳转操作，需要经过执行阶段之后才能够确定是否跳转

解决

1. 对于ret导致的数据冒险，可以在执行过程中插入气泡，暂停程序的执行，一直到执行完访存操作才能确定下一条指令的地址，继续执行
2. 对于分支条件指令，可以分支跳转预测，在一开始就规定是否跳转，但是分支预测的准确性对程序的性能有很大的影响，主要是出现预测错误需要采取相应的措施来处理

分支预测

PC预测逻辑单元，预设分支总是跳转的或者总是不跳转的，但是分支预测的准确性对程序的性能有很大的影响，主要是出现预测错误需要采取相应的措施来处理。插入气泡，但是这个里的插入气泡相当于是把这两条指令剔除了，会造成时钟周期的浪费

PC选择逻辑单元指令纠错单元，如果PC预测逻辑单元出错了，PC选择逻辑单元会根据实际的执行情况来改正预测错误。

暂停和插入气泡的实现

操作系统中有流水线寄存器，并且每次在时钟周期的上升沿都将输入作为输出输出出来，并且引入了两个信号量，暂停信号和气泡信号，并且初始值都为0

当执行暂停操作时，流水线寄存器中的暂停信号置位1，流水线寄存器保留数值不变，流水线运行阻塞

当执行气泡操作时，流水线寄存器中的气泡信号置位1，流水线寄存器数值保持为某个复位配置相当于nop

4.9 Y86-64流水线的实现

1. 取指阶段

   最复杂的地方就是下一条指令的地址：一般是顺序执行和跳转执行

   • 顺序执行：根据当前指令地址和当前指令的大小来预测下一条指令的位置
   • 跳转执行：做出一个假定的预测——分支预测策略
   • ret：返回指令的下一条指令地址从栈中取出，不会对返回地址做预测，采用和顺序执行一样的逻辑来处理执行

2. 译码阶段

   根据寄存器的ID从寄存器文件中读取地址，寄存器ID由字段 rA，rB 提供，通过srcA和srcB 输入到寄存器文件，最终译码出来可以用valA和valB来表示。可以用数据转发，就是不必等待寄存器写回到寄存器文件中再从中读取，而是可以直接使用寄存器的数值

   需要判断是直接采用转发的数据还是从寄存器文件中读取数据，依据是当前需要读取寄存器的ID值与转发的目的寄存器是否相等，转发源：

   1. ALU产生的输出结果，正常流程是再访存和写回之后才能完成寄存器的更新，采用数据转发，ALU的输出结果可以马上作为译码阶段的结果
   2. 内存的输出数据
   3. 是写入阶段时，对寄存器端口E还没有进行写入的数据
   4. 写回阶段时，对寄存器写入端口M还没有进行写入的数据

   5. 写回阶段时对寄存器写入端口E还没有进行写入的数据

      每个转发源有两个部分，一部分是寄存器的ID值，另一部分是转发数据。转发源是存在优先级的，执行→访存→写回

4.10 流水线的控制逻辑

为了避免冒险，需要在设计中添加控制逻辑单元

指令执行中出现的特殊情况

1. 加载/使用冒险 就是数据/控制冒险
2. 分支预测错误
3. 返回指令的处理
4. 对异常的处理

第五章

5.1 优化程序性能

编写高效的程序：

1. 选择适当的算法和数据结构
2. 理解器的能力和局限性
3. 探索并行化

妨碍优化的因素：

1. 不确定的指针
2. 函数调用

5.2 优化程序性能

减少函数的调用可以提升程序的性能

降低函数调用的开销

消除不必要的内存引用

5.3 现代处理器

指令级并行的实现

整体设计分为两部分

1. 指令控制单元 ICU
2. 执行单元 EU

从内存中读取指令序列，然后对指令进行译码

现代处理器可以把一条指令中的多个操作分别给不同的元件取执行，节约运行时间。现代处理器每个时钟周期可以执行多个操作，而且可以是乱序执行的

现代处理器采取的分支预测技术来预测分支并且可以预测分支的目标地址，甚至在不确定分支结果的时候就可以提前运行选择的分支，如果发现分支预测错误，就会将状态重置到分支点之前的状态，开始执行另外一个方向上的指令——投机执行。执行结果暂时不会放到寄存器文件或者内存中，直到确认应该执行这些指令时再把结果写回到寄存器或者内存中。预测错误执行单元会丢弃分支点之后计算出来的结果，执行单元还会告诉分支单元，并且指出正确的分支，此时分支逻辑单元开始在新的位置取指

在指令执行单元中，退役单元，包含寄存器文件，同时控制寄存器的更新，指令在译码时，指令的相关信息被放置在一个先进先出的队列中，这些信息会一直保存在队列中，直到

1. 当一条指令完成了，并且所有引起这条指令得到分支点也都被确认预测正确，指令就可以退役了，可以更新寄存器
2. 引起该指令的某个分支点预测错误，指令会被清空，丢弃所有计算出来的结果

通过这种处理方式，即便是预测错误也不会对计算机造成影响

5.4 数据流图

• 延迟界限：在下一条指令开始之前，这条指令必须结束
• 吞吐量界限：处理器功能单元的原始计算能力

存在四种类型的寄存器

1. read-only 只读寄存器
2. write-only 只写寄存器
3. local 局部寄存器
4. loop 循环寄存器

一个循环程序在不断运行的过程中，会不断的对数据进行读取和写入操作，导致程序运行速率降低

5.5 循环展开

可以减少一些与程序结果无关的操作，能够减少整个计算中关键路径的操作数量，减少一写延迟等待，在循环展开之后，运算过程可以调用多个寄存器来实现运算，减少延迟等待

但是当循环展开到一定的极限的时候就会受到吞吐量界限的限制从而程序的性能下降

5.6 理解内存性能

现代处理器中有16个寄存器用来保存浮点数，一旦在一次使用中超出了这个界限，就会分配一些栈空间用来存储存储数据，就会带来内存读写的开销

• 加载操作：将数据从内存中读取到寄存器中
• 存储操作：将数据从寄存器保存到到内存中，不会影响任何寄存器的值，存储操作不会产生数据相关

写读相关会导致处理速度下降，因为如果写入和读出的地址是同一个，读取数据依赖于写入数据之后，就会产生延迟

对于寄存器的操作，在指令被译码成具体的操作的时候，处理器就已经能判断哪些寄存器出现了相关操作，但是对于内存操作，只有把具体的地址计算出来才能判断是否出现了相关操作

提高程序运行性能的方式

1. 针对具体的问题选择合适的算法和数据结构
2. 遵循一些基本的编码原则，比如消除连续的调用和消除不必要的内存引用
3. 根据硬件的设计，利用循环展开等技术来提高指令级并行

第六章 存储技术

存储类型	速度
寄存器	立即使用
chche 告诉缓存	4~75时钟周期
内存	几百个时钟周期
磁盘	几千万个时钟周期

RAM 随机访问存储器

需要在有电的情况下才能保存数据

• static RAM 静态

  将每个bit位的信息存储在一个双稳态的存储器单元内，每个存储器单元需要6个晶体管来实现，只要有电就能一直存储原来的数据

• dynamic RAM 动态

  存储的原理是电容充电，每个bit位存储对应一个电容和一个晶体管，这个电容很小，对干扰十分敏感，并且电容电压受到干扰之后无法回到之前

  会有很多原因导致漏电，使得DRAM会在10~100ms内失去电荷，因此内存系统需要不断地读出数据然后重写来刷新内存中地每一位

  同步DRAM比异步DRAM更快

两种结构不同，导致速度存在差异，SRAM速度要快于DRAM，但是价格更贵

处理器芯片中的cache采用的是SRAM，内存采用的是DRAM

一个用DRAM封装成地内存模块的基本组成是由 8 个DRAM芯片组成的，每个DRAM中有8M的内存，每个超单元可以存储8位的数据，每个 64 位的数据使用 8 个超单元来存储，但是这8个超单元并不存在于同一个DRAM芯片上，其中最低8位存储在DRAM0，以此类推直到DRAM7存储最高8位数据，当处理器向内存控制器发起读取数据的请求时，内存控制器将地址转换成超单元地址（i， j），然后发送到内存模块，然后内存模块将超单元地址广播到所有的DRAM中，然后每个DRAM会输出它对应的超单元的数据，最后内存模块将所有的超单元合并为1个64位的数据输出到内存控制器

机械磁盘

依靠盘片来存储数据，盘片表面涂有磁性的记录材料，主轴带动盘片高速旋转

对于SRAM和DRAM之类的

$K=2^{10}$ $M = 2^{20}$ $G = 2^{30}$ $T = 2^{40}$

对于磁盘之类的IO设备

$K=2^{10}$ $M = 10^{6}$ $G = 10^{9}$ $T = 10^{12}$

对于磁盘扇区的访问的时间 = 寻道时间 + 旋转时间 + 传送时间

• 寻道时间

  传动臂将读写头移动到目标扇区所在的磁道所用的时间，取决于当前位置与目标位置的距离

  通常时间 3~9ms 左右

• 旋转时间

  决定因素：

  • 当前读写头所在的扇区位置与目标扇区位置
  • 盘片的速度

• 传送时间

  传送数据的时间

对于操作系统来说，整块磁盘被抽象成一个个逻辑块序列，与磁盘上的块区都是512字节，磁盘内有一个小块的磁盘控制器，它维护着逻辑块号与实际磁盘扇区之间的映射关系，当操作系统需要从磁盘中读取数据时，就会发送一个命令到磁盘控制器，就是让磁盘控制器读取特定逻辑块号的数据，用（盘面，磁道，扇区）的三元组来表示一个唯一的物理扇区，然后读写头把读到的数据放入一个缓冲区中，最后将目标数据复制到内存里

固态硬盘

是由一个或者多个闪存芯片组成的，还包含一个闪存转换层，功能与磁盘控制器类似，都是将操作系统对逻辑块的请求翻译成对底层物理设备的访问

固态硬盘内存操作包括 读写和擦除

闪存芯片是基于 nand flash 实现的

每个闪存芯片是由一个或者多个 die 组成的，每个 die 可以分为多个 plane ，每个 plane 包含多个 block ，但是这个 block 与逻辑块是没有关系的，其中又被分为了多个 page，固态硬盘就是以 page 为单位读写的，对于不同规格的闪存芯片，其中 page 的大小可能并不相同。

由于闪存芯片的写入原则，导致每次写入只能从 1 变为 0，所以page在读写之前存储位为1，写入相当于是将某些存储位从1写为0，并且在写入之前，page 必须擦除，不能直接覆盖，写入操作的基本单位是 page，但是擦除操作的基本单位是 block，本质就是将所有的存储位都变为1，经过多次擦除操作之后，block就会磨损，直到block发生损坏之后就不能再使用了，所以对于闪存翻译层会使用磨损平均算法，将擦除平均到所有的块上来最大化每个块的寿命

应用程序的局部性

• 时间局部性

  对于一个内存被引用了一次，程序很可能在不远的将来再次引用这个内存

• 空间局部性

  对于一个内存被引用了一次，程序很可能在不远的将来再次引用这个内存附近的内存

对于一个二维数组，内存中的存储是按照行优先的顺序来存储的，如果代码中引用顺序一致的话速率就会比较高（空间局部性）

存储器层次结构

中心思想是，速度更小，容量更小的存储设备作为速度更慢，容量更大的存储设备的缓存

在层次结构中，数据总是以块为单元在相邻的块之间复制，对于相邻层块的大小是固定的，但是对于不相邻层块的大小是不固定的，一般来说距离CPU越远得到设备访问时间就越长

随着CPU与内存之间的性能的差距加大，在内存和寄存器之间又插入了一些缓存

缓存命中

对于读取第 K+1 层中的数据，会先查看第 K 层中是否有该数据的缓存，如果有就是缓存命中，如果没有目标数据就是缓存不命中，那么第K层就会读取第K+1层中包含目标数据的块，如果第K层已经满了，这个块就会覆盖现存的一个块，这个过程被称为替换，被替换的块成为牺牲快，常用替换方式有随机替换和LRU（淘汰最少使用的存储块）

整个cache被划分为一个或者多个 set ，每个set包含一个或者多个cache line（高速缓存行），每个cache line由3部分组成，分别是有效位，标记，数据块，有效位来标记数据是否有效，cache的大小是所有数据块的和，不包括有效位和标记。

当从cache中读取数据时，CPU将地址发送到 cache中，如果cache中保存着目标数据的副本，就立即将目标数据发回CPU

对于cache中如果每个set中只有一个cacheline的话，就将这种结构的cache成为直接映射

判断是否缓存命中的步骤

1. 组选择

   根据组索引值来确定目标数据属于哪一个set的

2. 行匹配

   先查看有效位是否置1，再对比cacheline中的标记与地址中的标记位是否一致，如果一致就是在当前的cacheline中，如果不一致或者cache时无效的表示数据不存在于cacheline中

3. 字抽取

   行匹配如果命中就可以进行，可以通过目标偏移量来确定数据的位置，以字为单位的偏移

如果没有命中就需要读取下一层的内存了，对于直接映射的 cache 来说，直接将当前的cacheline的行替换掉就可以了

冲突不命中

对于不同的块有可能对应着同一个set，所以在交替引用之下会产生数据不命中的结果

组相联 全相连 cacheline

组相连 每个set中的cacheline数量>1

1. 组选择

   根据组索引值来确定目标数据属于哪一个set的

2. 行匹配

   遍历每一行cacheline，寻找有效位为并且标签匹配的cacheline

3. 字抽取

   行匹配如果命中就可以进行，可以通过目标偏移量来确定数据的位置，以字为单位的偏移

如果没有命中就需要读取下一层的内存了，必须在组中选择一行来覆盖，如果有空行就填入空行中，否则就需要覆盖掉一行，可以使用LFU策略，LRU策略或者随机替换

• LFU 最不常使用的行
• LRU 最后一次访问时间最久远的行

全相联 只有一个set，所有的cache都包含在内

不需要组索引来进行组选择了，地址只需要为标记和块偏移就可以

只适合做容量较小的高速缓存

写入

当向cache中写入数据的时候需要考虑写命中和写不命中的情况

• 写命中 找到了对应的cacheline

  • 写穿透

    CPU在写cache的同时写内存，保证数据永远是新的，cache替换时直接扔掉旧数据
    

  • 写回

    只写cache，不写内存，比较省事，当更新算法要驱逐这一块内存的时候再写入内存中
    
    但是会增加cache的复杂性，cache需要有一个标志位来记录是否被修改过
    

• 写不命中 没有找到对应的cacheline

  • 写分配

    就是先把目标数据所在的块从内存加载到cache中，再往cache中写，通常与写回搭配
    

  • 写不分配

    绕开cache，直接把要写的内容写到内存里，通常与写穿透搭配
    

容量较大的cache可能会提高命中率，但是运行后速率慢，较大的cache可能会增加命中的时间

数据块较大能利用程序中可能存在的空间局部性，帮助提高命中率，但是相应的cache的行数就少，会导致一些时间局部性较好的代码命中率下降，而且块越大，导致的不命中处罚也就越严重，对于数据传送时间会比较长

第七章 编译器

7.1 编译器驱动程序

链接

是将各种代码和数据收集并组合成一个文件的过程，最终得到的文件可以被加载到内存中执行，早期链接是手动执行的，现在链接是由链接器自动完成的

编译的流程

预处理→编译→汇编→链接

加载→执行

7.2 可重定位目标文件

查看操作系统的笔记

7.3 符号和符号表

7.4 符号解析与静态库

在linux系统种，静态库以一种成为archive的特殊文件格式存放在磁盘上，以.a 结尾，是一组可重定位的目标文件的集合，可以通过 objdump -t libc.a 来查看这个静态库包含哪些目标文件，也可以使用 ar 指令解压该静态库

ar指令的使用：

• -r 将objfile文件插入静态库尾或者替换静态库中同名文件
• -x 从静态库文件种抽取目标文件
• -t 打印静态库的成员文件列表
• -d 从静态库种删除目标文件
• -s 重置静态库文件索引
• -v 显示详细信息
• -c 创建静态库文件

7.5 静态库的解析过程

在符号解析阶段，链接器从左到右按照命令行种出现的顺序来扫描可重定位文件和静态库文件

其中由于编译器驱动程序总是会把libc.a传给链接器，所以不必显式声明

链接器会维护三个集合

1. 集合E 在链接器扫描的过程中发现了可重定位目标文件就会放到这个集合中，链接即将完成之时，这个集合中的文件最终会被合并起来行程可执行文件
2. 集合U 用来存放未定义的符号
3. 集合D 它是用来存放输入文件中已经定义的符号

链接开始时，三个集合都为空，对于命令行上每一个文件，链接器会判断，如果文件是一个目标文件，那么链接器就会把文件添加进集合E中，同时修改集合U和D来反映文件中的符号定义和引用，如果文件是静态库文件，链接器就会尝试在这个静态库文件中寻找集合U中未解析的符号，如果找到了就将该.o文件放入集合E中，并且从集合U中移除，如果其中还定义了其他符号，就添加到集合D中，直到EUD不再发生变化，最后不在E中的目标文件将会被丢弃。操作完成之后，如果集合U是空的，链接器会合并集合E中的文件来生成可执行文件，如果U是非空的，链接器就会输出一个错误并且终止。但是这会导致一些链接错误，因为目标文件和库文件的输入顺序就很重要。如果把一些静态链接库放在前面，U中一开始是空的，就不会对任何符号引用解析，所以直到结束之后会发现有一些符号未定义。并且如果库不是独立的，那就必须对它们进行排序（调用者放前面），也可以重复库，也可以把它们合并成一个静态库文件

7.6 重定位

分为两步

1. 重定位节和符号定义

   链接器将可重定位目标文件中的 text section 合成为一个新的 text section ，合成之后的 text section 就是可执行目标文件的 text section，完成之后程序中的每条指令和全局变量都有了唯一的运行时内存地址

2. 重定位符号引用

   对于函数调用，会有call指令，一开始指令的最终地址是不确定的会先填充0，链接器需要修改对函数符号的引用，使它指向正确的运行地址，链接器还依赖于可重定位条目的数据结构

重定位条目

可重定位目标文件是由汇编器产生的，当汇编器在生成可重定位目标文件时，并不知道数据和代码最终放在内存的那个位置，也不清楚全局变量和外部函数的位置，对于最终位置不确定的符号就会产生一个重定位条目，用来告诉链接器在合成可执行文件时应该如何修改这个引用，代码的重定位条目放在 .rel.text 中。对于已初始化的重定位条目放在 .rel.data 中

重定位条目的结构体定义

typedef struct {
 long offset; // 表示被修改的引用的节偏移量
 long type:32, // 链接器会根据type来修改新的引用
    symbol:32;// 表示被修改的引用是哪一个符号
 long addend; // 一个常数，一些类型的重定位要使用它对被修改应用的值做偏移调整
}ELF64_Rela;

定义了32中重定位类型，一般只关心PC相对地址重定位(R_X86_64_PC32)和绝对地址重定位(R_X86_64_32)

ref_addr = ADDR(main) + r.offset // 重定位的绝对地址，引用时地址
*ref_ptr = ADDR(func) - ref_addr + r.addend // 更新符号引用，使得运行时指向对应的函数
// addend 字段默认为 -4 其实是执行到跳转指令的时候，PC已经到达下一条指令的位置了，所以需要用到算数回调

• 重定位相对引用

  其中的偏移调整值 addend 是默认为-4的，因为当执行当前指令时，PC的实际地址是指向了下一条指令

  执行call指令可以分为两步

  1. 将PC值压入栈中
  2. 修改PC数值，在PC数值上加上偏移量

• 重定位绝对引用

  对于绝对地址引用的计算比较简单， addend 默认为0

重定位之后，对应的符号重定位地址都会被更新，执行完重定位之后，可以确定目标文件的 text section 和 data section 的内容，当程序执行加载的时候，会把这些 section 中的字节都复制到内存里，不用修改就可以执行

7.7 可执行目标文件

第八章 异常

8.1 异常控制流

控制流

是一个PC的运行序列

平滑控制流是指运行的地址都是连续的，如果其中产生了突变，也就是程序的运行地址不相邻了，通常是由跳转，函数调用和返回这类指令造成的。这种突变属于是必要的机制，但是系统在运行的过程中需要对系统状态的变化做出反应，这种就是异常控制流

软件异常允许程序进行非本地跳转来响应错误。非本地跳转指的是违反通常的调用/返回栈规则的跳转，是一种应用层的异常控制流，可以通过函数 setjmp 和 longjmp 来实现

异常

当处理器正在执行应用程序中的某一条指令的时候，系统发生一个事件，可能与当前程序的执行相关（程序错误），也可能不相关（IO请求），然后处理器从执行应用程序切换到异常处理程序，异常完成之后，根据引起的异常的类型选择是否返回。处理异常需要软硬件的配合

系统为每种类型的异常都分配了唯一的异常编号，有些是由处理器的设计者分配的，其他的是由操作系统内核的设计者分配的。处理器在得到异常编号的时候，会在异常表中查找到异常处理程序的入口来处理异常。异常表是在系统启动时分配和初始化的一个跳转表，异常号就是这个跳转表的索引号。异常表的起始地址是保存在CPU的一个特殊的寄存器（异常表基址寄存器）中。异常的处理类似一个间接的函数调用。

函数调用时，在跳转到目的函数之前，处理器首先将返回地址压入栈中。根据异常的类型，返回地址要么是当前指令要么是下一条指令。当处理异常时，会把处理器额外的一些状态压入到栈中，当重新开始这段程序时需要这些状态。控制从用户态转向内核态时，所有的内容都要被压入到内核栈中而不是用户栈中。异常处理程序是运行在内核态的，对所有的系统资源都有访问权限

根据异常的事件类型，发生3种情况

• 异常处理程序将控制返回到之前正在执行的指令
• 异常处理程序将控制返回到没有发生异常将要执行的下一条指令
• 异常处理程序终止之前CPU正在执行的程序

8.2 异常（Linux异常表）

1. 中断

   异步⇒ 由处理器CPU外部的IO设备产生的

   

2. 陷阱

   同步⇒ CPU执行当前指令产生的结果

   故意触发，是执行一条指令的结果，为用户程序和操作系统内核之间提供一个类似函数的接口。陷阱就是由 syscall 产生的

   

3. 故障

   同步⇒ CPU执行当前指令产生的结果

   是由错误情况引起的，有可能被故障处理程序修复

   如果修复，就返回引起故障的指令重新执行，否则终止运行

   

4. 终止

   同步⇒ CPU执行当前指令产生的结果

   是由一些不可恢复的错误导致的，通常是硬件错误

   

8.3 进程与上下文

逻辑控制流

PC在程序运行时有一系列的程序计数器的数值，与可执行程序中的指令是一一对应的，把这个PC值的序列叫做逻辑控制流。一个处理器上可以有多个进程，时间片轮转→每个进程轮流占用CPU。把两个在时间上重叠的情况称为并发流，两个流的执行被成为并发运行。

并发是交替运行

并行是同时运行

为了限制应用程序执行某些特殊指令以及限制可以访问的地址空间范围，通常处理器通过控制寄存器的模式位来实现这些限制功能。该寄存器描述了当前进程的权限，设置控制寄存器的模式位之后，进程就运行在内核模式。运行在内核模式的进程可以执行指令集中的任何指令，访问系统中任意内存位置。否则就运行在用户模式，不允许执行特权指令。特权指令可以停止处理器，改变模式位以及发起一个IO操作。用户模式的进程也不能直接引用内核区域的代码和数据，入如果试图访问内核区域会导致保护故障然后终止运行，但是可以通过系统调用间接的访问内核的代码和数据。

一般来说，应用程序一开始运行在用户模式下的，进程从用户模式切换到内核模式需要通过中断，故障或者系统调用，当这类异常发生时，执行异常处理程序处理异常，处理器的模式会从用户模式，当返回应用程序继续执行时，会从内核模式返回到用户模式

上下文

上下文就是内容重新启动一个被抢占的进程所需的状态

组成：

• 通用目的寄存器
• 浮点寄存器
• 程序计数器
• 用户栈
• 状态寄存器
• 内核栈
• 各种内核数据结构：描述地址空间的页表，有关当前进程信息的进程表，进程已打开文件的信息表

进程调度：进程执行的某些时刻，内核可以决定抢占当前的进程，然后重新开始执行先前被抢占的进程，由内核中的调度器来执行。当内核调度了一个新的进程运行后，它就抢占当前进程，并使用上下文切换的机制来将控制转到新的进程

上下文切换

1. 保存当前进程上下文
2. 恢复某个先前被抢占的进程的上下文
3. 将控制传递给这个新恢复的进程

系统调用和中断会引发上下文切换

8.4 进程的创建

程序：一段代码和数据，执行之前以文件得到形式存储在磁盘上，运行时，程序以段的形式存储在内存的地址空间中

进程：正在执行中程序的一个具体的实例

从程序员角度来看，状态

1. 运行 要么在CPU上运行，要么等待被执行，最终会被内核调度执行

2. 暂停 进程被挂起，不会被调度执行

   SIGSTOP SIGTSTP SIGTTIN SIGTTOU 会使程序进入暂停状态，并且一直保持该状态

   直到收到 SIGCONT 信号，进程继续运行

3. 终止

   • 进程收到一个信号，该信号默认行为就是终止进程
   • 进程从主程序返回
   • 调用 exit() 函数

void fork(void)

调用一次，返回两次，一次返回到父进程，返回值为子进程的进程号pid，另外一次返回到新创建的子进程，返回值为0。二者具有完全相同的内容但是不同的地址空间，共享文件描述符，二者是独立并发运行的，父进程会先开始执行，然后是子进程开始执行

标准输入输出

用C去写文件时的操作， File *fp=fopen()这个fp就是向系统申请的，相当于一通往文件的通道。文件描述符

其实， stdin,stdout,stderr就是一个文件描述符，不过他是随着计算机系统的开启默认打开的，其中0就是 stdin，表示输入流，指从键盘输入，1代表 stdout，2代表 stderr，1,2默认是显示器。 printf()其实就是向 stdout中输出，等同于 fprintf(stdout，“****”)， perror()其实就是向 stderr中输出，相当于 fprintf(stderr，“***”)

stderr，和 stdout还有重要一点区别， stderr是没有缓冲的，它立即输出，而 stdout默认是行缓冲，也就是它遇到 ‘\n’，才向外输出内容，如果你想 stdout也实时输出内容，那就在输出语句后加上 fflush(stdout)，这样就能达到实时输出的效果

8.5 execve和waitpid函数

具体内容看操作系统笔记

8.6 信号

是一种更高层次的软件形式的异常，允许内核和进程中断其他的进程

发送信号的几种方式

1. 用 /bin/kill 程序发送信号

   例如：

   • /bin/kill -9 1 表示向进程1发送终止信号
   • /bin/kill -9 -1 表示向进程组1发送终止信号，将会发送到进程组的每一个进程中，进程组中所有进程都将终止

2. 从键盘发送信号

   键盘输入 ctrl-c 键系统会发送一个中断信号到前台进程组中的所有进程中

   键盘输入 ctrl-z 系统会挂起前台进程组的所有进程

3. 用 kill 函数发送信号

   int kill(pid_t pid, int sig);

   可以向进程发送终止信号

   如果 pid>0，函数kill发送信号sig给进程pid

   如果 pid=0，函数kill发送信号sig给调用进程所在的进程组中的所有进程包括自己

   如果 pid<0，函数kill发送信号sig给对应进程组(id=abs(pid))的所有进程

4. 用 alarm 函数发送信号

   unsigned int alarm(unsigned int secs); 可以向自己发送信号

   secs表示函数alarm安排内核在secs秒之后发送一个SIGALRM信号给调用进程，如果为0直接发送信号

进程组

每个进程都只属于一个进程组，每个进程组都有自己的ID值来唯一标识，这个ID是一个正整数

pid_t getpgrp(void); 获取当前进程所属的进程组ID值

默认情况下一个子进程和它的父进程属于同一个进程组

pid_t setpgrp(pid_t pid, pid_t pgid); 进程可以调用该函数来改变自己或其他进程的进程组，pid表示原来进程组的id值，pgid表示更改后进程组的id。如果参数pid为0，那就使用当前进程的PID值。如果pgid为0，那就用pid指定的进程的PID值作为进程组的ID值。

接收信号

当内核把进程从内核模式切换到用户模式时，会检查进程未阻塞的待处理的信号集合，如果集合为空，内核将控制传递到进程的逻辑控制流中的下一条指令。如果集合非空，那么内核选择集合中的一个信号，强制进程接收该信号。接收信号会触发控制转移到信号处理程序，完成处理之后，将控制返回给被中断的程序。每一个信号都有被预定义的默认行为

1. 进程终止 SIGKILL
2. 进程终止并转储内存 dumping core 转储内存就是把代码和数据的内存镜像都写在磁盘上
3. 进程挂起直到被SIGCONT信号重启
4. 进程可以直接忽略的信号

待处理信号：只被接收未被处理的信号，一种类型的信号最多有一个待处理信号，之后接收到的该类型的信号只会被简单的丢弃。

信号处理程序可以被其他信号处理程序中断

第九章 虚拟内存

9.1 虚拟内存

计算机系统中，多个进程之间共享CPU和内存，如果进程太多会因为无法获得足够的内存空间而无法运行，并且，如果某个进程不小心把数据写入到另外一个进程的内存空间中就会发生一些奇怪的错误。

现代计算机系统提供了一种对内存的抽象概念，虚拟内存，可以自动完成内存管理的相关工作，并不需要外部干预

1. 虚拟内存遍布计算机系统的各个层面，在硬件异常，汇编器，链接器，加载器，文件以及进程的设计中都扮演了重要角色
2. 虚拟内存为应用程序提供强大的能力，可以创建和释放内存空间，将内存空间映射到磁盘文件的某个部分，与其他进程共享内存等
3. 如果虚拟内存使用不当，程序会产生很复杂的错误。每次引用一个变量，间接引用一个指针或者调用一个malloc函数时会与虚拟内存产生交互

物理地址

CPU通过物理地址访问内存，物理地址通过内存总线传递给内存控制器

虚拟寻址

CPU通过虚拟地址访问内存，要先转化为响应的物理地址，这个任务叫做地址翻译，由内存管理单元来实现该功能。

地址空间

一个非负整数的有序集合，如果地址空间中的整数是连续的，就是一个线性地址空间

物理地址空间

对应系统中的物理内存

虚拟内存（虚拟内存）

虚拟内存可以看成一个由磁盘上N个连续的字节组成的数组，其中每个字节都有一个唯一的虚拟地址，这个虚拟地址就是数组得到索引值。虚拟内存中被分割成块，就是虚拟页，每个虚拟页大小为P个字节。并且物理内存也被分割为物理页，大小是一样的。虚拟页面分为3类

1. 未分配的——虚拟内存系统还没有创建的页，没有任何数据与之相关联，不占用任何磁盘空间，没有映射物理空间
2. 已缓存的——当前已经缓存在物理内存页中
3. 未缓存的——已经被分配，但是没缓存在物理内存页中

把进程整个复制到内存空间中去，可能会由于数据太多导致内存不够用，并且这种复制内存可能会花费相当多的时间。可以把它切碎，分成一个个小单元，每个单元可以是4kb大小，称为1页或者页面，其中只有一部分页面会在内存中。当CPU需要访问的地址不在内存中的页面中时，可以从磁盘中加载对应的部分到内存中，同时内存不够时，也可以把长期不访问的页面保存到磁盘中，然后删除内存中的部分——虚拟内存

虚拟内存的使用流程

先把虚拟内存地址发送给内存管理单元MMU，把虚拟地址转换为物理地址后，通过总线访问内存，内存从总线中获得物理地址。

其中MMU转换地址需要一个用来记录虚拟地址到物理地址页框的映射关系，成为页表。进程的虚拟地址空间可以比实际内存空间大。把内存中对应的框叫做页框，用于加载一个页面，并且页面的映射没有顺序。

最终转化为2进制之后，偏移地址量都是一致的，只是页面所对应的页框号是不同的，这个是根据页表的映射关系来确定的

页面号中间可能有二级页面号，这种称为多级页表。好处是可以只让部分页表保存在内存中，页表的加载也可以同虚拟内存的使用类似

记录映射关系的页表，其中每一项叫做页表项，包含

• 页框号
• 一位表示该页面是否在内存中
• 保护位，记录读写执行的权限
• 修改位，访问位，高速缓存禁止位

页表通常是保存在内存中，那转换器MMU每次转换都需要从内存中读取就会很慢，所以需要硬件加速。MMU中有暂时存储最近使用的部分页表项，这称为转换检测缓冲区TLB或者相联存储器

1. 什么是虚拟内存？解决了什么问题？

虚拟内存是操作系统内存管理的一种技术，每个进程启动时，操作系统会提供一个独立的虚拟地址空间，这个地址空间是连续的，进程可以很方便的访问内存，这里的内存指的是访问虚拟内存。虚拟内存的目的，一是方便进程进行内存的访问，二是可以使有限的物理内存运行一个比它大很多的程序。

虚拟内存的基本思想：每个程序拥有自己的地址空间，这个空间被分割成很多块，每块称为一页，每一页地址都是连续的地址范围。这些页被映射到物理内存，但不要求是连续的物理内存，也不需要所有的页都映射到物理内存，而是按需分配，在程序片段需要分配内存时由硬件执行映射(通常是 MMU)，调入内存中执行。

2. 说说分页和分段的机制？

分页是实现虚拟内存的技术，虚拟内存按照固定的大小分为页面，物理内存也会按照固定的大小分成页框，页面和页框大小通常是一样的，一般是 4KB，页面和页框可以实现一对一的映射。分页是一维的，主要是为了获得更大的线性地址空间。但是一个地址空间可能存在很多个表，表的数据大小是动态增长的，由于多个表都在一维空间中，有可能导致一个表的数据覆盖了另一个表。

分段是把虚拟内存划分为多个独立的地址空间，每个地址空间可以动态增长，互不影响。每个段可以单独进行控制，有助于保护和共享。

3. 页表的作用？为什么引入多级页表？

页表实现了虚拟内存到物理内存的映射，当访问一个虚拟内存页面时，页面的虚拟地址将作为一个索引指向页表，如果页表中存在对应物理内存的映射，则直接返回物理内存的地址，否则将引发一个缺页异常，从而陷入到内核中分配物理内存，返回对应的物理地址，然后更新页表。

为了加快虚拟地址到物理地址的转换，多数系统会引入一个转换检测缓冲区（TLB）的设备，通常又称为快表，当请求访问一个虚拟地址时，处理器检查是否缓存了该虚拟地址的映射，如果命中则直接返回物理地址，否则就通过页表搜索对应的物理地址。

由于虚拟内存通常比较大(32 位系统通常是 4G)，要实现整个地址空间的映射，需要非常大的页表。解决的办法是引入多级页表，只将那些用到的页面装载进来，因此，多级页表可以大大节约地址转换所需要的的空间。

4. 页面置换算法有哪几种？

当访问的页面不在内存中时，会发生一个缺页异常，操作系统必须将该页换出内存，如果此时内存已满，则操作系统必须将其中一个页面换出，放到 swap 交换区中，为当前访问的页面腾出空间，这个过程称为页面置换。操作系统提供了多种页面置换算法：

最优页面置换算法

选择一个将来最长时间不会被访问的页面换出。这样可以保证将来最低的缺页率。这是一种理论上的算法，因为无法知道哪个页面是将来最长时间都不会被访问的。

最近未使用页面置换算法 (NRU)

为每个页面设两个状态位：被访问时设置为 R=1 位，页面被修改时，设置为 M=1 位。当启动一个进程时，所有页面都被初始化为 R=0，M=0。其中 R 位会被定时的清 0，以此区分最近被访问的页面和没有被访问的页面。

于是所有页面可以分为以下 4 类：

0 类：R=0，M=0；

1 类：R=0，M=1；

2 类：R=1，M=0；

3 类：R=1，M=1；

当发生缺页中断时，NRU 算法随机地从类编号最小的非空类中挑选一个页面将它换出（挑选优先级：1 类 > 2 类 > 3 类）。

最近最少未使用（LRU）页面置换算法

在内存中维护一个所有页面的单链表。当一个页面被访问时，将这个页面移到链表表头。这样就能保证链表表尾的页面是最近最久未访问的。

因为每次访问都需要更新链表，因此这种方式实现的 LRU 代价很高。

先进先出（FIFO）页面置换算法

维护一个链表，最先进入的页面放在表头，最后进入的页面放在表尾，当缺页中断发生时，直接淘汰表头的页面，并把新的页面放在表尾。

这种算法有可能置换掉经常访问的页面，导致缺页率升高。

第二次机会页面置换算法

对 FIFO 算法做一个修改：取出表头的页面时，检查该页面的 R 位，如果是 1 表示是最近有访问的，将其清 0，然后放入表尾，然后继续检查下一个表头的页面，直到遇到一个 R 位为 0 的页面，将其换出。

时钟页面置换算法

与上一个算法类似，只不过单链表改成了环形链表，形成一个时钟，移动的也不是页面，而是中间的表针。检查页面逻辑类似，如果该页面 R 为 0，则直接置换该页面，否则将该 R 位清 0，然后表针向前移动。

5. 内存是如何分配的

Linux 分配物理内存的主要机制是页面分配机制（页分配器），使用了著名的伙伴算法，主要用来分配页大小的整数倍的内存(4n KB)。如果是小于页大小的内存分配，通常使用 slab 管理器。通过 slab 分配的内存通常会缓存起来，方便下次使用。

6. 内存是如何回收的？

应用程序用完内存后，可以调用 free() 释放内存，或调用 unmap() 取消内存映射，归还系统。

在内存紧张时，会通过一系列机制来回收内存，如以下三种方式：

• 回收缓存。主要是页缓存。
• 回收不常访问的页面。使用页面置换算法，把不常用的页面放到交换区中。
• 通过 OOM 杀死占用大量内存的进程，释放内存。