虚拟内存（Virtual memory）

背景

前面主存用到的策略都有一个基本的要求：正在执行的指令必须在物理内存中。
第一种方法是将整个逻辑地址空间放到物理内存中。

• 首先，它限制了一个程序的大小不能超过实际的物理内存的大小；
• 其次，许多情况下，整个的程序的所有路径并不会都覆盖到，比如大的数据结构，很少会遇到的异常处理代码；（空间上）
• 最后，在整个程序的所有路径都能覆盖到的情况下，也不是同时会覆盖整个程序。（时间上）

第二种方法就是具备执行部分加载的程序的能力

• 程序大小不再受限于物理内存大小；
• 每个程序运行时占用更少的内存，但更多的程序运行时间
• 更少的IO 需要加载或swapin 程序到内存中，每个进程运行更快

虚拟内存（Virtual memory）-将物理内存隔离开来

• 执行时只需要程序的一部分在内存中；

• 逻辑地址空间可以远大于实际的物理内存；

• 多个进程可以共享内存空间；

• 允许更多并发运行的程序；

• 需要更少的IO 去加载进程或swap 进程；

  
  image.png

• 虚拟地址空间-进程在内存中的逻辑视图
  i) 从地址0开始直到最后的连续地址空间；
  ii) 栈空间从MAX 逻辑地址空间开始，向下增长；堆向上增长；
  iii) 最大空间使用率
  ix) 中间不是的部分（hole)

• 物理内存是以page frame为最小单位组织的；

• MMU 负责虚拟地址到物理地址的映射;

image.png

• 运行的多个进程文件共享和内存共享

  • lib 库可以被多个进程共享；

  • 多个进程可以 共享内存，比如进程通过共享内存通信；

• 进程创建过程用fork 共享的page 可以加速进程创建

image.png

• 虚拟内存的实现方式：

  • 按需分页（Demand paging）

  • 按需分段（Demand segmentation）

按需分页（Demand paging）

• 不是加载的阶段就把整个程序都加载进内存，而是在需要一个page的时候加载它

• 好处

  • 需要更少的IO，没有不必要的IO

  • 需要更少的内存

  • 更快的响应

  • 可以运行更多进程，提高多程序设计能力

  • 更高CPU利用率和带宽

• 类似于带swap的分页系统

• page 引用

  • 无效的引用==> 中止

  • 有效的但是在辅存中==> 加载到内存中

• 基本实现

  • 页表项增加valid-invalid bit, 以区分在内存否
    i）valid bit: 在内存中
    ii）invalid bit: 不在内存中
    iii) 初始化valid-invalid bit 成invalid bit

    
    image.png

  • MMU 实现区分valid- invalid功能

    • 在MMU 地址转换过程，若页表项的valid- invalid bit 为 invalid 位时，产生缺页错误（page fault）

  • 辅存（swap 空间）

  • 指令重新执行

  • 缺页错误（page fault）
    处理步骤：
    1.初次引用一个页会陷入OS，产生缺页错误
    2.查询另一张表
    若无效引用，则中止程序；
    若只是不在内存中；进入步骤3；
    3.找一个空闲的frame；
    4.swap 这个在辅存中的内容到frame中通过发disk io；
    5.重新设置页表项成在内存特定frame号中,且设置valid- invalid bit 成valid
    6.重新执行发生缺页错误的指令；

    
    image.png

  • 补充说明：
    纯按需分页（pure demand paging）：
    i)启动一个进程没有任何一部分在内存中
    ii)OS 设置PC 指向进程的第一条指令，不在内存中，引起缺页错误
    并且每个其他进程在第一次访问时都这样；
    iii)一个指令可能访问多个page，这样会引发多个缺页错误

• 空闲frame 链表

  • OS 维护一个空闲frame 链表，用以满足缺页错误时申请frame 以存放从辅存加载进来的内容;
  • 分配空闲frame时会zero-fill-on-demand,即分配空闲frame之前清除里面的内容
  • 系统启动时，所有可用的内存都放在空闲frame链表中。

