页面置换算法作业
题目信息
页面访问序列：1, 2, 3, 2, 1, 4, 3, 1, 4, 5, 4, 1
物理块数：M = 3
总访问次数：12次
1. FIFO算法（先进先出）
原理： 最早进入内存的页面最先被替换
详细过程：
访问页面: 1 2 3 2 1 4 3 1 4 5 4 1
步骤: 1 2 3 4 5 6 7 8 9 10 11 12
物理块1: 1 1 1 1 1 4 4 4 4 5 5 5
物理块2: 2 2 2 2 2 3 3 3 3 4 4
物理块3: 3 3 3 3 3 1 1 1 1 1
缺页情况: × × × √ √ × × × × × × √访问1：物理块空，装入1 → 缺页
访问2：物理块未满，装入2 → 缺页
访问3：物理块未满，装入3 → 缺页
访问2：2在物理块中 → 命中
访问1：1在物理块中 → 命中
访问4：物理块满，替换最早的1，装入4 → 缺页
访问3：3在物理块中 → 命中
访问1：物理块满，替换最早的2，装入1 → 缺页
访问4：4在物理块中 → 命中
访问5：物理块满，替换最早的3，装入5 → 缺页
访问4：4在物理块中 → 命中
访问1：1在物理块中 → 命中
FIFO结果：
缺页次数：6次
缺页率：6/12 = 50%
2. LRU算法（最近最少使用）
原理： 替换最长时间未被访问的页面
详细过程：
访问页面: 1 2 3 2 1 4 3 1 4 5 4 1
步骤: 1 2 3 4 5 6 7 8 9 10 11 12
物理块1: 1 1 1 2 1 1 3 1 1 5 4 1
物理块2: 2 2 2 2 4 4 4 4 4 5 5
物理块3: 3 3 3 3 3 3 3 3 3 3
缺页情况: × × × √ √ × √ √ √ × √ √
使用时间: 1 2 3 2 1 4 3 1 4 5 4 1访问1：装入1，时间戳=1 → 缺页
访问2：装入2，时间戳=2 → 缺页
访问3：装入3，时间戳=3 → 缺页
访问2：2命中，更新时间戳=4 → 命中
访问1：1命中，更新时间戳=5 → 命中
访问4：替换最久未用的3，装入4，时间戳=6 → 缺页
访问3：替换最久未用的2，装入3，时间戳=7 → 缺页
访问1：1命中，更新时间戳=8 → 命中
访问4：4命中，更新时间戳=9 → 命中
访问5：替换最久未用的3，装入5，时间戳=10 → 缺页
访问4：4命中，更新时间戳=11 → 命中
访问1：1命中，更新时间戳=12 → 命中
LRU结果：
缺页次数：5次
缺页率：5/12 ≈ 41.67%
3. OPT算法（最优置换）
原理： 替换将来最长时间不会被访问的页面
详细过程：
访问页面: 1 2 3 2 1 4 3 1 4 5 4 1
步骤: 1 2 3 4 5 6 7 8 9 10 11 12
物理块1: 1 1 1 1 1 1 3 1 1 1 4 1
物理块2: 2 2 2 2 4 4 4 4 5 5 5
物理块3: 3 3 3 3 3 3 3 3 3 3
缺页情况: × × × √ √ × √ √ √ × √ √
未来访问分析：
位置6: 1(位置8),2(不再出现),3(位置7) → 替换2
位置10: 1(位置12),4(位置11),3(不再出现) → 替换3访问1：装入1 → 缺页
访问2：装入2 → 缺页
访问3：装入3 → 缺页
访问2：2命中 → 命中
访问1：1命中 → 命中
访问4：查看未来访问：1在位置8出现，2不再出现，3在位置7出现，替换2 → 缺页
访问3：3命中 → 命中
访问1：1命中 → 命中
访问4：4命中 → 命中
访问5：查看未来访问：1在位置12出现，4在位置11出现，3不再出现，替换3 → 缺页
访问4：4命中 → 命中
访问1：1命中 → 命中
OPT结果：
缺页次数：4次
缺页率：4/12 ≈ 33.33%
总结对比
评论