第 9 章

C H A P T E A 9 . .

虚拟内存

一个系统中的进程是与其他进程共享 CPU 和主存资源的。然而，共享主存会形成一些特殊的挑战。随着对 CPU 需求的增长，进程以某种合理的平滑方式慢了下来。但是如果太多的进程需要太多的内存，那么它们中的一些就根本无法运行。当一个程序没有空间可用时，那就是它运气不好了。内存还很容易被破坏。如果某个进程不小心写了另一个进程使用的内存，它就可能以某种完全和程序逻辑无关的令人迷惑的方式失败。

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

虚拟内存是计算机系统最重要的概念之一。它成功的一个主要原因就是因为它是沉默地、自动地工作的，不需要应用程序员的任何干涉。既然虚拟内存在幕后工作得如此之好，为什么程序员还需要理解它呢？有以下儿个原因：

虚拟内存是核心的。虚拟内存遍及计算机系统的所有层面，在硬件异常、汇编器、链接器、加载器、共享对象、文件和进程的设计中扮演着重要角色。理解虚拟内存将帮助你更好地理解系统通常是如何工作的。
. • 虚拟内存是强大的。虚拟内存给予应用程序强大的能力，可以创建和销毁内存片 ( ch unk ) 、将内存片映射到磁盘文件的某个部分，以及与其他进程共享内存。比如，你知道可以通过读写内存位置读或者修改一个磁盘文件的内容吗？或者可以加载一个文件的内容到内存中，而不需要进行任何显式地复制吗？理解虚拟内存将帮助你利用它的强大功能在应用程序中添加动力。
虚拟内存是危险的。每次应用程序引用一个变量、间接引用一个指针，或者调用一个诸如 ma l l oc 这样的动态分配程序时，它就会和虚拟内存发生交互。如果虚拟内存使用不当，应用将遇到复杂危险的与内存有关的错误。例如，一个带有错误指针的程序可以立即崩溃于＂段错误”或者“保护错误＂，它可能在崩溃之前还默默地运行了几个小时，或者是最令人惊慌地，运行完成却产生不正确的结果。理解虚拟内存以及诸如 ma l l oc 之类的管理虚拟内存的分配程序，可以帮助你避免这些错误。
这一章从两个角度来看虚拟内存。本章的前一部分描述虚拟内存是如何工作的。后一部分描述的是应用程序如何使用和管理虚拟内存。无可避免的事实是虚拟内存很复杂，本章很多地方都反映了这一点。好消息就是如果你掌握这些细节，你就能够手工模拟一个小系统的虚拟内存机制，而且虚拟内存的概念将永远不再神秘。
第二部分是建立在这种理解之上的，向你展示了如何在程序中使用和管理虚拟内存。你将学会如何通过显式的内存映射和对像 ma l l oc 程序这样的动态内存分配器的调用来管

理虚拟内存。你还将了解到 C 程序中的大多数常见的与内存有关的错误，并学会如何避免它们的出现。

9. 1 物理和虚拟寻址

计算机系统的主存被组织成一个由 M 个连续的字节大小的单元组成的数组。每字节

都有一个唯一的物理地址 ( Physical Address,

PA)。第一个字节的地址为 o, 接下来的字节地址为 1, 再下一个为 2’ 依此类推。给定这种简单的结构， CP U 访问内存的最自然的方式就是使用物理地址。我们把这种方式称为物理寻址 ( phys ic al add ress ing ) 。图 9-1 展示了一个物理寻址的示例，该示例的上下文是一条加载指令，它读取从物理地址 4 处开始的 4 字节字。当 CP U 执行这条加载指令时，会生成一个有效物理地址，通过内存总线，把它传递给主存。主存取出从物理地址 4 处开始的 4 字节字，并将它返回给 CP U , CP U 会将它存放在一个寄存器里。

主存

物理地址 2:

M-l:E3 #

数据字

图 9-1 一个使用物理寻址的系统

早期的 PC 使用物理寻址，而且诸如数字信号处理器、嵌入式微控制器以及 Cray 超级

计算机这样的系统仍然继续使用这种寻址方式。然而，现代处理器使用的是一种称为虚拟寻址( vir t ual address ing ) 的寻址形式，参见图 9-2。

CPU 芯片主存

;———————– – – ——————

！虚拟地址地址翻译！物理地址 I:

, - - - - _- - - _j_ - - - - - - - - - - - - - – - - - - - - - - – - - – - - - - _- - - j 5:

M-1:尸三

数据字

图 9- 2 一个使用虚拟寻址的系统

使用虚拟寻址， CP U 通过生成一个虚拟地址( Virt ual Address, VA ) 来访问主存，这个虚拟地址在被送到内存之前先转换成适当的物理地址。将一个虚拟地址转换为物理地址的任务叫做地址翻译 ( address t ra nslat io n ) 。就像异常处理一样，地址翻译需要 CPU 硬件和操作系统之间的紧密合作。CP U 芯片上叫做内存管理单元 ( Memory Managem ent Unit, MM U ) 的专用硬件，利用存放在主存中的查询表来动态翻译虚拟地址，该表的内容由操作系统管理。

9. 2 地址空间

地址空间 ( add ress s pace) 是一个非负整数地址的有序集合：

{0,1,2, ..,}

如果地址空间中的整数是连续的，那么我们说它是一个线性地址空间 ( linea r address

space) 。为了简化讨论，我们总是假设使用的是线性地址空间。在一个带虚拟内存的系统中， CPU 从一个有 N = 沪个地址的地址空间中生成虚拟地址，这个地址空间称为虚拟地

址空间 ( vir t ual address space) :

{0 , 1, 2 ,…, N — 1 }

一个地址空间的大小是由表示最大地址所需要的位数来描述的。例如，一个包含 N = 矿个地址的虚拟地址空间就叫做一个 n 位地址空间。现代系统通常支持 32 位或者 64 位虚拟地址空间。

一个系统还有一个物理地址空间 ( ph ys ic al address space), 对应于系统中物理内存的

M 个字节：

{0,1,2,… , M — 1 }

M 不要求是 2 的幕，但是为了简化讨论，我们假设 M = 2勹

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

让练习题 9. 1 完成下面的表格，填写缺失的条目，并且用适当的整数取代每个问号。利用下列单位： K= z10 ( 如lo , 千），M = 沪 ( m ega , 兆，百万），G = 230 (giga, 千兆，十亿）， T = 2气 t era , 万亿），P = 250 (peta, 于于兆），或 E = 260 (exa, 千兆兆）。

虚拟地址位数( n ) 虚拟地址数( N ) 最大可能的虚拟地址
8
21 = 64K
232— I =?G-1
2" = 256T
64

3 虚拟内存作为缓存的工具
概念上而言，虚拟内存被组织为一个由存放在磁盘上的 N 个连续的字节大小的单元组成的数组。每字节都有一个唯一的虚拟地址，作为到数组的索引。磁盘上数组的内容被缓存在主存中。和存储器层次结构中其他缓存一样，磁盘（较低层）上的数据被分割成块，这些块作为磁盘和主存（较高层）之间的传输单元。V M 系统通过将虚拟内存分割为称为虚拟页CV 江 t ua l Page, VP)的大小固定的块来处理这个问题。每个虚拟页的大小为 P = 沪字节。类似地，物理内存被分割为物理页 ( P h ysica l Page, PP), 大小也为 P 字节（物理页也被称为页帧 ( pag e fr am e) ) 。
在任意时刻，虚拟页面的集合都分为三个不相交的子集：
- 未分配的： V M 系统还未分配（或者创建）的页。未分配的块没有任何数据和它们相关联，因此也就不占用任何磁盘空间。

缓存的：当前已缓存在物理内存中的已分配页。
- 未缓存的：未缓存在物理内存中的已分配页。
  图 9-3 的示例展示了一个有 8 个虚拟页的小虚拟内存。虚拟页 0 和 3 还没有被分配，

因此在磁盘上还不存在。虚拟页 l 、4 和 6 被缓存在物理内存中。页 2、5 和 7 已经被分配了，但是当前并未缓存在主存中。

VPO VP I

虚拟内存物理内存

pp 0

pp I

VP 2•-p - 11 不农仔口 ‘J IN- I

虚拟页 ( VP ) 物理页 ( pp )

PP 2m-p - I

存储在磁盘上缓存在DRAM 中

图 9分一个 VM 系统是如何使用主存作为缓存的

9. 3. 1 DRAM 缓存的组织结构

为了有助于清晰理解存储层次结构中不同的缓存概念，我们将使用术语 SRAM 缓存来表示位于 CPU 和主存之间的 L1、L2 和 L3 高速缓存，并且用术语 DR AM 缓存来表示虚拟内存系统的缓存，它在主存中缓存虚拟页。

在存储层次结构中， DRAM 缓存的位置对它的组织结构有很大的影响。回想一下， DR AM 比 SRAM 要慢大约 10 倍，而磁盘要比 DRAM 慢大约 100 000 多倍。因此， DR AM 缓存中的不命中比起 SR AM 缓存中的不命中要昂贵得多，这是因为 DRA M 缓存不命中要由磁盘来服务，而 S RAM 缓存不命中通常是由基于 DR AM 的主存来服务的。而且，从磁盘的一个扇区读取第一个字节的时间开销比起读这个扇区中连续的字节要慢大约

100 000 倍。归根到底， D RAM 缓存的组织结构完全是由巨大的不命中开销驱动的。

因为大的不命中处罚和访问第一个字节的开销，虚拟页往往很大，通常是 4KB ~ 2M B。由于大的不命中处罚， DR AM 缓存是全相联的，即任何虚拟页都可以放置在任何的物理页中。不命中时的替换策略也很重要，因为替换错了虚拟页的处罚也非常之高。因此，与硬件对 S RA M 缓存相比，操作系统对 DR AM 缓存使用了更复杂精密的替换算法。

（这些替换算法超出了我们的讨论范围）。最后，因为对磁盘的访间时间很长， DRAM 缓存总是使用写回，而不是直写。

9. 3. 2 页表

同任何缓存一样，虚拟内存系统必须有某种方法来判定一个虚拟页是否缓存在D RAM 中的某个地方。如果是，系统还必须确定这个虚拟页存放在哪个物理页中。如果不命中，系统必须判断这个虚拟页存放在磁盘的哪个位置，在物理内存中选择一个牺牲页，并将虚拟页从磁盘复制到 DRA M 中，替换这个牺牲页。

这些功能是由软硬件联合提供的，包括操作系统软件、MMU ( 内存管理单元）中的地址翻译硬件和一个存放在物理内存中叫做页表( page ta ble ) 的数据结构，页表将虚拟页映射到物理页。每次地址翻译硬件将一个虚拟地址转换为物理地址时，都会读取页表。操作系统负责维护页表的内容，以及在磁盘与 DRAM 之间来回传送页。

图 9-4 展示了一个页表的基本组织结构。页表就是一个页表条目 ( P age Table Entry, PT E) 的数组。虚拟地址空间中的每个页在页表中一个固定偏移昼处都有一个 PT E。为了

我们的目的，我们将假设每个 PT E 是由一个有效位 C valid bit ) 和一个 n 位地址字段组成的。有效位表明了该虚拟页当前是否被物理内存

缓存在 DRA M 中。如果设置了有效位，物理页号或 ( D RAM )

有效位磁舟铀计」 VPI I PP O

那么地址字段就表示 D RAM 中相应的物理页的起始位置，这个物理页中缓存了该虚拟页。如果没有设置有效位，那么一个空地址表示这个虚拟页还未被分配。否则，这个地址就指向该虚拟页在

磁盘上的起始位置。

PTE O I 0

PTE71 I

常驻内存的页表＼、\

VP2 VP7

VP4

虚拟内存

（磁盘）

VP!

VP2

pp 3

图 9-4 中的示例展示了一个有 8 个

、、、、、、、谥

( DRAM) 、、、、、 I VP3

虚拟页和 4 个物理页的系统的页表。四

、、 I

VP4

个虚拟页 ( VP 1、 VP 2 、 VP 4 和 VP

7 ) 当前被缓存在 DRAM 中。两个页

、、、、、、

勹 VP6

VP7

(VP 0 和 VP 5) 还未被分配，而剩下的件I 9- I 页表

页 ( VP 3 和 VP 6) 已经被分配了，但是当前还未被缓存。图 9-4 中有一个要点要注意，因为 DRA M 缓存是全相联的，所以任意物理页都可以包含任意虚拟页。

心练习题 9. 2 确定下列虚拟地址大小( n ) 和页大小CP ) 的组合所需要的 PT E 数量：

n	P=2P	I	PTE 数量
16	4K
16	8K
32	4K
32	8K

9. 3. 3 页命中

考虑一下当 CPU 想要读包含在 VP 2 中的虚拟内存的一个字时会发生什么（图 9-5) , VP 2 被缓存在 DR AM 中。使用我们将在 9. 6 节中详细描述的一种技术，地址翻译硬件将虚拟地址作为一个索引来定位 PT E 2, 并从内存中读取它。因为设置了有效位，那么地址翻译硬件就知道 VP 2 是缓存在内存中的了。所以它使用 PT E 中的物理内存地址（该地址指向 p p 1 中缓存页的起始位置），构造出这个字的物理地址。

物理内存

(DRAM)

如 I PPO

VP2

立

妇 I PP 3

、、、、、

、、\

、、、

、、

常驻内存的页表、一、、、、、＼！

( D RAM ) 、、、、、[

、、、、、、、、

图 9 - 5 V M 页命中。对 V P 2 中一个字的引用就会命中

9. 3. 4 缺页

在虚拟内存的习惯说法中， D RAM 缓存不命中称为缺页 ( page fault ) 。图 9-6 展示了在缺页之前我们的示例页表的状态。 CP U 引用了 V P 3 中的一个字， V P 3 并未缓存在DR AM 中。地址翻译硬件从内存中读取 PT E 3, 从有效位推断出 VP 3 未被缓存，并且触发一个缺页异常。缺页异常调用内核中的缺页异常处理程序，该程序会选择一个牺牲页，在此例中就是存放在 p p 3 中的 VP 4。如果 VP 4 已经被修改了，那么内核就会将它复制回磁盘。无论哪种情况，内核都会修改 VP 4 的页表条目，反映出 VP 4 不再缓存在主存中这一事实。

厂有三 #

o I·-

PTE 7 I汇飞二、、

常驻内存的页表＼、、、＼＼、、

( DRAM ) 、、、、

物理内存

(DRAM)

VPI I PPO

义义

VP4 I PP 3

虚拟内存

（磁盘）

VPI VP2

VP3

、、、、、 I

、、、、I、

、、勹

VP4 VP6

VP7

图 9-6 V M 缺页（之前）。对 VP 3 中的字的引用会不命中，从而触发了缺页

接下来，内核从磁盘复制 V P 3 到内存中的 pp 3, 更新 PT E 3, 随后返回。当异常处理程序返回时，它会重新启动导致缺页的指令，该指令会把导致缺页的虚拟地址重发送到地址翻译硬件。但是现在， VP 3 已经缓存在主存中了，那么页命中也能由地址翻译硬件正常处理了。图 9-7 展示了在缺页之后我们的示例页表的状态。

物理内存

( DRAM )

VP I I PPO VP2

VP7

VP3 I PP 3

PTE 7 I I

、＼

、、、

、、、、、、、、、、

虚拟内存

（磁盘）

VP I

VP2

(DRAM) -,,、、、、、I、、、V、P、3 、、

、、、、、、—

VP4 VP6

VP7

图 9-7 VM 缺页（之后。）缺页处理程序选择 VP 4 作为牺牲页，并从磁盘上用 VP 3 的副本取代它。在缺页处理程序重新启动导致缺页的指令之后，该指令将从内存中正常地读取字，而不会再产生异常

虚拟内存是在 20 世纪 60 年代早期发明的，远在 CPU-内存之间差距的加大引发产生SRA M 缓存之前。因此，虚拟内存系统使用了和 S R A M 缓存不同的术语，即使它们的许多概念是相似的。在虚拟内存的习惯说法中，块被称为页。在磁盘和内存之间传送页的活动叫做交换 ( s wapping ) 或者页面调度( paging ) 。页从磁盘换入（或者页面调入）DR AM 和从 DRA M 换出（或者页面调出）磁盘。一直等待，直到最后时刻，也就是当有不命中发生时，才换入页面的这种策略称为按需页面调度( dem and paging ) 。也可以采用其他的方法，例如尝试着预测不命中，在页面实际被引用之前就换入页面。然而，所有现代系统都使用的是按需页面调度的方式。

9. 3. 5 分配页面

图 9-8展示了当操作系统分配一个新的虚拟内存页时对我们示例页表的影响，例如，调用 ma l l o c 的结果。在这个示例中， VP5 的分配过程是在磁盘上创建空间并更新 PT E 5, 使它指向磁盘上这个新创建的页面。

物理内存

(DRAM)

VP I IPP 0 PTE O I O I null –r J VP2

VP3IPP 3

虚拟内存

（磁盘）

PTE 7 I I ,, 、、、主、＼ VP!

常驻内存的页表＼、、、、、、、、、、、 I VP2

9. 3. 6 又是局部性救了我们

(DRAM)

\、、、、、、：’,,,,.[

VP3

VP4

当我们中的许多人都了解了虚拟内存的概念之后，我们的第一印象通常是它的效率应该是非常低。因为不命中处罚很大，我们担心页面调度会破坏程序性能。实际上，虚拟内存工

‘,,<、、、、、、、寸

VP5

VP6

舌 #

图 9-8 分配一个新的虚拟页面。内核在磁盘上分配 VP 5,

并且将 PTE 5 指向这个新的位置

作得相当好，这主要归功于我们的老朋友局部性(l ocalit y) 。

尽管在整个运行过程中程序引用的不同页面的总数可能超出物理内存总的大小，但是局部性原则保证了在任意时刻，程序将趋向千在一个较小的活动页面 (active page)集合上工作，这个集合叫做工作集 ( working set) 或者常驻集合( resident set) 。在初始开销，也就是将工作集页面调度到内存中之后，接下来对这个工作集的引用将导致命中，而不会产生额外的磁盘流量。

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

区且统计缺页次数

你可以利用 L m u x 的 ge tr u s a ge 函数监测缺页的数量（以及许多其他的信息）。

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

在上一节中，我们看到虚拟内存是如何提供一种机制，利用 DR A M 缓存来自通常更大的虚拟地址空间的页面。有趣的是，一些早期的系统，比如 DEC PDP-11 / 70 , 支持的是一个比物理内存更小的虚拟地址空间。然而，虚拟地址仍然是一个有用的机制，因为它

大大地简化了内存管理，并提供了一种自然的保护内存的方法。到目前为止，我们都假设有一个单

虚拟地址空间

物理内存

独的页表，将一个虚拟地址空间映射到

物理地址空间。实际上，操作系统为每个进程提供了一个独立的页表，因而也就是一个独立的虚拟地址空间。图 9- 9 展示了基本思想。在这个示例中，进程 l 的页表将 V P l 映射到 P P 2, VP 2 映射到 pp 7。相似地，进程）的页表将

进程i:

进程 j :

N-1

地址翻译

共享页面

VP 1 映射到 PP 7, VP 2 映射到 PP N - 1

M - 1

10 。注意，多个虚拟页面可以映射到同图 9-9 VM 如何为进程提供独立的地址空间。操作系统一个共享物理页面上。为系统中的每个进程都维护一个独立的页表

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

简化链接。独立的地址空间允许每个进程的内存映像使用相同的基本格式，而不管代码和数据实际存放在物理内存的何处。例如，像我们在图 8-13 中看到的，一个给定的 L in ux 系统上的每个进程都使用类似的内存格式。对于 64 位地址空间，代码段总是从虚拟地址 Ox 4 0 00 0 0 开始。数据段跟在代码段之后，中间有一段符合要求的对齐空白。栈占据用户进程地址空间最高的部分，并向下生长。这样的一致性极大地简化了链接器的设计和实现，允许链接器生成完全链接的可执行文件，这些可执行文件是独立于物理内存中代码和数据的最终位置的。
简化加栽。虚拟内存还使得容易向内存中加载可执行文件和共享对象文件。要把目标文件中 . t e x t 和 . da 七a 节加载到一个新创建的进程中， L in u x 加载器为代码和数据段分配虚拟页，把它们标记为无效的（即未被缓存的），将页表条目指向目标文件中适当的位置。有趣的是，加载器从不从磁盘到内存实际复制任何数据。在每个页初次被引用时，要么是 CP U 取指令时引用的，要么是一条正在执行的指令引用一个内存位置时引用的，虚拟内存系统会按照需要自动地调入数据页。
将一组连续的虚拟页映射到任意一个文件中的任意位置的表示法称作内存映射( mem ory m a pping ) 。Lin u x 提供一个称为 mma p 的系统调用，允许应用程序自己做内存映射。我们会在 9. 8 节中更详细地描述应用级内存映射。
简化共享。独立地址空间为操作系统提供了一个管理用户进程和操作系统自身之间共享的一致机制。一般而言，每个进程都有自己私有的代码、数据、堆以及栈区域，是不和其他进程共享的。在这种情况中，操作系统创建页表，将相应的虚拟页映射到不连续的物理页面。
然而，在一些情况中，还是需要进程来共享代码和数据。例如，每个进程必须询用相同的操作系统内核代码，而每个 C 程序都会调用 C 标准库中的程序，比如 pr i nt f 。操作系统通过将不同进程中适当的虚拟页面映射到相同的物理页面，从而安排多个进程共享这部分代码的一个副本，而不是在每个进程中都包括单独的内核和 C 标准库的副本，如图 9-9 所示。
简化内存分配。虚拟内存为向用户进程提供一个简单的分配额外内存的机制。当一个运行在用户进程中的程序要求额外的堆空间时（如调用 ma l l o c 的结果），操作系统分配一个适当数字（例如 k ) 个连续的虚拟内存页面，并且将它们映射到物理内存

中任意位置的 K 个任意的物理页面。由于页表工作的方式，操作系统没有必要分配

k 个连续的物理内存页面。页面可以随机地分散在物理内存中。

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

任何现代计算机系统必须为操作系统提供手段来控制对内存系统的访问。不应该允许一个用户进程修改它的只读代码段。而且也不应该允许它读或修改任何内核中的代码和数据结构。不应该允许它读或者写其他进程的私有内存，并且不允许它修改任何与其他进程共享的虚拟页面，除非所有的共享者都显式地允许它这么做（通过调用明确的进程间通信系统调用）。

就像我们所看到的，提供独立的地址空间使得区分不同进程的私有内存变得容易。但是，地址翻译机制可以以一种自然的方式扩展到提供更好的访问控制。因为每次 CP U 生成一个地址时，地址翻译硬件都会读一个 PT E , 所以通过在 PT E 上添加一些额外的许可位来控制对一个虚拟页面内容的访问十分简单。图 9-10 展示了大致的思想。

带许可位的页表

SUP READ WRITE 地址物理内存

I PPO

亡 pp 2

PP4

SUP READ WRITE 地址

./"

PP6

VPO: 进程}: VP I:	否是	是是	不口是	pp 9 pp 6	V I PP 9
VP 2:	不口	是	定曰	PP I I	恤 I PP 11 啊 I

图 9-10 用虚拟内存来提供页面级的内存保护

在这个示例中，每个 PT E 中已经添加了三个许可位。SUP 位表示进程是否必须运行在内核（超级用户）模式下才能访问该页。运行在内核模式中的进程可以访问任何页面，但是运行在用户模式中的进程只允许访问那些 SU P 为 0 的页面。READ 位和 WRIT E 位控制对页面的读和写访问。例如，如果进程 1 运行在用户模式下，那么它有读 VP 0 和读写VP 1 的权限。然而，不允许它访问 VP 2。

如果一条指令违反了这些许可条件，那么 CPU 就触发一个一般保护故障，将控制传递给一个内核中的异常处理程序。Linu x s hell 一般将这种异常报告为＂段错误( seg menta tion fault ) " 。

6 地址翻译
这一节讲述的是地址翻译的基础知识。我们的目标是让你了解硬件在支持虚拟内存中的角色，并给出足够多的细节使得你可以亲手演示一些具体的示例。不过，要记住我们省略了大量的细节，尤其是和时序相关的细节，虽然这些细节对硬件设计者来说是非常重要的，但是超出了我们讨论的范围。图 9-11 概括了我们在这节里将要使用的所有符号，供读者参考。

符	号	物理地址 ( PA) 的组成部分描述
PPO		物理页面偏移量（字节）
PPN co		物理页号缓冲块内的字节偏移鱼
CI		高速缓存索引
CT		高速缓存标记

图 9-11 地址翻译符号小结

形式上来说，地址翻译是一个 N 元素的虚拟地址空间( VAS ) 中的元素和一个 M 元素

的物理地址空间( PAS ) 中元素之间的映射，

MAP : VAS– PASU0

这里

A’ 如果虚拟地址 A 处的数据在 P AS 的物理地址 A’ 处

MAPCA) = { O 如果虚拟地址 A 处的数据不在物理内存中

图 9-12 展示了 MMU 如何利用页表来实现这种映射。CPU 中的一个控制寄存器，页表

基址寄存器( Page Table Base Register , PT BR)指向当前页表。n 位的虚拟地址包含两个部分：一个 p 位的虚拟页面偏移 ( Virt ual Page Offset, VPO) 和一个( n - p ) 位的虚拟页号 ( Virtu al

页表基址寄存器(PTBR)

n-1

虚拟页号( VPN )

虚拟地址

p p - 1 0

虚拟页偏移批< v o )

物理页号( PPN )

页表

如果有效位= 0,

那么页面就不在

存储器中（缺页） m- 1

物理页号 ( PPN )

P /- 1 i 。1

物理页偏移量( PPO )

物理地址图 9-12 使用页表的地址翻译

Page Numbe r , VPN) 。 MMU 利用 VPN 来选择适当的 PTE。例如， VPN 0 选择 PTE O , VPN 1 选择 PTE 1, 以此类推。将页表条目中物理页号 ( Physical Page Number, PPN) 和虚拟地址中的 VPO 串联起来，就得到相应的物理地址。注意，因为物理和虚拟页面都是 P 字节的，所以物理页面偏移( Physical Page Offset, PPO) 和 VPO 是相同的。