• 按需分页的性能

  • 主要操作：
    服务缺页错误
    从磁盘读页到内存—比较耗时
    重新执行指令
  • 缺页概率
    0<= p <= 1
    p = 0, 没有缺页错误
    p = 1, 每个内存引用都是缺页错误
  • 有效访问时间（EAT）
    EAT=(1-p)内存访问时间+p缺页错误时间
    举例说明:(内存访问:200ns, 缺页服务:8ms)
    EAT=(1-p)200+p(8ms)
    =200+7,999,8008p (ns)
    若1000个中有1个缺页错误，
    EAT=200+7,999,800 0.001 = 8.2ms
    相比200ns，性能降级40倍
    若想要性能降级小于10%==> 220>200+p(8ms); p< 0.000 0025
    说明要让性能降级在合理的水平，需要更少的内存访问会出现缺页错误。
    按需分页系统中，保持缺页错误概率很低的概率至关重要;否则有效访问时间增加，进程也会执行得很慢；
  • 优化
    使用swap空间
    i) 同样设备上，Swap 空间IO 比文件系统IO 要快，swap 空间以更大的块分配，更少管理（没有文件查找和间接分配方式）
    ii) 在进程启动时拷贝整个文件image到swap空间，后续从swap空间对磁盘上的程序binary（只读，不修改）按需分页swap in;但在释放frame时直接丢弃不用swap out 到swap空间。
    iii) swap空间还是需要使用
    • 不与文件相关的内存（匿名内存，比如heap, stack）
    • 在内存中修改的页，还没写到文件系统中；

页替换-内存分配过度处理

• 内存分配过度处理：寻找内存中实际不在使用的页，页换出

  • 杀手进程：分页应该对用户透明，其他进程不可见
  • 标准的交换技术（swap整个进程）：拷贝开整个进程销太大
  • 页替换技术+ 交换技术结合（现代OS采用）

• 包含基本的页替换的页错误处理程序：
  1.找磁盘上期望的页的位置
  2.找一个空闲的frame：
  若有空闲frame，使用空闲frame；
  若没有空闲frame，采用页替换算法选一个victim frame；
  写victim frame到辅存，修改相应的页表。
  3.将期望的页的内容从磁盘加载到新的空闲frame中，更新页表项到新分配的frame
  4.继续执行引起页错误的指令

  
  image.png
  

  5.注意：
  没有空闲frame的case，需要两个页传输（一个page in，一个page out),加倍页错误处理程序的时间，增加EAT；

  • 可以减少这种开销实现
  • 页表增加dirty bit,
  • 只要page有任何写，HW 设置 dirty位
  • 替换的时候，查看dirty位，则写frame到辅存中 ；否则直接释放页

• 页替换实现了逻辑内存和物理内存的隔离

  • 进程地址空间的页不必都在内存中，这样进程逻辑地址空间不必受限物理内存空间大小

• 按需分页实现

  • 需解决两大问题:
    frame分配算法：分配多少frame给一个进程，替换哪个frame
    页替换算法：选择要替换的frame，最小页错误比例

  • 评估叶替换算法好坏的方法：给定一个特定的内存引用序列，计算页错误次数

页替换算法

• FIFO页替换算法-按照FIFO先进先出的原则，替换掉最早入队的的内存页

  
  image.png

• 最优页替换算法

  • 替换掉未来最长时间不使用的page
  • 难以实现，不能预知未来
  • 用于衡量算法好坏

image.png

• LRU（Least Recently Used）页替换
  • 用过去信息而不是未来的
  • 替换掉最近最长时间没有使用的page
  • 将上次使用的时间与page联系起来
  • 好算法，用的比较多

image.png

• 基于时间计算器的LRU实现
  i）每个page entry有个时间计数器变量；每次引用一个page，将这个时间计算器设置成时钟值；
  ii）需要换页时，查看时间计算器，以找最小的值-需要搜索整个表

• 基于栈的LRU实现

  • 将页号以双向链表的形式按照stack 方式管理页；
  • 引用的page
    将它放到栈顶
    需要改变6个指针
  • 最近用到的page总是在栈顶；
  • 最近没用到的page总是在栈底；
  • 每次内存访问，都要更新，开销更大（改变6个指针值-从栈中间移除entry，并插入到栈顶）
  • 替换时不需要搜索

image.png

• 近似LRU替换

  • 需要特殊硬件支持reference bit
  • 页表增加reference bit
    每个page有个bit，初始值为0
    每次引用page时，HW 设置该bit 1
  • 需要替换一个page时选择任何一个其bit 为0的page（如果存在的话）；

• 基于计数的页替换

  • 不常使用，开销比较大
  • LFU（最不经常使用）
    • 替换使用次数最小的page;
    • 基于活跃使用的页会有比较大的引用次数；
    • 问题：进程初始阶段频繁访问的页，后续该页从不范围页。这样初始阶段会有比较大的引用次数，会持续在内存。解决办法：定期指数右移引用次数，以指数衰减
  • MFU （最常使用）
    基于最小计数的页，可能刚刚引入，但还未使用

