• 创建/更新时间:2025年12月20日

CAPSA 是一个轻量级缓存性能模拟器,用于在相同的访问序列上比较 ARC、LRU、LFU、FIFO、2Q 和理论最优 OPT 算法。所有内置负载由 capsa/trace_suite.py 使用基于函数的脚本动态生成,无需预生成的跟踪文件。

• 固定缓存大小:32 页
• 固定请求数:每个负载 50000 次请求
• 7 个内置负载:覆盖不同算法的优势场景
• 两种使用模式:带数字参数的命令行或交互式 CLI 菜单
• 动态生成:所有负载实时生成,保证可重现性
• 简单设计:使用循环、条件分支和均匀分布,避免复杂随机

• Python 3.10+

# 克隆或下载项目后,直接运行
python main.py

# 方式1:交互式菜单(推荐)
python main.py
# 方式2:命令行参数
python main.py -1 # 运行负载 1
python main.py -1 -3 -5 # 运行负载 1、3 和 5
python main.py -7 # 运行第 7 个负载(WL07)
# 方式3:运行所有负载并显示汇总表(推荐用于快速对比)
python main.py -all # 运行所有负载,显示美观的命中率汇总表
# 生成实际负载(可选)
python generate_fixed_traces.py

交互式菜单将显示所有 7 个负载及其特征,您可以:

• 输入用空格或逗号分隔的负载编号(例如,1 3 5 或 1,3,5)
• 按 Enter 运行所有负载
• 选择多个负载进行批量分析

以下描述直接对照 capsa/trace_suite.py,确保注释与实现一一对应,并聚焦于设计思路与关键特征。

设计思路

• 热集:页面 1-5,在每轮中分别访问 100 次(合计 500 次请求)。
• 冷集:页面 6-105,每轮各访问 1 次(100 次请求)。
• 共 600 次请求/轮,循环约 83 轮后裁剪到 50000 次请求。

关键特征

• 热集频率远高于冷集,LFU 能稳定锁定热页。
• LRU/2Q 需要不断腾挪冷页,容易被冷集刷新。

设计思路

• 热集:页面 1-20,每轮 10 次访问(200 次请求)。
• 温集:页面 21-60,每轮 1 次访问(40 次请求)。
• 每轮 240 次请求,循环约 208 轮并裁剪至 50000。

关键特征

• 工作集 60 页覆盖热+温,远大于缓存 32 页。
• 热集与温集频率差距有限,测试 LFU 在"刚好逼近缓存"时的稳定性。

设计思路

• 维护一个 28 页窗口(略小于缓存 32 页)。
• 窗口每次滑动 1 页,按顺序访问窗口内的所有页面。
• 通过移动窗口循环覆盖数百页,并裁剪为 50000 次请求。

关键特征

• 纯粹的最近使用场景,无频率信息可用。
• LRU/ARC 等基于 recency 的算法可以稳定保持 28 页工作集。

设计思路

• 污染阶段:页面 1-32 被访问 50 轮,使 LFU 计数拉满。
• 切换阶段:立即改为循环访问页面 33-64,直到补足 50000 次请求。
• 由于切换阶段页面数等于缓存容量,命中率理论上可接近 100%。

关键特征

• LFU 在切换后仍"抱紧"旧热集,命中率暴跌。
• 只关注栈距离的算法(LRU、FIFO、ARC、2Q)能快速替换旧页面,几乎全命中。

设计思路

• 热浪:三个 10 页热集依次访问,重复次数依次为 5/4/3。
• 双滑窗:两个 32 页窗口在不同起点扫描。
• 热桥:热集 1 与热集 3 交替访问以恢复热点。
• 大窗口:两个 48 页窗口继续扫描。
• 冷扫描:一次性访问 200 个唯一页面后进入下一轮,循环直至 50000。

关键特征

• 单轮内包含频率积累、短窗口、长窗口与冷扫描,模式切换极为频繁。
• 考察 2Q/ARC 对多阶段突变的响应,以及算法如何在极端"扫描夹层"中保住热集。

设计思路

