[系统运维]CSAPP笔记（下）

1. 链接

1. 简介

1. 链接是将各种代码和数据片段收集在一起并且组合成为一个单一的文件的过程，所得到的文件可以被加载到内存并执行；链接可以发生在编译时，也就是源代码被翻译成机器码的时候；也可以发生在加载时，也就是程序被加载到内存并执行的时候；也可以执行于运行时，也就是由应用程序来执行。在现代系统中，加载是由连接器完成的；
2. 加载是我们可以做到分离编译，我们不需要将一个大型的应用程序组织为一个巨大的源文件，而是将他们分解为更小的更好管理的模块，以便于独立的修改和编译这些模块，当想要修改这些模块中的一个的时候，我们只需要将这个模块重新编译并重新链接到应用就可以了，而不必将重新编译程序中的其它文件；

2. 编译驱动程序

1. 下图展示了两个简单的函数，我们可以得出链接器是怎么对这两个文件进行链接的：
   
   下图概括了驱动程序将上图中的程序从ASCII码源文件翻译为可执行目标文件的过程：
   
   驱动程序执行的大致过程如下所示：

   • 首先会运行C预处理器（cpp），将C源代码main.c翻译为一个ASCII码的中间文件main.i；
   • 运行C编译器（ccl），将main.i翻译为一个ASCII汇编语言文件main.s；
   • 运行编译器as，将main.s翻译为一个可重定位目标文件main.o；
   • 运行链接器程序ld，将main.o和sum.o以及一些必要的系统目标文件组合起来，创建一个可执行目标文件；

3. 静态链接

1. 为了构造出一个可执行文件，链接器必须完成以下的两个主要的任务：

   • 符号解析：每一个符号对应于一个函数，一个全局变量或者是一个静态变量；符号解析的目的就是将每一个符号引用和一个符号的定义关联起来；
   • 重定位：编译器和汇编器生成从地址0开始的代码和数据节。链接器通过把每个符号定义与一个内存位置关联起来，从而重定位这些节，然后修改对这些符号的引用，使得它们指向这个内存位置。链接器使用汇编器产生的重定位条目的详细指令不加甄别得执行以上的重定位操作。

2. 下图展示了在C语言中是怎么和静态库进行链接的：
   

3. 下图展示了C语言是如何动态链接共享库的：
   

4. Linux x86-64的内存映像

1. 在Linux x86-64系统中，代码段总是从地址 0x400000 处开始的，之后是数据段，运行时堆在数据段之后并通过malloc库向上增长，堆后面的区域是为共享区域保留的。用户栈总是从最大的合法用户地址(2^48 - 1)处开始，向较小的内存地址增长。栈之上的位置是为操作系统内核中的代码以及数据做准备的，也就是OS内核常驻内存的部分。
   
   以上的模型是非常重要的，在之后的各个知识点之中都会提到，涉及到了计算机系统中的方方面面。

2. 异常控制流

1. 简介

1. 从我们给处理器加电开始，直到断电为止，程序计数器会假设有以下的一个值的序列：a0,a1,…,a(n-1)；其中每一个ak是某一个相应的指令Ik的地址，每次从ak到a(k+1)的过渡称为控制转移。这样的控制转移序列叫做处理器的控制流；

2. 最简单的一种控制流是一个平滑的序列，其中每一个Ik和I(k + 1)在内存中都是相邻的，其中平滑流的突变（也就是Ik和I(k + 1)不相邻）通常是由诸如跳转，调用和返回的这样一些熟悉的指令造成的。这样一些指令都是必要的机制，使得程序能够对内部程序状态中的变化做出反应，内部程序状态是由程序变量表示的；

3. 但是系统也必须能够对系统状态的变化做出反应，这些系统状态不是被内部程序变量捕获的，而且也不一定要和程序的执行相关。比如一个硬件定时器定期产生的信号，这种事件必须得到处理；当数据包到达网络适配器之后必须存放在内存中，这种事件也必须得到处理；程序向磁盘请求数据，然后休眠，直到被通知数据已经到达了；当子进程终止的时候，创建这些子进程的父进程必须得到通知等；以上提到的事件都是系统状态发生变化的时候所产生的事件，这些事件也必须得到处理。

4. 现代操作系统用过使控制流发生突变来对以上的情况做出反应。我们将这些突变称作异常控制流（Exceptional Control Flow，ECF）。异常控制流发生在计算机系统中的各个层次。在硬件层，硬件检测到的事件会触发控制突然转移到异常处理程序；在操作系统层，内核通过向下文切换将控制由一个用户进程转移到另一个用户进程；在应用层一个进程可以发送信号到另一个进程，接收者会将控制突然转移到信号处理程序。一个程序可以通过回避通常的栈规则，并执行到其他函数中任意位置的非本地跳转来对错误做出反应；理解ECF是很重要的，它是我们理解其它的概念以及编写更好的应用程序的基础：

   • ECF是操作系统用来实现IO，进程和虚拟内存的基本机制；
   • 理解ECF可以帮助我们理解应用程序是如何与操作系统进行交互的。应用程序是通过一种叫做陷阱或者是系统调用的ECF形式来向操作系统请求服务的；比如向磁盘写数据，从网络之中读取数据，创建一个新进程，以及终止当前进程，都是通过应用程序调用系统调用函数来实现的；
   • ECF是计算机系统中实现并发的基本机制，在运行中的并发的例子有：中断应用程序执行的异常处理程序，在时间上重叠执行的进程以及线程，中断应用程序执行的信号处理程序等；
   • 在C++以及Java语言中通过try，catch和throw语句来提供软件异常机制。软件异常允许程序进行非本地跳转。非本地跳转是应用层的ECF，但是我们在Java中习惯性的直接将非本地跳转称作异常；

2. 异常

1. 简介

1. 异常是异常控制流的一种形式，它一部分由硬件实现，一部分由操作系统实现，所以说细节上在不同的机器或者是操作系统之间会存在差异，但是在整体的计算机系统中基本的思想都是相同的；

2. 异常就是控制流中的突变，用来响应处理器状态中发生的某些变化，下图展示了异常的基本思想：
   
   当处理器状态中发生一个重要的变化时，处理器正在执行某个当前指令Icurr。在处理其中不同的状态被编码为不同的位和信号，状态的变化称为事件，事件可能和当前正在执行的指令相关联，比如说发生了虚拟内存缺页，算数溢出，或者是一条指令试图除以零。另一方面，事件也可能和当前正在执行的指令没有关系，比如一个系统定时器产生的信号或一个IO请求完成。

3. 在任何情况下当处理器检测到有事件发生的时候，他就会通过一张叫做异常表的跳转表进行一个间接过程调用（异常），到一个专门设计用来处理这类事件的操作系统子系统（异常处理程序）。当异常处理程序执行完毕后会根据引起异常的事件类型来决定发生以下三种情况中的哪一种：

   • 处理程序将控制返回给Icur，即当事件发生的时候正在执行的指令；
   • 处理程序将控制返回给Inext，即如果没有发生异常的话将会执行的下一条指令；
   • 处理程序终止被中断的程序，也就是引起异常的程序；

4. 在Java中出现的异常是软件异常，是应用级的ECF；

2. 异常处理

1. 计算机系统为每种类型的异常都分配了一个唯一的非负整数的异常号。其中的一些号码是由硬件的设计者进行分配的，比如被零除，缺页，内存访问违例，断点以及算数运算溢出；还有一些号码是由操作系统的设计者进行分配的，比如系统调用和来自外部IO设备的信号：
   
   在系统启动的时候操作系统会分配并初始化一张称为异常表的跳转表，表中的表目k包含异常k的处理程序的地址；在运行的时候如果处理器检测到发生了一个事件，并且确定了相应的异常号k，处理器就会触发异常，方法就是执行间接过程调用，通过异常表的表目k跳转到相应的异常处理程序。异常号是到异常表中的索引，异常表的起始地址放在一个异常表基址寄存器的特殊CPU寄存器之中：
   
   异常类似于过程调用但是有一些重要的不同之处

   • 在过程调用中，在跳转到处理程序之前，处理器会将返回地址压入到栈中。但是异常处理程序会根据异常的不同而选择不同的返回方式，如果是返回而不是终止程序的话，那么要么返回到被中断程序的当前指令，要么返回到被中断程序的下一条指令；
   • 处理器会把一些额外的处理器状态压倒栈中，在处理程序返回后，重新开始执行被中断的程序的话会需要以上的处理器状态；
   • 如果控制从用户程序转移到内核，那么所有的这些项目都被压到内核栈中，而不是压到用户栈中；
   • 异常处理程序运行在内核模式下，这意味着它们对所有的系统资源都有完全的访问权限；

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

3. 异常的类别

1. 异常可以分为4类，分别是中断，陷阱，故障和终止，下图展示了它们之间的区别：
   

2. 中断是异步发生的，是来自处理器之外的设备所产生的信号导致的。硬件中断不是由任何一条指令所造成的。硬件中断的异常处理程序常常被称作中断处理程序；
   
   下图展示了一个中断的处理。例如网络适配器，磁盘控制器和定时器芯片等这类的IO设备会通过向处理器芯片上的一个引脚发送一个信号，并将异常号放到系统总线上来触发中断，异常号表示了引起中断的设备；在当前指令执行完毕之后，处理器会注意到中断引脚的电压变高了，于是就从系统总线中取出异常号，然后调用适当的中断处理程序进行处理。当处理程序返回的时候，他就会将控制返回给下一条指令。然后被中断的程序继续执行，就像没有发生过中断一样。剩下的三个异常类型都是同步发生的，是执行当前指令的结果，我们把这类指令叫做故障指令；

3. 陷阱和系统调用：陷阱是有意而为之的异常，是执行一条指令的结果，陷阱处理程序也会返回到下一条指令。陷阱最重要的用途就是在用户程序和内核之间搭建一个像过程一样的接口，叫做系统调用；由于用户程序的权限是有限的，比如说用户程序不能够直接去创建一个新的进程（fork），而是向内核请求服务，这类的只能向内核请求的服务还包括读取一个文件（read），终止当前的进程（exit），加载一个新的程序（execve）。为了允许用户程序对这些内核服务的受控的访问，处理器提供了一条“syscall n”指令，当用户程序想要请求一个服务n的时候，可以执行syscall指令，执行该指令会导致一个到异常处理程序的陷阱，这个异常处理程序会解析参数并调用适当的内核程序，下图展示了一个系统调用的过程：
   
   从我们程序员的角度来看，系统调用和普通的函数调用是一样的，然而两者的实现差异很大。普通函数只能运行在用户模式下，用户模式限制了可以执行的指令的类型，而且他们只能访问与调用函数相同的栈。而系统调用函数运行在内核模式下，内核模式允许系统调用执行特权指令，并访问定义在内核中的栈。

4. 故障：故障是由错误情况引起的，它可能会被故障处理程序修正。当故障发生的时候，处理器将控制转移给故障处理程序。如果处理程序能够修正这个故障的话，在处理程序处理完成之后就会将控制返回到引起故障的指令，并使引起故障的指令重新执行，否则处理程序就会返回到内核中的abort例程，abort例程会终止引起故障的程序，下图展示了当程序发生故障的时候会产生的情况：
   
   一个典型的故障就是缺页异常，当指令引用一个虚拟地址的时候，如果该虚拟地址对应的物理页面不在内存中，因此必须将相应的数据从磁盘中取出来，那么就会发生故障，一个页面就是虚拟内存的一个典型的块。缺页处理程序会从磁盘中加载适当的页面，然后将控制返回给引起故障的指令。当指令再次执行的时候，相应的物理页面就已经驻留在内存中了，指令就可以没有故障的运行完成了。

