操作系统笔记-7-虚拟内存

引言

上一篇笔记讲述了内存的地址空间抽象，但是还留下了问题，那就是当软件很大的时候虽然利用Swapping技术可以运行，但是每次交换整个进程的空间开销不容忽视，虽然近年来内存也有增长，但是软件大小增长的速度远大于内存增长的速度。

一个解决方法是Overlays(覆盖)，Overlays将程序分割为多个片段，称为覆盖，当程序开始时，覆盖管理器加载覆盖0，执行完成后，通知覆盖管理器加载覆盖1，然后覆盖1会在覆盖0top上（如果有空间），或者直接在覆盖0（如果没空间）。虽然，换入换出覆盖块由操作系统完成，但是需要程序员将程序分块，这是一个复杂的工作，并且非常容易出错。因此这种技术无法普及，因此人们又提出了新的解决方案，这次是完全交给系统完成，那就是今天要学习的一个技术-虚拟内存。

基本概念

原理

每个程序都有自己独立的空间，并且这个空间分了多个固定大小的块，这些块通常叫做页，每一个页都有一个连续的地址范围，每一个页都映射一个物理范围叫页框（页框的大小通常和页是一样），程序运行不需要所有的页都在内存中，当程序引用到在物理内存中的地址空间时，由硬件（MMU）完成映射；如果不在内存中，由操作系统载入内存并重新执行失败的指令。

页框

物理内存中对应虚拟内存的页叫页框，大小和虚拟内存页大小一致。（RAM和磁盘交换数据是以页为单位的。有不同页面大小混合使用的）

虚拟地址

• 虚拟地址是程序在虚拟空间生成的地址，类似于上一篇讲的逻辑地址，它不是真实的物理地址，需要通过一定的转换才能得到物理地址。

• 简单虚拟地址结构，分为两部分，前n位表示页编号，后m位表示偏移量

  

• 一个例子：假设一个系统页大小为4Kb，而应用程序需要的空间为64Kb，虚拟页有16个，因此页编号需要4位，而偏移量需要12位，总共16位就可以表示虚拟地址

页表

• 页表是一个列表项的集合，最简单的虚拟地址分为两部分，前n位表示的页编号便是页表的索引（这里的页表是很简单的页表，后边在讲如何解决大虚拟内存时会讲到多级页表）

• 页表项示意图

  

  • Present/absent位，表示虚拟页是否在内存中

  • 保护位，简单用一个位0-r/w，1-只读。或者用3个位，分别表示可读、可写和可执行

  • 修改位，当一个页面被写入时该位会自动修改，表示该页是脏的
  • 引用位，当一个页面被访问时，该位会被设置，它的值可以用来帮助OS在缺页时选择被淘汰的页面
  • 禁止缓存位，设置该位代表该位禁止被缓存，用于I/O设备，如果I/O设备有独立的内存空间，该位不需要使用

• 不同计算机的页表项大小可能不同

内存管理单元(MMU)

• 作用： 解析虚拟地址映射的物理地址，数学形式：$F(VA) = PV$

• MMU工作示意图

  

• 虚拟内存映射物理内存示意图

  

  上图是程序的虚拟空间64K，内存是32K，页和页框为4K，可以看到0-4095映射到8192-12287

• MMU映射过程

  

  • MMU内部处理流程
    1. 虚拟地址8196取出高4位计算页表索引，0010表示2，因为找到索引为2的页表项
    2. 通过Present/absent位判断虚拟页是否在内存中，此处的值为1，说明在内存中，找到页框号110；否则MMU发现虚拟地址找不到映射的物理地址，使CPU陷入操作系统(缺页中断)，OS会选择一个很少使用的页框交换出去，重新执行陷入OS的指令
    3. 将页框号+上偏移量就是物理内存地址，放到bus上

分页问题

加速分页-TLB

• 分页系统面临的两个问题

  1. 虚拟内存地址映射为物理内存地址必须快
  2. 如果虚拟地址空间很大，那么页表空间也要很大

• 解决方案-TLB(转换检测缓冲区)

  • 原理：通过观察，大部分的程序多数情况都是反复访问很少的的页，也就是说，只有很少的页被反复访问，大多数页很少访问，TLB硬件一般在MMU里。TLB示意图

    

• MMU硬件TLB管理

  当TLB失效时，有MMU硬件负责查找并且装载，主要的好处是一个简单的MMU可以节省芯片的很多空间让给缓存和其他可以提升性能的组件，TLB工作原理图

  

