🚀 LRU 页面置换算法
在操作系统内存管理中,除了 FIFO,另一种更聪明且常用的页面置换策略是 —— LRU 页面置换算法
📌 一、什么是 LRU 页面置换算法?
LRU(Least Recently Used,最近最少使用)页面置换算法是这样一种策略:
淘汰最近最久未被访问过的页面。
直白地说:如果一个页面很久没用了,那么它以后可能也不怎么用,所以优先把它换出去。
✅ 特点:
- 需要记录页面最近的访问历史
- 淘汰“最久没用”的页面,而不是最早进入的
- 通常使用栈(Stack)、链表(List) 或 **时间戳(Timestamp)**结构实现
❗ 二、缺页中断机制简介(同样适用 LRU)
当访问一个不在内存中的页面时:
- 触发缺页中断
- 如果内存满了,选择最近最久未使用的页面进行置换
- 加载新页面并恢复执行
💡 缺页次数依然是评估 LRU 表现的关键指标,通常 比 FIFO 更少的缺页次数。
🧪 三、LRU 算法示例分析
假设页面访问序列为:
[7, 0, 1, 2, 0, 3, 0, 4]
帧数 3,使用 LRU 策略:
步骤 | 页面访问 | 内存状态 | 缺页? |
---|---|---|---|
1 | 7 | 7 | ✅ |
2 | 0 | 7 0 | ✅ |
3 | 1 | 7 0 1 | ✅ |
4 | 2 | 0 1 2(7 最久未用,被换出) | ✅ |
5 | 0 | 0 1 2(已存在) | ❌ |
6 | 3 | 1 2 3(0 最久未用,被换出) | ✅ |
7 | 0 | 2 3 0(1 最久未用,被换出) | ✅ |
8 | 4 | 3 0 4(2 最久未用,被换出) | ✅ |
缺页次数:6
🔧 四、C语言实现(函数封装版)
#include <stdio.h>
int find_lru(int time[], int frames) {
int min = time[0], pos = 0;
for (int i = 1; i < frames; i++) {
if (time[i] < min) {
min = time[i];
pos = i;
}
}
return pos;
}
int lru_page_replacement(int pages[], int n, int frames) {
int memory[frames];
int time[frames];
int counter = 0, faults = 0;
for (int i = 0; i < frames; i++) memory[i] = -1;
for (int i = 0; i < n; i++) {
int found = 0;
for (int j = 0; j < frames; j++) {
if (memory[j] == pages[i]) {
found = 1;
time[j] = counter++; // 更新访问时间
break;
}
}
if (!found) {
int pos = -1;
for (int j = 0; j < frames; j++) {
if (memory[j] == -1) {
pos = j;
break;
}
}
if (pos == -1) pos = find_lru(time, frames);
memory[pos] = pages[i];
time[pos] = counter++;
faults++;
}
}
return faults;
}
int main() {
int pages[] = {7, 0, 1, 2, 0, 3, 0, 4};
int n = sizeof(pages) / sizeof(pages[0]);
int frames = 3;
int faults = lru_page_replacement(pages, n, frames);
printf("缺页中断次数: %d\n", faults); // 应输出 6
return 0;
}
🦀 五、Rust实现(函数封装版)
use std::collections::HashMap;
fn lru_page_replacement(pages: &[i32], frames: usize) -> usize {
let mut memory = Vec::new();
let mut last_used = HashMap::new();
let mut faults = 0;
let mut time = 0;
for &page in pages {
time += 1;
if memory.contains(&page) {
last_used.insert(page, time);
} else {
if memory.len() == frames {
// 找出最久未用的页面
let lru_page = memory
.iter()
.min_by_key(|&&p| last_used.get(&p).unwrap_or(&0))
.copied()
.unwrap();
memory.retain(|&p| p != lru_page);
}
memory.push(page);
last_used.insert(page, time);
faults += 1;
}
}
faults
}
fn main() {
let pages = vec![7, 0, 1, 2, 0, 3, 0, 4];
let frames = 3;
let faults = lru_page_replacement(&pages, frames);
println!("缺页中断次数: {}", faults); // 应输出 6
}
⚡ 六、为什么 LRU 不会出现 Belady 异常?
✅ LRU 是栈算法(Stack Algorithm)的一种,特点是:
- 随着帧数增加,缺页次数单调不增
- 永远不会因为增加帧数导致缺页次数增加
- 相比 FIFO 更聪明,性能更好
因此,LRU 不会出现 Belady 异常!
🎉 总结一览表
项目 | 内容 |
---|---|
页面置换算法 | LRU(最近最少使用) |
基本数据结构 | 哈希表 + 队列(或链表) |
缺页中断机制 | 淘汰最近最久未使用页面 |
Belady 异常 | ❌ 不会出现 |
优点 | 高效,缺页少,符合程序局部性原理 |
缺点 | 需要维护访问时间,稍复杂 |