0%

按需加载与页替换

发表于 2022-12-24 更新于 2025-12-05 分类于 Study 阅读次数：本文字数： 2.3k 阅读时长 ≈ 9 分钟

缺页与换页

进程加载

简单方法
- 将整个进程加载进内存 -> 运行它 -> 退出
问题
- 慢（特别是对于大的进程）
- 浪费空间（一个进程并不是每时每刻都需要所有的内存）
解决办法
- 按需加载页：只将实际使用的页加载进内存
- 换页：内存空间有限，只放频繁使用的那些页
机制
- 一部分虚存映射到内存，另一部分虚存映射到磁盘

缺页处理

内存访问（先查TLB）
若TLB不命中，则进行页表查找，找到PTE
若PTE的valid位=0（页不在内存），则触发缺页（Page Fault）
虚存管理中的缺页处理接管控制，将页从磁盘读到内存
更新PTE：填入PP#，将Valid位置1
重新执行该指令：重新进行内存访问

发生缺页后，如何切换到缺页处理？

缺页可能发生在一条指令执行的中途
应用程序透明：必须让用户程序不感知缺页
需要保存状态并从断点处继续执行

页替换

需要的页不再内存里 -> 需换入 -> 需为它分配一个页框
可能此时没有空闲页框 -> VM需要进行页替换

包含页替换的缺页处理算法

进程A发生缺页，发生缺页的页记为VP
- 陷入内核，保存进程A的当前状态: PC和寄存器
- 调用OS的缺页处理模块
  - 检查地址和操作类型的合法性，若不合法则终止进程
  - 为VP分配一个物理页框，记为PP
    - 如果有空闲页框PP1，则用它，记PP=PP1
    - 如果没有空闲页框，选择一个状态为used页框PP2
      - 如果他是脏的(M位=1)，则把它写回磁盘
      - PTE表项的valid置0，刷新TLB
      - 写回完成后，PP=PP2
  - 找到VP对应的磁盘页，把它读到这个页框(PP)中
  - 修改VP的PTE：填入PP#，将valid位置1，并把该PTE加载进TLB
- 恢复进程A的状态，重新执行发生缺页的指令
通用数据结构
- 空闲页框链表
- 一张映射表：页框->PID和虚页

页替换算法

随机选一页
最优算法（MIN）
NRU(Not Recently Used)
FIFO(First-In-First-Out)
FIFO with Second Chance
NFU(Not Frequently Used)
LRU(Least Recently Used)
Aging(Approximate LRU)
Clock
Working Set
WSClock

最优算法（MIN）

算法
- 替换在未来最长一段时间里不用的页
- 前提：知道未来所有的访问
例子
- 内存大小为4个页
- 访问序列：1,2,3,4,1,2,5,1,2,3,4,5
- 一共发生6次缺页
好处
- 是最优的方案，可以作为一种离线的分析手段
坏处
- 在线系统无法采用，因为不知道未来访问的顺序
- 没有线性时间复杂度的实现

FIFO

算法
- 选择最老的页扔掉
例子
- 内存大小为4个页
- 访问序列：1,2,3,4,1,2,5,1,2,3,4,5
- 一共发生10次缺页
好处
- 实现开销最小
坏处
- 频繁使用的页被替换

能否通过增加页的数量来减少缺页？

假设内存大小为3个页，访问序列：1,2,3,4,1,2,5,1,2,3,4,5，只发生9次缺页
"Belady's Anomaly"现象：采用FIFO算法时，有时会出现分配页数增多，缺页次数反而升高的异常现象

FIFO with Second Chance

核心思想
- 尽量让频繁使用的页留在内存，不被替换
- 替换时给访问过的页第二次机会，在内存中呆更长的时间
算法
- 检查最老页的R位，如果为0，则将其替换
- 如果为1，则将R位清0，将该页移到队尾，继续查找
例子
- 内存大小为4个页
- 访问序列：1,2,3,4,1,2,5,1,2,3,4,5
- 一共发生8次缺页
好处
- 实现简单
坏处
- 最坏情况可以需要很长时间

Clock

改进Second Chance的替换开销
- 移动开销
算法：把所有页框组织成环形链表
- 用一个表针指向最老的页
- 发生缺页的时候，按表针走动方向来检查页
- 第二次机会
  - 如果R位为1，则将R位清0，且表针向前移一格
  - 如果R位为0，则将该页替换，且表针向前移一格