• 应用程序和页缓冲

  • 前面的算法都是OS 预测未来内存的访问
  • 有些应用更清楚自己内存的访问特征—数据库
  • 内存密集访问的应用会加倍缓存
    i）OS维护一份内存作为IO 缓冲
    ii）应用留一份作为自己work使用
  • OS 可以提供直接访问辅存接口，给应用让道

frame分配

• 最大分配frame-由可用的物理内存的数量

• 保证至少分配最少数量的frame-由架构定义
  性能要求：分配的越少，页错误率越大，进程执行越慢

• 两种主要内存分配方案
  平均分配-所有进程分配同样数量的frame
  比例分配-根据进程的大小动态的分配

• 分配算法分类

  • 全局分配：进程可以从所有frame 中选择一个替换frame；一个进程可以从另一个进程中拿frame；
    i）各个进程执行时间会非常不同
    ii）更大的吞吐量-更常使用
  • 本地分配：每个进程从自己分配的所有frame中选择替换的frame；
    i）每个进程的性能更一致；
    ii）但内存可能不能充分利用；

• 一种全局页替换策略的实现

  • 所有的内存请求都从空闲frame 链表来满足；

  • 不是等这个链表空闲frame 数量在我们开始选择替换页前降为0，而是当链表空闲frame 数量低于一个特定阈值时，就开始触发页替换；
    i）低于最小阈值，触发回收；
    ii）高于最大阈值，挂起回收过程；
    iii）如果不能维持空闲frame 链表，可能更激进的页替换算法回收
    iiii）如果出现极端情况，出现空闲内存太少，则OOM killer直接选择杀死一个进程以释放这个进程的所有内存

  • 该策略尝试确保总是有足够的空闲内存用来满足新的内存申请请求；

image.png

内核内存分配

• 与用户层内存分配方式不一样

  • 内核从空闲内存池中分配内存，而不是空闲frame链表
  • 内核会请求各种不同大小的数据结构
  • 有些分配的内存需要物理连续，但用户内存多数散落在整个物理地址空间

• 分配策略
  伙伴系统
  slab 分配器

• 伙伴系统（buddy system）

  • 从固定大小的段分配内存，每个段由物理连续的frame 构成
  • 内存分配2^n个frame
  • 以大小为2^n 个frame 来满足内存请求；
  • 请求会以更高阶的数量的frame的内存来满足
  • 当需要的是更少的内存，把当前的大块拆分成两份低阶数量的frame，直到有合适的大小的内存可以满足

  • 例子：假设有256KB 的大块内存可用，内核请求一个21KB 的内存
    首先将256KB 的内存拆分成两个AL 和AR， 大小都是128KB；
    其中一个继续拆分2个64KB，BL,BR—> 其中一个继续拆分2个32KB，CL和CR，然后其中一个分配给这个内核请求

    
    image.png
  • 优势：可以快速的将相邻的未使用的内存合成一个更大的段
  • 缺点：碎片化

• slab 分配器（slab allocator）

  • slab 是有一个或多个物理连续的内存组成；

  • 一个cache 是有一个或多个slab 组成；

  • 每个独一无二的数据结构对应一个cache:

  • 每个cache 会产生许许多内核数据结构的实例化的对象；

  • 使用cache 来容纳内核对象；

  • 创建cache时，会分配大量的对象给cache(标记为free）；

  • 分配一个对象后，这个对象标记为used；
    如果slab 充满这个used 的对象，会从一个empty的slab中分配一个对象
    如果没有empty的slab，就分配新的slab；

  • slab 三种状态：full-all used , empty-all free, partial-部分free

  • 内存请求一来，slab 分配器
    会先从partial slab 中分配；
    如果没有，会从空的slab中分配一个；
    如果没有空的slab，则分配一个新的空的slab

  • 好处是：没有碎片化，快速内存请求响应

  • Linux 2.2 开始采用SLAB， 现在包含了另外两种SLOB和SLUB分配器，Linux 2.6.24开始SLUB替代SLAB 作为默认的内核分配器
    i）SLOB 用于内存有限的系统
    ii）SLUB是性能优化的SLAB，移除了per-CPU queue，和page 数据结构中的metadata

    
    image.png

其他

• 预寻页

  • 减少进程启动时，page fault的数量
  • 在进程引用page之前，预先对进程将需要的访问的所有或者一部分页寻页
  • 若预先的寻页没有被进程使用，则对应的IO和内存会被浪费；

• 程序的结构

  • 按需分页对用户透明的，但是若用户知道底层的按需分配机制，则能提高系统的性能。

  • 例子：
    每一排数据存在一个page 中
    程序1， 产生128*128 个page fault

    
    image.png
    

    程序2，产生128个page fault

    
    image.png