シリウスの砂

交换空间

✏️ 🔧 📄 13 min read

此前, 我们一直假设每个正在运行的进程的地址空间都能且需要放入物理内存,
但正如在分页中所言, 有时, 即使我们进行如此之多的优化, 也难以同时将所有页表存入物理空间.

因此为了支持更大的地址空间, 操作系统需要把当前没有使用的地址空间找个地方存储起来.
这需要使用更大但是慢的硬盘.

也就是增加交换空间, 让操作系统可以为多个并发运行的进程都提供巨大地址空间假象.

机制

交换空间

首先, 我们要在硬盘开辟一部分空间用于物理页的移入移出, 这就是所谓的交换空间.

Physical Memory and Swap Space

![note] 交换空间不是唯一的硬盘交换目的地 对于一个二进制程序, 其代码页最开始在硬盘, 运行时被加载到内存.
如果系统需要在物理内存中腾出空间以满足其他要求, 那么可以安全地使用这些代码页的内存空间,
因为稍后, 它们还可以重新从硬盘的二进制文件中加载.

存在位

如果允许页交换到硬盘, 那么 TLB 要有新的机制.

当硬件查找到 PTE 时, 需要判断页面是否处于物理内存, 这依赖存在位:

  • 若存在位被置为 1, 则表明页面处于物理内存, 可以像以前那样访问.
  • 若存在位被设为 0, 则表明页不在内存中, 而是在硬盘上, 此时访问行为通常被称为页错误.

在页错误被触发时, 操作系统会被唤醒, 通过页错误处理程序的代码来处理.

页错误

在处理页错误的时候, 操作系统需要将该页交换到内存中.

而操作系统如何知道所需要的页在哪里?
答案是页表, 操作系统可以利用 PTE 中的某些位存储硬盘地址.
当操作系统收到页错误, 就在 PTE 查找地址, 并把请求发送至硬盘, 将页面读取到内存.
当硬盘 I/O 结束后, 操作系统会更新页表, 将其标记为存在, 并且更新 PTE 的 PFN 字段记录新的物理地址, 重试引发页错误的指令.

VPN = (VirtualAddress & VPN_MASK) >> SHIFT
(Success, TlbEntry) = TLB_Lookup(VPN)
if Success == True:  # TLB Hit
    if CanAccess(TlbEntry.ProtectBits) == True:
        Offset = VirtualAddress & OFFSET_MASK
        PhysAddr = (TlbEntry.PFN << SHIFT) | Offset
        Register = AccessMemory(PhysAddr)
    else:
        raise ProtectionFault
else:  # TLB Miss
    PTEAddr = PTBR + (VPN * sizeof(PTE))
    PTE = AccessMemory(PTEAddr)
    if PTE.Valid == False:
        raise SegmentationFault
    else:
        if CanAccess(PTE.ProtectBits) == False:
            raise ProtectionFault
elif PTE.Present == True:
    # assuming hardware-managed TLB
    TLB_Insert(VPN, PTE.PFN, PTE.ProtectBits)
    RetryInstruction()
elif PTE.Present == False:
    raise PageFault

我们可以看到 TLB 未命中的三种重要情景

  1. 页有效且存在: 直接查找页表, 从中获取 PTE 对应的 PFN 填入, 然后重试指令.
  2. 页有效但不存在: 运行页错误处理程序, 将页面移入物理内存.
  3. 页无效: 非法访问, 触发段错误, 交由操作系统处理, 例如杀死进程.

其中页错误处理程序的控制流应该是:

PFN = FindFreePhysicalPage()
if PFN == -1:
    PFN = EvictPage() # Replace algorithm
DiskRead(PTE.DiskAddr, PFN)
PTE.present = True
PTE.PFN = PFN
RetryInstruction()

交换发生时刻

操作系统并不会等到内存已经完全满了才替换页面, 而是主动地预留一小部分空闲内存.

为此, 大多数操作系统会设置高水位线(HW)和低水位线(LW).
当系统发现有少于 LW 个页面可用时, 后台负责释放内存的线程开始运行, 直到有 HW 个可用的物理页.

这个线程被称为交换守护进程, 或者页守护进程.

所以事实上, 上面的页错误处理控制流中, 页交换算法会先检测有无空袭那也, 如果没有先激活后台的交换守护进程按需释放页,
然后等到一定数量的页面被释放后, 再度被激活, 将所需要的页交换到内存.

PFN = FindFreePhysicalPage()
PFN = ReplacePage() # Replace algorithm
DiskRead(PTE.DiskAddr, PFN)
PTE.present = True
PTE.PFN = PFN
RetryInstruction()
def ReplacePage():
    if space >= LW:
        return GetSpare()
    else:
        while spare <= HW:
            NotifySwapDaemon()
            Wait()
        return GetSpare()