5. 终止：终止是不可恢复的致命错误造成的结果。通常是一些硬件错误，比如DRAM或者SRAM位被损坏是发生的奇偶错误。终止处理程序不会将控制返回给应用程序，它会将控制返回给一个abort例程，该例程会终止这个应用程序；
   

3. 进程

1. 简介

1. 异常的存在允许操作系统内核提供进程这一概念；
2. 在现代的计算机系统之中运行一个程序的时候，我们就会得到一个假象，好像我们的程序就是系统中当前运行的唯一的程序一样。我们的程序好像是独占地使用处理器以及内存。处理器无间断的一条接着一条地执行我们程序中的指令，而我们程序中的代码以及数据就好像是系统内存中唯一的对象。这些假象都是通过进程的概念提供给我们的；
3. 进程的经典定义就是一个执行中的程序的实例。系统中的每一个程序都运行在一个进程的上下文之中。上下文是由程序正确运行所需要的状态组成的，这个状态包括存放在内存中的程序的代码以及数据，它的栈，通用目的寄存器中的内容，程序计数器，环境变量以及打开文件描述符的集合；
4. 每次用户向shell输入一个可执行目标文件的名字的时候，运行程序时shell就会创建一个新的进程，然后在这个新的进程的上下文之中运行这个可执行目标文件。应用程序也能够创建新的进程，并且在这个新进程的上下文之中运行它们自己的代码或者是其它应用程序；进程给应用程序提供了以下的关键抽象：一个独立的逻辑控制流，它会提供一个假象，好像我们的程序独占的使用处理器；一个私有的地址空间，它提供了一个假象，好像我们的应用程序在独占的使用内存系统；

2. 逻辑控制流

1. 即使在系统之中通常有许多的其它的程序在执行，但是进程可以向我们的程序提供一个假象，那就是我们的程序正在独占的使用处理器，此时如果我们使用调试器单步执行程序的话，我们就会看到一系列的程序计数器的值，这些值唯一的对应于每一条指令的地址，这个PC值的序列就叫做逻辑控制流，或者简称为逻辑流；
2. 在下图中展示了一个运行着三个进程的系统，处理器的一个物理控制流被分为了三个逻辑控制流，每个进程一个，其中的每一条竖线表示一个进程的逻辑控制流的一部分，可以看到，三个逻辑控制流的执行是交错的，A先执行了一会儿，然后是B执行直到完后，之后是C…，最后进程C执行完成；
   
   图中所展示的关键点在于进程是轮流使用处理器的，每个进程执行它的逻辑流的一部分，然后被其他进程抢占，该进程暂时挂起，之后抢占成功的那个进程会使用处理器处理自己的逻辑流。而对于运行在这三个进程上下文之一中的程序来说，它在用户看上去就像是在独占的使用处理器，但是实际上对于每一个程序来说CPU都会周期性的停顿，并不会一直执行某一个单一的程序。

3. 并发流

1. 计算机系统中的逻辑流有很多不同的形式，异常处理程序，进程，信号处理程序，线程和Java进程都是逻辑流的例子；
2. 一个逻辑流的执行在时间上与另一个流重叠就成为并发流，这两个流被称为并发的运行，更准确的说X和Y并发的话当且仅当X在Y开始之后和在Y结束之前开始，反过来也是一样，比如在上图之中进程A和B是并发的执行的，A和C也是并发的执行的，但是B和C却不是并发的执行的，因为B在C开始之前就已经结束了；
3. 多个流并发的执行的一般现象叫做并发，一个进程和其它进程轮流的执行叫做多任务，每个进程执行它的逻辑流的每一个时间段叫做时间片，所以多任务也叫作时间分片，比如进程A的流就是由两个时间片组成的；
4. 并发流的思想与流运行的处理器核数或者计算机数是无关的，如果两个流在时间上重叠那么他们就是并发的，即使他们运行在同一个处理器之上也是并发的。但是引入并行的概念也是有必要的，并行流是并发流的一个真子集。如果两个流并发的运行在不同的处理器核或者是计算机上，那么我们称它们为并行流（parallel flow），他们并行地运行（running in parallel），且并行地执行（parallel execution）；

4. 私有地址空间

1. 进程为运行在它的上下文之中的程序提供了一个假象，那就是那个程序好像是在独占地使用系统地址空间。在一台n位地址的机器上，地址空间就是2^n个可能地址的集合，进程为每一个程序提供它自己的私有地址空间，一般而言和某个私有地址空间中的某个地址相关联的那个内存字节是不可以被其他的进程读或者是写的，从这个意义上来看，这个地址空间是私有的；尽管和每一个私有地址空间相关联的内存的内容一般是不同的，但是每个地址空间都有相同的通用结构，下图展示了一个x86-64 Linux进程的地址空间的组织结构。地址空间的地步是保留给用户程序使用的，包括通常的代码，数据，堆和栈段。代码段总是从地址0x400000开始的，地址空间的顶部是保留给操作系统内核的，内核是操作系统常驻内存的部分。该部分包含内核在代表进程执行指令时（比如当应用程序执行系统调用时，注意，内核是在“代表”进程来执行指令的，并不是创建了一个新的进程，还是在原来的进程之中）使用到的代码，数据和栈：
   

5. 用户模式和内核模式

1. 为了对操作系统内核提供一个非常安全的进程抽象，处理器必须提供一种机制，限制一个应用可以执行的指令以及它们可以访问的地址空间范围；
2. 处理器通常是通过某个控制寄存器中的一个模式位来提供这种功能的，该寄存器描述了一个进程是处于用户模式下的还是处于内核模式下的，如果设置了模式位，进程就运行在内核模式中（有时也称作超级用户模式），一个运行在内核模式下的进程可以执行指令集中的任何指令，并且可以访问系统中的任何内存位置；当没有设置模式位时，进程就运行在用户模式中，用户模式中的进程不允许执行任何的特权指令，比如停止处理器，改变模式位或者是发起一个IO操作，也不允许用户模式中的进程直接引用地址空间中位于内核区域的代码和数据。任何这样的尝试都会导致严重的保护故障。用户程序必须通过系统调用接口间接地访问内核代码和数据；
3. 运行应用程序代码的进程初始时是在用户模式下的，进程从用户模式切换到内核模式的唯一的方法就是通过诸如中断，故障或陷入系统调用这样的异常，当异常发生的时候，控制会传递到异常处理程序，处理器将模式从用户模式转变为内核模式。处理程序会运行在内核模式之中，当它返回到应用程序代码时，处理器就把模式从内核模式改回到用户模式。
4. 在Linux中，提供了一种叫做/prco的文件系统，它允许用户模式进程访问内核数据结构，它将许多内核数据结构的内容输出为一个用户程序可以读的文本文件的层次结构，比如可以使用/proc文件系统找出一般的系统属性，像CPU类型，某个特殊进程使用的内存段等；

6. 上下文切换

1. 操作系统内核使用一种叫做上下文切换的较高层次的异常控制流来实现多任务，即实现进程之间的切换。上下文切换是基于之前的较低层次的异常控制流；

2. 内核为每一个进程维护着一个上下文，上下文就是内核重新启动一个之前被抢占的进程所需要的状态，这些状态包括通用目的寄存器，浮点寄存器，程序计数器，用户栈，状态寄存器，内核栈和各种内核数据结构，包括描述地址空间的页表，包含有关进程信息的进程表，以及进程已打开文件的信息的文件表；

3. 在进程执行的某些时刻，内核可以决定抢占当前的进程，并重新开始一个先前被抢占了的目前正在处于挂起状态的进程，该过程叫做调度，具体选择哪一个进程是由相应的调度策略决定的，该过程由内核中称作调度器的代码完成。当内核选择了一个新的进程运行时，我们就说内核调度了这个进程。在内核调度了一个新的进程之后，它就抢占当前的进程，并使用一种上下文切换的机制来将控制转移到新的进程，上下文切换会进行以下的操作：

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

   当内核代表用户执行系统调用的时候，可能会发生上下文切换，如果系统调用因为需要等待某个事件而发生阻塞，那么内核会让当前的进程睡眠并切换到另外的进程，而不是非要等到事件发生的时候才使处理器重新处于忙碌状态。比如，如果一个read系统调用需要访问磁盘，内核可以选择进行上下文切换从而运行另外一个进程，而不是等到数据从磁盘到达。另外一个示例就是sleep系统调用，它会让调用进程休眠。一般而言即使是系统调用没有阻塞，内核也可以决定进行上下文切换，而不是将控制返回给调用进程；

4. 中断也可能会引发上下文切换，比如所有的系统都拥有某种产生周期性定时器中断的机制，通常为每1ms或者每10ms一次，每次发生定时器中断时，内核就可以判定当前的进程已经运行了足够长的时间，并决定切换到另一个进程；

5. 下图展示了一对进程A和B之间的上下文切换的过程：
   
   在这个例子中，进程A初始运行在用户模式下，之后它通过read系统调用陷入到内核，内核中的陷阱处理程序请求来自磁盘控制器的DMA传输，并且会安排在磁盘控制器完成从磁盘到内存的数据传输后，磁盘会发出一个中断信号中断处理器。磁盘读取数据需要一段相当长的时间，数量级是几十毫秒，所以内核会决定进行从进程A到进程B的上下文切换，而不是什么都不做。这里有一个点需要特别注意：在切换之前，内核正代表进程A在用户模式下执行指令，也就是说没有单独的内核进程。在切换的第一部分中，内核代表进程A在内核模式下执行指令，之后会在某一个时刻开始代表B在内核模式下执行指令。在切换完成之后，内核代表B在用户模式下执行指令。随后进程B会运行直到磁盘向处理器发送一个中断信号，表示数据已经从磁盘传送到了内存。内核在收到中断指令之后就会执行一个从进程B到进程A的上下文切换，将控制返回给进程A中紧随在系统调用read之后的那条指令，进程A继续运行，直到下一次异常发生。

7. fork函数

1. 父进程通过调用fork函数创建一个新的子进程，创建出来的子进程和父进程几乎是完全一样的，子进程会得到与父进程用户级虚拟地址空间相同的但是独立的一份副本，包括代码和数据段，堆，共享库以及用户栈，子进程还会获得父进程的打开文件描述符的一个副本，所以子进程可以读写父进程打开的任何文件。父进程以及子进程之间最大的差别就是它们的PID是不一样的。fork函数会返回两次，分别是在父进程以及子进程之中，在父进程中，fork函数会返回子进程的PID，在子进程中，fork函数会返回0，因为子进程的PID总是非零的，所以说我们可以根据返回的PID来区分子进程以及父进程。下图展示了一个使用fork创建子进程的父进程的示例，该程序在父进程中将x减一，在子进程中将x的值加一，然后我们可以看到我们所得到的结果：
   
   fork函数是比较奇怪的：

   • 调用一次，返回两次：fork函数被父进程调用一次，但是却返回两次，一次是返回到父进程，返回的是子进程的PID，还有一次是返回到创建的子进程，返回的值是0，具有多个fork实例的程序是非常复杂的；
   • 并发执行：创建出来的子进程和父进程是并发的运行的，各自是独立的进程，内核能够以任意的方式交替执行他们在逻辑控制流中的指令。在一次运行之中可能是先执行父进程中的语句然后再执行子进程中的语句，但是在另一次的执行之中所得到的顺序可能是截然相反的，我们无法对不同进程中的指令的交替执行做出任何的假设；
   • 相同但是独立的地址空间，子进程和父进程的地址空间是一样的，但是他们是相互独立的，所以说在父进程中对x进行修改不会影响到子进程，反过来也是如此；
   • 共享文件：子进程会得到父进程的打开文件描述符的一个副本，所以可以说子进程和父进程是共享文件的；

   下面的一段程序以及其对应的进程图会展示fork函数的执行特点：
   
   以上的程序中两次调用了fork函数，我们可以看到当父进程调用fork函数时会得到一个子进程，当再次调用fork函数的时候不仅仅原来的父进程会再次得到一个子进程，之前的到的子进程也会跟着调用一次fork函数，并得到一个属于自己的子进程，所以说拥有多个fork实例的程序是非常复杂的；

