Table of contents

计算机系统漫游

信息就是位+上下文

程序被其他程序翻译成不同的格式

hello程序的生命周期是从一个高级C语言开始的，因为这种形式能够被人读懂。然而，为了在系统上运行hello.c程序，每条C诗句都必须被其他程序转化为一系列的低级机器语言指令。然后这些指令按照一种称为可执行目标程序的格式打好包，并以二进制磁盘文件的形式存放起来。目标程序也称为可执行目标文件。

了解编译系统如何工作是大有益处的

优化程序性能

理解链接时出现的错误

避免安全漏洞

处理器读并解释储存在中的指令

系统的硬件组成

  • 总线
  • I/O设备
  • 主存

  • 处理器

    • 加载
    • 存储
    • 操作
    • 跳转

高速缓存至关重要

存储设备形成层次结构

在处理器和一个较大较慢的设备（例如主存）之间插入一个更小更快的存储设备（例如高速红艳艳）的想法已经成为一个普通的观念。实际上，每个计算机系统中的存储设备都被组织成了一个存储器层次结构，在这个层次结构中， 从上至下，设备的访问速度起来越慢，容量越来越大，并且每字节的造价也越来越便宜。

操作系统管理硬件

所有应用程序对硬件的操作深度都必须通过操作系统。

操作系统有两个基本功能

  1. 防止硬件被失控的应用程序滥用
  2. 向应用程序提供简单一致的机制来控制复杂而又通常大不相同的低级硬件设备。

操作系统通过几个基本的抽象概念来实现这两个功能

  1. 进程进程则是对处理器、主存和I/O设备的抽象表示。
  2. 虚拟内存虚拟内存是对主存和磁盘I/O设备的抽象表示
  3. 文件文件是对I/O设备的抽象表示
  • 进程
  • 线程

  • 虚拟内存

    虚拟内存是一个抽象概念，它为每个进程提供了一个假象，即每个进程都在独占地使用主存。每个进程看到的内存都是一致的，称为虚拟地址空间。在Linux中，地址空间最上面的区域是保留给操作系统中的代码和数据的，这对所有进程来说都是一样。地址空间的底部区域存放用户进程定义的代码和数据。注意，地址是从下往上增大的。从下往上依次是：

    1. 程序代码和数据。
    2. 堆
    3. 共享库
    4. 栈
    5. 内核虚拟内存

  • 文件

    文件就是字节序列，每个I/O设备，包括磁盘、键盘、显示器，甚至网络，都可以看成是文件。

系统之间利用网络通信

程序结构和执行

信息的表示和处理

信息存储

  • 十六进制表示法
  • 字数据大小

  • 寻址和字节顺序

    大端法小端法

  • 表示字符串

    C语言中字符串被编码为一个以null(其值为0)字符结尾的字符数组。每个字符都同某个标准编码来表示，最常见的是ASCII字符码。

  • 表示代码

  • 布尔代数简介

    二进制值是计算机编码、存储和操作信息的核心，所以围绕数值0和1的研究已经深化出了丰富的数学知识体系。被称作布尔代数。

  • C语言中的位级运算

    1. |
    2. &
    3. ^

  • C语言中的逻辑运算

    • 类型

      1. ||
      2. &&
      3. !

    • 与位级运算的区别

      1. 逻辑运算认为所有非零的参数都表示TRUE，而参数0表示FALSE
      2. 逻辑运算符&&和||与它们对应的位级运算&和|之间第三个重要的区别是，如果对第一个参数求值就能确定表达式的结果，那么逻辑运算符就不会对第二个参数求值。

  • C语言中的移位运算

    • 类型

      1. <<
      2. >>
      3. >>>

整数表示

  • 一些术语
    符号 类型 含义
    B2T_w 函数 二进制转补码
    B2U_w 函数 二进制转无符号数
    U2B_w 函数 无符号数转二进制
    U2T_w 函数 无符号转补码
    T2B_w 函数 补码转二进制
    T2U_w 函数 补码转无符号数
    TMin_w 常数 最小补码值
    TMax_w 常数 最大补码值
    UMax_w 常数 最大无符号数
    +^t_w 操作 补码加法
    +^u_w 操作 无符号数加法
    *^t_w 操作 补码乘法
    *^u_w 操作 无符号乘法
    -^t_w 操作 补码取反
    -^u_w 操作 无符号取反

  • 整数数据类型

    C语言支持多种整形数据类型——表示有限范围的整数。每种类型都能用关键字来指定大小，这些关键字包括char、short、long，同时还可以指示被表示的数字是非负数(声明为unsigned),歌者可能是负数（默认）。

  • 无符号数的编码

  • 补码编码

    最常见的有符号数的计算机表示方式誻补码形式。在这个定义中，将字的最高有效位解释为负权。补码的范围是不对称的： |TMin| = |TMax| + 1, 也就是说，TMin没有与之对应的正数。最大的无符号数值刚好比补码的最大值的两倍大一点： UMax = 2TMax + 1。 C语言标准并没有要求要用补码形式来表示有符号整数，但是几乎所有的机器都是这么做的。 C库中的文件 <limits.h>定义了一组常量，来限定编译器运行的这台机器的不同整形数据类型的取值范围。 ISOC99标准在文件stdint.h中引入了这个整数类型类。这个文件定义了一组数据类型，它们的声明形式如intN_t和uintN_t,对应不同的N值指定N位有称号和无符号整数。关于整数数据类型的范围和表示，Java标准是非常明确的。它要求采用补码表示。在Java中，单字节数据类型称为byte,而不是char。这些非常具体的要求都是为了保证无论在什么机器上运行，Java程序都能表现地完全一样。

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

    C语言允许在各种不同的数字数据类型之间做强制类型转换。对于大多数C语言的实现，处理同样字长的有符号数和无符号数之间的转换的一般规则是：数值可能会改变，但是位模式不变。

  • C语言中的有符号数与无符号数

    C语言支持所有整形数据类型的有符号和无符号运算。尽管C语言标准i同有指定有符号数要采用某种表示，但是几乎所有的机器都使用补码。 C语言允许无符号数和有符号数之间的转换。虽然C标准没有精确规定应如何进行这种转换，但大多数系统遵循的原则是底层的位表示保持不变。另外，当一种类型的表达式被赋值给另外一种类型的变量时，转换是隐式发生的。

  • 扩展一个数字的位表示
  • 截断数字
  • 关于有符号数与无符号数的建议

整数运算

  • 无符号加法

    当执行C程序时， 不会将溢出作为错误而发信号。不过有的时候，我们可能希望判定是否发生的溢出。

  • 补码加法

  • 补码的非

    对于w位的补码加法来说， TMin是自己的加法的逆，而对其他任何数值x都有-x作为基加法的逆。

  • 无符号乘法

    C语言中的无符号乘法被定义为产生w位的值，就是2w位的整数税种的低w从头再来表示的值。

  • 补码乘法

  • 乘以常数

    由于整数乘法比移位和加法的代价要大得多，许多C语言编译器试图以移位、加法和减法的组和来消除很多整数乘以常数的情况。

  • 除以2的幂

    除以2的幂也可以用移位运算来实现，只不过我们用的是右移，而不是左移。

  • 关于整数运算的最后思考

浮点数

浮点数表示对形如V=x*2^y的有理数进行编码。它对执行涉及非常大的数字、非常接近于0的数字，以及更普遍地作为实数运算的近似值的计算，是很有用的。

  • 二进制小数

    数字权的与十进制的小数点符号相关，这意味着小数点左边的数字的权是10的正幂，得到整数值，而小数点右边的数字的权是10的负幂，得到小数值。假定我们公考虑有限长度的编码，那么十进制表示法不能准确地表达像三分之一这样的数。类似，小数的二进制表示法只能表示那些能够被写成x*2^y的数。其他的值只能够被近似的表示。

  • IEEE浮点表示

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

    1. 符号sign: s决定这个ovtj是负数还是正数
    2. 尾数significand M是一个二进制小数
    3. 阶码 exponent E的作用是对浮点数加权，这个权重是2的E次幂（可能是负数）。

    • 表示的数值类型

      1. 规格化的值这是最普遍的情况，当exp的位模式既不全为0,也不全为1
      2. 非规格化的值当阶码哉为全0时
      3. 特殊值当阶码全为1的时候。当小数域全为0时，得到的值表示无穷，当s=0时是正无穷，当s=1时为负无穷。
  • 数字示例

  • 舍入

    因为表示方法限制了浮点数的范围和精度，所以浮点运算只能挖地表示实数运算。因此，对于值x,我们一般想用一种系统的方法，能够找到“最接近的”匹配值x’，它可以用期望的浮点形式表示出来。这就是舍入运算的任务。

  • 浮点运算

    浮点加法不具有结合性。激战加法满足了单调性。

  • C语言中的浮点数

    所有的C语言版本提供了两种不同的浮点数据类型:float和double。

    • 当int, float和double格式之间进行强制类型转换时，程序改变数值和位模式的原则如下（假设int是32位的）

      • 从int转换成float,数字不会溢出，但是可能被舍入。
      • 从int或float转换成double,因为double有更大的范围，也有更高的精度，所以能够保留精确的数值。
      • 从double转换成float,因为范围要小一些，所以值可能溢出成正无穷或负无穷。另外，由于精确度较小，它还可能被舍入。
      • 从float或者double转换成int,值将会向零舍入。例如1.99将被转换成1,而-1.99将被转换成-1。

程序的机器级表示

程序编码

  • 机器级代码

    汇编代码表示非常接近于机器代码。与机器代码的二进格式相比，汇编代码的主要特点是它用可读性更好的文本格式表示。一条机器指令只执行一个基本的操作。

  • 示例

    1. 查看C语言编译器产生的汇编代码 
      gcc -Og -S filename.c
    2. 汇编代码 
      gcc -Og -c filename.c
    3. 生成可执行文件 
      gcc -Og -p prog file1.c file2.c
    4. 反汇编 
      objdump -d program.o

  • 关于格式的注解

    gcc产生的汇编代码中所有以.形状的行都是指导汇编器和链接器工作的伪指令。我们通常可以忽略这些行。

数据格式

由于是从16位体系结构扩展成32位的，Intel用术语“字（word）”表示16位数据类型。因此，称32位数为“双字（double word）”， 64位数为“四字（quad word）”

C声明 Intel数据类型 汇编代码后缀 大小（字节
char 字节 b 1
short 字 w 2
int 双字 l 4
long 四字 q 8
char* 四字 q 8
float 单精度 s 4
double 双精度 l 8

大多数GCC生成的汇编代码指令都有一个字符的后缀，表明操作数的大小。例如：数据传送指令有四个变种：movb, movw, movl, movq

访问信息

一个x86-64的CPU包含一组16个存储64位值的通用目的寄存器。这些寄存器用来存储整数数据和指针。整数寄存器。所有16个寄存器的低位部分都可以作为字节、字（16位）、双字（32位）和四字（64位）数字来访问。

63 31 15 7 0
%rax %eax %ax %al 返回值
%rbx %ebx %bx %bl 被调用者保存
%rcx %ecx %cx %cl 第4个参数
%rdx %edx %dx %dl 第3个参数
%rsi %esi %si %sil 第2个参数
%rdi %edi %di %dil 第1个参数
%rbp %ebp %bp %bpl 被调用者保存
%rsp %esp %sp %spl 栈指针
%r8 %r8d %r8w %r8b 第5个参数
%r9 %r9d %r9w %r9b 第6个参数
%r10 %r10d %r10w %r10b 调用者保存
%r11 %r11d %r11w %r11b 调用者保存
%r12 %r12d %r12w %r12b 被调用者保存
%r13 %r13d %r13w %r13b 被调用者保存
%r14 %r14d %r14w %r14b 被调用者保存
%r15 %r15d %r15w %r15b 被调用者保存
  • 对于生成小于8字节结果的指令，寄存器中剩下的字节会怎样，对此有两条规则
    1. 生成1字节和2字节数字的指令会保持剩下的字节不变。
    2. 生成4字节数字的指令会把高4个字节置0.

  • 操作数指示符

    大多数指令有一个或多个操作数(operand)，指示出执行一个操作中要使用的源数据值，以及旋转结果的目的位置。

    • 各种不同的操作数的可能性被分为三种类型。
      1. 立即数(immediate): 用来表示常数值在ATT格式的汇编代码中，立即数的书写方式是$后面跟一个用标准C表示法表示的整数。不同的指令允许的立即数值范围不同，汇编器会自动造势最紧凑的方式进行数值编码。
      2. 寄存器(register): 它表示某个寄存器的内容 16个寄存器的低位1字节，2字节，4字节，8字节中的一个作为操作数，这些字节数分别对应于8位，16位，32位，64位。我们使用rN来表示任意寄存器N,用引用R[rN]来表示它的值，这是将寄存器集合看成一个数组R.
      3. 内存引用它会根据计算出来的地址访问某个内存位置。我们使用Mb[Addr]表示对存储在内存中从地址Addr开始的b个字节值的引用。
        • 寻址模式有多种不同的寻址模式，允许不同形式的内存引用。下表中Imm(r_b,r_i, s)表示的是最常用的形式。这样的引用有四个组成部分： 一个立即数偏移Imm,一个基址寄存器r_b,一个变址寄存器r_i和一个比例因子s,这里s必须是1,2,4或者8。基址和变址寄存器都必须是64位寄存器。有效地址被计算为Imm+R[r_b] + R[r_i] * s。操作数模式
          类型 格式 操作数值 名称
          立即数 $Imm Imm 立即数寻址
          寄存器 r_a R[r_a] 寄存器寻址
          存储器 Imm M[Imm] 绝对寻址
          存储器 (r_a) M[R[r_a]] 间接寻址
          存储器 Imm(r_b) M[Imm+R[r_b]] （基址+偏移量）寻址
          存储器 (r_b, R_i) M[R[r_b] + R[r_i]] 变址寻址
          存储器 Imm(r_b, r_i) M[Imm+R[r_b] + R[r_i]] 变址寻址
          存储器 (,r_i,s) M[R[r_i] * s] 比例变址寻址
          存储器 Imm(,r_i, s) M[Imm + R[r_i] * s] 比例变址寻址
          存储器 (r_b, r_i, s) M[R[r_b] + R[r_i] * s] 比例变址寻址
          存储器 Imm(r_b, r_i, s) M[Imm + R[r_b] + R[r_i] * s] 比例变址寻址

  • 数据传送指令

    源操作数指定的值是一个立即数，存储在寄存器中或者内存中。目的操作紵个位置，要么是一个寄存器，要么是一个内存地址。 x86-64加了一条限制，传送指令的两个操作数不能都指向内存地址。大多数情况下，MOV指令只会更新目的操作数指定的那些寄存器字节或内存位置。唯一例外的是movl指令以寄存器作为目的时，它会把该寄存器高位4字节设置为0。

    指令 效果 描述
    MOV s, D D <- S 传送
    movb 传送字节
    movw 传送字
    movl 传送双字
    movq 传送四字
    movabsq I, R R <- I 传送绝对的四字
    • MOV指令的一种可能的组合。第一个是源操作数，第二个是目的操作数。
      1. movl $0x4050, %eax Immediate - Register, 4 bytes
      2. movw %bp, %sp Register - Register, 2bytes
      3. movb (%rdi, %rcx), %al Memory - Register, 1byte
      4. movb $-17, (%rsp) Immediate - Memory, 1byte
      5. movq %rax, -12(%rbp) Register - Memory, 8bytes

    • 将较小的源值复制到较大的目的指令

      • MOVZ类

        指令会把目的中简便的字节填充为0

        指令 效果 描述
        MOVZ S, R R <- 零扩展(S) 以零扩展进行传送
        movzbw 将做了零扩展的字节传送到字
        movzbl 将做了零扩展的字节传送双字
        movzwl 将做了零扩展的字传送到双字
        movzbq 将做了零扩展的字节传送到四字
        movzwq 将做了零扩展的字传送到四字

      • MOVS

        指令通过符号扩展来填充，把源操作的最高位进行复制。

        指令 效果 描述
        MOVS S,R R <- 符号扩展（S） 传送符号扩展的字节
        movsbw 将做了符号扩展的字节传送到字
        movsbl 将做了符号扩展的字节传送到双字
        movswl 将做了符号扩展的字传送到双字
        movsbq 将做了符号扩展的字节传送到四字
        movswq 将做了符号扩展的字传送到四字
        movslq 将做了符号扩展的双字传送到四字
        cltq %rax <- 符号扩展(%eax) %eax符号扩展到%rax

  • 压入和弹出栈数据

    栈指针%rsp保存着栈顶元素的地址。

    指令 效果 描述
    pusq S R[%rsp] <- R[%rsp] - 8; M[R[%rsp]] <- S 将四字压入栈
    popq D D <- M[R[%rsp]]; R[%rsp] <- R[%rsp] + 8 将四字弹出栈

