将主存看成是一个存储在磁盘上的地址空间的高速缓存，在主存中只保存活动区域，并根据需要在磁盘和主存之间来回传送数据，通过这种方式，它高效地使用了主存。其实这一章还是讲解虚拟内存的，也就是和内核中的内存管理相关。

• 它为每个进程提供了一致的地址空间，从而简化了存储器管理
• 它保护了每个进程的地址空间不被其他进程破坏。
• 在硬件异常、汇编器、链接器、加载器、共享对象、文件和进程的设计中扮演着重要角色。
• 存储器让应用程序有了强大的能力，可以创建和销毁存储器片、将存储器片映射到磁盘文件的某个部分，以及与其他进程共享存储器。

一、物理和虚拟地址

主存被组织成一个由M个连续的字节大小的单元组成的数组。

每字节都有一个唯一的物理地址（Physical Address，PA）。第一个字节的地址为0，累加。

• 物理寻址(virtual addressing)：CPU访问存储器的最自然的方式就是使用物理地址。

  早期的PC、数字信号处理器、嵌入式微控制器、Cray超级计算机这样的系统仍然使用物理寻址。
  

• 虚拟寻址（virtual addressing）CPU通过生成一个虚拟地址来访问主存。

  现在处理器使用虚拟寻址。

• 地址翻译（address translation）：将一个虚拟地址转换为物理地址的任务。

  地址翻译需要CPU和操作系统之间的紧密合作。

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

  

二、地址空间

• 地址空间(adress space)是一个非整数地址的有序集合：{0,1,2,...}

• 如果地址空间中的整数是连续的，那么我们说它是一个线性地址空间(linear address space)。

• 在一个带虚拟存储器的系统中，CPU从一个有N = 2 ^ n个地址空间中生成虚拟地址，这个地址空间称为虚拟地址空间(virtual address space)：{0,1,2,3,...,N-1}

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

• 一个系统还有一个物理地址空间(physical addresss space)，它与系统中物理存储器的M字节相对应：{0,1,2,...M-1}

M不要求是2的幂，但是为了简化讨论，我们假设M = 2 ^ m。

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

三、虚拟存储器作为缓存的工具

虚拟存储器——虚拟页VP，每个虚拟页大小为P=2^平字节

物理存储器——物理页PP，也叫页帧，大小也为P字节。

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

• 未分配的：VM系统还没分配/创建的页，不占用任何磁盘空间。
• 缓存的：当前缓存在物理存储器中的已分配页
• 未缓存的：没有缓存在物理存储器中的已分配页
  
  1.DRAM缓存的组织结构

DRAM缓存：表示虚拟存储器系统的缓存，它在主存中缓存虚拟页。

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

2.页表

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

这些功能是由许多软硬件联合提供的，包括操作系统软件，MMU(存储器管理单元)中地址翻译硬件和一个存放在物理存储器中叫做页表(page table)的数据结构。

• 页表将虚拟页映射到物理页。
• 页表就是一个页表条目(Page Table Entry，PTE)的数组。
• 每个PTE由一个有效位和一个n位地址字段组成
  

3.页命中

地址翻译硬件将虚拟地址作为一个索引来定位PTE2，并从存储器中读取他。因为设置了有效位，VP2是缓存在存储器中，使用PTE中的物理存储器地址构造出这个字的物理地址。

4.缺页

缺页（page fault）：DRAM缓存不命中。

在磁盘和存储器之间传送页的活动叫做交换或者页面调度

按需页面调度：当有不命中发生时，才换入页面的策略。

5.分配页面

操作系统分配一个新的虚拟存储器页。

6.局部性

程序往往在一个较小的活动页面集合上工作，这个集合叫做工作集或者常驻集。

颠簸：页面不断换进换出。

四、虚拟存储器作为存储器管理的工具

操作系统为每个进程提供了一个独立的页表，因而也就是一个独立的虚拟地址空间。

多个虚拟页面可以映射到同一个共享物理页面上。

按需页面调度和独立的虚拟地址空间的结合，对存储器的使用和管理造成了深远的影响：

简化链接简化加载简化共享简化存储器分配

五、虚拟存储器作为存储器保护的工具

计算机系统必须为操作系统提供手段来控制对存储器系统的访问。

PTE的三个许可位：

• SUP：表示进程是否必须运行在内核模式下才能访问该页
• READ：读权限
• WRITE：写权限

六、地址翻译

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

MMU利用页表实现映射。CPU中的一个控制寄存器---页表基址寄存器（Page Table Base Register，PTBR）：指向当前页表。

页面命中，CPU硬件执行的步骤：

处理器生成一个虚拟地址，并把它传送给MMUMMU生成PTE地址，并从高速缓存/主存请求得到它高速缓存/主存向MMU返回PTEMMU构造物理地址，并把它传送给高速缓存/主存高速缓存/主存返回所请求的数据字给处理器

页面命中完全是由硬件来处理的，与之不同的是，处理缺页要求硬件和操作系统内核协作完成：

