第九章 虚拟存储器

• 为了更加有效地管理存储器并且少出错，现代系统提供了一种对主存的抽象概念，叫做虚拟存储器（VM）。虚拟存储器是硬件异常、硬件地址翻译、主 存、磁盘文件和内核软件的完美交互，它为每个进程提供了一个大的、一致的和私有的地址空间。通过一个很清晰的机制，虚拟存储器提供了三个重要的能力：
  1）它将主存看成是一个存储在磁盘上的地址空间同，主存中只保存活动区域，并根据需要在磁盘和主存之间来回传送数据，通过这种方式，它高效地使用了主存。
  2）它为每个进程提供了一致的地址空间，从而简化了存储器管理。
  3）它保护了每个进程的地址空间不被其他进程破坏。

9.1 物理和虚拟寻址535

• 当CPU执行这条加载指令时，它会生成一个有效物理地址，通过存储器总线，把它传递给主存。主存取出从物理地址4处开始的4字节的字，并将它返回 给CPU，CPU会将它存放在一个寄存器里。早期的PC使用物理寻址，而且诸如数字信号处理器、嵌入式微控制器以及Cray超级计算机这样的系统仍然继续 使用这种寻址方式。然而，现代处理器使用的是一种称为虚拟寻址的寻址形式，参见图：
  

9.2 地址空间535

• 地址空间是一个非负整数地址的有序集合。
• 一个地址空间的大小是由表示最大地址所需要的位数来描述的，例如一个包含N＝2的n次方个地址的虚拟地址空间就叫做一个n位地址空间。现代系统典型地支持32位或者64位虚拟地址空间，一个系统还有一个物理地址空间，它与系统中物理存储器的M个字节相对应。

9.3 虚拟存储器作为缓存的工具536

• 概念上而言，虚拟存储器被组织为一个由存放在磁盘上的N个连续的字节大小的单元组成的数组。每字节都有一个唯一的虚拟地址，这个唯一的虚拟地址是 作为到数组的索引的。磁盘上数组的内容被缓存在主存中。和存储器层次结构中其他缓存一样，磁盘（较低层）上的数据被分割成块，这些块作为磁盘和主存（较高 层）之间的传输单元。VM系统通过将虚拟存储器分割为称为虚拟页的大小固定的块来处理这个问题。每个虚拟页的大小为P=2的p次方字节。类似地，物理存储 器被分割为物理页大小也为P字节（物理页也称为页帧。

• 在任意时刻，虚拟页面的集合都分为三个不相交的子集

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

9.3.1 dram缓存的组织结构537

• 为了有助于清晰地理解存储 中不同的缓存概念，我们将使用术语SRAM缓存来表示位于CPU和主存之间的L1、L2和L3高速缓存，并且用术语DRAM缓存来表示虚拟存储器系统的缓存，它在主存中缓存虚拟页。
• 在存储层次结构中，DRAM缓存的位置对它的组织结构有很大的影响。回想一下SRAM比DRAM要快大约10倍，而DRAM要比磁盘快大约 100000多倍。因此，DRAM缓存中的不命中比起SRAM缓存中的不命中要昂贵得多，因为DRAM缓存不命中要由磁盘来服务，而SRAM缓存不命中通 常是由基于DRAM的主存来服务的。而且，从磁盘的一个扇区读取第一字节的时间开销要比从这个扇区中读连续的字节慢大约100000倍。归根到 底，DRAM缓存的组织结构完全是由巨大的不命中开销驱动的。
• 因为大的不命中处罚和访问第一字节的开销，虚拟页往往很大，典型地是4KB～2MB。由于大的不命中处罚，DRAM缓存是全相联的，也就是说，任 何虚拟页都可以放置在任何的物理页中。不命中时的替换策略也很重要，因为替换错了虚拟页的处罚也非常之高。因此，与硬件对SRAM缓存相比,操作系统对 DRAM缓存使用了更复杂精密的替换算法。最后，因为对磁盘的访问时间很长，DRAM缓存总是使用写回，而不是直写。

9.3.2 页表537

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

9.3.3 页命中538

9.3.4 缺页538