图 9-13a 展示了当页面命中时， CPU 硬件执行的步骤。

笫 l 步：处理器生成一个虚拟地址，并把它传送给 MMU 。
- 笫 2 步： MMU 生成 PT E 地址，并从高速缓存／主存请求得到它。
- 笫 3 步：高速缓存／主存向 MMU 返回 PT E。
- 笫 4 步： MMU 构造物理地址，并把它传送给高速缓存／主存。
  ．第 5 步：高速缓存／主存返回所请求的数据字给处理器。
  CPU芯片 CD
  : P’I’EA

a ) 页面命中

b ) 缺页

图 9-13

页面命中和缺页的操作图 ( VA, 虚拟地址。PT EA : 页表条目地址。

PTE: 页表条目。PA: 物理地址）

页面命中完全是由硬件来处理的，与之不同的是，处理缺页要求硬件和操作系统内核协作完成，如图 9-136 所示。

笫 l 步到笫 3 步：和图 9-13a 中的第 1 步到第 3 步相同。
- 笫 4 步： PT E 中的有效位是零，所以 MMU 触发了一次异常，传递 CPU 中的控制到操作系统内核中的缺页异常处理程序。
- 笫 5 步：缺页处理程序确定出物理内存中的牺牲页，如果这个页面已经被修改了，则把它换出到磁盘。
  ．第 6 步：缺页处理程序页面调入新的页面，并更新内存中的 PT E 。

．第 7 步：缺页处理程序返回到原来的进程，再次执行导致缺页的指令。CPU 将引起缺页的虚拟地址重新发送给 MMU。因为虚拟页面现在缓存在物理内存中，所以就会命中，在 MMU 执行了图 9-13b 中的步骤之后，主存就会将所请求字返回给处理器。

; 练习题 9. 3 给定一个 32 位的虚拟地址空间和一个 24 位的物理地址，对于下面的页面大小 P , 确定 VP N 、VPO、PPN 和 P PO 中的位数：

p	VPN位数	VPO位数	PPN位数	PPO位数
IKB
2KB
4KB
8KB

9. 6. 1 结合高速缓存和虚拟内存

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

图 9-14 展示了一个物理寻址的高速缓存如何和虚拟内存结合起来。主要的思路是地址翻译发生在高速缓存查找之前。注意，页表条目可以缓存，就像其他的数据字一样。

CPU 芯片 i——:–

PTE

不命中

PTEA

I 内存

PA I 数据

命中

高速缓存

图 9-1"1 将 V M 与物理寻址的高速缓存结合起来 ( V A , 虚拟地址。

PTEA, 页表条目地址。P T E , 页表条目。P A , 物理地址）

9. 6. 2 利用 TLB 加速地址翻译

正如我们看到的，每次 CP U 产生一个虚拟地址， MMU 就必须查阅一个 PT E , 以便将虚拟地址翻译为物理地址。在最糟糕的情况下，这会要求从内存多取一次数据，代价是几十到几百个周期。如果 PT E 碰巧缓存在 Ll 中，那么开销就下降到 1 个或 2 个周期。然而，许多系统都试图消除即使是这样的开销，它们在 MM U 中包括了一个关于 PT E 的小的缓存，称为翻译后备缓冲器 ( T ra ns la t io n Lookaside Buffer, TLB)。

TLB是一个小的、虚拟寻址的缓存，其 n- 1 p +t p+t- 1 p p-1 0

中每一行都保存着一个由单个 PTE 组成的块。 j TLB标记 (TLBT) I TLB索引 (TLBI) I VPO

‘y ,

T L B 通常有高度的相联度。如图 9-15 所示，

VPN

用于组选择和行匹配的索引和标记字段是从图 9- l5 虚拟地址中用以访问 TLB 的组成部分

虚拟地址中的虚拟页号中提取出来的。如果 TLB 有 T = 2’ 个组，那么 T LB 索引 ( T LBD是由

VPN 的 t 个最低位组成的，而 TLB 标记 (T LBT)是由 VPN 中剩余的位组成的。

图 9- l 6a 展示了当 T LB 命中时（通常情况）所包括的步骤。这里的关键点是，所有的地址翻译步骤都是在芯片上的 MMU 中执行的，因此非常快。

笫 1 步： CPU 产生一个虚拟地址。
笫 2 步和笫 3 步： MMU 从 T LB 中取出相应的 PT E。
．第 4 步： MMU 将这个虚拟地址翻译成一个物理地址，并且将它发送到高速缓存／主存。
笫 5 步：高速缓存／主存将所请求的数据字返回给 CPU 。
当 T LB 不命中时， MMU 必须从 L1 缓存中取出相应的 PT E , 如图 9-166 所示。新取出的 PT E 存放在 T LB 中，可能会覆盖— 个已经存在的条目。

CPU 芯片

—————————————-

iC–P–U–芯–片———————————

血 - - -

G) 数据

TLB命中

图 9-16 T LB 命中和不命中的操作图

＠ #

TLB不命中

9. 6. 3 多级页表

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

用来压缩页表的常用方法是使用层次结构的页表。用一个具体的示例是最容易理解这个思想的。假设 32 位虚拟地址空间被分为 4KB 的页，而每个页表条目都是 4 字节。还假设在这一时刻，虚拟地址空间有如下形式：内存的前 ZK 个页面分配给了代码和数据，接下来的 6K 个页面还未分配，再接下来的 1023 个页面也未分配，接下来的 1 个页面分配给了用户栈。图 9-17 展示了我们如何为这个虚拟地址空间构造一个两级的页表层次结构。

一级页表中的每个 PT E 负责映射虚拟地址空间中一个 4MB 的片( chunk ) , 这里每一片都是由 1024 个连续的页面组成的。比如， PT E 0 映射第一片， PT E 1 映射接下来的一片，以此类推。假设地址空间是 4GB, 1024 个 PT E 已经足够覆盖整个空间了。

如果片 1 中的每个页面都未被分配，那么一级 PTE i 就为空。例如，图 9-17 中，片 2~ 7 是未被分配的。然而，如果在片 1 中至少有一个页是分配了的，那么一级 PT E i 就指向一个二级页表的基址。例如，在图 9-17 中，片 0、1 和 8 的所有或者部分巳被分配，所以它们的一级 PTE 就指向二级页表。

一级页表二级页表虚拟内存

已分配的 2K 个代码和数据 VM 页

PTE 5 (null)

PTE 6 (null)

PTE 7 (null)

Gap I 6K 个未分配的 VM 页

(IK-9)

空PTE

1023 』

图 9- 17 一个两级页表层次结构。注意地址是从上往下增加的

二级页表中的每个 PT E 都负责映射一个 4KB 的虚拟内存页面，就像我们查看只有一级的页表一样。注意，使用 4 字节的 PT E , 每个一级和二级页表都是 4KB 字节，这刚好和一个页面的大小是一样的。

这种方法从两个方面减少了内存要求。第一，如果一级页表中的一个 PT E 是空的，那么相应的二级页表就根本不会存在。这代表着一种巨大的潜在节约，因为对于一个典型的程序， 4GB 的虚拟地址空间的大部分都会是未分配的。第二，只有一级页表才需要总是在主存中；虚拟内存系统可以在需要时创建、页面调入或调出二级页表，这就减少了主存的压力；只有最经常使用的二级页表才需要缓存在主存中。

图 9-18 描述了使用 K 级页表层次结构的地址翻译。虚拟地址被划分成为 K 个 VP N 和

1 个 VPO 。每个 VP N i 都是一个到第 z 级页表的索引，其中 1 ::::;;;i::::;;; k。第）级页表中的每个 PT E , 1::::;;;j 冬 k —1, 都指向第 j + l 级的某个页表的基址。第 k 级页表中的每个 PTE 包含某个物理页面的 PP N , 或者一个磁盘块的地址。为了构造物理地址，在能够确定 PPN 之前， MMU 必须访问 K 个 PT E。对于只有一级的页表结构， PPO 和 VPO 是相同的。

虚拟地址

n - 1

曰勹

m-1 p-q

PPN I PPO

物理地址

图 9- 18 使用 K 级页表的地址翻译

访问k 个 PT E , 第一眼看上去昂贵而不切实际。然而，这里 T LB 能够起作用，正是通过将不同层次上页表的 PT E 缓存起来。实际上，带多级页表的地址翻译并不比单级页表慢很多。

6. 4 综合：端到端的地址翻译
在这一节里，我们通过一个具体的端到端的地址翻译示例，来综合一下我们刚学过的这些内容，这个示例运行在有一个 T LB 和 Ll cl- cache 的小系统上。为了保证可管理性，我们做出如下假设：
- 内存是按字节寻址的。
- 内存访问是针对 1 字节的字的（不是4 字节的字）。
- 虚拟地址是 14 位长的( n = 14) 。
- 物理地址是 12 位长的( m = 1 2) 。
- 页面大小是 64 字节( P = 64) 。

T LB 是四路组相联的，总共有 16 个条目。
Ll cl- cache 是物理寻址、直接映射的，行大小为 4 字节，而总共有 16 个组。
图 9-19 展示了虚拟地址和物理地址的格式。因为每个页面是 26 = 64 字节，所以虚拟地址和物理地址的低 6 位分别作为 VPO 和 PPO 。虚拟地址的高 8 位作为 VP N。物理地址的高 6 位作为 PP N。
13 12 11 10 9 8 7 6 5 4 3 2 1 0
虚拟地址 I I I I I I I I I I I I I j

VPN

（虚拟页号）

VPO

（虚拟页偏移）

物理地址

11 . 10 . 9l

8 . 7 . 6 .

5 . 4 .

3 . 2 .

1 . 0

PPN

（物理页号）

PPO

（物理页偏移）

图 9-19 小内存系统的寻址。假设 14 位的虚拟地址 ( n = l 4 ) ,

1 2 位的物理地址 ( m = l 2 ) 和 64 字节的页面 CP = 64 )

图 9-20 展示了小内存系统的一个快照，包括 T LB C 图 9- ZOa ) 、页表的一部分（图9 - 206 ) 和 Ll 高速缓存（图9- ZOc) 。在 T LB 和高速缓存的图上面，我们还展示了访问这些设备时硬件是如何划分虚拟地址和物理地址的位的。

T LB。T LB 是利用 VP N 的位进行虚拟寻址的。因为 T LB 有 4 个组，所以 VP N 的低 2 位就作为组索引( T LBI) 。VP N 中剩下的高 6 位作为标记CT L BT ) , 用来区别可能映射到同一个 T LB 组的不同的 VP N。
页表。这个页表是一个单级设计，一共有 28 = 256 个页表条目( PT E ) 。然而，我们只对这些条目中的开头 16 个感兴趣。为了方便，我们用索引它的 VP N 来标识每个
PTE; 但是要记住这些 VP N 并不是页表的一部分，也不储存在内存中。另外，注意每个无效 PT E 的 PPN 都用一个破折号来表示，以加强一个概念：无论刚好这里存储的是什么位值，都是没有任何意义的。
高速缓存。直接映射的缓存是通过物理地址中的字段来寻址的。因为每个块都是 4 字节，所以物理地址的低 2 位作为块偏移( CO ) 。因为有 16 组，所以接下来的 4 位就用来表示组索引 ( CD 。剩下的 6 位作为标记CCT ) 。

