【免费】百度笔试题资源-CSDN文库

需积分: 0 7 浏览量 2012-09-06 09:17:29 上传评论收藏 25KB DOC 举报

资源详情

资源评论

资源推荐

1. 常见的页面调度算法有哪些？请至少列出三种。如何判断一个调度算法的好坏？

解答：

1）常见的页面调度算法

（1）随机算法 rand（Random Algorithm）。

利用软件或硬件的随机数发生器来确定主存储器中被替换的页面。这种算法最简单，而且

容易实现。但是，这种算法完全没用利用主存储器中页面调度情况的历史信息，也没有反

映程序的局部性，所以命中率较低。

（2）先进先出调度算法（FIFO）

先进先出调度算法根据页面进入内存的时间先后选择淘汰页面，本算法实现时需要将页

面按进入内存的时间先后组成一个队列，每次调度队首页面予以淘汰。它的优点是比较

容易实现，能够利用主存储器中页面调度情况的历史信息，但是，它没有反映程序的局

部性，因为最先调入主存的页面，很可能也是经常要使用的页面。

（3）最近最少调度算法 LFU（Least Frequently Used Algorithm ）

先进先出调度算法没有考虑页面的使用情况，大多数情况下性能不佳。根据程序执行的

局部性特点，程序一旦访问了某些代码和数据，则在一段时间内会经常访问他们，因此

最近最少用调度在选择淘汰页面时会考虑页面最近的使用，总是选择在最近一段时间以

来最少使用的页面予以淘汰。算法实现时需要为每个页面设置数据结构记录页面自上次

访问以来所经历的时间。

（4）最近最不常用调度算法 LRU（Least Recently Used Algorithm）

由于程序设计中经常使用循环结构，根据程序执行的局部性特点，可以设想在一段时间

内经常被访问的代码和数据在将来也会经常被访问，显然这样的页面不应该被淘汰。最

近最不常用调度算法总是根据一段时间内页面的访问次数来选择淘汰页面，每次淘汰访

问次数最少的页面。算法实现时需要为每个页面设置计数器，记录访问次数。计数器由

硬件或操作系统自动定时清零。

（5）最优替换算法 OPT（Optimal replacement Algorithm）

前面介绍的几种页面调度算法主要是以主存储器中页面调度情况的历史信息为依据的，

他假设将来主存储器中的页面调度情况与过去一段时间时间内主存储器中的页面调度情

况是相同的。显然，这种假设不总是正确的。最好的算法应该是选择将来最久不被访问

的页面作为被替换的页面，这种算法的命中率一定是最高的，它就是最有替换算法。要

实现 OPT 算法，唯一的方法就是让程序先执行一遍，记录下实际的页地址流情况。根

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余1页未读，立即下载

评论0

内容反馈

微岩

粉丝: 749
资源: 16

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip