深入理解计算机系统——基础知识

2021-05-03

CS:APP

Word count: 11.2k | Reading time≈ 39 min

深入理解计算机系统——基础知识

前言

为了方便我查询一些我可能会忘记的基础知识，我写下这篇博客

中间可能有自己的一些经验看法

以下的知识没有先后顺序，用时特定自查

通用寄存器

EAX 是”累加器”(accumulator)，它是很多加法乘法指令的缺省寄存器。
EBX 是”基地址”(base)寄存器，在内存寻址时存放基地址。
ECX 是计数器(counter)，是重复(REP)前缀指令和LOOP指令的内定计数器。
EDX 则总是被用来放整数除法产生的余数。
ESI/EDI 分别叫做”源/目标索引寄存器”(source/destination index)，因为在很多字符串操作指令中，DS:ESI指向源串,而ES:EDI指向目标串.
EBP 是”基址指针”(BASE POINTER)，它最经常被用作高级语言函数调用的”框架指针“(frame pointer)，在破解的时候,经常可以看见一个标准的函数起始代码（左为目标寄存器）：
1
2
3
push ebp ;保存前一个函数帧指针ebp
mov ebp,esp ;EBP设为当前帧指针
sub esp, xxx ;预留xxx字节给函数临时变量.

ESP 专门用作堆栈指针，被形象地称为栈顶指针，堆栈的顶部是地址小的区域，压入堆栈的数据越多，ESP也就越来越小。在32位系统中，ESP每次减少4字节。
使用惯例：eax,edx,ecx被划分为调用者保存寄存器；ebx,esi,edi被划分为被调用者保存寄存器

专用寄存器

EIP指令指针（Instruction Pointer.）。代码段中下一个指令的指针。自动更新。
ESP堆栈指针（Stack pointer.）。指针指向栈顶（在SS（Stack Segment）栈段寄存器）。与POP、PUSH、CALL等指令一起使用

段寄存器

寄存器名	寄存器功能
CS	Code Segment. 代码段
DS	Data Segment. 数据段
SS	Stack Segment. 栈堆段
ES	Extra Data Segment. 额外数据段
FS	Extra Data Segment.额外数据段
GS	Extra Data Segment.额外数据段

EFLAGS寄存器

EFLAGS(program status and control) register主要用于提供程序的状态及进行相应的控制

EFLAGS 标志。cpu中各种条件的状态。 EFLAGS寄存器的各个位的用途如下所述：

00 Carry (CF)：保存加法后的进位或者减法后的借位。也指示错误情况。
02 Parity (PF)：奇数位数为0，偶数位数为1。80x86的过时功能。
04 Auxiliary Carry (AF)：BCD加法或者减法后，DAA和DAS指令使用的高度专用标志。
06 Zero (ZF)：如果算术或逻辑指令的结果为0，则ZF为1。
07 Sign (SF)：如果算术或逻辑指令的结果符号为负，则SF为1。
08 Trap (TF)：陷阱使能。微处理器在调试和控制寄存器指示的条件下中断指令流。
09 Interrupt (深入理解计算机系统——基础知识/iF)：控制INTR(深入理解计算机系统——基础知识/interrupt request)引脚的操作。如果为1，中断使能。由STI和CLI指令设置。
10 Direction (DF)：指定在字符串指令期间DI和/或SI寄存器的递增或递减模式。如果DF为1，寄存器自动递减。由STD和CLD指令设定。
11 Overflow (OF)：为加法和减法指令设置。
12 and 13 I/O privilege level (深入理解计算机系统——基础知识/iOPL)：保持代码必须运行的特权级别，以便执行任何与输入输出相关的指令。00是最高的。
14 Trap Nested Task (NT)：当一个系统任务在保护模式下通过call指令调用另一个系统任务时设置。

下半部分不记录了，用不到

浮点数

一个浮点数由三部分组成：

符号。1为负，0为正，数值0特殊处理
阶码，移码（将补码的符号位取反减一）表示，所以我们将阶码加1取反符号位得到的就是指数。
尾数，顺序排列尾数。如1000 0000表示的是0.1

规格化数，1.f * 2^E，E在区间（-126，127）

非规格化数，0.f * 2^(-126)

特殊值

NAN，不是一个数
无穷大

一些容易忽略的指令

