问题：放宽假设

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

一、“虚拟内存”

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)

Value Meaning
1 page is present in physical memory
0 The 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：虽然未来不可确定，我们是否有方法预测未来？

  • 最近用的少的被淘汰
历史信息 Meaning Algorithms
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
  • 其他策略
    • 需时加载、分组写入、抖动应对