• 阶段 A:页面 1-6 重复 12 次(72 次请求)。
• 阶段 B:30 页滑动窗口一次扫描,起点随轮漂移。
• 阶段 C:页面 31-36 循环 6 次,并插入桥接页 90-105。
• 阶段 D:扫描 60 个唯一页面后立即回到两个热集。

关键特征

• 以更短的四段结构复刻 ARC 常见场景:频率 → 最近使用 → 热集切换 → 冷扫描。
• 能快速观察 ARC 如何凭借 T1/T2 调节跨阶段恢复命中率。

设计思路

• 每 5000 次请求切换一次模式:
  • 模式 1:热集(1-5)高频 + 冷集(6-20)单次访问。
  • 模式 2:30 页滑动窗口,窗口起点随阶段推进。
  • 模式 3:长扫描中每 50 次插入 5 次热集访问。
• 循环三个模式直到 50000 次请求。

关键特征

• 将频率、最近使用、扫描三个典型场景以固定节奏串联。
• 主要用于验证 ARC / 2Q 在长期运行中面对模式突变的自恢复能力。

以下数据由 python main.py -all 在 2025年11月25日(缓存 32 页、每个负载 50000 次请求)实测获得,列顺序固定为 LFU / LRU / FIFO / 2Q / ARC / OPT(单位:命中率 %):

该表可直接复制到报告中,用于分析各算法在不同负载下的真实表现。

主入口点,提供命令行接口。支持三种模式:

• 数字参数模式:使用 -1, -2 等参数直接指定负载
• 交互式菜单模式:不带参数运行,显示所有负载供选择
• 汇总模式:使用 -all 参数运行所有负载并显示汇总表

主要功能:

• 解析命令行参数或显示交互菜单
• 调用 trace_suite.py 生成负载序列
• 使用 simulator.py 运行模拟
• 使用 metrics.py 生成性能报告

可选工具,将动态生成的负载序列导出为文本文件。生成的 .trace 文件保存在 traces/ 目录中,可用于外部分析或调试。

定义统一的缓存接口 Cache 抽象基类。所有缓存算法必须实现:

• access(page_id: int) -> bool:访问页面,返回命中(True)或未命中(False)
• get_stats() -> Dict[str, int]:返回内部统计信息(如命中/未命中计数)

这确保了所有算法具有统一的接口,便于在相同条件下进行比较。

包含 6 种缓存算法的独立实现:

• lru.py:最近最少使用(LRU)算法,基于 OrderedDict 实现 O(1) 操作
• lfu.py:最不常用(LFU)算法,按访问频率和 LRU 共同淘汰
• fifo.py:先进先出(FIFO)算法,使用队列实现
• arc.py:自适应替换缓存(ARC),实现自适应的 LRU/LFU 混合策略
• two_q.py:2Q 双队列算法,利用 FIFO 热身队列与 LRU 主队列结合
• opt.py:理论最优(OPT)算法,需要预知未来访问序列

每个实现都是独立的,可以单独测试和优化。

模拟器核心,负责执行模拟过程:

• Simulator 类:顺序读取跟踪序列,将每个页面访问传递给缓存算法
• SimulationResult 数据类:记录模拟结果,包括命中率、未命中数、执行时间等
• 使用 time.perf_counter_ns() 测量算法开销(非实际 I/O 时间)

性能指标收集器和报告生成器:

• MetricsCollector 类:将 SimulationResult 转换为人类可读的报告
• ReportConfig 数据类:配置报告格式和内容
• 生成包含命中率排名、运行时间排名等信息的详细报告

负载定义和生成模块,这是项目的核心:

• 定义 7 个固定负载的生成函数
• 每个负载使用函数式编程方式生成,保证可重现性
• TraceRecipe 数据类:描述每个负载的元数据(键、文件名、类别、目标等)
• repeat_function():辅助函数,用于重复执行某个函数
• trim_to_target():辅助函数,确保生成的序列长度恰好为 50000

• 所有负载都是动态生成的,不需要预生成的跟踪文件
• 所有模拟的缓存大小固定为 32 页
• 每个负载生成恰好 50000 次请求
• 所有负载使用简单的循环、条件分支和均匀分布,避免复杂随机
• 确保不同算法命中率差异明显(10%、30%、60%等),便于对比分析
• 代码注释为中文,便于理解和维护