算术和逻辑操作

整数算术和逻辑操作，大多数操作都分成了指令类，这些指令类有各种带不同大小操作数的变种（只有lead没有其他大小的变种）。这些操作被分为四组：加载有效地址，一元操作，二元操作和移位。

指令 效果 描述
leaq S,D D <- &S 加载有效地址
INC D d <- d + 1 加1
DEC D D <- D - 1 减1
NEG D D <- -D 取负
NOT D D <- ~D 取补
ADD S,D D <- D + S 加
SUB S,D D <- D - S 减
IMUL S,D D <- D * S 乘
XOR S,D D <- D ^ S 异或
OR S,D D <- D 或 S 或
AND S,D D <- D & S 与
SAL K,D D <- D << K 左移
SHL K,D D <- D << K 左移（等同于SAL）
SAR K,D D <- D >> K 算术右移
SHR K,D D <- D >>> K 逻辑右移

  • 加载有效地址

    加载有效地址leaq实际上是movq指令的变形。它的指令形式是从内存读数据到寄存器但实际上它根本就没有引用内存。它的第一个操作数看上去是一个内存引用，但该指令并不是从指定的位置读入数据，而是将有效地址写入到目的操作数。

  • 一元和二元操作

    第二组中的操作是一元操作，只有一个操作数，既是源又是目的。这个操作数可以是一个寄存器，也可以是一个内存位置。第三组是二元操作，其中，第二个操作数既是源又是目的。不过，要注意，源操作数是第一个 ，目的操作数是第二个。第一个操作数可以是立即数、寄存器或是内存位置。第二个操作数可以是寄存器或是内存位置。注意，当第二个操作数为内存地址时，处理器必须从内存读出值，执行操作，再把结果写回内存。

  • 移位操作

    最后一组是移位操作，先给出移位量，然后第二项给出的是要移位的数。

  • 说明

    算术和逻辑操作的大多数指令，既可以用于无符号运算，也可以用于补码运算。只有右移操作要求区分有符号和无符号数。

  • 特殊的算术操作

    两个64位有符号整数相乘得到的乘积需要128位来表示。x86-64指令对128位（16字节）数的操作提供有限的支持。Intel把16字节的数称为八字（oct word）。支持产生两个64位数字的全128位税种以及整数除尘的指令如下：

    指令 效果 描述
    imulq S R[%rdx]: R[%rax] <- S * R[%rax] 有符号全乘法
    mulq S R[%rdx]: R[%rax] <- S * R[%rax] 无符号全乘法
    clto R[%rdx]: R[%rax] 符号扩展（R[%rax]） 转换为八字
    idivq S R[%rdx] <- R[%rdx]: R[%rax] mod S 有符号除法
    divq S R[%rdx] <- R[%rdx]: R[%rax] mod S 无符号除法

控制

  • 条件码

    除了整数寄存器，CPU还维护着一组单个位的条件码（condition code）寄存器，它们描述了最近的算术或逻辑操作的属性。可以检测这些寄存器来执行条件分支指令。最常见的条件码有：

    • CF：进位标志。阳近的操作使最高位产生了进位。可用来检查无符号操作的溢出。
    • ZF：零标志。最近的操作得出的结果为0。
    • SF：符号标志。最近的操作得到的结果为负数。
    • OF：溢出标志。最近的操作导致一个补码溢出–正溢出或负溢出。
    • 比较和测试指令
      指令 基于 描述
      CMP S1, S2 S2 - S1 比较
      cmpb 比较字节
      cmpw 比较字
      cmpl 比较双字
      cmpq 比较四字
      TEST S1, S2 S1 & S2 测试
      testb 测试字节
      testw 测试字
      testl 测试双字
      testq 测试四字

  • 访问条件码

    条件码通常不会直接读取，常用的使用方法有三种：我们将这一豆类指令称为SET指令。

    1. 可以根据条件码的某种组合，将一个字节设置为0或1,2
    2. 可以条件中转到程序的某个其他的部分
    3. 可以有条件地传送数据
    指令 同义名 效果 设置条件
    sete D setz D <- ZF 相等/零
    setne D setnz D <- ~ZF 不等/非零
    sets D D <- SF 负数
    setns D D <- ~SF 非负数
    setg D setnle D <- ~(SF ^ OF) & ~ZF 大于（有符号>）
    setge D setnl D <- ~(SF ^ OF) 大于等于（有符号>=）
    setl D setnge D <- SF ^ OF 小于（有符号<）
    setle D setng D <- (SF ^ OF) 或 ZF 小于等于（有符号<=）
    seta D setnbe D <- ~CF & ~ZF 超过（无符号>）
    setae D setnb D <- ~CF 超过或相等（无符号>=）
    setb D setnae D <- CF 低于（无符号<）
    setbe D setna D <- CF 或 ZF 低于或相等（无符号<=）

  • 跳转指令

    正常执行的情况下，指令按照它们出现的顺序一条一条地执行。跳转（jump）指令会导致执行切换到程序中一个全新的位置。这些跳转的目的地通常用一个标号（label）指明。下表列举了不同的跳转指令。jmp指令是无条件跳转。它可以是直接跳转，即跳转目标是作为指令的一部分编码的;也可以是间接跳转，即跳转目标是从寄存器或内存位置中读出的。汇编语言中，直接跳转是给出一个标号作为跳转目标的，间接跳转的写法是*后面跟一个操作数指示符。例如：jmp *%rax 用寄存器%rax中的值作为跳转目标 jmp *(%rax) 以%rax中的值作为读地址，从内存中读出跳转目标。

    指令 同义名 跳转条件 描述
    jmp Label 1 直接跳转
    jmp *Operand 1 间接跳转
    je Label jz ZF 相等/零
    jne Label jnz ~ZF 不相等/非零
    js Label SF 负数
    jns Label ~SF 非负数
    jg Label jnle ~(SF ^ OF) & ~ZF 大于
    jge Label jnl ~(SF ^ OF) 大于或等于
    jl Label jnge SF ^ OF 小于
    jle Label jng (SF ^ OF) 或 ZF 小于或等于
    ja Label jnbe ~CF & ~ZF 超过
    jae Label jnb ~CF 超过或相等
    jb Label jnae CF 低于
    jbe Label jna CF 或 ZF 低于或相等
  • 跳转指令的编码
  • 用条件控制来实现条件分支

  • 用条件传送来实现条件分支

    条件传送指令

    指令 同义名 传送条件 描述
    cmove S,R cmovz ZF 相等/零
    cmovne S,R cmovnz ~ZF 不相等/非零

  • 循环

    C语言提供了多种循环结构，即do-while，while和for。

    • do-while
    • while

    • for

      for (init-expr; test-expr; update-expr) {
  body-statement
}

      这样一个循环的行为与下面这段使用while循环的代码的行为一样

      init-expr;
while (test-expr) {
  body-statement
  update-expr;
}

  • switch语句

    switch(开关)语句可以根据一个整数索引值进行多重分支。在处理具有多种可能结果的测试时，这种语句特别有用。它们不公提高了C代码的可读性，而且通过使用跳转表(jump table)这种数据结构使得实现更加高效。和使用一组很长的if-else语句相比，使用跳转表的优点是执行开关语句的时间与开关情况的数量无关。

过程

过程是软件中一种很重要的抽象。它提供了一种封闭代码的方式，用一组指定的参数和一个可选反返回值实现了某种功能。然后，可以在程序中不同的地方调用这个函数。要提供对过程的机器级支持，必须要处理许多不同的属性。为了讨论方便，假设过程P调用过程Q,Q执行后返回到P.这些动作包括下面一个或多个机制：

  • 传递控制：在进入过程Q的时候，程序计数器必须被设置成Q的代码的起始地址，然后在返回时，要把程序计数器设置为P中调用Q后面那条指令的地址。
  • 传递数据：P必须能够向Q提供一个或多个参数，Q必须能够向P返回一个值。
  • 分配和释放内存：在开始时，Q可能需要为局部变量分配空间，而在返回前，又必须释放这些存储空间。

  • 运行时栈

    C语言过程调用机制的一个关键特性（大多数其他语言也是如此）在于使用了栈数据结构提供的后进先出的内存管理原则。在过程P调用过程Q的例子中，可以看到当Q在执行时，P以及所有在向上追溯到P的调用链中的过程，都是暂时被挂起的。当Q运行时，它只需要为局部变量分配新的存储空间，或者设置到另一个过程的调用。另一方面，当Q返回时，任何它所分配的局部存储空间都可以被释放。因此，程序可以用栈来管理它的过程所需要的存储空间，栈和程序寄存器存放着传递控制和数据、分配内存所需要的信息。当P调用Q时，控制和数据信息添加到栈尾。当P返回时，这些信息会释放掉。当X86_64过程需要的存储空间走出寄存器能够存放的大小时，就会在栈上分配空间。这个部分称为过程的栈帧(stack fram)。当前正在执行的过程的帧总是在栈顶。通过寄存器，过程P可以传递最多6个整数值（也就是指针和整数），但是如果Q需要更多的参数，P可以在调用Q之前在自己的栈帧里存储好这些参数。为了提高空间和时间效率，x86_64过程只分配自己所需要的栈帧部分。例如，许多过程有6个或者更少的参数，那么所有的参数都可以通过寄存器传递。

  • 转移控制

    将控制从函数P转移到函数Q只需要简单地把程序计数器（PC）设置为Q的代码的起始位置。不过，当稍后从Q返回的时候，处理器必须记录好它需要继续P的执行的代码位置。在x86——64机器中，这个信息是用指令call Q调用过程Q来记录的。该指令会把地址A压入栈中，并将PC设置为Q的起始地址。压入的地址A被称为返回地址，是紧跟在call指令后面的那条指令的地址。对应的指令ret会从栈中弹出地址A,并把PC设置为A. call指令有一个目标，即指明被调用过程起始的指令地址。同跳转一样，调用可以是直接，也可以是间接的。在汇编代码中，直接调用的目标是一个标号，而间接调用的目标是*后面跟一个操作数指示符。

  • 数据传送

    当调用一个过程时，除了要把控制传递给它并在过程返回时再传递回来之外，过程调用还可能包括把数据作为参数传递，而从过程返回还有可能包括返回一个值。x86-64中，大部分过程间的数据传送是通过寄存器实现的。 x86-64中，可以通过寄存器最多传递6个整形（例如整数和指针）参数。寄存器的使用是有特殊顺序的，寄存器使用的名字取决于要传递的数据类型的大小，会根据参数在参数列表中的顺序为它们分配寄存器。

    Table 1: 传递函数参数的寄存器。
    操作数据大小 1 2 3 4 5 6
    64 %rdi %rsi %rdx %rcx %r8 %r9
    32 $edi %esi %edx %ecx %r8d %r9d
    16 %di %si %dx %cx %r8w %r9w
    8 %dil %sil %dl %cl %r8b %r9b

    如果一个函数有大于6个整形参数，走出个的部分就要通过栈来传递。把参数7-N个参数放到栈上，而参数7位于栈顶。通过栈传递参数时，所有的数据大小都向8的倍数对齐。

  • 栈上的局部存储

    e 些时候，局部数据必须存放在内存中，学见的情况包括：

    • 寄存器不足够存放所有的本地数据
    • 对一个局部变量使用地址运算符’&’，因此必须能够为它产生一个地址
    • 某些局部变量是数组或结构，因此必须能够通过数组或结构引用被访问到。

  • 寄存器中的局部存储空间

    寄存器组是唯一被所有过程共享的资源。虽然在给定时刻只有一个过程是活动的，我们仍然必须确保当一个过程（调用者）调用另一个过程（被调用者）时，被调用者不会覆盖调用者稍后会使用的寄存器值。根据惯例，寄存器%rbx、%rbp和%r12-%r15被划分为被调用者保存寄存器。当过程P调用过程Q时，Q必须保存这些寄存器的值，保证它们的值在Q返回到P时与Q被调用时是一样的。过程Q保存一个寄存器的值不变，要么就是根据不去改变它，要么就是把原始值压入栈中，改变寄存器的值，然后在返回前从栈中弹出旧值。压入寄存器的值会在栈帧中创建标号为“保存的寄存器”的一部分。所有其他的寄存器，除了栈指针%rsp,都分类为调用者保存寄存器。这就意味着任何函数都能修改它们。可以这样来理解“调用者保存”这个名字：过程P在某个此类寄存器中有局部数据，然后调用过程Q。因为Q可以随意修改这个寄存器，所以在调用之前首先保存好这个数据是P（调用者）的现任。

  • 递归过程

数组分配和访问

  • 基本原则

    对于数据类型T和整形常数N,声明如下： T A[N]; 起始位置表示为x_A。这个声明有两个效果。首先，它在内存中分配一个L*N字节的连续区域，这里的L是数据类型T的大小（单位为字节）。其次，它引入了标识符A,可以用A来作为指向数组开头的指针，这个指针的值就是x_A。可以用0-N-1的整数索引来访问该数组元素。数组元素i会被存放在地址为x_A + L * i的地方。

  • 指针运算

    C语言允许对指针进行运算，而计算出来的值会根据该指针引用的数据类型的大小进行伸缩。也就是说，如果p是一个指向类型为T的数据的指针，p的值为x_p，那么表达式p + i的值为x_p + L * i，这里的L是数据类型t的大小。单操作数操作符"&“t “*“可以产生指针和间接引用指针。也就是说，对于一个表示某个对象的表达式Expr, &Expr是给出该对象地址的一个指针。对于一个表示地址的表达式AExpr, *AExpr给出该地址处的值。因此，表达式Expr和*&Expr是等价的。数组引用A[i]等同于表达式*(A + i)。

  • 嵌套的数组

  • 定长数组

    C语言编译器能够优化定长多维数组上的操作代码。

  • 变长数组

    C99允许数组的维度是表达式，在数组被分配的时候才计算出来。