call指令：过程调用，将返回地址入栈，并跳转到被调用过程的起始处。返回地址就是紧跟在call后的那条指令的地址。
ret指令：从过程调用中返回，将返回地址出栈，并跳转到返回地址。
push指令：入栈，esp减4字节，操作数就是入栈的数据
pop指令：出栈，esp加4字节，操作数就是出栈的数据保存的地址
cmp指令：比较指令，cmp s2,s1基于s1-s2，只设置条件码
test指令：测试指令，test s2,s1基于s1&s2，只设置条件码

leave指令：为返回准备栈，等价于

1 2	movl %ebp,%esp //栈指针设置为帧指针 popl %ebp //ebp存储一开始被保存的旧的ebp,esp指向返回地址的节点

栈帧图

用c语言描述函数：

void f( (void)arrgument 1, (void)arrgument 2, ....... ,(void)arrgument n){
    void local variable 1;
    void local variable 2;
    void local variable 3;
    ......
    void local variable n;
}

图中的地址从上往下递减的，栈顶在下，栈底在上。

Return address和Previous frame pointer分别是返回地址和调用者的帧指针。

跳转指令

指令	功能	条件
`JE`	相等则跳转	`ZF`=1
`JNE`	不相等则跳转	`ZF`=0
`JA`	无符号大于则跳转	`CF`=0 and`ZF`=0
`JG`	有符号大于则跳转
`JS`	为负则跳转
`jle`	有符号小于或者等于跳转
`JGE`	有符号大于或等于跳转
`JBE`	无符号小于等于则跳转

优化程序性能

程序优化的第一步就是消除不必要的内容，让代码尽可能有效地执行它期望的工作。这包括消除不必要的函数调用、条件测试和存储器引用。使用图形数据流表示法，可以使处理器对指令的执行形象化，我们还可以利用它预测程序的性能。、

程序优化的第二步，利用处理器提供的指令级并行能力，同时执行多条指令。

Amdahl定律，可以量化对系统某个部分进行优化所带来的整体效果。主要思想是当我们加快系统一个部分的速度时，对系统整体性能的影响依赖于这个部分有多重要和速度提高了多少。所以要想大幅度提高系统的速度，我们必须按提高系统很大一部分的速度。
$$
S=\frac{1}{(1-a+\frac{a}{n})}
$$
说明：

S为全局加速倍数（原来总时间/加速后总时间）
a为并行计算所占比例（可以并行计算代码量/总代码量），就是可以优化的部分。
n为并行节点处理个数，可以理解为CPU的核心数，就是可以优化的倍数。
所以这个公式其实就是，将可以优化的部分优化n倍。

关键路径是在循环的反腐执行过程中形成的数据相关链，常常通过确认关键路径来决定执行一个循环所需要的时间。

存储器别名使用是指两个指针可能同时指向同一个存储器的位置的情况。在只考虑执行安全的优化中，编译器必须假设不同的指针可能会指向存储器的同一个位置，这造成了第一个妨碍优化的因素，这也是可能严重限制编译器产生优化代码机会的程序的一个方面。如果编译器不能确定指针的指向，它就会假设所有的情况都有可能，所以我们需要做的就是在编写程序的时候明确指针的指向。

1 2	q=y; p=x; t1=*q; //t1= x or y?

函数调用是第二个妨碍优化的因素。尽可能减少函数的调用可以优化程序，但是编译器会假设最糟糕的情况，并保持所有的函数调用不变。所以，我们需要在编写程序的时候将函数调用的次数尽可能减少，这件事情只能coder来做，编译器为了安全是不会去做的。

int fun1(){
    return f() + f() + f() + f();
}
int fun2(){
    return 4 * f();
}
/* 这两个函数看似得到的是同一个结果，而且fun2函数明显要优于fun1，因为函数调用次数少。 */
/* 如果f()代码如下    */
int counter=0;
int f(){
    return counter++;
}
/* 因为f改变了全局变量counter，所以fun1和fun2的功能完全不同，分别是return (0+1+2+3)和return 4*0
** 所以，我们不能期望编译器自己将fun1改变成fun2去优化程序，因为这种情况不安全     
*/

用内联函数优化函数调用是指将函数调用替换为函数体。这样做既减少函数调用的开销，也允许对展开的函数做进一步的优化。

每元素的周期数（Cycles Per Element ，CPE）作为程序性能的度量标准。它的计算过程是：先得到函数的元素个数和周期的散点图，后经过最小二乘方拟合得到折线图，其中折线的斜率表明每元素的周期数CPE。

消除循环的低效率，for(深入理解计算机系统——基础知识/i=0;i<vec_length();i++)调用函数作为循环的测试条件，意味着我们需要调用很多次函数，这是非常低效的。代码移动可以优化事变要执行很多次却不改变计算结果的计算，在本例中，我们将循环内部的的函数调用移到循环前面。