• 软件TLB管理

  当TLB失效时，会生成一个TLB失效并将问题交给OS解决，查找和装载TLB由OS完成

  • 减少TLBmiss：OS会预加载，系统推断接下来需要使用的页
  • 降低TLB miss时的开销
    • 存在问题：如果用软件管理TLB，当TLB实现时，会通过搜索页表索引页，假如此时存放页表的页不在TLB中，就会引起二次TLB失效
    • 解决办法：在内存上固定区域维护一个大（比如4KB）的TLB表项的缓存，该固定区域的页一直在存在TLB中，当TLB实现时，先查找TLB的缓存
  • TLB miss类型
    • soft miss(软失效)：TLB未命中，但是页在内存中
    • hard miss(硬失效)：TLB未命中，且页不在内存中，开销将非常高
    • minor page fault(次要缺页错误)：页不在该进程的页表中，但是在内存中，在其他进程的页表中，这一种只需要在进程的页表中简单的更新映射
    • major page fault(严重缺页错误)：页需要从磁盘调入
    • segmentation fault(段错误)：程序访问非法地址

大内存页表问题

• 问题：如果内存非常大，那么页表也很大，比如4G的内存，采用4KB的页大小，那么页表将有100w个页表项，因为页可能分散在内存的各个页框，所以需要维护这个包含100w个页表项的页表，并且有多少个进程就有多少个这种页表，非常浪费空间。

• 分级页表

  • 原理：采用多级的设置，可以避免始终保持所有的页表在内存中。比如一个进程所需空间进程上下文4M，Data段4M，Stack段4M，总共需要12M，因此虽然虚拟页表还是很大，但是很多都是没有用到的，这些没有用到的页表不应该保存在内存中，而采用两级页表时，只需要保存4个页表，一个顶级页表，一个0-4M、一个4-8M，一个8-12M3个2级页表。顶级页表除了0，其他的页表项Present/absent都会设置为0，每个进程的页表都是独立的

    

    上图a中PT1、PT2分别表示一级页表索引和二级页表索引。上图中一个进程只用3个顶级页表，而其他页表在/不在位被设置为0，当这些不在页表被访问时，会产生一个缺页中断，OS会做处理，这时访问了不该访问的内存。

  • 4级页表，4k的页，每级页表用9位索引，最大支持256TB内存

    $2^9 * 2^9 * 2^9 * 2^9 * 2^{12} = 2^{48}$bytes

• 倒序页表

  • 解决的问题：64位地址下的页表会非常大，并且每个进程还有自己独立的页表

  • 原理：传统的页表是通过虚拟地址查找对应物理页，但是每个物理页同一时间只能对应一个进程。所以，可以将传统的页表的表项由虚拟页换成页框，这样页表就会小了很多，当搜索的时候利用进程+虚拟页来查找。搜索需要软件实现，可以借助hash结构，倒序页表示意图

    

  • 倒序页表工作示意图

    

页面置换算法

页面置换算法其实就是缓存淘汰算法，因为可以将高速容量小的存储设备看成低速容量大的存储设备的缓存，那么其实主存就是磁盘的缓存，所以这些页面置换算法都是通用的缓存淘汰算法

最优页面置换算法

• 原理：用页面需要访问前执行的指令数来标记，置换标记数大的。将缺页中断尽可能推迟

• 缺点：不可实现，因为OS不知道各个页面将在什么时候被访问

• 一个例子，当页框为7-0-1要载入2时，选择7置换出去，因为后续页的访问顺序 0->1->7，7在更远的时间线上才会使用

  

最近未使用页面置换算法（NRU）

• 原理：为了统计虚拟页面使用信息，用两个状态位R和M来标识，页面被访问时R（读/写）会被设置，页面被写入（修改）时M会被设置。周期性将R位重置，M位不会被重置，因为不知道该修改的页是否写回了磁盘。将会有以下几种情况

  1. class 0: 没有访问，没有修改
  2. class 1: 没有访问，已修改
  3. class 2: 被访问，没有修改
  4. class 3: 被访问，已修改

  NRU算法随机从类编号（class 0-3）最小的非空类中挑选一个页面置换，它的核心思想置换一个已修改的但未被访问的页比置换一个“干净”但频繁访问的页更好。

FIFO页面置换算法

• 原理：链表存储页面装载，发生缺页中断时，用链表头交换

• 优点：低开销

• 缺点：老的页面可能是频繁使用的，由于这个原因，该算法很少使用

• 一个例子，假设这里有三个页框，上边的数字代表虚拟页，下边是页框里映射虚拟页的变化

  

