《深入理解计算机系统》学习笔记——虚拟内存虚拟内存

虚拟内存

虚拟内存是硬件异常、硬件地址翻译、主存、磁盘文件和内核软件的完美交互，它为每个进程提供了一个大的、一致的和私有的地址空间。

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

程序员需要理解虚拟内存的原因：

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

物理和虚拟内存

计算机系统的主存被组织成一个由M个连续的字节大小的单元组成的数组。每个字节都有一个唯一的物理地址（Physical Address, PA）。

CPU访问内存的最自然的方式就是使用物理地址，称为物理寻址（physical addressing）。

使用虚拟寻址，CPU通过生成一个虚拟地址（Virtual Address, VA）来访问主存，这个虚拟地址在被送到内存之前先转换成适当的物理地址。
将一个虚拟地址转换成物理地址的任务叫做地址翻译（address teanslation）。

CPU芯片上叫做内存管理单元（Memory Management Unit, MMU）的专用硬件，利用存放在主存中的查询表来动态翻译虚拟地址，该表的内容由操作系统管理。

地址空间

地址空间（address space）是一个非负整数地址的有序集合：

{0,1,2,...}

如果地址空间中的整数是连续的，那么它是一个线性地址空间（linear address space）。

在一个带虚拟内存的系统中，CPU从一个有 N=$2^n$个地址的地址空间中生成虚拟地址，这个地址空间称为虚拟地址空间（virtual address space）：

{0,1,2,...,N-1}

一个地址空间的大小是由表示最大地址所需要的位数来描述的。

一个系统还有一个物理地址空间（physical address space），对应于系统中物理内存的M个字节：

{0,1,2,...,M-1}

虚拟内存的基本思想：允许每个数据对象有多个独立的地址，其中每个地址都选自一个不同的地址空间。

主存中的每个字节都有一个选自虚拟地址空间的虚拟地址和一个选自物理地址空间的物理地址。

虚拟内存作为缓存的工具

VM系统通过将虚拟内存分割为称为虚拟页（Virtual Page, VP）的大小固定的块来处理这个问题。每个虚拟页的大小为 P=$2^p$字节。
物理内存被分割为物理页（Physical Page, PP），大小也为P字节（物理页也被称为页帧（page frame））。

虚拟页面的集合都分为三个不相交的子集：

• 未分配的： VM系统还未分配（或者创建）的页。
• 缓存的： 当前已缓存在物理内存中的已分配页。
• 未缓存的： 未缓存在物理内存中的已分配页。

DRAM缓存的组织结构

SRAM缓存表示位于CPU和主存之间的L1、L2和L3高速缓存；
DRAM缓存表示虚拟内存系统的缓存，它在主存中缓存虚拟页。

DRAM缓存的组织结构完全是由巨大的不命中开销驱动的。

DRAM缓存总是使用写回，而不是直写。

页表

操作系统软件、MMU（内存管理单元）中的地址翻译硬件和一个存放在物理内存中叫做页表（page table）的数据结构，页表将虚拟页映射到物理页。

每次地址翻译硬件将一个虚拟地址转换为物理地址时，都会读取页表。

操作系统负责维护页表的内容，以及在磁盘与DRAM之间来回传送页。

页表就是一个页表条目（Page Table Entry, PTE）的数组。
虚拟地址空间中的每个页在页表中一个固定偏移量处都有一个PTE。

页命中

缺页

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

页从磁盘换入（或者页面调入）DRAM和从DRAM换出（或者页面调出）磁盘。一直等待，指代最后时刻，也就是当有不命中发生时，才换入页面的这种策略称为按需页面调度（demand paging）。

分配页面

又是局部性救了我们

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

如果工作集的大小超出了物理内存的大小，那么程序将产生一种不幸的状态，叫做抖动（thrashing），这时页面将不断地换进换出。

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

虚拟地址仍然是一个有用的机制，因为它大大地简化了内存管理，并提供了一种自然的保护内存的方法。

VM简化了链接和加载、代码和数据共享，以及应用程序的内存分配。

• 简化链接。 独立的地址空间允许每个进程的内存映像使用相同的基本格式，而不管代码和数据实际存放在物理内存的何处。
• 简化加载。 虚拟内存还使得容易向内存加载可执行文件和共享对象文件。
• 简化共享。 独立地址空间为操作系统提供了一个管理用户进程和操作系统自身之间共享的一致机制。
• 简化内存分配。 虚拟内存为向用户进程提供一个简单的分配额外内存的机制。

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

