11 KiB
11 KiB
行，我直接给你一版“可当笔记+可当实现模板+可当面试答案”的压缩版，全塞满但保证结构清晰。你可以一屏一屏滚着读。
一、问题模型（统一抽象，后面所有算法共用）
页面置换问题 = 给定引用串 + 固定物理页框数 → 最小化缺页次数
-
输入：
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++实现
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++实现
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++实现
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：时间戳（简单但慢）
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（衰减）
基本实现（简化版）
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++实现
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 的工作机制
想象一个有固定容量的队列，数据流的操作遵循以下规则：
- 访问数据：
- 如果数据已经在缓存中（命中），则将其移动到队列的最前端（表示它刚被用过）。
- 如果数据不在缓存中（未命中），将其插入到队列的最前端。
- 淘汰数据：
- 当新数据进入且缓存已满时，直接丢弃队列末尾的数据，因为它就是那个“最久没用过”的对象。
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)
考虑到你对系统级语言的偏好，这里给出一个简单的逻辑结构示例：
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 实现）吗？