异质的数据结构

C语言提供了两种将不同匠对象组合到一起创建数据类型的机制：结构(structure)，用关键字struct来声明，将多个对象集合一个单位中; 联合(union)， 用关键字union来声明，允许用几种不同的类型来引用一个对象。

  • 结构

    C语言的struct声明创建一个数据类型，将可能不同类型的对象聚合到一个对象中。用名字来引用结构的各个组成部分。类似于数组的实现，结构的所有组成部分都存放在内存中一段连续的区域内，而指向结构的指针就是结构第一个字节的地址。编译器维护关于每个结构类型的信息，指示每个字段的字节偏移。它以这些偏移作为内存引用指令中的位移，从而产生对结构元素的引用。结构的各个字段的选取完全是在编译时处理的。机器代码不包含关于字段声明或字段名字的信息。

  • 联合

    联合提供了一种方式，能够规避C语言的类型系统，允许以多种类型来引用一个对象。联合声明的语法与结构的语法一样，只不过主义相差比较大。它们是用不同的字段来引用相同的内存块。

  • 数据对齐

    许多计算机系统对基本数据类型的合法地址做出了一些限制，要求某种类型对象的地址必须是某个值K（通常是2、4、8）的倍数。这种对齐限制简化了形成处理器和内存系统之间接口的硬件设计。编译器在汇编代码中放入命令，指明僵尸数据所需的对齐。

    .align 8

    对于包含结构的代码，编译器可能需要在字段的分配中插入间隙，以保证每个结构元素都满足它的对齐要求。而结构本身对它的起始地址也有一些对齐要求。

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

    • 理解指针

      指针是C语言的一个核心特色。它们以一种统一方式，对不同数据结构中的元素产生引用。

      • 指针和它们映射到机器代码的关键原则

        • 每个指针都对应一个类型通常，如果对象类型为T,那么指针的类型为T*。特殊的void *类型代表通用指针。
        • 每个指针都有一个值。这个值是某个指定类型的对象的地址。特殊的NULL(0)值表示该指针没有指向任何地方。
        • 指针用’&‘运算符创建这个运算符可以应用到任何lvalue类的C表达式上，lvalue意指可以出现在同仁语句左边的表达式。
        • * 操作衔用于间接引用指针其结果是一个值，它的类型与该指针的类型一致。
        • 数组与指针紧密联系将指针从一种类型强制转换成另一种类型，只改变它的类型，而不改变它的值。
        • 指针也可以指向函数

    • 使用GDB调试器

      Table 2: GDB命令示例
      命令 效果
      开始和停止
      quit 退出GDB
      run 运行程序(在此给出命令行参数)
      kill 停止程序
      断点
      break multstore 在函数multstore入口处设置断点
      break * 0x400540 在地址0x400540处设置断点
      delete 1 删除断点1
      delete 删除所有断点
      执行
      stepi 执行一条指令
      stepi 4 执行4条指令
      nexti 类似于stepi,但以函数调用为单位
      continue 继续执行
      finish 运行到当前函数返回
      检查代码
      disas 反汇编当前函数
      disas multstore 反汇编函数multstore
      disas 0x400540 反汇编位于地址0x400540附近的函数
      disas 0x400540,0x40054d 反汇编指定地址范围内的代码
      print /x $rip 以十六进制输出程序计数器的值
      检查数据
      print $rax 以十进制输出%rax的内容
      print /x $rax 以十六进制输出%rax的内容
      print /t $rax 以二进制输出%rax的内容
      print 0x100 输出0x100的十进制表示
      print /x 555 输出555的十六进制表示
      print /x ($rsp + 8) 以十六进制输出%rsp的内容加上8
      print *(long *) 0x7fffffffe818 输出位于地址0x7fffffffe818的长整数
      print *(long *)($rsp + 8) 输出位于地址%rsp+8处的长整数
      x/2g 0x7fffffffe818 检查从地址0x7fffffffe818开始的双(8字节)字
      x/20bmultstore 检查函数multstore的前20个字节
      有用的信息
      info frame 有关当前栈帧的信息
      info registers 所有寄存器的值
      help 获取有关GDB的信息

    • 内存越界引用和缓冲区溢出

      C对于数组引用不进行任何边界检查，而且局部变量和状态信息（例如保存的寄存器值和返回地址）都存放在栈中。

    • 对抗缓冲区举出攻击

      1. 栈随机化栈随机化的思想使得栈的位置在程序每次运行时都有变化。在Linux系统中，栈随机化已经变成了标准行为。它是更大的一类技术中的一种，这类技术称为地址空间布局随机化（Address-Space Layout Randomization），或者简称ASLR。
      2. 栈破坏检测计算机的第二道防线是能够检测到何时栈已经被破坏。最近的GCC版本在产生的代码中加入了一种栈保护者(stack protector)机制，来检测缓冲区越界。其思想是在栈帧中任何局部缓冲区与栈状态之间存储一个特殊的金丝雀值。是在程序每次运行时随机产生的，因此，攻击同有简单的办法能够知道它是什么。在恢复寄存器状态和从函数返回之前，程序检查这个金丝雀值是否被该函数的某个操作或者该函数调用 的某个函数的某个操作改变了。如果是的，那么程序异常中止。
      3. 限制可执行代码区域

    • 支持变长栈帧

      为了管理变长栈帧，x86-64代码使用寄存器%rbp作为帧指针（frame pointer）（有时称为基指针(base pointer)，这也是%rbp中bp两个字母的由来）

浮点代码

处理器的浮点体系结构包括多个方面，会影响对浮点数据操作的程序如何被映射到机器上，包括：

  • 如何存储和访问浮点数值。通常是通过某种寄存器方式来完成
  • 对浮点数据操作的指令
  • 向函数传递浮点数参数和从函数返回浮点数结果的规则
  • 函数调用过程中保存寄存器的规则
  • 浮点传送和转换操作
  • 过程中的浮点代码
  • 浮点运算操作
  • 定义和使用浮点常数
  • 在浮点代码中使用位级操作
  • 浮点比较操作
  • 对浮点代码的观察结论

处理器体系结构

一个处理器支持的指令和指令的字节级编码称为它的指令集体系结构（Instruction-Set Architecture, ISA）

Y86-64指令集体系结构

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

  • 程序员可见的状态

    Y86-64程序中的每条指令都会读取或修改处理器状态的某些部分。这称为程序员可见状态，这里的程序员既可以是用汇编代码写程序的人，也可以是产生机器级代码的编译器。在处理器实现中，只要我们保证机器 级程序能够访问程序员可见状态，就不需要完全按照ISA暗示的方式来表示和组织这个处理器状态。

  • Y86-64指令

  • 指令编码

    • 比较CISC和最初的RISC指令集
      CISC RISC
      指令数量很多。Intel描述全套指令的文档有1200多页 指令数量少得多，通常少于100个
      有些指令的延迟很长。包括将一个整块从内存的一个部分复制到另一部分的指令，以及其他一些将多个寄存器的值复制到内存或从内存复制到多个寄存器的指令 没有较长的延迟的指令。有些早期 的RISC机器甚至没有整数乘法指令，要求编译器通过一系列g加法为实现乘法。
      编码是可变长度的。X86-64的指令长度可以是1-15个字节 编码是固定长度的。通常所有的指令都编码为4个字节
      指定操作数的方式很多样。在X86-64中，内存操作数指示符可以有许多不同的组合，这些组合由领衔量、基址和变址寄存器以及伸缩因子组成 简单寻址方式。通常只有基址和统称量寻址
      可以对内存和寄存器操作数进行算术和逻辑运算。 只能对寄存器操作数进行算术和逻辑运算，允许使用内存引用的只有load和store指令，load是从内存读到寄存器，store是从寄存器写到内存。这种方法被称为load/store体系结构
      对机器级程序来说实现细节是不可见的。ISA提供了程序和如何执行程序之间的清晰的抽象 对机器级程序来说实现细节是可见的。有些RISC机器禁止某些特殊的指令序列，而有些跳转要到下一条指令执行完了以后才会第一次。编译器必须在这些约束条件下进行性能优化。
      有条件码，作为指令执行的副产品，设置了一些特殊的标志位，可以用于条件分支检测 没有条件码。相反，对条件检测来说，要用明确的测试指令，这些指令会将测试结果放在一个普通的寄存器中。
      栈密集的过程链接。栈被用来存取过程参数和返回地址。 寄存器密集的过程链接。寄存器被用来存取过程参数和返回地址。因此有些过程能完全避免内存引用。通常处理器有更多的（最多的有32个）寄存器

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

在硬件设计中，用电子电路来计算对位进行运算的函数，以及在各种存储器单元中存储位。大多数现代电路技术都是用信号线上的高电压和低电压来表示不同的位值。要实现一个数字系统需要三个主要的组成部分：计算对位进行操作的函数的组合逻辑、存储位的存储器单元，以及控制存储器单元更新的时钟信号。

  • 逻辑门

    逻辑门是数字电路的基本计算单元。它们产生的输出，等于它们输入位值的某个布尔函数。逻辑门总是活动的。一旦一个门的输入变化了，在很短的时间内，输出就会相应的变化。

  • 组合电路和HCL布尔表达式

    将很多的逻辑门组合成一个网，就能构建计算块，称为组合电路。

    • 构建这些网有几个限制

      • 每个逻辑门的输入必须连接到下述选项之一
        1. 一个系统输入（称为主输入）
        2. 某个存储器单元的输出
        3. 某个逻辑门的输出
      • 两个或多个逻辑门的输出不能连接在一起。否则它们可能会使线上的信号矛盾，可能会导致一个不合法的电压a中电路故障。
      • 这个网必须是无环的。

  • 字级的组合电路和HCL整数表达式

    通过将逻辑门组合成大的网，可以构造出能计算更加复杂函数的组合电路。

  • 集合关系

    在处理器设计中，很多时候都需要将一个信号与许多可能匹配的信号做比较，以此来检测正在处理的某个指令代码是否属于某一类指令代码。

  • 存储器和时钟

    组合电路从本质上讲，不存储任何信息。相反，它们只是简单地响应输入信号，产生等于输入的某个函数的输出。为了产生时序电路，也就是有状态并且在这个状态上进行计算的系统，我们必须引入按位存储信息的设置。存储设备都是由同一个时钟控制的，时钟是一个周期性信号，决定什么时候要把新值加载到设軠中。

    • 考虑两类存储器设备
      • 时钟寄存器（简称寄存器）：存储单个位或字。时钟信号控制寄存器加载输入值。
      • 随机访问存储器（简称内存）存储多个字，用地址来选择该读或该写哪个字。

Y86-64的顺序实现

  • 将处理组织成阶段

    通常，处理一条指令包括很多操作。将它们组织成霜个特殊的阶段序列，即使指令的动作差异很大，但所有的指令都遵循统一的序列。每一步的具体处理取决于正在执行的指令。创建这样一个框架，我们就能够设计一个充分利用硬件的处理器。下面是关于各个阶段以及各有阶段内执行操作的简略描述：

    • 取指(fetch): 指从内存读取指令字节，地址为程序计数器（PC）的值。
    • 译码(decode):
    • 执行(execute):
    • 访存(memory):
    • 写回(write back):
    • 更新PC(PC udpate):
  • SEQ硬件结构
  • SEQ的时序
  • SEQ阶段的实现

流水线的通用原理

流水线化的一个重要我就是提高了系统的吞量，也就是单位时间内服务的顾客总数，不过它也会轻微地增加延迟，就是服务一个用户所需要的时间。

  • 计算流水线
  • 流水线操作的详细说明
  • 流水线的局限性
  • 带反馈的流水线系统

Y86-64的流水线实现

流水线冒险

优化程序性能

在程序开发和优化的过程中，我们必须考虑代码使用的方式，以及影响它的关键因素。通常程序员必须在实现和维护程序的简单性与它的运行速度之间做出权衡。研究程序的汇编代码表示是理解编译器以及产生的代码会如何运行的最有效手段之一。一个很有用的策略是只重写程序到编译器由此就能产生有效代码所需要的程度就好了。这样能尽量避免损害代码的可读性、模块性和可移植性，就好像我们使用的是具有最低能力的编译器。同样，通过测量值和检查生成的汇编代码，反复修改源代码和分析它的性能是很有帮助的。对于新手程序员来说，不断修改源代码，试图欺骗编译器产生有效的代码，看起来很奇怪，但这确实是编写很多高性能程序的方式。

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

现代编译器运用复杂精细的算法来确定一个程序中计算的是什么值，以及它们是被如何使用的。然后会利用一些机会来简化表达式，在几个不同的地方使用同一个计算，以及降低一个给定的计算必须被执行的次数。大多数编译器，包括GCC,向用户提供了一些对它们所使用的优化的控制。编译器必须很小心地对程序只使用安全的优化，也就是说对于程序可能遇到的所有可能的情况，在C语言标准提供的保证之下，优化后得到的程序和未优化的版本有一样的行为。限制编译器只进行安全的优化，消除了造成不希望的运行时行为的一些可能的原因，但是这也意味着程序员必须花费更大的力气写出编译器能够将之转换成有效机器代码的程序。

表示程序性能

我们引入试题标准每元素的周期数（Cycles Per Element, CPE），作为一种表示程序性能并指导我们改进代码的方法。CPE这种试题标准帮助我们在更细节的级别上理解迭代程序的循环性能。这样的试题标准对执行重复计算的程序来说是很适当的。处理器活动的顺序是由时钟控制的，时钟提供了某个频率的规律信号，通常用千兆赫兹（GHz），即十亿周期每秒来表示。每个时钟周期的时间是时钟频率的倒数。通常是以纳秒（nanosecond, 1纳秒等于10^-9秒）或皮秒（picosecond, 1皮秒等于10^-12秒）为单位。用时钟周期来表示，度量值表示的是执行了多少条指令，而不是时钟运行得有多快。

消除循环的低效率

将在循环中不改变的代码放到循环外边。

减少过程调用

消除不必要的内存引用

理解现代处理器

  • 整体操作

    ICU从指令高速缓存（instruction cache）中读取指令，指令高速缓存是一个特殊的高速存储器，它包含最近访问的指令。当程序遇到分支时，现代处理器采用了一种分支预测的技术，处理器会猜测是否会选择分支，同时还预测分支的目的地址。指令译码逻辑接收实际的程序指令，，并将它们转换成一组基本操作（有时称为微操作）。 EU接收来自取指单元的操作。通常，每个时钟周期会接收多个操作。这些操作会被分派到一组功能单元中，它们会执行实际的操作。这些功能单元专门用来处理不同类型的操作。读写内存是由加载和存储单元实现的。在ICU中，退役单元（retirement unit）记录正在进行的处理，并确保它遵守机器级程序的顺序主义。任何对程序寄存器的更新都只会在指令退役时才会发生，只有在处理器能够确信导致这条指令的所有分支都预测正确了，才会这样做。控制操作数在执行单元间传送的最常见的机制称为寄存器重命名。

  • 功能单元的性能

    每个运算都是由以下这些数值来刻画的：一个是延迟（latency），它表示完成运算所需要的总时间，另一个是发射时间（issue time），它表示两个 连续的同类型的运算之间需要的最小时钟周期数，还有一个是容量（capactiy），它表示能够执行该运算的功能单元的数量。

  • 处理器操作的抽象模型

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