第二次机会页面置换算法

• 原理：该算法是在FIFO上修正置换频繁使用页面问题，当缺页中断发生时，取出最老的页面判断R标记，如果为0，立即置换，如果为1，则置为0并放入链表尾，并且更新它的载入时间，然后遍历后边的次老页面，直到找到一个满足条件的页面

  

• 缺点：需要在链表中移动页面

时钟页面置换算法

• 原理：解决第二次机会页面置换算法，需要在链表中移动页面。将链表以时钟的形式展示：如下图，一个指针指向最老的页表，缺页发生时，检查R标记为0直接置换，为1清除R标记，指针指向下一个页面

  

最近最少使用(LRU)

• 原理：置换未使用时间最长的页面。用特殊硬件实现64位原子自增器C，每执行一条指令C原子自增1，并将该值设置访问的页表项，缺页发生时，检查页表中该计数值，最小的就是最近最少使用的页面

• 缺点：需要硬件支持

• 一个例子

  

软件模拟LRU(NFU)

• 原理：每个页表项有一个计数器，每当时钟中断时，OS扫描内存中的所有页表，读取R标记（0/1）加到计数器上，等到缺页时，选择计数最低的置换

• 缺点：计数器不会忘记计数值，假设一个页表在第一阶段频繁使用，但是第二阶段时不常使用，会使得在第二阶段时该页表依然具有很高的计数。第二阶段开始将会频繁使用的页表因为执行时间短，计数低，被不幸的置换出去

• 优化：一个小优化可以使得NFU可以接近LRU的表现，每次将R位加到计数器时，先将计数器右移一位，然后将R值加到计数器左端而不是右端。这样可以让页表在不使用时指数方式衰减

• 一个例子

  

• 和LUR的区别

  1. 上图的page3和5在e的时候，前两次都没有访问过，而在前两次之前的同一个时钟周期都被访问过，则根据LRU规则，3和5页面的计数值是一样的，所以会从中选择出一个页面置换；而NFU规则，会选择页面3置换，因为页面5在更早之前被访问过
  2. 第二个区别是，NFU的计数器有位数限制，本例为8，超过8个时钟周期，早期的记录便会丢失，如前9周期和前1000周期将会被视为一样，LRU不会

工作集页面置换算法

• 理论：大部分进程都表现出局部性访问特性。在一个阶段只会访问少部分的页，找出工作集，发生缺页时，找出不在工作集中的页置换出去

• 假设用$w(k,t)$代表t时刻k次内存访问的工作集，那么工作集大小和选择k的关系，$w(k,t)$不会无限变大，因为进程不可能访问比它地址空间所能容纳页上限还多的页面

  

• 作用：在多道程序设计系统中，经常把进程交换到磁盘上让其他进程运行，当进程恢复运行时，进程会不断的发生缺页直到它的工作集全部载入内存。利用工作集，可以在程序运行前，将工作集载入内存，就不会频繁发生缺页。

• 实现

  • 最初设想：硬件实现，每进行一次内存访问，就左移一位，然后在最右边插入最新访问的页号，缺页发生时读出寄存器中的值，然后排序和去重，剩下的便是最近k次内存访问的工作集。维护该寄存器和处理缺页开销太大，导致实际没有使用这种方案

  • 替代方法：用时间来代替k次统计工作集，有一个定期的时钟中断用软件方法清除R位，发生中断时，会遍历页表项，判断R位结合最近上次访问时间来决定哪个页面置换出去具体算法如下

    1. 当R==1时，将实际时间写入页表项的上次使用时间
    2. 当R==0时，则该页作为置换候选项，计算实际时间和上次使用时间的间隔作为生存时间，然后与阈值时间对比，如果大于该阈值，则该页被置换
    3. 当R==0，且生存时间小于阈值，则把它留下来但是要记录上次使用时间的最小值
    4. 如果扫描完成都没有满足的，则选择R==0的生存时间最长的淘汰
    5. 如果没有R==0的则最好选择一个干净的页面淘汰

    示意图如下

    

工作集时钟置换算法

• 原理：由于工作集页面置换算法，在扫描整个列表，才能确定被置换的页面，开销比较高，所以出现了工作集时钟页面置换算法，该算法会记录最近一次使用的时间，具体算法如图

  

• 缺页时情况

  1. 如果R=1，说明在当前时钟滴答内被访问过，将R位置为0，指向下一个节点
  2. 如果R=0且M=0，判断当前实际时间-最近使用的时间是否大于阈值，如果大于，直接置换该页，否则指向下一个节点
  3. 如果M=1，考虑到此时置换当前页会调度磁盘可能导致进程切换，指向下一个节点