减少过程调用，还是减少循环中函数的调用，这次是用数组直接取值来代替用函数取值。

消除不必要的存储器引用，直接用指针来取值会对存储器进行读出或写入的操作，我们用临时变量来代替指针取值，可以直接在寄存器上操作，这会大大增强函数性能。

算术运算的延迟和发射时间

利用微处理器微体系结构的优化

指令级并行指，在实际的处理器中，是同时对多条指令求值。在代码级上，似乎是一次执行一条指令，每条指令都包括从寄存器或存储器取值，执行一个操作，并把结果存回到一个寄存器或存储器位置。但是复杂奇异的微处理器结构让多条指令可以并行地执行，同时又呈现一种简单地顺序执行指令的表象。

两种界限描述了程序的最大性能：

延迟界限：当一系列操作必须严格顺序执行时，就会遇到延迟界限，因为在下一条指令开始前，这条指令必须结束。给出了函数所需要的最小CPE值。
吞吐量界限：刻画了处理器功能单元的原始计算能力。这个界限是程序性能的终极限制。

分支预测技术，分支是指条件转移指令，现代处理器会猜测是否会选择分支，同时还预测分支的目标地址。使用投机执行的技术，处理器会开始取出位于它预测的分支会跳到的地方的指令，并对指令译码，甚至在它确定分支预测是否正确之前就开始执行这些操作。如果预测错误，会将状态重新设置到分支点的状态，并开始取出和执行另一个方向上的指令。

边界检查是通过条件语句判断的，所以利用分支预测技术可以让处理器预测分支结果，不会让边界检查对程序执行中关键路径的指令取值和处理产生太大影响。所以不要过分关心可预测的分支。

对于本质上无法预测的情况，如果编译器能够产生使用条件数据传送而不是条件控制转移的代码，可以极大提高程序的性能。

每个运算都是由两个周期计数值来刻画的：

延迟：表示完成运算所需要的总时间。
发射时间：表示两个连续的同类型运算之间需要的最小时钟周期数，发射时间的倒数是这个功能单元的最大吞吐量。
我理解的延迟和发射时间：因为使用流水线实现运算，所以延迟是指完成一个流水线所需要的周期数，而发射时间指的是在流水线开始后，完成一个运算所需要的时钟周期数，它的倒数就是指每个周期可以完成多少运算，也就是功能单元的最大吞吐量。例如：整数加法的发射时间是0.33倒数是3，延迟是1，它有能力每个周期执行三个加法，但如果只执行一个加法，那时间还是一个周期。

完全流水化的功能单元是指发射时间为1的功能单元，每个时钟周期可以开始一个新的运算，

程序的数据流表示，作为分析在现代处理器上执行的机器级程序性能的一个工具，这是一种图形化的表示方法，展示了不同操作之间的数据相关是如何限制它们的执行顺序的。这种限制形成了图中的关键路径，这是执行一组机器指令所需时钟周期数的一个下界。

从机器级代码到数据流图：

机器级代码
第一步，将机器级代码译码成操作。如图所示：左边的方框和线给出各个指令是如何使用和更新寄存器的，顶部的方框表示开始时的寄存器值，底部的方框表示最后寄存器的值，右边的是各种操作，弧线表示操作产生的不对应于任何寄存器的值，相连的两个操作具有相关性（A->B，指必须等A结束，B才能进行）。

第二步，将操作抽象城数据流图。重新排列操作符，更清晰地表明了从顶部源寄存器（只读寄存器和循环寄存器）到底部目的寄存器（只写寄存器和循环寄存器）的数据流。如图所示：白色操作符表示无关操作符（不属于某个循环寄存器之间的相关链），蓝色操作符则相反。

第三步，消除了白色的操作符，只保留了循环寄存器。所以两大数据相关链条是：mul对程序值acc的修改、add对程序值i的修改。因为整数加法延迟1个周期，而单精度乘法延迟为4个周期，所以关键路径是mul对acc的修改，因为另一条链不会制约程序性能。
最后，我们将循环扩展，并将关键路径标出，得到数据流图。从图中我们看到，关键路径长为L*n，也就是说程序至少需要L*n个周期才能执行完。除了整数加法之外，测量出的CPE也确实等于运算的延迟 L。

除了关键路径之外，还有其他的影响性能因素，包括可用的功能单元的数量和任何一步中功能单元之间能够传递数据值的数量，这也是为什么整数加法不等于关键路径期望的CPE。