与Second Chance算法相比
- 更加高效
如果内存很大
- 轮转一遍需要很长的时间

LRU

替换最长时间没有使用的页
- 将所有页框组织成一个链表
- 前端为最久未访问页（LRU端）：替换的页
- 后端为最近刚访问的页（MRU端）：新加载的页和命中的页
- 每次命中将页重新插入 MRU 端
例子
- 内存大小为4个页
- 访问序列：1,2,3,4,1,2,5,1,2,3,4,5
- 一共发生8次缺页
好处
- 对 MIN 算法的很好近似
坏处
- 实现困难

NRU（Not Recently Used）

算法
- 按下面顺序，随机选择一个页
  - 未访问过且未修改过
  - 未访问过且修改过
  - 访问过且未修改过
  - 访问过且修改过
例子
- 内存大小为4个页
- 访问序列：1,2,3,4,1,2,5,1,2,3,4,5
- 一共发生7次缺页
好处
- 实现简单
坏处
- 需要扫描内存中所有页的R位和M位

LFU（Least Frequently Used）

算法：记录每个页的访问次数，替换访问次数最少的页
- 每页有一个访问计数器，用软件模拟
- 每个时钟中断时，所有页的计数器分别和它的R位值相加
例子
- 内存大小为4个页
- 访问序列：1,2,3,4,1,2,5,1,2,3,4,5
- 一共发生8次缺页
坏处
- 过去访问频繁、现在不访问的页，可能无法被替换出去

Aging

在LFU的基础上消除过去访问的影响
- 每个时钟中断时，先将所有页计数器右移1位，再将每页计数器最高位与该页的R位相加
- 替换时，选择计数器最小的页
Aging 和 LRU 的主要差别
- 记录下来的历史更短（计数器长度）
- 无法区分访问的先后顺序（同一个tick内）
Aging需要多少位才够用
- 实际工作中8位就工作的很好

Working Set

主要思想
- 80/20原则
  - 80%的访问只涉及20%的内存空间
  - 80%的访问都来自20%的代码
- 空间局限性
  - 相邻的页很可能会被访问
- 时间局限性
  - 被访问的页很可能在不远的将来再被访问
工作集的概念
- 工作集被定义为在最近K次访问的那些页
- 把工作集放在内存能大大地减少缺页
- 工作集可以近似为过去T秒钟里使用的页
算法：记录页的"上次访问时间"
- 在缺页处理时，扫描该进程所有的页
- 如果R位为1，将该页的上次访问时间设置为当前时间
- 如果R位为0，计算当前时间和上次访问时间之差
  - 如果差值大于T，则该页在过去T秒里没有被访问过，则替换它
  - 否则，检查下一页
- 将发生缺页的页加入工作集

WSClock

将 Working Set类似的组织成环形链表（类似 Clock）
按表针走动的顺序来检查页
如果R位为1
- 将R位置成0，该页的上次访问时间设置为当前时间
- 检查下一页
如果R位为0
- 设差值为当前时间-上次访问时间
- 如果该值小于等于T，则代表在过去T秒里被访问过，检查下一页
- 如果该值大于T，则代表在过去T秒里没有被访问过
  - 若M位为1，则将该页写回加入写回链表（异步进行写回），并检查下一页
  - 若M位为0，则将该页替换出去

总结

LRU很好但是实现困难，Aging是一个很好的近似LFU
Clock被认为是一个很好的实际解决方案
所有的替换算法都不会优化由Cold Miss带来的缺页

算法	特点
MIN	最优算法，但无法在实际系统中实现
FIFO	没有考虑重复访问的情况，仅根据第一次访问时的顺序进行替换
Second Chance	在FIFO的基础上考虑了重复访问
Clock	基于Second Chance，可以更加高效的实现
LRU	考虑了访问时效性，实现时有频繁链表操作，开销较大
NRU	粗粒度近似LRU，只区分有无访问，同时优先保留脏页；与LRU比，时效性考虑较少
LFU	考虑访问的次数，将访问次数多的数据留在内存中；容易受短期高频访问的影响
Aging	近似LFU，更容易实现；记录窗口短；相同访问次数时，无法区分时效性
Working Set	实现开销大
WSClock	基于WS优化实现时的数据结构（环形链表），实现开销小