实验3-页面调度算法
实验报告
院 （系）： 专业班级： 学 号: 姓 名: 实验地点: 实验日期:
一、实验目的及要求
通过本实验可以加深理解有关虚拟存储器的工作原理，进一步体会和了解页面替换算法的具体实现方法。 二、实验环境
PC /Windows系统/Visual C++6.0 三、实验内容
① 实现三种算法：先进先出；OPT；LRU
② 页面序列从指定的文本文件（TXT文件）中取出
③ 输出：第一行：每次淘汰的页面号，第二行：显示缺页的总次数 四、实验步骤
1．先进先出(FIFO)置换算法的思路
该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单，只需把一个进程已调入内存的页面，按照先后次序连接成一个队列，并设置一个替换指针，使它总指向最老的页面。
2．最近久未使用(LRU)置换算法的思路
最近久未使用置换算法的替换规则，是根据页面调入内存后的使用情况来进行决策的。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间，当需淘汰一个页面的时候选择现有页面中其时间值最大的进 行淘汰。
3.最佳（OPT）置换算法的思路
其所选择的被淘汰的页面，将是以后不使用的，或者是在未来时间内不再被访问的页面，采用最佳算法，通常可保证获得最低的缺页率。
4、流程图如下图所示：
五、调试过程 程序结构分析：
程序共有以下九个部分：
int findSpace(void);//查找是否有空闲内存
int findExist(int curpage);//查找内存中是否有该页面
int findReplace(void);//查找应予置换的页面 void display(void);//显示 void FIFO(void);//FIFO算法 void LRU(void);//LRU算法 void OPT(void);//OPT算法；
void BlockClear(void);//BLOCK清空，以便用另一种方法重新演示 int main() //主程序
六、实验结果及分析
程序源代码： #include #define Bsize 3 #define Psize 20
struct pageInfor {
int content;//页面号 int timer;//被访问标记 };
class PRA { public:
PRA(void);
int findSpace(void);//查找是否有空闲内存
int findExist(int curpage);//查找内存中是否有该页面 int findReplace(void);//查找应予置换的页面 void display(void);//显示
void FIFO(void);//FIFO算法 void LRU(void);//LRU算法 void Optimal(void);//OPTIMAL算法 void BlockClear(void);//BLOCK恢复 pageInfor * block;//物理块 pageInfor * page;//页面号串 private: };
PRA::PRA(void) {
int QString[20]={7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1};
block = new pageInfor[Bsize]; for(int i=0; i
block[i].content = -1; block[i].timer = 0; }
page = new pageInfor[Psize]; for(i=0; i
page[i].content = QString[i]; page[i].timer = 0; } }
int PRA::findSpace(void) {
for(int i=0; i
return i;//找到空闲内存，返回BLOCK中位置 return -1; }
int PRA::findExist(int curpage) {
for(int i=0; i
if(block[i].content == page[curpage].content) return i;//找到内存中有该页面，返回BLOCK中位置
return -1; }
int PRA::findReplace(void) {
int pos = 0;
for(int i=0; i
if(block[i].timer >= block[pos].timer)
pos = i;//找到应予置换页面，返回BLOCK中位置 return pos; }
void PRA::display(void) {
for(int i=0; i
void PRA::Optimal(void) {
int exist,space,position ;
for(int i=0; i
exist = findExist(i); if(exist != -1)
{ cout
space = findSpace(); if(space != -1) {
block[space] = page[i]; display(); } else {
for(int k=0; k
if(block[k].content != page[j].content)
{ block[k].timer = 1000; }//将来不会用，设置TIMER为一个很大数 else {
block[k].timer = j; break; } }
position = findReplace(); block[position] = page[i]; display(); } } } }
void PRA::LRU(void) {
int exist,space,position ;
for(int i=0; i
exist = findExist(i); if(exist != -1) {
cout
block[exist].timer = -1;//恢复存在的并刚访问过的BLOCK中页面TIMER为-1 } else {
space = findSpace(); if(space != -1) {
block[space] = page[i]; display(); } else {
position = findReplace(); block[position] = page[i]; display(); } }
for(int j=0; j
void PRA::FIFO(void) {
int exist,space,position ;
for(int i=0; i
exist = findExist(i); if(exist != -1)
{cout
space = findSpace(); if(space != -1) {
block[space] = page[i]; display(); } else {
position = findReplace(); block[position] = page[i]; display(); } }
for(int j=0; j
block[j].timer++;//BLOCK中所有页面TIMER++ } }
void PRA::BlockClear(void) {
for(int i=0; i
block[i].content = -1; block[i].timer = 0; } }
void main(void) {
cout
cout应用Optimal算法"应用FIFO算法"应用LRU算法"退出"
while(select) {
cin>>select; switch(select) { case 0: break; case 1:
cout
cout
cout
cout
cout
cout
cout
实验截图如下图所示：
下面原理相同
七、总结
页面置换算法的思想可以说比较简单，易懂，但是在实现的时候，也遇到了很多的问题，比如说在找空闲物理块的时候，起初我是比较物理块是否等于0，若为0，则直接把页面放入，后来发现不论什么时候都是把0替换出去，才恍然大悟，既然页面标号有0，就不能用0来表示空闲物理块，后来就换成用-1来表示物理块空闲了。
通过编写本实验，不仅理解了OS中页面置换算法，也锻炼编程能力，编程过程中会遇到些小问题，可以通过各种途径解决，另外，编程之前要做好整体规划，最好写出来，把各个模块的功能和主要变量都写成文档，这样效率很高。