8. 回收子进程

1. 当一个进程因为某种原因而终止的时候，内核并不会立即把他从系统之中清除，进程会被保持在一种已终止的状态中，直到它被父进程回收。当父进程回收已经终止的子进程的时候，内核将子进程的退出状态返回给父进程，然后抛弃已终止的进程，从此时开始，该进程才是真正的不存在了。一个终止了但是还没有被回收的进程被称为僵尸进程；
2. 如果一个父进程终止了，那么内核会安排init进程成为它的孤儿进程的养父，init进程的PID为1，是在系统启动的时候由内核进行创建的，它不会终止，是所有进程的祖先，如果父进程没有回收它的僵死进程就终止了，那么内核会安排init进程去回收它们。不过，对于长时间运行的程序，比如说shell或者服务器，总是应该回收它们的僵死子进程，即使僵死子进程没有在运行，但是它们仍然消耗着系统的内存资源，一直不回收的话会导致内存泄漏。
3. 一个进程可以通过waitpid函数来等待它的子进程终止或停止：
   
   在默认情况下也就是options = 0时，该函数会挂起调用者进程，直到进程的等待集合中的一个子进程终止。如果等待集合中的一个进程在刚开始调用的时候就已经终止了，那么该函数会立即返回。以上的两种情况该函数都会返回导致该函数返回的已终止的子进程的PID。此时，已终止的子进程已经被回收，内核会从系统中删除掉它的所有痕迹。

4. 信号

1. 简介

1. 信号允许进程以及内核中断其它进程；信号就是一条小消息，它通知进程系统中发生了一个某种类型的事件，下图展示了Linux系统上支持的30种不同类型的信号：
   
   每一种信号类型都对应与某种系统事件。底层硬件异常是由内核异常处理程序处理的，正常情况下对用户进程是不可见的。为此信号提供了一种机制，通知用户进程发生了这些异常，比如如果一个进程试图除以0，那么内核就会发送给她一个SUGFPE信号等等。

2. 信号术语

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

• 发送信号：内核通过更新目的进程上下文中的某个状态来发送一个信号给目的进程，发送信号可能是因为内核检测到了一个系统事件，比如说除零错误或者是子进程终止；也可能是因为一个进程调用了kill函数，该函数会显示的要求内核发送一个信号给目的进程，当然进程可以给自己发送信号；
• 接收信号：当目的进程被内核以某种方式对信号的发送做出反应的时候，它就接受了信号。在接收信号之后进程可以忽略这个信号，也可以终止或者是执行一个叫做信号处理程序的用户层函数来捕获这个信号，下图展示了信号处理程序捕获一个信号的基本思想：
  
  一个发出但是没有被处理的信号叫做待处理信号，在任何时刻一种类型最多只会有一个待处理信号，如果一个进程已经有一个类型为k的待处理信号，那么任何接下来发送到这个进程的类型为k的信号都不会排队等待，而只是简单的被抛弃。一个进程可以选择性的阻塞接收某种信号，当一个信号被阻塞的时候，它仍可以被发送，但是产生的待处理信号不会被接收，直到进程取消对这种信号的阻塞；一个待处理信号最多只能被接收一次。内核为每一个进程在pending位向量中维护着一个待处理信号的集合，在blocked位向量中维护着被阻塞的信号的集合。只要传送了一个类型为k的信号，内核就会设置pending位向量中的第k位，只要接收了一个类型为k的信号，内核就会清除pending中的第k位。

3. 以上的信号机制都是基于进程组这个概念的，每一个进程都属于一个进程组，进程组是由一个正整数进程组ID来标识的；在默认情况下一个子进程和它的父进程同属于一个进程组。
4. Unix shell 使用作业这个抽象的概念来表示为对一条命令行求值而创建的进程。在任何时刻，至多只有一个前台作业和0个或多个后台作业，比如当我们键入 linux> ls | sort 的时候，会创建一个由两个进程组成的前台作业，这两个进程是通过Unix管道连接起来的：一个进程运行ls程序，另一个进程运行sort程序。shell会为每一个作业创建一个独立的进程组。进程组ID通常取自作业中父进程中的一个。比如在下图中展示了一个拥有一个前台作业和两个后台作业的shell，前台作业的父进程PID为20，进程组ID也为20。父进程创建了两个子进程，每个也都是进程组20的成员。
   

5. 非本地跳转

1. 像Java以及C++这种高级语言都拥有用户级的异常控制流形式，比如说Java中的try…catch语句块，同时C语言也提供了一种用户级的异常控制流形式，称为非本地跳转，它将控制直接从一个函数转移到另一个当前正在执行的函数，而不需要经过正常的调用返回程序，C语言的非本地跳转是通过setjmp以及longjmp实现的，setjmp函数会将当前的调用环境保存到缓冲区中，供后面的longjmp使用，并返回0。缓冲区中的调用环境包括程序计数器，栈指针，以及通用目的寄存器。longjmp函数会从缓冲区中恢复相应的调用环境，然后触发一个从最近一次初始化缓冲区的setjmp调用的返回，然后setjmp返回，并且会携带有非零的返回值。非本地跳转的一个非常重要的应用就是允许从一个深层嵌套的函数调用中立即返回，通常是由检测到某一个错误地情况引起的。这样的话我们就可以使用非本地跳转直接返回到一个普通的本地化的错误处理程序，而不是费力的解开调用栈。非本地跳转的另一种重要应用是使一个信号处理程序分支到一个特殊的代码位置，而不是返回到被信号到达中断了的指令的位置。
2. C++以及Java提供的异常机制是较高层次的，是C语言中的setjmp函数以及longjmp函数的更加结构化的版本。我们可以把try语句中的catch子句看做类似于setjmp函数，将throw语句看做类似于longjmp函数。

3. 虚拟内存

1. 简介

1. 一个系统中的进程和其它的进程一起共享CPU以及主存的资源。如果太多的进程都需要较大的内存空间，那么会有很多的进程根本就无法运行。同时内存很容易被破坏，如果一个进程错误地修改了另一个进程的地址空间，那么将会产生致命的错误。为了更加有效地管理内存并且减少出错的可能，现代系统提供了一种对主存的抽象的概念，叫做虚拟内存。从名字中就可以看出我们的一大目的就是提供一组虚拟的内存，使内存的大小看起来更大，从而能够正确的运行更多的进程，而不是使某一些进程根本就无法得到运行。就比如说有的大型游戏需要的内存最少是4GB，而我们自己的内存条却刚好只有4GB，再加上游戏之外的内存需求就已经超过了我们的内存条的大小，那么并不是说该游戏就不能够在我们的机器上运行，虚拟内存可以保证游戏能够正常的在我们的机器上运行，只不过有时候可能会特别的卡。虚拟内存（VM）是硬件异常，硬件地址翻译，主存，磁盘文件和内核软件的完美交互，它为每一个进程提供了一个更大的，一致的和私有的地址空间。虚拟内存提供了如下的三个重要的能力：

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

2. 物理寻址和虚拟寻址

1. 计算机系统中的内存被组织为一个由M个连续的字节大小的字节大小的单元组成的数组。每字节都有唯一的物理地址，第一个字节的地址为0，第二个字节的地址为1，以此类推。对于这种简单的结构，CPU访问内存的最自然的方式就是使用物理地址，我们把CPU直接寻找物理地址的过程称为物理寻址，下图展示了物理寻址的示例，该示例的上下午是一条加载指令，它会读取从物理地址4处开始的连续的4字节字。当CPU加载这条指令的时候就会生成一个有效的物理地址，并通过内存总线将该地址传递给主存，主存在得到地址之后会取出从物理地址4处开始的4字节字，并将它返回给CPU，CPU会将得到的4字节字存放在一个寄存器中；
   
   早期的PC以及现在的数字信号处理器，嵌入式微控制器以及Cray超级计算机等系统使用的是物理寻址，但是现代处理器使用的是一种称为虚拟寻址的寻址形式，如下图所示：
   
   使用虚拟寻址时CPU并不会直接生成一个物理地址而是通过生成一个虚拟地址来访问主存，这个虚拟地址在被送到内存之前会先转换为适当的物理地址，将一个虚拟地址转换为一个物理地址的过程叫做地址翻译，就像异常处理一样，地址翻译需要CPU硬件和操作系统之间的紧密合作。CPU芯片上叫做内存管理单元（Memory Management Unit，MMU）的专用硬件会利用存放在主存中的查询表来动态翻译虚拟地址，该表的内容由操作系统管理。

3. 地址空间

1. 地址空间是一个非负整数地址的有续集和：
   {0,1,2,…}
   如果地址空间中的整数是连续的，那么我们说它是一个线性地址空间。我们这里讨论的各种知识点都是基于线性地址空间的。在一个带有虚拟内存的系统中CPU会从一个拥有N=2^n个地址的地址空间中生成虚拟地址，这个被生成的虚拟地址的集合叫做虚拟地址空间；

2. 一个地址空间的大小是由表示最大地址所需的位数来描述的，例如一个包含N=2^n个地址的虚拟地址空间就叫做一个n位地址空间。现代系统通常支持32位或者64位虚拟地址空间，一个系统还有一个物理地址空间，对应于物理内存的M个字节；虽说M不要求是2的幂，但是为了简化我们假设 M = 2^m；

3. 地址空间的概念是很重要的，因为它清楚的区分了数据对象（字节）和它们的属性（地址）。我们可以允许每一个数据对象有多个独立的地址，其中的每个地址都选自不同的地址空间。这就是虚拟内存的基本思想。主存中的每个字都有一个选自虚拟地址空间的虚拟地址和一个选自物理地址空间的物理地址。

4. 虚拟内存作为缓存的工具

1. 简介

1. 从概念上来讲，虚拟内存被组织为一个由存放在磁盘上的N个连续的字节大小的单元组成的数组。每字节都有唯一的虚拟地址来作为到数组的索引。磁盘上数组的内容被缓存到主存中。和存储器层次结构中其它缓存一样，磁盘上的数据被分割成块，这些块作为磁盘和主存之间的传输单元。VM系统通过将虚拟内存分割为称为虚拟页（Virtual Page，VP）的大小固定的块来处理这个问题。每一个虚拟页的大小是P = 2^p字节。类似地，物理内存被分割为物理页（Physical Page），大小也是P字节，物理页也被称作页帧。在任意的时刻，虚拟页面的集合都分为三个不相交的子集：

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

   下图展示了一个拥有8个虚拟页的小虚拟内存，虚拟页0和虚拟页3还没有被分配，因此在磁盘上还不存在。虚拟页1,4和6被缓存在物理内存中。虚拟页2,5和7虽然已经被分配了，但是它们还没有被缓存在物理内存中，所以说它们的状态是未缓存的。
   

2. DRAM缓存的组织机构

