问题：放宽假设

当虚拟地址空间大于物理内存大小时，如何超越物理内存进行存储？

一、“虚拟内存”

1. 基本原理

  • OS的存储是分层级(hierarchy)的
    • 越上层的存储越快
    • 越底层的存储空间越大
    • time-space trade-off

OS利用大而慢的设备，透明的提供巨大虚拟地址空间的假象

  • 解决方案：用外存(硬盘)模拟内存，达到扩大内存的效果

enter image description here

enter image description here

2. 交换空间(swap space)

  • 在硬盘上开辟一部分空间用于物理页的移入和移出
    • 交换空间以页为单位进行组织

enter image description here

3. 实现机制

一般寻址流程

enter image description here

页表项新增存在位(present bit)

ValueMeaning
1page is present in physical memory
0The page is not in memory but rather on disk. （前提：有效位为1）

当页表不存在内存中， 则引发页错误，陷入内核。

回顾：页表项

enter image description here

页错误的触发与处理

页表项用于记录在外存的位置信息

enter image description here

如果内存满了怎么办(没有空闲页帧了)？

  • 换出(page out)一些内存中的页面，称为页淘汰
  • 较差的页面替换策略可能导致程序运行慢10000~100000倍

页淘汰

enter image description here

enter image description here

  • 页错误的处理：
PFN = FindFreePhysicalPage();
if (PFN == -1)        // no free page found
    PFN = EvictPage(); // run replacement algorithm
DiskRead(PTE.DiskAddr, PFN); // sleep (waiting for I/O)
PTE.present = True; // update page table with present
PTE.PFN = PFN;      // bit and translation (PFN)
RetryInstruction(); // retry instruction
  • 进行页面交换的真实时机
    • OS不会等到内存真正全部用完，而会主动调控
    • 交换守护进程/页守护进程
      • 设置高水位线(High Watermark, HW)和低水位线(Low Watermark, LW)
      • 当内存低于LW，则开始淘汰(evict)页面直到达到HW

“虚拟内存”小结

  • 基本原理
    • 用外存模拟内存
  • 实现机制
    • 存在位，页错误
  • 页错误的处理
    • 淘汰页面、换入页面、修改页表项

二、策略

  1. 页面替换策略
  • 指选择被淘汰页面的方法
  • 可将物理内存看作是外存的cache，分页地址转换时，如果 页面在内存中，则视为cache命中
  • 度量指标：平均内存访问时间（AMAT）

$$AMAT = P_{Hit} * T_M +( P_{Miss} * T_D)$$

$T_D$可能是$T_M$的100000倍。

参数含义
$T_M$The cost of accessing memory
$T_D$The cost of accessing disk
$P_{Hit}$The probability of finding the data item in the cache (a hit)
$P_{Miss}$The probability of not finding the data in the cache (a miss)

未命中率强烈影响平均访存时间。

最优替换策略(OPT)

  • 替换下次访问距当前最远的页
    • 当前留在内存里的页都比它重要
  • 理论上可以达到总体未命中数最少

enter image description here

先入先出策略(FIFO)

  • 进入内存时间最早的页面被淘汰
    • 页面加入时放在队列头部，每次从页面尾部淘汰页面

enter image description here

eg：

  • 访问序列1 2 3 4 1 2 5 1 2 3 4 5
  • 缓存分别为3和4

Belady异常（Belady Anomaly）

  • 一般来说，当缓存变大时，缓存命中率会提高

enter image description here

随机选择(Random)

运行千次的随机实验，有些时候随机策略效果和OPT一样

Hint：虽然未来不可确定，我们是否有方法预测未来？

  • 最近用的少的被淘汰
历史信息MeaningAlgorithms
recency (上次访问的时间)上一次访问离当前时间点最远的被淘汰LRU
frequency (最近访问的频率)最近被访问的频率低的被淘汰LFU

最近最少使用策略(LRU)

  • 替换上次使用距离最远的页面
  • LRU一定比FIFO和随机好吗？
  • 性能比较：随机访问
    • 每次从100个页面中随机选 择一个访问，10000次访问
    • 对于没有局部性的访问序列，各替换策略一样 (OPT除外)

enter image description here

  • 性能比较：80-20负载场景
    • 80%的引用是访问20%的页
    • LRU可以尽可能地保留热门页

enter image description here

  • 性能比较：循环顺序访问
    • 反复顺序访问50个页面， 共10000次访问
    • 对于特定访问序列，随机效果反而更好

enter image description here

  • 如何实现LRU策略？
    • 为了记录页面使用情况，必须对每次内存访问进行记录
    • 一种尝试：增加硬件支持，记录每次页访问的时间。替换时扫描系 统中所有的页，找出最近最少使用的页
      • 给每个页帧设一个“未访问次数”计数器，每访问一页，对应页帧计数清 0，其余页帧计数加1，淘汰计数最大的页帧
  • 可否实现一个更快的近似算法？

时钟算法（Clock）

  • 一种基于FIFO+LRU的简化算法
  • 轮流淘汰，被访问的页面则推迟一轮淘汰
    • 硬件在页面被访问时置页表项中的访问位为1， 硬件开销比LRU小
    • 淘汰表针指向的页面，若页面访问位为1，则 将访问位置0，表针指向下一页
while (1) {
    if (当前页的使用位 == 0) {
        淘汰当前页;
        当前页指向下一页;
        break;
    }
    当前页的使用位 = 0;
    当前页指向下一页;
}
  • 性能接近LRU
  • 改进：尽量避免淘汰 脏页(被修改过的页， dirty bit标识)

enter image description here

其他虚拟内存策略

  • 何时从外存加载页面内容
    • 预取(prefetching/prepaging)：提前加载
    • 需时加载(按需分页，Demand paging)：访问到时加载
  • 何时将脏页写回外存(硬盘)
    • 一页一写：当页面变脏就写回
    • 分组写入(grouping/cluster)：积攒一些脏页，再一次性写入
  • 如何应对系统的抖动
    • 同时运行进程过多，导致内存过载，系统不断进行换页
    • 例：
      • 进程A运行：换出进程B，换入进程A
      • 进程B运行：换出进程A，换入进程B
    • 准入控制(Admission control)：只允许部分进程运行，避免内存过载
    • 杀死部分内存密集型进程：由一个专门的守护进程完成(out-of memory killer)，解除内存过载
  • 写时复制(COW, Copy On-Write)
    • 一种快速复制技巧，不实际复制，只映射到相同页框 （只读）
    • 直到进程修改页面时，才进行内存分配

“虚拟内存”策略小结

  • 页面替换策略
    • 评价指标：未命中率，可行性、复杂度
    • OPT、FIFO、随机、LRU、Clock
  • 其他策略
    • 需时加载、分组写入、抖动应对