操作系统-虚拟内存前世今生

学习背景

在前面对ZGC的讲解里，我们介绍了虚拟指针，它是依靠虚拟内存技术实现的。今天我们就来学习一下虚拟内存技术，虚拟内存技术在面试里问的不多，(字节除外)，正好可以作为我们学习完毕复杂理论后的过度。高强度学习配合低强度学习，不太疲惫也不太轻松，学习的效率才能更高。

地址空间

操作系统的内存模型被称为分层存储体系(memory hierarchy),这个体系由若干快速且易丢失且昂贵的高速缓存cache和速度适中价格适中且同样易丢失的内存，以及速度慢，单价格低廉且不易丢失的磁盘构成。 在比较早期的操作系统中根本没有存储体系抽象，对内存的操作都是直接操作物理内存，比如mov registor1 1000 表示将1000这个位置的内存移动到registor1中。早期一般有三种模型，操作系统位于ram的底部，操作系统位于rom的顶部，操作系统位于ram的底部但是驱动程序位于rom的顶部

第1,3中都有明显的缺陷就是用户程序对内存的操作可能造成操作系统的崩溃。很明显的对于绝对内存地址的操作存在致命缺陷，因为一个程序可能会操作另一个程序的内存，虽然有一些办法补救，比如静态重定位。但现代操作系统基本不采用这行方案，也就是不直接操作内存。除了少部分嵌入式设备外，因为这些设备的任务都是事前预设好的，用户不可能再烤面包机上运行自己程序。但也有例外，少部分昂贵的嵌入式设备不会直接操作内存。 为了解决这个问题，我们提出地址空间的概念，地址空间是指一个进程可以寻址的内存地址集合，各个进程只能操作自己的地址空间，除了某些时候需要共享地址空间时除外。地址空间的概念非常广，电话号码，ip甚至网址都可以算作是一种地址空间的标识方法。

基址寄存器和界限寄存器

一种已经过时的内存重定位定位的方法，方程序被重新加载到内存时，我们需要判断它应该被加载到哪个位置。程序的起始地址会被加载到基址寄存器，程序的长度被加载到界限寄存器。每次程序访问内存时，cpu会把地址发送到内存总线，把基址寄存器加到程序发出的地址上，同时检查程序提供的地址是否大于界限寄存器的值，防止访问越界。

交换技术

计算机的内存是有限的，将进程一直保持在内存中需要消耗巨大的内存，如果做不到，那么就需要解决内存超载的问题，常见的解决办法是交换(swapping)技术和虚拟内存(virtual memory),交换内存将程序完整的调入内存，运行一段时间然后存回磁盘，这样空闲的进程就不会占用内存(但是有一部分进程会被周期性唤醒工作后又进入休眠)。虚拟内存则更加先进，甚至允许程序在只有一部分被调入内存的情况下完成。

这这个图里，我们看到一开始只有A进程，然后调入B, C进程，在d图里显示A又被调出，接着调入D，调出B。最后又把A 调入。很明显的A 进程的位置最后发生了变化。在重新调入的时候需要对调入位置进行重新定位, 基址寄存器和界限寄存器就是用于这种情况。可以发现在调入调出进程的过程中有一部分内存产生了空洞(hole),通过尽可能的将空洞内存往下移，可以将连续的空洞内存合成一块较大的内存。这个技术被称为内存紧缩(memory compaction)，但是这个操作比较浪费时间。还有个问题就是如果进程的内存大小不是固定不变，但是大部分进程都可以从堆中申请内存，如果一个进程的旁边是空闲内存，那么可以直接把空闲内存划分给进程，但是如果进程旁边是另一个进程内存，那么就需要将待交换的进程更换到更大空闲区去，或者把相邻的内存交换到其他空闲区或者调出到磁盘。如果一个进程内存不断增长，且磁盘交换区也满了，那么这个进程只能挂起或者结束。 为了避免频繁的交互和移动进程内存造成的开销，一种做法是在分配内存时分配额外的内存，但这么做就造成了再交换时，也将额外的不使用的内存交换了出去。