虚拟地址

‘TLBT I七TLBI-

13 12 II IO 9 8 7 6 5 4 3 2 I 0

I I I I I I I I I I I I I I I

, VPN .‘VPO I

11I1IJ1iJlI II会 #

TLB: 四组， 16 个条目，四路组相联

VPN 00

PPN 有效位

VPN 08

OA OB

OD OE OF

PPN 有效位

页表：只展示了前16 个 PTE

物理地址

• CT• • CI• +- CO -+

II 10 9 8 7 6 5 4 3 2 I 0

I I I I I I I I I I I I I

PPN• • PPO•

索引有效位块 0 块 l 块 2 块 3

高速缓存： 16 个组，4 字节的块，直接映射

图 9 - 2 0

小内存系统的 T LB、页表以及缓存。T LB、页表和缓存中所有的值都是十六进制表示的

给定了这种初始化设定，让我们来看看当 CPU 执行一条读地址 Ox 0 3 d 4 处字节的加载指令时会发生什么。（回想一下我们假定 CPU 读取 1 字节的字，而不是 4 字节的字。）为了

开始这种手工的模拟，我们发现写下虚拟地址的各个位，标识出我们会需要的各种字段，并确定它们的十六进制值，是非常有帮助的。当硬件解码地址时，它也执行相似的任务。

开始时， MMU 从虚拟地址中抽取出 VP N ( OxOF) , 并且检查 T LB, 看它是否因为前面的某个内存引用缓存了 PT E OxO F 的一个副本。T LB 从 VPN 中抽取出 T LB 索引( Ox 03) 和 T LB 标记 ( Ox3 ) , 组 Ox 3 的第二个条目中有效匹配，所以命中，然后将缓存的 PP N ( OxOD) 返回给 MMU。

如果 T LB 不命中，那么 MMU 就需要从主存中取出相应的 PT E。然而，在这种情况中，我们很幸运， T L B 会命中。现在， MMU 有了形成物理地址所需要的所有东西。它通过将来自 PT E 的 PP N ( Ox OD) 和来自虚拟地址的 VPO ( Ox l 4) 连接起来，这就形成了物理地址( Ox 35 4) 。

接下来， MMU 发送物理地址给缓存，缓存从物理地址中抽取出缓存偏移 CO ( OxO) 、缓存组索引 CIC Ox5 ) 以及缓存标记 CT ( Ox OD) 。

因为组 Ox5 中的标记与 CT 相匹配，所以缓存检测到一个命中，读出在偏移量 co 处的数据字节( Ox 3 6) , 并将它返回给 MMU , 随后 MMU 将它传递回 CP U。

翻译过程的其他路径也是可能的。例如，如果 T LB 不命中，那么 MMU 必须从页表中的 PT E 中取出 PP N。如果得到的 PT E 是无效的，那么就产生一个缺页，内核必须调入合适的页面，重新运行这条加载指令。另一种可能性是 PT E 是有效的，但是所需要的内存块在缓存中不命中。

练习题 9. 4 说明 9. 6. 4 节中的示例内存系统是如何将一个虚拟地址翻译成一个物理地址和访问缓存的。对于给定的虚拟地址，指明访问的 T LB 条目、物理地址和返回的缓存字节值。指出是否发生了 T LB 不命中，是否发生了缺页，以及是否发生了缓存不命中。如果是缓存不命中，在“返回的缓存字节”栏中输入“—"。如果有缺页，则在 " PP N" 一栏中输入“—“ ，并且将 C 部分和 D 部分空着。

虚拟地址： Ox03d7

虚拟地址格式

13 12

I I

11 10 9

I I

L8J 7 6

5 4 3 2 1 0

I I I I I I

地址翻译
物理地址格式

11 10 9 8 7 6 5 4 3 2 I 0

物理内存引用

9. 7 案例研究： Intel Core i7/ Linux 内存系统

我们以一个实际系统的案例研究来总结我们对虚拟内存的讨论：一个运行 Linux 的Intel Core i7。虽然底层的 Haswe ll 微体系结构允许完全的 64 位虚拟和物理地址空间，而现在的（以及可预见的未来的）Core i7 实现支持 48 位( 256T B) 虚拟地址空间和 52 位( 4PB) 物理地址空间，还有一个兼容模式，支持 32 位( 4GB) 虚拟和物理地址空间。

图 9-21 给出了 Core i7 内存系统的重要部分。处理器封装( processor package) 包括四个核、一个大的所有核共享的 L3 高速缓存，以及一个 DDR3 内存控制器。每个核包含一个层次结构的 T LB、一个层次结构的数据和指令高速缓存，以及一组快速的点到点链路，这种链路基于 QuickPat h 技术，是为了让一个核与其他核和外部 1/ 0 桥直接通信。TLB 是虚拟寻址的，是四路组相联的。Ll 、L2 和 L3 高速缓存是物理寻址的，块大小为 64 字节。Ll 和 L2 是 8 路组相联的，而 L3 是 16 路组相联的。页大小可以在启动时被配置为

4KB 或 4MB 。Lin ux 使用的是 4KB 的页。

9. 7. 1 Core i7 地址翻译

图 9-22 总结了完整的 Core i7 地址翻译过程，从 CPU 产生虚拟地址的时刻一直到来自内存的数据字到达 CPU 。Core i7 采用四级页表层次结构。每个进程有它自己私有的页表层次结构。当一个 Linux 进程在运行时，虽然 Core i7 体系结构允许页表换进换出，但是与已分配了的页相关联的页表都是驻留在内存中的。CR3 控制寄存器指向第一级页表( Ll) 的起始位置。CR3 的值是每个进程上下文的一部分，每次上下文切换时， CR3 的值都会被恢复。

处理器封装

,———————————————————————————————————-

核 x 4

MMU

（地址翻译）

LI d-TLB 1 1 LI i-TLB

64 个条目， 4 路 128 个条目，4 路

L2 统一高速缓存

256 KB, 8 路

u 统一 TLB 512 个条目，4 路

到其他核到1/0 桥

13统一高速缓存

8 MB, 16 路

（所有的核共享）

DDR3存储器控制器

（所有的核共享）

! ._ 卜–匕– ——— — ——-

主存

图 9- 21 Core i7 的内存系统

Ll d-cache

( 64 组， 8 行／组）

TLB

不命中

CR3

页表

图9-22 Core i7 地址翻译的概况。为了简化，没有显示 i-cache 、i-T LB 和 L2 统一 T LB

图 9-23 给出了第一级、第二级或第三级页表中条目的格式。当 P = l 时( Linux 中就总是如此），地址字段包含一个 40 位物理页号( PPN ) , 它指向适当的页表的开始处。注意，这强加了一个要求，要求物理页表 4KB 对齐。

63 62 52 51

2 11

98 7 6 5 4 3 2 I 0

三页表物理基地址

未使用

G I PS I I A I CD I WT IUIS尸1

OS 可用（磁盘上的页表位置）三

图 9-23 第一级、第二级和第三级页表条目格式。每个条目引用一个 4K B 子页表

图 9-24 给出了第四级页表中条目的格式。当 P = l , 地址字段包括一个 40 位 PPN,

它指向物理内存中某一页的基地址。这又强加了一个要求，要求物理页 4KB 对齐。

63 62 5251

三页表物理基地址

12 11 9 8 7

未使用

6 5 4 3 2 1 0

D I A ICD IWTIUIS匠千=1

OS可用（磁盘上的页表位置）曰

图 9-24 第四级页表条目的格式。每个条目引用一个 4K B 子页

PT E 有三个权限位，控制对页的访问。R / W 位确定页的内容是可以读写的还是只读的。U/ S 位确定是否能够在用户模式中访问该页，从而保护操作系统内核中的代码和数据

不被用户程序访问。XDC禁止执行）位是在 64 位系统中引入的，可以用来禁止从某些内存页取指令。这是一个重要的新特性，通过限制只能执行只读代码段，使得操作系统内核降低了缓冲区溢出攻击的风险。

当 MMU 翻译每一个虚拟地址时，它还会更新另外两个内核缺页处理程序会用到的位。每次访问一个页时， MMU 都会设置 A 位，称为引用位( reference bit ) 。内核可以用这个引用位来实现它的页替换算法。每次对一个页进行了写之后， MMU 都会设置 D 位，又称修改位或脏位Cdirty bit ) 。修改位告诉内核在复制替换页之前是否必须写回牺牲页。内核可以通过调用一条特殊的内核模式指令来清除引用位或修改位。

图 9-25 给出了 Core i7 MMU 如何使用四级的页表来将虚拟地址翻译成物理地址。36 位 VP N 被划分成四个 9 位的片，每个片被用作到一个页表的偏移量。CR3 寄存器包含 Ll 页表的物理地址。VP N 1 提供到一个 Ll P ET 的偏移量，这个 PT E 包含 L2 页表的基地址。VP N 2 提供到一个 L2 PT E 的偏移量，以此类推。

VPN!

VPN2

VPN3

VPN4

VPO 虚拟地址

CR3

LI PT 的

物理地址

12 到物理和虚拟页的偏移量

每个条目每个条目

512 GB 区域 1 GB 区域

每个条目

2 MB 区域

每个条目 1 页的物理

4 KB 区域地址

PPN

PPO 物理地址

图 9- 25 Core i7 页表翻译 (PT: 页表， PT E: 页表条目， VPN: 虚拟页号， VPO: 虚拟页偏移，

PPN: 物理页号， PPO: 物理页偏移量。图中还给出了这四级页表的 Linu x 名字）

m 优化地址翻译

在对地址翻译的讨论中，我们描述了一个顺序的两个步骤的过程， l) M MU 将虚拟地址翻译成物理地址， 2 ) 将物理地址传送到 L l 高速缓存。然而，实际的硬件实现使用了一个灵活的技巧，允许这些步骤部分重叠，因此也就加速了对 Ll 高速缓存的访问。例如，页面大小为 4KB 的 Core i7 系统上的一个虚拟地址有 12 位的 VP O , 并且这些位和相应物理地址中的 PP O 的 1 2 位是相同的。因为八路组相联的、物理寻址的 Ll 高速缓存有 64 个组和大小为 64 字节的缓存块，每个物理地址有 6 个Oog 2 64 ) 缓存偏移位和

6 个(l og为4) 索引位。这 12 位恰好符合虚拟地址的 VPO 部分，这绝不是偶然！当 CP U

需要翻译一个虚拟地址时，它就发送 VP N 到 MMU, 发送 VPO 到高速 L1 缓存。当 MMU

向 T LB 请求一个页表条目时， L1 高速缓存正忙着利用 VPO 位查找相应的组，并读出1 这个组里的 8 个标记和相应的数据宇。当 MMU 从 T LB 得到 PPN 时，缓存已经准备好试着把这个 PPN 与这 8 个标记中的一个进行匹配了。

9 . 7 . 2 Linux 虚拟内存系统

一个虚拟内存系统要求硬件和内核软件之间的紧密协作。版本与版本之间细节都不尽相同，对此完整的阐释超出了我们讨论的范围。但是，在这一小节中我们的目标是对L in u x 的虚拟内存系统做一个描述，使你能够大致了解一个实际的操作系统是如何组织虚拟内存，以及如何处理缺页的。

Lin u x 为每个进程维护了一个单独的

虚拟地址空间，形式如图 9-26 所示。我们已经多次看到过这幅图了，包括它那些熟悉的代码、数据、堆、共享库以及栈段。

与进程相关的数据结构

（例如，页表、task 和

mm结构，内核栈）

内核虚拟

内存

既然我们理解了地址翻译，就能够填入更

多的关千内核虚拟内存的细节了，这部分虚拟内存位千用户栈之上。

内核虚拟内存包含内核中的代码和数据结构。内核虚拟内存的某些区域被映射到所有进程共享的物理页面。例如，每个进程共享内核的代码和全局数据结构。有趣的是， L in u x 也将一组连续的虚拟页面

（大小等千系统中 DRAM 的总量）映射到相应的一组连续的物理页面。这就为内核提供了一种便利的方法来访问物理内存中任何特定的位置，例如，当它需要访问页

%r sp 一令

br k -

物理内存

内核代码和数据

进程虚拟

内存

表，或在一些设备上执行内存映射的 J/0 O x4 0 0 00 0 0 0 –+

操作，而这些设备被映射到特定的物理内 °

存位置时。图 9-26 一个 Linux 进程的虚拟内存

内核虚拟内存的其他区域包含每个进程都不相同的数据。比如说，页表、内核在进程的上下文中执行代码时使用的栈，以及记录虚拟地址空间当前组织的各种数据结构。

L inux 虚拟内存区域
Lin ux 将虚拟内存组织成一些区域（也叫做段）的集合。一个区域( area ) 就是巳经存在着的（已分配的）虚拟内存的连续片( ch unk ) , 这些页是以某种方式相关联的。例如，代码段、数据段、堆、共享库段，以及用户栈都是不同的区域。每个存在的虚拟页面都保存在某个区域中，而不属于某个区域的虚拟页是不存在的，并且不能被进程引用。区域的概念很重要，因为它允许虚拟地址空间有间隙。内核不用记录那些不存在的虚拟页，而这样的页也不占用内存、磁盘或者内核本身中的任何额外资源。
图 9- 27 强调了记录一个进程中虚拟内存区域的内核数据结构。内核为系统中的每个进程维护一个单独的任务结构（源代码中的七a s k_s tr uc t ) 。任务结构中的元素包含或者指向内核运行该进程所需要的所有信息（例如， PI O、指向用户栈的指针、可执行目标文件的名字，以及程序计数器）。

t as k_s r七

uc t mm_ s rt

uc t

vm_ar ea_s tr uc t 进程虚拟内存

vrn_start vrn_prot

vrn_flags 数据

代码

vrn prot vrn_flags vrn_next

图 9- 27 Linux 是如何组织虚拟内存的

任务结构中的一个条目指向mm_s tr uc t , 它描述了虚拟内存的当前状态。我们感兴趣的两个字段是 pgd 和 mma p , 其中 pgd 指向第一级页表（页全局目录）的基址，而 mma p 指向一个vrn_ar e a _ s tr uc t s ( 区域结构）的链表，其中每个vrn_ ar e a _s tr uc t s 都描述了当前虚拟地址空间的一个区域。当内核运行这个进程时，就将 pgd 存放在 CR3 控制寄存器中。

为了我们的目的，一个具体区域的区域结构包含下面的字段：

vrn_ s t a r 七：指向这个区域的起始处。
• vm_ e nd : 指向这个区域的结束处。
vrn王r o t : 描述这个区域内包含的所有页的读写许可权限。
vm_flags: 描述这个区域内的页面是与其他进程共享的，还是这个进程私有的（还描述了其他一些信息）。
vm next: 指向链表中下一个区域结构。

Linux 缺页异常处理
假设 MMU 在试图翻译某个虚拟地址 A 时，触发了一个缺页。这个异常导致控制转移到内核的缺页处理程序，处理程序随后就执行下面的步骤：
1. 虚拟地址 A 是合法的吗？换句话说， A 在某个区域结构定义的区域内吗？为了回答这个问题，缺页处理程序搜索区域结构的链表，把 A 和每个区域结构中的 vrn_ s t ar t 和vm_e nd 做比较。如果这个指令是不合法的，那么缺页处理程序就触发一个段错误，从而终止这个进程。这个情况在图 9-28 中标识为 " l " 。
因为一个进程可以创建任意数量的新虚拟内存区域（使用在下一节中描述的 mma p 函数），所以顺序搜索区域结构的链表花销可能会很大。因此在实际中， L in ux 使用某些我们没有显示出来的字段， L in ux 在链表中构建了一棵树，并在这棵树上进行查找。
2 ) 试图进行的内存访问是否合法？换句话说，进程是否有读、写或者执行这个区域内页面的权限？例如，这个缺页是不是由一条试图对这个代码段里的只读页面进行写操作

的存储指令造成的？这个缺页是不是因为一个运行在用户模式中的进程试图从内核虚拟内存中读取字造成的？如果试图进行的访问是不合法的，那么缺页处理程序会触发一个保护异常，从而终止这个进程。这种情况在图 9-28 中标识为 " 2" 。

3 ) 此刻，内核知道了这个缺页是由于对合法的虚拟地址进行合法的操作造成的。它是这样来处理这个缺页的：选择一个牺牲页面，如果这个牺牲页面被修改过，那么就将它交换出去，换入新的页面并更新页表。当缺页处理程序返回时， CPU 重新启动引起缺页的指令，这条指令将再次发送A 到 MMU。这次， MMU 就能正常地翻译 A, 而不会再产生缺页中断了。

vrn_ar ea_s t r uct 进程虚拟内存

段错误：

访问一个不存在的页面

＠）正常缺页

保护异常：

vm_next

图 9-28 Linux 缺页处理

8 内存映射
Lin ux 通过将一个虚拟内存区域与一个磁盘上的对象( o bject ) 关联起来，以初始化这个虚拟内存区域的内容，这个过程称为内存映射( memory mapping ) 。虚拟内存区域可以映射到两种类型的对象中的一种：
1. Linu x 文件系统中的普通文件：一个区域可以映射到一个普通磁盘文件的连续部分，例如一个可执行目标文件。文件区( sect io n ) 被分成页大小的片，每一片包含一个虚拟页面的初始内容。因为按需进行页面调度，所以这些虚拟页面没有实际交换进入物理内存，直到 CPU 第一次引用到页面（即发射一个虚拟地址，落在地址空间这个页面的范围之内）。如果区域比文件区要大，那么就用零来填充这个区域的余下部分。
  1. ) 匿名文件：一个区域也可以映射到一个匿名文件，匿名文件是由内核创建的，包
    含的全是二进制零。CP U 第一次引用这样一个区域内的虚拟页面时，内核就在物理内存中找到一个合适的牺牲页面，如果该页面被修改过，就将这个页面换出来，用二进制零覆盖牺牲页面并更新页表，将这个页面标记为是驻留在内存中的。注意在磁盘和内存之间并没有实际的数据传送。因为这个原因，映射到匿名文件的区域中的页面有时也叫做请求二进制零的页( dem and-ze ro page ) 。
    无论在哪种情况中，一旦一个虚拟页面被初始化了，它就在一个由内核维护的专门的交换文件( s wa p file) 之间换来换去。交换文件也叫做交换空间 ( s wa p s pace ) 或者交换区域