• 在虚拟存储器的习惯说法中，DRAM缓存不命中称为缺页。
• 缺页异常调用内核中的缺页异常处理程序，该程序会选择一个牺牲页，在此例中就是存放在PP3中的VP4。如果VP4已经被修改了，那么内核就会将它拷贝回磁盘。无论哪种情况，内核都会修改VP4的页表条目，反映出VP4不再缓存在主存中这一事实。
• 接下来，内核从磁盘拷贝VP3到存储器中的PP3，更新PTE3，随后返回。当异常处理程序返回时，它会重新启动导致缺页的指令，该指令会把导致 缺页的虚拟地址重发送到地址翻译硬件。但是现在，VP3已经缓存在主存中了，那么页命中也能由地址翻译硬件正翻译硬件正常处理了。图4展示了在缺页之后我 们的示例页表的状态：
  

9.3.5 分配页面539

• 下图展示了当操作系统分配一个新的虚拟存储器页时对我们示例页表的影响，例如调用malloc的结果。
  

9.3.6 又是局部性救了我们539

• 只要我们的程序有好的时间局部性，虚拟存储器系统就能工作得相当好。但是，当然不是所有的程序都能展现良好的时间局部性。如果工作集的大小超出了 物理存储器的大小，那么程序将产生一种不幸的状态，叫做颠簸这时页面将不断地换进换出。虽然虚拟存储器通常是有效的，但是如果一个程序性能慢得像爬一样， 那么聪明的程序员会考虑是不是发生了颠簸。

9.4 虚拟存储器作为存储器管理的工具540

• 按需页面调度和独立的虚拟地址空间的结合，对系统中存储器的使用和管理造成了深远的影响。特别地，VM简化了链接和加载、代码和数据共享，以及应用程序的存储器分配。
• 简化链接
• 简化加载
• 简化共享
• 简化存储器分配

9.5 虚拟存储器作为存储器保护的工具541

• 任何现代计算机系统必须为操作系统提供手段来控制对存储器系统的访问。不应该允许一个用户进程修改它的只读文本段。而且也不应该允许它读或修改任 何内核中的代码和数据结构。不应该允许它读或者写其他进程的私有存储器，并且不允许它修致任何与其他进程共享的虚拟页面，除非所有的共享者都显式地允许它 这么做（通过调用明确的进程间通信系统调用）。
• 就像我们所看到的，提供独立的地址空间使得分离不同进程的私有存储器变得容易。但是，地址翻译机制可以以一种自然的方式扩展到提供更好的访问控 制。因为每次CPU生成一个地址时，地址翻译硬件都会读一个PTE，所以通过在PTE上添加一些额外的许可位来控制对一个虚拟页面内容的访问十分简单。下 图展示了大致的思想。在这个示例中，每个PTE中已经添加了三个许可位。SUP位表示进程是否必须运行在内核超级用户）模式下才能访问该页。
  

9.6 地址翻译542

• 所有符号如下：
  

• 当页面命中时，CPU硬件执行的步骤

  第一步：处理器生成一个虚拟地址并把它传送给MMU
  第二步：MMU生成PTE地址，并从高速缓存／主存请求得到它
  第三步：高速缓存／主存向MMU返回PTE
  第四步：MMU构造物理地址并把它传送给高速缓存／主存
  第五步：高速缓存／主存返回所请求的数据字给处理器。
  页面命中完全是由硬件来处理的，与之不同的是，处理缺页要求硬件和操作系统内核协作完
  第一步到第三步：和图中的第一步到第三步相同；
  第四步：PTE中的有效位是零，所以MMU触发了一次异常，传递CPU中的控制到操作系统内核中的缺页异常处理程序。
  第五步：缺页处理程序确定出物理存储器中的牺牲页，如果这个页面已经被修改了，则把它换出到磁盘。
  第六步：缺页处理程序页面调入新的页面，并更新存储器中的PM。
  第七步：缺页处理程序返虚拟地址重新发送给MMU。因为虚拟页面现在缓回到原来的进程，再次执行导致缺页的指令。CPU将引起缺页的现在缓存在物理存储器中，所以就会命中，在MMU执行了图中的步骤之后，主存就会将所请求字返回给处理器。

9.6.1 结合高速缓存和虚拟存储器544

