虚拟内存笔记（三）虚拟内存替换策略与机制

实验代码仓库链接

一、虚拟内存的实现机制：为何能超越物理内存？

虚拟内存的核心思想是为每个进程提供一个远大于实际物理内存的私有地址空间。这使得多个程序可以并发运行，并且每个程序都“认为”自己拥有大量的可用内存。这种“假象”是通过在内存层级结构中增加一层——硬盘上的存储空间——来实现的。

1. 交换空间 (Swap Space)

为了实现超越物理内存的目标，操作系统会在硬盘上开辟一部分专用空间，称为交换空间 (Swap Space) 或交换分区 (Swap Partition)。

• 作用：当物理内存不足以容纳所有活跃进程的页面时，操作系统可以将物理内存中一些暂时不用的物理页帧 (Physical Page Frames) 的内容“换出” (Swap Out) 到交换空间中。当这些被换出的页面再次被访问时，再从交换空间“换回” (Swap In) 到物理内存中。
• 管理：操作系统需要维护数据结构（通常是页表的一部分）来记录每个被换出到硬盘的页面的确切位置（硬盘地址）。
• 容量限制：物理内存和交换空间的总大小，共同决定了系统在某一时刻能够寻址 (addressable) 的最大虚拟内存页数。但实际能同时驻留在物理内存中的页数，则受限于物理内存的大小。

2. 核心组件与流程：TLB、页表、存在位与缺页中断

虚拟内存笔记（二） TLB

当CPU试图访问一个虚拟地址时，硬件和操作系统协同工作：

1. 虚拟地址转换：CPU将虚拟地址 (Virtual Address, VA) 分为虚拟页号 (Virtual Page Number, VPN) 和页内偏移 (Offset)。
2. TLB查询 (Translation Lookaside Buffer)：
   • MMU (Memory Management Unit) 首先检查TLB，看是否有VPN的缓存条目（TLB命中）。
   • TLB命中：直接从TLB获取物理页号 (Physical Page Number, PFN)，与偏移量组合得到物理地址，访问内存。
3. TLB未命中 (TLB Miss)：
   • 硬件（或在某些RISC系统中由操作系统）需要遍历页表 (Page Table Walk) 来查找对应的页表项 (Page Table Entry, PTE)。PTE通常存储在物理内存中。
   • VPN用作索引，在当前进程的页表中找到对应的PTE。
4. PTE检查与存在位 (Present Bit / Valid Bit)：
   • 每个PTE中都有一个存在位 (Present Bit 或 Valid Bit)。
     • 存在位 = 1 (有效)：表示该虚拟页当前存在于物理内存中。PTE中包含了该页对应的PFN。MMU用此PFN构建物理地址，访问内存。同时，TLB可能会被更新。
     • 存在位 = 0 (无效)：表示该虚拟页当前不在物理内存中（可能从未加载，或已被换出到交换空间），或者访问权限不足（如写只读页）。这将触发一个缺页中断 (Page Fault)。

3. 缺页中断 (Page Fault)：交换发生的时刻

当发生缺页中断（因为存在位为0且页面应在磁盘上）时，控制权转移给操作系统内核中的缺页处理程序 (Page Fault Handler)：

1. 定位页面：操作系统检查PTE（或其他辅助数据结构）以确定所需页面在交换空间中的硬盘地址。
2. 选择牺牲页 (Victim Page)：如果物理内存已满，操作系统必须运行页面替换算法 (见下文“策略”部分) 来选择一个物理页帧作为“牺牲品”。
3. 换出牺牲页：
   • 如果牺牲页是“脏”的 (Dirty Page，即自载入内存后被修改过，其PTE中的Dirty Bit会被设置)，则必须先将其内容写回交换空间，以保存更改。
   • 如果牺牲页是“干净”的 (Clean Page)，则其内容可以直接被覆盖，因为磁盘上的副本仍然是最新的。
   • 更新牺牲页的PTE，将其存在位设为0，并记录其在交换空间的位置。