循环展开

循环展开是一种程序变换，通过增加每次迭代计算的元素的数量，减少循环的迭代次数。

提高并行性

  • 多个累积变量

    对于一个可结合和可交换的合并运算来说，比如说整数加法或乘法，我们可以通过将一组合并运算分割成两个或更多的部分，并在最后合并结果来提高性能。

  • 重新结合变换

    重新结合变换能够减少计算中关键路径上操作的数量，通过更好地利用功能单元的流水线能力得到更好的性能。

理解内存性能

  • 加载的性能

    一个包含加载操作的程序的性能既依赖于流水线的能力，也依赖于加载单元的延迟。

  • 存储的性能

    与加载操作一样，在大多数情况中，存储操作能够在完全流水线化的模式中工作，每个周期开始一条新的存储。

应用：性能提高技术

  • 优化性能的基本策略

    • 高级设计：为遇到的问题选择适当的算法和数据结构。
    • 基本编码原则
      • 消除连续的函数调用
      • 消除不必要的内存引用
    • 低级优化
      • 展开循环
      • 通过使用例如多个累积变量和重新结合等技术，找到方法提高指令级并行
      • 用功能性的风格重写条件操作，使得编译采用条件数据传送

确认和消除性能瓶颈

  • 程序剖析

    程序剖析（profiling）运行程序的一个版本，其中插入了工具代码，以确定程序的各个部分需要多少时间。剖析的一个有力之处在于可以在现实的基准数据（benchmark data）上运行实际程序的同时，进行剖析。 Unix系统提供了一个剖析程序GPROF.

  • 使用剖析程序来指导优化

存储器层次结构

到目前为止，在对系统的研究中，我们依赖于一个简单的计算机系统模型，CPU执行指令，而存储器系统为CPU存放指令和数据。实际上，存储器系统是一个具有不同容量、成本和访问时间的存储设备的层次结构。CPU寄存器保存着最常用的数据。靠近CPU的小的、快速的调整缓存存储器作为一部分存储在相对慢速的主存储器中数据和指令的缓冲区域。主存缓存存储在容量较大的、慢速磁盘上的数据，而这些磁盘常常又作为存储在通过网络连接的其他机器的磁盘或磁带上的数据的缓冲区域。作为一个程序员，你需要理解存储器层次结构，因为它对应用程序的性能有着巨大的影响。如果你的程序需要的数据是存储在CPU寄存器中，那么在指令的执行期间，在0个周期内就能访问到它们。如果存储在调整缓存中，需要4-75个周期。如果存储在主存中，需要上百个周期。而如果存储在磁盘上，需要大约几千万个周期。这不是计算机系统中一个基本而持久的思想：如果你理解了系统是如何将数据在存储器层次结构中上上下下移动的，那么你就可以编写自己的应用程序，使得它们的数据项存储在层次结构中较高的地方，在那里CPU能更快地访问到它们。这个思想轻裘缓带着计算机程序的一个称为局部性的基本属性。具有良好局部性的程序倾向于一次又一次地访问相同的数据项集合，或是倾向于访问邻近的数据项集合。

存储技术

  • 随机访问存储器 RAM

    • 静态RAM SRAM
    • 动态RAM DRAM

    • 访问主存

      数据流通过称为总线的共享电子电路在处理器和DRAM主存之间来来回回。每次CPU和主存之间的数据传送都是通过一系列步骤来完成的，这些步骤称为总线事务。读事务从主存传送数据到CPU.写事务从CPU传送数据到主存。

  • 磁盘存储

    从磁盘上读信息的时间为毫秒级，比从DRAM读慢了10万倍，比从SRAM读慢了100万倍。

    • 磁盘构造

    • 磁盘容量

      一个磁盘上可以记录的最大位数称为它的最大容量，或者简称为容量。磁盘容量是由以下技术因素决定的：

      • 记录密度：磁盘一英寸的上可以放入的位数。
      • 磁道密度：从盘片中心出发半径一英寸的段内可以有的磁道数。
      • 面密度：记录密度与磁道密度的乘积

    • 磁盘操作

      磁盘用读写头来读写储存在磁性表面的位，而读写头连接到一个传送臂一端，通过沿着半径前后移动这个传动臂，鸡翅器可以将读写头定位在盘面上的任何磁道上。这样的机械运行称为寻道。一旦读写头定位到了期望的磁道上，那么当磁道上的每个经的下面时，读写头可以感知到这个位的值，也可以修改这个位的值。三产以扇区大小的块来读写数据。对扇区的访问时间有三个主要的部分：

      • 寻道时间
      • 旋转时间
      • 传送时间

  • 固态硬盘

    固态硬盘是一种基于闪存的存储技术。固态硬盘随机访问时间比旋转磁盘要快，能耗更低，同时也更结实。不过反复写之后，闪存块会磨损，所以SSD也容易损坏。

  • 存储技术趋势

    • 不同的存储技术有不同的价格和性能折中
    • 不同存储技术的价格和性能属性以截然不同的速率变化着
    • DRAM和磁盘的性能满后于CPU的性能

局部性

一个编写良好的计算机程序常常具有良好的局部性。局部性通常有两种不同的形式：时间局部性和空间局部性。

  • 对程序数据引用的局部性

  • 取指令的局部性

    因为程序指令是存放在内存中的，CPU必须取出这些指令，所以我们也能够评价一个程序关于取指令的局部性。

  • 评价程序中局部性的一些简单原则

    • 重复引用相同变量的程序有良好的时间局部性。
    • 对于具有步长为k的引用模式的程序，步长越小，空间局部性越好。具有步长为l的引用模式的程序有很好的空间局部性。在内存中以大步长跳来跳去的程序空间局部性会很差
    • 对于取指令来说，循环有好的时间和空间局部性。循环体越小，循环迭代次数越多，局部性越好。

存储器层次结构

  • 存储器层次结构中的缓存

    层次结构中的每一层都缓存来自较低一层的数据对象。数据总是以块大小为传送单元在第K层和第K+1层之间来回复制的。

    • 缓存命中问题

      1. 缓存命中当程序需要第K+1层的某个数据对象时，它首先在当前存储在第K层的一个块中查找。如果刚好缓存在第K层中，那么就是我们所说的缓存命中。
      2. 缓存不命中如果第K层中没有缓存数据对象，那么就是我们所说的缓存不命中。当发生缓存不命中时，第K层的缓存从第K+1层缓存中取出包含对象的那个块，如果第K层的缓存已经満了，可能就会覆盖现存的一个块。覆盖一个现存的块的过程称为替换或驱逐这个块。被驱逐的这个块有时也称为牺牲块。决定该替换哪个块是由缓存的替换策略来控制的。
      3. 缓存不命中的种类
        1. 冷不命中
        2. 冲突不命中
      4. 缓存管理

高速缓存存储器

  • 通用的高速缓存存储器组织结构
  • 映射映射高速缓存
  • 组相联高速缓存
  • 全相联高速缓存
  • 有关写的问题

  • 高速缓存参数的性能影响

    1. 高速缓存大小的影响较大的高速缓存可能会提高命中率，但是使较大存储器运行得更快总是要难一些。
    2. 块大小的影响大的块有利有弊。较大的块能利用程序中可能存在的空间局部性，帮助提高命中率。不过对于给定的高速缓存大小，块越大就意味着高速缓存行数越少，这会损害时间局部性比空间局部性更好的程序中的命中率。
    3. 相联度的影响
    4. 写策略的影响

编写高速缓存友好的代码

  • 确保代码高速缓存友好的基本方法

    1. 让最常见的情况运行得快。
    2. 尽量减小每个循环内部的缓存不命中数量
    3. 将你的注意力集中在内循环上，大部分计算和内存访问都发生在这里
    4. 通过按照数据对象存储在内存中的顺序、以步长为1的来读数据，从而使得你程序中的空间局部性最大。
    5. 一旦从存储器中诗篇了一个数据对象，京尽可能多地使用它，从而使得程序跌时间局部性最大。

高速缓存对程序性能的影响

在系统上运行程序

链接

链接(linking)是将各种代码和数据片段收集并组合成为一个单一文件的过程，这个文件可被加载（复制）到内存并执行。链接可以执行于编译时（compile time），也就是在源代码被翻译成机器代码时;也可以执行于加载时（load time），也就是在程序被加载器（loader)加载到内存并执行时;甚至执行于运行时（run time）,也就是由应用程序来执行。在现代系统中，链接是由叫做链接器（linker）的程序自动执行的。链接器在软件开发中扮演着一个关键的角色，因为它们使得健康编译成为可能。

  • 理解链接器的重要性
    • 理解链接器将帮助你构造大型程序
    • 理解链接器将帮助你避免一些危险的编程错误
    • 理解链接将帮助你理解语言的作用域规则是如何实现的
    • 理解链接将帮助你理解其他重要的系统概念
    • 理解链接将使你能够利用共享库

编译器驱动程序

一个例子： gcc -Og -o prog main.c sum.c

  1. cpp(C预处理器)将源程序翻译成一个ASCII码的中间文件main.i
  2. ccl（C编译器）将main.i翻译成一个ASCII汇编语言文件main.s
  3. as（汇编器）将main.s翻译成一个可重定位目标文件main.o
  4. 经过相同的过程生成sum.o
  5. ld(链接器)将main.o和sum.o以及一些必要的系统目标文件组合起来，创建一个可执行目标文件prog

静态链接

像Linux LD程序这样的静态链接器以一组可重定位目标文件和命令行参数作为输入，生成一个完全链接的、可以加载和运行的可执行目标文件作为输出。为了构造可执行文件，链接器必须完成两个主要任务：

  • 符号解析
  • 重定位

目标文件

目标文件有三种形式：

  • 可重定位目标文件。
  • 可执行目标文件
  • 共享目标文件

可重定位目标文件

典型的ELF可重定位目标文件内容

内容 说明
ELF 头 以一个16字节的序列开始，这个序列描述了生成该文件的系统的字的大小和字节顺序。ELF头剩下的部分包含帮助链接器语法分析和解释目标文件的信息
.text 已编译程序的机器代码
.rodata 只读数据，比如printf语句中的格式串和开关语句的跳转表
.data 已初始化的全局和静态C变量
.bss 未初始化的僵尸和静态C变量，以及所有被初始化为0的全局或静态变量
.symtab 一个符号表，它存放在程序中定义和引用的函数和全局变量的信息
.rel.text 一个.text中位置的列表，当链接器把这个目标文件 和其他文件组合时，需要修改这些位置
.rel.data 被模块引用或pgyqr所有全局变量的重定位信息
.debug 一个高度符号表，其条目是程序中定义的局部变量和类型定义，程序中定义和引用的全局变量，以及原始的C源文件。只有以-g选项编译器驱动程序时，才会得到这张表。
.line 原始C源程序中的行号和.text节中机器指令之间的映射。只有以-g选项调用编译器驱动程序时，才会得到这张表
.strtab 一个字符串表，其内容包括.symtab和.debug节中的符号表，以及节头部中的节名字。字符串表就是以null结尾的字符串的序列。
节头部表

符号和符号表

每个可重定位目标模块m都有一个符号表，它包含m定义和引用的符号的信息。在链接器的上下文中，有三种不同的符号：

  • 由模块m定义并能被其他模块引用的全局符号。全局链接器符号对应于非静态的C函数和全局变量
  • 同其他模块定义并被模块m引用的全局符号。这些符号称为外部符号，对应于在其他模块中定义的非静态C函数和全局变量
  • 只被模块m定义和引用的局部符号。它们对应于带static属性的C函数和全局变量。这些符号在模块m中任何位置都可见，但是不能被其他模块引用。

符号解析

链接器解析符号引用的方法是将每个引用与它输入的可重定位目标文件的符号表中的一个确定的符号定义关联起来。对那些和引用定义在相同模块中的局部符号的引用，符号解析是非常简单明了的。编译器只允许每个模块中每个局部符号有一个定义。静态局部变量也会有本地链接器符号，编译器还要确保它们拥有唯一的名字。不过，对全局符号的引用解析就棘手得多。当编译器遇到一个不是在当前模块中定义的符号(变量或函数名)时，会假设该符号是在其他某个模块中定义的，生成一个链接器符号表条目，并把它交给链接器处理。如果链接吕在它的任何输入模块中都找不到这个被引用符号的定义，就输出一条（通常很难阅读的）错误信息并终止。

  • 链接器如何解析多重定义的全局符号

    在编译时，编译器向汇编器输出每个全局符号，或者昌强或者是弱，而汇编器把这个信息隐含地编码在可重定位目标文件的符号表里。函数和已初始化的全局变量是强符号，未初始化的全局变量是弱k答。根据强弱符号的定义，Linux链接器使用下面的规则来处理多重定义的符号名：

    1. 不允许有多个同名的强符号
    2. 如果有一个强符号和多个弱符号同名，那么选择强符号。
    3. 如果有多个弱符号同名，那么从这些弱符号中任意选择一个。这是一个细微而令人讨厌的错误，尤其是因为它只会触发链接器发出一条警告。当你怀疑有此类错误时，用像GCC-fno-common标志这样的选项调用链接器，这个选项会告诉链接器，在遇到多重定义的全局符号时，触发一个错误。或者使用-Werror选项，它会的把所有的警告都变为错误。

  • 与静态库链接

    所有的编译系统都提供一种机制，将所有相关的目标模块打包成为一个单独的文件，称为静态库（static library），它可以用做链接器的输入。当链接器构造一个输出的可执行文件时，它只复制静态库里被应用程序引用的目标模块。静态库概念被提出来，将相关的函数可以被编译为独立的目标模块，然后封装成一个单独的静态库文件。然后应用程序可以通过在命令行上指定单独的文件名字来使用这些库中定义的函数。在链接时，链接器将只复制被程序引用的目标模块，这就减少了可执行文件在磁盘和内存中的大小。在Linux系统中，静态库以一种称为存档（archive）的特殊文件格式存放在磁盘中。存档文件是一组连接起来的可重定位目标文件的集合，有一个头部用来描述每个成员目标文件的大小和位置。

  • 链接器如何使用静态库来解析引用

    虽然静态库很有用，但是它们同时b民是一个程序员迷惑的源头，原因在于Linux链接器使用它们解析外部引用的方式。在符号解析阶段，链接器从左到右按照它们在编译器驱动程序命令行上出现的顺序来扫描可重定位目标文件和存档文件。在这次扫描中，链接器维护一个可重定位目标文件的集合E, 一个未解析的符号集合U,以及一个在前面输入文件中已定义的符号集合D。初始时，E，U和D均为空。

    1. 对于命令行上的每个输入文件f,链接器会判断f是一个目标文件还是一个存档文件。如果f是一个目标文件，那么链接器把f添加到E,修改U和D来反映f中的符号定义和引用，并继续下一个输入文件。
    2. 如果f是一个存档文件，那么链接器就深度匹配U中 esrr符号和由存档文件成员定义的符号。如果某个存档文件成员m,定义了一个符号来解析U中的一个引用，那么就将m添加到E中，并且链接器修改U和D来反映m中的符号定义和引用。对存档文件中所有的成员目标文件都依次进行这个过程，直到U和D都不再发生变化。此时，任何不包含在E中的成员目标文件都简单地被丢弃，而链接器将继续处理下一个输入文件。
    3. 如果当链接器完成对命令行上输入文件的扫描后，U是非空的，那么链接器就会输出一个错误并终止。否则，它会合并和重定位E中的目标文件，构建输出的可执行文件。不幸的是，这种算法会导致一些令人困扰的链接时错误，因为命令行上的库和目标文件的顺序非常重要。在命令行中，如果定义一个符号的库出现在引用这个符号的目标文件之前，那么引用就不能被解析，链接会失败。所以，关于库的一般准则是将它们放在命令行的结尾。如果各个库的成员是相互独立的（也誻说没有成员引用另一个成员定义的符号），那么这些库就可以以任何顺序放置在命令行的结尾处。另一方面，如果库不是相互独立的，那么必须对它们排序，使得对于每个被存档文件的成员外部引用的符号s,在命令行中至少有一个s的定义是在对s的引用之后的。如果需要满足依赖需求，可以在命令行上重复库。

