操作系统课程设计页面置换算法
操作系统 课程设计说明书
题目: 页面置换算法程序设计
院 系： 计算机科学与工程
专业班级： 学 号： 学生姓名： 指导教师：
2014年 11月 21 日
2014年11月21日
安徽理工大学课程设计（论文）成绩评定表
目 录
1 问题描述 ................................................................................................. 1 2 需求分析 ................................................................................................. 1 3 概要设计 ................................................................................................. 1 3.1 设计思路 ...................................................................................... 1 3.2 功能模块设计 .............................................................................. 2 3.3 算法流程图 .................................................................................. 2 4 详细设计 ................................................................................................. 4 4.1 相关知识 ...................................................................................... 4 4.2 置换算法函数代码设计 .............................................................. 4 4.3 辅助函数代码设计 .................................................................... 10 5 调试分析 ............................................................................................... 12 6 测试结果 ............................................................................................... 13 7 设计体会 ............................................................................................... 15 参考文献 ................................................................................................... 15
1 问题描述
编写程序实现：
（1）先进先出页面置换算法（FIFO） （2）最近最久未使用页面置换算法（LRU） （3）最佳置换页面置换算法（OPT）
设计一个虚拟存储区和内存工作区，编程序演示以上三种算法的具体实现过程，并计算访问命中率。演示页面置换的三种算法。通过随机数产生一个指令序列，将指令序列转换成为页地址流。计算并输出各种算法在不同内存容量下的命中率。
2 需求分析
在地址映射过程中，若在页面中发现所要访问的页面不再内存中，则产生缺页中断。当发生缺页中断时操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。
在进程运行过程中，若其所要访问的页面不在内存需把它们调入内存，但内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据，送磁盘的对换区中。但应将哪个页面调出，所以需要根据一定的算法来确定。
常用的算法有先进先出置换算法（FIFO）、最近最久未使用置换算法（LRU）和最佳置换算法（OPT），该设计是在VC++6.0环境下用上述三种算法来实现页面置换算法的模拟程序，然后计算访问命中率，并测试结果。
3 概要设计
3.1 设计思路
选择置换算法，先输入所有页面号，为系统分配物理块，依次进行置换： FIFO基本思想：是用队列存储内存中的页面，队列的特点是先进先出，与该算法是一致的，所以每当发生缺页时，就从队头删除一页，而从队尾加入缺页。
或者借助辅助数组time[mSIZE]记录物理块中对应页面的进入时间，每次需要置换时换出进入时间最小的页面。
LRU基本思想：是用一维数组page[pSIZE]存储页面号序列，memery[mSIZE]是存储装入物理块中的页面。数组flag[10]标记页面的访问时间。每当使用页面时，刷新访问时间。发生缺页时，就从物理块中页面标记最小的一页，调出该页，换入所缺的页面。
OPT基本思想：是用一维数组page[pSIZE]存储页面号序列，memery[mSIZE]是存储装入物理块中的页面。数组next[mSIZE]记录物理块中对应页面的最后访问时间。每当发生缺页时，就从物理块中找出最后访问时间最大的页面，调出该页，换入所缺的页面。 3.2 功能模块设计
（1）置换算法函数：
void FIFO( )：先进先出页面置换算法 void LRU( )：最近最久未使用置换算法 void OPT( )：最佳置换算法 （2）辅助函数：
void output(int t)：计算输出 void showInfo( )：显示信息 void download( )：载入数据 void mDelay(int Delay)：设置延迟 void compute( )：计算过程延迟 3.3 算法流程图 算法流程图如图1所示。
图1 算法流程图
4 详细设计
4.1 相关知识
（1）虚拟存储器的引入：
局部性原理：程序在执行时在一较短时间内仅限于某个部分；相应的，它所访问的存储空间也局限于某个区域，它主要表现在以下两个方面：时间局限性和空间局限性。
（2）虚拟存储器的定义：
虚拟存储器是只具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。
（3）虚拟存储器的实现方式：
分页请求系统，它是在分页系统的基础上，增加了请求调页功能、页面置换功能所形成的页面形式虚拟存储系统。
请求分段系统，它是在分段系统的基础上，增加了请求调段及分段置换功能后，所形成的段式虚拟存储系统。
（4）页面分配：
平均分配算法，是将系统中所有可供分配的物理块，平均分配给各个进程。按比例分配算法，根据进程的大小按比例分配物理块。
考虑优先的分配算法，把内存中可供分配的所有物理块分成两部分：一部分按比例地分配给各进程；另一部分则根据个进程的优先权，适当的增加其相应份额后，分配给各进程。
（5）页面置换算法：
常用的页面置换算法有FIFO、LRU、OPT等。 4.2 置换算法函数代码设计
（1）先进先出页面置换算法设计
算法思想：借助辅助数组time[mSIZE]记录物理块中对应页面的进入时间，每次需要置换时换出进入时间最小的页面。
其功能实现代码如下： void FIFO( ) {
int time[10]={0};/*记录进入物理块的时间*/ int i,j,k,m;
int max=0;/*记录换出页*/ int count=0;/*记录置换次数*/
/*前mSIZE个数直接放入*/
for(i=0;i
for(i=mSIZE;i
for(j=0,k=0;j
if(k==mSIZE)/*如果不在物理块中*/ {
count++;/*计算换出页*/ max=time[0]
if(time[m]
max=m;
if(memery[j]!=page[i])
k++;
memery[i]=page[i]; time[i]=i;
for(j=0;j
temp[i][j]=memery[j];
memery[max]=page[i];
time[max]=i;/*记录该页进入物理块的时间*/
}
}
}
temp[i][j]=memery[j];
else { }
for(j=0;j
temp[i][j]=memery[j];
compute(); output(count);
（2）最近最久未使用置换算法设计
算法思想：用一维数组page[pSIZE]存储页面号序列，memery[mSIZE]是存储装入物理块中的页面。数组flag[10]标记页面的访问时间。每当使用页面时，刷新访问时间。发生缺页时，就从物理块中页面标记最小的一页，调出该页，换入所缺的页面。
其功能实现代码如下： void LRU( ){
int memery[10]={0};
int flag[10]={0};/*记录页面的访问时间*/ int i,j,k,m;
int max=0;/*记录换出页*/ int count=0;/*记录置换次数* /*前mSIZE个数直接放入*/ for(i=0;i
memery[i]=page[i];
}
for(j=0;j
for(i=mSIZE;i
for(j=0,k=0;j
if(k==mSIZE)/*如果不在物理块中*/ { } else { }
if(memery[j]!=page[i])
k++;
else
flag[j]=i;/*刷新该页的访问时间*/
count++;/*计算换出页*/ max=flag[0]
if(flag[m]
max=m;
memery[max]=page[i];
flag[max]=i;/*记录该页的访问时间*/ for(j=0;j
temp[i][j]=memery[j];
for(j=0;j
temp[i][j]=memery[j];
}
compute(); output(count);
（3）最佳置换算法设计
算法思想：用一维数组page[pSIZE]存储页面号序列，memery[mSIZE]是存储装入物理块中的页面。数组next[mSIZE]记录物理块中对应页面的最后访问时间。每当发生缺页时，就从物理块中找出最后访问时间最大的页面，调出该页，换入所缺的页面。
其功能实现代码如下： void OPT( ){
int memery[10]={0};
int next[10]={0};/*记录下一次访问时间*/
int i,j,k,l,m;
int max;/*记录换出页*/ int count=0;/*记录置换次数*/ /*前mSIZE个数直接放入*/
for(i=0;i
for(i=mSIZE;i
for(j=0,k=0;j
memery[i]=page[i]; for(j=0;j
temp[i][j]=memery[j];
if(memery[j]!=page[i])
k++;
}
if(k==mSIZE)/*如果不在物理块中*/ {
count++;/*得到物理快中各页下一次访问时间*/ for(m=0;m
for(l=i+1;l
if(memery[m]==page[l])
break;
next[m]=l;
/*计算换出页*/ } compute(); output(count);
} else{ }
for(j=0;j
temp[i][j]=memery[j]; max=next[0]>=next[1]?0:1; for(m=2;m
if(next[m]>next[max])
max=m;/*下一次访问时间都为pSIZE,则置换物理块中第一个*/
memery[max]=page[i]; for(j=0;j
temp[i][j]=memery[j];
4.3 辅助函数代码设计
（1）计算输出void output(int t)函数设计 其功能实现代码如下： void output(int t){
int i,j,k,l; int flag;
for(k=0;k
for(i=20*k;(i
for(j=0;j
for(i=20*k;(i
for(i=mSIZE+20*k;(i
for(flag=0,l=0;l
if(temp[i][l]==temp[i-1][l])
flag++;}
if(i>=j)
printf("|%d|",temp[i][j]);
if(((i+1)%20==0)||(((i+1)%20)&&(i==pSIZE-1)))
printf(" %d\n",page[i]);
else
printf(" %d ",page[i]);
else
printf("| |");
if(flag==mSIZE)/*页面在物理块中*/
}
}
}
}
printf(" ");
else
printf("|%d|",temp[i][j]);
if(i%100==0)
continue;
printf("\n");
printf("----------------------------------------\n"); printf("缺页次数：%d\t\t",t+mSIZE); printf("缺页率：%d/%d\n",t+mSIZE,pSIZE); printf("置换次数：%d\t\t",t);
printf("访问命中率：%d%%\n",(pSIZE-(t+mSIZE))*100/pSIZE); printf("----------------------------------------\n");
（2）计算过程延迟void compute( )函数设计 其功能实现代码如下： void compute() {
int i;
printf("正在进行相关计算，请稍候"); for(i=1;i
mDelay(15); if(i%4==0)
printf("\b\b\b\b\b\b \b\b\b\b\b\b");
}
}
else printf("Θ");
for(i=0;i++
5 调试分析
（1）系统主界面如图2所示。
图2 系统主界面
（2）初始化数据如图3所示。
图3 初始化数据
（3）选择界面如图4所示。
图4 选择界面
6 测试结果
（1）测试先进先出（FIFO），结果正确，如图5所示。
图5 先进先出（FIFO）测试
（2）测试最近最久未使用（LRU），结果正确，如图6所示。
图6 最近最久未使用（LRU）测试
（3）测试最佳（OPT），结果正确，如图7所示。
图7 最佳（OPT）测试
7 设计体会
通过两周时间的课程设计，我对计算机操作系统主存管理以及C语言的使用都有了更深的了解。当然也遇到不少问题，也正是国为这些问题引发的思考给我带来了收获。从当初不喜欢上机写程序到现在能主动写程序，从当初拿着程序不知从何下手到现在知道如何分析问题，如何用专业知识解决实际问题的转变。我发现无论是专业知识还是动手能力，自己都有很大程度的提高。在实际上机操作过程中，不仅是让我了解三种页面置换算法的理论知识和基本思想，更重要的是培养解决实际问题的能力，为后续课程的学习及实践打下良好的基础。
这次课程设计让我更加了解大一学到的C语言和这个学期学到的计算机操作系统相关知识的紧密联系，更加理解了页式存储管理中淘汰机制和几种置换算法，培养了我的动手能力，更令我的创造性思维得到拓展。不仅要求设计者对课本知识有较深刻的了解，同时要有较强的思维动手能力。
这次的课程设计让我有一个深刻的体会：严谨！编程最需要的就是严谨，往往检查到的错误是在某个括号、分号、引号等不应该犯错的地方上。程序设计时难免遇到错误，但这不是坏事情，它可以让我发现自己的薄弱环节，在具体操作中还可以巩固所学的操作系统主存管理中的页面置换，而且也体会到了C语言的语句简洁、使用灵活、执行效率高等特点。
通过此次课程设计，我懂得了实践的重要性，要理论联系实际，才能把自己所掌握的知识更好地运用。并且切实地感受到同学之间的相互帮助，遇到自己实在弄不懂的地方，和同学讨论一下，两个人共同提高。
参考文献
[1] 龚沛曾等编.C/C++程序设计教程.北京：高等教育出版社,2004. [2] 谭浩强编著.C程序设计（第二版）.北京：清华大学出版社,1999. [3] 张尧学等编著.计算机操作系统教程.北京：清华大学出版社，2011. [4] 孟庆昌等编. 操作系统. 北京：电子工业出版社，2009. [5] 刘腾红等编著. 操作系统. 北京：中国铁道出版社,2008.
[6] 汤子瀛等编著. 计算机操作系统.西安：西安电子科技大学出版社,2011