1. 在这里使用SRAM缓存来表示位于CPU和主存之间的L1，L2和L3高速缓存，使用DRAM缓存表示虚拟内存系统的缓存，它在主存中缓存虚拟页；
2. 在存储层次结构中，DRAM缓存的位置对它的组织结构有很大的影响。DRAM比SRAM要慢大约10倍，而磁盘比DRAM慢大约100000多倍，因此DRAM缓存中的不命中比起SRAM缓存中的不命中要昂贵的多。DRAM的缓存不命中需要磁盘来服务，但是SRAM的缓存不命中通常是基于DRAM主存来服务的。而且从磁盘中的一个扇区读取第一个字节的时间开销比起读这个扇区中连续的字节要慢大约100000倍，归根到底DRAM缓存的组织结构完全是由巨大的不命中开销驱动的。
3. 因为巨大的不命中处罚和访问第一个字节的开销，虚拟页往往是非常大的，通常是4KB~2MB。由于大的不命中处罚，所以为了降低不命中，DRAM缓存是全相联的，即任何的虚拟页都可以放置在任何的物理页中。不命中时的替换策略也是很重要的，因为替换错了虚拟页所带来的处罚也是很高的。因此与硬件对SRAM缓存相比，操作系统对DRAM缓存使用了更加复杂精密的替换算法。对于写的问题，由于对磁盘的访问时间很长，所以DRAM在向磁盘写数据的时候所采用的总是写回而不是直写。

3. 页表

1. 同任何的缓存一样，虚拟内存系统必须有某种方法来判定一个虚拟页是否缓存在DRAM中的某个地方。如果虚拟页缓存在DRAM中，系统还必须确定这个虚拟页存放在哪个物理页中。但是如果发生了不命中，也就是相应的虚拟页并没有被缓存在DRAM中，那么系统必须判断这个虚拟页存放在磁盘中的哪个位置，在找到该虚拟页在磁盘中的存放位置之后，如果DRAM还可以容纳更多的页面的话，那么就直接将相应的虚拟页放置在DRAM之中，否则系统就在物理内存中选择一个牺牲页，并将虚拟页从磁盘复制到DRAM中，替换掉这个牺牲页。
2. 以上的功能都是由软硬件结合起来完成的，包括操作系统软件，MMU内存管理单元中的地址翻译硬件和一个存放在物理内存中叫做页表的数据结构，页表将虚拟页映射的物理页。每次地址翻译硬件将一个虚拟地址转换为物理地址时，都会读取页表。操作系统负责维护页表的内容，以及在磁盘与DRAM之间来回传送页。
3. 下图展示了一个页表的基本组织结构。页表就是一个页表条目（Page Table Entry，PTE）的数组。虚拟地址空间中的每个页在页表中一个固定偏移量处都有一个PTE。在这里假设每个PTE是由一个有效位和一个n位地址字段组成的。有效位表明该虚拟页当前是否缓存在DRAM之中，如果设置了有效位则表明该表目中的地址字段就表示DRAM中相应的物理页的起始地址，这个物理页就是相应的虚拟页的缓存。如果没有设置有效位，那么当地址字段是空的时候就表示这个虚拟页还未被分配。否则这个地址就指向该虚拟页在磁盘上的起始位置。
4. 下图展示了一个拥有8个虚拟页和4个物理页的系统的页表。其中VP1, VP2, VP4和VP7当前已经被缓存在DRAM中，VP0和VP5这两个页还未被分配，虚拟页VP3和VP6已经被分配了但是还没有被缓存在DRAM之中。因为DRAM缓存是全相联的，所以任意的物理页都可以包含任意的虚拟页。

4. 页命中

1. 当CPU想要读取包含在VP2中的虚拟内存的一个字时，地址翻译硬件会将虚拟地址作为一个索引来定位到PTE2，并从内存中读取它。因为设置了有效位，那么地址翻译硬件就会知道VP2是已经缓存在内存中的了。所以它会使用PTE中的物理内存地址（改地址指向PP1中缓存页的起始位置），构造出这个字的物理地址，过程如下图所示：
   

5. 缺页

1. 我们在虚拟内存系统中称DRAM缓存不命中为缺页，下图展示了缺页的情况：
   
   CPU引用了VP3中的一个字，但是VP3并没有缓存在DRAM之中。地址翻译硬件从内存中读取PTE3，发现有效位并没有被设置，所以地址翻译硬件会得到VP3并没有被缓存的结论，并触发一个缺页异常，。缺页异常会调用内核中的缺页异常处理程序，该程序会选择一个牺牲页，在此例中就是存放在PP3中的VP4；如果VP4已经被修改了，那么内核就会将它复制回磁盘。无论哪一种情况内核都会修改VP4的页表条目，将VP4替换出去；之后内核会从磁盘中复制VP3到内存中的PP3并更新PTE3，随后返回。当异常处理程序返回的时候，它会重新启动导致缺页的指令，该指令会把导致缺页的虚拟地址重新发送到地址翻译硬件。此时VP3已经被缓存到DRAM之中了，地址翻译硬件就可以正常进行处理。在虚拟内存的习惯说法中，将数据块称为页。在缓存和内存之间传送页的活动叫做交换（swapping）或者页面调度。当有不命中发生时才换入页面的策略称为按需页面调度。也可以尝试预测不命中，在页面实际被引入之前就换入页面，然而几乎所有的现代系统使用的都是按需页面调度的方式。
   

6. 分配页面

下图展示了当操作系统分配一个新的虚拟内存页时对我们示例页表的影响，例如当我们调用malloc函数分配VP5的时候，系统会在磁盘上创建空间并更新PTE5，使它指向磁盘上这个新创建的页面。对于一个页表条目，如果有一个页面已经被分配在了虚拟内存上但是还没有被缓存在物理内存中，那么页表条目指向虚拟内存地址，如果页面缓存在了物理内存中，那么页表条目指向物理内存地址。

7. 局部性带来的效果

1. 如果没有局部性的存在，虚拟内存的效率应该是比较低的，因为不命中所带来的开销是很大的，因此页面调度可能会破坏程序的性能，但是实际上虚拟内存工作的很好；
2. 尽管在整个运行过程中程序引用的不同页面的总数很可能超出了物理内存的总大小，但是局部性原则保证了在任意的时刻程序将趋向于在一个较小的活动页面集合上工作，这个集合叫做工作集或者常驻集合。在初始开销，也就是将工作集页面调度到内存中之后，接下来对这个工作集的引用将导致命中，而不会产生额外的磁盘流量。
3. 只要我们所编写的程序具有好的时间局部性，虚拟内存系统就能工作的相当好，如果工作集的大小超过了物理内存的大小，那么程序将会产生抖动，这时页面将会不断地换进换出。虽然虚拟内存通常是有效的，但是当出现抖动的时候程序还是会执行的很慢。

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

操作系统为每一个进程提供了一个独立的页表，也就相当于为每一个进程提供了一个独立的虚拟地址空间。下图展示了其基本的思想：

在以上的示例中，进程 i 的页表将VP1映射到PP2，VP2映射到PP7；进程 j 的页表将VP1映射到PP7，VP2映射到PP10，多个虚拟页面可以映射到同一个共享物理页面上。VM系统简化了链接和加载，也简化了代码和数据共享，同时也使得应用程序的内存分配方式更加的简洁。

1. 简化链接：独立的地址空间允许每个进程的内存映像使用相同的基本格式，而不管代码和数据实际存放在物理内存的何处。这样的一致性极大地简化了连接器的设计和实现，允许连接器生成完全链接的可执行文件，这些可执行文件独立于物理内存中代码和数据的最终位置；
2. 简化加载：虚拟内存使得我们更加容易地向内存中加载可执行文件和共享对象文件。比如要把目标文件中的.text和.data节加载到一个新创建的进程中，Linux加载器为代码和数据段分配虚拟页。但是加载器从不从磁盘到内存实际复制任何数据。在每个页初次被引用的时候，要么是CPU取指令时引用的，要么是一条正在执行的指令引用一个内存位置时引用的，虚拟内存系统会按照需要自动地调入数据页；
3. 简化共享：独立地址空间为操作系统提供了一个管理用户进程和操作系统自身之间共享的一致机制。一般而言每个进程都有自己的私有代码，数据，堆以及栈区，这些内容是不和其它的进程共享的。在这种情况下操作系统负责创建页表，将相应的虚拟页映射到不连续的物理页面。但是在一些情况之中仍然需要进程来共享代码和数据。例如每个进程必须调用相同的操作系统内核代码，以及每个C程序都必须调用C标准库之中的程序。操作系统将不同进程中适当的虚拟页面映射到相同的物理页面。从而安排多个进程共享这部分代码的一个副本，而不是在每一个进程中都包括单独的内核以及C标准库的副本；
4. 简化内存分配：虚拟内存为用户进程中的程序提供了一个简单的分配额外内存的机制。当一个运行在用户进程中的程序要求额外的堆空间的时候，操作系统会分配一个适当的 k 个连续的虚拟内存的页面。并且将它们映射到物理内存中任意位置的 k 个任意的物理页面。由于页表的工作方式，操作系统没有必要分配 k 个连续的物理内存页面。页面可以随机的分散在物理内存中；

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

现代计算机都需要为操作系统提供一些方法来控制对内存系统的访问。不允许一个用户进程修改只读的代码段，同时也不允许用户进程修改任何内核中的代码和数据结构，也不允许用户进程读取其它进程的私有内存区域，不允许用户进程修改任何修与其它进程共享的虚拟页面。除非所有的共享者都显示地声明允许修改共享的虚拟页面。地址翻译机制可以通过在页表项（PTE）上添加一些额外的许可位来控制对一个虚拟页面内容的访问。下图展示了这种做法的大致思想：

在这个示例中，每一个PTE增加了3个许可位。SUP表示进程是否必须运行在超级用户模式，也就是内核之下才能够访问该页面。运行在内核模式中的进程可以访问任何页面，但是运行在用户模式下的进程却只能够访问SUP位为0的页面，READ位和WRITE位控制对页面的读和写访问。例如如果进程 i 运行在用户模式下，那么它有读VP0和写VP1的权限，但是不允许它访问VP2。如果一条指令违反了许可条件，那么CPU就会触发一个一般保护故障，将控制传递给一个处于内核之中的异常处理程序，Linux shell 一般将这种异常称作段错误。

7. 地址翻译

1. 整体步骤

下图展示了在介绍地址翻译的过程中将会使用到的符号：

如果我们将地址翻译进行抽象的话，那么可以说地址翻译是一个N元素的虚拟地址空间中的元素和一个M元素的物理地址空间中元素的映射，下图展示了MMU是如何利用页表实现以上的映射的。其中页表基址寄存器（Page Table Base Register，PTBR）是CPU中的一个控制寄存器，它保存有页表在物理内存中的起始地址；n 位的虚拟地址空间包含有两个部分，一个 p 位的虚拟页面偏移量（Virtual Page Offset，VPO），它作为要读取的数据在虚拟页面中的偏移量；和一个 n - p 位的虚拟页号（Virtual Page Number，VPN），它作为到页表中的索引：

MMU内存管理单元会利用VPN来选取适当的PTE。例如VPN0会选取PTE0，VPN1会选取PTE1，以此类推。最终我们将页表条目中的物理页号（Physical Page Number，PPN）和虚拟地址中的VPO串联起来，就可以得到相应的物理地址。由于物理页面和虚拟页面都是P字节的，所以物理页面偏移量（Physical Page Offset，PPO）和 VPO是相同的。