(swap area)。需要意识到的很重要的一点是，在任何时刻，交换空间都限制着当前运行着的进程能够分配的虚拟页面的总数。

8. 1 再看共享对象
内存映射的概念来源于一个聪明的发现：如果虚拟内存系统可以集成到传统的文件系统中，那么就能提供一种简单而高效的把程序和数据加载到内存中的方法。
正如我们已经看到的，进程这一抽象能够为每个进程提供自己私有的虚拟地址空间，可以免受其他进程的错误读写。不过，许多进程有同样的只读代码区域。例如，每个运行 Linux shell 程序 ba s h 的进程都有相同的代码区域。而且，许多程序需要访问只读运行时库代码的相同副本。例如，每个 C 程序都需要来自标准 C 库的诸如 pr i nt f 这样的函数。那么，如果每个进程都在物理内存中保持这些常用代码的副本，那就是极端的浪费了。幸运的是，内存映射给我们提供了一种清晰的机制，用来控制多个进程如何共享对象。
一个对象可以被映射到虚拟内存的一个区域，要么作为共享对象，要么作为私有对象。如果一个进程将一个共享对象映射到它的虚拟地址空间的一个区域内，那么这个进程对这个区域的任何写操作，对于那些也把这个共享对象映射到它们虚拟内存的其他进程而言，也是可见的。而且，这些变化也会反映在磁盘上的原始对象中。
另一方面，对于一个映射到私有对象的区域做的改变，对于其他进程来说是不可见的，并且进程对这个区域所做的任何写操作都不会反映在磁盘上的对象中。一个映射到共享对象的虚拟内存区域叫做共享区域。类似地，也有私有区域。
假设进程 1 将一个共享对象映射到它的虚拟内存的一个区域中，如图 9- 29a 所示。现在假设进程 2 将同一个共享对象映射到它的地址空间（并不一定要和进程 1 在相同的虚拟地址处，如图 9-296 所示）。

进程 l 的	物理	进程2 的	进程 1 的	物理	进程 2 的
虚拟内存	内存	虚拟内存	虚拟内存	内存	虚拟内存

共享对象

a ) 进程 1 映射了共享对象之后

共享对象

b ) 进程 2 映射了同一个共享对象之后

图 9-29 一个共享对象（注意，物理页面不一定是连续的）

因为每个对象都有一个唯一的文件名，内核可以迅速地判定进程 1 已经映射了这个对象，而且可以使进程 2 中的页表条目指向相应的物理页面。关键点在于即使对象被映射到了多个共享区域，物理内存中也只需要存放共享对象的一个副本。为了方便，我们将物理页面显示为连续的，但是在一般情况下当然不是这样的。

私有对象使用一种叫做写时复制( copy-on-write) 的巧妙技术被映射到虚拟内存中。一个

私有对象开始生命周期的方式基本上与共享对象的一样，在物理内存中只保存有私有对象的一份副本。比如，图 9-30a 展示了一种情况，其中两个进程将一个私有对象映射到它们虚拟内存的不同区域，但是共享这个对象同一个物理副本。对于每个映射私有对象的进程，相应私有区域的页表条目都被标记为只读，并且区域结构被标记为私有的写时复制。只要没有进程试图写它自己的私有区域，它们就可以继续共享物理内存中对象的一个单独副本。然而，只要有一个进程试图写私有区域内的某个页面，那么这个写操作就会触发一个保护故障。

当故障处理程序注意到保护异常是由于进程试图写私有的写时复制区域中的一个页面而引起的，它就会在物理内存中创建这个页面的一个新副本，更新页表条目指向这个新的副本，然后恢复这个页面的可写权限，如图 9-30b 所示。当故障处理程序返回时， CPU 重新执行这个写操作，现在在新创建的页面上这个写操作就可以正常执行了。

进程1 的虚拟内存

物理进程2 的

内存虚拟内存

私有的写时复制对象

a ) 两个进程都映射了私有的写时复制对象之后

私有的写时复制对象

b ) 进程2 写了私有区域中的一个页之后

写私有的写时复制的页

图 9-30 一个私有的写时复制对象

通过延迟私有对象中的副本直到最后可能的时刻，写时复制最充分地使用了稀有的物理内存。

9. 8. 2 再看 f or k 函数

既然我们理解了虚拟内存和内存映射，那么我们可以清晰地知道 f or k 函数是如何创建一个带有自己独立虚拟地址空间的新进程的。

当 f or k 函数被当前进程调用时，内核为新进程创建各种数据结构，并分配给它一个唯一的 PID。为了给这个新进程创建虚拟内存，它创建了当前进程的 mrn_ s tr uc t 、区域结构和页表的原样副本。它将两个进程中的每个页面都标记为只读，并将两个进程中的每个区域结构都标记为私有的写时复制。

当 f or k 在新进程中返回时，新进程现在的虚拟内存刚好和调用 f or k 时存在的虚拟内存相同。当这两个进程中的任一个后来进行写操作时，写时复制机制就会创建新页面，因此，也就为每个进程保持了私有地址空间的抽象概念。

9. 8. 3 再看 ex ecv e 函数

虚拟内存和内存映射在将程序加载到内存的过程中也扮演着关键的角色。既然已经理解了这些概念，我们就能够理解 e x e c v e 函数实际上是如何加载和执行程序的。假设运行

在当前进程中的程序执行了如下的 e xe c ve 调用：

execve(“a.out”, NULL, NULL);

正如在第8 章中学到的，e xe cve 函数在当前进程中加载并运行包含在可执行目标文件a . out

中的程序，用a .out 程序有效地替代了当前程序。加载并运行a . OU七需要以下几个步骤：

删除已存在的用户区域。删除当前进程虚拟地址的用户部分中的已存在的区域结构。
- 映射私有区域。为新程序的代码、数据、bss 和栈区域创建新的区域结构。所有这些新的区域都是私有的、写时复制的。代码和数据区域被映射为 a . out 文件中的. t e xt 和. da t a 区。bss 区域是请求二进制零的，映射到匿名文件，其大小包含在a . out 中。栈和堆区域也是请求二进制零的，初始长度为零。图9-31 概括了私有区域的不同映射。
- 映射共享区域。如果 a . o ut 程序与共享对象（或目标）链接，比如标准 C 库 li bc .
  so, 那么这些对象都是动态链接到这个程序的，然后再映射到用户虚拟地址空间中的共享区域内。
- 设置程序计数器 ( PC ) 。 e x e c v e 做的最后一件事情就是设置当前进程上下文中的程序计数器，使之指向代码区域的入口点。
  下一次调度这个进程时，它将从这个入口点开始执行。L in u x 将根据需要换入代码和数据页面。

运行时堆

（通过 malloc 分配的）

｝私有的，请求二进制零的

未初始化的数据(.bss) ｝私有的，请求二进制零的

I已初始化的数据(. da ca )

代码(.t ex七）

。

｝私有的，文件提供的

图 9- 31 加载器是如何映射用户地址空间的区域的

8. 4 使用 mmap 函数的用户级内存映射
Linux 进程可以使用 mmap 函数来创建新的虚拟内存区域，并将对象映射到这些区域中。

#include <unistd.h>

#include <sys/mman.h>

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

返回：若成功时则为指向映射区域的指针，若出错则为 MAP_FAILED( —1) 。

mrna p 函数要求内核创建一个新的虚拟内存区域，最好是从地址 s t ar t 开始的一个区域，并将文件描述符 f d 指定的对象的一个连续的片( ch un k ) 映射到这个新的区域。连续的对象片大小为 l e n g t h 字节，从距文件开始处偏移量为 o f f s e t 字节的地方开始。s t a r t 地址仅仅是一个暗示，通常被定义为 NU LL 。为了我们的目的，我们总是假设起始地址为NU LL。图 9-32 描述了这些参数的意义。

} length (字节）

s t ar t

（或

定的地址）

文件描述符f d 指定进程虚拟内存的磁盘文件

图 9-32 mmap 参数的可视化解释

参数 p r o t 包含描述新映射的虚拟内存区域的访问权限位（即在相应区域结构中的 vrn_ p r o t 位）。

PROT_EXEC: 这个区域内的页面由可以被 CPU 执行的指令组成。
- PROT_READ: 这个区域内的页面可读。
- PROT_WRITE: 这个区域内的页面可写。
- PROT_NONE: 这个区域内的页面不能被访问。
  参数 fl a g s 由描述被映射对象类型的位组成。如果设置了 MAP _A NON 标记位，那么被映射的对象就是一个匿名对象，而相应的虚拟页面是请求二进制零的。MAP _PRI VAT E 表示被映射的对象是一个私有的、写时复制的对象，而 MAP _SH ARED 表示是一个共享对象。例如
  bufp = Mmap(NULL, size, PROT_READ, MAP_PRIVATEIMAP_ANON, 0, O);

让内核创建一个新的包含 s i z e 字节的只读、私有、请求二进制零的虚拟内存区域。如果调用成功，那么 b u f p 包含新区域的地址。

mu n ma p 函数删除虚拟内存的区域：

#include <un i s t d . h>

#include <sys/mman.h>

int munmap(void *start, size_t length);

返回：若成功则为 o, 若出错则为一1.

mu n ma p 函数删除从虚拟地址 s t ar t 开始的，由接下来 l e n g t h 字节组成的区域。接下来对已删除区域的引用会导致段错误。

沁§ 练习题 9. 5 编写一个 C 程序 mma p c o p y . c , 使用 mma p 将一个任意大小的磁盘文件复制到 s t d o u t 。输入文件的名字必须作为一个命令行参数来传递。

9 动态内存分配
虽然可以使用低级的 mma p 和 mu nma p 函数来创建和删除虚拟内存的区域，但是 C 程序员还是会觉得当运行时需要额外虚拟内存时，用动态内存分配器( d ynam ic memory allo cator ) 更方便，也有更好的可移植性。
动态内存分配器维护着一个进程的虚拟内存区

域，称为堆 ( hea p ) ( 见图 9-33 ) 。系统之间细节不同，但是不失通用性，假设堆是一个请求二进制零的区域，它紧接在未初始化的数据区域后开始，并向上生长（向更高的地址）。对于每个进程，内核维护着一个变量 br k( 读做 " break" ) , 它指向堆的顶部。

分配器将堆视为一组不同大小的块( block ) 的集合来维护。每个块就是一个连续的虚拟内存片( ch un k ) , 要么是已分配的，要么是空闲的。已分配的块显式地保留为供应用程序使用。空闲块可用来分配。空闲块保持空闲，直到它显式地被应用所分配。一个巳分配的块保持已分配状态，直到它被释放，这种释放要么是应用程序显式执行的，要么是内存分配器自身隐式

执行的。

分配器有两种基本风格。两种风格都要求应用显 °

式地分配块。它们的不同之处在千由哪个实体来负责释放已分配的块。

用户栈

共享库的内存映射区域

堆

未初始化的数据 ( .bs s )

已初始化的数据 ( . da t a )

代码（．七ext )

图 9-33 堆

仁堆顶