地址翻译

形式上，地址翻译是一个N元素的虚拟地址空间（VAS）中的元素和一个M元素的物理地址空间（PAS）中元素之间的映射，

CPU中的一个控制寄存器，页表基址寄存器（Page Table Base Register, PTBR）指向当前页表。
n位的虚拟地址包含两个部分：
一个p位的虚拟页面偏移（Virtual Page Offset, VPO）和一个（n-p）位的虚拟页号（Virtual Page Number, VPN）。

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

•	笫1步：处理器生成一个虚拟地址，并把它传送给MMU 。
•	笫2步：MMU生成PTE地址，并从高速缓存/主存请求得到它。
•	笫3步：高速缓存/主存向MMU返回 PTE。
•	笫4步：MMU构造物理地址，并把它传送给高速缓存/主存。
•	笫5步： 高速缓存/主存返回所请求的数据字给处理器。

处理缺页要求硬件和操作系统内核协作完成 ， 如图 9-13b 所示。

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

结合高速缓存和虚拟内存

使用物理寻址，多个进程同时在高速缓存中有存储块和共享来自相同虚拟页面的块成为很简单的事情。

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

利用TLB加速地址翻译

每个CPU产生一个虚拟地址，MMU就必须查阅一个PTE，以便将虚拟地址翻译为物理地址。
在最糟糕的情况下，这会要求从内存多取一次数据，代价是几十到几百个周期。

在MMU中包括了一个关于PTE的小的缓存，称为翻译后备缓冲器（Translation Lookaside Buffer, TLB）。

TLB是一个小的、虚拟寻址的缓存，其中每一行都保存着一个由单个PTE组成的块。
TLB通常有高度的相联度。

TLB命中时（通常情况）所包括的步骤：

第1步：CPU产生一个虚拟地址。
第2步和第3步：MMU从TLB中取出相应的PTE。
第4步：MMU将这个虚拟地址翻译成一个物理地址，并且将它发送到高速缓存/主存。
第5步：高速缓存/主存将所请求的数据字返回给CPU。

当TLB不命中时，MMU必须从L1缓存中取出相应的PTE。
新取出的PTE存放在TLB中，可能会覆盖一个已经存在的条目。

多级页表

用来压缩页表的常用方法是使用层次结构的页表。

一级页表中的每个PTE负责映射虚拟地址空间中一个4MB的片（chunk），这里每一片都是由1024个连续的页面组成的。
二级页表中的每个PTE都负责映射一个4KB的虚拟内存页面，就像我们查看只有一级的页表一样。

这种方法从两个方面减少了内存要求：
第一，如果一级页表中的一个PTE是空的，那么相应的二级页表就根本不会存在。
第二，只有一级页表才需要总是在的主存中；虚拟内存系统可以在需要时创建、页面调入或调出二级页表，这就减少了主存的压力；只有最经常使用的二级页表才需要缓存在主存中。

综合：端到端的地址翻译

端到端的地址翻译示例：
示例运行在有一个TLB和L1 d-cache的小系统上。

为了保证可管理性，做出如下假设：

- 内存是按字节寻址的。
- 内存访问是针对1字节的字的（不是4字节的字）。
- 虚拟地址是14位长的（n=14）。
- 物理地址是12位长的（m-12）。
- 页面大小是64字节（P=64）。
- TLB是四路组相联的，总共有16个条目。
- L1 d-cache 是物理寻址、直接映射的，行大小为4字节，而总共有16个组。

虚拟地址和物理地址的格式。

下图展示了小内存系统的一个快照，包括TLB、页表的一部分和L1高速缓存。

• TLB。 TLB是利用VPN的位进行虚拟寻址的。

• 页表。 这个页表是一个单级设计，一共有 $2^8=256$个页表条目（PTE）。

• 高速缓存。 直接映射的缓存是通过物理地址中的字段来寻址的。
  

    CPU执行一条读地址 0x03d4处字节的加载指令：
    
    １．MMU从虚拟地址中抽取VPN（0x0F）
    ２．依据VPN在TLB进行命中测试．这里命中得到PPN．
    如不命中，则从内存页表取得PPN，并将其放入TLB，再次对TLB访问．
    若PPN存在但有效位为０，
    则触发缺页异常，从磁盘将PPN对应的磁盘页调入内存，更新页表．
    若PPN不存在且有效位为０，触发段错误．
    再次执行此访问．
    若PPN存在且有效位为１但访问权限和页表项中冲	突，触发段错误．
    ３．PPN+VPO得到物理地址
    ４．将物理地址划分为CT/CI/CO对高速缓存进行命中测试
    这里命中，取得此地址处一个字节的数据信息．发到CPU．
    如不命中，从内存取得一个指定内存地址开始的缓存行大小数据块放入高速缓存，
    再次对高速缓存进行访问．
  

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