• 在任何既使用虚拟存储器又使用SRAM高速缓存的系统中，都存在应该使用虚拟地址还是使用讨论范围，但是大多数系统是选择物理寻址的。使用物理寻 址L多个进程同时在高速缓存中有存储块和共享来自相同虚拟页面的块成为很简单的事情。而且，高速缓存无需处理保护问题，因为访问权限的检查是地址翻译过程 的一部分。

9.6.2 利用tlb加速地址翻译545

• 正如我们看到的，每次CPU产生一个虚拟地址，MMU就必须查阅一个PTE，以便将虚拟地址翻译为物理地址。在最糟糕的情况下，这又会要求从存储 器取一次数据，代价是几十到几百个周期。如果PTE正碰巧缓存在L1中，那么开销就下降到1个或2个周期。然而，许多系统都试图消除这样的开销，它们在 MMU中包括了一个关于PTE的小的缓存，称为翻译后备缓冲器。
• TLB是一个小的、虚拟寻址的缓存，其中每一行都保存着一个由单个PTE组成的块。TLB通常有高度的相联性。如图所示，用于组选择和和行匹配的 索引和标记字段是从虚拟地址中的虚拟页号中提取出来的。如果TLB有T＝2的t次方个组，那么TLB索引（T田1）是由VPN的t个最低位组成的，而 TLB标记是由VPN中剩余的位组成的。

9.6.3 多级页表546

• 到目前为止，我们一直假设系统只用一个单独的页表来进行地址翻译。但是如果我们只有32位的地址空间、4KB的页面和一个4字节的PTE，那么即 使应用所引用的只是虚拟地址空间中的很小一部分，也总是需要—个4MB的页表驻留在存储器中。对于地址空间为64位的系统来说，问题将变得更复杂。

9.6.4 综合:端到端的地址翻译547

1. TLB是利用VPN的位进行虚拟寻址的。因为TLB有四个组，所以VPN的低两位就作为组索引（TLBI）。VPN中剩下的高6位作为标记（TLBT），用来区别可能映射到同一个TLB组的不同的VPN。
2. 页表。这个页表是一个单级设计，一共有256个页表条目（PTE）。然而，我们只对这些条目中的开头16个感兴趣。为了方便，我们用索引它的 VPN来标识每个PTE；但是要记住PPN都用一个破折号来表示，以加强一个概念：无论刚好这里存储的是什么位值，都是没有任何意义的。
3. 高速缓存。直接映射的缓存是通过物理地址中的字段来寻址的。

9.7 案例研究:intel core i7/linux存储器系统550

1. 处理器包包括四个核、一个大的所有核共享的L3高速缓存，以及一个DDR3存储器控制器。
2. 每个核包含一个层次结构的TLB、一个层次结构的数据和指令高速缓存，以及一组快速的点到点连接，这种连接是基于Intel QuickPath技术的，是为了让一个核与其他核和外部Ｉ／Ｏ桥直接通信。TLB是虚拟寻址的，是四路组相联的。L１、Ｌ２和Ｌ３高速缓存是物理寻址 的，其中，Ｌ１和Ｌ２是八路组相联的，Ｌ３是16路组相联的，块大小为64字节。页大小在启动时被配置为4KB或4MB。Ｌｉｎｕｘ使用的是4KB的页。

9.7.1 core i7地址翻译551

1. PTE有三个权限位，控制对页的访问。R／Ｗ位确定页的内容是可以读写的还是只读的。U／Ｓ位确定是否能够在用户模式中访问该页，从而保护操作系 统内核中的代码和数据不被用户程序访问。XD（禁止执行）位是在６４位系统中引入的，可以用来禁止从某些存储器页取指令。这是一个重要的新特性，通过限制 只能执行只读文本段，使得操作系统内核降低了缓冲区溢出攻击的风险。
2. 当MMU翻译每一个虚拟地址时，它还会更新另外外两个内核缺页处理程序会用到的位。每次访问一个页时，MMU都会设置A位，称为引用位。内核可以 用这个引用位来实现它的页替换算法。每次对一个页进行了写之后，MMU都会设置D位，又称脏位。脏位告诉内核在拷贝替换页之前是否必须写回牺牲页。内核可 以通过调用一条特殊的内核模式指令来清除引用位或脏位。

9.7.2 linux虚拟存储器系统554

