🚀 LRU 页面置换算法

在操作系统内存管理中,除了 FIFO,另一种更聪明且常用的页面置换策略是 —— LRU 页面置换算法


📌 一、什么是 LRU 页面置换算法?

LRU(Least Recently Used,最近最少使用)页面置换算法是这样一种策略:

淘汰最近最久未被访问过的页面。

直白地说:如果一个页面很久没用了,那么它以后可能也不怎么用,所以优先把它换出去。

✅ 特点:

  • 需要记录页面最近的访问历史
  • 淘汰“最久没用”的页面,而不是最早进入的
  • 通常使用栈(Stack)链表(List) 或 **时间戳(Timestamp)**结构实现

❗ 二、缺页中断机制简介(同样适用 LRU)

当访问一个不在内存中的页面时:

  1. 触发缺页中断
  2. 如果内存满了,选择最近最久未使用的页面进行置换
  3. 加载新页面并恢复执行

💡 缺页次数依然是评估 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 异常 ❌ 不会出现
优点 高效,缺页少,符合程序局部性原理
缺点 需要维护访问时间,稍复杂