( br k 指针）

显式分配器 ( ex plicit allocator) , 要求应用显式地释放任何巳分配的块。例如， C 标准库提供一种叫做 ma l l o c 程序包的显式分配器。C 程序通过调用 ma l l o c 函数来
．分配一个块，并通过调用 fr e e 函数来释放一个块。C++ 中的 ne w 和 d e l e t e 操作符与 C 中的 ma l l o c 和 fr e e 相当。
- 隐式分配器 ( im plicit allocator), 另一方面，要求分配器检测一个巳分配块何时不再被程序所使用，那么就释放这个块。隐式分配器也叫做垃圾收集器( ga r bage collec
  tor), 而自动释放未使用的已分配的块的过程叫做垃圾收集 ( ga r ba ge collect io n ) 。例如，诸如 L is p、M L 以及 Java 之类的高级语言就依赖垃圾收集来释放已分配的块。
  本节剩下的部分讨论的是显式分配器的设计和实现。我们将在 9. 10 节中讨论隐式分配器。为了更具体，我们的讨论集中于管理堆内存的分配器。然而，应该明白内存分配是一个普遍的概念，可以出现在各种上下文中。例如，图形处理密集的应用程序就经常使用标准分配器来要求获得一大块虚拟内存，然后使用与应用相关的分配器来管理内存，在该块中创建和销毁图形的节点。

9. 1 ma l l o c 和 fr e e 函数
C 标准库提供了一个称为 ma l l o c 程序包的显式分配器。程序通过调用 ma l l o c 函数来从堆中分配块。

#include <stdlib.h>

void *malloc(size_t size);

返回：若成功则为己分配块的指针，若出错则为 NULL。

ma l l o c 函数返回一个指针，指向大小为至少 s i z e 字节的内存块，这个块会为可能包含在这个块内的任何数据对象类型做对齐。实际中，对齐依赖于编译代码在 32 位模式(gee -m3 2) 还是 64 位模式（默认的）中运行。在 3 2 位模式中， ma l l o e 返回的块的地址总是 8 的倍数。在 64 位模式中，该地址总是 1 6 的倍数。

田日－个字有多大

回想一下在第 3 章中我们对机器代码的讨论， In tel 将 4 宇节对象称为双宇。然而，在本节中，我们会假设宇是 4 字节的对象，而双宇是 8 宇节的对象，这和传统术语是一致的。

如果 ma l l o e 遇到问题（例如，程序要求的内存块比可用的虚拟内存还要大），那么它就返回 N U LL , 并设置 e rr n o。ma l l o e 不初始化它返回的内存。那些想要已初始化的动态内存的应用程序可以使用 e a l l o e , e a l l o e 是一个基于 ma l l o e 的瘦包装函数，它将分配的内存初始化为零。想要改变一个以前已分配块的大小，可以使用r e a l l oe 函数。

动态内存分配器，例如 ma l l o e , 可以通过使用 mrna p 和 mu n ma p 函数，显式地分配和释放堆内存，或者还可以使用 s br k 函数：

#include <unistd.h>

void *sbrk(intptr_t incr);

返回：若成功则为旧的 brk 指针，若出铸则为一1.

s br k 函数通过将内核的 b r k 指针增加 i ncr 来扩展和收缩堆。如果成功，它就返回b r k 的旧值，否则，它就返回 —1 , 并将 er r n o 设置为 ENOMEM。如果 i n cr 为零，那么s br k 就返回 b r k 的当前值。用一个为负的 i n cr 来调用 s br k 是合法的，而且很巧妙，因为返回值( br k 的旧值）指向距新堆顶向上 a b s ( i n cr ) 字节处。

程序是通过调用 f r e e 函数来释放已分配的堆块。

#include <stdlib.h> void free(void *ptr);

返回：无．

p tr 参数必须指向一个从 ma l l o c 、 c a l l o c 或者r e a l l o c 获得的已分配块的起始位置。如果不是，那么 fr e e 的行为就是未定义的。更糟的是，既然它什么都不返回， f r ee 就不会告诉应用出现了错误。就像我们将在 9. 11 节里看到的，这会产生一些令人迷惑的运行时错误。

图 9- 3 4 展示了一个 ma l l o c 和 f r e e 的实现是如何管理一个 C 程序的 1 6 字的（非常）小

的堆的。每个方框代表了一个 4 字节的字。粗线标出的矩形对应于已分配块（有阴影的）和空闲块（无阴影的）。初始时，堆是由一个大小为 16 个字的、双字对齐的、空闲块组成的。

（本节中，我们假设分配器返回的块是 8 字节双字边界对齐的。）

图 9- 3 4 a : 程序请求一个 4 字的块。ma l l o c 的响应是：从空闲块的前部切出一个 4
字的块，并返回一个指向这个块的第一字的指针。
- 图 9- 34 b : 程序请求一个 5 字的块。

ma l l o c 的响应是：从空闲块的前部分配一个 6 字的块。在本例中， ma l l o c 在块里填充了一个额外的字，是为了保待空闲块是双字边界对齐的。

图 9- 3 4 c : 程序请求一个 6 字的块，而ma l l o c 就从空闲块的前部切出一个 6 字的块。
- 图 9- 3 4 d : 程序释放在图 9- 3 4 b 中分配的那个 6 字的块。注意，在调用 fr e e 返回之后，指针 p 2 仍然指向被释放了的块。应用有责任在它被一个新的 ma l l o c 调用重新初始化之前，不再使用 p 2。
- 图 9- 3 4 e : 程序请求一个 2 字的块。在这种情况中， ma l l o c 分配在前一步中被释放了的块的一部分，并返回一个
  1

I I I I I I I I I I I I I #

a)pl = malloc(4*sizeof(int))

1 2

II I I I I I I I 牖 I I #

b)p2 = malloc (5*sizeof (i n 七））

1 2 3

I I I I I I I I 蹋 I I #

c)p3 = ma l l oc ( 6*s i zeo f (i n 七））

p1 p2

+ +

I I I I I I I #

free (p2)
1 p!,4 3

I I I I I I I I I I I #

e)p4 = ma ll oc ( 2* 江 zeof ( i nt ) )

指向这个新块的指针。

9. 2 为什么要使用动态内存分配
程序使用动态内存分配的最重要的原因是经常直到程序实际运行时，才知道某些数
图 9-34
用 ma l l oc 和 fr e e 分配和释放块。每个
方框对应于一个字。每个粗线标出的矩形对应于一个块。阴影部分是已分配的块。已分配的块的填充区域是深阴影的。无阴影部分是空闲块。堆地址是从左往右增加的

据结构的大小。例如，假设要求我们编写一个 C 程序，它读一个 n 个 ASCII 码整数的链表，每一行一个整数，从 s t d i n 到一个 C 数组。输入是由整数 n 和接下来要读和存储到数组中的 n 个整数组成的。最简单的方法就是静态地定义这个数组，它的最大数组大小是硬编码的：

#include “csapp.h”
1. #define MAXN 15213
  3
  4 int array [MAXN] ;
  5
  6 int main()
  7 {
  s int i, n;
  9
  10 scanf("%d", &n);
if (n > MAXN)
app_error(“Input file toobig”);
for (i = O; i < n; i++)
scanf ("%d", &array [i]);
exit(O); 16 }

像这样用硬编码的大小来分配数组通常不是一种好想法。MAXN 的值是任意的，与机器上可用的虚拟内存的实际数量没有关系。而且，如果这个程序的使用者想读取一个比 MAXN 大的文件，唯一的办法就是用一个更大的 MAXN 值来重新编译这个程序。虽然对于这个简单的示例来说这不成问题，但是硬编码数组界限的出现对于拥有百万行代码和大量使用者的大型软件产品而言，会变成一场维护的噩梦。

一种更好的方法是在运行时，在已知了 n 的值之后，动态地分配这个数组。使用这种方法，数组大小的最大值就只由可用的虚拟内存数量来限制了。

1 #include “csapp.h”

3 int main()

5 int *array, i, n;

7 scanf ("%d", &n);

8 array = (int *)Malloc(n * sizeof(int)); 9 for (i = 0; i < n; i ++)

s can f ( " %d " , &array[i]);
1. free(array);
2. exit(O);
  13 }

动态内存分配是一种有用而重要的编程技术。然而，为了正确而高效地使用分配器，程序员需要对它们是如何工作的有所了解。我们将在 9. 11 节中讨论因为不正确地使用分配器所导致的一些可怕的错误。

9. 3 分配器的要求和目标
显式分配器必须在一些相当严格的约束条件下工作：
- 处理任意请求序列。一个应用可以有任意的分配请求和释放请求序列，只要满足约束条件：每个释放请求必须对应于一个当前巳分配块，这个块是由一个以前的分配请求获得的。因此，分配器不可以假设分配和释放请求的顺序。例如，分配器不能假设所有的分配请求都有相匹配的释放请求，或者有相匹配的分配和空闲请求是嵌套的。
- 立即响应请求。分配器必须立即响应分配请求。因此，不允许分配器为了提高性能重新排列或者缓冲请求。
- 只使用堆。为了使分配器是可扩展的，分配器使用的任何非标量数据结构都必须保存在堆里。
- 对齐块（对齐要求）。分配器必须对齐块，使得它们可以保存任何类型的数据对象。
- 不修改已分配的块。分配器只能操作或者改变空闲块。特别是，一旦块被分配了，就不允许修改或者移动它了。因此，诸如压缩已分配块这样的技术是不允许使用的。
  在这些限制条件下，分配器的编写者试图实现吞吐率最大化和内存使用率最大化，而这两个性能目标通常是相互冲突的。
- 目标 1 : 最大化吞吐率。假定 n 个分配和释放请求的某种序列：
  R 。,R1 , …，Rk’ …，Rn - I

我们希望一个分配器的吞吐率最大化，吞吐率定义为每个单位时间里完成的请求数。例如，如果一个分配器在 1 秒内完成 500 个分配请求和 500 个释放请求，那么它的吞吐率就是每秒 1000 次操作。一般而言，我们可以通过使满足分配和释放请求的平均时间最小化来使吞吐率最大化。正如我们会看到的，开发一个具有合理性能的分配器并不困难，所谓合理性能是指一个分配请求的最糟运行时间与空闲块的数量成线性关系，而一个释放请求的运行时间是个常数。

目标 2: 最大化内存利用率。天真的程序员经常不正确地假设虚拟内存是一个无限的资源。实际上，一个系统中被所有进程分配的虚拟内存的全部数量是受磁盘上交换空间的数量限制的。好的程序员知道虚拟内存是一个有限的空间，必须高效地使用。对于可能被要求分配和释放大块内存的动态内存分配器来说，尤其如此。
有很多方式来描述一个分配器使用堆的效率如何。在我们的经验中，最有用的标准是峰值利用率 ( peak utiliza tion ) 。像以前一样，我们给定 n 个分配和释放请求的某种顺序
R。R,1, …，Rk’ …，Rn- 1
如果一个应用程序请求一个 p 字节的块，那么得到的巳分配块的有效栽荷 ( payload ) 是 p 字节。在请求凡完成之后，聚集有效栽荷 ( agg rega te pa yload ) 表示为p k’ 为当前已分配的块的有效载荷之和，而几表示堆的当前的（单调非递减的）大小。
那么，前 k+ l 个请求的峰值利用率，表示为 Uk , 可以通过下式得到：

队＝ m a x;,;;k; P ;

那么，分配器的目标就是在整个序列中使峰值利用率 Un- 1 最大化。正如我们将要看到的，在最大化吞吐率和最大化利用率之间是互相牵制的。特别是，以堆利用率为代价，很容易编写出吞吐率最大化的分配器。分配器设计中一个有趣的挑战就是在两个目标之间找到一个适当的平衡。

调性假设

我们可以通过让 Hk 成为前k + l 个请求的最高峰，从而使得在我们对队的定义中放宽单调非递减的假设，并且允许堆增长和降低。

9. 9. 4 碎片

造成堆利用率很低的主要原因是一种称为碎片 ( fr ag m ent a tio n ) 的现象，当虽然有未使用的内存但不能用来满足分配请求时，就发生这种现象。有两种形式的碎片：内部碎片(internal fragmentation) 和外部碎片 ( ext e rn a l fr a gm e n ta t ion ) 。

内部碎片是在一个已分配块比有效载荷大时发生的。很多原因都可能造成这个问题。例如，一个分配器的实现可能对已分配块强加一个最小的大小值，而这个大小要比某个请求的有效载荷大。或者，就如我们在图 9-34b 中看到的，分配器可能增加块大小以满足对齐约束条件。

内部碎片的量化是简单明了的。它就是已分配块大小和它们的有效载荷大小之差的和。因此，在任意时刻，内部碎片的数最只取决于以前请求的模式和分配器的实现方式。

外部碎片是当空闲内存合计起来足够满足一个分配请求，但是没有一个单独的空闲块足够大可以来处理这个请求时发生的。例如，如果图 9-34e 中的请求要求 6 个字，而不是

2 个字，那么如果不向内核请求额外的虚拟内存就无法满足这个请求，即使在堆中仍然有

6 个空闲的字。问题的产生是由于这 6 个字是分在两个空闲块中的。

外部碎片比内部碎片的扯化要困难得多，因为它不仅取决于以前请求的模式和分配器的实现方式，还取决于将来请求的模式。例如，假设在 K 个请求之后，所有空闲块的大小都恰好是 4 个字。这个堆会有外部碎片吗？答案取决于将来请求的模式。如果将来所有的分配请求都要求小于或者等于 4 个字的块，那么就不会有外部碎片。另一方面，如果有一个或者多个请求要求比 4 个字大的块，那么这个堆就会有外部碎片。

因为外部碎片难以量化且不可能预测，所以分配器通常采用启发式策略来试图维持少量的大空闲块，而不是维持大量的小空闲块。

9. 5 实现问题
可以想象出的最简单的分配器会把堆组织成一个大的字节数组，还有一个指针 p , 初始指向这个数组的第一个字节。为了分配 s i ze 个字节， ma l l o c 将 p 的当前值保存在栈里，将 p 增加 s 工ze , 并将 p 的旧值返回到调用函数。fr e e 只是简单地返回到调用函数，而不做其他任何事情。
这个简单的分配器是设计中的一种极端情况。因为每个 ma l l o c 和 fr e e 只执行很少量的指令，吞吐率会极好。然而，因为分配器从不重复使用任何块，内存利用率将极差。一个实际的分配器要在吞吐率和利用率之间把握好平衡，就必须考虑以下几个问题：
- 空闲块组织：我们如何记录空闲块？

放置：我们如何选择一个合适的空闲块来放置一个新分配的块？
分割：在将一个新分配的块放置到某个空闲块之后，我们如何处理这个空闲块中的剩余部分？
合并：我们如何处理一个刚刚被释放的块？
本节剩下的部分将更详细地讨论这些问题。因为像放置、分割以及合并这样的基本技术贯穿在许多不同的空闲块组织中，所以我们将在一种叫做隐式空闲链表的简单空闲块组织结构中来介绍它们。

9. 9. 6 隐式空闲链表

任何实际的分配器都需要一些数据结构，允许它来区别块边界，以及区别巳分配块和空闲块。大多数分配器将这些信息嵌入块本身。一个简单的方法如图 9-35 所示。

rna l l oc 返回一个指针，它指向有效载荷的开始处

31 头部

， #

3 2 I 0

} a= I: 已分配的

a=O: 空闲的

块大小包括头部、

有效载荷和所有的填充

图 9-35 一个简单的堆块的格式

在这种情况中，一个块是由一个字的头部、有效载荷，以及可能的一些额外的埃充组成的。头部编码了这个块的大小（包括头部和所有的填充），以及这个块是已分配的还是空

闲的。如果我们强加一个双字的对齐约束条件，那么块大小就总是 8 的倍数，且块大小的最低 3 位总是零。因此，我们只需要内存大小的 29 个高位，释放剩余的 3 位来编码其他信息。在这种情况中，我们用其中的最低位（已分配位）来指明这个块是已分配的还是空闲的。例如，假设我们有一个已分配的块，大小为 24 ( 0x1 8) 字节。那么它的头部将是

Ox00000018 I Ox1 = Ox00000019

类似地，一个块大小为 40 ( 0x 28) 字节的空闲块有如下的头部：

Ox00000028 I OxO = Ox00000028

头部后面就是应用调用 ma l l o c 时请求的有效载荷。有效载荷后面是一片不使用的填充块，其大小可以是任意的。需要填充有很多原因。比如，填充可能是分配器策略的一部分，用来对付外部碎片。或者也需要用它来满足对齐要求。

假设块的格式如图 9-35 所示，我们可以将堆组织为一个连续的已分配块和空闲块的序列，如图 9-36 所示。

目口勹16" I I 圈立。I I I I I

Ti•11I I I - 圃扂的

＇ , ，＇’ : ，’ ＇’ ，’

’’ ’’ '’

’’ '’

’’ :’

图 9-36 用隐式空闲链表来组织堆。阴影部分是已分配块。没有阴影的部分是空闲块。头部标记为（大小（字节／）已分配位）

我们称这种结构为隐式空闲链表，是因为空闲块是通过头部中的大小字段隐含地连接着的。分配器可以通过遍历堆中所有的块，从而间接地遍历整个空闲块的集合。注意，我们需要某种特殊标记的结束块，在这个示例中，就是一个设置了已分配位而大小为零的终止头部 ( ter minating header) 。（就像我们将在9. 9. 12 节中看到的，设置已分配位简化了空闲块的合并。）

隐式空闲链表的优点是简单。显著的缺点是任何操作的开销，例如放置分配的块，要求对空闲链表进行搜索，该搜索所需时间与堆中已分配块和空闲块的总数呈线性关系。

很重要的一点就是意识到系统对齐要求和分配器对块格式的选择会对分配器上的最小块大小有强制的要求。没有巳分配块或者空闲块可以比这个最小值还小。例如，如果我们假设一个双字的对齐要求，那么每个块的大小都必须是双字( 8 字节）的倍数。因此，图 9-

35 中的块格式就导致最小的块大小为两个字：一个字作头，另一个字维持对齐要求。即使应用只请求一字节，分配器也仍然需要创建一个两字的块。

练习题 9. 6 确定下面 ma l l o c 请求序列产生的块大小和头部值。假设： 1 ) 分配器保持双字对齐，并且使用块格式如图 9-35 中所示的隐式空闲链表。 2) 块大小向上舍入为最接近的 8 字节的倍数。

9. 9. 7 放置已分配的块

当一个应用请求一个 K 字节的块时，分配器搜索空闲链表，查找一个足够大可以放置

所请求块的空闲块。分配器执行这种搜索的方式是由放置策略 ( placem e n t policy ) 确定的。一些常见的策略是首次适配( fi rs t fit ) 、下一次适配( next fi t ) 和最佳适配( bes t fi t ) 。

首次适配从头开始搜索空闲链表，选择第一个合适的空闲块。下一次适配和首次适配很相似，只不过不是从链表的起始处开始每次搜索，而是从上一次查询结束的地方开始。最佳适配检查每个空闲块，选择适合所需请求大小的最小空闲块。

首次适配的优点是它趋向于将大的空闲块保留在链表的后面。缺点是它趋向千在靠近链表起始处留下小空闲块的＂碎片“，这就增加了对较大块的搜索时间。下一次适配是由Donald Knut h 作为首次适配的一种代替品最早提出的，源千这样一个想法：如果我们上一次在某个空闲块里已经发现了一个匹配，那么很可能下一次我们也能在这个剩余块中发现匹配。下一次适配比首次适配运行起来明显要快一些，尤其是当链表的前面布满了许多小的碎片时。然而，一些研究表明，下一次适配的内存利用率要比首次适配低得多。研究还表明最佳适配比首次适配和下一次适配的内存利用率都要高一些。然而，在简单空闲链表组织结构中，比如隐式空闲链表中，使用最佳适配的缺点是它要求对堆进行彻底的搜索。在后面，我们将看到更加精细复杂的分离式空闲链表组织，它接近于最佳适配策略，不需要进行彻底的堆搜索。

9. 9. 8 分割空闲块

一旦分配器找到一个匹配的空闲块，它就必须做另一个策略决定，那就是分配这个空闲块中多少空间。一个选择是用整个空闲块。虽然这种方式简单而快捷，但是主要的缺点就是它会造成内部碎片。如果放置策略趋向于产生好的匹配，那么额外的内部碎片也是可以接受的。

然而，如果匹配不太好，那么分配器通常会选择将这个空闲块分割为两部分。第一部分变成分配块，而剩下的变成一个新的空闲块。图 9-37 展示了分配器如何分割图 9-36 中

8 个字的空闲块，来满足一个应用的对堆内存 3 个字的请求。

！双字

i对齐的

图 9-37 分割一个空闲块，以满足一个 3 个字的分配请求。阴影部分是已分配块。没有阴影的部分是空闲块。头部标记为（大小（字节／）已分配位）

9. 9. 9 获取额外的堆内存

如果分配器不能为请求块找到合适的空闲块将发生什么呢？一个选择是通过合并那些在内存中物理上相邻的空闲块来创建一些更大的空闲块（在下一节中描述）。然而，如果这样还是不能生成一个足够大的块，或者如果空闲块巳经最大程度地合并了，那么分配器就会通过调用 s br k 函数，向内核请求额外的堆内存。分配器将额外的内存转化成一个大的空闲块，将这个块插入到空闲链表中，然后将被请求的块放置在这个新的空闲块中。

9. 9. 10 合并空闲块

当分配器释放一个已分配块时，可能有其他空闲块与这个新释放的空闲块相邻。这些邻接的空闲块可能引起一种现象，叫做假碎片 ( fa ult fragmentation), 就是有许多可用的

空闲块被切割成为小的、无法使用的空闲块。比如，图 9- 38 展示了释放图 9-37 中分配的块后得到的结果。结果是两个相邻的空闲块，每一个的有效载荷都为 3 个字。因此，接下来一个对 4 字有效载荷的请求就会失败，即使两个空闲块的合计大小足够大，可以满足这个请求。

图 9-38 假碎片的示例。阴影部分是已分配块。没有阴影的部分是空闲块。头部标记为（大小（字节）／已分配位）

为了解决假碎片问题，任何实际的分配器都必须合并相邻的空闲块，这个过程称为合并( coalescing ) 。这就出现了一个重要的策略决定，那就是何时执行合并。分配器可以选择立即合并 ( im mediat e coalescing), 也就是在每次一个块被释放时，就合并所有的相邻块。或者它也可以选择推迟合并( defe r red coalescing) , 也就是等到某个稍晚的时候再合并空闲块。例如，分配器可以推迟合并，直到某个分配请求失败，然后扫描整个堆，合并所有的空闲块。

立即合并很简单明了，可以在常数时间内执行完成，但是对于某些请求模式，这种方式会产生一种形式的抖动，块会反复地合并，然后马上分割。例如，在图 9-38 中，反复地分配和释放一个 3 个字的块将产生大最不必要的分割和合并。在对分配器的讨论中，我们会假设使用立即合并，但是你应该了解，快速的分配器通常会选择某种形式的推迟合并。

9. 11 带边界标记的合井
分配器是如何实现合并的？让我们称想要释放的块为当前块。那么，合并（内存中的）下一个空闲块很简单而且高效。当前块的头部指向下一个块的头部，可以检查这个指针以判断下一个块是否是空闲的。如果是，就将它的大小简单地加到当前块头部的大小上，这两个块在常数时间内被合并。
但是我们该如何合并前面的块呢？给定一个带头部的隐式空闲链表，唯一的选择将是搜索整个链表，记住前面块的位置，直到我们到达当前块。使用隐式空闲链表，这意味着每次调用 fr e e 需要的时间都与堆的大小成线性关系。即使使用更复杂精细的空闲链表组
织，搜索时间也不会是常数。

Knuth 提出了一种聪明而通用的技术，叫做 31

3 2 I 0

a= 001: 已分配的

边界标记 ( boundary tag), 允许在常数时间内进行对前面块的合并。这种思想，如图 9-39 所示，是在每个块的结尾处添加一个脚部( footer , 边界标记），其中脚部就是头部的一个副本。如果每个块包括这样一个脚部，那么分配器就可以通过检查它的脚部，判断前面一个块的起始位置和状态，这个脚部总是在距当前块开始位置一个字的距离。考虑当分配器释放当前块时所有可能存在的

情况：

头部 a= 000: 空闲的

脚部

图 9-39 使用边界标记的堆块的格式

前面的块和后面的块都是已分配的。
) 前面的块是已分配的，后面的块是空闲的。
) 前面的块是空闲的，而后面的块是已分配的。
) 前面的和后面的块都是空闲的。
图 9-40 展示了我们如何对这四种情况进行合并。

，，

情况 l

情况2

n+ m1+ m2 J f

，．

情况3 情况 4

n+ m1+ m2 j f

图 9-40 使用边界标记的合并（情况 1 : 前面的和后面块都已分配。情况 2 : 前面块巳分配，后面块空闲。情况 3: 前面块空闲，后面块已分配。情况 4 : 后面块和前面块都空闲）

在情况 1 中，两个邻接的块都是已分配的，因此不可能进行合并。所以当前块的状态只是简单地从已分配变成空闲。在情况 2 中，当前块与后面的块合并。用当前块和后面块的大小的和来更新当前块的头部和后面块的脚部。在情况 3 中，前面的块和当前块合并。用两个块大小的和来更新前面块的头部和当前块的脚部。在情况 4 中，要合并所有的三个块形成一个单独的空闲块，用三个块大小的和来更新前面块的头部和后面块的脚部。在每种情况中，合并都是在常数时间内完成的。

边界标记的概念是简单优雅的，它对许多不同类型的分配器和空闲链表组织都是通用的。然而，它也存在一个潜在的缺陷。它要求每个块都保持一个头部和一个脚部，在应用程序操作许多个小块时，会产生显著的内存开销。例如，如果一个图形应用通过反复调用 ma l l o c 和 fr e e 来动态地创建和销毁图形节点，并且每个图形节点都只要求两个内存字，那么头部和脚部将占用每个已分配块的一半的空间。