看上去，延迟界限是基本的界限，限制了合并运算能执行的速度。接下来的优化是调整操作的结构，增强指令级并行性。

我们想对程序做变换，使得唯一的限制变成吞吐量界限。

循环展开是一种程序变换，通过增加每次迭代计算的元素的数量，减少循环的迭代次数。首先，它减少了不直接有助于程序结果的操作的数量，例如循环索引计算和条件分支。其次，它提供了一些方法（例如重关联变换优化，就是改变值合并的顺序），可以进一步变化代码，减少整个计算中关键路径上的操作数量。

提高并行性，因为数据相关，虽然功能单元能够做到采用流水线一个周期开始一个新的操作，但是它只会每L（延迟）个周期开始一个新的操作。我们需要打破这种顺序相关，得到比延迟界限更好性能的方法。

多个累计变量，多个关键路径并行，这种方法利用了功能单元的流水线能力。在k更大一些，CPE不会更低是因为功能单元已经在最大负荷下工作了，也就是吞吐量界限。
重新结合变换，减少关键路径上操作的数量，另一种打破顺序相关从而使性能提高到延迟界限之外的方法。另一条数据相关链可以很快得进行处理，不会影响程序性能。样例中(x * array[n-1]) * array[n] => x * (array[n-1] * array[n])

理解存储器性能

加载操作对性能的影响

加载操作是将内存中的数据读出到寄存器中。
一个包含加载操作的程序的性能既依赖于流水线的能力，也依赖于加载单元的延迟。
由于加载单元的每个时钟周期只能启动一条加载操作，所以CPE不可能小于1。
对于每个被计算的元素必须加载k个值的应用，我们不可能获得低于k的CPE
计算当前加载地址，需要先获取上一轮的地址，由此加载操作之间就存在数据相关，就需要考虑加载延迟了

存储操作对性能的影响

存储操作是将寄存器中的数据保存到内存中，所以存储操作不会产生数据相关，但是存储操作会影响加载操作，出现写/读相关
首先需要先了解加载和存储单元的细节。在存储单元中会有一个存储缓冲区，用来保存发射到存储单元但是还未保存到数据高速缓存的存储操作的地址和数据，由此避免存储操作之间的等待。
加载操作会检查存储缓冲区中是否有需要的地址，如果有，则直接将存储缓冲区中的数据作为加载操作的结果。
要在更大范围观察写/读相关，不一定存在一个迭代中，可能在相邻迭代中，只要发现有存储操作，而后执行相同地址的加载操作，就会有写/读相关，必须等存储操作进行完成，才能进行加载操作。

存储器层次

存储器层次的中心思想，对于每个位于k层的更快、更小的存储设备作为位于k+1层的更大、更慢的存储设备的缓存。

存储层次为什么有效？由于局部性，相对于层次 k+1 的数据，程序趋向于更频繁访问层次 k 的数据。因此，允许层次 k+1 的存取速度更慢，空间更大，单位价格更便宜。

这种存储层次构建了一个价格接近最底层存储层次、大容量存储，而读取数据的速率接近最顶层的存储层次。

读吞吐率 ( 读带宽 ) ：单位时间从存储器读出字节的数量 (MB/s)

存储器山： 读带宽的时间和空间局部性的二维函数

RAM随机访问存储器

SRAM静态随机访问存储器，一个六晶体管电路实现，更贵更快。

DRAM动态随机访问存储器，一个电容和一个访问晶体管组成，便宜速度慢。

高速缓存cache

其中行就是cache块

CPU向cache请求数据块，会发生两种情况：

命中：我们需要的数据块存在于高速缓存中，就命中了。
不命中：我们需要的数据块不在cache中，需要在下一层存储器层次（主存等）中去找，称为不命中。
- 冷不命中：如果k层缓存是空的，则对任何数据的访问都是不命中的。属于短暂事件，在缓存暖身后不会出现。
- 冲突不命中：
  - k层缓存比k +1层缓存空间更小，只能存放k+1层缓存数据块的子集 。
    例如，k+1层的块 i 必须放在 k层的 (深入理解计算机系统——基础知识/i mod 4) 块中（严格放置策略），
  - 缓存够大，但是所需的多个数据块都被映射到同一个缓存块中，导致一直发生冲突不命中
    例如，块0和块8映射到同一个缓存块，反复引用块 0, 8, 0, 8, 0, 8, … 那么每次都会产生冲突
- 容量不命中：如果程序执行时，因为请求的数据块大小超过cache大小，所需的块不能全部调入Cache 中，则当某些块被替换后，若又重新被访问，就会发生失效。这种失效称为容量失效。

