三种页面置换算法详解(含C语言代码)（提供百度网盘链接，可免费下载）
需积分: 0 102 浏览量
2018-04-16
16:34:30
上传
评论 10
收藏 121KB DOCX 举报
实验四 存储器管理——页面置换算法实践（2 学时）
1. 实验目的
（1）加深对页面置换算法的理解。
（2）掌握几种页面置换算法的实现方法。
（3）通过实验比较各种置换算法的优劣。
2. 实验内容
参考用 C 语言实现的先进先出算法 FIFO 的代码，实现最佳置换算法 OPT 和最近最少使
用算法 LRU。使得随机给出一个页面执行序列，计算不同置换算法的缺页数，缺页率和命
中率。
3. 实验类型
动手实践型
4. 预备知识
A．先进先出(FIFO)页面置换算法
这是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即选择在内存中
驻留时间最久的页面予以淘汰。该算法实现简单，只需把一个进程已调入内存的页面，
按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页
面。但该算法与进程实际运行的规律不相适应，因为在进程中，有些页面经常被访问，
比如，含有全局变量、常用函数、例程等的页面，FIFO 算法并不能保证这些页面不被淘
汰。
这里，我们仍用上面的例子，但采用 FIFO 算法进行页面置换(图 4-27)。当进程第
一次访问页面 2 时，将把第 7 页换出，因为它是最先被调入内存的；在第一次访问页面
3 时，又将把第 0 页换出， 因为它在现有的 2， 0， 1 三个页面中是最老的页。 由图 4-
27 可以看出，利用 FIFO 算法时进行了 12 次页面置换，比最佳置换算法正好多一倍。
B．最佳(Optimal)置换算法
最佳置换算法是由 Belady 于 1966 年提出的一种理论上的算法。 其所选择的被淘汰
页面，将是以后永不使用的，或许是在最长(未来)时间内不再被访问的页面。采用最佳
置换算法，通常可保证获得最低的缺页率。但由于人们目前还无法预知一个进程在内存
的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现
的，但可以利用该算法去评价其它算法。现举例说明如下。
资源评论