1. 一个虚拟存储器系统要求硬件和内核软件之间的紧密协作。版本与版本之间细节都不尽同，对此完整的阐释超出了我们讨论的范围，但是，在这一小节中我 们的目标是对Linux的虚拟存储器系统做一个描述，使你能够大致了解一个实际的操作系统是如何组织虚拟存储器，以及如何处理缺页的。
2. 内核虚拟存储器包含内核中的代码和数据结构。内核虚拟存储器的某些区域被映射到所有进程共享的物理页面。例如，每个进程共享内核的代码和全局数据 结构。有趣的是，Linux也将一组连续的虚拟页面（大小等于系统中DRAM的总量）映射到相应的一组连续的物理页面。这就为内核提供了一种便利的方法来 访问物理存储器中任何特定的位置，例如，当它需要访问页表，或在一些设备上执行存储器映射的I/O操作，而这些设备被映射到特定的物理存储器位置时。
3. （1）Linux虚拟存储区域（2）Linux缺页异常处理

9.8 存储器映射556

Linux(以及其他一些形式的Unix)通过将一个虚拟存储器区域与一个磁盘上的对象(object)关联起来，以初始化这个虚拟存储器区域的内容，这个过程称为存储器映射(memory mapping)。虚拟存储器区域可以映射到两种类型的对象的一种：

(1)Unix文件上的普通文件：一个区域可以映射到一个普通磁盘文件的连续部分，例如一个可执行目标文件。文件区(section)被分成页大小 的片，每一片包含一个虚拟页面的初始化内容。因为按需进行页面高度，所以这些虚拟页面没有实际进行物理存储器，直到CPU第一次引用到页面(即发射一个虚 拟地址，落在地址空间这个页面的范围之内)。如果区域文件区要大，那么就用零来填充这个区域的余下部分。
(2)匿名文件：一个区域也可以映射到一个匿名文件，匿名文件是由内核创建的，包含的全是二进制零。CPU第一次引用这样一个区域内的虚拟页面时，内核就 在物理存储器中找到一个合适的牺牲页面，如果该页面被修改过，就将这个页面换出来，用二进制零覆盖牺牲页面并更新页表，将这个页面标记为是驻留在存储器中 的。注意在磁盘和存储器之间没有实际的数据传送。因为这个原因，映射到匿名文件的区域中的页面有时也叫做请求二进制零的页(demand-zero page)。
无论在哪种情况下，一旦一个虚拟页面被初始化了， 它就在一个由内核维护的专门的交换文件(swap file)之间换来换去。交换文件也叫做交换空间(swap space)或者交换区域(swap area)。需要意识到的很重要的一点，在任何时刻，交换空间都限制着当前运行着的进程能够分配的虚拟页面的总数。

9.8.1 再看共享对象557

1. 存储器映射的概念来源于一个聪明的发现：如果虚拟存储器系统可以集成到传统的文件系统中，那么就能提供一种简单而高效的把程序和数据加载到存储器中的方法。
2. 正如我们已经看到的进程这一抽象能够为每个进程提供自己私有的虚拟地址空间，可以免受其他进程的错误读写。不过，许多进程有同样的只读文本区域例 如，每个运行Unix外壳程序tcsh的进程都有相同的文本区域。而且，许多程序需要访问只读运行时库代码的相同拷贝。例如，每个C程序都需要来自标准c 库的诸如printf这样的函数。那么，如果每个进程都在物理存储器中保持这些常用代码的复制拷贝，那就是极端的浪费了。幸运的是，存储器映射给我们提供 了一种清晰的机制，用来控制多个进程如何共享对象。
3. 一个对象可以被映射到虚拟存储的一个区域，要么作为共享对象，要么作为私有对象。如果一个进程将一个共享对象映射到它的虚拟地址空间的一个区域 内，那么这个进程对这个区域的任何写操作，对于那些也把这个共享对象映射到它们虚拟存储器的其他进程而言也是可见的。而且，这此变化也会反映在磁盘上的原 始对象中。(IPC的一种方式)
   另一方面，对一个映射到私有对象的区域做的改变，对于其他进程来说是不可见的，并且进程对这个区域所做的任何写操作都不会反映在磁盘上的对象中。一个映射到共享对象的虚拟存储器区域叫做共享区域。类似地，也有私有区域。
