深入理解计算机系统 | 血肉苦痛，机械飞升

发布日期: 2024-07-23

更新日期: 2024-11-26

文章字数: 11.4k

阅读时长: 42 分

阅读次数:

1.系统架构

2.信息的表示与处理

现代计算机存储和处理的信息都以二值信号表示(位)，把位组合在一起，再加上某种解释(编码)。
三种最重要的编码:无符号编码(unsigned)针对大于等于0的数，补码编码(signed)针对有符号整数，浮点数编码(floating point)表示实数,通过有限位对数字编码会造成 溢出

2.1信息存储

大多数计算机使用8位的块作为最小可寻址内存单元(字节),将内存视为一个非常大的字节数组(虚拟内存),内存中每个字节都由唯一的数字标识(地址),所有地址集合(虚拟地址空间)

所以虚拟地址空间就是展示给机器级程序的概念性映像。

2.1.1十六进制表示法

一个字节的值域用十六进制表示则为 $00_{16} \sim FF_{16}$ 很简洁地描述了一个字节，c语言用0x表示16进制。

2.1.2字数据大小

每台计算机的指针数据都有个标称大小，代表着虚拟地址空间地最大大小(字长)，如果字长为 $w$ 位，该虚拟地址的范围为 $0 \sim 2^w-1$ 。

目前大多数计算机都从32位转为64位字长，32位字长虚拟地址为4GB不满足目前普遍16GB以上的内存容量。

C语言基本数据类型在32/64位系统下的典型字节大小如下表

类型(有符号 / 无符号)	32位	64位
char / unsigned char	1	1
short / unsigned short	2	2
int / unsigned	4	4
long / unsigned long	4	8
int32_t / uint32_t	4	4
int64_t / uint64_t	8	8
char *	4	8
float	4	4
double	8	8

2.1.3寻址和字节顺序

在几乎所有的机器上，多字节对象都被存储为连续的字节序列，其地址为所用字节的最小地址。

假设一个 $w$ 位的整数其位表示为 $[x_{w-1}(最高有效位),...,x_0(最低有效位)]$ ,将其表示为字节后相应有最高有效字节，最低有效字节。机器有下列两种存储数的方式：

大端法：最高有效字节存储在最低地址上
小端法：最低有效字节存储在最低地址上

大多数Intel兼容机都只用小端模式。小端模式最广泛。(linux,windows,ios都使用小端模式)
大小端主要是在网络编程、反汇编和强制类型转换时会有用。

2.1.4表示字符串

每个字符都用某个编码标准表示，然后组成一个字符数组，以null(其值为0)作为结束(字符串)

ASCII编码采用8位表示字符，主要使用于英文文档
Unicode编码采用32位表示字符，能够表示所有的符号，但是占用内存过大
作为替代UTF-8使用可变长度编码，用更小的内存表示Unicode中任何字符，更加广泛。

2.1.5表示代码

不同的机器类型使用不同的且不兼容的指令和编码方式，不同的操作系统也有不同的编码规则。

2.1.6布尔代数

基于二进制运算已经演化出数学知识体系(布尔代数)，用于研究逻辑推理的基本规则。

4个布尔运算：~,&,|,^(异或)

2.1.7C语言中的位级运算

如上一节。
常见用法就是在一个字中选出一个位集合(掩码)

2.1.8C语言中的逻辑运算

||,&&,!

逻辑运算认为非0表示TRUE,0表示FALSE
如果第一个参数求值能确定表达式结果，第二个参数不再求值。

2.1.9C语言中的移位运算

<<,>>
在左端补0然后右移(逻辑右移)，在左端补最高有效位然后右移(算术右移)

几乎所有的编译器都对有符号数使用算术右移，无符号数逻辑左移。

2.2整数表示

用位对整数编码有两种方式：一种只能表示非负数，第二种表示所有整数，

2.1.1整型数据类型

表示有限范围的整数。

2.1.2无符号数的编码

B 2 U_w(\vec{x}) \doteq \sum_{i=0}^{w-1} x_i 2^i

其中 $\vec{x}$ 表示位向量， $w$ 表示该整数的位数。
该函数为双射。

2.1.3补码的编码

将字的最高位解释为负权。

B 2 T_w(\vec{x}) \doteq-x_{w-1} 2^{w-1}+\sum_{i=0}^{w-2} x_i 2^i

该函数也是双射

2.1.4有符号数和无符号数之间的转换

数值可能会变但是位模式不变

2.1.5C语言中的有符号数和无符号数

无符号数后面加u，运算中如何混合，都会转换为无符号数。

2.1.6扩展一个数的位表示