• 扫描回到起点的情况

  1. 至少调度过一次写操作，只需移动指针寻找到第一个调度过写操作的页面（这个页面并不一定是需要第一个调度写操作的页面，因此磁盘为了优化，通常对写操作会重排序）
  2. 没有调度过写操作，随便选择一个干净的页面置换（扫描过程中要记录干净的页面），如果没有干净的页面，就置换当前指针指向的页面

分页设计和实现问题

局部分配和全局分配

• 页面置换时，只能从进程自己分配的页框中选择置换，全局分配页面置换算法作用域是全局页框的。如下例子

  

  当进程A发生缺页中断时，如果采用局部分配，那么A5将会被替换出去；如果采用全局分配，那么B3将会被替换出去

• 通常全局分配比局部分配更好，因为局部分配算法，随着工作集增大，缺页会越来越频繁；但是当工作集减小时，局部算法又会浪费内存

• 全局分配算法实现

  1. 检测工作集大小，工作集大小由“老化”位指出，但是不能防止颠簸，因为工作集大小可能在几微秒内变化
  2. 定期会确定运行的进程的数目为进程分配等额的内存，看似公平，但是通常进程需要的内存不同，比如为30Kb和300Kb分配同样的内存是不合理的
  3. 按进程大小的比例来分配内存，但是必须程序运行时动态更新，管理内存动态分配的一种方法是PFF(缺页中断率)
  4. 比较明智的方法是为进程分配一个最小的内存

• PFF(缺页中断率)

  用来管理动态为进程增加和减少页框。但是仅仅是控制分配集大小。下图是PFF示意图，A代表高缺页中断率，应该分配内存。B则代表有低中断率，有空余的内存。

  

负载控制

• 问题：当所有进程组合的工作集需要的内存超过了内存的容量，那么会引起颠簸。一个现象是OS中所有进程PFF都很高，则表示所有的进程都需要额外内存，但是没有进程需要更少的内存，则该种情况所有进程都会颠簸
• 解决办法：减少运行的进程。可以将进程交换出去，释放占用的页框，然后分配给其他颠簸的进程。交换进程到磁盘还要考虑，在多处理器系统中，过低的进程会浪费CPU周期，所以交换时不光考虑进程大小和分页率还要考虑进程的特性(计算密集型还是I/O密集型)

分页大小

• 内部碎片：程序的代码段、数据段和栈段在分页时，通常最后一页不能刚好装满，最后一页估计会浪费$\frac{1}{2}$的空间。假设内存有n个段，页大小为p bytes，所以内存的内部碎片为

  $$wasted = \frac{np}{2} bytes$$

• 选择小页面的好处

  1. 减少内存碎片
  2. 减少内存浪费，假设页大小为32Kb，一个进程分为个阶段，每个阶段需要4Kb，那么进程有28Kb的空间都属于浪费的

• 选择大页面的优点

  1. 页表更小
  2. 相对小页面会占用更少的TLB，TLB是非常昂贵的
  3. 在某些机器，进程切换时，会将页表载入硬件寄存器，小页面页表更大，因为花费时间比大页面长

• 平衡：OS在系统中采用不同的页面大小，内核采用大页面，而用户空间程序采用小页面

• 数学分析：假设进程平均大小为s bytes，页大小为p bytes，页表项大小为e bytes，需要的页表项空间为$\frac{es}{p}$，内部碎片为$\frac{p}{2}$，因此一个进程的空间开销为

  $$overhead = \frac{es}{p} + \frac{p}{2}$$

  因为要求p的大小的最优值，对p求导，并令等式等于0

  $$-\frac{se}{p^2}+\frac{1}{2} = 0$$

  p的解为 $p = \sqrt{2se}$，假设s为1MB，e为8bytes则p为4KB

分离指令和数据空间

• 存在问题：如果地址空间足够大，a的模型是ok的，但是如果地址空间小，就出现问题。程序空间示意图

  

• 一种解决方法

  PDP-11分离指令和数据空间，如上图的b，使用此种模型，链接器必须知道何时使用分离的I-space和D-space，因为数据被重定位到虚拟空间的0而不是在程序之后。它们有独立的页表

• 现实应用

  虽然如今的普遍的x64架构应用64位地址，地址空间已经足够大。但是指令和数据空间分离还是有广泛的应用，比如CPU的L1缓存

共享页