4. 换入所需页：从交换空间将所需的页面读入到上一步空出的物理页帧中。
5. 更新PTE：更新所需页面的PTE，设置其存在位为1，清除Dirty Bit，记录新的PFN。
6. 恢复执行：缺页中断处理完毕后，之前导致缺页的指令会重新执行，此时TLB未命中后，页表查找会成功，程序继续执行。

二、页面替换与管理策略

由于物理内存通常远小于虚拟地址空间的总和，操作系统需要智能策略来管理哪些虚拟页面驻留在物理内存中，哪些被换出。

1. 缓存管理与性能目标

可以将物理内存看作是所有虚拟内存页的一个子集的缓存。页面替换策略的目标是尽量提高缓存命中率 (Hit Rate)，即程序访问的页面尽可能已经在物理内存中，从而减少代价高昂的磁盘I/O（页面换入换出）次数。

平均内存访问时间 (AMAT - Average Memory Access Time) 是衡量虚拟内存性能的关键指标：
AMAT = (P_hit * T_m) + (P_miss * T_d)
其中：

• P_hit: 页面命中物理内存的概率。
• T_m: 访问物理内存的时间 (相对较快)。
• P_miss: 页面未命中物理内存（即发生缺页）的概率 (P_miss = 1 - P_hit)。
• T_d: 处理缺页的平均时间，包括磁盘I/O时间 (非常慢)。

目标是最小化AMAT，这主要通过最大化 P_hit (即选择好的替换策略)来实现。

2. 页面替换算法 (Page Replacement Algorithms)

当需要从物理内存中换出一个页面以便为新页面腾出空间时，以下算法用于选择“牺牲”页面：

• FIFO (First-In, First-Out 先进先出)

  • 原理：替换最早进入内存的页面。实现简单，通常用一个队列维护所有驻留页。
  • 缺点：可能会换出经常使用的页面，因为它可能很早就被加载了。可能遭受Belady现象（增加物理内存帧数反而导致缺页率上升）。
  • 

• 随机 (Random)

  • 原理：随机选择一个页面进行替换。
  • 优点：实现简单，开销小。
  • 缺点：性能不稳定，可能碰巧换出重要页面，也可能碰巧换出不重要页面。通常比FIFO略好，因为避免了FIFO系统性地淘汰早期关键页的问题。
  • 

• LRU (Least Recently Used 最近最少使用)

  • 原理：替换在过去最长时间内未被访问过的页面。基于局部性原理 (Principle of Locality)：
    • 时间局部性 (Temporal Locality)：最近被访问过的页面，在不久的将来很可能再次被访问。
    • 空间局部性 (Spatial Locality)：如果一个内存位置被访问，那么其附近的内存位置也很可能在不久的将来被访问（体现在预取和整个页面加载）。
  • LRU认为，如果一个页面很久没被访问，那么它在将来被访问的可能性也较低。
  • 优点：通常能提供较好的性能，接近最优算法 (OPT/MIN，替换未来最长时间内不会被访问的页面，但无法预测未来)。
  • 缺点：实现开销大。精确实现LRU需要在每次内存访问时更新数据结构（如链表或时间戳），这对于大量的页来说非常耗时。
  • 

• 近似LRU (Approximated LRU) / 时钟算法 (Clock Algorithm) / 第二次机会算法 (Second Chance)

  • 背景：由于精确LRU开销过高（如果LRU要维护一个链表，每次驱逐都要进行一次全表扫描，性能开销太大），实际系统中常采用近似算法。
  • 原理：
    1. 所有物理页帧被组织成一个循环链表（像一个时钟的表盘）。
    2. 每个页帧关联一个使用位 (Use Bit / Reference Bit)，由硬件在页面被访问时设置（置为1）。
    3. 一个时钟指针指向链表中的某个页帧。
    4. 当需要替换页面时：
       • 检查指针当前指向的页P的使用位。
       • 如果使用位为1 (最近被使用过)：将其使用位清零 (置为0)，指针前进到下一页 (P+1)。这给了该页面“第二次机会”。
       • 如果使用位为0 (最近未被使用过)：该页面成为牺牲页被替换。指针前进到替换后的新页的下一页。
  • 优点：开销远小于精确LRU，性能接近LRU。
  • 缺点：不如精确LRU，但通常足够好。
  • 
    图片来自小林coding

