【操作系统】虚拟内存总结

虚拟内存技术的基础：离散内存分配，即进程的逻辑地址空间分散地存储在内存不连续的物理地址空间中，典型的技术有：分段、分页、段页式。

虚拟内存的基本思想是：每个程序拥有自己的地址空间，这个空间被分割成多个块，每个块被称作一页或页面。每一页有连续的地址范围，这些页被映射到物理内存，但并不是所有的页都必须在内存中才能运行程序。当程序引用到一部分在物理内存中的地址空间时，由硬件立刻执行必要的映射。当程序应用到一部分不在物理内存中的地址空间时，由操作系统负责将缺失的部分装入物理内存并重新执行失败的指令。

1、虚拟地址

由程序产生的这些地址成为虚拟地址,它们构成了一个虚拟地址空间

• 在没有虚拟内存的计算机上，系统直接将虚拟地址送到内存总线上，读写操作使用具有同样地址的物理内存字
• 在使用虚拟内存的情况下，虚拟地址不是被直接送到内存总线上，而是被送到内存管理单元（MMU），MMU把虚拟地址映射为物理内存地址。

虚拟地址空间按照固定大小划分成被称为页面的若干单元。在物理内存中对应划分成的单元被称为页框

如果想要访问的虚拟地址（页面）没有映射到物理内存，则会引发一个缺页中断。此时操作系统会采用页面置换算法，将需要置换的页框（即映射的页面）的内容写入磁盘，随后把想要访问的页面读到刚才回收的页框中（映射），然后重启刚才的指令。

2、MMU内存映射规则

在图3-10中可以看到一下虚拟地址的例子，虚拟地址8196（二进制是 0010 0000 0000 0100）用图3-9所示的MMU映射机制进行映射，输入的16位虚拟地址被分为4位的页号和12位的偏移量。4位的页号可以表示16个页面，12位的偏移量可以为一页内的全部4096个字节编址。

可用页号作为页表的索引，以得出对应于该虚拟页面的页框号。

如果"在/不在"位是0，则引起一个缺页中断。如果该位为1，则将页表中查到的页框好复制到输出寄存器的高3位中，再加上输入虚拟地址中的低12位偏移量，如此就构成了15位物理地址。输出寄存器的内容随即被作为物理地址送到内存总线。

3、页表

页表内部包含的是一条条的页表项，每条页表项都是一个页面和一个页框的对应关系。换句话说页表中保存的是页面和页框的映射（类似于hash）。

页表的目的是把虚拟页面映射为页框。从数学的角度说，页表是一个函数，它的参数是虚拟页号，椰果是物理页框号。

虚拟页号可以作为页表的索引，以找到该虚拟页面对应的页表项。由页表项可以找到页框号（如果“在位”的话）。然后把页框号拼接到偏移量的高位端，已替换掉虚拟页号，形成送往内存的物理地址。

作为一种最简单的实现，虚拟地址到物理地址的映射可以概括如下：虚拟地址被分为虚拟页号（高位部分）和偏移量（低位部分）。偏移量最大值可近似表示页框和页面（页框和页面的大小通常相同）的大小，虚拟页号最大值则可近似表示虚拟页面的数量。

（1）页表项结构

页表项的结构是于机器密切相关的，但不同机器的页表项存储的信息都大致相同。图3-11中给出了页表项的一个例子。不同计算机的页表项大小可能不一样，但32位是一个常用的大小。

• 页框号

  页表映射的抓哟目的是找到这个值

• “在/不在”位

  • 为1时，表示该表项是有效的，可以使用
  • 为0时，则表示该表项对应的虚拟页面现在不在内存中，访问该页会引起一个缺页中断

• 保护位

  指出一个页允许什么类型的访问。最简单的形式是这个域只有一位，0表示读写，1表示只读。更先进的方法是使用三维，各位分别对应是否启动读、写、执行该页面。

• 修改位

  在写入一页时由硬件自动设置修改位。如果是一个页面已经被修改过（即它是“脏”的）则必须把它写回磁盘。如果一个页面没有被修改过（即它是“干净”的），则只简单地把它丢弃就可以了。

• 访问位

  无论是读还是写，系统都会在该页面被访问时设置访问位。它的值被用来帮助操作系统在发生缺页中断时选择要被淘汰的页面

• 高速缓存禁止位

  通过这一位可以禁止高速缓存。

4、加速分页

在任何分页系统中都需要考虑的两个问题：

• 虚拟地址到物理地址的映射必须非常快
  • 每条指令会进行一两次或更多次的页表访问。如果执行一条指令需要1ns，页表查询必须在0.2ns内完成，以避免映射成为一个主要瓶颈。
• 如果虚拟地址空间很大，页表也会很大
  • 假设页面大小为4KB，则32位就有100万页面（页表项），64位则更多。而且每个进程都需要自己的页表（进程有自己的虚拟地址空间）

（1）转换检测缓冲区（快表）（解决快速分页问题）

