存储系列之 虚拟内存：分页技术
引言：前面连续几章讲述的文件系统是存储系统的外存管理的一种抽象，而虚拟内存则是存储系统的内存管理的一种抽象。其实这两种原理有相似地地方，当然也就有不同的地方。同时这两者也属于操作系统内核的范畴。
1、虚拟内存的概念
虚拟内存又叫虚拟存储器（Virtual Memory），虚拟内存是计算机系统内存管理的一种技术。
我们都知道，进程运行前必须将程序加载到内存中，而根据Parkinson定律“存储有多大，程序就会有多长”，所以如何有效的管理内存一直是计算机需要解决的问题，也因此提出了很多简单高效的方案，例如虚拟内存是其中之一。所以虚拟内存是因为内存不足而提出来的，而目前这种技术也已经普遍应用在大多数操作系统中，具体实现起来可能稍有不同。
虚拟内存简单的定义就是把进程在内存和磁盘之间换进换出。如何换？页面置换。当然这只是比较常见的方法，也还有其他方法或者几种方法的组合。
2、交换技术
在虚拟内存技术提出之前，其实已有另一种更简单更直接的技术：交换技术。
交换技术，就是把各个进程完整地调入内存，运行一段时间后，然后再放回到磁盘上。
而虚拟内存，只需把进程的一部分内容存放在内存中，而且也能保证进程的正常运行。
这两种方式虽然加载的对象大小不相同，但是都需要进程的换进换出。同时，进程的堆栈是实时变化的，那么该如何管理内存空间呢？
其中，操作系统的内核进程是常驻在内存，一般固定在内存空间地址最低端，如上图。32位系统中，一般情况下固定大小1GB为系统区，而其他3GB为用户区。
2.1 空闲块的管理
内存是动态分配的，那么如何记录当前内存的使用情况？有以下两种方式。
（1）位图法
在位图法中，内存被划分为很多个单元，每个单元对应于位图中的某个数据位，0表示空闲，1表示占用。如下图显示了部分的内存和相应的位图。
分配单元的大小是一个很重要的设计问题，分配单元越小，位图越大。位图法，简单；但是查找一串K个连续的0，比较复杂和缓慢。
（2）链表法
对内存的管理建立一个链表来管理已分配和空闲的内存空间。如上图的(c)，P 代表进程Process，H表示空闲Hole，接下来两个字段依次表示起始地址和长度，最后一个字段是指向下一个节点的指针。在这个例子中，链表是按照地址从低到高排序的。这样做的好处是当一个进程运行结束或被置换出去时，可以很方便地来更新链表。
2.2 空闲块的查找
当一个新的程序加载进来的时候又该如何找到空闲的地址空间？通常的分配算法有最先匹配法、下次匹配法、最佳匹配法、最坏匹配法和快速匹配法。这些算法特别是前面几个都有些类似，我们简单介绍下。
最先匹配法的基本思路是：假如进程的大小M，从链表的首节点开始查找，每个空闲块的长和M比较，是否大于或等于它，直到找到第一个符合要求的节点。
下次匹配法是在上次查找的结果基础下继续查找直到匹配成功。
最佳匹配法需要遍历所有节点，找到能装得下的最小空闲块。而最坏匹配法则相反，找能装得下的最大的空闲块。事实上，这两种都有比较而且遍历所有链表，效果不佳。
快速匹配法和其他不太一样，基本思路是：对于一些常用的请求大小例如2K、4K、8K等，为它们分别设置链表。这样查找匹配非常快，但是如果程序结束时或者被置换后，可能需要合并左邻右舍等操作操作复杂，如果不能合并则可能形成小空洞碎片。
对于这些碎片或者说一些不连续的小黑洞，可以采用内存紧缩（memory compation）技术：把所有的进程都尽可能地往内存地址的低端移动，相应地，那些空闲的小分区就会往高端移动，从而在地址高端形成一个较大的空闲区。
3、虚拟内存
上面的交换技术是把程序作为一个整体放入内存。但如果程序太大了，超出了空闲内存的容量，没办法装入，该怎么办？事实上大部分可能是这种情况。
当时人们通常采用的解决方案是覆盖技术，即：把程序划分成若干个部分，每个部分叫做覆盖块（overlay），然后把那些当前需要用到的指令和数据的覆盖块保存在内存中，其他放外存，运行一段时候后，在内外存之间再交换所需的覆盖块。
虽然覆盖块的交换是由操作系统完成，但是覆盖块的划分最开始由程序员来手工完成，这是一项非常复杂的工作，费时费力。后不久人们又想到了一种办法，可以把工作交给计算机完成。
这种方法叫做虚拟存储器（Virtual Memory）（Fotheringham，1961），我们一般称作虚拟内存。它的基本思路是：程序的代码、数据和栈的总大小可以超过实际可用的物理内存的大小。操作系统把当前需要的那些部分保留在内存中，而把其余部分保持在磁盘上。然后在再需要的时候，再把各个程序片段在内存和磁盘之间来回交换。
3.1 分页
大部分虚拟存储系统采用的是一种称为分页（paging）的技术。这种方式叫做虚拟页式存储管理。
由程序产生的地址称为虚拟地址（virtual address），它们构成了一个虚拟地址空间（virtual address space）。虚拟地址也叫做线性地址（linear address）。
如果计算机没有使用虚拟存储机制，那么虚拟地址就是最终的物理地址，它被直接放在地址总线上，从而可以对相应地址的内存单元进行读写操作。如果计算机使用了虚拟存储机制，那么虚拟地址不是直接放在地址总线上，而是被送到存储管理单元（Memory Management Unit，MMU），由它负责把虚拟地址映射为物理地址。MMU一般集成在CPU芯片内部，从逻辑上讲，它可以是单独的一个芯片。
物理内存空间划分为固定大小的内存块，称为物理页面，或者是页框（page frame）。
虚拟地址空间也划分成大小相同的块，称为虚拟页面，或者简称页面（page）。
页面和页框的大小通常是一样的，要求是2的整数次幂，一般在512字节到1G字节之间。程序在换入换出的时候是以页面为单位。
MMU可以完成虚拟地址到物理地址的映射，但是我们知道，虚拟地址空间是远远大于物理地址空间即内存空间的，所以也就不能保证所有虚拟地址能找到对应的物理地址，即无法完成映射。此时，MMU会引发一个缺页中断（page fault），把这个问题交给操作系统处理。操作系统从内存中挑选一个使用不多的物理页面，把它的内容写回到磁盘，从而腾出了一个空闲页面，然后把引发缺页中断的那个虚拟页面装入该空闲页面中，并对地址映射进行更新。最后回到被中断的指令重新开始。
下面我们来看看MMU的内部结构，了解一下它的工作原理。举例：页面大小4KB、虚拟地址空间是64KB、物理内存是32KB，因此可得到16个虚拟页面和8个物理页面。如下图所示，虚拟地址8196（二进制是0010 0000 0000 0100），输入的16位虚拟地址被划分为两部分：4位的页号和12位的偏移量。4位的页号可以表示16个页面，12位的偏移量可以寻址4096个字节。
在进行地址映射时，使用虚拟页面号作为索引去访问页表（page table），从而得到相应的物理地址。如果有效位（页表最低位）为0，则产生缺页中断，陷入操作系统中；否则将页表查到的物理页面号加上偏移量，就得到了15位的物理地址。
3.2 页表
如上所述，虚拟地址被分为虚拟页面号（高位）和偏移量（低位）两部分。高4位指定虚拟页面号，也可以是3位、5位或其他，不同的划分表示不同的页面大小。
页表的用途是将虚拟页面映射为相应的物理页面。
上述例子中只是16位的虚拟地址空间，那么32位的虚拟地址空间为4GB，64位的地址空间可达16EB（虽然我们普遍不用这么多位），如果将页面映射放在一个页表中，那么页表项将非常庞大。此外由于每个进程都有自己的虚拟地址空间，因此每个进程也有自己的页表。这样，页表的数量和规模将更加庞大。有没有一种大而快速的页面映射解决方案呢？分级。
（1）多级页表
多级页表的基本思路是：虽然进程的虚拟地址空间很大，但是当进程在运行时，并不会用到所有的虚拟地址，所以没必要把所有的页表项都保存在内存中。
如下图，一个典型的二级页表的例子，虚拟地址为32位，页面大小4KB。虚拟页面号为20位，分成两级，最高10位表示页目录，中间10位为页表，从而形成10+10+12的二级页表。 二级页表也可以扩展为三级、四级或更多级。64位处理器典型地划分为9+9+9+9+12的四级页表。更多的级别带来了更多的灵活性，但算法的复杂性也会更高。
（2）页表项
页目录项和页表项具有相同的结构，但不同的CPU对页表项的具体安排会有所不同，我们讨论一些共性。如下图，给出了一个页表项的示例。页表项的长度因机器而异，一般使用的32位即4字节。
物理页面号------最重要的就是物理页面号，页映射的目的就是找到这个值。
有效位------1表示该表项是有效的，可以使用；0则表示该表项对应的虚拟页面现在不在内存中，访问该页面会引起一个缺页中断。
保护位------指出一个页允许什么样的方式访问，最简单的形式是只有一位，0表示读/写，1表示只读；更先进的方式是使用三位，各位分别表示是否启用读、写、执行该页面。
修改位------记录页面的使用情况，在写入一个页时自动设置修改位。如果一个页面已经被修改过（称为“脏页面”），则必须把它写会磁盘。如果没有被修改过（称为“干净页面”），可以直接被覆盖，因为它在磁盘上有备份。修改位也称为脏位，反映了页面的当前状态。
访问位------不论是读还是写，系统都会在该页面被访问时设置访问位。用于页面置换算法中，未被访问的通常认为是不经常使用的而被置换出去。页面置换我们稍后介绍。
禁止缓存位------禁止该页面被高速缓存，对于映射到设备寄存器而不是常规内存的页面很重要。具有独立的I/O空间而不使用内存映射I/O的机器不需要这一位。高速缓存在下一章介绍。
3.3 关联存储器TLB
从上面我们可以看出，每一次内存访问，都需要两次访问页表，而随着页表的增多，整体性能是会受很大影响的。后面人们发现绝大多数程序运行时，在任意一个阶段都只会访问一小部分的页面，而非所有页面。这就是访问的局部性原理，或者说程序局部性原理。
人们利用这个特性为计算机设计和增加了一种快速查找的硬件，即TLB（Translation lookaside Buffer）或者称为关联存储器（associative memory），用来存放最常用的页表项。这种硬件设备可以直接把虚拟地址映射到物理地址，而不必访问内存，所以简称为快表。TLB通常位于MMU中，只包含了少量的表项，书上说不超过64，网上有的说不超过256，总之非常少。
工作过程：当一个虚拟地址到来时，MMU首先会到TLB中查找，这个查找非常快，因为它是并行的方式，即同时与所有的页表项进行比较。如果找到了，直接取出物理页面号。否则如果权限够的话将再去内存中查找所需的物理页面号；然后，再将找到的物理页面号所在的页表项添加到TLB中，同时驱逐TLB中某一个页表项；最后将被驱逐的页表项的修改位复制到对应的内存中的页表项。
软件TLB管理
上面我们描述的硬件TLB，TLB的管理和TLB未命中时的处理都交由MMU硬件完成，只有当页面不在内存中时才会陷入到操作系统。
而在现代有些机器中，几乎所有的页面管理工作都是有软件来完成，TLB表项也由操作系统负责载入。如果发生TLB未命中，MMU会产生一个TLB中断，把问题交给操作系统。操作系统来对TLB进行页面置换，但是这项工作必须用很少的命令完成，因为TLB未命中的频率远远高于缺页中断的频率。为此，人们也设计出了一些方法来提高未命中的概率，例如在内存固定位置设置一个较大的缓冲区，存放最近常用的TLB表项；或者预测常用的页面预先装入TLB中。
3.4 反置页表
前面我们讲述的页表方案是通过进程的虚拟页面号来组织的，用虚拟页表号来作为访问页表的索引。如果页面大小4KB，32位寻址时，一个进程的页表项个数是100万。如果再按每个页表项长度是4字节，一个进程的页表需要4MB的内存空间。这是32位，如果变成64位寻址，需要的内存显然是个天文数字。
一种解决方案就是反置页表（inverted page table），也称作倒排页表，根据内存的物理页面号来组织页表，用物理页面号作为访问页表的索引。有多少个物理页面，就在页表中设置多少个页表项。而一般情况下物理页面远远小于虚拟页面，所以这种方法节省了大量的内存空间。但同时也带来一个问题，即从虚拟页面号到物理页面号的转换变得复杂。必须搜索整个页表。
摆脱这种困境就是使用TLB。因为TLB存放了我们经常访问的页面。不过如果TLB未命中，则仍然需要对整个反置页表进行搜索。为了加快加快这个过程，人们又想到了一个办法，使用虚拟地址建立一个哈希表。如果两个虚拟页面具有相同的哈希值，那么它们就用链表连起来。（这种方法是不是似曾相识呢：Redis+MySQL，后面提到LRU方法亦是。）
4、其他
以上对虚拟内存的页式存储管理的基本原理已经介绍完成，我们再深入了解几个知识点。最后补充一下其他的存储管理方式。
4.1 页面置换的算法和策略
虚拟内存的核心就是进程的换入换出，也就是缺页中断进行页面置换。问题来了，如何选择被置换的页面？页面的换进换出是需要开销的，所以一个好的页面算法就是尽量减少页面换进换出的次数。
最优算法------易于描述但无法实现，一般用作目标或者说算法性能评价的依据。思路是：对于每一个虚拟页面，都计算出下一次访问的时间，用指令数来计算，然后选择等待时间最长的那个页面。明显的比较理想，虚拟页面多而且下一次访问也是不确定的。
最近未使用算法------Not Recently Used，NRU。按页表项中的访问位和修改位的值对页面进行分成四类，对应四个值，值越小，越没被使用过。然后在值最小的那类再随机抽取一个页面。
先进先出算法------First In First Out，FIFO。把最先访问的页面放在链表的首部，后面访问的再依次排队在链表的首部，最先的变成了尾部，选择的就是链尾页面。该算法可能会淘汰一些不常用的页面，但是也存在淘汰一些常用只是暂时没用的页面。
第二次机会算法------针对FIFO进行了改进，根据FIFO得到一个页面时不是直接淘汰，而是再给一次机会，把它放在链表的首部。
时钟算法------第二次机会需要移动链表节点，时钟算法将链表变成环形，首尾相连。
最近最久未使用------Least Recently Used，LRU。选择最久未被使用的页面。最优算法的一个近似，它的理论依据是程序的局部性原理。如果某个页面被访问了，它很有可能马上被访问；同样如果它很久没被访问，那么将来可能很长时间也不会被访问。在LRU基础上，利用页表项中的访问位和修改位这两个值和二进制移位，得到改进的算法，叫老化算法。减少了LRU链表的操作。
上面讨论的算法是在一个进程内部，如果在相互竞争的进程之间如何分配呢？有两种策略。
局部分配策略------为每个进程分配固定大小的内存空间。
全局分配策略------所有进程可以动态分配内存空间。通常情况下比局部策略更好，置换页面的时候可以考虑整个内存空间，减少缺页发送的次数。
4.2 工作集模型
页式存储管理中，进程启动之初，所有页面都在外存，所以CPU去取第一个页面时，会引发缺页中断。随着是一系列的缺页中断，一段时间后，中断次数会减少。这种策略就叫做请求调页（demand paging）,根据需要随要随调。
而前面我们介绍过局部性原理，绝大多数进程实际访问的页面只是很小的一部分，我们把一个进程当前正在使用的页面集合叫做它的工作集（working set）。如果我们在程序运行前就预先装入它的页面，这种技术叫做预先调页（prepaging）。而装入的页面就是进程运行所需的工作集，这种方法叫做工作集模型。为了实现工作集模型，操作系统必须知道哪些页面属于工作集，一种方法就是前面讨论的老化算法。当然，随着时间的变化，进程的工作集也会发生变化。一般工作集具有渐进式、缓慢变化的特点。
但是进程的工作集有时会发送剧烈的变动，它的运行可能进入一个调整期。如果分配给一个进程的物理页面数太少，不能包含整个工作集，这是进程会造成很多的缺页中断，需要频繁的在内存和外存之间置换页面，从而使得进程的运行速度变慢，我们把这种状态称作抖动（Denning）。同时我们也应该要优化我们的代码尽量减少和避免这种情况的发生！
4.3 页面大小
页面大小在页式存储管理系统中是一个非常重要的参数，也是一个可以自定义的参数。查看系统中页的大小：
[root@localhost mysql]# getconf PAGESIZE
4096
内核是以页面作为内存管理的单位，内存分配时，每次分配都是页面大小的整数倍。页面越小，内碎片就会越少。分配的内存一般不会是页面的整数倍，最后一个页面剩下的空间叫做内碎片。页面越小，同时页表就越庞大，进程运行时系统开销也会越大。
另外，在内存和磁盘之间传送数据也是以页面为单位的。所以文件系统的逻辑块大小最好和页面大小保持一致。
大多数计算机使用的页面大小在512字节到1M之间，典型的值是1KB、4KB和8KB。现在随着内存容量越来越大，页面大小也越来越大。
4.4 段式和段页式存储管理
前面介绍都是跟分页方式相关的虚拟内存。事实上，虚拟内存的调度方式有分页式、段式、段页式3种。只是现在大部分的操作系统使用了分页式，而且理解了分页式，再来看其他两种就非常容易了。
（1）段式存储管理
分页式存储管理是一维的，而段式则是二维的。即分页式存储的虚拟地址从0到某一个最大地址，一个接一个。而段式存储提供多个相互独立的地址空间，称为段（segment）；每个段的内部都是从0到某一个最大值这样一个线性地址，段的长度可以动态变化。
分段有助于在几个进程之间共享函数和数据，一个典型的例子就是共享库（shared library）。页式存储管理也可以实现共享库，但是要复杂得多，实际上它们都是通过模拟分段来实现的。
在具体实现上，段式和页式存储系统是完全不同的：页面是定长的而段不是。所以，随着程序的运行，段式存储很容易形成外碎片（external fragmentation）或者叫做跳棋盘（checkerboarding）。外碎片通常比较小，无法再装入新的段，容易造成浪费。当然这个问题也可以通过前面2.2节讲过的紧缩技术来解决。
（2）段页式存储管理
Intel Pentinum支持16K个段，每个段最多可以容纳4GB的虚拟地址空间。操作系统可以对其进行设置，使他支持纯页式、纯段式或者段页式存储管理。大多数操作系统如Linux和Windows都采用纯页式存储管理。
Pentinum虚拟存储器的核心是两张表，局部描述符（Local Descriptor Table，LDT）和全局描述符（Global Descriptor Table，GDT）。每个进程都有自己的LDT，但是GDT只有一个，为计算机上所有进程共享。LDT描述的是每个程序自己的段，包括代码段、数据段、栈段等，而GDT描述的是系统的段，包括操作系统本身。
上图是Pentinum代码段描述符的结构，数据段略有不同。本文不再铺开描述了，有兴趣可以参考：分段机制与GDT|LDT。
推荐阅读：Linux内核之 内存管理
参考资料：
《操作系统设计与实现》第三版 上册。
《深入理解LINUX内核》第三版。