• LFU
  LFU算法解析
• W-TINY-LFU
  W-TinyLFU缓存驱逐算法解析

3. 工作负载示例对算法性能的影响

不同的页面替换算法在不同的工作负载下表现各异：

• 无局部性工作负载：程序随机访问大量页面。
  • 所有算法表现都较差，因为无法有效预测未来访问。LRU和近似LRU可能略好于FIFO和随机，但差距不大。
• 80-20 工作负载 (高局部性)：80%的访问集中在20%的“热点”页面上。
  • LRU和近似LRU表现非常好，能有效将热点页面保留在内存中。
  • FIFO和随机表现较差，因为它们可能错误地换出热点页面。
• 循环顺序工作负载：顺序访问一组页面，然后循环。例如，访问页0, 1, …, 49, 0, 1, …
  • 当缓存大小略小于循环序列长度时（例如缓存49页，访问50页）：
    • FIFO 和 LRU (及近似LRU) 在这种情况下表现最差（0%命中率），因为它们总是在页面即将被再次访问前将其换出。
    • 随机算法反而可能表现得更好，因为它不按固定顺序淘汰，有一定几率保留住即将被访问的页面。
  • 当缓存大小足以容纳整个工作集时：所有策略的命中率都会很高（接近100%）。此时，替换策略的选择变得不那么重要。

4. 其他页面管理策略

除了页面替换，虚拟内存子系统还涉及其他管理策略：

• 脏页处理 (Handling Dirty Pages)

  • PTE中通常有一个修改位 (Dirty Bit / Modified Bit)。当对页面进行写操作时，硬件会自动设置该位。
  • 当一个“脏”页面被选为牺牲页时，操作系统必须将其内容写回磁盘（交换空间或文件系统）以保存修改，然后才能用新内容覆盖它。
  • “干净” (Clean) 的页面（未被修改）则可以直接被覆盖，无需写回，因为磁盘上的副本仍然是有效的。这可以显著减少不必要的磁盘写入。

• 页面加载策略 (Page Loading Policies)

  • 按需分页 (Demand Paging)：这是最常见的策略。操作系统只在页面首次被实际访问（即发生缺页中断）时，才将其从磁盘加载到物理内存。
  • 预取 (Prefetching)：操作系统试图预测将来可能需要的页面，并提前将它们加载到内存中。例如，如果代码页 P 被加载，系统可能会推测代码页 P+1 很快也会被访问，于是也将其预取。预取能减少缺页次数，但如果预测不准，则会浪费I/O带宽和内存空间。

• 写回策略 (Write-Back Policies for Dirty Pages)

  • 聚集写入 (Clustering / Grouping)：操作系统可能会将多个“脏”页面收集起来，然后一次性将它们批量写入磁盘。由于磁盘I/O的特性（寻道和旋转延迟占比较大），执行一次大的写操作通常比执行多次小的写操作更高效。

三、内存过载与抖动 (Thrashing)

当系统中运行的进程的总内存需求（它们的工作集大小之和）远超过可用的物理内存时，系统会陷入抖动 (Thrashing) 状态。

• 表现：系统花费绝大部分时间在页面换入换出上，而不是执行有用的计算。CPU利用率急剧下降，磁盘活动异常频繁。
• 应对策略：
  • 准入控制 (Admission Control)：一些早期或特定系统会监控系统负载。如果检测到抖动，可能会暂停一些进程，减少活跃进程的工作集总和，使其能够适应物理内存，从而让系统能够取得进展。
  • 内存不足杀手 (Out-Of-Memory Killer, OOM Killer)：现代Linux系统中的一种机制。当系统内存极度不足时，OOM Killer会选择一个或多个“内存密集型”进程并终止它们，以强行释放内存。这种方法简单粗暴，但能快速缓解内存压力。选择哪个进程被杀死是一个复杂的问题，如果杀错关键进程（如X服务器），可能导致系统部分功能不可用。
  • 工作集模型 (Working Set Model)：通过跟踪每个进程最近访问的页面集合（即工作集），操作系统可以尝试确保每个运行进程的工作集都能容纳在物理内存中。如果不能，则可能需要换出整个进程。