不命中率：不命中次数所占的百分比。具体计算：

在c语言中，数组是以行优先的方式去保存在存储器中的。
如果我们按a[0][0]、a[0][1]、......、a[0][n]的顺序去访问或者读取，那么强制不命中率=单个元素字节数/cache数据块大小
如果我们按a[0][0]、a[1][0]、......、a[n][0]的顺序去访问或者读取，那么强制不命中率=100%
若Cache命中时间是1周期，则其不命中处罚时间达到100周期，所以命中率为97%和99%的周期数分别是2和4，差距很大。

当把一个数据块调入高一层(靠近CPU)存储器时，可以放在哪些位置上？（映像规则），一共有三种：

全相联映像：主存中的任一块可以被放置到Cache中的任意一个位置。空间利用率最高，冲突概率最低，实现最复杂。

全相连Cache：S=1，只有一组，包括所有的行
直接映射：主存中的每一块只能被放置到Cache中唯一的一个位置。空间利用率最低，冲突概率最高，实现最简单

直接映射Cache：E=1，每组有1行
组相连映象：主存中的每一块可以被放置到Cache中唯一的一个组中的任何一个位置。作为两种映像的折中。

E-路组相连Cache：E=E，每组有E行

当所要访问的块在高一层存储器中时，如何找到该块?（查找算法）

我们通过一个地址在cache查找数据块，地址组成：标记t、组索引s、偏移量b

定位到组
检查组内任意行是否与标记匹配。如果匹配且行有效（有效位为1），则命中
以偏移量定位数据

当发生失效时，应替换哪一块？（替换算法）

先进先出法(FIFO)：如果不匹配，新行替换旧行。
随机法：为了均匀使用组中的各块，这种方法随机地选择被替换的块。
最近最少使用法LRU (Least Recently Used)：选择近期最少被访问的块作为被替换的块。但由于实现比较困难，现在实际上实现的LRU都只是选择最久没有被访问过的块作为被替换的块。

当进行写访问时，应进行哪些操作（写策略）

写命中：就是cache行有效位为1，反之则不命中

局部性原理

一个编写良好的程序倾向于引用最近引用过的数据本身，或者引用的数据项邻近于其最近引用过的数据项

时间局部性(Temporal locality)：最近被引用过的数据很可能很快会被多次引用
空间局部性(Spatial locality)：一个存储位置被引用了一次，很可能很快其附近存储位置也会被引用。

步长：按顺序、连续的对 v 的引用，我们称为步长为1的引用模式。同理，在一个连续的向量中，每隔k个元素对向量进行访问，称为步长为k的引用。一般来说，随着步长的增加，空间局部性会下降。

取指令的局部性：指令存在于存储器中，cpu 要读指令就必须取出指令。所以也能评价对于取指令的局部性。在循环中，循环体内的指令多次被执行，所以有良好的时间和空间局部性。

对cache友好的代码要有良好的局限性，我们对代码评价局部性的简单原则：

重复引用同一个变量有良好的时间局部性
对于步长为k的引用的程序，步长越小，空间局部性越好。
对于取指令来说、循环有较好的时间和空间局部性。
我们需要优化内循环内部的引用（例如：矩阵分块），大部分计算和存储器的访问都在这里。

编译系统

GCC编译器驱动程序读取源程序hello.c，并把它翻译成一个可执行目标文件hello。

预处理阶段。预处理器（cpp）根据字符#开头的命令，修改原始的c程序。
编译阶段。编译器（ccl）将文本文件hello.i翻译成文本文件hello.s，它包含一个汇编语言程序。
汇编阶段。接下来，汇编器（as）将hello.s翻译成机器语言指令，并把这些指令打包成一个叫做可重定位目标程序的格式。
链接阶段。如果，hello程序调用了一个printf函数，它是每个c编译器都会提供的标准C库中的一个函数。printf函数存在于一个名为printf.o的单独的预编译好了的目标文件中，而这个文件必须以某种方式合并到我们的hello.o程序中。链接器（ld）就负责处理这种合并。结果就得到hello文件，它是一个可执行目标文件（简称可执行文件），可以被加载到内存中，由系统执行。

链接和链接器

链接（linking）是将各种代码和数据部分收集起来并组合成为一个单一文件的过程，这个文件可被加载（或被拷贝）到存储器执行。