处理器封装（processor package）包括四个核、一个大的所有核共享的L3高速缓存，以及一个DDR3内存控制器。
每个核包含一个层次结构的TLB、一个层次结构的数据和指令高速缓存，以及一组快速的点到点链路，这种链路基于QuickPath技术，是为了让一个核与其他核和外部 I/O 桥直接通信。
TLB是虚拟寻址的，是四路组相联的。

Core i7地址翻译

Linux虚拟内存系统

1. Linux虚拟内存区域

Linux将虚拟内存组织成一些区域（也叫做段）的集合。
一个区域（area）就是已经存在着的（已分配）虚拟内存的连续片（chunk），这些页是以某种方式相关联的。

虚拟内存按区域为单位划分，区域是虚拟页的集合

2. Linux缺页异常处理

内存映射

通过将一个虚拟内存区域与一个磁盘上的对象关联起来，以初始化此虚拟区域内容映射到：
１．Linux文件系统的普通文件内一个区域
虚拟地址区域关联到磁盘文件某个区域
映射时，仅更新页表，不调磁盘页到内存．
首次访问时，会调入磁盘页，更新页表．
２．匿名文件
虚拟地址区域关联到内存某个区域
映射时，仅更新页表，不实际操作被映射内存区域．
首次访问时，内存页之前映射关系取消［通过更新页表实现］，如有写回需求，则写回磁盘．然后，内存页初始化为全是二进制０，更新页表．

再看共享对象

一个对象可被映射到虚拟内存的一个区域，要么作为共享对象，要么作私有对象。

另一方面，对于一个映射到私有对象的区域做的改变，对于其他进程来说是不可见的，并且进程对这个区域所做的任何写操作都不会反映在磁盘上的对象中。

一个映射到共享对象的虚拟内存区域叫做共享区域。

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

对于每个映射私有对象的进程，相应私有区域的页表条目都被标记为只读，并且区域结构被标记为私有的写时复制。

再看 fork 函数

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

当 fork 在新进程中返回时，新进程现在的虚拟内存刚好和调用 fork 时存在的虚拟内存相同。

再看 execve 函数

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

• 删除已存在的用户区域。删除当前进程虚拟地址的用户 部分中的已存在的区域结构。
• 映射私有区域。为新程序的代码、数 据、bss 和栈区域创建新的区域结构。
• 映射共享区域。
• 设置程序计 数器( P C ) 。
  

使用mmap函数的用户级内存映射

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

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

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

• PROT_EXEC: 这个区域内 的页面由可以被 CPU 执行的指令组成。
• PROT_READ: 这个区域内的页面可读。
• PROT_WRITE: 这个区域内的页面可写。
• PROT_NONE: 这个区域内的页面不能被访问。

参数 flags 由描述被映射对象类型的位组成。

动态内存分配

动态内存分配器维护着一个进程的虚拟内存区域，称为堆( heap)。

分配器有两种基本风格。

• 显式分配器 ( explicit allocator) , 要求应用显式地释放任何已分配的块。

• 隐式分配器 ( implicit allocator), 另一方面，要求分配器检测一个已分配块何时不再被程序所使用，那么就释放这个块。
  隐式分配器也叫做垃圾收集器( garbage collec­tor), 而自动释放未使用的已分配的块的过程叫做垃圾收集 ( garbage collection )。

malloc 和 free 函数

C 标准库提供了一个称为 malloc 程序包的显式分配器。程序通过调用 malloc 函数来从堆中分配块。

#include <stdlib.h>
void *malloc(size_t size);
//返回： 若成功则为己分配块的指针， 若出错则为NULL 。

malloc 函数返回一个指针，指向大小为至少 size 字节的内存块，这个块会为可能包含在这个块内的任何数据对象类型做对齐。

// malloc内部可借助mmap和munmap　或　sbrk实现
void* malloc(size_t size);
void free(void* ptr);
// 改变内核关于此进程的brk指针
void* sbrk(intptr_t incr);

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

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

分配器的要求和目标

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