四、实验验证：工作负载对算法性能的影响

为了凭经验证明和量化不同的内存访问模式（工作负载）如何影响常见及一些先进页面替换算法（FIFO、随机、LRU、时钟/近似LRU、LFU、W-TinyLFU）在不同缓存大小下的性能（主要是缺页率），我们可以设计并执行以下实验。

目标：
通过模拟实验，观察并分析不同工作负载下，各种页面替换算法的缺页率，并验证理论预期，同时评估LFU和W-TinyLFU等算法的性能。
I. 实验设置与工具

1. 模拟器环境：

   • 开发一个自定义的模拟器（例如，使用 Python、Java 或 C++）。这能提供对参数和日志记录的完全控制。
   • 模拟器接收页面访问序列、缓存大小（物理页帧数）和页面替换算法作为输入。
   • 输出总的缺页次数。

2. 模拟器核心组件：

   • 缓存（物理内存表示）： 一个数据结构（如列表、字典、数组）来表示可用的物理页帧。其大小是关键的实验参数。
   • 页表项（PTE）存根（可选，但对LRU/Clock有益）： 虽然不需要完整的PTE，但对于LRU（用于时间戳）或Clock（用于使用位）等算法，缓存条目需要关联元数据。
   • 页面访问序列生成器/加载器： 一个模块，用于为不同的工作负载生成或读取预定义的页面访问序列。
   • 算法实现： 为每种页面替换算法提供独立的模块。
   • 指标收集器： 用于计算缺页次数、命中次数，（可选）如果扩展了功能，还可以计算脏页的磁盘写回次数。

3. 可变参数：

   • 页面替换算法：
     • FIFO (先进先出)
     • 随机 (Random)
     • LRU (最近最少使用 - 模拟中的理想实现)
     • 时钟 (Clock / 近似LRU)
     • LFU (Least Frequently Used - 最不经常使用)
     • W-TinyLFU (Window TinyLFU)
   • 缓存大小（物理页帧数量）：
     • 将在一个范围内变化。例如，如果一个工作负载中的唯一页面总数为 N，缓存大小可以从 N 的一个很小百分比（如10%）到 N（或略大以观察100%命中率）。
     • 关键点：对于一个包含 L 个页面的循环工作负载，测试缓存大小为 L-1、L 和 L+1。
   • 工作负载（页面访问序列）： (详见下文)

II. 工作负载定义与生成

对于所有工作负载，假设：

• 可供访问的唯一虚拟页面总数： U_PAGES = 100 (可调整)
• 一个序列中的总页面访问次数： TOTAL_ACCESSES = 10,000 (为了统计稳定性)

1. 工作负载1：无局部性（随机访问）

   • 描述： 每次页面访问都是对 U_PAGES 中随机选择的一个页面的访问。没有时间或空间局部性。
   • 生成： 对于 i 从 0 到 TOTAL_ACCESSES - 1：
     page_accessed = random_integer(0, U_PAGES - 1)
   • 预期行为： 所有算法的性能都会较差。LRU 可能略好于随机算法，FIFO 如果早期加载的重要页面被逐出，则可能表现不佳。