可以看到，在上图中比如A，除了A程序使用的内存，和A程序存放的数据，还预留了一部分A的堆栈内存，A程序使用的数据从底向上增长，A分配的堆栈自顶向下增长，当两者之间空闲区域被用完了，就将A进程交换出去。或者结束

空闲内存管理

一般内存管理有两种方式，利用位图和链表

位图

位图的思路很简单，将内存划分为小的几个字节或者几千个字节的分配单元，每个单元表示位图中的一位，0表示空闲，1表示占用。这么做的需要慎重考虑划分的分配单元的大小，比如4个字节占用一个位图和划分32个字节占用一个位图分别需要划分出1/4的内存或者1/32的内存来存储位图。看起来似乎分配单元划分的大一些比较好，但是分配单元划分的过大或导致分配时进程占用内存不是分配单元的整数倍时，最后一个分配单元中就会有一部分内存被浪费。而且在将k个分配单元的进程调入内存时，需要在位图中寻找到k个连续0，这个操作比较耗时还可能越界。

链表

链表的记录方式是维护一个进程P和空闲内存H的链表，每个链表包含指示标识(标识是P还是H)，起始地址，长度，下一个节点的指针。比如进程X，当进程X被终止后X处的位置被置为空闲内存，当两块空闲内存相连时，我们可以把两个链表节点合称为一个，这样链表节点少了一个但是获得了更大连续内存空间。有的链表甚至有双向指针，这样不仅能找到下一个节点的位置，还能方便的判断上一个节点的是P还是H确定是否能合并。

给链表分配内存的方法有多种

1. 首次适配算法(first fit) 沿着链表搜索，当找到足够大的空闲区域能容纳进程时，就将链表一分为二，一部分划分给进程使用，一部分新城新的H节点。对首次适配算法的改进是下次适配(next fit)算法，它的思想是不从头搜索，而是每次记录下搜索到的合适位置，下次搜索时从这个位置开始向下搜索，下次适配算法的性能略低于首次适配算法。
2. 最佳适配(best fit) 就是搜索整个链表，找到最接近进程需要内存大小的节点，将它分配给进程。但这么做很慢，而且会产生大量的无用的小内存区，因为它每次拆分的是最适合进程的内存区。事实上，因为这些无用的小内存区，最佳适配往往比首次适配浪费更多的内存。
3. 最差适配(worst fit) 和最大适配相反，就是它总是分配一个最大可用空闲区，这么做能避免产生大量小的内存区，但是大的连续内存块又被拆分了。仿真实验表示这也不是个好主意

分析上面4种算法，我们发现，如果将进程和空闲区分别用不同的链表表示，那么能极大的增加分配速率，比如分别用两个链表表示进程和空闲区，而且按照内存大小排序，那么要分配内存时，只需从小到大搜索节点，第一个遇到的节点就是最佳适配，也是首次适配(这时下次适配就没有意义了)。而且还节点中就不需要额外的表示是P还是H的标志了,但这么做的话释放/分配内存需要将一个链表的节点移动到另一个链表，这又比较慢。

还有一种分配算法叫做快速适配算法,它是将那些常用大小的内存区排序,并组织成链表,比如第一个节点是4K，第二个节点8K，第三个12K，以此类推。快速适配算法找到固定大小的内存时很快的，但是它的缺点也很明显，当进程终止时查看相邻快是否是空闲内存能否合并很慢，如果不合并，那么又会出现大量的无法利用的小空间

虚拟内存

产生虚拟内存技术的背景就是内存不够用，储设备增长速度跟不上软件使用内存增长速度。除了上面说的交换技术，早期的解决方式是覆盖(overlay),将程序切分为几个段，称为覆盖块，比如一开始装入覆盖0，其他覆盖块在磁盘中。当覆盖0执行完毕就调入覆盖1。覆盖技术很复杂且不易掌握，需要程序员将程序切分成很多段，这对于大型程序尤其难接受。所以没过多久就诞生了虚拟内存技术。

虚拟内存是为每个程序划分自己的地址空间，这个空间被分为多个块，块称为页面(page)。每个page有连续的地址空间，并不是所有page都必须在内存中才能运行程序，当程序引用一部分在地址空间时，由硬件程序执行必要的映射。当映射的地址不在物理内存中时，由操作系统将缺失的部分装入物理内存并重新执行失败的指令。当程序等待内存调入时，还可以把CPU交给其他程序运行。