重定位

一旦链接器完成了符号解析这一步，就把代码中的每个符号引用和正好一个符号定义关联起来。此时，链接器就知道它的输入目标模块中的代码节和数据节的确切大小。现在就可以开始重定位步骤了，在这个步骤中，将合并输入模块，并为每个符号分配运行时地址。重定位由两步组成：

  • 重定位节和符号定义。在这一步中，链接器将所有相同类型的节合并为同一类型的新的聚合节。
  • 重定位节中的符号引用。在这一步中，链接器修改代码节和数据节中对每个符号的引用，使得它们指向正确的运行时地址。要执行这一步，链接器依赖于可重定位目标模块中称为重定位条目（relocation entry）的数据结构。

  • 重定位条目

    当汇编器生成一个目标模块时，它并不知道数据和代码最终将放在内存中的什么位置。它也不知道这个模块引用的任何外部定义的函数或者全局变量的位置。所以，无论何时汇编器遇到对最终位置未知的目标引用，它就会生成一个重定位条目，告诉链接器在将目标文件合并成可执行文件时如何修改这个引用。代码的重定位条目放在.rel.text中。已初始化数据的重定位条目放在.rel.data中。 ELF重定位条目.每个条目表示一个必须被重定位的引用，并指明如何计算被修改的引用：

    typedef struct {
     long offset;  // 需要被修改的引用的节偏移
      long type:32,   // 告知链接器如何修改新的引用
            symbol:32;  // 标识被修改引用应该指向的符号
        long addend;  // 一些类型的重定位要使用它对被修改引用的值做偏移调整
} Elf64_Rela;

    ELF定义了32种不同的重定位类型，我们只关心其中两种最基本的重定位类型：

    1. R_X86_64_PC32 重定位一个使用32位PC相对地址的引用
    2. R_X86_64_32 重定位一个使用32位绝对地址的引用

  • 重定位符号引用

    1. 重定位PC相对引用
    2. 重定位绝对引用

  • 可执行目标文件

    可执行目标文件的格式类似于可重定位目标文件的格式。ELF头描述文件的总体格式。它还包括程序的入口点，也就是当程序运行时要执行的第一条指令的地址。.text、.rodata和.data节与可重定位目标文件中的节是相似的，除了这些节已经被重定位到它们最终的运行时内存地址以外。.init节定义了一个小函数，叫做_init，程序的初始化代码会调用它。因为可执行文件是完全链接的（已被重定位），所以它不再需要.rel节。

  • 加载可执行目标文件

    在Linux shell的命令行中我们可以使用./programName的方式调用可执行目标文件 programName。因为programName不是一个内置的shell命令，所以shell会认为它是一个可执行目标文件，通过调用某个驻留在存储器中称为加载器（loader）的操作系统代码来运行它。任何Linux程序都可以通过调用execve函数来调用加载器。加载器将可执行目标文件中的代码和数据从磁盘复制到内存中，然后通过跳转到程序的第一条指令或入口点来运行该程序。这个将程序复制到内存并运行的过程叫做加载。

  • 共享链接共享库

    静态库的缺点：需要定期维护和更新，一些代码会复制到每个运行进程的广西上。是对稀缺的内存系统资源的极大浪费。共享库（shared library）是致力于解决静态库缺陷的一个现代创新产物。共享库是一个目标模块，在运行或加载时，可以加载到任意的内存地址，并和一个在内存中的程序链接起来。这个过程称为动态链接（dynamic linking）,是由一个叫做动态链接器（dynamic linker）的程序来执行的。共享库也称为共享目标（shared object)，在Linux系统中通常用.so缀来表示。微软的操作系统大师地使用了共享库，它们称为DDL。共享库是以两种不同的方式来“共享”的。

    • 首先，在任何给定的文件系统中，对于一个库只有一个.so文件。所有引用该库的可执行目标文件共享这个.so文件中的代码和数据，而不是像静态库的内容那样被复制和嵌入到引用它们的可执行的文件中。
    • 其次，在内存中，一个共享库的.text节的一个副本可以被不同的正在运行的进程共享。

    一个例子，使用共享库libvector.so: -fpic选项指示编译器生成与位置无关的代码。 -shared选项指示链接器创建一个共享的目标文件。

    gcc -shared -fpic -o libvector.so addvec.c multvec.c
  • 从应用程序中加载和链接共享库

  • 位置无关代码

    共享库的一个主要目的就是允许多个正在运行的进程共享内存中的相同的库代码，因而节约富贵的内存资源。

    • PIC数据引用

      编译器通过运用以下这个有趣的事实来生成对全局变量的PIC引用：无论我们在内存中的休息加载一个目标模块（包括共享目标模块），数据段与代码段的距离总是保持不变。因此，代码段中任何指令和数据上任何变量之间距离都是一个运行时常量，与代码段和数据wdmr绝对内存位置是无关的。想要生成对全局变量PIC引用的编译器利用了这个事实，它在数据段开始的地方创建了一个表，叫做全局统称量表（Global Offset Table, GOT）。在GOT中，每个被这个目标模块引用的全局数据目标（过程或全局变量）都有一个8字节条目。编译器还为GOT中每个条目生成一个重定位记录。在加载时，动态链接器会重定位GOT中的每个条目，使得它包含目标的正确的绝对地址。每个引用全局目标的目标模块都有自己的GOT.

    • PIC函数调用

      假设程序调用一个由共享库定义的函数。编译器没有办法预测这个函数的运行时地址，因为定义它的共享模块在运行时可以加载到任意位置。GNU编译系统使用了一种很有趣的技术来解决这个问题，称为延迟绑定(lazy binding)，将过程地址的绑定推迟到第一次调用该过程时。所以第一次调用过程的运行时开销很大，但是其后的每次调用都只会花费一条指令和一个间接的内存引用。延迟绑定是通过两个数据结构之间简洁但又有些复杂的交互来实现的，这两个数据结构是：GOT和过程链接表（Procedure Linkage Table, PLT）。如果一个目标模块调用定义在共享库中的任何函数，那么它就有自己的GOT和PLT.

  • 库打桩机制

    Linux链接器支持一很强大的技术，称为库打桩（library interpositioning)，它允许你截获对共享库函数的调用，取而代之执行自己的代码。打桩可以发生在编译时、链接时或当程序被加载和执行的运行时。

    • 编译时打桩

      在gcc时使用-I参数进行打桩

    • 链接时打桩
    • 运行时打桩

  • 处理目标文件工具

    在Linux系统中有大量可用的工具可以理解和处理目标文件。特别地，GNU binutils包尤其有帮助，而且可以运行在每个Linux上。

    • AR：创建静态库，插入、删除、列出和提取成员。
    • STRINGS：列出一个目标文件中所有可打印的字符串。
    • STRIP：从目标文件中删除符号表信息。
    • NM：列出一个目标文件符号表中定义的符号
    • SIZE：列出目标文件中节的名字和大小。
    • READELF： 显示一个目标文件的完整结构，包括ELF头中编码的所有信息。包含SIZE和NM的功能。
    • OBJDUMP：所有二进制工具之母。能够显示一个目标文件中所有的信息。它最大的作用是反汇编.text节中的二进制指令。

    Linux系统为操作共享库还提供了LDD程序：

    • LDD： 列出一个可执行文件在运行时所需要的共享库。

异常控制流

现代系统通过使控制流发生突变来对这些情况做出反应。一般而言，我们把这些突变称为异常控制流（Exceptional Control Flow, ECF）。

  • ECF的重要性

    • 理解ECF将帮助你理解重要的系统概念
    • 理解ECF将帮助你理解应用程序是如何与操作系统交互的。
    • 理解ECF将帮助你编写有趣的新应用程序。
    • 理解ECF将帮助你理解并发。
    • 理解ECF将理解软件异常如何工作。

异常

异常是异常控制流的一种形式，它一部分由硬件实现，一部分由操作系统实现。异常就是控制流中的突变，用来响应处理器状态中的某些变化。在任何情况下，当处理器检测到有事件发生时，它就会通过一张叫做异常表（exception tablee）的跳转表，进行一个间接过程调用（异常），到一个专门设计用来处理这类事件的操作系统子程序（异常处理程序（exception handler））。当异常处理程序完成处理后，根据引起异常的事件的类型，会发生以下3种情况中的一种：

  1. 处理程序将控制返回给当前指令，即当事件发生时正在执行的指令。
  2. 处理程序将控制返回给将会执行的下一条指令。
  3. 处理程序终止被中断的程序。

  • 异常处理

    系统中可能的每种类型的异常都分配了一个唯一的非负整数的异常号（exception number）。其中一些号码是由处理器的设计者分配的，其他号码是由操作系统内核的设计者分配的。当系统启动时（当计算机重启或者加电时），操作系统分配和初始化一张称为异常表的跳转表，使得K包含异常K的处理程序的地址。异常号是到异常表中的索引，异常表的起始地址放在一个叫做异常表基地址寄存器（exception table base register）的特殊CPU寄存器里。

    • 异常处理类似于过程调用，但是有一些重要的不同之处：
      • 过程调用时，在跳转到处理器程序之前，处理器将返回地址压入栈中。然后，根据异常的类型，返回地址要么是当前指令（当事件发生时正在执行的指令），要么是下一条指令（如果事件不发生，将会在当前指令后执行的指令）。
      • 处理器也把一些额外的处理器状态压到栈里，在处理程序返回时，重新开始执行被中断的程序会需要这些状态。
      • 如果控制从用户程序转移到内核，所有这些项目都被压到内核中，而不是压到用户栈中。
      • 异常处理程序运行在内核模式下，这意味着它们对所有的系统资源都有完全的访问权限。

    一旦硬件触发了异常，剩下的工作就是由异常处理程序在软件中完成。在处理程序处理完事件后，它通过执行一条特殊的“从中断返回”指令，可选地返回到被中断的程序，该指令将适当的状态绞架到处理器控制和数据寄存器中，如果异常中断的是一个用户程序，就将状态恢复为用户模式，然后将控制返回给被中断的程序。

  • 异常的类别

    异常可以分为四类：中断（interrupt），陷阱（trap），故障（fault）和终止（abort）.

    Table 3: 异常分类的属性
    类别 原因 异常/同步 返回行为
    中断 来自IO设备的信号 异步 总是返回到下一条指令
    陷阱 有意的异常 同步 总是返回到下一条指令
    故障 潜在可恢复的错误 同步 可能返回到当前指令
    终止 不可恢复的错误 同步 不会返回

    • 中断

      中断是异步发生的，是来自处理器外部的IO设备的信号的结果。硬件的中断的异常处理程序常常称为中断处理程序（interrupt handler）。剩下的异常类型（陷阱，故障和终止）是同步发生的 ，是执行当前指令的结果。我们把这类指令叫做故障指令（faulting instruction）。

    • 陷阱和系统调用

      陷阱是有意的异常，是执行一条指令的结果。就像中断处理程序一样，陷阱处理程序将控制返回到下一条指令。陷阱最重要的用途是在用户程序和内核之间提供一个像过程一样的接口，叫做系统调用。从程序员的角度来看，系统调用和普通的函数调用是一样的。然而，它们的实现非常不同。普通的函数运行在用户模式中，用户模式限制了函数可以执行的指令的类型，而且它们只能访问与调用函数相同的栈。系统调用运行在内核模式中，内核模式允许系统调用执行特权指令，并访问定义在内核中的栈。

    • 故障

      故障由错误情况引起，它可能能够被故障处理程序修正。当故障发生时，处理器将控制转移给故障处理程序。如果处理程序能够修正这个错误情况，它就将控制返回到引起故障的指令，从而重新执行它。否则，处理程序返回到内核中的abort例程，abort例程会终止引起故障的应用程序。

    • 终止

      终止是不可恢复的致命错误造成的结果，通常是一些硬件错误，比如DRAM或者SRAM位被损坏时发生的奇偶错误。终止处理程序从不将控制返回给应用程序。

  • Linux/x86-64系统中的异常

    x86-64系统定义了一些异常有高达256种，0-31的号码对应的是由Intel架构师定义的异常，因此对任何x86-64系统都是一样的。32-255的号码对应的是操作系统定义的中断和陷阱。

    • Linux/x86-64故障和终止

    • Linux/x86-64系统调用

      我们将系统调用和与它们相关联的包装函数都称为系统级函数，这两个术语可以互换使用。在x86-64系统上，系统调用 是通过一条称为syscall的陷阱指令来提供的。所有到Linux系统调用的参数都是通过通用寄存器而不是栈传递的。按照惯例，寄存器%rax包含系统调用号，寄存器%rdi、% rsi、%rdx、%10、%r8和%r9包含最多6个参数。从系统调用返回时，寄存器%rcx和%r11都会被破坏，%rax包含返回值。

      Table 4: Linux x86-64系统中常用的系统调用示例
      编号 名字 描述
      0 read 读文件
      1 write 写文件
      2 open 打开文件
      3 close 关闭文件
      4 stat 获得文件信息
      9 mmap 将内存页映射到文件
      12 brk 重置堆顶
      32 dup2 复制文件描述符
      33 pause 挂起进程直到信号到达
      37 alarm 调度告警信号的传送
      39 getpid 获得进程ID
      57 fork 创建进程
      59 execve 执行一个程序
      60 _exit 终止进程
      61 wait4 等待一个进程终止
      62 kill 发送信号到一个进程

进程

