行，我直接给你一版“可当笔记+可当实现模板+可当面试答案”的压缩版，全塞满但保证结构清晰。你可以一屏一屏滚着读。

---

# 一、问题模型（统一抽象，后面所有算法共用）

**页面置换问题 = 给定引用串 + 固定物理页框数 → 最小化缺页次数**

* 输入：

  * `pages[]`：页面访问序列（虚拟页号）
  * `frames`：物理页框数（内存容量）
* 输出：

  * `page_faults`：缺页次数
* 核心状态：

  * `memory`：当前在内存中的页集合
  * 替换策略：当 `memory` 满时，决定踢谁

---

# 二、FIFO（First-In First-Out，最简单但很蠢）

## 思想

谁最早进来谁先滚（队列）

## 特点

* 实现极简单
* 会出现 **Belady异常（页框增加反而缺页更多）**

## 数据结构

* 队列 `queue`
* 集合 `set`（O(1)判断是否命中）

## 过程

```
访问 page:
  if page 在 memory:
    命中
  else:
    缺页
    if memory 未满:
        加入 queue + set
    else:
        victim = queue.pop_front()
        删除 victim
        插入新 page
```

## C++实现

```cpp
int FIFO(const vector<int>& pages, int capacity) {
    unordered_set<int> memory;
    queue<int> q;
    int faults = 0;

    for (int p : pages) {
        if (memory.count(p)) continue;

        faults++;
        if (memory.size() == capacity) {
            int victim = q.front(); q.pop();
            memory.erase(victim);
        }
        memory.insert(p);
        q.push(p);
    }
    return faults;
}
```

---

# 三、OPT（Optimal，理论最优，用来对比）

## 思想

淘汰 **未来最久不会再用** 的页

## 特点

* 最优（理论下界）
* 不可实现（需要预知未来）

## 数据结构

* 当前内存 `memory`
* 每次缺页 → 扫描未来找“最晚使用”的

## 过程核心

```
for 每个 page:
  if miss:
    if 未满: 加入
    else:
      对 memory 中每个页：
        找它下一次出现的位置
      选“最远”或“不再出现”的
```

## C++实现

```cpp
int OPT(const vector<int>& pages, int capacity) {
    vector<int> memory;
    int faults = 0;

    for (int i = 0; i < pages.size(); i++) {
        int p = pages[i];

        if (find(memory.begin(), memory.end(), p) != memory.end())
            continue;

        faults++;

        if (memory.size() < capacity) {
            memory.push_back(p);
        } else {
            int idx = -1, farthest = i;

            for (int j = 0; j < memory.size(); j++) {
                int k;
                for (k = i + 1; k < pages.size(); k++) {
                    if (pages[k] == memory[j]) break;
                }
                if (k > farthest) {
                    farthest = k;
                    idx = j;
                }
            }
            memory[idx] = p;
        }
    }
    return faults;
}
```

---

# 四、LRU（Least Recently Used，最重要）

## 思想

淘汰 **最近最久没用** 的页（用“过去”预测“未来”）

## 特点

* 实际系统常用
* 不会出现 Belady 异常
* 需要维护“访问顺序”

---

## 实现1：链表 + 哈希（标准解）

### 数据结构

* `list`：维护访问顺序（最新在前）
* `unordered_map`：页 → 迭代器

### 操作复杂度

* 全部 O(1)

### C++实现

```cpp
int LRU(int capacity, const vector<int>& pages) {
    list<int> lru;
    unordered_map<int, list<int>::iterator> pos;
    int faults = 0;

    for (int p : pages) {
        if (pos.count(p)) {
            lru.erase(pos[p]);
        } else {
            faults++;
            if (lru.size() == capacity) {
                int victim = lru.back();
                lru.pop_back();
                pos.erase(victim);
            }
        }
        lru.push_front(p);
        pos[p] = lru.begin();
    }
    return faults;
}
```

---