链接器（ld）在软件开发中扮演着一个关键的角色，因为它们使得分离编译（separate compilation）成为可能。我们可以将一个大型的应用程序分解成几个更小的、更好管理的模块，可以独立地修改和编译这些模块。当我们改变其中一个模块时，只需要重新编译它，并重新链接应用，而不必重新编译其他文件。

链接器做了什么？

符号解析。将每个符号引用和刚好和一个符号定义联系起来。
重定位。将各自的代码和数据合并到一起。将可重定位文件中符号的相对位置重定位到可执行文件中该符号相应的的绝对存储位置。更新所有的符号引用到其绝对位置。

目标文件

目标文件三种形式：

可重定位目标文件。包含二进制代码和数据。多个可重定位目标文件合并起来创建一个可执行文件。
可执行目标文件。包含二进制代码和数据。可被直接拷贝到存储器执行。
共享目标文件。一种特殊的可重定位目标文件。

下图是一种ELF（Executable and Linkable Format，可执行可链接的格式）可重定位目标文件格式。

ELF头。
- 以一个十六字节的序列开始，这个序列描述了生成该文件的系统的字的大小和字节顺序。
- ELF头剩下的部分包含帮助链接器语法分析和解释目标文件的信息。
  - ELF头的大小。
  - 目标文件的类型（如可重定位、可执行或者是共享的）
  - 机器类型（IA32）
  - 节头部表的文件偏移
  - 节头部表中的条目大小和数量。
夹在ELF头和节头部表之间的都是节。一个典型的ELF可重定位目标文件包含下面几个节：
- .text：已编译程序的机器代码。
- .rodata：只读数据。比如printf语句中的格式串和switch语句的跳转表。
- .data：已初始化的全局C变量。局部C变量在运行时保存在栈中，链接器不关心它。
- .bss：未初始化的全局C变量。在目标文件中，未初始化变量不需要占据任何实际的磁盘空间，仅仅是为了空间效率的占位符。
- .symtab：一个符号表，它存放在程序中定义和引用的函数和全局变量的信息。
- .rel.text：一个.text节中位置的列表，在与其他可重定位目标文件结合时需要修改这些位置。
- .rel.data：被模块引用或定义的任何全局变量的重定位信息。
- .debug：一个调试符号表。包括局部变量、全局变量以及原始的C源文件。只有用-g选项才会得到这张表。
- .line：原始C源程序中的行号和.text节中机器指令之间的映射。只有用-g选项才会得到这张表。
- .strtab：一个字符串表，其内容包括.symtab和.debug节中的符号表，以及节头部中的节名字。
节头部表描述不同节的位置和大小，目标文件中每个节都有一个固定大小的条目（entry）。

下图是一种ELF（Executable and Linkable Format，可执行可链接的格式）可执行文件格式。

ELF头，描述文件的总体格式。
段头部表，将连续的节映射到存储器段。
节部分，与可重定位目标文件相似，不同之处在于
- .init节定义了一个函数_init，程序初始化会调用它。
- 因为已经重定位完成，所以不再需要**.rel前缀的节**了

链接器符号和符号表

链接器符号是什么？符号表又是什么？

链接器符号其实就是程序中的变量名、函数名。
符号表是编译器为存储变量名、函数名、对象、类、接口等各种实体的出现情况而创建和维护的一种重要的数据结构。

链接器符号分为三种：

Global symbols（模块内部定义的全局符号）：由本模块定义并能被其他模块引用。对应于非静态的的c函数以及被定义为不带c语言static属性的全局变量。
External symbols（外部定义的全局符号）：由其他模块定义并被模块引用的全局符号。对应于定义在其他模块中的c语言函数和变量。
Local symbols（本模块的局部符号）：仅由本模块定义和引用的本地符号。对应于在模块中定义的带static的C语言函数和全局变量，这些函数和变量只能在本模块中引用，不能在其他模块中引用。
注意：链接器的局部符号不是指程序中的局部变量（分配在栈中的临时性变量），链接器不关心这种局部变量。

全局符号的强弱：

在编译时，编译器向汇编器输出的每个全局符号，或者是强符号，或者是弱符号。
强符号：函数和已初始化的全局变量。
弱符号：未初始化的全局变量。
对于多重定义的全局符号：强符号和弱符号中选强符号，强符号只能有一个，如果没有则选弱符号其中之一。
所以我们在编程时要注意尽可能地避免使用全局变量，若要使用需要合理使用static、extern，记得变量初始化。

.symtab节的中包含的ELF符号表举例：

重定位

在符号解析完成之后，进行重定位，分为两步：

