考研真题：有一个哀求分页式假造存储器体系，分配给某历程3个物理块，开始时内存中预装入第1.2.3个页面

 标题：

有一个哀求分页式假造存储器体系，分配给某历程3个物理块，开始时内存中预装入第1.2.3个页面，该历程的页面访问序列为1，2，4，2，6，2，1，5，6，1
(1)若接纳 OPT(oplimal，最佳)页面置换算法，则访问过程发生的缺页率为多少?
(2)若接纳 LRU(近来最久未利用算法)页面置换算法，则访问过程中的缺页率为多少? 
缺页率 = 缺页次数 / 总访问次数，
总访问次数为 10 次，初始内存预装入页面 1、2、3（不盘算为缺页）
准确解答：

（1）OPT（最佳置换算法）

原理：置换未来最长时间内不再被访问的页面。
访问过程分析：
初始内存页面：{1,2,3}

• 访问 1：掷中（内存有 1），不缺页。
  
• 访问 2：掷中（内存有 2），不缺页。
  
• 访问 4：未掷中（缺页）。内存中 1、2、3 的后续访问：1 在第 7、10 次出现，2 在第 4、6 次出现，3 无后续访问。置换 3，内存变为 {1,2,4}。缺页次数 = 1。
  
• 访问 2：掷中，不缺页。
  
• 访问 6：未掷中（缺页）。内存中 1、2、4 的后续访问：1 在第 7、10 次出现，2 在第 6 次出现，4 无后续访问。置换 4，内存变为 {1,2,6}。缺页次数 = 2。
  
• 访问 2：掷中，不缺页。
  
• 访问 1：掷中，不缺页。
  
• 访问 5：未掷中（缺页）。内存中 1、2、6 的后续访问：1 在第 10 次出现，6 在第 9 次出现，2 无后续访问。置换 2，内存变为 {1,5,6}。缺页次数 = 3。
  
• 访问 6：掷中，不缺页。
  
• 访问 1：掷中，不缺页。
  

缺页率：3/10=30%
（2）LRU（近来最久未利用算法）

原理：置换近来一段时间内最久未被利用的页面。
访问过程分析：
初始内存页面：{1,2,3}

• 访问 1：掷中，近来利用纪录更新为 1、2、3（最久未利用为 3）。
  
• 访问 2：掷中，近来利用纪录更新为 2、1、3（最久未利用为 3）。
  
• 访问 4：未掷中（缺页），置换最久未利用的 3，内存变为 {1,2,4}。缺页次数 = 1。近来利用纪录：4、2、1（最久未利用为 1）。
  
• 访问 2：掷中，近来利用纪录更新为 2、4、1（最久未利用为 1）。
  
• 访问 6：未掷中（缺页），置换最久未利用的 1，内存变为 {2,4,6}。缺页次数 = 2。近来利用纪录：6、2、4（最久未利用为 4）。
  
• 访问 2：掷中，近来利用纪录更新为 2、6、4（最久未利用为 4）。
  
• 访问 1：未掷中（缺页），置换最久未利用的 4，内存变为 {2,6,1}。缺页次数 = 3。近来利用纪录：1、2、6（最久未利用为 6）。
  
• 访问 5：未掷中（缺页），置换最久未利用的 6，内存变为 {2,1,5}。缺页次数 = 4。近来利用纪录：5、1、2（最久未利用为 2）。
  
• 访问 6：未掷中（缺页），置换最久未利用的 2，内存变为 {1,5,6}。缺页次数 = 5。
  
• 访问 1：掷中，不缺页。
  

缺页率：5/10=50%
错误解答： 

错误缘故因由
对标题明白错误，以为预装入第1，2，3个页面是指的是先将访问序列中的前三个先到场进去，故以为初始内存页面1，2，4，但标题中所指的预装入第1，2，3个页面 实际指的是页面编号为 1、2、3 的三个页面，而不是序列中的前三个位置对应的页面
（序列前三个是 1、2、4，但初始装入的是 1、2、3）
标题里的 “第 1、2、3 个页面” 指的是页面的编号（即页面 1、页面 2、页面 3），这是分页体系中对页面的直接编号，和后续的 “访问序列”（即访问哪些编号的页面）是对应的。
比如访问序列中的 “1” 就是访问页面 1，初始内存已经有页面 1，以是第一次访问 1 会掷中
如果初始装入的是序列前三个（1、2、4），那初始内存就不会有页面 3 了，后续分析会完全差别，即导致下面的错误分析