无符号数转更大(比如uint32_t转uint64_t)通过0扩展
补码数转更大(比如short转int)通过符号扩展

2.1.7截断数字

大变小

2.3整数运算

2.3.1无符号加法

定义运算符 $+_w^u$ 为无符号加法，截断 $w$ 位。

x+_w^u y=\left\{\begin{array}{lll} x+y, & x+y<2^w & \text { 正常 } \\ x+y-2^w, & 2^w \leqslant x+y<2^{w+1} & \text { 溢出 } \end{array}\right.

2.3.2补码加法

定义 $+_w^{\mathrm{t}}$ 为补码加法，截断 $w$ 位。

x+_w^{\mathrm{t}} y=\left\{\begin{array}{lll} x+y-2^w, & 2^{w-1} \leqslant x+y & \text { 正溢出 } \\ x+y, & -2^{w-1} \leqslant x+y<2^{w-1} & \text { 正常 } \\ x+y+2^w, & x+y<-2^{w-1} & \text { 负溢出 } \end{array}\right.

2.3.3补码的非

2.3.4无符号乘法

2.3.5补码乘法

2.3.6乘以常数

2.3.7除以2的幂

以上用到再补充

2.4浮点数

浮点数表示对形如 $V=x \times 2^y$ 的有理数编码。

2.4.1二进制小数

小数可以表示如下，其中 $d$ 为小数， $d_i$ 为小数的表示位。

d=\sum_{i=-n}^m 10^i \times d_i

2.4.2 IEEE浮点表示

如果非常大的数字，比如 $5 \times 2^{100}$ 上面的方法很难表示。改用直接表示科学计数法更加简单。

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

$s$ 表示符号，决定正负
$M$ 表示尾数,是一个二进制小数
$E$ 表示阶码，对浮点数加权。

3.程序的机器级表示

这一节主要是窥视C语言提供的抽象层下面的东西，来了解机器级编程。

3.1历史观点

主要是intel和AMD在处理器上的发展，产生了如今X86-64架构处理器。

3.2程序编码

为了了解一段c语言程序和机器代码之间的关系，从linux上默认编译器GCC C编译器出发

linux> gcc -Og -o p p1.c p2.c

这段指令就是用GCC C编译器将两个c文件p1.c,p2.c编译生成机器代码p。
-Og是生成机器代码的优化等级，如果优化等级过高会导致机器代码和原始代码之间的关系难以理解。
-o p表示生成可执行文件p
gcc命令调用了一整套程序
①C预处理：插入#include指定的文件，扩展用#define声明的宏
②编译器:产生两个源文件的汇编代码，名字分别位p1.s,p2.s。
③汇编器：将汇编代码转化位二进制目标代码p1.o,p2.o

目标代码是机器代码的一种形式，包含所有指令的二进制表示，但是还没有填入全局值的地址(因为代码还没有合并)

④链接器将两个目标代码文件和实现库函数代码合并，生成可执行代码文件p

可执行文件是机器代码的第二种形式，是处理器执行的代码格式。

机器级编码
指令集架构(ISA)定义机器级程序的格式和行为，比如x86-64将程序的行为描述成每条指令顺序执行。

3.3数据格式

由于x86-64由16位一步步扩展过来，所以将数据分为了字节，字，双字,四字,分别对应汇编代码b,w,l,q

3.4访问信息

处理器通过内置的寄存器来访问内存中的数据。x86-64包含16个64位的通用目的寄存器用来存储整数数据和指针。

3.5算术和逻辑操作

操作主要分为：加载有效地址leap、一元操作INC,DEC等、二元操作ADD,SUB等和移位SAL等。各种运算指令都是通过这4个基本操作或者其组合。

3.6控制

对于一些要跳转的代码比如条件语句、循环等汇编这边采用jump控制指令

3.7过程

过程是一种抽象，也就是c代码中可以被调用的函数等。
要提供对过程Q的机器级支持需要满足多个机制
①传递控制：进入过程时，程序计数器(PC)设置为Q代码的起始地址，返回时调用Q的后面的地址
②传递数据：能够为Q提供参数，Q也能返回一个值
③分配和释放内存：Q为局部变量分配空间，返回时释放空间

3.7.1运行时栈

栈向低地址生长

调用x86-64过程时会在栈上分配空间，该空间叫做过程的栈帧。

3.8数组分配和访问

T A[N]
T *p=A

如果数据类型T的大小为L，那么会分配 $L \cdot N$ 的连续区域。
如果p的值为 $x_p$ ,那么p+i的值为 $x_p+L \cdot i$

T A[N][M]

对于嵌套的数组，很显然需要 $L \cdot N \cdot M$ 的连续空间，将其看成5行3列的二维数组，在内存中按照行优先的顺序排列，，即A[0][0]然后A[0][1]。

3.9异质数据结构

对于多种类型对象的组合比如struct(将多个对象集合到一个单位),union(用多种不用的类型来引用一个对象)

3.9.1结构体

结构体所有组成部分都存放在内存的连续区域内，指向结构体的指针就是结构体第一个字节的地址。
比如下面的结构声明

struct rec{
    int i;
    int j;
    int a[2];
    int *p;
};

其内存中分配的空间如下
深入理解计算机系统-2024-07-24-14-14-09

3.9.2联合

struct S3{
    char c;
    int i[2];
    double v;
}
union U3{
    char c;
    int i[2];
    double v;
}

编译时其字段偏移量如下
深入理解计算机系统-2024-07-24-14-18-45
可见一个联合的总大小等于它最大字段的大小。
其应用情况为：针对一个数据结构中的两个不同字段的使用是互斥的，那么就将这两个字段声明为联合的一部分，从而减少分配空间的总量。
比如要实现一个二叉树的数据结构，只有叶子节点有数据，只有内部节点有指向两个孩子的指针，实现方式如下：

typedef enum{N_LEAF,N_INTERNAL} nodetype_t;

struct node_t{
    nodetype_t type;
    union node_u{
        struct{
            union node_u *left;
            union node_u *right;
        }internal;
        double data[2];
    }info;
}

为了确定一个给定节点的类型，所以引入了枚举类型。

3.10在机器级程序中将控制与数据结合起来

指针是联系控制和数据重要的概念。

3.10.1理解指针

①每个指针都对应一个类型
②每个指针都有一个值 NULL表示这个指针没有指向任何位置
③指针用&运算符创建
④*操作符用于间接引用指针采用内存引用来实现，要么存储到一个指定的地址，要么从指定的地址读取。
⑤数组与指针紧密联系类型强转，只改变类型，不改变值。

如果p是一个char *类型的指针,其值为 $x_0$ ,(int *)p+4*7计算为 $x_0+28$ ,而(int *)(p+7)计算为 $x_0+7$

⑥指针可以指向函数函数指针的值是该函数机器代码表示中第一条指令的地址。

int fun(int x,int *p);//函数定义
//指针声明
int (*fp)(int,int *);
fp=fun;
//指针调用
int y=1;
int result=fp(3,&y);

3.11浮点代码

用寄存器

3.12小结

关于其他编程语言的机器级实现：

C++和C非常相似，都是通过将源代码翻译为机器级的汇编代码，最后产生目标代码实现
Java的目标代码是一种特殊的二进制表示，称为Java字节码,但是这种目标代码是虚拟机的机器级程序，用软件解释器处理字节代码，模拟虚拟机的行为。其优点是相同的代码可以在许多不同的机器上执行。
另一种是即时编译的方法,动态地将字节代码作为程序地低级表示。当代码要执行多次时，这种方法执行更快。

4.处理器体系结构

上一节都是在x86-64指令集架构(ISA)下，不同的处理器有不同的ISA,一个程序编译在一种机器上运行就不能在另一种机器上运行。本章主要研究一个硬件系统执行Yx86-64ISA指令的方式。

4.1Y86-64指令集体系结构

定义一个指令集架构包括定义各种状态单元、指令集和它们的编码、一组编程规范和异常事件处理。

4.1.1程序员可见的状态

15个64位程序寄存器，3个1位条件码，程序计数器，程序状态码
深入理解计算机系统-2024-07-24-15-10-22

4.1.2Y86-64指令

也就是指令集
深入理解计算机系统-2024-07-24-15-13-11

4.1.3指令编码

涉及汇编到机器代码的转换
每条指令需要1~10个字节不等，第一个字节表明指令的类型，高4位时代码部分，低4位时功能部分。
如下图，第一个数表示代码，第二个数表示功能。
第一个字节的实例

x86-64被称为复杂指令集(CISC),其指令数量很多,在大型机占据了通知地位
精简指令集(RISC)通常少于100个，在嵌入式处理器市场表现出色。

4.2逻辑设计和硬件控制语言HCL

硬件设计是指令集的硬件载体。

4.3Y86-64的顺序实现

先描述一个称为SEQ的处理器，在每个时钟周期上，SEQ执行处理完一条完整指令所需的所有步骤。

4.3.1将处理组织成阶段

①取指从PC指向的内存地址中读取指令字节
②译码从寄存器中读入最多两个操作数
③执行算术/逻辑单元(ALU)执行指令指明的操作。
④访存将数据写入内存
⑤写回将结果写入寄存器
⑥更新PC 将PC设置成下一条指令的地址

4.3.2SEQ硬件结构

SEQ的抽象结构
更详细的硬件结构如下：白色方框表示时钟寄存器，浅蓝色方框表示硬件单元，控制逻辑块用灰色圆角矩形表示，线路的名字在白色圆圈中说明，宽度位字长的数据连接用中等粗度的线表示，宽度为字节或更窄的数据连接用细线表示，单个位的连接用虚线表示。
更详细的硬件结构

4.3.3SEQ的时序

4.3.4SEQ阶段的实现

关于SEQ各部分的硬件实现，可以用HCL写出来的那种。

4.4流水线的通用原理

三阶段流水线的计算硬件
三阶段流水线的时序
带反馈的流水线

4.5Y86-64的流水线实现

手搓CPU时再看吧

5优化程序性能

编写高效程序需要

选择一组适当的算法和数据结构；
编写出编译器能够有效优化以转换成高效可执行代码的源代码。

对于第二点就需要去理解编译器的能力和局限性。
程序员需要一个目标机器的模型，利用处理器提供的指令集并行能力，同时执行多跳指令。

5.1优化编译器的能力和局限性

大多数编译器会假设最糟糕的情况，并保持所有的函数调用不变。
比如：

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

显然在大多数情况下两个过程有相同的行为，且第二个过程性能高于第一种，但是如果xp和yp指向同一个位置时，两个过程就无法等价。

5.2表示程序性能

引入程序性能的度量标准：每元素的周期数(CPE)，通常用时钟周期来表示，比如一个4GHz的处理器时钟周期为0.25ns。
深入理解计算机系统-2024-07-24-21-56-31
上面的程序是实现长度为n的向量的前置和的功能，第二个函数进行了一部分循环展开。
深入理解计算机系统-2024-07-24-21-57-23
两个函数的运行时间分别近似于 $368+9n$ 和 $368+6n$ ，前面的常数是代码计时和初始化过程、准备循环以及完成过程的开销为368个周期，后面的线性因子可以称为CPE，显然CPE越小程序性能越好。

5.3一些加快性能的方法

1.消除循环
2.减少过程调用
3.消除不必要的内存引用
4.现代处理器的指令集并行
5.循环展开
6.提高并行性

6.存储器层次结构

在前面的部分都是把存储器作为一个线性字节数组。
实际上存储器系统分为CPU寄存器,靠近cpu的小的快速的高速缓存存储器(cache),主存储器，磁盘
指令执行阶段在cpu寄存器中0个周期内就能访问到,cache中需要4~75个周期，主存中需要上百的周期，磁盘中需要几千万个周期。

6.1存储技术

6.1.1RAM和ROM

随机存取存储器分为静态和动态的。静态的(SRAM)更快更贵(几兆)，用于cache或者CPU芯片上。动态的(DRAM)容量做得更大(几千兆)，用于作为主存以及图形系统的帧缓冲区。
SRAM只要有电就会永远保持它的值
DRAM容易漏电，需要随时刷新。

DRAM封装在内存模块中。(比如目前流行的DDR(Double Data-Rate Synchronous)系列，和显存VRAM)

非易失性存储器的代表闪存(flash)基于EEPROM,其主要产品由固态硬盘(SSD),存储的程序被称为固件(firmware)。
总线的作用是将数据流在CPU和DRAM主存之间传递。是一组并行的导线，能携带地址、数据和控制信号。
CPU,总线和主存

6.1.2磁盘

以前的磁盘通常叫做机械硬盘和光盘(用磁性材料)，现在基于FLASH技术的SSD发展起来，都统一叫磁盘。
下面这张图就是计算机组成的精华
磁盘的位置

6.1.3总结

速率比较:SRAM>DRAM>磁盘

6.2局部性

局部性指的是倾向于引用邻近于其他最近引用过的数据项的数据项。比如在硬件层引入cache来保存这些数据。

6.3存储器层次结构

存储器层次结构
缓存的使用
Intel Core i7Cache层次结构

7链接

链接就是把代码和数据组合成可以在内存中加载执行的单一文件的过程。

7.1编译器驱动程序

编译器驱动程序由编译系统提供，让用户可以调用语言预处理(cpp)、编译器(cc1)、汇编器(as)和链接器(ld)。

gcc -Og -o prog main.c sum.c #调用所有

#下面是分解步骤
cpp main.c /tmp/main.i #C预处理器将main.c翻译成ASCII码中间文件main.i
cc1 /tmp/main.i -Og -o /tmp/main.s #C编译器将main.i翻译成ASCII汇编文件main.s
as /tmp/main.s -o /tmp/main.o /tmp/main.s #汇编器将main.s翻译成可重定位目标文件main.o
ld -o  prog /tmp/main.o  /tmp/sum.o #链接器将main.o和sum.o以及一些必要的系统目标文件组合起来创建一个可执行目标文件prog

#执行 
./prog #加载器将prog中的代码和数据复制到内存中，然后将控制转移到这个程序的开头。

静态链接

7.2各名词和文件解释

静态链接器(ld)以一组可重定位目标文件和命令行参数作为输入，生成一个完全链接的、可以加载和运行的可执行目标文件作为输出。ld有两个任务：①符号解析②重定位
针对这个定义中的各个名词如下做出解释

7.2.1目标文件

目标文件都是二进制代码和数据，但是具有不同的作用。
定义中存在2种目标文件：可重定位目标文件和可执行目标文件。还存在第3种目标文件：共享目标文件。

7.2.1.1可重定位目标文件

顾名思义，可重定位目标文件是一个可以与其他可重定位目标文件合并起来的文件。
ELF头描述生成该文件的系统的字的大小和字节顺序。剩下的部分帮助ld语法分析和解释目标文件的信息。
信息主要有ELF头的大小，目标文件的类型，机器类型，节点头部表的文件偏移等。

.text:已编译程序的机器代码
.rodata:只读数据
.data:已初始化的全局和静态C变量
.bss:未初始化的全局和静态C变量
.symtab:一个符号表，它包含了程序中定义和引用的函数和全局变量的信息
.rel.text:一个重定位表，它包含了.text部分中的位置，这些位置需要在链接时被修改
.rel.data:一个重定位表，它包含了.data部分中的位置，这些位置需要在链接时被修改
.debug:一个调试符号表 (-g选项才有)
.line:原始C源程序中的行号与.text节中的机器指令之间的映射。(-g选项才有)
.strtab:一个字符串表，它包含了程序中引用的所有字符串

7.2.1.2可执行目标文件

典型的ELF可执行目标文件
Linux程序都有一个运行时内存映像：代码段总是从地址0x400000开始，后面是数据段，堆在数据段之后通过调用malloc库往上增长，堆后面的区域是为共享模块(后面介绍的动态链接)保留的。用户栈总是从最大的合法用户地址( $2^48-1$ )开始的，向较小内存地址增长。从地址 $2^48-1$ 开始时为内核(操作系统驻留内存的部分)中的代码和数据保留的。
Linuxx86-64运行时内存映像
加载器运行时，加载器跳转到程序的入口点，也就是_start函数的地址。

_start函数是在系统目标文件ctrl.o中定义的，_start函数调用系统启动函数__libc_start_main，该函数定义在libc.so中。它初始化执行环境，调用用户层的main函数，处理main函数中的返回值，并且在需要的时候把控制返回给内核。

7.3动态链接共享库

前面介绍了静态链接通过可重定位目标文件组合，但是几乎每个C程序会层层调用其他的标准库函数，如果全都使用静态链接生成的可执行文件非常巨大，造成内存资源的浪费。共享库是在运行或加载时进入内存的，冰河一个内存中的程序链接起来，用.so后缀表示，windows中用DLL表示。
一个库只有一个.so文件，所有引用该库的可执行目标文件共享这个文件。
动态链接共享库

8异常控制流

程序计数器假设一个值的序列 $a_0,a_1,...a_{n-1}$ ，其中 $a_k$ 是某个相应指令 $I_k$ 的地址。从 $a_k$ 到 $a_{k+1}$ 的过渡称为控制转移。控制转移的序列叫做cpu的控制流。
程序跳转、调用和返回这些指令叫做平滑流的突变( $I_k$ 和 $I_{k+1}$ 是不连续的)。

系统对系统状态的变化做出反应，通过使控制流发生突变来对这些情况做出反应，对于这种突变叫做异常控制流(ECF)。

比如硬件层：硬件检测到的事件会触发控制突然转移到异常处理程序；
在操作系统层：内核通过上下文切换将控制从一个用户进程转移到另一个用户进程；
在应用层：一个进程可以发送信号到另一个进程，而接收者会将控制转移到它的一个信号处理程序。

8.1异常

异常用来相应cpu状态中的某些变化。是异常控制流的一种形式，一部分由硬件实现，一部分由操作系统实现。
比如，cpu正在处理当前指令 $I_{curr}$ 时状态发生了一个重要的变化，该状态变化称为事件(event)。比如虚拟内存缺页，算术溢出、一个系统定时器产生信号等。
检测到事件发生时，通过异常表进行一个过程调用到异常处理子程序中进行处理。完成处理后会根据类型返回异常发生时的指令或者下一条指令或者直接终止程序。

在系统启动时，操作系统分配和初始化一张异常表，每个异常都分配唯一的非负整数异常号,一些是cpu设计者分配，一些事操作系统内核分配。

异常处理程序运行在内核模式。
类别有：中断(interrupt)，陷阱(trap),故障(fault)和终止(abort)
异常类别

8.2进程

异常是进程概念的基本构造块,进程是计算机科学中最成功的概念之一。
进程就是一个执行中的程序的实例。进程的上下文就是程序运行所需的状态组成，包括内存中的代码和数据。
逻辑控制流就是单个进程的程序计数器的PC值序列。

并发流就是一个逻辑流的执行在时间上与另一个流重叠，这两个逻辑流并发地运行
多个流并发地执行称为并发，一个进程和其他进程轮流运行叫做多任务,一个进程执行它地控制流的一部分的每一时间段叫做时间片，多任务也叫做时间分片

并行流是并发流的一个真子集，意思是两个流并发地运行在不同处理器核或者计算机上。
每个进程都有私有地址空间,为了限制应用可以执行地指令以及可以访问地地址空间范围，cpu通过控制寄存器的一个模式位来区分用户模式(用户进程运行)和内核模式(操作系统运行)。

应用程序进程从用户模式变为内核模式的唯一方法是通过中断、故障或者陷入系统调用。
Linux通过/proc文件系统允许用户模式进程访问内核数据结构的内容，/proc文件系统将许多内核数据结构输出位一个用户程序可以读的文本文件层次结构，比如用/proc文件系统找出一般的系统属性，cpu类型/proc/cpuinfo，某个特殊进程使用的内存段/proc//maps。Linux后续引入的/sys文件系统也可以输出系统总线核设备的额外低层信息。
操作系统内核使用一种称为上下文切换的高层形式的异常控制流来实现多任务，内核为每个进程维持一个上下文,内核抢占当前进程重新开始之前被抢占了的进程,该决策叫做调度，内核中的调度器进行处理。
进程上下文切换

8.3进程控制

Unix提供了大量从C程序中操作进程的系统调用，比如获取进程id，创建新进程，终止进程，回收子进程，让进程休眠，加载并运行新的程序等。

#include <sys/types.h>
#include <unistd.h>
pid_t getpid(void);
pid_t getppid(void);

pid_t fork(void);

#include<stdlib.h>
void exit(int status);

#include <sys/types.h>
#include <sys/wait.h>
pid_t waitpid(pid_t pid, int *statusp, int options);

#include <unistd.h>
unsigned int sleep(unsigned int secs);
int pause(void)

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

8.4信号

Linux信号更高层次的异常,允许进程和内核中断其他进程。信号通知系统中发生了某种类型的事件，比如Ctrl+C会给前台进程组中的每个进程发送一个SIGINT信号。

信号有很多术语：

发送信号表示内核通过更新目的进程上下文中的某个状态，发送一个信号给目的进程。
接收信号表示目的进程被内核强迫以某种方式对信号的发送做出反应。
待处理信号表示发出而没有被接收的信号。
进程组由一个正整数进程组ID(pgid)来标识，每个进程都只属于一个进程组，子进程和它的父进程同属于一个进程组。

/bin/kill -9 15213  #发送信号9(SIGKILL)给进程15213 
/bin/kill -9 -15213  #发送信号9(SIGKILL)给进程组15213的所有进程

作业表示shell中对一条命令行求值而创建的进程比如下面的命令表示由运行ls程序的进程和运行sort程序的进程组成的前台作业，这两个进程通过unix管道连接。

ls | sort

前台和后台进程组
Ctrl+C发送SIGINT信号到前台进程组所有进程中，Ctrl+Z发送SIGTSTP信号到前台前台进程组所有进程中。
信号处理程序可以被其他信号处理程序中断
隐式阻塞机制就是内核默认阻塞任何当前处理程序正在处理信号类型的待处理信号。比如捕获信号s，S程序正在处理时，发送过来的另一个信号s不会被接收。
显式阻塞机制就是可以使用sigprocmask函数和它的辅助函数明确地阻塞和接触阻塞选定地信号。

8.5非本地跳转

C语言提供了一种用户级异常控制流形式称为非本地跳转，将控制直接从一个函数转移到另一个正在执行的函数，不需要经过正常的调用-返回序列，用setjmp,longjmp函数来提供。

9虚拟内存

为了有效管理内存避免出错，现代系统提供了对主存的抽象概念叫做虚拟内存(VM),它为每个进程提供了一个大的、一致的和私有的地址空间.

①将主存看成一个存储在磁盘上的地址空间的高速缓存,在主存中只保存活动区域, 并根据需要在磁盘和主存之间来回传送数据.
②为每个进程提供了一致的地址空间
③保护每个进程的地址空间不被其他进程破坏
早期PC使用物理寻址,现在dsp,mcu和一些超级计算机仍然使用这种方式,现在处理器使用的是虚拟寻址,CPU生成一个虚拟地址访问主存,虚拟地址送到内存前转换成物理地址,该过程叫做地址翻译,相应的CPU上的硬件叫做内存管理单元(MMU)

物理地址空间是一个非负整数地址的有序集合, ${0,1,2,....M-1}$ ,如果整数连续叫做线性地址空间.CPU从 $N=2^n$ 个地址的物理地址空间中生成虚拟地址,称为虚拟地址空间 ${0,1,2,...,N-1}$ .

虚拟内存被组织为一个存放在磁盘上的N个连续的字节大小的单元组成的数组.但是磁盘上的数据被分割成块,这些块与主存进行数据交互,并不完全连续.所以VM系统将虚拟内存也分割为虚拟页(VP)大小固定的块来处理问题,每个虚拟页的大小为 $P=2^p$ 字节,物理内存分割为物理页(PP)/页帧大小也为P字节.
虚拟页分为三种:①未分配的:不占用磁盘空间;②缓存的:已缓存在物理内存中的已分配页③未缓存在物理内存中的已分配页.
VM系统使用主存作为缓存
在物理内存中存放着叫做页表的数据结构,页表将虚拟页映射到物理页,页表条目(PTE)中的有效位表明该虚拟页是否被缓存在DRAM中。

DRAM缓存不命中称为缺页,比如CPU引用VP3中的一个字,但是VP3并未缓存在DRAM中,从而触发缺页异常.
VM缺页
缺页处理程序选择VP4作为牺牲页,用VP3的副本取代它
缺页之后选择牺牲页
磁盘与内存之间的传送页的活动叫做页面调度
页面命中

对于32位地址空间、4KB的页面和4字节的PTE，也总是需要4MB( $2^20$ 个页面的PTE)的页表驻留在内存中，如果地址空间为64位，那么问题会更加严重(超过1EB的页表)。
多级页表用于解决这个问题，如下图，一级页表中的每个PTE负责虚拟地址空间的一个一个4MB的片(chunk),每个片都由1024个连续的页面组成。只有一级页表和经常使用的二级页表总是存放在内存中，典型的程序虚拟地址空间大部分都是未分配的，所以其二级页表根本不会存在。
两级页表
k级页表将虚拟地址划分为k个VPN(虚拟页号)和1个VPO(虚拟页偏移)。

9.1Intel Corei7内存系统研究

Core i7地址翻译
知道地址翻译后就够填补内核虚拟内存的细节了。其包含内核代码和数据结构，和被映射所有进程共享的物理页面，还有包含与该进程相关的数据结构。
一个Linux进程的虚拟内存

task_struct为进程的任务结构，包含内核运行该进程所需要的所有信息(PID等)
mm_struct描述了虚拟内存的当前状态，比如pgd指向第一级页表(页全局目录)的基址和mmap指向一个vm_area_struct(区域结构)的链表
vm_area_struct描述了当前虚拟地址空间的一个区域。
vm_start:指向这个区域的起始处。
vm_end ：指向这个区域的结束处。
vm_prot:描述这个区域内包含的所有页的读写许可权限。
vm_flags: 描述这个区域内的页面是与其他进程共享的，还是这个进程私有的(还描述了其他一些信息)。
vm_next:指向链表中下一个区域结构。

9.2内存映射

内存映射就是将一个虚拟内存区域与一个磁盘上的对象(object)关联起来，以初始化这个虚拟内存区域的内容。

存在两种类型对象：

linux文件系统中的普通文件:一个区域可以映射到一个普通磁盘文件的连续部分，例如一个可执行目标文件。文件区(section)被分成页大小的片，每一片包含一个虚拟页面的初始内容。因为按需进行页面调度，所以这些虚拟页面没有实际交换进入物理内存，直到CPU第一次引用到页面。(也就是把磁盘中的一个连续地址区域作为文件区,每个区根据虚拟页大小切分为很多片)
匿名文件：一个区域也可以映射到一个匿名文件，匿名文件是由内核创建的，包含的全是二进制零。

一旦一个虚拟页面被初始化了，他就在内核维护的专门的交换文件之间换来换去，交换文件也叫做交换空间。

9.2.1共享对象

共享对象就是将一个对象映射到虚拟内存的一个区域。

写时复制就是针对私有对象的映射方法，当进程试图写私有区域中的某个页面，就会在物理内存中创建这个页面的一个副本，在这个副本上进行写操作。
私有对象写时复制
所以当使用fork函数时，内核为新进程在虚拟内存中创建当前进程的原样副本，通过写时复制记录修改。
用户可以通过mmap函数完成内存映射

void *mmap(void *start,size_t length,int prot,int flags, int fd,off_t offset);

mmap参数可视化解释

9.2.2动态内存分配

动态内存分配器具有更好的可移植性,其维护着虚拟内存的堆区域,分配器将堆视为一组不同大小的块的集合，每个块就是一个连续的虚拟内存片,有两种状态:已分配和未分配。

9.2.3碎片

碎片表示不满足分配请求的未使用内存。分为内部碎片和外部碎片。内部碎片是已分配块比有效载荷大时发生(分配的内存大于需要的内存);外部碎片就是空闲内存合计起来足够满足一个分配请求

9.2.4隐式空闲链表

简单堆块的格式
将下图所示的结构称为隐式空闲链表,即将堆组织成一个连续的已分配块和空闲块的序列，阴影部分为已分配块，没有阴影的部分时空闲块。
隐式空闲链表组织堆

10 系统级I/O

输入/输出是主存和外部设备之间复制数据的过程。

10.1UnixI/O

一个linux文件就是一个m个字节的序列:

B_0,B_1,B_2,...,B_{m-1}

所有的I/O设备都被模型化为文件，而所有的输入和输出都被当做对相应的文件的读和写来执行。该方式允许Linux内核引出一个简单、低级的接口，称为Unix I/O。

10.2文件

每个Linux文件都有一个类型来表明它在系统中的角色。文件类型有：

普通文件：分为文本文件(只含有ASCII或者Unicode字符的普通文件)和二进制文件(所有其他文件)
目录：包含一组链接，每个链接都将一个文件名映射到一个文件,.是到该目录自身的链接，..是父目录的链接。
套接字：与另一个进程进行跨网络通信的文件
命名管道，符号链接，字符和块设备

10.3文件操作

打开和关闭文件： open将文件名转换为一个文件描述符，close关闭已打开的文件。
读和写文件：read和write函数将数据从文件复制到内存，或者从内存复制到文件。
读取文件元数据(文件的信息)：stat和fstat函数读取文件信息。
读取目录内容：readdir函数读取目录内容。

10.4共享文件

内核用三个相关的数据结构来表示打开的文件：描述符，文件表，v-node表
典型的打开文件的内核数据结构
打开同一个文件两次。
文件共享

10.4I/O重定向

I/O重定向允许将磁盘文件和标准输入输出联系起来，例如ls > foo.txt，让shell加载执行ls程序，同时将标准输出重定向到磁盘文件·foo.txt`。
其原理采用dup2函数完成，如下图，使用dup2(4,1)将fd4指向fd1指向的文件，
调用dup2(4,1)重定向标准输出之后的内核数据结构

10.5标准I/O

UnixI/O的较高级别替代就是标准I/O,libc库中提供了fopen,fclose,fread,fwrite,fgets,fputs,scanf,printf。
标准I/O库将一个打开的文件模型化为一个流。一个流就是一个指向FILE类型结构的指针。每个ANSI C程序开始时都有三个打开的流stdin,stdout和stderr。

类型为FILE的流时对文件描述符和流缓冲区的抽象,流缓冲区是为了使开销较高的Linux I/O系统调用的数量尽可能得小(例如getc函数的作用是返回文件的下一个字符，先调用一次read函数把大量的字符放入缓冲区中，后面的getc函数就不再调用read函数，而是直接读缓冲区的值)
I/O包之间的关系如下图，Unix IO在操作系统内核中实现，RIO和IO都是封装Unix IO实现的，RIO 函数是专为《深入理解计算机系统》这本书开发的read和write的健壮的包装函数
Unix IO,标准IO，RIO之间的关系

11 网络编程

11.1 客户端-服务器模型

每个网络应用都是基于客户端-服务器模型的，该模型中的基本操作是事务,流程如下
一个客户端-服务器事务
客户端和服务器都是进程而不是机器。

11.2 网络

对主机，网络只是一种I/O设备。

11.3 套接字接口

套接字接口是一组函数，和Unix I/O函数结合起来，用以创建网络应用,下图是典型的客户端-服务器事务的上下文中的套接字接口概述。
基于套接字接口的网络应用
客户端服务器通过socket函数来创建一个套接字描述符，用connect函数来简历和服务器的连接；服务器用bind将服务器套接字地址和套接字描述符联系起来;listen函数告诉内核该进程是服务器，将sockfd从主动套接字转化为一个监听套接字。服务器用accept函数等待客户端的连接请求。