474 lines
11 KiB
Markdown
474 lines
11 KiB
Markdown
行，我直接给你一版“可当笔记+可当实现模板+可当面试答案”的压缩版，全塞满但保证结构清晰。你可以一屏一屏滚着读。
|
||
|
||
---
|
||
|
||
# 一、问题模型（统一抽象，后面所有算法共用）
|
||
|
||
**页面置换问题 = 给定引用串 + 固定物理页框数 → 最小化缺页次数**
|
||
|
||
* 输入：
|
||
|
||
* `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 实现）吗？ |