大多数程序总是对少量的页面进行多次访问，而不是相反。因此只有很少的页表项会被反复读取，而其他的页表项很少被访问。

根据上述观察，提出一种解决方案：为计算机提供一个小型的硬件设备，将虚拟值直接映射到物理地址，而不必再访问页表。这种设备称为转换检测缓冲区(TLB),有时又称为相联存储器或快表

• TLB的的工作机制

  将一个虚拟地址放入MMU中进行转换时，硬件首先通过将该虚拟页号与TLB中所有的表项同时进行匹配，判断虚拟页面是否在其中。

  • 如果发现一个有效的匹配而且要进行的操作并不违反保护位，则将页框号直接从TLB取出而不必访问页表
  • 若没有有效的匹配，就会进行正常的页表查询。然后淘汰TLB中的一个表项，然后用新找到的页表项替代它。

（2）软件TLB管理

现在已经假设每一台具有虚拟内存的机器都具有由硬件识别的页表和一个TLB。在这种设计中，对TLB的管理和TLB的失效处理都完全由MMU硬件来实现。只有内存中没有找到某个页面时，才会陷入到操作系统

但是在许多现代的机器上，几乎所有的页面管理都是在软件中实现的。在这些机器上TLB表项被操作系统显式地装载。当TLB访问失效时，不再是由MMU到页面表中查找并取出需要的页表项，而是生成一个TLB失效并将问题交给操作系统解决。系统必须先找到该页面，然后从TLB中删除一个项，接着装载一个新的项，最后再执行先前出错的指令。

无论是用硬件还是用软件来处理TLB失效，常见的方法都是找到页表并执行索引操作以定位将要访问的页面。用软件做这样的搜索的问题在于，页表可能不再TLB中，这就会导致处理过程中的额外的TLB失效。可以通过在内存中的固定位置维护一个大的（如4KB）TLB表项的软件高速缓存来减少TLB失效

当使用软件TLB管理时，需要理解两种不同的TLB失效的区别在哪。

• 软失效

  一个页面访问在内存中而不在TLB中时，将产生软失效

• 硬失效

  一个页面访问不在内存中（也不再TLB中），将产生硬失效

实际情况未命中的情况可能既不是软失效或者硬失效。如果发生了一个缺页中断，则可能出现三种情况：

• 次要缺页错误

  所需的压面可能就在内存中，但却没有记录在进程的页表里，这种情况只需要把所需要的页面正确映射到页表中。

• 严重缺页错误

  如果需要重新从硬盘调入页面

• 段错误

  程序访问了一个非法的地址，根本不需要向TLB中新增映射。

5、针对大内存的页表

（1）多级页表

多级页表的简单例子如图3-13所示，在图3-13a中，32位的虚拟地址被划分为10位的PT1域，10位的PT2域和12位的Offset（偏移量）域，因为偏移量是12位，所以页面的大小是4KB，共有2²⁰个页面。

引入多级页表的原因是避免把全部页表一直保存在内存中。特别是那些从不需要的页表就不应该保留。

如图3-13b，在左边是顶级页表，它有1024个表项，对应于10位的PT1域。当一个虚拟地址被送到MMU时，MMU首先提取PT1域并把该值作为访问顶级页表的索引。因为整个4GB（32位）虚拟地址空间已经按4KB大小分块，所以顶级页表中这个1024个表项每一个都表示4M的块地址。

由索引顶级页表得到的表项中含有二级页表的地址或页框号。顶级页表的表项0指向程序正文的页表，表项1指向数据的页表，表项1023指向堆栈的页表，其他表项（阴影）未用。现在把PT2域作为访问选定的二级页表的索引，以便找到该虚拟页面的对应页框号。

给出一个多级页表映射的例子。考虑32位虚拟地址0x00403004（十进制 4206596）位于数据部分12292字节处。它的虚拟地址对应PT1=1，PT2=3，Offset=4。

• MMU首先用PT1作为索引访问顶级页表得到表项1，它对应的地址范围是4M到8M-1。
• 然后它通过PT2作为索引访问刚刚找到的二级页表并得到表项3，它对应的虚拟地址范围是在它的4M块内的12288 ～16383（即绝对地址4206592~4210687）。
• 这个表项含有虚拟地址0x00404004所在页面的页框号。
  • 如果该页面存在于内存中，则从二级页表中得到的页框号将于偏移量4结合形成物理地址
  • 如果该页面不存在于内存，则引发一次缺页中断

（2）倒排页表

在倒排页表这种设计中，实际内存中的每一个页框对应一个页框，而不是每个虚拟页面对应一个表项。

传统页表的设计是每个页对应一个页表项，倒排页表的设计是每个页框对应一个页表项。例如32位，1GB内存的计算机，页面和页框的大小位4KB，则传统页表有2²⁰个页表项，而倒排页表只有2⁸个页表项，比传统的页表小一些。

页面置换算法