幸运的是，有一种非常聪明的边界标记的优化方法，能够使得在已分配块中不再需要脚部。回想一下，当我们试图在内存中合并当前块以及前面的块和后面的块时，只有在前面的块是空闲时，才会需要用到它的脚部。如果我们把前面块的巳分配／空闲位存放在当前块中多出来的低位中，那么巳分配的块就不需要脚部了，这样我们就可以将这个多出来的空间用作有效载荷了。不过请注意，空闲块仍然需要脚部。

练习题 9. 7 确定下面每种对齐要求和块格式的组合的最小的块大小。假设：隐式空闲链表，不允许有效载荷为零，头部和脚部存放在 4 字节的字中。

对齐要求	已分配的块	空闲块最小块大小（字节）
单字	头部和脚部	头部和脚部
单字	头部，但是无脚部	头部和脚部
双字	头部和脚部	头部和脚部
双字	头部，但是没有脚部	头部和脚部

9. 12 综合：实现一个简单的分配器
构造一个分配器是一件富有挑战性的任务。设计空间很大，有多种块格式、空闲链表格式，以及放置、分割和合并策略可供选择。另一个挑战就是你经常被迫在类型系统的安全和熟悉的限定之外编程，依赖于容易出错的指针强制类型转换和指针运算，这些操作都属千典型的低层系统编程。
虽然分配器不需要大量的代码，但是它们也还是细微而不可忽视的。熟悉诸如
C+ + 或者 Java 之类高级语言的学生通常在他们第一次遇到这种类型的编程时，会遭遇一个概念上的障碍。为了帮助你清除这个障碍，我们将基于隐式空闲链表，使用立即边界标记合并方式，从头至尾地讲述一个简单分配器的实现。最大的块大小为 232 = 4GB 。代码是 64 位干净的，即代码能不加修改地运行在 3 2 位( ge e - m3 2 ) 或 6 4 位( g e e - m6 4) 的
进程中。
1. 通用分配器设计
  我们的分配器使用如图 9-41 所示的 me ml i b . e 包所提供的一个内存系统模型。模型的目的在于允许我们在不干涉已存在的系统层 ma l l o e 包的情况下，运行分配器。
  me m_ i n i t 函数将对千堆来说可用的虚拟内存模型化为一个大的、双字对齐的字节数组。在 me m_ he a p 和 me m_ br k 之间的字节表示已分配的虚拟内存。me m_ br k 之后的字节表示未分配的虚拟内存。分配器通过调用 me m_ s br k 函数来请求额外的堆内存，这个函数和系统的 s br k 函数的接口相同，而且语义也相同，除了它会拒绝收缩堆的请求。
  ．分配器包含在一个源文件中( mm. e ) , 用户可以编译和链接这个源文件到他们的应用之中。分配器输出三个函数到应用程序：
  extern int mm_init(void);
  2 extern void *mm_malloc (size_t size);
  3 extern void mm_free (void *ptr);
  mm i n i t 函数初始化分配器，如果成功就返回 o, 否则就返回—1 o mm_ma l l o c 和 mm_ f r e e 函数与它们对应的系统函数有相同的接口和语义。分配器使用如图 9-39 所示的块格式。最小块的大小为 16 字节。空闲链表组织成为一个隐式空闲链表，具有如图 9-42 所示的恒定形式。
  第一个字是一个双字边界对齐的不使用的填充字。填充后面紧跟着一个特殊的序言块(prologue block) , 这是一个 8 字节的已分配块，只由一个头部和一个脚部组成。序言块是在初始化时创建的，并且永不释放。在序言块后紧跟的是零个或者多个由 ma l l o c 或者fr e e 调用创建的普通块。堆总是以一个特殊的结尾块( epilog ue block ) 来结束，这个块是一个大小为零的已分配块，只由一个头部组成。序言块和结尾块是一种消除合并时边界条件的技巧。分配器使用一个单独的私有( s t a t i c ) 全局变量( he a p _ 让 s t p ) , 它总是指向序言块。（作为一个小优化，我们可以让它指向下一个块，而不是这个序言块。）

code/vmlma llod memlib.c

I* Private global variables *I

static char *mem_heap; I* Points to first byte of heap *I
static char *mem_brk; I* Points to last byte of heap plus 1 *I
static char *mem_max_addr; I* Max legal heap addr plus 1*/
5
I*
* mem_init - Initialize the memory system model
s *I
9 void mem_init (void) 10 {
mem_heap = (char *)Malloc(MAX_HEAP);
mem_brk = (char *)mem_heap;
mem_max_addr = (char *)(mem_heap + MAX_HEAP); 14 }
15
I*
* mem_sbrk - Simple model of the sbrk function. Extends the heap
* by incr bytes and returns the start address of the new area. In
* this model, the heap cannot be shrunk.
*I
void *mem_sbrk(int incr) 22 {
23 cha 工 *ol d_br k = mem_brk;
24
if ((incr < 0) 11 ((mem_brk + incr) > mem_max_addr)) {
errno = ENOMEM;
fprintf(stderr, “ERROR: mem_sbrk failed. Ran out of memory … \n”);
return (void *)-1; 29 }
mem_brk += incr;
return (void *)old_brk; 32 }

code/vmlmal/odmemlib.c

图 9-41 memlib.c: 内存系统模型

序言块普通块 l

普通块2 普通块n 结尾块 hdr

！双字

！对齐的

static char *heap_listp

图9- 42 隐式空闲链表的恒定形式

2 操作空闲链表的基本常数和宏

图 9-43 展示了一些我们在分配器编码中将要使用的基本常数和宏。第 2 4 行定义了一些基本的大小常数：字的大小( WSIZE ) 和双字的大小( DSIZE ) , 初始空闲块的大小和扩展堆时的默认大小CCH UNKSIZE) 。

在空闲链表中操作头部和脚部可能是很麻烦的，因为它要求大量使用强制类型转换和指针运算。因此，我们发现定义一小组宏来访问和遍历空闲链表是很有帮助的（第9 25 行）。PACK

宏（第9 行）将大小和已分配位结合起来并返回一个值，可以把它存放在头部或者脚部中。

codelvmlmallodmm.c

I* Basic constants and macros *I

#define WSIZE 4 I* Word and header/footer size (bytes) *I
#define DSIZE 8 I* Double word size (bytes) *I
4 #define CHUNKSIZE (1«12) I* Extend heap by this amount (bytes) *I
5
6 #define MAX(x, y) ((x) > (y)? (x) : (y))
7
B I* Pack a size and allocated bit into a word *I
9 #define PACK(size, alloc) ((size) I (alloc))
10
11 I* Read and write a word at address p *I
12 #define GET(p) (*(unsigned int *)(p))
13 #define PUT(p, val) (*(unsigned int *) (p) = (val))
14
I* Read the size and allocated fields from address p *I
#define GET_SIZE(p) (GET(p) & -Ox7)
#define GET_ALLOC(p) (GET(p) & Ox1)
18
I* Given block ptr bp, compute address of its header and footer *I
#define HDRP(bp) ((char *) (bp) - WSIZE)
#define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)
22
23 I* Given block ptr bp, compute address of next and previous blocks *I
24 #define NEXT_BLKP(bp) ((char *) (bp) + GET_SIZE(((char *) (bp) - WSIZE)))
25 #define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *) (bp) - DSIZE)))

code/vm/ma llod mm.c

图 9- 43 操作空闲链表的基本常数和宏

GE T 宏（第1 2 行）读取和返回参数 p 引用的字。这里强制类型转换是至关重要的。参数 p 典型地是一个( v i o d * ) 指针，不可以直接进行间接引用。类似地， P U T 宏（第1 3 行）将 v a l 存放在参数 p 指向的字中。

G ET _S IZE 和 G E T _ A L L O C 宏（第1 6~ 17 行）从地址 p 处的头部或者脚部分别返回大小和巳分配位。剩下的宏是对块指针( blo ck pointer, 用bp 表示）的操作，块指针指向第一个有效载荷字节。给定一个块指针 b p , H DR P 和 F T R P 宏（第20 ~ 21 行）分别返回指向这个块的头部和脚部的指针。N E XT _BL K P 和 P R E V _ BL K P 宏（第24 ~ 25 行）分别返回指向后面的块和前面的块的块指针。

可以用多种方式来编辑宏，以操作空闲链表。比如，给定一个指向当前块的指针 b p ,

我们可以使用下面的代码行来确定内存中后面的块的大小：

size_t size= GET_SIZE(HDRP(NEXT_BLKP(bp)));

3. 创建初始空闲链表

在调用 mm_ ma l l o c 或者 mm_ fr e e 之前，应用必须通过调用 mm_ i n i t 函数来初始化堆

（见图9- 44 ) 。

mm_ i n i t 函数从内存系统得到 4 个字，并将它们初始化，创建一个空的空闲链表（第4

~ 10 行）。然后它调用 e x 七e n d _ h e a p 函数（图9- 45 ) , 这个函数将堆扩展 C H U N KSIZE 字

节，并且创建初始的空闲块。此刻，分配器已初始化了，并且准备好接受来自应用的分配和释放请求。

code/vm/mallodmm.c

int rnm_init(void)

｛

I* Create the initial empty heap *I

if ((heap_listp = mem_sbrk(4*WSIZE)) == (void *)-1) r et urn 一 1 ;

PUT(heap_listp, O);

PUT(heap_listp + O*WSIZE), PACK(DSIZE, 1)); PUT(heap_listp + (2*WSIZE), PACK(DSIZE, 1));

PUT(heap_listp + (3*WSIZE), PACK(O, 1)); heap_listp += (2*WSIZE);

I* Alignment padding *I I* Prologue header *I I* Prologue footer *I I* Epilogue header *I

I* Extend the empty heap with a free block of CHUNKSIZE bytes *I

if (extend_heap(CHUNKSIZE/WSIZE) == NULL) return -1;

return O;

图 9-44 mm_ini t: 创建带一个初始空闲块的堆

1 static void *extend_heap(size_t words)

2 {

3 char *bp; size_t size;

code/ vmlmallod mm.c codelvm/ma llod mm.c

6 I* Allocate an even number of words to maintain alignment *I

7 size= (words% 2)? (words+!) * WSI ZE : words* WSIZE;

8 if ((long) (bp = mem_sbrk(size)) == -1)

9 return NULL;

I* Initialize free block header/footer and the epilogue header *I
PUT(HDRP(bp), PACK(size, 0)); I* Free block header *I
PUT(FTRP(bp), PACK(size, O)); I* Free block footer *I
PUT(HDRP(NEXT_BLKP(bp)), PACK(O, 1)); I* New epilogue header*/
15
I* Coalesce if the previous block was free *I
return coalesce(bp);
18 }

codelvm/mallodmm.c

图 9-45 ext e nd_heap : 用一个新的空闲块扩展堆

e x 七e n d_ h e a p 函数会在两种不同的环境中被调用： 1 ) 当堆被初始化时； 2 ) 当 mm—ma l l a c 不能找到一个合适的匹配块时。为了保持对齐， e x 七e n d _ h e a p 将请求大小向上舍入为最接近的 2 字( 8 字节）的倍数，然后向内存系统请求额外的堆空间（第7 9 行）。

e x t e n d _ h e a p 函数的剩余部分（第12 17 行）有点儿微妙。堆开始于一个双字对齐的边界，并且每次对 e x t e nd _ he a p 的调用都返回一个块，该块的大小是双字的整数倍。因此，对 me m_ s br k 的每次调用都返回一个双字对齐的内存片，紧跟在结尾块的头部后面。这个头部变成了新的空闲块的头部（第12 行），并且这个片的最后一个字变成了新的结尾

块的头部（第14 行）。最后，在很可能出现的前一个堆以一个空闲块结束的情况中，我们调用 c o a l e s c e 函数来合并两个空闲块，并返回指向合并后的块的块指针（第1 7 行）。

4 释放和合并块

应用通过调用 mm_ fr e e 函数（图9-46) , 来释放一个以前分配的块，这个函数释放所请求的块( b p) , 然后使用 9. 9. 11 节中描述的边界标记合并技术将之与邻接的空闲块合并起来。

code/vm/mallodmm.c

1 void mm_free(void *bp)

2 {

3 size_t size= GET_SIZE(HDRP(bp));

5 PUT(HDRP(bp), PACK(size, O));

6 PUT(FTRP(bp), PACK(size, 0));

7 coalesce(bp);

8 }

10 static void *coalesce(void *bp)

11 {

12 size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp)));

13 size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));

14 size_t size= GET_SIZE(HDRP(bp));

if (prev_alloc && next_alloc) { I* Case 1 *I
return bp;
18 }
19
else if (prev_alloc && !next_alloc) { I* Case 2 *I
size += GET_SIZE (HDRP (NEXT_BLKP(bp))) ;
22 PUT(HDRP(bp), PACK(size, O));
23 PUT(FTRP(bp), PACK(size,O));
24 }
25
else if (!prev_alloc && next_alloc) { I* Case 3 *I
size += GET_SIZE(HDRP(PREV_BLKP(bp)));
PUT(FTRP(bp), PACK(size, 0));
PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
bp = PREV_BLKP(bp);
31 }
32
else { I* Case 4 *I
size+= GET_SIZE(HDRP(PREV_BLKP(bp))) +
GET_SIZE(FTRP(NEXT_BLKP(bp)));
PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
PUT(FTR 王）(NEXT_BLKP(bp)), PACK(size, O));
bp = PREV_BLKP(bp);
39 }
40 return bp;
41 }
code/vm/mallodmm.c
图 9-46 mm_free: 释放一个块，并使用边界标记合并将之与所有的邻接空闲块在常数时间内合并

c o a l e s c e 函数中的代码是图 9-40 中勾画的四种情况的一种简单直接的实现。这里也有一个微妙的方面。我们选择的空闲链表格式（它的序言块和结尾块总是标记为已分配）允许我们忽略潜在的麻烦边界情况，也就是，请求块 b p 在堆的起始处或者是在堆的结尾处。如果没有这些特殊块，代码将混乱得多，更加容易出错，并且更慢，因为我们将不得不在每次释放请求时，都去检查这些并不常见的边界情况。

5. 分配块

一个应用通过调用 mm_ma l l o c 函数（见图9-47 ) 来向内存请求大小为 s i z e 字节的块。在检查完请求的真假之后，分配器必须调整请求块的大小，从而为头部和脚部留有空间，并满足双字对齐的要求。第 12 13 行强制了最小块大小是 16 字节： 8 字节用来满足对齐要求，而另外 8 个用来放头部和脚部。对于超过 8 字节的请求（第15 行），一般的规则是加上开销字节，然后向上舍入到最接近的 8 的整数倍。

code/vmlmallodmm.c

void *mm_malloc(size_t size)

3		size_t asize; I* Adjusted block size *I
4		size_t extendsize; I* Amount to extend heap if no fit *I
5		char *bp;
7		I* Ignore spurious requests *I
8		if (size == 0)
		return NULL;
10
11		I* Adjust block size to include overhead and alignment reqs. *I
12		if (size <= DSIZE)
13		asize = 2*DSIZE;
14		else
15		asize = DSIZE * ((size + (DSIZE) + (DSIZE-1)) / DSIZE);
16
17		I* Se a 工 ch the free list for a fit *I
18		if ((bp = find_fit (asize)) != NULL) {
19		place(bp, asize);
20		return bp;
21
22
23		I* No fit found. Get more memory and place the block *I
24		extendsize = MAX(asize,CHUNKSIZE);
25		if ((bp = extend_heap(extendsize/WSIZE)) == NULL)
26		return NULL;
27		place(bp, asize);
28		return bp;
29	}
		code/v mlma llod mm.c
		图 9- 47 mm_malloc: 从空闲链表分配一个块

一旦分配器调整了请求的大小，它就会搜索空闲链表，寻找一个合适的空闲块（第18 行）。如果有合适的，那么分配器就放置这个请求块，并可选地分割出多余的部分（第19 行），然后返回新分配块的地址。

如果分配器不能够发现一个匹配的块，那么就用一个新的空闲块来扩展堆（第24 26 行），把请求块放置在这个新的空闲块里，可选地分割这个块（第27 行），然后返回一个指针，指向这个新分配的块。

练习题 9. 8 为 9. 9. 1 2 节中描述的简单分配器实现一个 f i n d _ 丘 t 函数。

static void *f i nd_fi t (s i ze_t a s i z e )

你的解答应该对隐式空闲链表执行首次适配搜索。

练习题 9. 9 为示例的分配器编写一个 p l a c e 函数。

s t a t i c v o i d p l a ce ( v o i d *bp, si ze_t as i ze)

你的解答应该将请求块放置在空闲块的起始位置，只有当剩余部分的大小等于或者超出最小块的大小时，才进行分割。

9. 13 显式空闲链表
隐式空闲链表为我们提供了一种介绍一些基本分配器概念的简单方法。然而，因为块分配与堆块的总数呈线性关系，所以对于通用的分配器，隐式空闲链表是不适合的（尽管对于堆块数最预先就知道是很小的特殊的分配器来说它是可以的）。
一种更好的方法是将空闲块组织为某种形式的显式数据结构。因为根据定义，程序不需要一个空闲块的主体，所以实现这个数据结构的指针可以存放在这些空闲块的主体里面。例如，堆可以组织成一个双向空闲链表，在每个空闲块中，都包含一个 pr e d ( 前驱）和 s uccC后继）指针，如图 9-48 所示。
31 3 2 I 0 31 3 2 1 0
头部头部

原来的有效载荷

脚部

a ) 分配块

脚部

b ) 空闲块

图 9-48 使用双向空闲链表的堆块的格式

使用双向链表而不是隐式空闲链表，使首次适配的分配时间从块总数的线性时间减少到了空闲块数量的线性时间。不过，释放一个块的时间可以是线性的，也可能是个常数，这取决于我们所选择的空闲链表中块的排序策略。

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

另一种方法是按照地址顺序来维护链表，其中链表中每个块的地址都小于它后继的地址。在这种情况下，释放一个块需要线性时间的搜索来定位合适的前驱。平衡点在于，按

照地址排序的首次适配比 LIFO 排序的首次适配有更高的内存利用率，接近最佳适配的利用率。

一般而言，显式链表的缺点是空闲块必须足够大，以包含所有需要的指针，以及头部和可能的脚部。这就导致了更大的最小块大小，也潜在地提高了内部碎片的程度。

9. 9. 14 分离的空闲链表

就像我们已经看到的，一个使用单向空闲块链表的分配器需要与空闲块数量呈线性关系的时间来分配块。一种流行的减少分配时间的方法，通常称为分离存储 ( s eg regated

storage), 就是维护多个空闲链表，其中每个链表中的块有大致相等的大小。一般的思路是将所有可能的块大小分成一些等价类，也叫做大小类 ( size clas s ) 。有很多种方式来定义大小类。例如，我们可以根据 2 的幕来划分块大小：