4. 共享对象的关键点在于即使对象被映射到了多个共享区域，物理存储器也只需要存放共享对象的一个拷贝。
5. 一个共享对象(注意，物理页面不一定是连续的。)
6. 私有对象是使用一种叫做写时拷贝(copy-on-write)的巧妙技术被映射到虚拟存储器中的。对于每个映射私有对象的进程，相应私有区域的页表条目都被标记为只读，并且区域结构被标记为私有的写时拷贝。

9.8.2 再看fork函数558

1. 当fork函数被当前进程调用时，内核为新进程创建各种数据结构，并分配给它一个唯一的PID。为了给这个新进程创建虚拟存储器，它创建了当前进 程的mm_struct、区域结构和页表的原样拷贝。它将两个进程中的每个页面都为标记只读，并将两个进程中的每个区域结构都标记为私有的写时拷贝。
2. 当fork在新进程中返回时，新进程现在的虚拟存储器刚好和调用fork时存在的虚拟存储器相同。当这两个进程中的任一个后来进行写操作时，写时拷贝机制就会创建新页面，因此，也就为每个进程保持了私有地址空间的抽象概念。

9.8.3 再看execve函数559

假设运行在当前进程中的程序执行了如下的调用：

execve("a.out",NULL,NULL) ;

execve函数在当前进程中加载并运行包含在可执行目标文件a.out中的程序，用a.out程序有效地替代了当前程序。加载并运行a.out需要以下几个步骤：

删除已存在的用户区域。删除当前进程虚拟地址用户部分中的已存在的区域结构。
映射私有区域。为新程序的文本、数据、bss和栈区域创建新的区域结构。所有这些新的区域都是私有的、写时拷贝的。文本和数据区域被映射为a.out文件 中的文本和数据区。bss区域是请求二进制零的，映射到匿名文件，其大小包含在a.out中。栈和堆区域也是请求二进制零的。
映射共享区域。如果a.out程序与共享对象(或目标)链接，比如标准C库libc.so，那么这些对象都是动态链接到这个程序的，然后再映射到用户虚拟地址空间中的共享区域内。
设置程序计数器(PC)。execve做的最后一件事情就是设置当前进程上下文中的程序计数器，使之指向文本区域的入口点。

下一次调度这个进程时，它将从这个入口点开始执行。Linux将根据需要换入代码和数据页面。

9.8.4 使用mmap函数的用户级存储器映射559

参数含义：
start：这个区域从start开始
fd：文件描述符
length：连续的对象片大小
offset：距文件开始处的偏移量
prot：访问权限位，具体如下：
PROT_EXEC:由可以被CPU执行的指令组成
PROT_READ:可读
PROT_WRITE:可写
PROT_NONE:不能被访问
flag：由描述被映射对象类型的位组成，具体如下：
MAP_ANON:匿名对象，虚拟页面是二进制0
MAP_PRIVATE:私有的、写时拷贝的对象
MAP_SHARED：共享对象

mmap函数要求内核创建一个新的虚拟存储器区域是，最好是从地址start开始的一个区域，并将文件描述符fd指定的对象的一个连续的片 (chunk)映射到这个新区域。连续的对象片大小为length字节，从距文件开始处偏移量为offset字节的地方开始。start地址仅仅是一个暗 示，通常被定义为NULL。

9.9 动态存储器分配561

1. 动态存储器分配器维护着一个进程的虚拟存储器区域，称为堆。
2. 存储器分配器有两种：显示分配器，隐式分配器。

9.9.1 malloc和free函数561

1. 显示分配器包括：malloc和free，这两个函数就是两个分配器，只是职能不同。
2. 隐式分配器，也叫垃圾收集器，看来只有垃圾收集的功能。没有相应的分配功能。
3. malloc返回一个指针，指向大小为至少size字节的存储块。遇到问题的话，就返回NULL。
4. sbrk扩展和收缩堆。
5. freee参数必须为malloc，calloc，realloc返回的指针。其没有返回值。

9.9.2 为什么要使用动态存储器分配563

这里的存储器分配器，是对堆内部空间的分配和释放。和堆大小没有关系。
直到程序实际运行时，程序才知道某些数据结构的大小。

9.9.3 分配器的要求和目标564

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