2. 工作负载2：80-20 局部性（热点/冷点页面）

   • 描述： 表现出时间局部性。80%的访问针对20%的页面（热点集），20%的访问针对其余80%的页面（冷点集）。
   • 生成：
     • 热点集： HOT_PAGES_COUNT = 0.20 * U_PAGES (例如，20个页面，假设为页面0-19)
     • 冷点集： COLD_PAGES_COUNT = 0.80 * U_PAGES (例如，80个页面，假设为页面20-99)
     • 对于 i 从 0 到 TOTAL_ACCESSES - 1：
       • dice_roll = random_float(0, 1)
       • 如果 dice_roll < 0.80：
         page_accessed = random_integer(0, HOT_PAGES_COUNT - 1) (访问热点页)
       • 否则：
         page_accessed = random_integer(HOT_PAGES_COUNT, U_PAGES - 1) (访问冷点页)
   • 预期行为： LRU 和 Clock 应该表现非常好，因为它们能有效地将热点页面保留在缓存中。FIFO 和随机算法表现会较差，因为它们不太可能保留热点页面。

3. 工作负载3：顺序循环

   • 描述： 按固定顺序访问一组页面，然后重复该序列。
   • 生成：
     • 循环长度： LOOP_PAGES = 50 ( U_PAGES 的一个子集，例如页面0-49)
     • 对于 i 从 0 到 TOTAL_ACCESSES - 1：
       page_accessed = i % LOOP_PAGES
   • 预期行为（关键测试点）：
     • 如果 缓存大小 < LOOP_PAGES (例如，对于50个循环页面，缓存有49个页帧)：
       • FIFO 和 LRU 将表现极差（接近0%命中率），它们会持续地在页面即将再次被需要之前将其换出。
       • 随机算法在这种情况下可能表现得比FIFO/LRU更好。
     • 如果 缓存大小 >= LOOP_PAGES：在初始填充后，所有算法都应达到接近100%的命中率。

III. 页面替换算法实现细节（供模拟器使用）

• FIFO：

  • 维护一个当前在缓存中的页面队列。
  • 当缓存已满发生缺页时：淘汰队列头部的页面。将新页面添加到队尾。

• 随机：

  • 当缓存已满发生缺页时：从缓存中随机选择一个页面进行淘汰。

• LRU (理想实现)：

  • 为缓存中的页面维护一个列表/时间戳。
  • 在访问时（命中或缺页加载）：将被访问的页面标记为最近使用的（例如，移动到列表末尾，或更新时间戳）。
  • 当缓存已满发生缺页时：淘汰最长时间未被使用的页面（例如，从列表头部，或时间戳最旧的）。

• 时钟 (近似LRU)：

  • 缓存页帧排列成一个带有“时钟指针”的循环缓冲区。
  • 每个页帧有一个“使用位”（初始为0）。
  • 在访问时（命中或缺页加载）：将被访问页面的页帧的使用位置为1。
  • 当缓存已满发生缺页时：
    1. 从时钟指针处开始。
    2. 如果当前页帧的使用位为1：将其置为0，指针前进。重复此步骤。
    3. 如果当前页帧的使用位为0：淘汰此页面。将新页面放入此处。设置其使用位（通常为0，在加载后第一次实际访问时再设为1，具体取决于变体）。指针前进。

• LFU (Least Frequently Used - 最不经常使用):

  • 原理： 替换访问频率最低的页面。
  • 实现：
    • 为缓存中的每个页面维护一个访问计数器。
    • 每次页面被访问（命中或缺页加载后），其计数器增加。
    • 当缓存已满发生缺页时：淘汰计数器值最小的页面。
    • 平局处理 (Tie-breaking): 如果有多个页面的计数器值相同且最小，通常使用LRU或FIFO来选择其中一个（例如，淘汰它们中最近最少使用的那个，或者最早进入的那个）。为了简化，也可以随机选择一个。
  • 问题：
    • 历史污染 (Cache Pollution by Old Popular Items): 早期非常热门但后来不再使用的页面，其计数器可能仍然很高，导致难以被淘汰。
    • 新项目饿死 (New Item Starvation): 新加入的页面计数器从1开始，可能很快被淘汰，即使它将来会变得热门。