## 实现2：时间戳（简单但慢）

```cpp
int LRU_slow(const vector<int>& pages, int capacity) {
    vector<int> memory;
    unordered_map<int, int> last_used;
    int faults = 0;

    for (int i = 0; i < pages.size(); i++) {
        int p = pages[i];

        if (find(memory.begin(), memory.end(), p) != memory.end()) {
            last_used[p] = i;
            continue;
        }

        faults++;

        if (memory.size() < capacity) {
            memory.push_back(p);
        } else {
            int lru_page = memory[0];
            for (int m : memory) {
                if (last_used[m] < last_used[lru_page])
                    lru_page = m;
            }
            replace(memory.begin(), memory.end(), lru_page, p);
        }
        last_used[p] = i;
    }
    return faults;
}
```

---

# 五、LFU（Least Frequently Used）

## 思想

淘汰访问次数最少的页

## 问题

* “历史包袱”：旧热点永远不走
* 需要加 aging（衰减）

---

## 基本实现（简化版）

```cpp
int LFU(const vector<int>& pages, int capacity) {
    unordered_map<int, int> freq;
    vector<int> memory;
    int faults = 0;

    for (int p : pages) {
        if (find(memory.begin(), memory.end(), p) != memory.end()) {
            freq[p]++;
            continue;
        }

        faults++;

        if (memory.size() < capacity) {
            memory.push_back(p);
        } else {
            int victim = memory[0];
            for (int m : memory) {
                if (freq[m] < freq[victim])
                    victim = m;
            }
            replace(memory.begin(), memory.end(), victim, p);
            freq.erase(victim);
        }
        freq[p] = 1;
    }
    return faults;
}
```

---

# 六、Clock（Second Chance，操作系统最常用）

## 思想（LRU的近似）

* 每页有一个 **引用位 R**
* 扫描环：

  * R=1 → 置0，跳过（给第二次机会）
  * R=0 → 淘汰

## 数据结构

* 环形数组
* `ref_bit[]`
* 指针 `hand`

---

## 过程

```
while true:
  if ref_bit[hand] == 0:
    替换
    break
  else:
    ref_bit[hand] = 0
    hand++
```

---

## C++实现

```cpp
int Clock(const vector<int>& pages, int capacity) {
    vector<int> memory(capacity, -1);
    vector<int> ref(capacity, 0);
    int hand = 0, faults = 0;

    for (int p : pages) {
        bool hit = false;
        for (int i = 0; i < capacity; i++) {
            if (memory[i] == p) {
                ref[i] = 1;
                hit = true;
                break;
            }
        }
        if (hit) continue;

        faults++;

        while (true) {
            if (ref[hand] == 0) {
                memory[hand] = p;
                ref[hand] = 1;
                hand = (hand + 1) % capacity;
                break;
            } else {
                ref[hand] = 0;
                hand = (hand + 1) % capacity;
            }
        }
    }
    return faults;
}
```

---

# 七、算法对比（你考试/面试直接用）

| 算法    | 是否最优  | 是否可实现   | 时间复杂度 | 是否Belady异常 |
| ----- | ----- | ------- | ----- | ---------- |
| FIFO  | 否     | 是       | O(1)  | 会          |
| OPT   | 是     | 否       | O(n²) | 不会         |
| LRU   | 近似最优  | 是       | O(1)  | 不会         |
| LFU   | 不稳定   | 是       | O(n)  | 不一定        |
| Clock | LRU近似 | 是（OS常用） | O(1)  | 不会         |

---

# 八、核心理解（你真正该掌握的）

你别死记算法，要抓住这条主线：

**页面置换的本质 = 用过去信息预测未来访问**

* FIFO：完全不预测 → 垃圾
* OPT：完美预测 → 理论
* LRU：用“最近”预测 → 工程最佳
* Clock：LRU的低成本近似 → OS实际用
* LFU：用“频率”预测 → 容易翻车

