用C++手把手实现四种页面置换算法（附完整可运行代码）

从零实现四种页面置换算法：C++实战指南

当你第一次在操作系统课本上看到页面置换算法时，那些抽象的流程图和数学公式可能让你觉得这不过是又一个需要死记硬背的理论概念。但当你真正动手在C++中实现它们时，才会发现从理论到代码之间横亘着无数细节陷阱——指针越界、循环条件错误、状态更新遗漏，每一个小失误都可能导致整个算法行为异常。本文将带你完整实现FIFO、LRU、OPT和CLOCK四种经典置换算法，不仅提供可直接编译运行的代码，更会重点解析那些教科书上不会告诉你的实现技巧和调试经验。

1. 环境准备与基础框架

1.1 项目初始化

我们使用现代C++（C++11及以上）实现这些算法，确保代码清晰且安全。首先创建基本项目结构：

mkdir page_replacement && cd page_replacement touch main.cpp algorithms.h algorithms.cpp

在algorithms.h中定义我们的核心接口和数据结构：

#pragma once #include <vector> #include <string> class PageReplacer { public: virtual void access_page(int page_num) = 0; virtual int replace_page() = 0; virtual std::string get_name() const = 0; virtual void print_state() const = 0; virtual ~PageReplacer() = default; int page_faults = 0; std::vector<int> memory_frames; };

1.2 测试数据生成

为验证算法正确性，我们需要可重复的测试用例。这段代码生成包含局部性特征的页面序列：

std::vector<int> generate_page_sequence(int length) { std::vector<int> sequence; std::default_random_engine generator; std::uniform_int_distribution<int> distribution(0, 9); // 生成具有局部性的序列 int current = 0; for (int i = 0; i < length; ++i) { if (distribution(generator) < 3) { // 30%概率跳转到新区域 current = distribution(generator) * 10; } sequence.push_back(current + distribution(generator)); } return sequence; }

2. FIFO算法实现

2.1 核心思想与数据结构

FIFO（先进先出）是最直观的置换策略，可以用循环队列高效实现。关键数据结构：

class FIFOReplacer : public PageReplacer { std::queue<int> access_order; std::unordered_set<int> present_pages; size_t capacity; public: FIFOReplacer(size_t frame_count) : capacity(frame_count) {} // ... 实现接口方法 };

2.2 完整实现代码

void FIFOReplacer::access_page(int page_num) { if (present_pages.find(page_num) != present_pages.end()) { return; // 页面已在内存 } page_faults++; if (memory_frames.size() < capacity) { memory_frames.push_back(page_num); access_order.push(page_num); present_pages.insert(page_num); } else { int victim = access_order.front(); access_order.pop(); present_pages.erase(victim); auto it = std::find(memory_frames.begin(), memory_frames.end(), victim); *it = page_num; access_order.push(page_num); present_pages.insert(page_num); } }

注意：实际实现中我们使用标准库的queue和unordered_set，而非手动管理指针数组，这大大降低了出错概率。

2.3 常见陷阱与优化

• Belady异常：在某些访问模式下，增加物理帧数反而会导致缺页率上升
• 队列同步问题：确保内存帧列表与队列始终保持一致
• 性能优化：使用哈希表（unordered_set）加速页面存在性检查

3. LRU算法实现

3.1 两种实现方式对比

我们选择更高效的链表+哈希表实现：

class LRUReplacer : public PageReplacer { struct Node { int page; Node *prev, *next; Node(int p) : page(p), prev(nullptr), next(nullptr) {} }; Node *head, *tail; std::unordered_map<int, Node*> page_map; // ... 其他成员 };

3.2 关键操作实现

void LRUReplacer::access_page(int page_num) { if (page_map.count(page_num)) { // 移动到头节点 Node* node = page_map[page_num]; remove_node(node); add_to_head(node); return; } page_faults++; Node* new_node = new Node(page_num); if (memory_frames.size() < capacity) { memory_frames.push_back(page_num); } else { // 淘汰尾节点 Node* victim = tail; remove_node(victim); auto it = std::find(memory_frames.begin(), memory_frames.end(), victim->page); *it = page_num; delete victim; page_map.erase(victim->page); } add_to_head(new_node); page_map[page_num] = new_node; }

4. OPT算法实现

4.1 理论限制与实用实现

虽然OPT算法理论上无法实现（需要预知未来），但我们可以模拟已知访问序列的情况：

class OPTReplacer : public PageReplacer { std::vector<int> future_accesses; size_t current_index = 0; // ... 其他成员 };

4.2 置换策略实现

int OPTReplacer::find_victim() { int farthest = -1, victim = -1; for (int page : memory_frames) { auto it = std::find( future_accesses.begin() + current_index, future_accesses.end(), page ); if (it == future_accesses.end()) { return page; // 不再被访问的页面是理想选择 } int distance = it - (future_accesses.begin() + current_index); if (distance > farthest) { farthest = distance; victim = page; } } return victim; }

5. CLOCK算法实现

5.1 环形缓冲区设计

CLOCK算法（又称二次机会算法）通过访问位实现近似LRU的效果：

class ClockReplacer : public PageReplacer { struct Frame { int page; bool referenced; }; std::vector<Frame> frames; size_t hand = 0; // ... 其他成员 };

5.2 核心置换逻辑

void ClockReplacer::access_page(int page_num) { // 检查页面是否已在内存 for (auto& frame : frames) { if (frame.page == page_num) { frame.referenced = true; return; } } page_faults++; while (true) { Frame& current = frames[hand]; if (!current.referenced) { // 替换该页 current.page = page_num; current.referenced = true; hand = (hand + 1) % frames.size(); return; } current.referenced = false; hand = (hand + 1) % frames.size(); } }

6. 性能对比与可视化

6.1 测试框架实现

void test_algorithm(PageReplacer* algo, const std::vector<int>& sequence) { auto start = std::chrono::high_resolution_clock::now(); for (int page : sequence) { algo->access_page(page); } auto end = std::chrono::high_resolution_clock::now(); auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start); std::cout << algo->get_name() << " 结果:\n"; std::cout << "缺页次数: " << algo->page_faults << "\n"; std::cout << "缺页率: " << (float)algo->page_faults / sequence.size() << "\n"; std::cout << "耗时: " << duration.count() << "μs\n\n"; }

6.2 典型测试结果

使用序列[1,2,3,4,1,2,5,1,2,3,4,5]在3个物理帧下的表现：

7. 工程实践建议

1. 内存管理：

   • 使用智能指针（unique_ptr/shared_ptr）管理动态分配的对象
   • 在LRU实现中考虑对象池模式减少内存分配开销

2. 性能优化：

   • 对热点路径进行内联优化
   • 考虑无锁数据结构实现多线程版本

3. 测试策略：

   • 使用Google Test框架构建自动化测试
   • 生成包含不同局部性特征的测试序列

TEST(PageReplacerTest, FIFOBeladyAnomaly) { std::vector<int> sequence = {1,2,3,4,1,2,5,1,2,3,4,5}; FIFOReplacer small(3), large(4); for (int page : sequence) { small.access_page(page); large.access_page(page); } EXPECT_GT(small.page_faults, large.page_faults); }

在实现这些算法时，最深的体会是：理论上的时间复杂度分析在实际编码中可能被常数因子完全颠覆。比如理论上O(1)的哈希表操作，在小数据量时可能比线性搜索还慢。真正可靠的性能数据必须来自针对实际工作负载的基准测试。