💾 内存页面淘汰算法详解

📚 什么是页面淘汰算法？

在操作系统内存管理中，当内存已满但需要加载新的页面时，需要选择某个页面将其换出到外存，这个选择策略就是页面淘汰算法（Page Replacement Algorithm）。

目标：减少页面缺页率，提高系统性能。

🎯 主要页面淘汰算法

1. OPT（最佳置换算法）

原理：选择未来最长时间内不再被访问的页面淘汰。

特点：理论上的最优算法，但无法实现（需要预知未来）。

作用：作为其他算法的性能基准。

2. FIFO（先进先出算法）

原理：选择最早进入内存的页面淘汰。

实现：使用队列管理页面。

缺点：可能淘汰频繁使用的页面（Belady异常）。

3. LRU（最近最少使用算法）⭐

原理：选择最近最久未使用的页面淘汰。

实现：维护访问时间戳或使用栈。

优点：性能接近OPT，实际应用中常用。

缺点：需要硬件支持，开销较大。

4. LFU（最不经常使用算法）

原理：选择访问次数最少的页面淘汰。

实现：为每个页面维护访问计数器。

缺点：某些页面初期频繁访问但之后不再使用，难以淘汰。

5. Clock（时钟算法）

原理：环形队列+CLOCK指针，近似LRU。

实现：每个页面有一个访问位，淘汰时检查：

优点：开销比LRU小，性能较好。

🎬 LRU算法动态演示

交互式LRU演示

使用说明：
1. 设置内存块数（默认：3）
2. 输入页面访问序列（如：1,2,3,4,1,2,5,1,2,3）
3. 点击"开始演示"观看LRU算法执行过程

🎬 FIFO算法动态演示

交互式FIFO演示

📊 算法对比

算法 淘汰原则 实现难度 性能 缺点
OPT 未来最久不使用 无法实现 最优（理论） 需要预知未来
FIFO 最早进入内存 简单 较差 Belady异常
LRU 最近最久未使用 中等 优秀 硬件开销大
LFU 访问次数最少 中等 良好 初期频繁页面难淘汰
Clock 近似LRU 较简单 良好 性能略低于LRU

💻 LRU算法代码实现示例

// JavaScript实现LRU算法
class LRU {
    constructor(capacity) {
        this.capacity = capacity;
        this.cache = new Map(); // 维护插入顺序
    }

    access(page) {
        if (this.cache.has(page)) {
            // 页面命中，删除后重新插入（更新到最新）
            this.cache.delete(page);
            this.cache.set(page, true);
            return 'HIT';
        } else {
            // 页面缺失
            if (this.cache.size >= this.capacity) {
                // 内存已满，淘汰最近最少使用的页面（Map的第一个元素）
                const oldestPage = this.cache.keys().next().value;
                this.cache.delete(oldestPage);
                console.log(`淘汰页面：${oldestPage}`);
            }
            this.cache.set(page, true);
            return 'FAULT';
        }
    }
}

// 使用示例
const lru = new LRU(3);
const sequence = [1, 2, 3, 4, 1, 2, 5, 1, 2, 3];
let faults = 0;

sequence.forEach(page => {
    const result = lru.access(page);
    console.log(`访问页面${page}：${result}`);
    if (result === 'FAULT') faults++;
});

console.log(`总缺页次数：${faults}`);

🎓 知识点总结

关键概念：

🔗 实际应用场景

LRU的应用

📖 内存页面淘汰算法 - 操作系统核心概念

交互式学习工具 | 动态可视化演示