---

# 九、你如果继续往下学（很关键）

你下一步应该看：

* 工作集模型（Working Set）
* 局部性原理（Temporal / Spatial Locality）
* 页抖动（Thrashing）
* Linux实际实现（active/inactive list，本质是LRU变种）

---

如果你要，我下一步可以直接给你：

**“Linux 内核到底怎么做页面置换（不是课本版，是源码级逻辑）”**
那个才是真正有含金量的版本。

---

**LRU**（Least Recently Used，最近最少使用）是一种非常经典的**缓存淘汰算法**。

它的核心思想基于“时间局部性”原理：**如果一个数据在最近一段时间内没有被访问过，那么在将来它被访问的可能性也比较小。** 因此，当缓存空间存满时，我们会优先清理掉那个“最久未被访问”的数据。

---

### 1. LRU 的工作机制

想象一个有固定容量的队列，数据流的操作遵循以下规则：

1.  **访问数据**：
    * 如果数据已经在缓存中（命中），则将其移动到队列的**最前端**（表示它刚被用过）。
    * 如果数据不在缓存中（未命中），将其插入到队列的**最前端**。
2.  **淘汰数据**：
    * 当新数据进入且缓存已满时，直接丢弃队列**末尾**的数据，因为它就是那个“最久没用过”的对象。



---

### 2. 工业级实现：哈希表 + 双向链表

在实际编程中（如 Redis 或操作系统内存管理），为了达到 $O(1)$ 的操作效率，通常采用 **Hash Map + Doubly Linked List** 的组合结构：

* **双向链表 (Double Linked List)**：负责维护数据的**访问顺序**。
    * 靠近 `Head` 的是最近访问的。
    * 靠近 `Tail` 的是最久未访问的。
* **哈希表 (Hash Map)**：负责**快速定位**。
    * Key 是数据的标识，Value 是指向链表节点的**指针/引用**。这样不需要遍历链表就能找到数据。

#### 为什么不用普通数组或单链表？
* **数组**：虽然查询快，但移动元素（把中间的挪到开头）需要 $O(n)$，代价太高。
* **单链表**：删除末尾节点时，无法在 $O(1)$ 时间内找到前驱节点。

---

### 3. LRU 的优缺点

| 优点 | 缺点 |
| :--- | :--- |
| **性能均衡**：对具有时间局部性的数据流非常高效。 | **缓存污染**：如果偶尔发生一次大规模的“全表扫描”，会导致热点数据全部被踢出。 |
| **实现简单**：逻辑清晰，是面试和系统设计中的首选。 | **无法感知频率**：一个数据即便访问了 1000 次，只要它比只访问 1 次的数据更早被访问，它也会被淘汰。 |

---

### 4. 代码实现参考 (Rust)

考虑到你对系统级语言的偏好，这里给出一个简单的逻辑结构示例：

```rust
use std::collections::HashMap;

struct LRUCache {
    capacity: usize,
    // 实际生产中通常使用双向链表配合 Raw Pointer 或 RefCell
    // 这里示意：Map 存 Key -> (Value, Access_Timestamp)
}

impl LRUCache {
    fn get(&mut self, key: i32) -> Option<i32> {
        // 1. 在 Map 中找
        // 2. 如果找到，更新该节点的顺序（移到链表头）
        // 3. 返回值
        None
    }

    fn put(&mut self, key: i32, value: i32) {
        // 1. 如果 Key 存在，更新 Value 并移到头
        // 2. 如果不存在，插入新节点到头
        // 3. 如果超过 capacity，删除链表尾部节点，并同步从 Map 中移除
    }
}
```

### 下一步建议
LRU 虽然经典，但在面对高并发或特定访问模式时有其局限性。你想了解它的改进版 **LRU-K**（解决缓存污染问题）或者像 Linux 内核中使用的 **Clock 算法**（更节省内存的近似 LRU 实现）吗？