操作系统页面置换算法题，谁会？

Question

考虑一个仅460个字节的程序的下述内存的访问序列（该序列的下标均从0开始）10、11、104、170、73、309、185、245、246、434、458、364且页面大小为100字节。

（1）写出页面的访问序列。
（2）假设内存中仅有200字节可供程序使用且采用FIFO算法，那么共发生多少次缺页中断？ （3）如果采用最近最久未使用算法（LRU），则又会发生多少次缺页中断？

Answer 1

第二次机会算法：

与FIFO、OPT、LRU、NRU等同为操作系统中请求分页式管理方式的页面置换算法。

第二次机会算法的基本思想是与FIFO相同的，但是有所改进，避免把经常使用的页面置换出去。当选择置换页面时，依然和FIFO一样，选择最早置入内存的页面。但是二次机会法还设置了一个访问状态位。所以还要检查页面的的访问位。如果是0，就淘汰这页；如果访问位是1，就给它第二次机会，并选择下一个FIFO页面。当一个页面得到第二次机会时，它的访问位就清为0，它的到达时间就置为当前时间。如果该页在此期间被访问过，则访问位置为1。这样给了第二次机会的页面将不被淘汰，直至所有其他页面被淘汰过（或者也给了第二次机会）。因此，如果一个页面经常使用，它的访问位总保持为1，它就从来不会被淘汰出去。

第二次机会算法可视为一个环形队列。用一个指针指示哪一页是下面要淘汰的。当需要一个存储块时，指针就前进，直至找到访问位是0的页。随着指针的前进，把访问位就清为0。在最坏的情况下，所有的访问位都是1，指针要通过整个队列一周，每个页都给第二次机会。这时就退化成FIFO算法了。