FIFO、LRU、OPT这三种置换算法的缺页次数

时间:2021-01-18 23:33:38


转载自:http://yinzhezq.blog.163.com/blog/static/1648628902010112961039187/


考虑下述页面走向:

          12342156212376321236

     当内存块数量分别为3时,试问FIFOLRUOPT这三种置换算法的缺页次数各是多少?

   答:缺页定义为所有内存块最初都是空的,所以第一次用到的页面都产生一次缺页。

       当内存块数量为3时:


FIFO、LRU、OPT这三种置换算法的缺页次数


发生缺页中断的次数为16

  在FIFO算法中,先进入内存的页面被先换出。当页6要调入时,内存的状态为415,考查页6之前调入的页面,分别为5124,可见4为最先进入内存的,本次应换出,然后把页6调入内存。

FIFO、LRU、OPT这三种置换算法的缺页次数


发生缺页中断的次数为15

  在LRU算法中,最近最少使用的页面被先换出。当页6要调入时,内存的状态为521,考查页6之前调入的页面,分别为512,可见2为最近一段时间内使用最少的,本次应换出,然后把页6调入内存。


FIFO、LRU、OPT这三种置换算法的缺页次数


发生缺页中断的次数为11

    在OPT算法中,在最远的将来才被访问的页面被先换出。当页6要调入时,内存的状态为125,考查页6后面要调入的页面,分别为212,可见5为最近一段时间内使用最少的,本次应换出,然后把页6调入内存。


OPT算法因为要知道后面请求的页框,因此我觉得这个算法有个小小的bug,如果在某个请求中,若在该请求的页框之后的页框序列中至少存在一个和当前内存块中不匹配的页框,则按照内存块的顺序(从上往下)替换没有出现的页框。比如上面那个OPT例子。对于最后一个页框请求,因为6未命中,且6之后没有请求的序列,因此应该替换3,所以替换后的序列为6 , 2 ,1   当然,这只是针对做题而言。