下入展示了当页命中时CPU硬件执行的步骤：

1. 处理器生成一个虚拟地址VA，并将其传送给MMU；
2. MMU生成一个页表项地址PTEA，并从高速缓存/主存中请求得到页表项；
3. 高速缓存和主存返回PTE给MMU；
4. MMU构造物理地址PA，并将它传送给高速缓存/主存；
5. 高速缓存/主存返回所请求的数据字给处理器；
   

页命中完全是由硬件来处理的，与之不同的是，处理缺页的时候要求硬件和操作系统内核协作完成，步骤如下所示：

1. 第 1 步到第 3 步与不缺页时的步骤是一样的；
2. 第 4 步：由于PTE中的有效位是0，所以MMU会触发一个缺页异常，传递CPU中的控制到操作系统内核中的缺页处理程序；
3. 第 5 步：缺页处理程序会确定出物理内存中的牺牲页，如果这个页已经被修改了，那么就将其同步回磁盘；
4. 第 6 步：缺页处理程序调入所需的新的页面，并更新内存中的PTE；
5. 第 7 步：缺页处理程序返回到原来的进程再次执行导致缺页的指令。之后就可在在不发生缺页的情况下得到所需的数据了。
   

2. 结合高速缓存和虚拟内存

下图展示了一个物理寻址的高速缓存是如何和虚拟内存结合起来的，主要思路是将高速缓存放在MMU和内存之间：

3. 利用TLB加速地址翻译

每次CPU产生一个虚拟地址，MMU就必须查阅一个PTE，将虚拟地址翻译为物理地址，查阅的代价是几十都几百个周期。如果我们将PTE缓存在L1之中，那么查询PTE的开销就会下降到 1 个或 2 个周期。然而许多系统甚至试图消除这样的开销，这类系统在MMU中包括了一个关于PTE的小的缓存，称为翻译后备缓冲器（Translation Lookaside Buffer，TLB）。TLB是一个小的，虚拟寻址的缓存，其中每一行都保存有一个由单个PTE组成的块，TLB通常具有很高的相联度，如图所示，用于组选择和行匹配的索引和标记字段是从虚拟地址中的虚拟页号中提取出来的。如果TLB有T = 2^t 个组，那么TLB索引（TLBI）就是由VPN的 t 个最低位组成的，而TLB标记（TLBT）是由VPN中剩余的位组成的。下图展示了当TLB命中时所包括的所有步骤。所有的地址翻译步骤都是在芯片上的MMU中执行的，因此执行的非常的快：

1. CPU产生一个虚拟地址；
2. MMU从TLB中取出相应的PTE；
3. MMU利用得到的PTE将虚拟地址翻译成一个物理地址；
4. 高速缓存/主存将所请求的数据字返回给CPU；

当TLB不命中的时候MMU必须从L1缓存中取出相应的PTE，然后将新取出的PTE存放在TLB中，这个过程可能会覆盖一个已经存在的条目：

4. 多级页表

1. 我们之前展示的例子都是只有一个单独的页表，但是实际上单独的页表会导致页表所占用的内存是巨大的，比如说一个32位的地址空间，它的最大内存为 2^32 = 4GB，而不是4Gb，不能够将这里的32位理解为32bit，假设一个页的大小是4KB，一个页表项的大小是4B，那么系统中一共有4GB/4KB = 1024K 的页面，那么页表的大小就是 4 * 1024 * 1024B = 4MB，可以看到最终的页表大小是很大的，占用了过多的内存；

2. 减少页表占用内存大小的最常用的方法就是使用层次结构的页表，也就是多级页表。还是假设一个32位的虚拟地址空间，每一个页面（数据块）的大小是4KB，那么一共有1024K个页面，每一个页表条目的大小为4B，下图展示了为一个虚拟地址空间构造的两级页表层次结构：
   
   一级页表中的每个PTE负责映射虚拟地址空间中一个4MB的片，这里每一个片都是由1024个连续的页面组成的；如果片 i 中的每一个页都没有被分配，那么PTEi就为空，如果在片i中至少有一个页是分配了的，那么一级PTEi就指向一个二级页表的基址，就像上图中的PTE0，PTE1以及PTE8。它们指向了二级页表。使用二级页表的话，如果一级页表中的一个PTE是空的话，那么相应的二级页表根本就不会存在，这就大大的减少了对内存的占用，因为对于一个典型的应用程序来说，4GB的虚拟地址空间中的大部分都是未分配的。除此之外，只有一级页表才需要总是存储在内存之中，在以上的实例之中一级页表的大小仅仅是4KB；二级页表只有在需要的时候才会存储在内存中，一个二级页表的大小也是4KB。

3. 如图展示了使用 k 级页表层次结构的地址翻译示意图，虚拟地址空间被分为 k 个VPN和 1 个VPO。每个VPNi都是一个到第 i 级页表的索引，其中 1 <= i <= k，第 j 级页表中的每一个PTE都指向第 j + 1 级某个页表的基址。如果我们将要寻找的页面已经被缓存在了物理内存之中，那么第 k 级页表中的每个PTE包含有某个物理页面的PPN，否则的话将会包含一个磁盘地址。VPO的位数是根据页面的大小确定的，VPN的位数是根据页表项的数目决定的：
   
   虽说多级页表看上去是昂贵的，但是TLB起到了关键的作用，通过将不同层次上页表的PTE缓存起来，使得多级页表的地址翻译并不会比单级页表的地址翻译慢很多。

8. Intel Core i7/Linux内存系统

1. Core i7 地址翻译

1. 虽然一个运行Linux的 i7 底层的Haswell微体系结构允许完全的64位虚拟和物理地址空间，但是现在的 i7 实现的是48位（256TB）虚拟地址空间和52位（4PB）物理地址空间，还有一个兼容模式用以支持32位（4GB）虚拟和物理地址空间。下图给出了Core i7内存系统的重要组成部分。处理器封装包含有四个核，一个所有核共享的L3高速缓存，还有一个DDR3内存控制器。每个核包含一个层次结构的TLB，一个层次结构的数据和指令高速缓存，以及一组快速的点到点链路，这种链路基于QuickPath技术，是为了让一个核与其它核和外部IO桥直接通信。TLB是虚拟寻址的并且L1和L2的TLB是 4 路相联的。L1, L2以及L3的高速缓存是物理寻址的，块的大小是64字节。L1, L2高速缓存是8路相联的，L3高速缓存是16路相联的。页的大小可以在启动时被配置为4KB或者是4MB。在Linux中使用的是4KB的页：
   

2. 下图给出了完整的i7地址翻译过程，i7采用四级页表层次结构。每个进程都有他自己私有的页表层次结构。当一个Linux进程在运行的时候，虽说i7体系结构允许将页表换进换出，但是与已经分配了的页相关联的页表都是驻留在内存中的。CR3控制寄存器指向第一级页表（L1）的起始位置，CR3的值是每一个进程上下文的一部分，每次发生上下文切换时，CR3的值都会被恢复。
   
   CPU会发出一个虚拟地址VA，由于TLB是利用VPN的位进行虚拟寻址的，所以MMU会根据虚拟地址的VPN去查询TLB，由于Linux的页面大小是4KB，所以虚拟页面偏移量VPO占有12位，用以表示4K个地址，每一个地址中可存储的数据是 1 个字节；又因为i7是48位的，所以VPN就有36位；L1 d-TLB是 4 路相联并且拥有64个条目，所以L1 d-TLB一共有16组，可得L1 d-TLB的组索引（TLBI）占有4位，那么剩下的32位（VPN 36 - 4）就是TLB标记位TLBT，组索引用于确定所要寻找的PPN位于哪一个组，而标记位用来区别可能映射到同一个TLB组的不同的VPN。这样就可以根据VPN在TLB中唯一地确定我们需要的PPN（如果存在的话）。如果TLB命中MMU就可以将得到的PPN和PPO（和VPO相同）组合在一起得到物理地址PA，否则的话就会去页表中查找PPN；得到PA之后MMU就会去高速缓存中寻找所缓存的数据。高速缓存是物理寻址的，直接映射的缓存是通过物理地址中的字段来寻址的，因为Linux i7中的每个数据块是64字节并且物理地址是52位，所以物理地址中的低6位作为块偏移CO，由于L1 d-cache有64组，所以接下来的6位就用来表示组索引CI，而剩下的40位就用来作为标记CT。如果根据组索引CI以及标记CT可以确定唯一的一行，那么我们就可以根据块偏移CO得到我们所需的数据，然后将所得到的数据返回给CPU，这就是L1高速缓存命中的情况。如果发生的L1不命中，那么MMU就会根据PA在主存中确定所需数据的起始地址，然后读取所需的数据并将结果返回给CPU。以上就是运行Linux的Intel Core i7的地址翻译过程。

3. 下图展示了第一级，第二级以及第三级页表中条目的格式，当 P = 1时（在Linux中就总是如此），地址字段包含一个 40 位的物理页号（PPN），它指向适当的页表的开始处。这里有一个要求就是物理页表必须是4KB对齐的。
   
   下图展示了第四级页表中条目的格式。当 P = 1的时候，地址字段包含一个 40 位的PPN，它指向物理内存中某一个页的基地址，这又加强了一个要求，要求物理页是4KB对齐的。
   
   注意以上的示意图之中有些许的瑕疵，第12至51位表示的应该是页物理基地址而不是页表物理基地址；P位1时表示的是页在物理内存中而不是子页表在物理内存中。XD位是在64位操作系统之中引入的，可以用来禁止从某些内存页之中取指令，这样子就可以限制只能执行只读代码段，使得操作系统内核降低了缓冲区溢出攻击的风险；

4. 当MMU翻译每一个物理地址时，它还会更新另外两个内核缺页处理程序在系统发生缺页的时候需要用到的位。每次访问一个页时，MMU都会设置A位，称为引用位，内核可以利用这个引用位来实现它的页替换算法。当对一个页面进行了写操作的时候，MMU会设置D位，该位也称为修改位或脏位。修改位告诉内核在复制替换页之前是否必须写回牺牲页，将修改同步到磁盘。内核可以通过调用一个特殊的内核指令来清除以上提到的引用位和修改位。他们都是在替换页面时所要用到的位。

5. 下图给出了Core i7 MMU如何使用四级的页表来将虚拟地址翻译成物理地址。其中36位的VPN被划分成了四个9位的片，每个片被用作到一个页表的偏移量。CR3寄存器包含了L1页表的物理地址。VPN1提供到一个L1 PTE的偏移量，这个PTE包含了L2页表的基地址，以此类推，直到VPN4包含一个L4 PTE的偏移量，这个PTE包含了我们所需页的物理地址。
   

6. 优化地址翻译：在对地址翻译的过程中我们描述了一个顺序的两个步骤的过程：一是MMU将虚拟地址翻译为物理地址；二是将物理地址传送到L1高速缓存。然而实际的硬件实现使用了一个巧妙地方式，允许以上的步骤存在部分重叠，因此也就加速了对L1高速缓存的访问。例如页面大小为 4KB 的 Core i7 系统上的一个虚拟地址有12位的VPO，并且这些位和相应的物理地址中的PPO的12位是相同的。因为 8 路组相联的，物理寻址的L1高速缓存有64个组和大小为64字节的缓存块。所以物理地址有6个块偏移位和6个组索引位。这12位恰好符合虚拟地址的VPO部分。当CPU需要翻译一个虚拟地址的时候，它就发送VPN到MMU，发送VPO到高速L1缓存。当MMU向TLB请求一个页表条目时。L1高速缓存就会利用VPO位查找相应的组，并读出组里面的 8 行数据，包括8个标记和相应的数据字。当MMU利用VPN得到PTE进而得到物理地址中的PPN时，高速缓存就可以将得到的8个标记与PPN进行比较，进而将PPN与这8个标记中的其中一个进行匹配，最终得到我们所需的数据。