(1)处理任意请求序列
(2)立即响应请求
(3)只使用堆
(4)对齐块（对齐要求）——在大多数系统中，这意味着分配器返回的块是8字节边界对齐的。
不修改已分配的块——像压缩已分配块这样的技术是不允许被使用的（这里是指已分配的块，而不是堆，sbrk函数可以扩展和收缩堆）

分配器有两个目标：
(1)最大化的吞吐率——其实就是以最快的方式执行诸如malloc和free这样的函数；
(2)最大化存储器利用率——通常用峰值利用率来表示存储器利用率，这个值是有效载荷/堆大小。

这两个目标其实是相互抑制的。

9.9.4 碎片565

堆的碎片：内部碎片和外部碎片。

内部碎片——对齐约束条件和具体实现中有最小分配块的要求。
外部碎片——有很多空间块，但满足不了一个分配请求。

9.9.5 实现问题565

9.9.6 隐式空闲链表565

隐式空闲链表——空闲块通过头部的大小字段隐含地连接在一起。

9.9.7 放置已分配的块567

1. 当一个应用请求一个k字节的块时，分配器搜索空闲链表，查找一个足够大可以放置所请求块的空闲块，执行这种搜索的方式由放置策略确定。
2. 首次分配:从头开始搜索空闲链表
3. 下一次适配：从上一次查询结束的地方开始搜索
4. 最佳适配：检查每个空闲块，选择适合所请求大小的最小空闲块

9.9.8 分割空闲块567

9.9.9 获取额外的堆存储器567

9.9.10 合并空闲块568

为了解决假碎片问题，任何实际的分配器都必须合并相邻的空闲块，这个过程称为合并。这就出现了一个重要的策略决定，那就是何时执行合并。分配器可以 选择立即合并以选择推迟合并。也就是等到某个稍晚的时候再合并空闲块。例如，分配器可以推迟合并，直到某个分配请求失败，然后扫描整个堆，合并所有的空闲 块。立即合并很简单明了，可以在常数时间内执行完成，但是对于某些请求模式，这种方式会产生一种形式的抖动，块会反复地合并，然后马上分割。例如，在图 中，反复地分配和释放个3个字的块将产生大量不必要的分割和合并。在对分配器的讨论中，我们会假设使用立即合并，但是你应该了解，快速的分配器通常会选择 某种形式的推迟合并。

9.9.11 带边界标记的合并568

想要释放的块称为当前块。
考虑当分配器释放当前块时所有可能存在的情况：
1）前面的块和后面的块都是已分配的。
2）前面的块是已分配的，后面的块是空闲的
3）前面的块是空闲的，而后面的块是已分配的。
4）前面的和后面的块都是空闲的。

9.9.12 综合:实现一个简单的分配器570

构造一个分配器是一件富有挑战性的任务。设计空间很大，有多种块格式、空闲链表格式，以及放置、分割和合并策略可供选择。另一个挑战就是你经常被迫在类型系统的安全和熟悉的限定之外编程，依赖于容易出错的指针强制类型转换和指针运算，这些操作都属于典型的低层系统编程。

1. 一般分配器设计
2. 操作空闲链表的基本常数和宏
3. 创建初始空闲链表
4. 释放和合并块
5. 分配块

9.9.13 显式空闲链表576

使用双向链表而不是隐式空闲链表，使首次适配的分配时间从块总数的线性时间减少到了空所选择的闲块数量的线性时间。不过，释放一个块的时间可以是线线性的，也可能是个常数，这取决于我们所选择的空闲链表中块的排序策略。
一种方法是用后进先出的顺序维护链表，将新释放的块放置在链表的开始处。使用LIFO的顺序和首次适配的放置策略，分配器会最先检查最近使用过的块。在这种情况下，释放一个块可以在常数时间内完成。如果使用了边界标记，那么合并也可以在常数时间内完成；
另一种方法是按照地址顺序来维护链表，其中链表中每个块的地址都小于它后继的地址。在这种情况下，释放一个块需要线性时间的搜索来定位合适的前驱。平衡点 在于，按照地址排序的首次适配比LIFO排序的首次适配有更高的存储器利用率，接近最佳适配的利用率。一般而言，显式链表的缺点是空闲块必须足够大以包含 所有需要的指针，以及头部和可能的脚部。这就导致了更大的最小块大小，也潜在地提高了内部碎片的程度。

