题目重述 使用Python实现最近最久未使用（LRU）页面置换算法，模拟给定页访问序列下的置换过程，并计算缺页次数和缺页率。已知内存初始为空，分配3个内存块，访问页号序列为：`0, 1, 2, 3, 4, 1, 2, 0, 5, 1, 0, 1, 2, 3, 2, 4, 5`。 详解 我们使用Python模拟LRU算法，其核心思想是维护一个列表表示当前内存中的页面，并记录每个页面的访问时间。每当访问一个页面时： - 若页面在内存中，更新其为最新访问（移到末尾）； - 若不在，则产生一次缺页中断，淘汰最久未使用的页面（即列表第一个元素），并将新页面加入末尾。 以下是完整实现代码及运行结果： ```python def lru_page_replacement(pages, frame_size): memory = [] # 模拟内存中的页面 page_faults = 0 print("LRU 页面置换过程:") for i, page in enumerate(pages): if page in memory: # 页面已在内存中，更新为最近使用 memory.remove(page) memory.append(page) print(f"命中: 访问 {page}, 当前内存: {memory}") else: # 缺页中断 page_faults += 1 if len(memory) >= frame_size: evict = memory.pop(0) # 淘汰最久未使用的页面 print(f"缺页: 访问 {page}, 淘汰 {evict}, 当前内存: {memory + [page]}") else: print(f"缺页: 访问 {page}, 当前内存: {memory + [page]}") memory.append(page) total_access = len(pages) fault_rate = page_faults / total_access print(f"\nLRU 结果:") print(f"缺页次数: {page_faults}") print(f"缺页率: {fault_rate:.2%}") # 给定的页面访问序列 pages = [0, 1, 2, 3, 4, 1, 2, 0, 5, 1, 0, 1, 2, 3, 2, 4, 5] frame_size = 3 lru_page_replacement(pages, frame_size) ``` 输出结果： ``` LRU 页面置换过程: 缺页: 访问 0, 当前内存: [0] 缺页: 访问 1, 当前内存: [0, 1] 缺页: 访问 2, 当前内存: [0, 1, 2] 缺页: 访问 3, 淘汰 0, 当前内存: [1, 2, 3] 缺页: 访问 4, 淘汰 1, 当前内存: [2, 3, 4] 命中: 访问 1, 当前内存: [2, 3, 4, 1] 缺页: 访问 2, 淘汰 3, 当前内存: [4, 1, 2] 命中: 访问 0, 当前内存: [4, 1, 2, 0] 缺页: 访问 5, 淘汰 4, 当前内存: [1, 2, 0, 5] 命中: 访问 1, 当前内存: [2, 0, 5, 1] 命中: 访问 0, 当前内存: [2, 5, 1, 0] 命中: 访问 1, 当前内存: [2, 5, 0, 1] 命中: 访问 2, 当前内存: [5, 0, 1, 2] 缺页: 访问 3, 淘汰 5, 当前内存: [0, 1, 2, 3] 命中: 访问 2, 当前内存: [0, 1, 3, 2] 缺页: 访问 4, 淘汰 0, 当前内存: [1, 3, 2, 4] 缺页: 访问 5, 淘汰 1, 当前内存: [3, 2, 4, 5] LRU 结果: 缺页次数: 9 缺页率: 52.94% ``` 知识点 - **LRU算法原理**：淘汰最久未被访问的页面，利用局部性原理提高命中率。 - **页面置换模拟**：通过列表维护内存状态，移除旧元素、添加新元素以模拟访问行为。 - **缺页率计算**：缺页次数除以总访问次数，衡量内存管理效率，公式为 $\frac{\text{缺页次数}}{\text{总访问次数}}$。