2. Linux虚拟内存系统

1. Linux为每一个进程维护了一个单独的虚拟地址空间，形式如下图所示。其中内核虚拟内存包含内核中的代码和数据结构。内核虚拟内存中的某些区域被映射到所有进程共享的物理页面。例如每一个进程都共享内核的代码和全局数据结构。
   
   Linux将一组连续的虚拟页面（大小等于系统中DRAM的总量）映射到相应的一组连续的物理页面。这就为内核提供了一种便利的方法来访问内存中任何特定的位置。例如，当内核需要访问一个页表的时候；或者当内核在一些设备上执行内核映射的IO操作而这些设备被映射到了特定的物理内存位置时。内核虚拟内存的其它区域包含每一个进程都不相同的数据。比如说页表。内核在进程的上下文中执行代码时使用的栈，以及记录虚拟地址空间当前组织的各种数据结构。

2. Linux虚拟内存区域：Linux将虚拟内存组织为一些区域（段）的集合。一个区域就是一个已经存在的（已分配的）虚拟内存的连续片，这些页是以某种方式相关联的。例如代码段，数据段，堆，共享库段，以及用户栈都是不同的区域。每个存在的虚拟页面都保存在某个区域中，而不属于某个区域的虚拟页是不存在的（因为根本就没有被分配）并且不能够被进程引用。区域的概念是很重的，因为这允许了虚拟地址中存在间隙。内核不用去记录那些不存在的虚拟页，这样的页不会占用磁盘以及内存空间，同时也不会占用内核本身中的任何资源。

3. 下图展示了一个进程中虚拟内存区域的内核数据结构。内核为系统中的每个进程维护一个单独的任务结构task_struct，任务结构中的元素包含或指向内核运行该进程所需要的所有信息，例如PID，指向用户栈的指针，可执行目标文件的名字，以及程序计数器等：
   
   内核结构中的一个条目指向mm_struct，它描述了虚拟内存的当前状态，其中很重要的两个字段分别是pgd和mmap，pgd指向第一级页表的基址，而mmap指向一个区域结构vm_area_structs的链表，链表中的每一个vm_area_struct都描述了当前虚拟地址空间的一个区域。当内核运行这个进程时，就将pgd存放在CR3控制寄存器中。一个具体区域的区域结构包含以下的字段：

   • vm_start：指向区域的起始处；
   • vm_end：指向区域的结束处；
   • vm_port：描述这个区域内包含的所有页的读写许可权限；
   • vm_flags：描述这个区域内的页面是与其他进程共享的还是这个进程私有的（当然还包括其它的一些信息）；
   • vm_next：指向链表的下一个区域结构；

4. Linux缺页异常处理：假设MMU在试图翻译某个虚拟地址A的时候触发了一个缺页异常。这个异常会导致控制转移到内核中的缺页处理程序，处理程序随后会执行以下的步骤：

   • 首先会判断虚拟页是否是合法的，也就是会判断虚拟页是否在某个区域结构定义的区域内。缺页处理程序会搜索区域结构的链表，把A和每个区域结构中的vm_start和vm_end作比较。如果这个指令是不合法的，那么缺页处理程序就会触发一个段错误，从而终止这个进程；因为一个进程可以创建任意数量的新虚拟内存区域，所以顺序搜索区域结构的链表所带来的开销可能是比较大的。因此在实际的情况下，Linux会使用一些字段在链表中创建一棵树，并在这棵树上进行查找；
   • 然后判断试图进行的内存访问是否是合法的，也就是判断进程是否有读，写或者是执行这个区域内页面的权限；例如这个缺页是否是由一条试图对代码段之中的只读页面进行写操作的存储指令造成的；或者说这个指令是否是因为一个运行在用户模式下的进程试图从内核虚拟内存中读取字造成的。如果试图进行的访问是不合法的，那么缺页处理程序会触发一个保护异常从而终止这个进程；
   • 如果这个缺页不是以上的情况造成的，那么内核就会得到缺页是由于对合法的虚拟地址进行的合法的操作造成的。那么缺页处理程序就会选择一个牺牲页面，如果这个牺牲页面被修改过，那么就将其交换出去，换入新的页面并更新页表。当缺页处理程序返回时，CPU会重新启动引起缺页的指令，这条指令会再次将A发送给MMU。此时MMU就可以正常地翻译A而不会再产生缺页中断了。
     

9. 内存映射

1. 概念

Linux系统会将一个虚拟内存区域与一个磁盘上的对象关联起来，用以初始化虚拟内存区域中的内容。这个过程称作内存映射。虚拟内存区域可以映射到以下两种类型的对象中的一种：

1. Linux文件系统中的普通文件：一个区域可以映射到一个普通磁盘文件的连续部分，例如一个可执行文件。文件区被分为页大小的片，每个片包含一个虚拟页面的初始内容。因为按需进行页调度，所以这些虚拟页面没有实际交换进入物理内存直到CPU第一次引用到页面。如果一个区域的大小比文件区要大，那么就用0来填充这个区域的剩余部分；
2. 匿名文件：一个区域也可以映射到一个匿名文件，匿名文件是由内核创建出来的，其中包含的全都是二进制的0。CPU第一次引用这样一个区域内的虚拟页面时，内核就会在物理内存中找到一个合适的牺牲页面，如果该页面已经被修改过了，就将这个页面换出来，用二进制0覆盖牺牲页面的那一部分并更新页表，将这个页面标记为是已经驻留在内存中的。注意在磁盘以及内存之间并没有实际的数据传输。所以映射到匿名文件的区域中的页面有时也叫作请求二进制零的页；

但是无论是以上的哪一种情况，一旦一个虚拟页面被初始化了，它就在一个由内核维护的专门的交换文件之间换来换去。交换文件也叫作交换空间或交换区域。在任何时刻，交换空间都限制着当前运行着的进程能够分配的虚拟页面的总数。

2. 共享对象

1. 如果虚拟内存系统可以集成到传统的文件系统中，那么就能够提供一种简单而高效的把程序和数据加载到内存中的方法。进程这一抽象能够为每个进程提供自己私有的虚拟地址空间，可以免受来自其他进程的错误读写，但是许多进程有同样的只读代码区域。比如每个运行Linux shell程序bash的进程都有相同的代码区域。而且许多程序需要访问只读运行时库代码的相同副本。比如每个C程序都需要来自标准C库中诸如printf这样的函数。所以如果每一个进程都在内存中保存着那些常用代码的副本的话，那就太浪费空间了。内存映像可以帮助我们控制多个进程共享对象。一个对象可以被映射到虚拟内存中的一个区域，要么作为共享对象，要么作为私有对象。如果一个进程可以将一个共享对象映射到它的虚拟地址空间中的一个区域内，那么这个进程对这个区域内的任何写操作，对于那些同样把这个共享对象映射到它们自己的虚拟内存的其他进程而言，也是可见的。而且这些变化会反映在磁盘上的原始对象中。另外，对于一个映射到私有对象的区域做的改变对于其他进程来说是不可见的，并且进程对这个区域所做的任何写操作都不会反映在磁盘上的对象中。一个映射到共享对象的虚拟内存区域叫做共享区域，一个映射到私有对象的虚拟内存区域叫做私有区域。

2. 假设下图中的进程1将一个共享对象映射到它的虚拟内存的一个区域中，并且进程2将同一个共享对象映射的它的虚拟内存的一个区域中（并不一定和进程1在相同的虚拟地址处）。因为每一个对象都有唯一的文件名，所以内核可以迅速地判定进程1已经映射了这个对象，并且可以令进程2中的页表条目指向相应的物理页面。即使共享对象被映射到了多个区域，物理内存也只需要存放共享对象的一个副本。图中的物理页面显示的是连续的，但是在实际上往往不是连续的。
   

3. 对于私有对象，会使用一种叫做写时复制（copy-on-write）的技术被映射到虚拟内存中。一个私有对象开始生命周期的方式基本上和共享对象是一样的，在物理内存中只保存有私有对象的一个副本。比如在下图所示的例子中，两个进程将一个私有对象映射到它们虚拟内存的不同区域中，但是共享这一个对象的同一个物理副本。对于每一个映射私有对象的进程，相应的私有区域的页表条目都被标记为只读，并且区域结构被标记为私有的写时复制。只要没有进程试图写它自己的私有区域，他们就可以继续共享物理内存中对象的一个单独副本。只要有一个进程试图写私有区域内的某一个页面，那么这个写操作就会触发一个保护故障。
   
   之后故障处理程序会注意到保护异常是由于进程试图写私有的写时复制区域中的一个页面而引起的，之后处理程序就会在物理内存中创建这个页面的一个新副本，并更新页表条目指向这一个新的副本，然后恢复这个页面的可写权限，如上图所示。当故障处理程序返回时，CPU会重新执行这个写操作，现在在新创建的页面上这个写操作就可以正常执行了。通过这种方式，一个进程的写操作是不会改变原有的私有对象的，改变的只是私有对象中的页的一个副本，这种改变对其它进程来所不可见，并且也不用同步回磁盘。写时复制技术通过采取只有在一个进程写私有对象的时候才将私有对象中的副本创建出来的方法，充分地使用了稀有的物理内存。

4. 通过以上的知识，我们可以得出fork函数是怎么创建一个带有调用者独立地址空间的新进程的；当fork函数被当前进程调用时，内核会为子进程创建各种的数据结构，并分配给它唯一的PID，为了给这个新进程创建虚拟内存，它创建了当前进程的mm_struct，区域结构和页表的原样副本。它会将父进程以及子进程的每个页面都标记为只读，并将两个进程中的每个区域结构都标记为私有的写时复制。当fork函数在新进程中返回时，新进程现在的虚拟内存刚好和父进程调用fork时存在的虚拟内存相同，当这两个进程中的任意一个执行写操作的时候，写时复制机制就会创建新页面，因此也就为每个进程保持了私有地址空间的抽象概念。此外，进程的地址空间结构中的各个区域的私有以及共享情况如下所示：
   

10. 动态内存分配

1. 相关概念

1. 在C语言中，动态内存分配是由动态内存分配器完成的。动态内存分配器维护着一个进程的虚拟内存区域，就是我们所熟知的堆。不同系统之间的细节有所不同，但是大体上是差不多的。假设堆是一个请求二进制零（私有的）的区域，它紧接着未初始化的数据区域之后开始，并向更高的地址生长，对于每一个进程，内核维护着一个变量brk，它指向堆的顶部。分配器将堆视为一组不同大小的块的集合来维护。每个块就是一个连续的虚拟内存片。要么是已分配的，要么是空闲的，已分配的块显示的保留为供应用程序使用，空闲块可以用来分配，一个已分配的块会保持已分配状态，直到它被释放，这种释放要么是程序显示执行的，要么是分配器隐式执行的，分配器可以分为显示分配器和隐式分配器。显示分配器要求显示的释放任何已经分配的块，比如C语言之中的malloc函数以及与之搭配的free函数。隐式分配器由分配器自动进行块释放，自动的释放已经不会再使用到的已分配的块的过程叫做垃圾收集，比如Java就是依赖垃圾收集技术来释放已分配的块。Intel将4字节对象称为双子。但是在以下的示例中我们都假设字是4字节的对象，而双子是8字节的对象。下图展示了malloc函数以及free函数是怎么分配块以及释放块的。
   
   malloc函数在分配块的时候是需要进行对齐的，我们这里的对齐要求是满足双字边界对齐的（图中的一个块是4个字节，也就是一个字）。当调用free函数的时候，就会将相应的指针指向的已分配块释放掉。在释放之后相应的指针仍然会指向已经被释放了的块，所以在C语言之中需要保证在相应的指针被再次赋值之前不会被使用。

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