• W-TinyLFU (Window TinyLFU):

  • 原理： W-TinyLFU 是一种结合了LRU（用于处理近期性）和LFU（用于处理频率）优点的算法，并使用布隆过滤器 (Bloom Filter) 或类似的概率数据结构来高效地估计大量不在缓存中的项目的频率，以解决LFU的缺点。它通常包含一个主缓存（通常是LRU或其变种，如SLRU）和一个小的“窗口”缓存（也是LRU）。

  • 简化版核心思想 (适用于页面替换模拟)：

    1. 频率估计器 (Frequency Estimator): 通常使用一个或多个计数最小 स्के치 (Count-Min Sketch) 或布隆过滤器来近似估计所有被访问过的项目（包括不在缓存中的）的访问频率。
    2. 主缓存 (Main Cache): 采用一种策略，如分段LRU (Segmented LRU - SLRU) 或简单的LRU。SLRU通常将缓存分为两部分：一个“保护区” (Probationary Segment) 和一个“受保护区” (Protected Segment)。新项目进入保护区，如果再次被访问，则移入受保护区。
    3. 淘汰决策：
       • 当需要淘汰页面时，会比较候选淘汰页（例如，来自主缓存LRU段的尾部）和新进入页的估计频率。
       • 如果新进入页的估计频率显著高于候选淘汰页，则新页进入缓存，旧页被淘汰。
       • 否则，新页可能被拒绝进入主缓存（或只记录其频率），而旧页保留。

  • 模拟器中的简化实现考虑：

    • 主缓存 (Cache): 可以是一个简单的LRU列表。
    • 频率跟踪 (Frequency Sketch): 可以用一个字典/哈希表来存储所有曾经被访问过的页面的精确频率计数（在模拟中，我们不需要严格的内存限制，所以可以不用概率数据结构，但要意识到实际TinyLFU的优势在于此）。
    • 淘汰逻辑：
      1. 命中时： 增加命中页面的频率计数。将命中页面移至LRU的MRU端。
      2. 未命中（缺页）时，缓存已满：
         • 候选淘汰页 (Victim): 从LRU缓存的LRU端选出。
         • 新进入页 (Candidate): 即将加载的页面。
         • 增加新进入页的频率计数。
         • 比较： 如果 frequency(Candidate) > frequency(Victim)，则淘汰 Victim，加载 Candidate 到MRU端。
         • 否则 (频率不够高)： Victim 保留在缓存中（可能移到MRU端，模拟其“被挽救”），而 Candidate 不进入缓存（或者说，被认为“不值得”替换掉当前的 Victim）。 注意：这种“不进入”的处理对于页面替换场景来说意味着缺页仍然发生，只是我们选择不替换那个特定的Victim。在实际缓存系统中，这可能意味着新项目被丢弃。在页面替换中，新页面最终总是要加载的，所以关键是谁被换出。
         • 更符合页面替换的W-TinyLFU思路： 所有缺页都必须加载。问题是换出谁。
           • 当缺页发生且缓存满时，从LRU列表中找到LRU项作为潜在的牺牲者 (V_lru)。
           • 比较新页面 (P_new) 的频率和 V_lru 的频率。
           • 如果 freq(P_new) > freq(V_lru)，则换出 V_lru，P_new 加入LRU的MRU端。
           • 否则 (P_new 频率不高)，P_new 仍然需要加载，但我们可能选择换出另一个频率更低的页面（如果存在的话），或者如果V_lru已经是频率最低的之一，就换出V_lru。 为了简化，如果P_new频率不高于V_lru，我们仍然换出V_lru（LRU行为），但P_new的频率已经被记录和更新了。 真正的W-TinyLFU有更复杂的接纳策略。
    • 为了更贴近W-TinyLFU： 可以考虑一个“窗口LRU” (Window Cache) 和一个“主LRU” (Main Cache)。新项目先进入窗口LRU。如果从窗口LRU淘汰时其频率足够高，则进入主LRU，并可能淘汰主LRU中频率较低的项。如果从主LRU淘汰，则彻底淘汰。
      • 对于页面替换模拟，我们可以简化为：一个主LRU缓存。所有访问都更新全局频率计数。淘汰时，优先淘汰LRU端的页面，但如果一个即将进入的页面频率明显高于LRU端的页面，则新页面有更高的“价值”。这个逻辑与上面“比较”类似。

  • W-TinyLFU 在模拟中的关键：

    1. 所有被访问过的页面（无论是否在缓存中）都要有一个频率计数。
    2. 缓存本身通常基于LRU进行管理。
    3. 淘汰决策会同时考虑LRU位置和频率计数。 一个简单的策略可以是：当发生缺页且缓存满时，查看LRU端的页面 V。如果新页面 N 的频率 freq(N) 大于 freq(V)，则换出 V 并加载 N。否则，换出 V 并加载 N（此时表现得像LRU，但频率信息已被更新）。更复杂的版本会有一个准入门槛。
    • 一个更实际的W-TinyLFU模拟变体：
      • 维护一个主LRU缓存。
      • 维护所有访问过的页面的频率（例如，使用Count-Min Sketch，或模拟中用精确计数）。
      • 当缺页发生，需要加载页面P_new：
        • 从LRU缓存中找到牺牲候选项P_victim (LRU端的页面)。
        • 如果 frequency(P_new) > frequency(P_victim)，则P_new替换P_victim。
        • 否则，P_new不进入缓存（在真实缓存中），P_victim保留。但在页面替换中，P_new必须加载。 所以这里调整为：P_new替换P_victim。但是，P_victim在被替换前，其频率信息用于了决策。这种简化可能更偏向于“频率优先的LRU”。
      • 另一种方法 (SLRU + TinyLFU思想)：
        • 缓存分为两段：S_probation (试用段，LRU管理) 和 S_protected (保护段，LRU管理)。例如，S_probation 占缓存20%，S_protected 占80%。
        • 所有页面访问都更新全局频率计数器 (TinyLFU部分)。
        • 缺页加载 P_new： P_new 进入 S_probation 的MRU端。如果 S_probation 满了，其LRU端的页面 P_evict_prob 被淘汰。
        • P_evict_prob 被淘汰时： 检查 frequency(P_evict_prob)。如果其频率高于 S_protected LRU端的页面 P_lru_prot 的频率，则 P_evict_prob 进入 S_protected 的MRU端，而 P_lru_prot 被彻底淘汰。否则，P_evict_prob 被彻底淘汰。
        • 命中 P_hit 在 S_probation 中： 将 P_hit 移到 S_protected 的MRU端。如果 S_protected 满了，其LRU端的页面 P_lru_prot 被移到 S_probation 的MRU端（如果 S_probation 也满了，再按其规则淘汰）。
        • 命中 P_hit 在 S_protected 中： 将 P_hit 移到 S_protected 的MRU端。

  • 鉴于模拟的复杂性，建议先实现一个简化的、结合频率和近期性的版本，例如：

    1. 维护一个LRU列表作为缓存。
    2. 维护所有已访问页面的频率计数。
    3. 当发生缺页且缓存满时，从LRU列表末尾取出页面 V_lru。
    4. 如果新页面 P_new 的频率 freq(P_new) 大于 freq(V_lru)，则换出 V_lru。
    5. 否则（freq(P_new) <= freq(V_lru)），换出 V_lru（此时表现为纯LRU的替换选择，但频率信息已用于未来的潜在决策）。
    6. 新加载的页面 P_new 放入LRU列表的MRU端，并更新其频率。