异常是允许操作系统内核提供进程（process）概念的基本构造块，进程是计算机科学中最深度、最成功的概念之一。在现代系统上运行一个程序时，我们会到一个假象，就好像我们的程序是系统中当前运行的唯一的程序一样。我们的程序好像是独占地使用处理器和内存。进程的经典定义就是一个执行中程序的实例。系统中的每个程序都运行在某个进程的上下文（context）中。上下文是由程序正确运行所需的状态组成的。它个状态包括存放在内存中的程序的代码和数据，它的栈、通用上的寄存器的内容、程序计数器、环境变量以及打开文件描述符的集合。我们将关注进程提供给应用程序的关键抽象：

  • 一个独立的控制流，它提供一个假象，好像我们的程序独占地使用处理器。
  • 一个私有的地址pwuj，它提供一个假象，好像我们的程序独占地使用内存系统。

  • 逻辑控制流

    实际上进程昌轮流使用处理器的。每个进程执行它的流的一部分，然后被抢占（preempted）(暂时挂起)，然后轮到其他进程。

  • 并发流

    一个逻辑流的执行在时间上与另一个流重叠，称为并发流（concurrent flow），这两个流被称为并发地运行。多个流并发地执行的一般现象被称为并发（concurrency）。一个进程和其他进程轮流运行的概念称为多任务（multitasking）。一个进程执行它的控制流的一部分的每一时间叫做时间片（time slice）。因此，多任务也叫做时间分片（time slicing）。如果两个流并发地运行在不同的处理器核或者计算机上，那么我们称它们为并行流（parallel flow），它们并行地运行（running in parallel），且并行地执行（parallel execution）。

  • 私有地址空间

    进程也为每个程序提供一种假象，好像它独占地使用系统地址空间。

  • 用户模型和内核模式

    为了使操作系统内核提供一个无懈可击的进程抽象，处理器必须提供一种机制，限制一个应用可以执行的指令以及它可以访问的地址空间范围。处理器通常是用某个控制寄存器中的一个模式们（mode bit）来提供这种功能的，该寄存器描述了进程当前享有的特权。当设置了模式位时，进程就运行在内核模式中（有时叫做超级用户模式）。一个运行在内核模式的进程可以执行指令集中的任何指令，并且可以访问系统中的任何内存位置。没有设置模式位时，进程就运行在用户模式中。用户模式中的进程不允许执行特权指令（privileged instruction），也不允许用户模式中的进程直接引用地址空间中内核区内的代码和数据。运行应用程序代码的进程初始时是在用户模式中的。进程从用户模式变为内核模式的唯一方法是通过诸如中断、故障或者陷入系统调用这样的异常。当异常发生时，控制传递到异常处理程序，处理器将模式从用户模式变为内核模式。 Linux提供了一种聪明的机制，叫做/proc文件系统，它允许用户模式进程访问内核数据结构的内容。/proc文件系统将许多内核数据结构的内容输出为一个用户程序可以yfnr广西文件的层次结构。

  • 上下文切换

    操作系统内核使用一种称为上下文切换（context switch）的较高层形式的异常控制流来实现多任务。内核为每个进程维持一个上下文（context）。上下文誻内核重新启动一个被抢占的进程所需的状态。安由一些对象的值组成，这些对象包括通用上的寄存器、浮点寄存器、程序计数器、用户栈、状态寄存器、内核栈和各种内核数据结构，比如描述地址空间的页表、包含有关当前进程信息的进程表，以及包含进程已打开文件的信息的文件表。在进程执行的某些时刻，内核可以决定抢占当前进程，并重新开始一个先前被抢占了的进程。这种决策就叫做调度（scheduling），是由内核中称为调试器的（scheduler）的代码处理的。在内核调度了一个新的进程运行后，它就抢占当前进程，并使用一种称为上下文切换的机制来将控制转移到新的进程。上下文切换会：

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

    当内核代表用户执行系统调用时，可能会发生上下文切换。如果系统调用因为等待某个事件发生而阻塞，那么内核可以让当前进程休眠，切换到另一个进程。

系统调用错误处理

当Unix系统级函数遇到错误时，它们通常会返回-1,并设置全局整数变量errno来表示什么出错了。

进程控制

  • 获取进程ID

    每个进程都有一个唯一的正数（非零）进程ID（PID）。getpid函数返回调用进程的PID。getppid函数返回它的父进程的PID.

      #include <sys/types.h>
#include <unistd.h>
#include <stdio.h>

int main() {
        pid_t pid = getpid();
        printf("current pid: %d\n", pid);
        return 0;
}

    getpid和getppid函数返回一个类型为pid_t的整数值，在Linux系统上它在types.h中被定义为int。

  • 创建和终止进程

    从程序员的角度来看，我们可以认为进程总是处于下面三种状态之一：

    • 运行：进程要么在CPU上运行，要么在等待被执行且最终会被内核调度。
    • 停止：进程的执行被挂起（suspended）,且不会被调试。
    • 终止：进程永远地停止了。进程会因为三种原因终止：
      • 收到一个信号，该信号的默认行为是终止进程
      • 从主程序返回
      • 调用exit函数

    • 创建进程

      父进程通过调用fork函数创建一个新的运行的子进程。新创建的子进程几乎但不完全与父进程相同。子进程得到与父进程用户级虚拟地址空间相同的（但是独立的）一份副本，包括代码和数据段、堆、共享库以及用户栈。子进程还获得与父进程任何打开文件描述符相同的副本，这就意味着当父进程调用fork时，子进程可以读写父进程打开的任何文件。父进程和新创建的子进程之间最大的区别在于它们有不同的PID. fork函数是有趣的，因为它只被调用一次，却会返回两次：一次是在调用进程（父进程）中，一次是在新创建的子进程中。在父进程中，fork函数返回子进程的PID.在子进程中，fork返回0.

  • 回收子进程

    当一个进程由于某种原因终止时，内核并不是立即把它从系统中清除。相反，进程被保持在一种已终止的状态中，直到被它的父进程回收（reaped）。当父进程回收已终止的子进程时，内核将子进程的退出状态传递给父进程，然后热度已终止的进程，从此时开始，该进程就不存在了。一个终止了但还未被回收的进程被称为僵死进程(zommbie)。如果一个父进程终止了，内核会安排init进程成为它的孤独进程的养父。一个进程可以通过调用waitpid函数来等待它的子进程终止或者停止。 waitpid函数有点复杂。默认情况下（当options=0时），waitpid挂起调用进程的执行，直到它的等待集合中的一个子进程终止。如果等待集合中的一个进程在刚调用的时刻就已经终止了，那么waitpid就立即返回。在这两种情况中，waitpid返回导致waitpid返回的已终止子进程的pid。

    1. 判断等待集合的成员等待集合的成员是由参数pid来确定的：

      • 如果Pid>0,那么等待集合就是一个单独折子进程，它的进程id等于pid。
      • 如果Pid=-1,那么等待集合就是由父进程所有的子进程组成的。

    2. 修改默认行为可以通过将options设置为常量以下值修改默认行为

      • WNOHANG
      • WUNTRACED
      • WCONTINUED

      还可以用或运算把这些选项组合起来，例如：WNOHANG | WUNTRACED

    3. 检查已回收子进程的退出状态如果statusp参数是非空的，那么waitpid京会在status中放上关于导致返回的子进程的状态信息，status是statusp指向的值。

    4. 错误条件如果调用进程没有子进程，那么waitpid返回-1,并设置errno为ECHILD。如果waitpid函数被一个信号中断，那么它返回-1,并设置errno为EINTR。

    5. wait函数 wait函数是waitpid函数的简单版本。调用wait(&status)行人于调用waitpid(-1, &status, 0)。

  • 让进程休眠

    sleep函数将一个进程挂起一段指定的时间。

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

    如果请求的时间量已经到了，sleep返回0,否则返回还剩下的要休眠的秒数。

  • 加载并运行程序

    execve函数在当前进程的上下文中加载并运行一个新程序。

    #include <unistd.h>
int execve(const char *filename, const char *argv[], const char *envp[]);

    execve函数加载并运行可执行目标文件filename,且带参数列表argv和环境变量列表envp。只有当出现错误时，例如找不到filename，execve才会返回到调用程序。所以，与fork一次调用返回两次不同，execve调用一次并从不返回。

  • 利用fork和execve运行程序

信号

一个信号就是一条小消息，它通知进程系统中发生了一个某种类型的事件。每种信号类型都对应于某种系统事件。低层的硬件异常是由内核异常处理程序处理的，正常情况下，对用户进程而言是不可见的。信号提供了一种机制，通知用户进程发生了这些异常。

Table 5: Linux信号
序号 名称 默认行为 相应事件
1 SIGHUP 终止 终端线挂断
2 SIGINT 终止 来自键盘的中断
3 SIGQUIT 终止 来自键盘的退出
4 SIGILL 终止 非法指令
5 SIGTRAP 终止并转储内存 跟踪陷阱
6 SIGABRT 终止并转储内存 来自abort函数的终止信号
7 SIGBUS 终止 总线错误
8 SIGFPE 终止并转储内存 浮点异常
9 SIGKILL 终止 杀死程序
10 SINUSR1 终止 用户定义的信号1
11 SIGSEGV 终止并转储内存 无效的内存引用（段故障）
12 SIGUSR2 终止 用户定义的信号2
13 SIGPIPE 终止 向一个没有读用户的管道做写操作
14 SIGALRM 终止 来自alarm函数的定时器信号
15 SIGTERM 终止 软件终止信号
16 SIGSTKFLT 终止 协处理器上的栈故障
17 SIGCHLD 忽略 一个子进程停止或者终止
18 SIGCONT 忽略 继续进程如果该进程停止
19 SIGSTOP 停止直到下一个SIGCONT 不是来自终端的停止信号
20 SIGTSTP 停止直到下一个SIGCONT 严自终端的停止信号
21 SIGTTIN 停止直到下一个SIGCONT 后台进程从终端读
22 SIGTTOU 停止直到下一个SIGCONT 后台进程向终端写
23 SIGURG 忽略 套接字上的紧急情况
24 SIGXCPU 终止 CPU时间限制超出
25 SIGXFSZ 终止 文件大小限制超出
26 SIGVTALRM 终止 虚拟定时器期满
27 SIGPROF 终止 剖析定时器期满
28 SIGWINCH 忽略 窗口大小变化
29 SIGIO 终止 在某个描述符上可执行IO操作
30 SIGPWR 终止 电源故障

  • 信号术语

    传送一个信号到目的进程是由两个不同步骤组成的：

    • 发送信号：内核通过更新目的进程上下文中的某个状态，发送一个信号给目的进程。
    • 接收信号：当目的进程被内核强迫以某种方式对信号的发送做出反应时，它就接收了信号。

    一个发出而没有被接收的信号叫做待处理信号。在任何时刻，一种类型至多只会有一个待处理信号。如果一个进程有一个类型为k的待处理信号，那么任何接下来发送到这个进程的类型为k的信号都不会排队等待;它们只是被简单地丢弃。一个进程可以有选择性地阻塞接收某种信号。当一种信号被阻塞时，它仍可以被发送，但是产生的待处理信号不会被接收，直到进程取消对这种信号的阻塞。一个待处理信号最多只能被接收一次。

  • 发送信号

    Unix系统提供了大量向进程发送信号的机制。所有之些机制都是基于进程组（process group）这个概念的。

    1. 进程组每个进程都只属于一个进程组，进程组是由一个正整数进程组ID来标识的。getpgrp函数返回当前进程的进程组ID 默认地，一个子进程和它的父进程同属于一个进程组。一个进程可以通过使用setpgid函数来改变自己或者其他进程的进程组。 
      #include <unistd.h>
int setpgid(pid_t pid, pid_t pgid);
      setpgid函数将进程pid的进程组改为pgid。如果pid是0,那么就使用当前进程的pid。如果pgid是0,那么就用pid指定的进程的进程的pid作为进程组ID.
    2. 用/bin/kill程序发送信号
    3. 从键盘发送信号
    4. 用kill函数发送信号进程通过调用kill函数发送信号给其他进程（包括它们自己） 
      #include <sys/types.h>
#include <signal.h>
int kill(pid_t pid, int sig);
      如果pid大于零，那么kill函数发送信号号码sig给进程pid.如果pid等于零，那么kill发送信号sig给调用进程所在进程组中的每个进程，包括调用进程自己。如果pid小于零，kill发送信号sig给进程组|pid（pid的绝对值）中的每个进程。
    5. 用alarm函数发送信号进程可以通过调用alarm函数向它自己发送SIGALRM信号 
      #include <unistd.h>
unsigned int alarm(unsigned int secs);
      alarm函数安排内核在secs秒后发送一个SIGALRM信号给调用进程。

  • 接收信号

    当内核把进程p从内核模式切换到用户模式时，它会检查p进程的未被阻塞的待处理信号的集合，如果这个集合为空，那么内核将控制传递到p的逻辑控制流中的下一条指令。如果集合是非空的，那么内核选择集合中的某个信号K（通常是最小的K），并且强制p接收信号K.收到这个信号会触发进程采取某种行为。一旦进程完成了这个行为，那么控制就传递回p的逻辑控制流中的下一条指令。每个信号类型都有一个预定义的默认行为，是下面中的一种：

    • 进程终止
    • 进程终止并转储内存
    • 进程停止（挂起）直到被SIGCONT信号重启
    • 进程忽略该信号

  • 阻塞和解除阻塞信号

    Linux提供阻塞信号的隐匿和的机制：

    • 隐式阻塞机制。内核默认阻塞任何当前处理程序正在处理信号类型的待处理的信号。
    • 显式阻塞机制。应用程序可以使用sigprocmask函数和它的辅助函数，明确地阻塞和解除阻塞选定的信号。

  • 编写信号处理程序

    信号处理是Linux系统编程最棘手的一个问题。处理程序有几个属性使得它们很难推理分析：

    1. 处理程序与主程序并发运行，共享同样的全局变量，因此可能与主程序和其他处理程序互相干扰
    2. 如何以及何时接收信号的规则常常有违人的直觉
    3. 不同的系统有不同的信号处理语义

    • 安全的信号处理

      • 一些保守的编写处理程序的原则

        • 处理程序要尽可能简单
        • 在处理程序中只调用异步信号安全的函数异步信号安全的函数能够被信号处理程序安全地调用，原因有二：要么它可重入的，要么它不能被信号处理程序中断。
        • 保存和恢复errno 许多Linux异步信号安全的函数都会在出错返回时设置errno.在处理程序中调用这样的函数可能会干扰主程序中其他依赖于errno的部分。
        • 阻塞所有信号，保护对共享全局数据结构的访问。如果处理程序和主程序或其他处理程序共享一个全局数据结构，那么在访问该数据结构时，你的处理程序和主程序应该暂时阻塞所有的信号。
        • 用volatile声明全局变量 volatile类型限定符定义一个变量，告诉编译器不要缓存这个变量。
        • 用sig_atomic_t声明标志在常见的处理程序设计中，处理程序会写全局标志来记录收到 的信号。主程序周期性地读这个标志，响应信号，再清除该标志。对于通过这种方式来共享的标志，C提供一种整形数据类型sig_atomic_t,对它的读和写保证会是原子的（不可中断的），因为可以用一条指令来实现它们： 
          volatile sig_atomic_t flag;

    • 正确的信号处理

      信号的一个与直觉不符的方面是未处理的信号是不排队的。因为pending位微量中每种类型的信号只对应有一位，所以每种类型最多只能有一个未处理的信号。因此，如果两个类型k的信号发送给一个目的进程，而因为目的的进程当前正在执行信号k的处理程序，所以信号k被阻塞了，那么第二个信号就简单地被丢弃了; 它不会排队。

    • 可移植的信号处理

      Unix信号处理的另一个缺陷在于不同的系统有不同的信号处理语义。

      • signal函数的语义各有有不同。有些老的Unix系统在信号k被处理程序捕获之后就把对信号k的反应恢复到默认值。在这些系统上，每次运行之后，处理程序必须调用signal函数，显式地重新设置它自己。
      • 系统调用可以被中断像read、write和accept这样的系统调用潜在地会阻塞进程一段较长的时间，称为慢速系统调用。在某些较早的Unix系统中，当处理程序捕获到一个信号时，被中断的慢速系统调用在信号处理程序返回时不再继续，而是立即返回给用户一个错误条件，并将errno设置为EINTR。在这些系统上，程序员必须包括手动重启被中断的系统调用的代码。

      要解决这些问题，Posix标准定义了sigaction函数，它允许用户在设置信号处理时，明确指定他们想要的信号处理语义。

      #include <signal.h>