{1},{2},{3,4},{5 ~ 8},..·,{1025 ~ 2048},{2049 ~ 4096},{4097 ~ =}

或者我们可以将小的块分派到它们自己的大小类里，而将大块按照 2 的幕分类：

{1},{2},{3}, … , {1023}, {1024}, {1025 ~ 2048},{2049 ~ 4096 } , {4097 ~ =}

分配器维护着一个空闲链表数组，每个大小类一个空闲链表，按照大小的升序排列。当分配器需要一个大小为 n 的块时，它就搜索相应的空闲链表。如果不能找到合适的块与之匹配，它就搜索下一个链表，以此类推。

有关动态内存分配的文献描述了几十种分离存储方法，主要的区别在千它们如何定义大小类，何时进行合并，何时向操作系统请求额外的堆内存，是否允许分割，等等。为了使你大致了解有哪些可能性，我们会描述两种基本的方法：简单分离存储( sim ple segrega ted s to ra ge ) 和分离适配( segrega t ed fit ) 。

1 简单分离存储

使用简单分离存储，每个大小类的空闲链表包含大小相等的块，每个块的大小就是这个大小类中最大元索的大小。例如，如果某个大小类定义为{1 7 ~ 32} , 那么这个类的空闲

链表全由大小为 32 的块组成。

为了分配一个给定大小的块，我们检查相应的空闲链表。如果链表非空，我们简单地分配其中第一块的全部。空闲块是不会分割以满足分配请求的。如果链表为空，分配器就向操作系统请求一个固定大小的额外内存片（通常是页大小的整数倍），将这个片分成大小相等的块，并将这些块链接起来形成新的空闲链表。要释放一个块，分配器只要简单地将这个块插入到相应的空闲链表的前部。

这种简单的方法有许多优点。分配和释放块都是很快的常数时间操作。而且，每个片中都是大小相等的块，不分割，不合并，这意味着每个块只有很少的内存开销。由于每个片只有大小相同的块，那么一个已分配块的大小就可以从它的地址中推断出来。因为没有合并，所以已分配块的头部就不需要一个已分配／空闲标记。因此已分配块不需要头部，同时因为没有合并，它们也不需要脚部。因为分配和释放操作都是在空闲链表的起始处操作，所以链表只需要是单向的，而不用是双向的。关键点在于，在任何块中都需要的唯一字段是每个空闲块中的一个字的 su c c 指针，因此最小块大小就是一个字。

一个显著的缺点是，简单分离存储很容易造成内部和外部碎片。因为空闲块是不会被分割的，所以可能会造成内部碎片。更糟的是，因为不会合并空闲块，所以某些引用模式会引起极多的外部碎片（见练习题 9. 10 ) 。

练习题 9. 10 描述一个在基于简单分离存储的分配器中会导致严重外部碎片的引用模式。

分离适配
使用这种方法，分配器维护着一个空闲链表的数组。每个空闲链表是和一个大小类相关联的，并且被组织成某种类型的显式或隐式链表。每个链表包含潜在的大小不同的块，这些块的大小是大小类的成员。有许多种不同的分离适配分配器。这里，我们描述了一种简单的版本。
为了分配一个块，必须确定请求的大小类，并且对适当的空闲链表做首次适配，查找一个合适的块。如果找到了一个，那么就（可选地）分割它，并将剩余的部分插入到适当的空闲链表中。如果找不到合适的块，那么就搜索下一个更大的大小类的空闲链表。如此重复，直到找到一个合适的块。如果空闲链表中没有合适的块，那么就向操作系统请求额外的堆内存，从这个新的堆内存中分配出一个块，将剩余部分放置在适当的大小类中。要释放一个块，我们执行合并，并将结果放置到相应的空闲链表中。
分离适配方法是一种常见的选择， C 标准库中提供的 G N U rna ll o c 包就是采用的这种方法，因为这种方法既快速，对内存的使用也很有效率。搜索时间减少了，因为搜索被限制在堆的某个部分，而不是整个堆。内存利用率得到了改善，因为有一个有趣的事实：对分离空闲链表的简单的首次适配搜索，其内存利用率近似于对整个堆的最佳适配搜索的内存利用率。
1. 伙伴系统
  伙伴系统( buddy s ys tem ) 是分离适配的一种特例，其中每个大小类都是 2 的幕。基本的思路是假设一个堆的大小为沪个字，我们为每个块大小沪维护一个分离空闲链表，其中 O< k< m。请求块大小向上舍入到最接近的 2 的幕。最开始时，只有一个大小为沪个字的空闲块。
  为了分配一个大小为 2k 的块，我们找到第一个可用的、大小为 3 的块，其中 k< J < m。如果 j = k , 那么我们就完成了。否则，我们递归地二分割这个块，直到 j = k 。当我们进行这样的分割时，每个剩下的半块（也叫做伙伴）被放置在相应的空闲链表中。要释放一个大小为
  2k 的块，我们继续合并空闲的伙伴。当遇到一个巳分配的伙伴时，我们就停止合并。
  关千伙伴系统的一个关键事实是，给定地址和块的大小，很容易计算出它的伙伴的地址。例如，一个块，大小为 32 字节，地址为：
  XX X …x OOO OO

它的伙伴的地址为

XX X …x l OOOO

换句话说，一个块的地址和它的伙伴的地址只有一位不相同。

伙伴系统分配器的主要优点是它的快速搜索和快速合并。主要缺点是要求块大小为 2 的幕可能导致显著的内部碎片。因此，伙伴系统分配器不适合通用目的的工作负载。然而，对于某些特定应用的工作负载，其中块大小预先知道是 2 的幕，伙伴系统分配器就很有吸引力了。

9. 10 垃圾收集

在诸如 C rna l l oc 包这样的显式分配器中，应用通过调用 rna l l o c 和 fr e e 来分配和释放堆块。应用要负责释放所有不再需要的已分配块。

未能释放已分配的块是一种常见的编程错误。例如，考虑下面的 C 函数，作为处理的一部分，它分配一块临时存储：

void garbage()

｛

int *P = (int *)Malloc(15213);

return; I* Array pis garbage at this point *I

因为程序不再需要 p , 所以在 g ar b a g e 返回前应该释放 p。不幸的是，程序员忘了释放这个块。它在程序的生命周期内都保持为己分配状态，毫无必要地占用着本来可以用来满足后面分配请求的堆空间。

垃圾收集器 ( ga r bage coll ecto r ) 是一种动态内存分配器，它自动释放程序不再需要的已分配块。这些块被称为垃圾( ga r ba ge ) (因此术语就称之为垃圾收集器）。自动回收堆存储的过程叫做垃圾收集( ga r bage collection ) 。在一个支待垃圾收集的系统中，应用显式分配堆块，但是从不显示地释放它们。在 C 程序的上下文中，应用调用 ma l l o c , 但是从不调用 fr e e 。反之，垃圾收集器定期识别垃圾块，并相应地调用 fr e e , 将这些块放回到空闲链表中。

垃圾收集可以追溯到 J oh n M cCa r t h y 在 20 世纪 60 年代早期在 MIT 开发的 Lis p 系统。它是诸如 Java 、ML 、Perl 和 M a t hema tica 等现代语言系统的一个重要部分，而且它仍然是一个重要而活跃的研究领域。有关文献描述了大量的垃圾收集方法，其数量令人吃惊。我们的讨论局限于 McCa r t h y 独创的 Ma r k & S weep ( 标记＆清除）算法，这个算法很有趣，因为它可以建立在已存在的 ma l l o c 包的基础之上，为 C 和 C ++ 程序提供垃圾收集。

9. 10. 1 垃圾收集器的基本知识

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

，．

喻气 , ..

、. -.,’’-星.’.飞,•

图 9-49 垃圾收集器将内存视为一张有向图

当存在一条从任意根节点出发并到达 p 的有向路径时，我们说节点 p 是可达的( reacha ble ) 。在任何时刻，不可达节点对应千垃圾，是不能被应用再次使用的。垃圾收集器的角色是维护可达图的某种表示，并通过释放不可达节点且将它们返回给空闲链表，来定期地回收它们。

像 M L 和 J ava 这样的语言的垃圾收集器，对应用如何创建和使用指针有很严格的控制，能够维护可达图的一种精确的表示，因此也就能够回收所有垃圾。然而，诸如 C 和

C++ 这样的语言的收集器通常不能维持可达图的精确表示。这样的收集器也叫做保守的垃圾收集器 ( co nse r va tive garbage collector) 。从某种意义上来说它们是保守的，即每个可达块都被正确地标记为可达了，而一些不可达节点却可能被错误地标记为可达。

收集器可以按需提供它们的服务，或者它们可以作为一个和应用并行的独立线程，不断地更新可达图和回收垃圾。例如，考虑如何将一个 C 程序的保守的收集器加入到已存在的 ma l l o c 包中，如图 9- 50 所示。

动态内存分配器

! ,——–, #

一一1

- - - - – - - – - - – – - - – - - - – - - - - – - - – - - - - - – - - – - - - - – - - - – - - – – – – - - J

图 9-50 将一个保守的垃圾收集器加入到 C 的 ma l l oc 包中

无论何时需要堆空间时，应用都会用通常的方式调用 ma l l o c 。如果 ma l l o c 找不到一个合适的空闲块，那么它就调用垃圾收集器，希望能够回收一些垃圾到空闲链表。收集器识别出垃圾块，并通过调用 fr e e 函数将它们返回给堆。关键的思想是收集器代替应用去调用 f r e e 。当对收集器的调用返回时， ma l l o c 重试，试图发现一个合适的空闲块。如果还是失败了，那么它就会向操作系统要求额外的内存。最后， ma l l o c 返回一个指向请求块的指针（如果成功）或者返回一个空指针（如果不成功）。

10. 2 Mark & Sweep 垃圾收集器
Mark &.Sw ee p 垃圾收集器由标记 ( ma r k ) 阶段和清除 ( sweep ) 阶段组成，标记阶段标记出根节点的所有可达的和已分配的后继，而后面的清除阶段释放每个未被标记的已分配块。块头部中空闲的低位中的一位通常用来表示这个块是否被标记了。
我们对 Mark &.Swee p 的描述将假设使用下列函数，其中 ptr 定义为t ype de f void *p七r :
•• ptr i s P七r (ptr p) 。如果 p 指向一个巳分配块中的某个字，那么就返回一个指向这个块的起始位置的指针 b。否则返回 NU L L 。
- int blockMarked (ptr b) 。如果块 b 是已标记的，那么就返回 tr ue 。
- i n七 b l o c kA ll o c a t e d (ptr b) 。如果块 b 是已分配的，那么就返回 tr ue 。
- void markBlock (p 七r b ) 。标记块 b。
- int length (b ) 。返回块 b 的以字为单位的长度（不包括头部）。
- void unmarkBlock (ptr b) 。将块 b 的状态由己标记的改为未标记的。
- ptr ne x 七Bl o c k (p 七r b ) 。返回堆中块 b 的后继。
  标记阶段为每个根节点调用一次图 9-Sl a 所示的 mar k 函数。如果 p 不指向一个已分配并且未标记的堆块， mar k 函数就立即返回。否则，它就标记这个块，并对块中的每个字递归地调用它自己。每次对 mar k 函数的调用都标记某个根节点的所有未标记并且可达的后继节点。在标记阶段的末尾，任何未标记的已分配块都被认定为是不可达的，是垃圾，可以在清除阶段回收。
  清除阶段是对图 9-51 6 所示的 s we e p 函数的一次调用。s we e p 函数在堆中每个块上反复循环，释放它所遇到的所有未标记的已分配块（也就是垃圾）。
  图 9-52 展示了一个小堆的 Mark &.Sweep 的图形化解释。块边界用粗线条表示。每个方
  块对应于内存中的一个字。每个块有一个字的头部，要么是已标记的，要么是未标记的。

void mark(ptr p) {

if ((b = isPtr(p)) == NULL) return;

if (blockMarked(b))

return; markBlock(b);

len = length(b);

for (i=O; i < len; i++) mark (b [i]) ;

return;

void sweep(ptr b, ptr end) { while (b < end) {

if (blockMarked(b)) unmarkBlock(b);

else if (blockAllocated(b)) free(b);

b = nextBlock(b);

｝

return;

｝

a) mar k 函数 b ) s we e p 函数

图 9-51 ma r k 和 s we ep 函数的伪代码

标记前：

根节点

1 2 3 4 i 5

标记后：

久七:,

口未标记的块头部口巳标记的块头部

清除后： I 全闲

空闲的

图 9-52 Mark &.S weep 示例。注意这个示例中的箭头表示内存引用，而不是空闲链表指针

初始情况下，图 9-52 中的堆由六个已分配块组成，其中每个块都是未分配的。第 3

块包含一个指向第 1 块的指针。第 4 块包含指向第 3 块和第 6 块的指针。根指向第 4 块。

在标记阶段之后，第 1 块、第 3 块、第 4 块和第 6 块被做了标记，因为它们是从根节点可达的。第 2 块和第 5 块是未标记的，因为它们是不可达的。在清除阶段之后，这两个不可达块被回收到空闲链表。

9. 10. 3 C 程序的保守 Ma rk & Sweep

Mark&Sweep对 C 程序的垃圾收集是一种合适的方法，因为它可以就地工作，而不需要移动任何块。然而， C 语言为 i s Ptr 函数的实现造成了一些有趣的挑战。

第一， C 不会用任何类型信息来标记内存位置。因此，对 i s Ptr 没有一种明显的方式来判断它的输入参数 p 是不是一个指针。第二，即使我们知道 p 是一个指针，对 i s Pt r 也没有明显的方式来判断 p 是否指向一个已分配块的有效载荷中的某个位置。

对后一问题的解决方法是将已分配块集合维护成一棵平衡二叉树，这棵树保持着这样一个属性：左子树中的所有块都放在较小的地址处，而右子树中的所有块都放在较大的地址处。如图 9-53 所示，这就要求每个已分配块的头部里有两个附加字段Cl e 红和 r i ght )。每个字段指向某个巳分配块的头部。i s Ptr (ptr p)函数用树来执行对已分配块的二分查找。在每一步中，它依赖于块头部中的大小字段来判断 p 是否落在这个块的范围之内。

三＞块剩余的部分

图 9-53 一棵已分配块的平衡树中的左右指针

平衡树方法保证会标记所有从根节点可达的节点，从这个意义上来说它是正确的。这是一个必要的保证，因为应用程序的用户当然不会喜欢把他们的已分配块过早地返回给空闲链表。然而，这种方法从某种意义上而言又是保守的，因为它可能不正确地标记实际上不可达的块，因此它可能不会释放某些垃圾。虽然这并不影响应用程序的正确性，但是这可能导致不必要的外部碎片。

C 程序的 Mar k &. S weep 收集器必须是保守的，其根本原因是 C 语言不会用类型信息来标记内存位置。因此，像 i n t 或者 f l oa t 这样的标量可以伪装成指针。例如，假设某个可达的巳分配块在它的有效载荷中包含一个 i nt , 其值碰巧对应于某个其他已分配块 b 的有效载荷中的一个地址。对收集器而言，是没有办法推断出这个数据实际上是 i n t 而不是指针。因此，分配器必须保守地将块 b 标记为可达，尽管事实上它可能是不可达的。

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

对 C 程序员来说，管理和使用虚拟内存可能是个困难的、容易出错的任务。与内存有关的错误属于那些最令人惊恐的错误，因为它们在时间和空间上，经常在距错误源一段距离之后才表现出来。将错误的数据写到错误的位置，你的程序可能在最终失败之前运行了好几个小时，且使程序中止的位置距离错误的位置已经很远了。我们用一些常见的与内存有关错误的讨论，来结束对虚拟内存的讨论。

9. 11. 1 间接引用坏指针

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

间接引用坏指针的一个常见示例是经典的 s c a n f 错误。假设我们想要使用 s c a n f 从

s t d i n 读一个整数到一个变量。正确的方法是传递给 s c a n f 一个格式串和变量的地址：

scanf(“¼d”, &val)

然而，对于 C 程序员初学者而言（对有经验者也是如此！），很容易传递 v a l 的内容，而不是它的地址：

s canf ( “1 儿 d” , val)

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

9. 11 . 2 读未初始化的内存

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

I* Return y = Ax *I

int *matvec(int **A, int *x,

｛

int n)

int l., j;

int *Y = (int *)Malloc(n * sizeof(int));

for (i = O; i < n; i++)

for (j = O; j < n; j++) y[i] += A[i] [j] * x[j];

return y;

在这个示例中，程序员不正确地假设向量 y 被初始化为零。正确的实现方式是显式地将

y [ i ]设置为零，或者使用 c a l l o c 。

9. 11. 3 允许栈缓冲区溢出

正如我们在 3. 10. 3 节中看到的，如果一个程序不检查输入串的大小就写入栈中的目标缓冲区，那么这个程序就会有缓冲区溢出错误( b uff e r overflow bug ) 。例如，下面的函数就有缓冲区溢出错误，因为 g e t s 函数复制一个任意长度的串到缓冲区。为了纠正这个错误，我们必须使用 f g e t s 函数，这个函数限制了输入串的大小：

void bufoverflow()

｛

char buf[64];

gets(buf); I* Here is the stack buffer overflow bug *I return;

9. 11. 4 假设指针和它们指向的对象是相同大小的

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

f* Create an nxm array *f

int **makeArrayl(int n, int m)

｛

int i;

int **A= (int **)Malloc(n * sizeof(int));

for (i “‘0; i < n; i ++)

A[i] “’(int•)Malloc(m * sizeof(int)); return A;

这里的目的是创建一个由 n 个指针组成的数组，每个指针都指向一个包含 m 个 i nt 的数组。然而，因为程序员在第 5 行将 s i z e o f (int *)写成了江ze o f (int), 代码实际上创建的是一个 i n 七的数组。

这段代码只有在 i n t 和指向 i n t 的指针大小相同的机器上运行良好。但是，如果我们在像 Core i7 这样的机器上运行这段代码，其中指针大于 i nt , 那么第 7 行和第 8 行的循环将

写到超出 A 数组结尾的地方。因为这些字中的一个很可能是已分配块的边界标记脚部，所以我们可能不会发现这个错误，直到在这个程序的后面很久释放这个块时，此时，分配器中的合并代码会戏剧性地失败，而没有任何明显的原因。这是“在远处起作用 ( actio n at dis tance)” 的一个阴险的示例，这类 ”在远处起作用” 是与内存有关的编程错误的典型情况。

9. 11. 5 造成错位错误

错位(off- by-one)错误是另一种很常见的造成覆盖错误的来源： I* Create an nxm array *I

2 int **makeArray2(int n, int m)

3 {

4 int i;

5 int **A= (int **)Malloc(n * sizeof(int *));

7 for (i = 0; i <= n; i ++)

8 A[i] = (int *)Malloc(m * sizeof(int)); return A;

10 }

这是前面一节中程序的另一个版本。这里我们在第 5 行创建了一个 n 个元素的指针数组，但是随后在第 7 行和第 8 行试图初始化这个数组的 n + l 个元素，在这个过程中覆盖了 A 数组后面的某个内存位置。

9. 11. 6 引用指针，而不是它所指向的对象

如果不太注意 C 操作符的优先级和结合性，我们就会错误地操作指针，而不是指针所指向的对象。比如，考虑下面的函数，其目的是删除一个有 *s i z e 项的二叉堆里的第一项，然后对剩下的 *s i z e - 1 项重新建堆：

int *binheapDelete(int **binheap, int *Size)

3 int *packet= binheap[O];

5 binheap[O] = binheap[*size - 1];

6 *size–; I* This should be (*size)– *I

heapify(binheap, *size, 0);
return(packet);

在第 6 行，目的是减少 s i z e 指针指向的整数的值。然而，因为一元运算符－－和＊的优先级相同，从右向左结合，所以第 6 行中的代码实际减少的是指针自己的值，而不是它所指向的整数的值。如果幸运地话，程序会立即失败；但是更有可能发生的是，当程序在执行过程后很久才产生出一个不正确的结果时，我们只有一头的雾水。这里的原则是当你对优先级和结合性有疑问的时候，就使用括号。比如，在第 6 行，我们可以使用表达式(*s i ze ) 一一，清晰地表明我们的意图。

9. 11. 7 误解指针运算

另一种常见的错误是忘记了指针的算术操作是以它们指向的对象的大小为单位来进行的，而这种大小单位并不一定是字节。例如，下面函数的目的是扫描一个 i n t 的数组，并

返回一个指针，指向 v a l 的首次出现：

int *Search(int *P, int val)

｛

while (*p && *P != val)

p += sizeof(int); I* Should be p++ *I return p;

｝

然而，因为每次循环时，第 4 行都把指针加了 4 ( 一个整数的字节数），函数就不正确地扫描数组中每 4 个整数。

9. 11. 8 引用不存在的变量

没有太多经验的 C 程序员不理解栈的规则，有时会引用不再合法的本地变量，如下列所示：

int *stackref 0

｛

int val; return &val;

这个函数返回一个指针（比如说是 p ) , 指向栈里的一个局部变量，然后弹出它的栈帧。尽管 p 仍然指向一个合法的内存地址，但是它已经不再指向一个合法的变量了。当以后在程序中调用其他函数时，内存将重用它们的栈帧。再后来，如果程序分配某个值给

*p, 那么它可能实际上正在修改另一个函数的栈帧中的一个条目，从而潜在地带来灾难性的、令人困惑的后果。

9. 11. 9 引用空闲堆块中的数据

一个相似的错误是引用已经被释放了的堆块中的数据。例如，考虑下面的示例，这个示例在第 6 行分配了一个整数数组x , 在第 10 行中先释放了块x , 然后在第14 行中又引用了它：

int *heapref (int n, int m)

｛

int i;

int *X, *y;

x = (int *)Malloc(n * sizeof(int));

IIOther calls to mal/oc and free go here

free(x);

y = (int *)Malloc(m * sizeof(int));

for

(i = O; i < m; i++)

y[i] = x[i]++; I* Oops! x[i] is a word in a free block *I

return y;

取决千在第 6 行和第 10 行发生的 ma l l o c 和 fr e e 的调用模式，当程序在第 1 4 行引用x [ i ] 时，数组 x 可能是某个其他巳分配堆块的一部分了，因此其内容被重写了。和其他许多与内存有关的错误一样，这个错误只会在程序执行的后面，当我们注意到 y 中的值被破坏了时才会显现出来。

9. 11. 10 引起内存泄漏

内存泄漏是缓慢、隐性的杀手，当程序员不小心忘记释放巳分配块，而在堆里创建了垃圾时，会发生这种问题。例如，下面的函数分配了一个堆块 x , 然后不释放它就返回：

void leak(int n)

｛

int *X = (int *)Malloc(n * sizeof(int)); return; I* xis garbage at this point *I

如果经常调用 l e a k , 那么渐渐地，堆里就会充满了垃圾，最糟糕的情况下，会占用整个虚拟地址空间。对于像守护进程和服务器这样的程序来说，内存泄漏是特别严重的，根据定义这些程序是不会终止的。

12 小结
虚拟内存是对主存的一个抽象。支待虚拟内存的处理器通过使用一种叫做虚拟寻址的间接形式来引用主存。处理器产生一个虚拟地址，在被发送到主存之前，这个地址被翻译成一个物理地址。从虚拟地址空间到物理地址空间的地址翻译要求硬件和软件紧密合作。专门的硬件通过使用页表来翻译虚拟地址，而页表的内容是由操作系统提供的。
虚拟内存提供三个重要的功能。第一，它在主存中自动缓存最近使用的存放磁盘上的虚拟地址空间的内容。虚拟内存缓存中的块叫做页。对磁盘上页的引用会触发缺页，缺页将控制转移到操作系统中的一个缺页处理程序。缺页处理程序将页面从磁盘复制到主存缓存，如果必要，将写回被驱逐的页。第二，虚拟内存简化了内存管理，进而又简化了链接、在进程间共享数据、进程的内存分配以及程序加载。最后，虚拟内存通过在每条页表条目中加入保护位，从而了简化了内存保护。
地址翻译的过程必须和系统中所有的硬件缓存的操作集成在一起。大多数页表条目位于 Ll 高速缓存中，但是一个称为 T LB 的页表条目的片上高速缓存，通常会消除访问在 Ll 上的页表条目的开销。
现代系统通过将虚拟内存片和磁盘上的文件片关联起来，来初始化虚拟内存片，这个过程称为内存映射。内存映射为共享数据、创建新的进程以及加载程序提供了一种高效的机制。应用可以使用 mmap 函数来手工地创建和删除虚拟地址空间的区域。然而，大多数程序依赖于动态内存分配器，例如 ma l l oc , 它管理虚拟地址空间区域内一个称为堆的区域。动态内存分配器是一个感觉像系统级程序的应用级程序，它直接操作内存，而无需类型系统的很多帮助。分配器有两种类型。显式分配器要求应用显式地释放它们的内存块。隐式分配器（垃圾收集器）自动释放任何未使用的和不可达的块。
对千 C 程序员来说，管理和使用虚拟内存是一件困难和容易出错的任务。常见的错误示例包括：间接引用坏指针，读取未初始化的内存，允许栈缓冲区溢出，假设指针和它们指向的对象大小相同，引用指针而不是它所指向的对象，误解指针运算，引用不存在的变量，以及引起内存泄湍。

参考文献说明

Kilburn 和他的同事们发表了第一篇关于虚拟内存的描述[ 63] 。体系结构教科书包括关千硬件在虚拟内存中的角色的更多细节[ 46] 。操作系统教科书包含关千操作系统角色的更多信息[ 102 , 106, 113] 。

Bovet 和 Cesati [ 11] 给出了 Linu x 虚拟内存系统的详细描述。Intel 公司提供了 IA 处理器上 32 位和 64 位

地址翻译的详细文档 [ 52]。

Knuth 在 1968 年编写了有关内存分配的经典之作[ 64] 。从那以后，在这个领域就有了大量的文献。

Wilson、Johnstone 、Neely 和 Boles 编写了一篇关于显式分配器的漂亮综述和性能评价的文章[ 118] 。本书中关千各种分配器策略的吞吐率和利用率的一般评价就引自千他们的调查。Jones 和 Lins 提供了关于垃圾收集的全面综述[ 56] 。Kern ighan 和 Rit chie [ 61] 展示了一个简单分配器的完整代码，这个简单的分配器是基千显式空闲链表的，每个空闲块中都有一个块大小和后继指针。这段代码使用联合( union ) 来消除大量的复杂指针运算，这是很有趣的，但是代价是释放操作是线性时间（而不是常数时间）。Doug Lea 开发了广泛使用的开源 malloc 包，称为 dl ma ll oc [ 67 ] 。

家庭作业

9. 11
在下面的一系列间题中，你要展示 9. 6. 4 节中的示例内存系统如何将虚拟地址翻译成物理地址，以及如何访问缓存。对于给定的虚拟地址，请指出访问的 T LB 条目、物理地址，以及返回的缓存字节值。请指明是否 T LB 不命中，是否发生了缺页，是否发生了缓存不命中。如果有缓存不命中，对千＂返回的缓存字节”用”-“来表示。如果有缺页，对千” PP N" 用"-“来表示，而 C 部分和 D 部分就空着。
虚拟地址： Ox027c

虚拟地址格式
地址翻译
3 12 JI 10 9 8 7 6 5 4 3
I 仁勹
物理地址格式
物理地址引用

11 10

仁工二］ #

9 8 7 6 5 4 3 2 1 0

I I I I I I I I I I

9. 12
对于下面的地址，重复习题 9. 11:
虚拟地址： Ox03a9

虚拟地址格式

13 12 II 10 9 8 7 6 5 4 3 2 I 0

地址翻译

c. 物理地址格式

11 10 9 8 7 6 5 4 3 2 I 0

D. 物理地址引用

9 13 对于下面的地址，重复习题 9. 11:
虚拟地址： Ox 00 40

虚拟地址格式
13 12 l l 10 9 8 7 6 5 4 3 2 I 0
地址翻译

参数	值
VPN
TLB 索引
TLB 标记
TLB 命中？（是 I 否）
缺页？（是 I 否）
PPN

物理地址格式

11 10 9 8 7 6 5 4 3 2 1 0

物理地址引用

•• 9. 14 假设有一个输入文件 he l l o . t x t , 由字符串” He l l o , world! \ n"组成，编写一个 C 程序，使用

mma p 将 he ll o . t 江的内容改变为" J e l l o , wor l d ! \ n" 。

9. 15 确定下面的 ma l l oc 请求序列得到的块大小和头部值。假设： 1) 分配器保持双字对齐，使用隐式空闲链表，以及图 9-35 中的块格式。2) 块大小向上舍入为最接近的 8 字节的倍数。
- 9. 16 确定下面对齐要求和块格式的每个组合的最小块大小。假设：显式空闲链表、每个空闲块中有四字节的 pr e d 和 s uc c 指针、不允许有效载荷的大小为零，并且头部和脚部存放在一个四字节的字中。