策略

内存压力迫使操作系统要换出一些页, 为常用的页腾出空间.
确定要踢出的页封装在操作系统的替换策略中.

评价指标

内存可以视为系统中虚拟内存页的缓存, 我们要做的就是用合理的策略减少缓存未命中, 减少从硬盘获取页的次数.

因此评价指标是平均内存访问时间(AMAT):

为访问内存的成本; 表示访问硬盘的成本; 和 分别为缓存命中与未命中的概率.

替换策略

最优替换策略

顾名思义, 是最优的替换策略, 可以使总体未命中达到最少, 但无法被实现, 只能作为评价其他替换策略的比较基准.

其思想是: 替换内存中在最远的将来才会被访问到的页.(也就是预知未来)

FIFO: 先进先出

页在进入系统时, 简单放入一个队列, 发生替换时队列头部的页被踢出.

随机

在内存满的时候随机选择一个页进行替换.

![warning] 关于 FIFO 与随机 这两个算法不具有栈特性.
也就是对于同样的访问序列, 增加缓存大小, 命中率可能反而下降.

LRU: 利用历史数据

为了提升策略的智能性, 我们可以参考一些历史访问情况.

一个可以参考的是历史信息是频率: 如果一个页面被访问了很多次, 那么说明其更有价值, 不应该被替换.
更常用的属性还有访问的近期性: 越近被访问过的页, 再次被访问的可能性就越大.

也就是我们遵循局部性原则(这里主要是时间局部性)

因此简单的基于历史的算法诞生:

  • “最不经常使用”(Least-Frequently-Used, LFU), 会替换最不经常使用的页.
  • “最近最少使用”(Least-Recently-Used, LRU), 会替换最近最少使用的页.
近似 LRU

从开销角度看, 近似 LRU 更为可行: 为硬件增加一个使用位(use bit), 或者称为引用位(reference bit).
每当页被引用(读写), 硬件将使用位设置为 1, 而操作系统负责清除该位.
而所有页被放在一个循环列表中, 开始时, 时钟只是指向某个特定的页, 当需要进行页替换时就扫过列表.
操作系统在扫过时检查指向的页的使用位, 如果为 1, 则说明近期被使用, 不能替换; 如果为 0, 则将其替换.
如果所有页的使用位都是 1, 就都置为 0.

这不是实现近似 LRU 的唯一办法, 只要周期性地清除使用位, 然后根据使用位判断是否可以替换, 都是可以的.
例如, 在一种变体中, 如果指向的页使用位为 1, 会将其置为 0, 然后指向下一页, 再次检查.

考虑脏页

这是对内存中页面是否被修改的额外考虑:

  • 如果页已经被修改而因此脏位置为 1, 那么踢出它的时候, 必须将其写回硬盘, 花费更多时间;
  • 如果页没有被修改, 那么踢出这个页不需要写入硬盘, 可以无成本踢出, 对应的物理页可以立即简单重用与其他目的.

所以一些操作系统倾向于踢出干净页, 而不是脏页.

实现这个修改, 需要在硬件包括一个修改位(modified bit), 也即脏位(dirty bit), 每次写入时置为 1.
随后, 替换算法可以扫描的时候先找到未使用又干净的页面, 如果没有再去查找脏的未使用页面.

其他策略

页选择策略

这个策略决定了操作系统需要何时将页载入内存.

对于大多数页而言, 操作系统只是按需分页, 在页被访问的时候将其载入内存.

但是操作系统也可以预测一个页面即将被使用, 从而提前载入, 也就是预取.
例如可以利用空间局部性, 假设代码页 P 被载入内存, 那么 P + 1 页可能很快就会被访问, 因此也应该载入内存.

磁盘写入策略

这决定了操作系统如何将页面写入硬盘.

操作系统可以简单地一次写入一个.

但是许多操作系统会在内存手机一批待完成写入的页面, 然后以更高效地写入方式将其写入, 也就是聚集写入, 或者分组写入.
这是考虑到磁盘驱动器的性质, 单次大的写入快于多次小的写入.

抖动

当内存被超额请求时, 也就是目前运行的进程的内存需求超出了可用内存, 那么操作系统将不断换页, 这种现象叫作抖动.

早期操作系统采用一些复杂的机制来检测并应对抖动.
例如系统可以决定不运行部分进程, 将其页面放入硬盘, 减少同时运行的进程正在使用的页面. 这被称为准入控制.

目前的操作系统用更严格的方式处理内存过载,
例如一些版本的 Linux, 会在内存超额请求的时候, 运行 out-of-memory killer, 选择一个内存密集型进程并杀死.

关系图谱

反向链接