• 处理任意请求序列。 一个应用可以有任意的分配请求和释放请求序列，只要满足约束条件：每个释放请求必须对应于一个当前已分配块，这个块是由一个以前的分配请求获得的。

• 立即响应请求。 分配器必须立即响应分配请求。

• 只使用堆 。 为了使分配器是可扩展的，分配器使用的任何非标量数据结构都必须保存在堆里。

• 对齐块（对齐要求）。 分配器必须对齐块，使得它们可以保存任何类型的数据对象。

• 不修改已分配的块。 分配器只能操作或者改变空闲块。

• 目标 1 : 最大化吞吐率。

• 目标 2 : 最大化内存利用率。

碎片

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

有两种形式的碎片：内部碎片 (internal fragmentation) 和外部碎片 ( external fragmentation) 。

内部碎片是在一个已分配块比有效载荷大时发生的。

内部碎片的量化是简单明了的。它就是巳分配块大小和它们的有效载荷大小之差的和。

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

外部碎片比内部碎片的量化要困难得多，因为它不仅取决于以前请求的模式和分配器的实现方式，还取决于将来请求的模式。

实现问题

一个实际的分配器要在吞吐率和利用率之间把握好平衡，就必须考虑以下几个问题：

• 空闲块组织
• 放置
• 分割
• 合并

隐式空闲链表

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

称这种结构为隐式空闲链表，是因为空闲块是通过头部中的大小字段隐含地连接着的。分配器可以通过遍历堆中所有的块，从而间接地遍历整个空闲块的集合。

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

放置已分配的块

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

分配器执行这种搜索的方式是由放置策略 (placement policy) 确定的。

一些常见的策略是首次适配( first fit )、下一次适配( next fit ) 和最佳适配( best fit )。

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

分割空闲块

一个大的空闲块会被拆分为一个已经分配块，余下部分组成一个新的空闲块。

获取额外堆内存

分配器在目前堆上无法完成对指定大小块的分配，分配器就会通过调用 sbrk 函数，向内核请求额外的堆内存。
分配器将额外的内存转化成一个大的空闲块，将这个块插入到空闲链表中，然后将被请求的块放置在这个新的空闲块中。

合并空闲块

当分配器释放一个已分配块时，可能有其他空闲块与这个新释放的空闲块相邻。
这些邻接的空闲块可能引起一种现象，叫做假碎片 (fault fragmentation), 就是有许多可用的空闲块被切割成为小的、无法使用的空闲块。

相邻的二个或多个空闲块可以合并为一个大的空闲块，可以在块释放时立即检查并合并，可以延迟到分配失败，再合并，然后重试。

9.带边界标记的合并

当前块的头部指向下一个块的头部，可以检查这个指针以判断下一个块是否是空闲的。如果是，就将它的大小简单地加到当前块头部的大小上，这两个块在常数时间内被合并。

边界标记 ( boundary tag), 允许在常数时间内进行对前面块的合并 。