1. 使用动态内存分配最重要的原因是经常会发生直到程序实际运行的时候才会知道某些数据结构的大小，比如一个数组，它的大小取决于用户的输入，在用户输入之前，也即在程序运行之前我们是无法得知该数组到底会是多大的，所以说选择动态内存分配是很合理的。同时使用动态内存分配也增加了程序的可移植性。

2. 同时分配器还需要在以下的约束条件下进行工作：

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

   在以上的约束下分配器会尽可能的得到最大化的吞吐率以及最大化的内存利用率。最大化吞吐率和最大化内存利用率是相互制约的，设计分配器的程序员所面临的一个巨大的挑战就是在以上的两个指标之间找到一个适当的平衡。

3. 内存碎片

1. 造成堆利用率很低的主要原因是一种称作碎片的现象，也就是堆中还有足够的未使用的内存但是却不能够用来满足分配的请求的一种现象。碎片的形式有两种，一种是内部碎片，一种是外部碎片。内部碎片是在一个已经分配块比实际的有效载荷大时发生的。很多原因会造成这种问题，比如说图9-34中(b)的情形，分配器增加了块的大小来满足对齐要求。对块增加的这一个字（4字节）的大小就是这个块的内部碎片，块的有效载荷就是除去增加的这一个字之后的大小。对内存中的内部碎片的大小进行统计是比较简单的。即所有的已分配块大小和它们的有效载荷大小之差的和。所以内存碎片的数量只取决于之前请求的模式以及分配器的实现方式。
2. 外部碎片是当空闲内存合计起来足够满足一个分配请求时，却没有任意的一个单独的空闲块足够大，以至于最终并不能满足分配请求。如果在9-34(e)中的请求要求是6个字，而不是2个字；那么即使在其中有6个字的空闲空间但是仍不能够满足分配请求。外部碎片的量化是很困难的，因为其不仅取决于过去的请求模式以及分配器的实现方式，还取决于将来的请求模式。假设在k个请求之后，所有空闲块的大小恰好都是4个字。如果将来的所有请求都小于或者是等于4个字的块，那么就不会有外部碎片，但是如果有一个或者是多个请求要求比4个字大的块，那么这个堆就会有外部碎片。换句话说就是那些空闲的块未必就是外部碎片，需要看之后的请求序列决定。

4. 实现问题

1. 一种最简单的分配器会把堆组织成一个大的字节数组，还有一个指针p，初始时指向这个数组的第一个字节。为了分配size个字节，malloc将p的当前值保存在栈李，然后将p增加size，并将p的旧值返回到调用函数。而free只是简单地返回到调用函数，而不做其它的任何事情。这个简单的分配器中的malloc和free只执行很少量的指令，吞吐率会很好，但是分配器并不会重复使用任何的块，所以内存利用率非常的低。一个实际的分配器需要在吞吐率和利用率之间把握好平衡，并考虑好以下的几个问题：

   • 空闲块组织：分配器应该如何记录空闲块；
   • 放置：分配器该如何选择一个合适的空闲块来放置一个新分配的块；
   • 分割：在将一个新分配的块放置到某个空闲块之后，分配器将如何处理这个空闲块中的剩余部分；
   • 合并：分配器会如何处理一个刚刚被释放的块；

5. 隐式空闲链表

1. 任何实际的分配器都需要一些数据结构，用来区别块边界，以及块是已经分配的块还是空闲块。大多数分配器会将这些信息嵌入到块本身，一个简单的方法如下图所示：
   
   在上图所示的情况中，一个块是由一个字的（4字节）头部，有效载荷，以及可能的一些额外的填充所组成的。头部编码了整个块的大小，以及这个块是已分配的还是空闲的。如果分配器强制要求双字对齐的话，那么块大小就总是8字节的倍数，所以块的最低3位总是零。因此我们只需要内存大小的29个高位，而剩余的3位用来编码其它的信息。我们可以使用最低的3位中的最低位来指明这个块是已分配的还是空闲的。例如我们有一个已分配的块，它的大小是24（0x18）字节，那么这个块的头部将是 0x00000018 | 0x1 = 0x00000019；类似地，一个块大小为40（0x28）字节的空闲块会有如下的头部：0x00000028 | 0x0 = 0x00000028；头部后面的就是应用调用malloc是请求的有效载荷。有效载荷后面是不使用的填充，也就是内部碎片，内部碎片的大小可能是任意的。需要填充的原因有很多。填充可能是分配其策略中的一部分，填充虽说增加了些许的内部碎片，但是它可以对付外部碎片。除此之外，填充也可能是为了满足对齐的要求。

2. 假设我们使用的就是以上的方式，那么我们可以将堆组织为一个连续的已分配块和空闲块的序列，如下图所示：
   
   我们将上图所示的结构称作隐式空闲链表，因为空闲块是通过头部中的大小字段隐含地连接着的。分配器可以通过遍历堆中的所有块来间接地遍历整个空闲块的集合。我们需要某种特殊标记的结束块，在这个示例中就是设置一个已分配位但是大小为零的终止头部（terminating header）。来表示隐式空闲链表的结束。

3. 隐式空闲链表的优点就是很简单，但是一个显著的缺点就是任何操作的开销，例如放置分配的块，需要我们对空闲链表进行搜索以找出合适的空闲块，该搜索所需的时间与堆中已分配块和空闲块的总数呈线性关系。如果分配器有对齐要求以及分配器对格式的选择会对分配器上的最小块大小有强制的要求。比如当分配器要求每个块的大小必须是双字（8字节）对齐的时候，那么一个块最小的大小为两个字。

6. 放置已分配的块

1. 当一个应用请求一个 k 字节的块时，分配器会搜索空闲链表，查找一个足够大的可以放置所请求块的空闲块。分配器执行这种搜索以找到合适的空闲块的方式是由放置策略确定的。常见的放置策略有首次适配（first fit），下一次适配（next fit）和最佳适配（best fit）。
2. 首次适配算法会从头开始搜索空闲链表，选择第一个合适的空闲块，下一次适配不会每一次都从链表的起始处开始搜索，而是从上一次查询借书的地方开始搜索空闲块。最佳适配同样会检查每一个空闲块，但是会选择满足所需请求大小的最小的空闲块。
3. 首次适配的优点就是它趋于将大的空闲块保留在链表的后面，缺点就是它趋向于在链表的起始处留下较小的空闲块的碎片，这就增加了对较大空闲块的搜索所需要的时间。下一次适配认为如果我们上一次在某个空闲块中已经发现了一个匹配，那么很可能在下一次我们也能在这个剩余块中发现匹配。下一次适配比首次适配运行的速度明显要更快一些，尤其是当链表的前面布满了许多小的碎片的时候。然而一些研究表明下一次适配的内存利用率比首次适配的要低很多，同时最佳适配的内存利用率比另外的两者都要高一些。但是在诸如隐式空闲链表这种简单的空闲链表组织结构中，使用最佳适配需要对堆进行彻底的搜索。最佳适配更适合应用于更加精细复杂的分离式空闲链表组织，它不需要最佳适配算法进行彻底的堆搜索。

7. 分割空闲块

一旦分配器找到了一个匹配的空闲块，它就必须做出一个决定，那就是使用多少这个空闲块中的空间，一种选择是使用掉整个空闲块。虽然这种方式简单而快捷，但是主要的缺点就是会造成内部碎片；如果分配策略采用的是最佳适配，也就是会产生好的匹配，那么产生的内部碎片会比较小，也是可以接受的；但是如果产生的匹配并不是很好，那么分配器通常会选择将这个空闲块分割为两部分，第一部分作为分配块，而剩下的变成一个新的空闲块，如图（是基于之前的图9-36的）展示了一个分配器是如何进行分割的，它用来满足一个应用对堆内存的3个字（加上头部的话一共需要分配4个字）的请求。分配器会将8个字的空闲块中的前4个字作为分配块，而后面的4个字作为空闲块。

8. 获取额外的堆内存

如果分配器不能够为请求块找到合适的空闲块；那么分配器可以选择合并那些在内存中物理上相邻的空闲块来创建一个更大的空闲块，如果这么做还是没有足够大的可以满足要求的空闲块，或者空闲块已经最大程度地合并了，那么分配器就会调用sbrk函数，向内核申请额外的堆内存。分配器将额外的内存转化为一个大的空闲块，并将这个块插入到空闲链表中，然后将被请求的块放置在这个新的空闲块中。

9. 合并空闲块

当分配器释放一个已分配块时，可能有其它空闲块与这个空闲块相邻。这些邻接的空闲块可能会引起一种叫做假碎片的现象，就是有许多可用的空闲块被切割成小的，无法使用的空闲块，下图展示了释放以上的图9-37中分配的块之后得到的结果。如果不采取合适的措施的话，就会产生两个相邻的空闲块，每一个的有效载荷（也就是去掉头部之后）都是3个字。因此如果我们发起一个4字有效载荷的请求的话就会导致失败，即使这两个空闲块加起来的大小是满足分配要求的。

为了解决假碎片的问题，任何实际的分配器都会合并相邻的空闲块，这个过程称为合并，这就需要分配器决定何时执行合并操作。分配器可以选择立即合并，也就是在每一次块被释放的时候就立即合并所有相邻的块。分配器也可以选择推迟合并，也就是等到某个稍晚的时候再合并空闲块。例如分配器可以等到某个分配请求失败的时候再扫描整个堆，然后合并所有的空闲块。立即合并虽然简单明了，可以在常数时间内执行完成，但是对于某些请求模式，这种方式会产生一种形式的抖动，块会被反复地合并，然后马上又被分割，例如在以上提到的图9-38中，反复的分配和释放一个3字的块将产生大量不必要的分割和合并，也就产生了抖动的现象。在这里假设分配器会采用立即合并。但是快速的分配器通常会选择某种形式的推迟合并。

10. 带边界标记的合并

1. 我们称想要释放的块为当前块，那么合并内存中的下一个空闲块是很简单并且是很高效的。当前块的头部指向下一个块的头部，可以检查这一个指针以判断下一个块是不是空闲的。如果是，就将它的大小简单地加到当前块头部的大小上，这两个块会在常数时间内被合并。但是仅仅只有头部的的话或者是不另外添加一些信息的话不容易合并前面的空闲块的。给定一个带头部的隐式空闲链表，唯一的选择就是搜索整个链表，记住前面的块的位置，直到我们到达当前的块。使用隐式空闲链表意味着每次调用free需要的时间与堆的大小是呈线性关系的，即使使用更加复杂且精密的链表，搜索的事件也不会是常数级别的；