重定位节和符号定义。链接器将所有相同类型的节合并成同一类型的新的聚合节。然后，链接器将运行时存储器地址赋给新的聚合节。程序的每个指令和全局变量都有唯一的运行时存储器地址。
重定位节中的符号引用。链接器依赖重定位条目修改代码节和数据节中对每个符号的引用，使得它们指向正确的运行时地址。

重定位条目的格式：

offset是需要被修改的引用的节偏移。
symbol标识被修改的引用应该指向的符号，就是符号名。
type告知链接器如何修改新的引用，也就是重定位类型。

两种最基本的重定位类型：

R_386_PC32：重定位一个使用32位PC相对地址的引用。PC相对地址就是距离程序计数器PC的当前运行时值的偏移量，PC值就是下一条指令的地址，PC=PC+value。
R_386_32：重定位一个使用32位绝对地址的引用。

refptr = .text + r.offset，重定位条目r的偏移加上.text节开始的位置，即需要被重定位的32位地址
对于R_386_PC32 类型，将这32位的值* refptr修改为ADDR(r.symbol)+ *reptr - refaddr(我认为等于reptr)，所以 *reptr 修改为重定位条目间隔位置与修改位置的相对距离与现在位置的值相加，也就是4字节地址末尾与重定位条目符号地址的相对距离。
对于R_386_32类型，将这32位的值* refptr修改为ADDR(r.symbol)+ *reptr ，所以 *reptr 修改为引用的绝对位置与现在可重定位条目间隔确定的位置的值相加。

库

静态库（.a存档文件集）： 一组连接起来的可重定位目标文件集合，有一个头部用来描述每个成员目标文件的大小和位置。允许增量更新

使用静态库的链接器行为：通过在一个或多个存档中查找符号来解析外部引用。若一个存档成员文件解析了引用，则可将其连接到可执行文件。

使用静态库时，链接器如何查找符号并解析外部引用？

按照命令行的顺序扫描可重定位文件和存档文件集。
在扫描过程中，维护一个当前未解析引用的列表。依据目标文件的符号定义，对遇到的每一个新**.o或.a 文件**, 尝试解析上述列表中每一个未解析的引用。
若在扫描结束时，未解析列表中仍有条目存在，则报错
所以命令行执行顺序很重要，原则上将库文件放在命令行末尾。

静态库的缺点：

对系统库进行修复时，需要对使用到这个库的所有程序进行重新链接。
在存储中和运行中的可执行文件都有多个副本。

共享库（动态链接库，DLLs， .so 文件）：包含代码和数据的目标文件，或者在加载时，或者在执行时，被动态加载和链接到应用中

使用共享库，加载时的动态链接：当创建可执行文件时，静态执行一部分链接，然后在程序加载时，动态完成链接过程。

在静态链接时，没有任何数据和代码被拷贝到可执行文件中。反之，链接器拷贝到一些重定位信息和符号信息，它们使得运行时可以解析对共享库中代码和数据的引用。
在加载时，执行动态链接，根据静态链接得到的信息，比如.interp节中的动态链接器的路径名，重定位共享库的数据和代码到存储器段和重定位可执行文件中所有由共享库定义的符号的引用，完成链接任务。

使用共享库，运行时的动态链接：将动态生成内容的每个函数打包在共享库中。

异常

异常就是控制流中的突变，用来响应处理器状态中的某些变化。状态变化称为事件。

在任何情况下，当处理器检测到有事件发生时，它会通过一张叫异常表的跳转表，调用一个专门用来处理这类事件的操作系统子程序。

当异常处理程序处理完异常之后，情况有三种：

返回，当事件发生时，正在执行的指令
返回，如果没有发生异常，将会执行的下一条指令
终止被中断的程序

异常的类别

进程

经典定义：进程就是一个执行中的程序。也就是说，我们每运行一个程序，都会创建一个新的进程。

我们不关注它如何实现，我们关注它所提供的应用程序的关键抽象：

一个独立的逻辑控制流。并不是独占处理器，而是多个进程去轮流使用处理器。
一个私立的地址空间。并不是独占地使用系统地址空间，而是一个进程给每个程序提供它自己的私有地址空间，理论上不能被其他进程读写。这是由虚拟存储器实现的。

并发是指多个逻辑控制流并发执行，注意与并行区别开。

多任务是指多个进程轮流执行。因为进程的控制流的一部分的时间段叫做时间片，所以多任务也称为时间分片。

内核为每个进程维持一个上下文。上下文就是内核重新启动一个被抢占的进程所需的状态，它由一些对象的值组成。