这种思想，是在每个 块的结尾处添加一个脚部( footer , 边界标记），其中脚部就是头部的一个副本。
如果每个块包括这样一个脚部，那么分配器就可以通过检查它的脚部，判断前面一个块的起始位置和状态，这个脚部总是在距当前块开始位置一个字的距离。
考虑当分配器释放当前块时所有可能存在的情况：

1. 前面的块和后面的块都是已分配的。
2. 前面的块是已分配的，后面的块是空闲的。
3. 前面的块是空闲的，而后面的块是已分配的。
4. 前面的和后面的块都是空闲的 。

显式空闲链表

一种更好的方法是将空闲块组织为某种形式的显式数据结构。

因为根据定义，程序不需要一个空闲块的主体，所以实现这个数据结构的指针可以存放在这些空闲块的主体里面。

释放一个块的时间可以是线性的，也可能是个常数，这取决于我们所选择的空闲链表中块的排序策略。

一种方法是用后进先出( LIFO) 的顺序维护链表，将新释放的块放置在链表的开始处。

另一种方法是按照地址顺序来维护链表，其中链表中每个块的地址都小于它后继的地址。

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

分离的空闲链表

一种流行的减少分配时间的方法，常称为分离存储，即维护多个空闲链表，
每个链表中的块有大致相等的大小。
分配器维护者一个空闲链表数组，每个大小类一个空闲链表。

两种基本的方法 ： 简单分离存储( simple segrega­ted storage) 和分离适配( segregated fit ) 。

1. 简单分离存储

每个大小类的空闲链表含大小相等的块，每个块的大小为此类中最大元素大小。
分配块简单的全部分配，无拆分。
无法完成分配时，请求一个虚拟页倍数的虚拟内存，将虚拟区域化为为指定大小的块，并将其链接成空闲链表．
没有块的合并和拆分，易于造成内部碎片，外部碎片。

2. 分离适配

分配器维护一个空闲链表的数组。
每个空闲链表和一个大小类关联。
为分配一个块，先确定请求的大小类。
在大小类搜索匹配块。找到，分配。剩余部分插入合适大小类链表。
找不到，在下一更大大小类搜索。
释放一个块，先合并，合并后的块放入合适大小类链表。

3. 伙伴系统

伙伴系统( buddy s ystem ) 是分离适配的一种特例， 其中每个大小类都是 2 的幂。
关于伙伴系统的一个关键事实是，给定地址和块的大小，很容易计算出它的伙伴的地址。
伙伴系统分配器的主要优点是它的快速搜索和快速合并。
主要缺点是要求块大小为 2 的幂可能导致显著的内部碎片。

垃圾收集

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

在C程序的上下文中，应用调用 malloc，但从不调用 free。反之，垃圾收集器定期识别垃圾块，并相应地调用 free，将这些块放回到空链表中。

垃圾收集器的基本知识

垃圾收集器将内存视为一张有向可达图（reachability graph）。

该图的节点被分成一组根节点（root node）和一组堆节点（heap node）。
每个堆节点对应于堆中的一个已分配块。
根节点对应于这样一种不在堆中的位置，它们中包含指向堆中的指针。
这些位置可以是寄存器、栈里的变量，或者是虚拟内存中读写数据区域内的全局变量。

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

收集器可以按需提供它们的服务，或者它们可以作为一个核应用并行的独立线程，不断地更新可达图和回收垃圾。

Mark & Sweep 垃圾收集器

Mark & Sweep 垃圾收集器由标记（mark）阶段和清楚（sweep）阶段组成，标记阶段标记出根节点的所有可达的和已分配的后继，而后面的清除阶段释放每个未被标记的已分配块。
块头部中空闲的低位中的一位通常用来表示这个块释放被标记了。

对Mark & Sweep的描述将假设使用下列函数，其中 ptr 定义为 typedef void *ptr：

• ptr isPtr (ptr p)。 如果 p 指向一个已分配块中的某个字，那么就返回一个指向这个块的起始位置的指针 b 。否则返回 NULL。
• int blockMarked(ptr b)。 如果块 b 是已标记的，那么就返回 true。
• int blockAllocated(ptr b)。 如果块 b 是已分配的，那么就返回 true。
• void markBlock(ptr b)。 标记块 b。
• int length(b)。 返回块 b 的以字为单位的长度（不包括头部）。
• void unmarkBlock(ptr b)。 将块 b 的状态由已标记的改为未标记的。
• ptr nextBlock(ptr b)。 返回堆中块 b 的后继。

C程序的保守 Mark & Sweep

Mark & Sweep 对C程序的垃圾收集是一种合适的方法，因为它可以就地工作，而不需要移动任何块。

将已分配块集合维护成一棵平衡二叉树，这棵树保持着这样一个属性：左子树中的所有块都放在较小的地址处，而右子树中的所有块都放在较大的地址处。

C程序的 Mark & Sweep 收集器必须是保守的，其根本原因是C语言不会用类型信息来标记内存的位置。

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

间接引用坏指针

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

间接引用坏指针的一个常见示例是经典的 scanf 错误。

读未初始化的内存

一个常见的错误就是假设堆内存被初始化为零。

正确的实现方式是显式地将 y[i] 设置为零，或者使用 calloc。

允许栈缓冲区溢出

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

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

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

造成错位错误

错位( off-by-one ) 错误是另一种很常见的造成覆盖错误的来源。

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

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

误解指针运算

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

引用不存在的变量

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

引用空闲堆块中的数据

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

引用内存泄漏

内存泄漏是缓慢、隐性的杀手，当程序员不小心忘记释放已分配块，而在堆里创建了垃圾时，会发生这种问题。

学习参考资料：

《深入理解计算机系统》 第3版

最后

以上就是和谐唇膏为你收集整理的《深入理解计算机系统》学习笔记——虚拟内存虚拟内存的全部内容，希望文章能够帮你解决《深入理解计算机系统》学习笔记——虚拟内存虚拟内存所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。