当发生缺页中断时，操作系统必须在内存中选择一个页面将其换出内存，以便为即将调入的页面腾出空间。如果要换出的页面在内存驻留期间已经被修改过，就必须把它写回磁盘以更新该页面在磁盘上的副本；如果该页面没有被修改过（如一个包含程序正文的页面），那么它在磁盘上的副本已经是最新的，不需要写回，直接用调入的页面覆盖被淘汰的页面就可以了

（1）最优页面置换算法（OPT）

• 置换未来需要或最远的将来才会使用的页面
• 此算法不可能实现

（2）最近未使用算法(NRU)

当发生缺页中断时，操作系统检查所有的页面并根据它们当前的R位(读取）和M位（修改）的值，把他们分为4类：

• 第0类，R=0,M=0
• 第1类，R=0,M=1
• 第2类，R=1,M=0
• 第3类，R=1,M=1

NRU算法随机地从类编号最小的非空类中挑选一个页面淘汰。

NRU的优点是：易于理解和能够有效地被实现

（3）先进先出页面置换算法（FIFO）

由操作系统维护一个所有当前在内存中的页面的链表，最新进入的页面放在表尾，最早进入的页面放在表头。当发生缺页中断时，淘汰表头的页面并把新调入的页面加到表尾。

• FIFO会出现一个现象：当分配给进程的物理页框数增加时，缺页次数反而增加了。

（4）第二次机会页面置换算法（SCR）

FIFO算法可能会把经常使用的页面置换出去，为了避免这一问题，对算法做一个简单的修改：检查最老页面的R位。如果R=0，那么这个页面既老又没有被使用，可以立即置换掉；如果R=1，就将R位清0，并把该页面放到链表的微端，修改它的装入事件和新装入的一样，并且继续搜索。

（5）时钟页面置换算法

SCR经常要在链表中移动页面，既降低了效率又不是很有必要。一个更好的办法是把所有的页面都保存在一个类似钟面的唤醒链表中，一个表指针指向最老的页面。

当发生缺页中断时，算法首先检查表针指向的页面，如果它的R位是0就淘汰该页面，并把新的页面插入这个位置，然后把表指针前移一个位置；如果R=1，就清除R并把表针向前移动一个位置。

（6）最近最少使用页面置换算法（LRU）

LRU的实现：在发生缺页中断的时候，置换未使用时间最长的页面。

虽然LRU在理论上可以实现，但代价很高。为了完全实现LRU，需要在内存中维护一个所有页面的链表，最近最多使用的页面在表头，最近最少使用的页面在表尾。困难的是在每次访问内存时都必须要更新整个链表。在链表中找到一个页面，删除它，然后把它移动到表头是一个非常费时的操作，即使使用硬件实现也一样费时。

总结

将机器的物理内存划分为多个独立的称为**段**的地址空间。每个段是由一个从0到最大的线性地址序列构成。各个段的长度可以是0到某个允许的最大值之间的任何一个值。不同的段的长度可以不同，并且通常情况下也都不相同。段的长度在运行期间可以动态改变，比如堆栈的长度在数据被压入时会增长，在数据被弹出时又会减小。

优点：

• 因为每个段都构成了一个独立的地址空间，所以他们可以独立地增长或减小而不会影响到其他的段。

• 如果每个过程都位于一个独立的段中并且起始地址是0，那么把单独编译号的过程链接起来的操作就可以得到很大的简化。当组成一个程序的所有过程都被编译和链接好以后，一个对段n中过程的调用将使用由两个部分组成的地址（n，0）来寻址到字0（入口点）。如果其中一个段修改，只需要编译其中一个段，而不用编译其他的段。

• 有助于在几个进程之间共享过程和数据。常见的例子就比如共享库

分段分页的比较

分页的优点：

• 统一的页面大小
• 可以只加载使用的一部分而不用把它全部调入内存

分段的优点：

• 易于编程、模块化、便于保护和共享

分页和分段相结合：MULTICS

它为每个程序提供了最多2¹⁸个段，每个段的的虚拟地址空间最长为65535个（36位）字长。为了实现它，MULTICS的设计者决定把每个段都看做一个虚拟内存并对它进行分页，以结合分页和分段的优点。

每个MULTICS程序都有一个段表，每个段对应一个描述符。因为段表可能会有25万多个表项，段表分身也是一个段并被分页。一个段描述符包含了一个段是否在内存的标志，只要一个段的任何一部分在内存中这个段就被认为是在内存中，并且他的页表也会在内存中，如果一个段在内存中，它的描述符将包含一个18位的指向它的特表的指针（见3-34a）

分段和分页相结合：Intel x86

• 现代操作系统都使用某种形式的虚拟内存。使用的技术有分页、分段、段页式。

• 最简单的情况下，每一个进程的地址空间被划分位同等大小的块，称为页面，页面可以被放入内存中任何可用的页框。有多种页面置换算法用于缺页中断时淘汰页面。

• 如果要处理在执行过程中大小有变化的数据结构，分段是一个有用的选择，它还能简化链接和共享。不仅如此，分段还有利于为不同的段提供不同的保护。