操作系统通过使用上下文切换的较高层形式的异常控制流来实现多任务，这个过程有三步：

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

下图是进程A和B上下文切换的一个实例，执行系统调用read到内核，内核中的陷阱程序请求磁盘控制器DMA传输，在传输完成后磁盘中断处理器。

从程序员角度，进程有三种状态：

运行。进程正在执行，或者等待被内核调度。
停止。被挂起，不会被调度。当收到信号时，再次开始运行。
终止。进程永远停止了。原因主要有：收到的信号的行为是终止进程、从主程序中返回、调用void exit(深入理解计算机系统——基础知识/int status)函数

进程控制，也就是从C程序中操作进程的系统调用。

#include <sys/types.h>
#include <unisd.h>
#include <sys/wait.h>

/* Linux系统中，pit_t被types.h定义为int */
pid_t getpid(void);          //返回调用进程的PID(唯一的正数进程ID)
pid_t getpid(void);          //返回父进程的PID，父进程指创建调用进程的进程

/************************************************************
** 子进程与父进程几乎但不完全相同。它们最大的区别是PID，除此之外相同。
** 所以当父进程调用fork时，子进程可以读写父进程中打开的任何文件 
*************************************************************/
pid_t fork(void);            //父进程通过fork函数创建一个新的运行子进程

pid_t waitpid(pid_t pid, int *status, int options)    //调用waitpid函数来等待它的子进程终止或停止
pid_t wait(深入理解计算机系统——基础知识/int *status)      //waitpid函数的简化版本，等价于调用waitpid(-1, status, 0)

unsigned int sleep(unsigned int secs)   //让进程休眠secs秒，返回值为剩余秒数，如果收到中断信号，则可能不为0
int pause(void)              //让进城休眠直到等到一个信号，总是返回-1
    
int execve(const char *filename, const char *argv[], const char *envp[])
//execve函数加载并运行可执行文件filename，参数列表argv和环境列表envp。
//如果成功，则不返回；如果错误，返回-1

子进程和父进程执行的特点：

fork调用一次返回两次，一次子进程返回0，一次父进程返回PID，可以用来分辨处于子进程还是父进程。。
并发执行。父进程子进程相互独立，并发执行。先后顺序不一定。
相同但是独立的地址空间。除了私有地址空间之外，代码、变量值完全相同，因此对数据做出的改变都是独立的。
共享文件。子进程会继承父进程打开的文件，当父进程调用fork时，std文件打开所以子进程不用再打开一次std文件，而是直接输出

fork的执行过程理解：当执行fork函数时，可以理解为分支，也就是从fork位置开始分成两支，并发执行接下来的代码。

加载一个可执行文件需要的命令行参数列表和环境列表：

新的程序开始时，一个典型的用户栈结构：

信号

Unix信号是一种更高层的软件形式的异常，允许进程中断其他进程。

一个信号就是一条小消息，它通知进程系统中发生了一个某种类型的事件。

虚拟存储器

虚拟存储器：一个由存放在磁盘上的N个连续的字节大小的单元组成的数组。每个字节和虚拟地址是一一对应的。

虚拟地址：就是磁盘上数组的索引。要比物理地址大很多。VPN作为页表的索引。VPO有p位定位业内的字节位置。

解决4 GB内存空间的不足问题：只将磁盘中的一部分放入内存中，以后根据实际的需要随时从硬盘中调入内容。

物理寻址和虚拟寻址

磁盘：在存储器层次是处于主存之下的一层。

虚拟页和物理页：VM系统将虚拟存储器分割为虚拟页（VP）的固定大小的块来进行与主存间的传输，大小为P字节，物理页（PP）同样也是P字节大小

页表：就是一个页表条目（PTE）的数组。为了判定一个虚拟页在哪个物理页，未命中判断虚拟页存放在磁盘的哪个位置，然后选择一个物理页作为牺牲页进行替换。

页表条目：一个有效位和n位地址组成。如果设置有效位，那么地址表示DRAM中物理页的起始位置，这个物理页缓存了该虚拟页。如果没有设置有效位，那么空地址表示该虚拟页未被分配。

VM页命中：对VP2的一个字的引用就会命中。也就是已经缓存在DRAM的

VM缺页：对VP3的引用不命中，从而触发缺页。然后选择VP4作为牺牲页，并从磁盘用VP3的拷贝来取代它。在缺页处理程序重新启动后，该指令将从存储器中正常读取字，而不会产生异常。

Copyright： Copyright is owned by the author. For commercial reprints, please contact the author for authorization. For non-commercial reprints, please indicate the source.