int sigaction(int signum, struct sigaction *act,, struct sigaction *oldact);
// 若成功则为0,出错则为-1

      sigaction函数运用并不广泛，因为它要求用户设置一个复杂结构的条目。一个更简洁的方式，就是定义一个包装函数，称为Signal,它调用sigaction.它的调用方式与signal函数的调用方式一样。 Signal包装函数设置了一个信号处理程序，其信号处理语义如下：

      • 只有这个处理程序当前正在处理的那种类型的信号被阻塞。
      • 和所有信号实现一样，信号不会排队等待。
      • 只要可能，被中断的系统调用会自动重启。
      • 一旦设置了信号处理程序，它就会一直保持，直到Signal带着handler参数为SIG_IGN或者SIG_DFL被调用。

  • 同步流以避免的并发错误

    一般而言，流可能交错的数量与指令的数量呈指数关系。这些交错中的一些会产生正确的结果，而有些则不会。基本的问题是以某种方式同步并发流，从而得到最大的可行的交错的集合，每个可行的交错都能得到正确的结果。

  • 显式地等待信号

    有时候主程序需要显式地等待某个信号处理程序运行。例如，当Linux shell创建一个前台作业时，在接收下一条用户命令之前，它必须等等作业终止，被SIGCHLD处理程序回收。

非本地跳转

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

操作进程的工具

Linux系统提供了大量的监控和操作进程的有用工具。

虚拟内存

一个系统中的进程是与其他进程共享CPU和主存资源的。为了更加有效地管理内存并且少出错，现代系统提供了一种对主存的抽象概念，叫做虚拟内存（VM）。虚拟内存是硬件异常、硬件地址翻译、主存、磁盘文件和内核软件的完美交互，它为每个进程提供了一个大小、一致的和私有的地址空间。通过一个很清晰的机制，虚拟内存提供了三个重要的能力：

  • 它将主存看成是一个存储在磁盘上的地址空间的高速缓存，在主存中只保存活动区域，并根据需要在磁盘和主存之间来回传送数据，通过这种方式，它高效地使用了主存。
  • 它为每个进程提供了一致的地址空间，从而简化了内存管理。
  • 它保护了每个进程的地址空间不被其他进程破坏。

我们为什么还需要理解虚拟内存：

  • 虚拟内存是核心的
  • 虚拟内存是强大的
  • 虚拟内存是危险的

物理和虚拟寻址

计算机系统的主存被组织成一个由M个连续的字节大小的单元组成的数组，每个字节都有一个唯一的物理地址。给定这种简单的结构，CPU访问内存的最自然的方式就是使用物理地址。我们把这种方式称为物理寻址。早期的PC使用物理寻址，然而，现代处理器使用的是一种称为虚拟寻址的寻址形式。使用虚拟寻址，CPU通过生成一个虚拟地址来访问主存，这个虚拟地址在被送到内存之前先转换成适当的物理地址。将一个虚拟地址转换为物理地址的任务叫做地址翻译。CPU芯片上叫做内存管理单元（MMU）的专用硬件，利用存放在主存中的查询表来动态翻译虚拟地址，该表的内容由操作系统管理。

地址空间

地址空间是一个非负数地址的有序集合。一个地址空间的大小是由表示最大地址所需要的倍数来描述的。例如，一个包含N等于2的n次方的虚拟地址空间就叫做一个n位地址空间。现代系统通常支持32位或64位虚拟地址空间。一个系统还有一个物理地址空间，对应于系统中物理内存的M个字节。地址空间清楚地区分了数据对象（字节）和它们的属性（地址）。主存中的每字节都有一个选自虚拟地址空间的虚拟地址和一个选自物理地址空间的物理地址。

虚拟内存作为缓存的工具

概念上，虚拟内存被组织为一个由存放在磁盘上的N个连续的字节大小的单元组成的数组.每字节都有一个唯一的虚拟地址，作为到数组的索引。硬盘上的数组的内容被缓存在主存中。物理内存被分割为物理面，大小为P字节（物理页也被称为页帧（page frame））。在任意时刻，虚拟页面的集合都分为三个不相交的子集：

  • 未分配的：VM系统还未分配（或者创建）的页。未分配的块没有任何数据和它们相关联，因此也就不占用任何磁盘空间。
  • 缓存的：当前已缓存在物理内存中的已分配页。
  • 未缓存的：未缓存在物理内存中的已分配页。

  • DRAM缓存的组织结构

    我们使用术语SRAM缓存来表示位于CPU和主存之间的L1,L2，和L3调整缓存，使用术语DRAM缓存来表示虚拟内存系统的缓存，它在主存中缓存虚拟页。与硬件对SRAM缓存相比，操作系统对DRAM缓存使用了更复杂精密的替换算法。因为对磁盘的访问时间很长，DRAM缓存总是使用写回，而不是直写。

  • 页表

    同任何缓存一样，虚拟内存系统必须有某种方法来判定一个虚拟页是否缓存在DRAM中的某个地方。如果是，系统还必须确定这个虚拟页存放在哪个物理页中。如果不命中，系统必须判断这个虚拟页存放在磁盘的哪个位置，在物理内存中造势一个牺牲页，并将虚拟页从磁盘复制到DRAM中，替换这个牺牲页。这个功能是由软硬伯联合提供的，包括操作系统软件、MMU（内存管理单元）中的地址翻译硬件和一个存放在物理内存中叫做页表（page table）的数据结构，页表将虚拟页映射到物理页。每次地址翻译硬件将一个虚拟地址转换为物理地址时，都会读取页表。操作系统负责维护页表的内容，以及在磁盘与DRAM之间来回传送页。

  • 页命中

  • 缺页

    在虚拟内存的习惯说法中，DRAM缓存不命中称为缺页（page fault）。在磁盘和内存之间传送页的活动叫做交换（swapping）或者页面调度（paging)。

  • 分配页面

  • 又是性救了我们

    尽管在整个运行过程中程序引用的不同页面的总数可能超出物理内存总的大小，但是局部性原则保证了在任意时刻，程序将趋向于在一个较小的活动页面（active page）集合上工作，这个集合叫做工作集（working set）或者常驻集合（resident set）。

虚拟内存作为内存管理的工具

虚拟内存提供了一种机制，利用DRAM缓存来自通常更大的虚拟地址空间的页面。操作系统为每个进程提供了一个独立的页表，因而也就是一个独立的虚拟地址空间。按需页面调度和独立的虚拟地址空间的结合，对系统中内存的使用和管理造成了深远的影响。特别地，VM简化了链接和加载、代码和数据共享，以及应用程序的内存分配。

  • 简化链接独立的地址空间允许每个进程的内存映像使用相同的基本格式，而不管代码和数据实际存放在物理内存的何处。
  • 简化加载虚拟内存还使得容易向内存中加载可执行文件和共享对象文件。将一组连续的虚拟页映射到任意一个文件中的任意位置的表示法称作内存映射（memory mapping）。Linux提供一个称为mmap的系统调用，允许应用程序自己做内存映射。
  • 简化共享独立地址空间为操作系统提供了一个管理用户进程和操作系统自身之间共享的一致机制。然而，在一些情况中，还是需要进程来共享代码和数据。例如，每个进程必须调用相同的操作系统内核代码，而每个C程序都会调用C标准库中的程序。操作系统通过将不同进程中适当的虚拟页面映射到相同的物理页面，从而安排多个进程共享这部分代码的一个副本，而不是在每个进程中都包括单独的内核和C标准库的副本。
  • 简化内存分配虚拟内存为向用户进程提供一个简单的分配额外内存的机制。

虚拟内存作为内存保护的工具

任何现代计算机系统必须为操作系统提供手段来控制对内存系统的访问。

地址翻译

内存映射

Linux通过将一个虚拟内存区域与磁盘上的对象关联起来，以初始化这个虚拟内存区域的内容，这个过程称为内存映射(memory mapping)。虚拟内存区域或以映射到两种类型的对象中的一种：

  • Linux文件系统中的普通文件
  • 匿名文件

动态内存分配

动态内存分配器维护着一个进程的虚拟内存区，称为堆。分配器将堆视为一组不同大小的块（block）的集合来维护。每个块就是一个连续的虚拟内存处，要么是已分配的，要么是空闲白的，已分配的块显示地保留为供应用程序使用。空闲块可用来分配。分配器有两种基本风格。

  • 显式分配器要求应用显式地释放任何已分配的块。
  • 隐式分配器要求分配器检测一个已分配块何时不再被程序所使用，那么就翻译这个块。隐式分配器也叫做垃圾收集（garbage collection）。

  • malloc和free函数

    malloc函数返回一个指针，指向大小为至少需要分配的size字节的内存块，这个块会为可能包含在这个块内的任何数据对象类型做对齐。在32位模式中， malloc返回的块的地址总是8的倍数。在64位模式中，该地址总是16的倍数。如果malloc遇到问题，那么它就返回NULL，并设置errno。

  • 为什么要使用动态内存分配

    程序使用动态内存分配的最重要的原因是经常直到程序实际运行时，才知道某些数据结构的大小。

  • 分配器的要求和目标

    显式分配器必须在一些相当严格的约束条件下工作：

    • 处理任意请求序列。
    • 立即响应请求
    • 只使用堆
    • 对齐块（对齐要求）
    • 不修改已分配的块。

    在这些限制条件下，分配器的编写者试图实现吞率最大化和内存使用率最大化，而这两个性能目标通常是相互冲突的。

    • 最大化吞率
    • 最大化内存利用率

  • 碎片

    造成堆利用率很低的主要原因是一种称为碎片(fragmentation)的现象，当虽然有未使用的内存但不能用来满足分配请求时，就会发生这种现象。有两种形式的碎片：内部碎片（internal fragmentation）和外部碎片（external fragmentation）。

    • 内部碎片是在一个已分配块比有效载荷大时发生的。
    • 外部碎片是当空闲内存合计起来足够满足一个分配请求，但是没有一个单独的空闲块足够大可以来处理这个请求时发生的。

  • 隐式空闲链表

    任何实际的分配器都需要一些数据结构，允许它来区别块边界，以及区别已分配块和空闲块。

  • 分割空闲块

    一旦分配器找到一个匹配的空闲块，它就必须做另一个策略决定，那就是分配这个空闲块中多少空间。

  • 获取额外的堆内存

    如果分配器不能为请求块找到合适的空闲块将发生什么？一个选择是通过合并那些在内存中物理上相信的空闲块来创建一些更大的空闲块。然而，如果这样还是不能生成一个足够大的块，或者如果空闲块已经最大程度地合并了，那么分配器就会通过调用sbrk函数，向内核请求额外的堆内存。

  • 合并空闲块

    为了解决假碎片问题，任何实际的分配器都必须合并相信的空闲块，这个过程称为合并（coalescing）。何时合并？

    • 可以是立即合并，也就是在每次一个块被释放时，就合并所有的相信块。立即合并可以在常数时间内执行完成，但是对于某些请求模式，这种方式会产生一种形式的拉动，块会反复地合并，然后马上分割。
    • 可以推迟合并，也就是等到某个的时候再合并空闲块。
  • 带边界标记的合并
  • 显式空闲链表

  • 分离的空闲链表

    • 简单分离存储

      使用简单分离存储，每个大小类的空闲链表包含大小相等的块，每个块的大小就是这个大小类中最大元素的大小。为了分配一个给定大小的块，我们检查相应的空闲链表。如果链表非空，我们简单地分配其中第一块的全部。空闲块是不会分割以满足分配请求的。如果链表为空，分配器就向操作系统请求一个固定大小的额外内存片，将这个片分成大小相等的块，并将这些块链接起来形成新的空闲链表。

      • 优点

        • 分配和释放块都是很快的常数时间操作。
        • 每个片中都是大小相等的块，不分割，不合并，这意味着每个块只有每少的内存开销。
        • 已分配块不需要头部，同时因为没有合并，它们也不需要脚部。
        • 在任何块中都需要的唯一字段是每个空闲块中的一个字的succ指针，因此最小块大小就是一个字。

      • 缺点

        很容易造成内部和外部碎片。

        • 因为空闲块是不会被分割的，扬剧脍 造成内部碎片。
        • 因为不会合并空闲块，所以某些引用模式会引起极多的外部碎片。

    • 分离适配

      分配器维护着一个空闲链表的数组。每个空闲链表是和一个大小类相关联的，并且被组织成某种类型的显式或隐式链表。每个链表包含潜在的大小不同的块，这些块的大小是大小类的成员。有许多种不同的分离适配分配器。分离适配方法是一种常见的选择，C标准库中提供的GNU malloc包就是采用的这种方法。

    • 伙伴系统

      是分离适配的一种特使，其中每个大小类都是2的幂。

垃圾收集

垃圾收集器(garbage collector)是一种动态内存分配器，它自动释放程序不再需要的已分配块。这些块被称为垃圾。自动回收堆存储的过程叫做垃圾收集。

  • 垃圾收集器的基本知识

    垃圾收集器将内存视为一张有向可达图（reachability graph）。当存在一条从任意根节点出发并到达p的有向路径时，我们说节点p是可达的（reachable）。

  • Mark & Sweep 垃圾收集器

    Mark&Sweep傅粉何郎食品在由标记（mark）阶段和清除（sweep）阶段组成，标记阶段标记出根节点的所有可达的已分配的后继，而后面的清除阶段释放每个未被标记的已分配块。

C程序中常见的与内存有关的错误

  • 间接引用坏指针

    在进程的虚拟地址空间中有较大的洞，没有映射到任何有意义的数据。如果我们试图间接引用一个指向这些洞的指针，那么操作系统就会以段异常中止程序。而且，虚拟内存的某些区域是只读的。试图写这些区域将会以保护异常踏上这个程序。

  • 读未初始化的内存

    虽然bss内存位置（诸如未初始化的全局C变量）总是被加载器初始化为零，但是对于堆内存却并不是这样的。

  • 允许栈缓冲区溢出

    如果一个程序不检查输入串的大小就写入栈中的目标缓冲区，那么这个程序就会有缓冲区溢出错误（buffer overflow bug）。

  • 假设指针和它们指向的对象是相同大小的
  • 造成错位错误

  • 引用指针，而不是它所指向的对象

    如果不太注意C操作符的优先级和结合性，我们就会错误地操作指针，而不是指针所指向的对象。

  • 误解指针运算
  • 引用不存在的变量

  • 引用空闲堆块中的数据

    引用已经被释放了的堆块中的数据。

  • 引起内存泄漏

    当程序员不小心忘记释放已分配块，而在堆里创建垃圾时，会发生这种问题。

小结