IV. 实验步骤

1. 对于每种工作负载类型（无局部性、80-20、顺序循环）：
   a. 为该工作负载生成或加载包含 TOTAL_ACCESSES 次页面引用的字符串。
   b. 对于每种页面替换算法：
   i. 对于每个缓存大小 C（来自预定义范围，例如，对于一般工作负载为10, 20, …, U_PAGES；对于顺序工作负载，特别测试 LOOP_PAGES-1, LOOP_PAGES, LOOP_PAGES+1）：
   1. 初始化模拟器：
   * 设置当前算法。
   * 设置当前缓存大小 C。
   * 清空缓存（置空）。
   * 将缺页计数器重置为0。
   * 重置算法特定状态（例如，FIFO队列、LRU列表、时钟指针/位）。
   2. 处理页面访问字符串：
   * 对于字符串中的每个 page_accessed：
   * 模拟器检查 page_accessed 是否在缓存中（“命中”）。
   * 如果命中：
   * 更新算法特定状态（例如，对于LRU，标记为MRU；对于时钟，设置使用位）。
   * 如果未命中（缺页）：
   * 增加缺页计数器。
   * 如果缓存有空闲页帧：将 page_accessed 加载到空闲页帧中。更新算法状态。
   * 如果缓存已满：
   * 应用当前页面替换算法选择一个 victim_page（牺牲页）。
   * 淘汰 victim_page。
   * 将 page_accessed 加载到释放的页帧中。
   * 更新算法状态。
   3. 记录结果： (工作负载类型, 算法名称, 缓存大小, 总缺页次数)。
   4. 计算缺页率： 缺页率 = 总缺页次数 / TOTAL_ACCESSES。记录此值。