对齐要求	已分配块	空闲块最小块大小（字节）
单字	头部和脚部	头部和脚部
单字	头部，但是没有脚部	头部和脚部
双字	头部和脚部	头部和脚部
双字	头部，但是没有脚部	头部和脚部

*.* 9. 17 开发 9. 9. 12 节中的分配器的一个版本，执行下一次适配搜索，而不是首次适配搜索。

•: 9. 18 9. 9. 12 节中的分配器要求每个块既有头部也有脚部，以实现常数时间的合并。修改分配器，使得空闲块需要头部和脚部，而已分配块只需要头部。

9. 19 下面给出了三组关于内存管理和垃圾收集的陈述。在每一组中，只有一句陈述是正确的。你的任务就是判断哪一句是正确的。
1. a ) 在一个伙伴系统中，最高可达 50 %的空间可以因为内部碎片而被浪费了。
  b ) 首次适配内存分配算法比最佳适配算法要慢一些（平均而言）。
  c ) 只有当空闲链表按照内存地址递增排序时，使用边界标记来回收才会快速。
  d ) 伙伴系统只会有内部碎片，而不会有外部碎片。
2. a ) 在按照块大小递减顺序排序的空闲链表上，使用首次适配算法会导致分配性能很低，但是可以避免外部碎片。
  b ) 对于最佳适配方法，空闲块链表应该按照内存地址的递增顺序排序。
  c ) 最佳适配方法选择与请求段匹配的最大的空闲块。
  d ) 在按照块大小递增的顺序排序的空闲链表上，使用首次适配算法与使用最佳适配算法等价。
3. M ark & Sweep 垃圾收集器在下列哪种情况下叫做保守的：
  a ) 它们只有在内存请求不能被满足时才合并被释放的内存。

) 它们把一切看起来像指针的东西都当做指针。
) 它们只在内存用尽时，才执行垃圾收集。
) 它们不释放形成循环链表的内存块。

:: 9. 20 编写你自己的 ma l l oc 和 fr e e 版本，将它的运行时间和空间利用率与标准 C 库提供的 ma l l oc 版本进行比较。

练习题答案

9. 1 这道题让你对不同地址空间的大小有了些了解。曾儿何时，一个 32 位地址空间看上去似乎是无法想象的大。但是，现在有些数据库和科学应用需要更大的地址空间，而且你会发现这种趋势会继续。在有生之年，你可能会抱怨个人电脑上那狭促的 64 位地址空间！

虚拟地址位数( n	)	虚拟地址数( N)
8	z8=256	2’-1 =255
16	i16= 64K	2'6- I =64K-1
32	232= 4G	232- I =4G- l
48	248= 256T	248 - l = 256T- l
64	264 = 16 384P	264 - I= 16 384P-1

9. 2 因为每个虚拟页面是 P = 沪字节，所以在系统中总共有 2勹沪= 2-“p 个可能的页面，其中每个都需要一个页表条目 ( PT E) 。

n	P=2p	PTE的数量
16	4K	16
16	8K	8
32	4K	IM
32	8K	512K

9. 3 为了完全掌握地址翻译，你需要很好地理解这类问题。下面是如何解决第一个子问题：我们有 n =

32 个虚拟地址位和 m = 24 个物理地址位。页面大小是 P = l KB, 这意味着对于 VPO 和 PPO , 我们都需要 log2 OK)= 10 位。（回想一下， VPO 和 PPO 是相同的。）剩下的地址位分别是 V PN 和 PP N。

p	VPN位数	VPO位数	PPN位数	PPO位数
IKB	22	10	14	10
2KB	21	11	13	11
4KB	20	12	12	12
8KB	19	13	11	13

9. 4 做一些这样的手工模拟，能很好地巩固你对地址翻译的理解。你会发现写出地址中的所有的位，然后在不同的位字段上画出方框，例如 VP N、T LBI 等，这会很有帮助。在这个特殊的练习中，没有任何类型的不命中： T LB 有一份 PT E 的副本，而缓存有一份所请求数据字的副本。对于命中和不命中的一些不同的组合，请参见习题 9. 11 、9. 12 和 9. 13 。

A. 00 0011 1101 0111

C. OOll 0101 Olll

9. 5 解决这个题目将帮助你很好地理解内存映射。请自己独立完成这道题。我们没有讨论 o pe n 、f s t a t

或者 wr i t e 函数，所以你需要阅读它们的帮助页来看看它们是如何工作的。

pcopy.c

code/vmlmmapcopy.c

9. 6 这道题触及了一些核心的概念，例如对齐要求、最小块大小以及头部编码。确定块大小的一般方法是，将所请求的有效载荷和头部大小的和舍入到对齐要求（在此例中是 8 字节）最近的整数倍。比如， ma ll o c (1 ) 请求的块大小是 4 + 1 = 5 , 然后舍入到 8 。而 ma ll o c ( 13 ) 请求的块大小是 13 + 4 = 17, 舍入到 24 。

请求	块大小（十进制字节）	块头部（十六进制）
malloc (1)	8	Ox9
malloc ( 5 )	16	Oxll
malloc (12)	16	Ox ll
ma ll o c (13)	24	Ox 1 9

9. 7 最小块大小对内部碎片有显著的影响。因此，理解和不同分配器设计和对齐要求相关联的最小块大小是很好的。很有技巧的一部分是，要意识到相同的块可以在不同时刻被分配或者被释放。因此，最小块大小就是最小已分配块大小和最小空闲块大小两者的最大值。例如，在最后一个子问题中，

最小的已分配块大小是一个 4 字节头部和一个 1 字节有效载荷，舍人到 8 字节。而最小空闲块的大小是一个 4 字节的头部和一个 4 字节的脚部，加起来是 8 字节，已经是 8 的倍数，就不需要再舍入了。所以，这个分配器的最小块大小就是 8 字节。

对齐要求	已分配块	空闲块	最小块大小（字节）
单字	头部和脚部	头部和脚部	12
单字	头部，但是没有脚部	头部和脚部	8
双字	头部和脚部	头部和脚部	16
双字	头部，但是没有脚部	头部和脚部	8

9. 8 这里没有特别的技巧。但是解答此题要求你理解简单的隐式链表分配器的剩余部分是如何工作的，是如何操作和遍历块的。

codelv mlmallod mm .c

static void *find_fit(size_t asize)

2 {

3 I* First-fit search *I

4 void *bp;

for (bp = heap_listp; GET_SIZE(HDRP(bp)) > O; bp = NEXT_BLKP(bp)) {
if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp)))) {
return bp;
9 }
10 }
return NULL; I* No fit *I
#endif
13 }
code/vmlmallod mm .c
9. 9 这又是一个帮助你熟悉分配器的热身练习。注意对于这个分配器，最小块大小是 16 字节。如果分割后剩下的块大于或者等于最小块大小，那么我们就分割这个块（第 6~ 10 行）。这里唯一有技巧的部分是要意识到在移动到下一块之前（第8 行），你必须放置新的已分配块（第 6 行和第 7 行）。
code/vmlmallodmm.c
1 static void place(void *bp, size_t asize)
2 {
3 size_t csize = GET_SIZE(HDRP(bp));
4
if ((csize - asize) >= (2*DSIZE)) {
PUT(HDRP(bp), PACK(asize, 1));
PUT(FTRP(bp), PACK(asize, 1));
s bp= NEXT_BLKP(bp);
PUT(HDRP(bp), PACK(csize-asize, O));
PUT(ITRP(bp), PACK(csize-asize, O)); 11 }
else {
PUT(HDRP(bp), PACK(csize, 1));
PUT(FTRP(bp), PACK(csize, 1));
15 }
16 }
code/vm/mallod mm.c
9. 10 这里有一个会引起外部碎片的模式：应用对第一个大小类做大员的分配和释放请求，然后对第二个大小类做大鼠的分配和释放请求，接下来是对第三个大小类做大量的分配和释放请求，以此类推。对于每个大小类，分配器都创建了许多不会被回收的存储器，因为分配器不会合并，也因为应用不会再向这个大小类再次请求块了。