虚拟内存是对主存的一个抽象。支持虚拟内存的处理器通过使用一种叫做虚拟寻址的间接形式来引用主存。处理器产生一个虚拟地址，在被发送到主存之前，这个地址被翻译成一个物理地址。从虚拟地址空间到物理地址空间的地址翻译要求硬件和软件紧密合并。专门的硬件通过使用页表翻译虚拟地址，而页表的内容是由操作系统提供的。虚拟内存提供三个重要的功能，第一，它在主存中自动缓存最近使用的存放磁盘上的虚拟地址空间的内容。虚拟内存缓存中的块叫做页。对磁盘上页的引用会触发缺页，缺页将控制转移到操作系统中的一个缺页处理程序。缺页处理程序将页面从磁盘复制到主存缓存，如果必要，将写回被驱逐的页。第二，虚拟内存简化了内存管理，进而又简化了链接、在进程间共享数据、进程的内存分配以及程序加载。最后虚拟内存通过在每条页表条目中加入 保护位，从而简化了内存保护。地址翻译的过程必须和系统中的所有的硬件缓存的操作集成在一起，大多数页表条目位于L1高速缓存中，但是一个称为TLB的页表条目的片上高速缓存，通常会消除访问在L1上的页表条目的开销。现代系统通过将虚拟内存片和磁盘上的文件片关联起来，来初始化虚拟内存片，这个过程称为内存映射。内存映射为共享数据、创建新的进程以及加载程序提供了一种高效的机制。应用可以使用mmap函数来手动地创建和删除虚拟地址空间的区域。然而，大多数程序依赖于动态内存分配器，例如malloc，它管理虚拟地址空间区域内一个称为堆的区域。动态内存分配器是一个感觉像系统级程序的应用级程序，它直接操作内存，而无需要类型系统的很多帮助。分配器有两种类型。显示分配器要求应用显式地释放它们的内存块。隐匿分配器（垃圾收集器）自动释放任何未使用的和不可达的块。

程序间的交互和通信

系统级I/O

I/O是在主存和外部设备（例如磁盘驱动器、终端和网络）之间复制数据的过程。输入操作是从IO设备复制数据到主丰，而输出操作是从主存复制数据到IO设备。

Unix I/O

所有的IO设备都被模型化为文件，而所有的输入和输出都被当作对相应文件的读和写来执行。这种将设备优雅地映射为文件的方式，允许Linux内核引出一个简单、低级的应用接口，称为UnixI/O，这使得所有的输入和输出都能以一种统一且一致的方式来执行：

  • 打开文件一个应用程序通过要求内核打开相应的文件，来宣告它想要访问一个I/O设备。
  • Linux shell创建的每个进程开始时都有本个打开的文件：标准输入，标准输出和标准错误。
  • 改变当前的文件位置。对于每个打开的文件，内核保持着一个文件位置k,初始为0。这个文件位置是从文件开头起始的字节领衔量。应用程序能够通过执行seek操作，显式地设置文件的当前位置为k.
  • 读写文件
  • 关闭文件

文件

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

  • 普通文件
  • 目录
  • 套接字
  • 命名通道
  • 符号链接
  • 字符
  • 块设备

打开和关闭文件

进程是通过调用open函数来打开一个已存在的文件或者创建一个新文件，open函数将文件转换为一个文件描述符，并且返回描述符数字。进程通过调用close函数关闭一个打开的文件。

读和写文件

应用程序是通过分别调用read和write函数来执行输入和输出的。通过调用lseek函数，应用程序能够显示地修改当前文件的位置。

用RIO包健壮地读写

RIO提供了两类不同的函数

  • 无缓冲的输入输出函数

    这些函数直接在内存和文件之间传送数据，没有应用级缓冲。它们对将二进制数据读写到网络和从网络读写二进制数据尤其有用。

  • 带缓冲的输入函数

读取文件元数据

应用程序能够通过调用stat和fstat函数，检索到关于文件的信息（有时也称为文件的元数据（metadata））。

读取目录内容

应用程序可以用readdir系统函数来读取目录的内容。函数closedir关闭流并释放其所有的资源。

共享文件

内核用三个相关的数据结构来表示打开的文件：

  • 描述符表每个进程都有它独立的描述符表，它的表项是由进程打开的文件描述符来索引的。每个打开的描述符表项指向文件表的一个表项。
  • 文件表打开文件的集合是由一张文件表来表示的，所有的进程共享这张表。
  • v-mode表同文件表一样，所有的进程共享这张v-node表。每个表项包含stat结构中的大多数信息，包括st_mode和st_size成员。

I/O重定向

Linux shell提供了I/O重定向操作符，允许用户将磁盘文件和标准输入输出联系起来。

标准I/O

C语言定义了一组高级输入输出函数，称为标准I/O库，为程序员提供了UnixI/O的较高级别的替代。这个库（libc）提供了打开和关闭文件的函数（fopen和fclose）、读和写字节的函数（fread和fwrite）、读和写字符串的函数（fgets和fputs），以及复杂的格式化的IO函数（scanf和printf）。

网络编程

客户端-服务器编程模型

每个应用都是基于客户端-服务器模型的。客户端-服务器模型中的基本操作是事务。一个客户端-服务器事务由以下四步组成：

  1. 当一个客户端需要服务时，它向服务器发送一个请求，发起一个事务。
  2. 服务器收到请求后，解释它，并以适当的方式操作它的资源。
  3. 服务器给客户端发送一个响应，并等待下一个请求。
  4. 客户端收到响应并处理它。

网络

客户端和服务器通常运行在不同的主机上，并且通过计算机网络的硬件和软件资源来通信。对主机而言，网络只是又一种IO设备，是数据源和数据接收方。互联网至关重要的秀发是，它能由采用完全不同和不兼容技术的种种局域网和广域网组成。每台主机和其他每台主机都是物理相连的，但是如何能够让某台源主机跨过所有这些不兼容的同络发送数据位到另一台目的主机呢？解决办法是一层运行在每台主机和跌幅器上的协议软件，它消除了不同网络之间的差异。这个软件实现一种协议，这种协议控制主机和路由器如何协同工作来实现数据传输。这种协议必须提供两种基本能力：

  • 命名机制。不同的局域网技术有不同和不兼容的方式来为主机分配地址。
  • 传送机制

全球IP因特网

  • IP
  • 因特网域名

套接字接口

套接字接口（socket interface）是一组函数，它们和Unix IO函数结合起来，用以创建网络应用。

  • 套接字地址结构

    从Linux内核的角度来看，一个套接字就是通信的一个端点。从Linux程序的角度来看，套接字就是一个有相应描述符的打开文件。

  • socket函数

    客户端和服务器使用socket函数来创建一个套接字描述符(socket descriptor)。

  • connect函数

    客户端通过调用connect函数来建立和服务器的连接。

  • bind函数
  • listen函数
  • accept函数
  • 主机和服务的转换

Web服务器

并发编程

基于进程的并发编程

构造并发程序最简单的方法就是用进程，使用那些大家都很熟悉的函数，像fork, exec, waitpid.

  • 基于进程的并发服务器

    一些说明：

    • 首先，通常服务器会运行很长的时间，所以我们必须要包括一个SIGCHILD处理程序，来回收全歼子进程的资源。
    • 项背，父子进程必须关闭它们各自的cnnfd副本。
    • 最后，因为套接字的文件表表项中的引用计数，直到父子进程的connfd都关闭了，到客户端的连接才会终止。

  • 进程的优劣

    对于在父子进程间共享状态信息，进程有一个非常清晰的模型：共享文件表，但是不共享用户地址空间。进程有独立的地址空间既是优点也是缺点。这样一来，一个进程不可能不小心覆盖另一个进程的虚拟内存， 这就消除了许多令人迷惑的错误。另一方面，独立的地址空间使得进程共享状态信息变得更加困难。

基于IO多路利用的并发编程

IO多路利用技术的基本思路就是使用seelct函数，要求内核挂起进程，只有在一个或多个IO事件发生后，才将控制返回给应用程序。

  • 基于IO多路复用的并发事件驱动服务器

  • IO多路复用技术的优劣

    • 优点

      • 它比基于进程的设计给了程序员更多的对程序行为的控制。
      • 一个基于IO多路复用的事件驱动服务器是运行在单一进程上下文中的，因此每个逻辑流都能访问该进程的全部地址空间。这使得在流之间共享数据变得很容易。
      • 你可以使用熟悉的调试工具，例如GDB来调试你的并发程序，就像对顺序程序那样。
      • 事件驱动设计常常比基于进程的设计要高效的多，因为它们不需要进程上下文切换来调度新的流。

    • 缺点

      • 编码复杂，并且随着并发粒度的减小，复杂性还会上升。
      • 它不能充分利用多核处理器。

基于线程的并发编程

线程就是运行在进程上下文中的逻辑流。线程由内核自动调度。每个线程都有它自己的线程上下文（thread context），包括一个唯一的整数线程ID、栈、栈指针、程序计数器、通用目的寄存器和条件码。所有的运行在一个进程里的线程共享该进程的整个虚拟地址空间。基于线程的逻辑流结合了基于进程和基于IO多路复用的流的我。同进程一样，线程由内核自动调度，并且内核通过一个整数ID来识别线程。同基于IO多路复用的流一样，多个线程运行在单一进程的上下文中，因此共享这个进程虚拟地址空间的所有内容，包括它的代码、数据、堆、共享库和打开的文件。

  • 线程执行模型

    每个进程开始生命周期时都是单一线程，这个线程称为主线程，在某一时刻，主线程创建一个对等线程，从这个时间开始，两个线程就并发地运行。最后因为主线程执行一个慢速系统调用，或者因为被系统的间隔计时器中断，控制就会通过上下文切换传递到对等线程。对等线程会执行一段时间，然后控制传递回主线程，依次类推。在一些重要的方面，线程执行是不同于进程的。因为一个线程的上下文要比一个进程的上下文小得多，线程的上下文切换要比进程的上下文切换快得多。另一个不同就是线程不像进程那样，不是按照严格的父子层次来组织的。主线程和其他线程的区别公在于它总是进程中第一个运行的线程。对等(线程)池概念的主要影响是，一个线程可以杀死它的任何对等线程，或者等待它的任意对等线程终止。另外，每个对等线程都能读写相同的共享数据。

  • Posix线程

  • 创建线程

    线程通过调用pthread_create函数来创建其他线程。

  • 终止线程

    一个线程以下列方式之一来终止的：

    • 当顶层的线程例程返回时，线程会隐式地终止。
    • 通过调用pthread_exit函数，线程会显式地终止。
    • 某个对等线程调用Linux的exit函数，该函数终止进程以及所有与该进程相关的线程。
    • 另一个对等线程通过以当前线程ID作为参数调用pthread_cancel函数来终止当前线程。

  • 回收已终止线程的资源

    线程通过调用pthread_join函数来等待线程终止。

  • 分离线程

    在任何一个时间点上，线程是可结合的或者是分享的。一个可结合的线程能够被其他线程收回或杀毒。在被其他线程回收之前，它的内存资源是不释放的。相反，一个分离的线程是不能被其他线程回收或杀死的。它的内存资源在它终止时由系统自动释放。

  • 初始化线程

    pthread_once函数允许你初始化与线程例程相关的状态。

  • 基于线程的并发服务器

多线程程序中的共享变量

  • 线程内存模型

    一组并发线程运行在一个进程的上下文中。每个线程都有它自己的线程上下文，包括线程ID、栈、栈指针、程序计数器、条件码和通用目的寄存器值。每个线程和其它线程一起共享进程上下文的剩余部分。这包括整个用户虚拟地址空间，它是由只读文本（代码）、读/写数据、堆以及所有的共享库代码和数据区域组成的。线程也共享相同的打开文件的集合。

  • 将变量映射到内存

    多线程的C程序中变量根据它们的存储类型被映射到虚拟内存：

    • 全局变量全局变量是定义在函数之外的变量。虚拟内存的读写区域只包含每个全局变量的一个实例，任何线程都可以引用。
    • 本地自动变量本地自动变量就是定义在函数内部但是没有static属性的变量。在运行时，每个线程的栈都包含它自己的所有本地变量的实例。
    • 本地静态变量本地静态变量是定义在函数内部并有static属性的变量。和全局变量一样，虚拟内存的读/写区域只包含在程序中声明的每个本地静态变量的一个实例。

  • 共享变量

    我们说一个变量是共享的，当且仅当它的一个实例被一个以上的线程引用。

用信号量同步线程

共享变量是十分方便，但是这们也引入了同步错误的可能性。

  • 进度图

    进度图将n个并发线程的执行模型化为一条n维笛卡儿空间中的轨迹线。进度图将指令执行模型化为从一种状态到另一种状态的转换。转换被表示为一条从一点到相信点的有向边。合法的转换是向右或者向上的。两条指令不能在同一时刻完成。一个程序的执行历史被模型化为状态空间中的一条轨迹线。在进度图中，两个临界区的交集形成的状态空间区域被称为不安全区。任何安全轨迹线都将正确地更新共享计数器。为了保证线程化程序示例的正确执行，我们必须以某种方式同步线程，使它们总有一条安全轨迹线。

  • 信号量

    信号量是具有非负整数值的全局变量，只能由两种特殊的操作来处理，这两种操作被称为P和V：

    • P 如果信号量是非零的，那个P将信号量减1,并且立即返回。如果信号量是0,那么就挂起这个线程，直到信号量变为非0,而一个V操作会重启这个线程。在重启之后，P操作将信号量减1,并将控制返回给调用都。
    • V v操作将信号量加1.如果没有任何线程阻塞在P操作等待信号量变成非零，那么V操作就会重启这些线程中的一个，然后该线程将信号量减1,完成它的P操作。

    P和V的定义确保了一个正在运行的程序绝不可能进入这样一种状态，也就是一个正确初始化了的信号量有一个负值。这个属性称为信号量不变性。

  • 使用信号量来实现互斥

    将每个共享变量与一个信号量联系起来，然后使用P和V操作将相应的临界区包围起来。以这种方式来保护共享变量的信号量叫做二元信号量，因为它的值总是0或者1.以提供互斥为目的的二元信号量常常也称为互斥锁（mutex）。

  • 利用信号量来调度共享资源

    除了提供互斥之外，信号量的咖一个重要作用是高度对共享资源的访问。

    • 生产者-消费者问题

使用线程提高并行性

其他并发问题

  • 线程安全

    • 我们能够定义出四个线程不安全函数类

      1. 不保护共享变量的函数
      2. 保持跨越多个调用的状态的函数
      3. 返回指向静态变量的指针的函数
      4. 调用线程不安全函数的函数

    • 可重入性

      可重入函数是指安它们被多冷战线程调用时，不会引用任何共享数据。可重入函数集合是线程安全函数的一个真子集。

    • 在线程化的程序中使用已存在的库函数

      大多数Linux函数，包括定义在标准C库中的函数都是线程安全的，只有一小部分是例外。

    • 竞争

      当一个程序的正确性依赖于一个线程要在另一个线程到达Y点之前到达它的控制流中的X点时，就会发生竞争。

    • 死锁

      死锁是指一组线程被阻塞了，等待一个永远也不会为真的条件。使用互斥锁加锁顺序规则可以去死锁：给定所有互斥操作一个全序，如果每个线程都是以一种顺序获得互斥锁并以相反的顺序释放，那么这个程序就是无死锁的。