前三步都是一样的PTE中的有效位为0，所以MMU触发了一次异常，传递CPU中的控制到操系统内核中的缺页异常处理程序。缺页处理程序确定出物理存储器中的牺牲页，如果这个页面被修改了，则把它换出到磁盘。缺页处理程序页面调入新的页面，并更新存储器中的PTE缺页处理程序返回到原来的进程，再次执行导致缺页的指令。CPU将引起缺页的虚拟地址重新发送给MMU

上面是前三步的过程，在页面命中的时候进行的处理。如果页面没有命中。

整体过程将是上图所示。最后还是处理器再次发送虚拟地址给MMU，不过这次不会导致缺页异常。

多级页表

采用层次结构，用来压缩页表。

1.以两层页表层次结构为例，好处是：

如果一级页表中的一个PTE是空的，那么相应的二级页表就根本不会存在

只有一级页表才需要总是在主存中，虚拟存储器系统可以在需要时创建、页面调入或调出二级页表，只有最经常使用的二级页表才缓存在主存中。

2.多级页表的地址翻译：

七、案例研究：Intel Core i7/Linux 存储器系统

Linux虚拟存储器系统

Linux为每个进程维持了一个单独的虚拟地址空间。

内核虚拟存储器包含内核中的代码和数据结构。内核虚拟存储器的某些区域被映射到所有进程共享的物理页面。例如，每个进程共享内核的代码和全局数据结构。

1.Linux虚拟存储器区域

Linux将虚拟存储器组织成一些区域(也叫做段)的集合。一个区域(area)就是已经存在着的(已分配的)虚拟存储器的连续片(chunk)，这些页是以某种方式相关联的。例如，代码段、数据段、堆、共享库段，以及用户栈都不同的区域。每个存在的虚拟页面保存在某个区域中，而不属于某个区域的虚拟页是不存在的，并且不能被进程引用。区域的概念很重要，因为它允许虚拟地址空间有间隙。内核不用记录那些不存在的虚拟页，而这样的页也不占用存储器。磁盘或者内核本身的任何额外资源。

内核为系统中的每个进程维护一个单独的任务结构(源代码中的task_struct)。任务结构中的元素包含或者指向内核运行该进程所需要的所有信息(例如，PID，指向用户栈的指针、可执行的目标文件的名字以及程序计数器)。

task_struct中的一个条目指向mm_struct，它描述了虚拟存储器中的当前状态。其中pgd指向第一级页表(页全局目录)的基址，而mmap指向一个vm_area_struct(区域结构)的链表。其中每个vm_area_structs都描述了当前虚拟地址空间的一个区域(area)。当内核运行这个进程时，它就将pgd存放在CR3控制寄存器中。

一个具体区域结构包含下面的字段：

• vm_start：指向这个区域的起始处。
• vm_end：指向这个区域的结束处。
• vm_prot：描述这个区域的内包含的所有页的读写许可权限。
• vm_flags：描述这个区域内页面是与其他进程共享的，还是这个进程私有的(还描述了其他一些信息)。
• vm_next：指向链表中下一个区域结构。

2.Linux缺页异常处理

八、存储器映射

1、Linux通过将一个虚拟存储器区域与一个磁盘上的对象（object）关联起来，以初始化这个虚拟存储器区域的内容，这个过程称为存储器映射（memory mapping）。虚拟存储器区域可以映射到两种类型的对象：

1）unix文件系统中的普通文件：一个区域可以映射到一个普通磁盘文件的连续部分。

2）匿名文件：一个区域也可以映射到一个匿名文件，匿名文件是由内核创建的，包含的全是二进制零。

一旦一个虚拟页面被初始化了，它就在一个由内核维护的专门的交换文件（swap file）间换来换去。

2、共享对象

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

3、私有对象，写时拷贝(copy-on-write)

私有对象是使用一种叫做写时拷贝的技术被映射到虚拟存储器中的。如图中所示：只要有一个进程试图写私有区域内的某个页面，那么这个写操作就会触发一个保护策略。它就会在物理存储器中创建这个页面的一个新拷贝，更新页面条目指向这个新的拷贝，然后恢复这个页面的可写权限。

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

九、 动态存储器分配

1、需要额外的虚拟存储器时，使用一种动态存储器分配器（dynamic memory allocator）。一个动态存储器分配器维护着一个进程的虚拟存储器区域，称为堆（heap）。在大多数的unix系统中，堆是一个请求二进制0的区域；对于每个进程，内核维护着一个变量brk，它指向堆的顶部。

2、分配器将堆视为一组不同大小的块（block）的集合来维护。每个块就是一个连续的虚拟存储器组块（chunk），要么是已分配的，要么是未分配的。

1）显式分配器（explicit allocator）：如通过malloc,free或C++中通过new,delete来分配和释放一个块。

2）隐式分配器（implicit allocator）：也叫做垃圾收集器（garbage collector）。自动释放未使用的已分配的块的过程叫做垃圾回收（garbage collection）。

3、malloc不初始化它返回的存储器，calloc是一个基于malloc的包装（wrapper）函数，它将分配的存储器初始化为0。想要改变一个以前已分配的块的大小，可以使用realloc函数。