V. 评估指标

• 主要指标：缺页率 (Page Fault Rate)。（或命中率 = 1 - 缺页率）。
• (可选次要指标)：磁盘写回次数。 如果模拟脏页（访问被标记为读/写），则计算脏页被淘汰的次数。这显示了保存修改数据的I/O开销。

VI. 数据分析与呈现

VII. 预期成果（待验证的假设）

(前面三种工作负载的预期成果同前，现在补充LFU和W-TinyLFU的预期)

• LFU：
  • 无局部性： 表现可能一般，类似于随机，因为它无法很好地适应变化。
  • 80-20 局部性： 应该表现良好，能识别并保留热点页面。但可能不如LRU灵活，如果热点集随时间变化，LFU的“历史污染”问题可能显现。
  • 顺序循环： 当缓存大小不足时，表现可能不佳，因为所有页面的频率会趋于一致，淘汰决策可能退化。
• W-TinyLFU (或其简化模拟版)：
  • 无局部性： 表现可能优于纯LFU，因为它结合了LRU的近期性，但仍受限于工作负载的随机性。
  • 80-20 局部性： 预期表现非常好，可能与LRU相当或更好，因为它既考虑频率也考虑近期性，能有效应对热点。
  • 顺序循环： 表现可能优于纯LFU和纯LRU。LRU部分有助于处理顺序性，而频率部分可以帮助区分不同阶段的页面。具体表现取决于其参数和简化程度。在完美循环且缓存略小的情况下，可能仍不如随机。

VIII. 可能的扩展（基础验证之外）

• 脏页： 修改工作负载以包含读/写信息。在模拟器中实现脏位跟踪。测量磁盘写回次数作为额外成本。
• 更多算法： 实现其他算法，如LFU（最不经常使用）或MRU（最近常使用）进行比较。
• 热启动 vs. 冷启动： 上述假设为冷启动（空缓存）。对于某些分析，可以在“预热”的缓存上运行模拟，尽管冷启动对于这些比较是典型的。
• 变化的局部性程度： 对于80-20工作负载，改变百分比（例如，90-10，70-30）以观察敏感度。
• 组合工作负载： 创建更复杂的访问模式。

关于W-TinyLFU模拟的进一步说明：
真正的W-TinyLFU实现较为复杂，涉及到概率数据结构（如Count-Min Sketch）和窗口机制。在模拟中，我们可以：

1. 使用精确频率计数： 代替概率数据结构，直接用哈希表记录每个页面的访问次数。这在模拟中是可行的，但要意识到这与实际内存受限环境下的TinyLFU实现有所不同。
2. 关注核心思想： 结合近期性（通过主缓存的LRU特性）和频率（通过全局频率计数）来做淘汰决策。简化的SLRU+TinyLFU思路是一个比较好的折中。