2. 我们可以使用一种叫做边界标记的技术来处理当前快之前的块，该技术允许我们在常数时间内进行对前面的块的合并。这种思想就是在每个块的结尾处添加一个脚部，那么分配器就可以通过检查它的脚部，判断前面一个块的其实位置和状态：
   
   当分配器要释放一个块的时候，会有以下的4中情况：

   • 前面的块和后面的块都是已分配的；
   • 前面的块是已分配的，后面的块是空闲的；
   • 前面的块是空闲的，而后面的块是已分配的；
   • 前面的块和后面的块都是空闲的；

   下图展示了分配器是如何处理以上的4中情况的：
   
   上图中头部a表示已分配，头部f表示表示空闲；在情况1中，两个邻接的块都是已分配的，因此不会进行合并，分配器仅仅会将当前块的状态从已分配变为空闲。在情况2之中，当前块与后面的块进行合并，然后分配器会将当前块的头部和后面块的脚部更新为当前块和后面块大小之和并将分配位由已分配更新为空闲。在情况3中，前面的块和当前的块合并。用两个块的大小的和来更新前面块的头部以及当前块的脚部，并将有效位更新为空闲；在情况4之中，用三个块的大小来更新前面块的头部和后面块的脚部，并将有效位更新为空闲。在以上的各种情况中，合并都是在常数的时间内完成的。

3. 边界标记的概念在许多不同类型的分配器和空闲链表组织结构中都是通用的。然而它在某些情况下也非常的浪费空间，它总是要求每个块都保持一个头部和一个脚部，在应用程序操作许多个小块的时候会产生显著的内存开销。比如一个图形应用通过反复调用malloc和free来动态的创建和销毁图形节点，并且每一个图形节点都只要求两个内存字，那么头部和脚部将占用每个分配块的一半的空间；

4. 当我们试图在内存中合并当前块以及前面的块和后面的块时，只有在前面的块是空闲时，才会需要用到它的脚部。如果我们将前面块的已分配/空闲位存放在当前块中多出来的低位中，那么已分配的块就不需要脚部了，这样我们就可以将这个多出来的空间用作有效载荷了。不过空闲块仍然需要脚部。

11. 显式空闲链表

1. 隐式空闲链表会因为块分配与堆块的总数呈线性关系，所以对于通用的分配器，是不适合采用隐式空闲链表的，虽说对于堆块数量预先就可以知道是很小的特殊分配器采用隐式空闲链表是很合适的；

2. 一种更好的方法是将空闲块组织为某种形式的显示数据结构，因为根据定义程序是不需要一个空闲块中的主体的，所以实现这个数据结构的指针可以存放在这些空闲块的主体里。例如可以将堆组织成一个双向空闲链表，在每一个空闲块之中都包含一个pred前驱指针和一个succ后继指针，如下图所示：
   
   使用双向链表而不是隐式空闲链表使得首次适配的时间从总块数的线性时间减少到了空闲块数的线性时间。释放一个块的时间可能是线性的也可能是一个常数，取决于分配器所选择的空闲链表中块的排序策略；

3. 一种方式是用后进先出（LIFO）的顺序维护链表，将新分配的块放置在链表的开始处。同时使用LIFO和首次适配的策略，分配器会最先检查最近使用过的块。在这种情况下释放一个块可以在常数时间内完成。如果也使用了边界标记的话，那么合并也可以在常数的时间内完成。

4. 另一种方式是按照地址顺序来维护链表，其中链表中的每个块的地址都小于它后继的地址。在这种情况下释放一个块需要线性时间的搜索来定位合适的前驱。但是这种方式会比LOFO排序的首次适配有更高的内存利用率，接近最佳适配的利用率；显式链表的缺点就是空闲块必须足够大，以包含所有需要的指针，以及头部和可能的脚部。这就导致了最小块的大小会更大，也提高了内存碎片的程度。

12. 分离的空闲链表

1. 一个使用单向空闲链表的分配器分配块时所需要的时间是与空闲块的数量呈线性关系的。一种比较常用的减少分配时间的方法被称作分离存储。该方法会维护多个空闲链表，其中每个链表中的块有大致相等的大小。一般的思路是将所有可能的块大小分成一些等价类，这些等价类也叫作大小类。有很多种方式来定义大小类。比如我们可以根据2的幂来划分块大小：{1}, {2}, {3, 4}, {5 ~ 8} , … , {1025 ~ 2048} , {2049 ~ 4096} … 或者我们可以将小的块分配到它们自己的大小类里，而将大块按照 2 的幂分类：{1}, {2}, {3}, … , {1023}, {1024}, {1025 ~ 2048}, {2049 ~ 4096} … ；
2. 分配器维护着一个空闲链表的数组，每个大小类一个空闲链表，并按照大小的圣墟排列。当分配器需要一个大小为n的块时，他就会搜索相应的空闲链表，如果找不到合适的块与之匹配，它就会继续搜索下一个链表，以此类推。分离存储方法有很多，两种基本的方法就是简单分离存储和分离适配。
3. 简单分离存储：使用简单分离存储的话每个大小类的空闲链表包含大小相等的块，每个块的大小就是这个大小类中最大元素的大小。例如如果某个大小类定义为 {17 ~ 32}，那么这个大小类的空闲链表全由大小为32的块组成。为了分配一个给定大小的块，程序会检查相应的空闲链表。如果链表是非空的，那么就简单地分配其中的第一块的全部，相应的空闲块并不会进行分割。如果链表是空的话，分配器就像操作系统请求一个固定大小的额外内存片，大小通常是页大小的整数倍，然后将这个片分成大小相等的块，并将这些块链接起来形成一个新的空闲链表。要释放一个块的时候，分配器只需要将要释放的块插入到相应的空闲链表的前部即可；
4. 这种简单的方法有很多的优点，分配和释放都是在常数级别的时间内完成的，同时每个片中都是大小相等的块，既不进行分割也不进行合并，正因为没有合并，所以已分配块的头部就不需要一个已分配/空闲标记。同时大小都是事先确定的，所以也不需要头部中表示大小的字段，所以分配块不需要头部，同时也不需要脚部。因为分配和释放都是在空闲链表的起始处操作的，所以链表只需要是单向的，不需要是双向的。所以任何块中都只需要唯一的字段就是每个空闲块中一个字的succ后继指针，所以最小块大小就是一个字。意味着每个块只有很少的内存开销。同时因为每个块的大小都是一样的，所以一个已分配块的大小就可以从它的地址中推断出来。该方法一个显著的缺点就是很容易造成内部碎片以外部碎片。因为空闲块是不会进行分割的，所以可能会造成内部碎片。同时因为不会合并空闲块，所以某些引用模式会引起极大的外部碎片。
5. 分离适配：使用这种方法，分配器维护着一个空闲链表的数组。每个空闲链表和一个大小类相关联，并且被组织成某种隐式或显式链表。每个链表中包含有很多的块，这些块的大小对应于大小类中块的大小。有许多种不同的分离适配分配器，在这里介绍一种比价简单的实现方式；为了分配一个块，必须确定请求所属于的大小类，然后找到相应的空闲链表，之后进行首次适配，查找一个合适的块。如果找到了满足的块，那么就可选择的分割它，并将剩余的部分插入到适当的空闲链表中。如果找不到合适的块，那么就继续搜索下一个更大的大小类的空闲链表。直到查找到一个合适的块。如果在空闲链表中没有合适的块，那么就向操作系统请求额外的堆内存，从这个新的堆内存中分配出一个块，将剩余部分放置在适当的大小类中。如果要释放一个块，分配器会执行合并，并将结果放置到相应的空闲链表中。
6. 分离适配方法是一种常见的选择，C标准库中提供的GNU malloc包采用的就是这种方式。因为这种方法既快速，对内存的使用也很有效率。搜索时间减少了，因为搜索被限制在堆的某个部分，而不是整个堆。内存利用率也得到了改善，对分离空闲链表的简单的首次适配搜索，其内存利用率近似于对整个堆的最佳适配搜索的内存利用率。
7. 伙伴系统：伙伴系统是分离适配的一种特例，每一个大小类都是2的幂。基本思路是假设一个堆的大小为2^m个字，分配器会为每一个大小为 2^k的块维护一个分离空闲链表。如果请求块的大小不是2的幂的话，请求块的大小就会被向上取为最接近的2的幂。在最开始时只有一个大小为 2^m 个字的空闲块。为了分配一个大小为 2^k 的块，分配器会找到第一个可用的，大小为 2^j 的块，其中 k <= j <= m，如果 j = k，那么我们就完成了对块的分配，否则的话会递归地对这个块进行二分切割，直到 j = k。当我们进行这样的分割时，每个剩下的半块（也叫做伙伴）被放置在相应的空闲链表中。要释放一个大小为 2^k 的块，分配器就会持续地合并空闲的伙伴，直到遇到一个已分配的伙伴。当给定一个块的地址和大小的时候，可以很容易的计算出它的伙伴的地址，例如一个大小为32字节，地址为xxx…xx00000的块，它的伙伴的地址为xxx…x10000，也就是一个块的地址和它的伙伴的地址只有一位是不同的。伙伴系统分配器的优点是它可以快速地执行搜索和合并操作。主要的缺点就是它要求块的大小必须是2的幂，这样就会导致有很多的内部碎片，所以通用的分配器并不会采用这样的方式。但是对于特定的分配器，比如可以预先知道块大小是2的幂，那么就可以采用伙伴系统。

13. 垃圾收集

1. 在诸如C语言中的malloc包这样的显示分配器中，应用通过调用malloc和free来分配和释放块，应用要负责释放所有已经不再需要使用的块；未释放已分配的块是一种常见的编程错误，例如以下的C程序：
   
   因为程序不再需要p，所以在函数返回之前应该释放p，但是如果在编写代码的时候忘记了释放p，那么它在程序的生命周期之内都会保持为已分配状态，不必要的占用着本来可以用来满足后面的分配请求所需的空间。

2. 垃圾收集器可以自动释放程序不再需要的已分配块。在一个支持垃圾收集的系统中，应用显式分配堆块，但是从来不会显式地释放它们。

3. 垃圾收集器将内存视为一张有向可达图，其形式如下图所示：
   
   图中的节点被分成一组根节点和一组堆节点，每个堆节点对应于堆中的一个已分配块。有向边 p->q 意味着块 p 中的某个位置指向块 q 中的某个位置，根节点是不存在于堆之中的，它们包含指向堆中的指针。这些位置可以是寄存器中的变量，也可以是栈里面的变量，或者是虚拟内存中读写数据区域内的全局变量。

4. 当存在一条从任意根节点发出并到达 p 的有向路径时，我们说点 p 是可达的。在任何时刻，不可达的节点都会被当作垃圾，不能够被应用再次使用，垃圾收集器就可以回收掉那些不可达的节点。垃圾收集器会维护有向图的表示，并通过释放不可达的节点并将它们返回给空闲链表来定期的回收它们。

5. 垃圾收集器之中有的会采用Mark Sweep算法，该算法由标记（mark）和清除（sweep）阶段组成，标记阶段标记出根节点的所有可达的和已分配的后继，而后面的清除阶段会清除掉每一个未被标记的节点。块头部中空闲的低位中会有一位通常用来表示这个块是否被标记了。实现该算法的相应的函数如下图所示：
   
   标记阶段为每一个根节点调用一次下图中的mark函数，如果 p 并不指向一个已分配并且未标记的堆块，mark函数就立即返回，否则它就会标记这个块，并对块中的每个字进行递归调用。每次对mark函数的调用都标记某个根节点的所有未标记并且可达的后继节点。sweep函数在堆中每个块上反复循环，释放掉它所遇到的所有未标记的已分配块：
   
   下图中第3块中包含一个指向第1块的指针；第4块指向第3块和第6块，跟指针指向第4块，经过标记阶段之后，1, 3, 4, 6 就都被标记了，2, 5未被标记，从而会被回收到空闲链表中：