4、分配器必须对齐块，使得它们可以保存任何类型的数据对象。在大多数系统中，以8字节边界对齐。

不修改已分配的块：分配器只能操作或者改变空闲块。一旦被分配，就不允许修改或者移动它。

5、碎片（fragmentation）

有内部碎片（internal）和外部碎片（external）。

• 内部碎片：在一个已分配块比有效载荷在时发生的。（如对齐要求，分配最小值限制等）
• 外部碎片：当空闲存储器合计起来足够满足一个分配请求，但是没有一个单独的空闲块足够大可以来处理这个请求时发生的。

6、隐式空间链表

堆块的格式：

由一个字的头部，有效荷载，和可能的额外填充组成。

将堆组织成一个连续的已分配块和空闲块的序列：

空闲块通过头部中的大小字段隐含地连接着，分配器可以通过遍历堆中所有的块，从而间接地遍历整个空闲块的集合。

需要：特殊标记的结束块。

系统对齐要求和分配器对块格式的选择会对分配器上的最小块大小有强制的要求。

7、一种流行的减少分配时间的方法，称为分离存储（segregated storage），维护多个空闲链表，其中每个链表中的块有大致相等的大小。

十、垃圾回收

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

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

3、指针的算术运算是以它们指向的对象的大小为单位来进行的。

十一、C程序中常见的与存储器有关的错误

（1）间接引用坏指针

在进程的虚拟地址空间中有较大的洞，没有映射到任何有意义的数据。

坏指针：

读：段异常

写：保护异常---覆盖存储器

（2）读未初始化的存储器

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

正确的做法是显示地初始化。

（3）允许栈缓冲区溢出

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

例如：gets()函数拷贝一个任意长度的串到缓冲区，就有缓冲区溢出错误。用fgets()函数可以纠正这个错误，它限制了输入串的大小。

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

int int*

在远处起作用

（5）造成错位错误

错位错误（off-by-one）：另一种覆盖错误。

例如：试图初始化具有n个元素的第（n+1）个元素，会覆盖数组后面的某个存储器。

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

注意C操作符的优先级和结合性。区别 ：size size+1 *(size+1)

（7）误解指针运算

指针的算术操作：p++

（8）引用不存在的变量

函数不能返回局部变量的指针或引用。

（9）引用空闲堆块中的数据

intx=new int (5); delete x; 后再次引用 int y=x; ---错误。

（10）引起存储器泄露

忘记了释放已分配的块。 new 之后忘记调用 delete;

课后作业中的问题和解决过程

9.3

问题：给定一个32位的虚拟地址空间和一个24位的物理地址，对于下面的页面大小P，确定VPN虚拟页号,VPO（虚拟页面偏移量）,PPN（物理页号）,PPO（物理页面偏移量）中的位数。

解答：

页面大小P = 1KB VPO和PPO要log2（1K）=10位 剩下的地址位是VPN = 22 PPN = 14

故可得下表

P	#VPN	#VPO	#PPN	#PPO
1KB	22	10	14	10
2KB	21	11	13	11
4KB	20	12	12	12
8KB	19	13	11	13

家庭作业9.11

其他

这章讲述的是虚拟存储器系统，我对它是如何工作以及它的特性有所了解。

这张内容和之前所学（例如堆栈进程等）内容都联系紧密，可以看做“糖葫芦中间的签子”。同时这些内容也在操作系统课上有讲解，对操作系统的学习来讲是一个很大的补充，更是结合了有关的代码。再次学习这本书，我理解的更加深入。同时，我认为这章也展现了将计算机系统中的软件和硬件的结合。在最后也详细描述了c程序中常见的与存储器有关的错误，这就可以让我们自己优化程序中某些地方，来满足应用程序的需要。

看完这章，也算是将《深入理解计算机系统》草草看过一遍。这本书写的相当详细，是一本很有价值的读物，值得我再去深入阅读理解，发现其中的奥秘。

学习进度条

	代码行数（新增/累积）	博客量（新增/累积）	学习时间（新增/累积）	重要成长
目标	5000行	30篇	400小时
第一周	100/100	2/2	25/25	安装了虚拟机并学习掌握核心的linux命令
第二周	100/200	1/3	30/55	虚拟机上的C语言编程
第三周	150/350	1/4	10/65	计算机中信息的表示和运算
第四周	0/350	0/4	3/68	复习前几周内容
第五周	75/420	1/5	20/88	程序的机器级表示
第六周	125/545	1/6	20/108	Y86指令 硬件语言控制HCL
第七周	72/617	1/7	20/128	磁盘 存储器相关结构
第八周	0/617	2/9	20/148	期中总结
第九周	185/802	2/11	25/173	系统级的输入输出
第十周	669/1472	2/13	20/193	重点代码的学习
第十一周	669/1472	2/15	35/228	process代码的学习
第十二周	20/1492	3/18	35/228	前几周代码复习
第十三周	808/2300	1/19	35/228	网络编程、并发、进程、多线程
第十四周	0/2300	1/20	20/248	虚拟存储器的概念及其作用

参考资料