分页(paging)

大部分虚拟内存都是用分页技术，程序产生的地址称为虚拟地址(virtual address)，这些虚拟地址构成了虚拟地址空间(virtual address space)。当进程访问虚拟地址时，不是将地址直接发送到内存总线，而是发送给内存管理单元MMU(memory management unit)。主流的MMU都是作为一个单独的芯片存在。(现代CPU，MMU则是CPU的一部分)

虚拟地址按照固定大小的page划分为若干单元，物理内存中对应的单元被称为页框(page frame)。page的大小不等，4K-1G均可能，甚至可以不同大小的page混用。

看下面这个例子，page0对应的物理地址是8192-12287，那么当执行对page 0的操作时，比如mov reg 0，会被MMU转换成mov reg 8192。可以看到虚拟地址空间是大于物理地址的，当访问一个不存在物理地址的page时，cpu会进入缺页中断/缺页错误(page fault),这时操作系统会选择一个很少使用的页框，将他的内容写入磁盘，将这个page frame原先对应的page里的标记置为不在，表示不在物理内存中。将需要使用的page对应的页框装载进内存，并将这个page的标识置为在，表示在内存中。

页表(page table)

页表是将页映射成页框的表格，比如对于一个16位的地址和4K的页，地址的高4位可以对应16个页，低12位可以对应在页中的偏移量，那么这么划分就可以表示出16个页表项，每个页表项对应4K的页框。实际上现代计算机的内存地址最大支持264,主流的主板则是支持239的地址，最大512G物理内存。好的主板甚至支持到了257的内存，不要认为地址位只跟操作系统有关，识别这些地址需要主板的支持，简单的说，一位需要一根线去读取里面的信息。

下面是页表内一个页表项的内容，页表项的实现和操作系统有关，但大致相同，里面每一项除了包含页框号，还包含一个额外的标志位，比如在/不在标志位，保护(P)标志位，0表示可读，1表示可写，还有的实现P位用了3个位，还有个X位表示是否可运行。修改(M)位也被称为脏位(D)，表示是否被修改过，在重新分配内存时，如果一个页是修改过得，那么必须写回磁盘，否则直接丢弃即可。访问位(r REFERENCED)。还有禁止高速缓存位。从数学上看，页表是一个转换函数，输入是虚拟页号，输出物理地址，它取出页对应的页框地址(即页框号)，再加上虚拟地址上低位的偏移量，得到对应的物理地址。

实际的页表实现很复杂，叫多级页表后面会说。(虚拟机内的页表会更加复杂包含影子页表和嵌套页表，但这不是重点我们不讲)

上面说的是大致原理，实际上去读虚拟地址时不会首先查找页表，而是查找MMU内的TLB(translation lookaside buffer页表的高速缓存，也叫做快表，存储最近转化的一些目录)，找不到再由table work unit去读取页表。在TLB里找不到需要查找的页表项时回去内存中查找页表，如果能找到，那这次时效称为软失效，如果内存里也不存在，那么称为硬失效，此时就需要操作系统从磁盘中读取页表调入内存，这种情况需要几毫秒的io，但在会对进程造成很大的延迟，它的处理时间是软失效的几百万倍。还有比硬失效更加严重的情况，比如引用了一个不存在的地址，这种情况称为段告错，属于程序错误。遍历页表的过程称为页表遍历。

多级页表

实际上页表的实现多是多级页表的，即将地址的高位再做拆分。我们可以计算一下多级页表和普通页表各自占用的内存。假设地址都是32位的，每个page映射4k的页框，每个指向页框的页表项占4B(因为32位地址大小就是4B)

假设页表不分级，就是只有一级页表，一级页表，那么总共可以有220个一级页表地址，即220个页表项，那么就需要1M * 4B = 4MB的地址存储页表，注意这只是一个进程的页表，每个进程都有自己的虚拟地址空间和页表。

