题目类型

  • 先进先出 · FIFO
  • 最佳置换算法 · OPT
  • 最近最少使用 · LRU

例题

例题1：

在一个请求分页系统中，加入一个作业的页面走向为：1，2，3，4，5，1，4，1，2，3，4，5.当分配给该作业的物理块数为4是，分别采用FIFO、LRU、OPT算法，计算访问过程中发生的缺页次数和缺页率。

页面走向 1 2 3 4 5 1 4 1 2 3 4 5
物理页0
物理页1
物理页2
物理页3
缺页

解析：

  • FIFO：先进先出……比谁长
页面走向 1 2 3 4 5 1 4 1 2 3 4 5
物理页0 1 1 1 1 5 5 5 5 5 5 4 4
物理页1 2 2 2 2 1 1 1 1 1 1 5
物理页2 3 3 3 3 3 3 2 2 2 2
物理页3 4 4 4 4 4 4 3 3 3
缺页 √ √ √ √ √ √ √ √ √ √
  • LRU：最久未使用
页面走向 1 2 3 4 5 1 4 1 2 3 4 5
物理页0 1 1 1 1 5 5 5 5 5 3 3 3
物理页1 2 2 2 2 1 1 1 1 1 1 5
物理页2 3 3 3 3 3 3 2 2 2 2
物理页3 4 4 4 4 4 4 4 4 4 4
缺页 √ √ √ √ √ √ √ √ √
  • OPT：被淘汰的页面将是未来最长时间内不再被访问的页面
页面走向 1 2 3 4 5 1 4 1 2 3 4 5
物理页0 1 1 1 1 1 1 1 1 1
物理页1 2 2 2 2 2 2 2 2
物理页2 3 3 5 5 5 5 5 5 5
物理页3 4 4 4 4 4 4 4 4
缺页 √ √ √ √ √ √

例题2：

  在一个请求式存储管理系统中，采用FIFO页面置换算法，假设一进程分配了4个页框，按下面页面进行：1、8、1、7、8、2、7、6、5、8、3、6请给出缺页的次数和缺页率。

解析：

页面走向 1 8 1 7 8 2 7 6 5 8 3 6
物理页0 1 1 1 1 1 1 1 6 6 6 6 6
物理页1 8 8 8 8 8 8 8 5 5 5 5
物理页2 7 7 7 7 7 7 8 8 8
物理页3 2 2 2 2 2 3 3
缺页 √ √ √ √ √ √ √ √

  缺页次数=8

  缺页率=8/12*100%

例题3：

  在一个请求分页系统中，采用LRU页面置换算法，例如一个作页的页面走向为4，3，2，1，4，3，5，4，3，2，1，5，当分配给该作业的物理块数M分别为3和4时，试计算访问过程中所发生的缺页次数和缺页率？（注意，所有内存块最初都是空的，所以，凡第一次用到的页面都产生一次缺页），并比较所得结果。

解析：

  1. 当M=3时，
页面走向 4 3 2 1 4 3 5 4 3 2 1 5
缺页标记 * * * * * * * * * *
M1 4 4 4 1 1 1 5 5 5 2 2 2
M2 3 3 3 4 4 4 4 4 4 1 1
M3 2 2 2 3 3 3 3 3 3 5

  • 缺页次数=10

  • 缺页率=缺页次数/总页数100%=10/12100%=83.3%


  1. 当M=4时
页面走向 4 3 2 1 4 3 5 4 3 2 1 5
缺页标记 * * * * * * * *
M1 4 4 4 4 4 4 4 4 4 4 4 5
M2 3 3 3 3 3 3 3 3 3 3 3
M3 2 2 2 2 5 5 5 5 1 1
M4 1 1 1 1 1 1 2 2 2
  • 缺页次数=8
  • 缺页率=8/12*100%=67%

例题4：

  假定某页式虚拟系统中，页面大小为100个单元，某作业占有实页面数为M=3，它的访问地址（走向）序列为75，175，66，267，32，102，333，166，22，255，256（数字为虚存的逻辑地址）。

（1）请指出这些单元对应的页面访问顺序序列；

（2）按先来先服务（FIFO）页面淘汰算法求出缺页率f，并画出图表表示之；

（3）按最近最久未使用（LRU）页面置换算法求出缺页率f，并画出图表表示之。

解析：

（1）访问序列为0，1，0，2，0，1，3，1，0，2，2。

（2）FIFO：

alt

  • 缺页率f=5/11=45.45%。

（3）LRU：堆栈方式

alt

  • 缺页率f=5/11=45.45%。