设计一个简单的页面置换算法模拟程序 -

题目

设计一个简单的页面置换算法模拟程序

信息

类型：问答
难度：⭐⭐

考点

虚拟内存管理,页面置换算法,编程实现能力

快速回答

实现一个模拟程序，对比FIFO和LRU页面置换算法的缺页率：

使用固定内存页框（如3个）
模拟给定页面访问序列（如：1,2,3,4,1,2,5,1,2,3,4,5）
分别统计两种算法的缺页次数
输出每次访问后的内存状态

## 解析

原理说明

虚拟内存通过页面置换算法管理物理内存有限而虚拟地址空间大的矛盾。当发生缺页中断时，系统需要选择被替换的页面：

FIFO：替换最早进入内存的页面
LRU：替换最近最久未使用的页面

代码示例（Python）

def fifo(pages, capacity):
    s = []
    page_faults = 0
    for page in pages:
        if page not in s:
            if len(s) == capacity:
                s.pop(0)
            s.append(page)
            page_faults += 1
        # 输出当前内存状态
    return page_faults

def lru(pages, capacity):
    s = []
    page_faults = 0
    for page in pages:
        if page not in s:
            if len(s) == capacity:
                s.pop(0)
            s.append(page)
            page_faults += 1
        else:
            s.remove(page)
            s.append(page)  # 移动到末尾表示最近使用
    return page_faults

# 测试
pages = [1,2,3,4,1,2,5,1,2,3,4,5]
capacity = 3
print("FIFO缺页次数:", fifo(pages, capacity))
print("LRU缺页次数:", lru(pages, capacity))

最佳实践

使用双向链表+哈希表实现O(1)复杂度的LRU（实际系统常用）
添加详细注释说明算法步骤
扩展支持OPT（最优置换）算法对比

常见错误

FIFO实现未严格按进入顺序替换（错误使用栈结构）
LRU未正确更新页面访问时间（移动页面到最新位置）
忽略相同页面连续访问的特殊情况

扩展知识

Belady异常：FIFO算法中增加页框可能使缺页率升高
工作集模型：实际系统基于局部性原理动态调整内存分配
Clock算法：LRU近似实现，通过引用位减少开销
缺页率公式：缺页次数 / 总访问次数 × 100%