• 存在问题：一个系统可能同时运行多个相同的程序或者几个用了相同库的程序，想象一下，即使相同的程序同时运行，系统要分配给它们独立的内存，但是程序的代码段是相同且不会改变的，如果能在同时运行时，内存只维护一个代码段，那就可以节省很多的空间；相同库也是一样的道理

• 解决办法-利用指令和数据空间分离

  

  为了防止进程被换出而导致共享页被换出，但是全局扫描哪些页是共享的开销很高，因此需要一个特殊的数据结构来跟踪共享页

• 数据页共享-利用写时复制技术

  Linux中当父进程创建子进程时，因为子进程要共享父进程的代码和数据，因此代码页和数据页都是进程共享的。但是此时共享的数据页都是只读状态，一旦进程对数据页发生写操作，就会陷入内核，系统便会重新拷贝一个副本，这时两个进程的页表分别指向该页的独立副本，页状态也被改为可读写。如下图的b

  

共享库

• 传统静态链接

  程序编译时，在目标文件中调用但是没有定义的函数(未定义外部函数)，链接器会查找外部库，找到了该函数的代码，然后加入到当前编译的可执行文件中存入磁盘。注意：这个可执行文件中是包含了外部库的方法的代码，如果有多个程序都用了该库，那么每个程序的可执行文件都包含库的代码，并且执行的时候也会有独立的内存存放这些相同的代码。

• DLL(动态链接库)

  程序编译时，当遇到调用目标文件中没有定义的外部函数时，不在将库中方法的代码加入可执行文件，而是载入一个运行时可以与被调用库的函数绑定的存根例程。依赖系统和配置信息，共享库和程序一起加载到内存或者运行到第一次调用库函数时加载，如果其他程序已经加载那么就不需要再次加载了

• 位置无关代码：解决库在不同程序调用载入时重定位的问题，如下图，如果进程1在载入共享库时，重定位了共享库的代码，那么进程2再调用时会导致问题，解决办法就是避免使用绝对地址，使用相对偏移量

  

清除策略

• 如果发生缺页时，系统有大量空闲内存时，此时分页系统工作在最佳状态
• 实现：利用一个后台进程(分页守护进程)定期检查内存，当发现空闲内存较少时，会根据预定的算法置换一些页面出去。利用双指针的结构，当置换算法选择了页置换时，如果页是修改过的，那就写回磁盘，然后加入链表头；如果缺页发生时，就从链表的尾部取空闲页。假如，此时缺页是正好被分页守护进程回收的页且还没被覆盖，那么就直接恢复不用从磁盘载入

虚拟内存控制

通常虚拟内存对开发人员都是透明的，但是某些高级系统提供了虚拟内存的控制。主要是用来实现不同进程间共享内存

• 用途：实现高性能消息传递系统，可以避免进程间消息传递时，数据从一个地址空间复制到另一个地址空间(开销很高)

缺页处理流程

1. 缺页发生时陷入内核，保存程序计数器
2. 启动一个汇编例程保存通用寄存器和其他易失性信息，以免被系统破坏；
3. OS发现缺页中断，尝试发现需要哪个虚拟页面，如果没有，则取出导致缺页执行的指令用软件分析，该指令在缺页时做什么操作
4. 检查该地址是否有效且请求的操作与保护权限是否一致，如果不一致，则为非法访问，向进程发一个信号或者杀掉进程。如果有效且没有发生错误，则检查内存是否有空闲的页框，如果没有则执行页面置换算法
5. 如果选出需要置换的页是修改过的脏页面，则需要先将修改写回磁盘，因为是阻塞操作，则发生上下文切换，挂起中断处理进程（OS内核进程），直到写回数据完成，写的过程中该页框会被设置为忙，防止其他进程操作
6. 该页面干净后需要找到需要调入的页的磁盘地址，调入页面，该操作也是阻塞的，中断处理进程被挂起，直到磁盘发出中断，页表被更新，载入页面完成
7. 恢复发生缺页中断指令以前的状态，程序计数器指回缺页的指令
8. 调度引发缺页的进程，操作系统返回调用它的汇编例程
9. 例程恢复寄存器和其他状态信息，返回用户空间继续执行，就像没有发生过缺页

交换空间实现

• 将整个进程按照程序text，data，statck全部映射到swap区中。每个进程分有固定大小的区，如图

  

• 进程开始时不映射到swap区，仅当发生交换时，将换出的页面写入swap区，但是需要在内存中建一个映射表（disk map）来映射换出的页

  

分段

总结

这一部分讲了虚拟内存的原理以及调度算法，下一篇将会学习高速缓存。