如果是多级页表，下面这样，那么情况就会变化，首先需要210个存放一级页表的地址(注意存放一级页表也是需要页表的)，每个一级页表对应210个二级页表，那么总共就有220个二级页表，对应1M个二级页表项。那么总的页表占用的内存就是1K * 4B+1M * 4B = 4.004MB

可以看到多级页表占用的内存反而变大了，但是实际上，多级页表是更省内存的，因为大部分程序用不到4G内存，那么这个进程一级页表对应的二级页表也就不分配，假设一级页表只使用了20%,那么只需要划分出20%的一级页表和对应的二级页表，就是

0.2 * 1K * 4B + 0.2 * 1M * 4B = 0.8008MB,也就相当于4M内存的20%，这就节省了空间

实际上，除了结构上的省内存，二级页表也更加省内存，因为根据局部性原理，我们可以把一个二级页表里的相邻页都调入内存，其他间隔较远的内存存储在磁盘，这样就更省内存了。

其实我们看到在这里的页表的大小都是与逻辑地址的大小成正相关，而且多个进程会有多个页表，那有没有办法让页表不以逻辑地址的大小相关，而是以物理页的大小相关。这就是反向页表。(其他实现还有哈希页表)

以上说的是页表的结构，下面举一个例子来实际的体验虚拟地址和页表，以及物理地址的关系。

假设页面大小是4k = 212字节，系统为32位

那么总共就需要220个页表项，先不考虑多级页表。那就需要申请220的数组arr，以数组的下标表示第几个页表项，每个页表项的长度32位，即4字节

对于虚拟内存地址4095来说，取前20位为页表项编号，得到0号页表项,arr[0],假设arr[0]对应的是10号物理页框，那么物理地址就是10 * 4096 + 4095，在计算物理地址的过程中，虚拟地址的前20位就是页框号，后12位就是偏移量。

那么此时每个页表项中只有20位是用来表示页框号的，还剩下12位未使用，我们可以使用这剩下的位来存储标志位。这样就充分利用了内存。

每个进程的页表其实是存储在PCB中的

反向页表(invert page table)

反向页表的思想是以物理页的页帧号(页框号)来查找逻辑页的页号，但是实际上我们在访问内存时还是需要在根据页号来找到页帧号（为什么我已经知道页帧号，还需要再找到一个页号？其实这里注意反向页表不是单独存在的，它还是要配合虚拟内存的的页式内存管理机制来存在的。也就是还是使用的虚拟内存地址来访问。我们根据反向页表能找到一个虚拟内存的页号，然后进程再使用虚拟内存的页号去访问），但是这个查找的过程很慢，只能顺着页框表不断遍历，找到对应页的逻辑页。反向页表实际占用空间举例

物理内存 16M

页面(页帧)大小 4K

页帧数4096 = 4k

页寄存器使用空间（8byte每个地址）8 * 4096 = 32k

页寄存器带来的额外开销32k/16m = 0.2%(约等于)。可以映射任意大小的虚拟内存 ，就算打开100个进程也只占用这点内存。

但是很明显，如果每次访问内存都要遍历所有的页框表，那么肯定会影响进程性能，所以最好是将整个页表加载进TLB来加速页面查找。但是总会有不在内存的页面，也就是软失效。这时是需要知道怎么根据页号，来查找页帧号，只靠上面说的结构是做不到的，我们还需要额外的设计，比如关联存储器和相关存储器，这是种特殊的硬件，能够并行的查找页号的页帧号，设计复杂且关联内存昂贵而且如果关联存储器设计在CPU之外的话，很难做到在单个时钟周期内完成。

哈希页表

除了硬件的实现外，还有哈希的实现。哈希实现就是根据页号对应页帧号的hash函数,一般为了加速哈希函数的输入除了页号还有pid。当然使用哈希就存在哈希碰撞的问题，即两个虚拟地址对应一个页框地址。解决办法是将hash值相同的页表以拉链的方式连接在一起。(是不是和java里的拉链法hash函数的结构很像)

这种反向页表一般在高端的CPU比如PowerPC存在。哈希页表虽然减少了内存浪费但是增加查询时间和共享内存的难度。实际上哈希页表是结合在反向页表里来实现的。

END

下一期讲解一下虚拟内存的页面置换算法，大家多多点赞。