页面置换算法实验报告.pdfVIP

页

面

置

换

算

法

实

验

报

告

院系:****************学院

班级:***********

姓名:***

学号:************

一、实验题目：页面置换算法

二．实验目的：

1、用C语言编写OPT、FIFO、LRU三种置换算法。

2、熟悉内存分页管理策略。

3、了解页面置换的算法。

4、掌握一般常用的调度算法。

5、根据方案使算法得以模拟实现。

6、锻炼知识的运用能力和实践能力。

三．实验内容及要求：

设计一个虚拟存储区和内存工作区，编程序演示下述算法的具体实现过程，

并计算访问命中率：

要求设计主界面以灵活选择某算法，且以下算法都要实现

1)最佳置换算法(OPT)：将以后永不使用的或许是在最长(未来)时间内不再

被访问的页面换出。

2)先进先出算法(FIFO)：淘汰最先进入内存的页面，即选择在内存中驻留

时间最久的页面予以淘汰。

3)最近最久未使用算法(LRU)：淘汰最近最久未被使用的页面。

四、实验结果

初始化结果

1，先进先出（FIFO）算法实验结果：

2，最近最久未使用（LRU）算法实验结果：

3，最佳使用法（OPT）实验结果：

五、实验总结

选择置换算法，先输入所有页面号，为系统分配物理块，依次进行置换：

OPT基本思想：

是用一维数组page[]存储页面号序列，memery[]是存储装入物理块中的页

面。数组next[]记录物理块中对应页面的最后访问时间。每当发生缺页时，就从

物理块中找出最后访问时间最大的页面，调出该页，换入所缺的页面。

若物理块中的页面都不再使用，则每次都置换物理块中第一个位置的页面。

FIFO基本思想：

是用队列存储内存中的页面，队列的特点是先进先出，与该算法是一致的，

所以每当发生缺页时，就从队头删除一页，而从队尾加入缺页。或者借助辅助数

组time[]记录物理块中对应页面的进入时间，每次需要置换时换出进入时间最小

的页面。

LRU基本思想：

是用一维数组page[]存储页面号序列，memery[]是存储装入物理块中的页

面。数组flag[10]标记页面的访问时间。每当使用页面时，刷新访问时间。发生

缺页时，就从物理块中页面标记最小的一页，调出该页，换入所缺的页面。

由以上分析可以得出：LRU算法的效率最高。事实上，FIFO算法调度是

依据各个页面的调入时间，而不是页面的使用情况；而OPT算法对今后要使用

的页面进行估算，因此算法无法预知今后页面的情况，故不符合时间，不能在

常规中使用。因此，LRU算法综合来说在三种算法中最高效且实用。

通过本次实验，我掌握了页面置换算法的基本思想，对于这些算法的性能

优劣有了较为直观的理解，收获颇大。

附录（算法代码）：

#includestdio.hvoidmDelay(unsignedintDelay);

#includestdlib.h/*主函数*/

/*全局变量*/voidmain()

intmSIZE;/*物理块数*/{

intpSIZE;/*页面号引用串个数*/inti,k,code;

staticintmemery[10]={0};/*物理块中的页

号*/请输入物理块的个数(M=10)：

staticintpage[100]={0};/*页面号引用串*/

staticinttemp[100][10]={0};/*辅助数组*/

/*置换算法函数*/请输入页面号引用串的个数

voidFIFO();(P=100)：

voidLRU();

voidOPT();