9.9.14 分离的空闲链表576

1. 简单分离存储
   每个大小类的空闲链表包含大小相等的块，每个块的大小就是这个大小类中最大元素的大小。
   优点：分配和释放块快
   缺点：容易造成碎片
2. 分离适配
   分配一个块：确定请求的大小类，对适当的空闲链表做首次适配，查找一个合适的块，找到一个之后，可选的分割它，并将剩余部分插入适当的空闲链表中，如果找 不到合适的块，就搜索下一个更大的大小类的空闲链表，直到找到一个合适的块，如果没有合适的块，就向操作系统请求额外的堆存储器，并从这个新的堆存储器中 分配出一个块，将剩余部分放置在适当的大小类中，释放块时，执行合并，并将结果放置在相应的空闲链表里。
3. 伙伴系统
   伙伴系统是分离适配的一种特例，每个大小类都是2的幂。
   优点：快速搜索和快速合并。
   缺点：内部碎片。

9.10 垃圾收集578

垃圾收集：采用何种方式来辨别垃圾呐，系统采用的是图的方式进行，将存储器视为一张有向图，每个节点是根节点或堆节点，节点表示的一个分配块，如果 在一个块中指向另一个块的某个位置，就连接，当存在一条从任意根节点出发并到达堆节点的有向路径时，视为可达，那些不可达的节点就是垃圾节点。再进行回收 时，有两个阶段，标记和回收，标记垃圾节点，清除。

9.10.1 垃圾收集器的基本知识579

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

9.10.2 mark&sweep垃圾收集器580

mark&sweep垃圾收集器由标记和清除阶段组成。

9.10.3 c程序的保守mark&sweep580

第一，C不会用任何类型信息来标记存储器位置。因此，对isPtr没有一种明显的方式来判断它的输入参数p是不是一个指针。第二，即使我们知道p是一个指针，对isPtr也没有明显的方式来判断p是否指向一个已分配块的有效载荷中的某个位置。
对后一问题的解决方法是将已分配块集合维护成一棵平衡二叉树，这棵树保持着这样一个属性：左子树中的所有块都放在较小的地址处，而右子树中的所有块都放在 较大的地址处。如图所示，这就要求每个已分配块的头部里有两个附加字段（left和right）。每个字段指向某个已分配块的头部。

9.11 c程序中常见的与存储器有关的错误581

9.11.1 间接引用坏指针582

经典的scanf错误

在这种情况下，scanf将把val的内容解释为一个地址，并试图将一个字写到这个位置。在最好的情况下，程序立即以异常中止。在最糟糕的情况 下，val的内容对应于虚拟存储器的某合法的读／写区域，于是我们就覆盖了存储器，这通常会在相当长的段时间以后造成灾难性的、令人困惑的后果。

9.11.2 读未初始化的存储器582

一个常见的错误

9.11.3 允许栈缓冲区溢出582

使用fgets()纠正错误，这个函数限制了输入串的大小。

9.11.4 假设指针和它们指向的对象是相同大小的583

一种常见的错误是假设指向对象的指针和他们所指向的对象是大小相同的。

9.11.5 造成错位错误583

错位错误是一种很常见的覆盖错误来源。

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

9.11.7 误解指针运算584

另一种常见的错误是忘记了指针的算术操作是以它们指向的对象的大小为单位来进的，而这种大小单位并不一定是字节。

9.11.8 引用不存在的变量584

不理解栈的规则，有时会引用不再合法的本地变量。

9.11.9 引用空闲堆块中的数据584

一个相似的错误是引用已经被释放了的堆块中的数据。

9.11.10 引起存储器泄漏585

存储器泄露是缓慢隐形的杀手。

9.12 小结585

虚拟存储器是对主存的一个抽象。支持虚拟存储器的处理器通过使用一种叫做虚拟寻址的间接形式来引用主存。处理器产生一个虚拟地址，在被发送到主存之 前，这个地址被翻译成一个物理地址。从虚拟地址空间到物理地址空间的地址翻译要求硬件和软件紧密合作。专门的硬件通过使用页表来翻译虚拟地址，而页表的内 容是由操作系统提供的。

第十四周 第九章学习

原文：http://www.cnblogs.com/heiguirenxi/p/5043813.html