计算机操作系统-页面置换算法.doc

课 程 设 计 报 告

课程名称 计算机系统与系统软件
课题名称 页面置换算法问题

专 业 信息管理与信息系统
班 级 ************
学 号 *************
姓 名 *******
指导教师 *********************

2013年 7 月 7 日
课 程 设 计 任 务 书

课程名称 计算机操作系统
课 题 页面置换算法问题

专业班级 ********
学生姓名 ******
学 号 **************
指导老师 *********************
审 批

任务书下达日期 2013 年 6 月 27 日
任务完成日期 2013 年 7 月 7 日一、设计内容与设计要求
1.课程设计目的
全面熟悉、掌握JAVA程序设计基本知识，增强对不同的问题运用和灵活选择合适的数据结构以及JAVA程序设计的本领，熟悉编制和调试程序的技巧，掌握分析结果的若干有效方法，进一步提高上机动手能力，增强JAVA程序设计概念，熟悉java语言编程，养成提供文档资料的习惯和规范编程的思想，为后继课程的实验以及课程设计打下较扎实的基础。
进一步提高上机动手能力，培养使用计算机解决实际问题的能力，为后继课程的实验以及课程设计，特别是自学、毕业论文的完成打下扎实的基础。
2.课题题目
页面置换算法问题
3.设计要求
⑴设计课题题目：按学号顺序（每15位学生选择一题）选择相应题号的课题。换题者不记成绩。
⑵根据自己对应的课题完成以下主要工作：①完成系统需求分析：包括系统设计目的与意义；系统功能需求（系统流程图）；输入输出的要求。②完成系统总体设计：包括系统功能分析；系统功能模块划分与设计（系统功能模块图）。③完成系统详细设计：包括需求分析；类层次图；界面设计与各功能模块实现。④系统调试：调试出现的主要问题，编译语法错误及修改，重点是运行逻辑问题修改和调整。⑤使用说明书及编程体会：说明如何使用你编写的程序，详细列出每一步的操作步骤。⑥关键源程序（带注释）
⑶按规定格式完成课程设计报告，将其打印稿(A4纸)上交给老师存档。
⑷不得抄袭他人程序、课程设计报告，每个人应体现自己的个性。设计。
二、进度安排
第18周 星期三 上午 8:00-12:00
星期四 上午 8:00-12:00 下午 14:30-18:30
课题4：页面置换算法问题
（一）、课程设计题目：
页面置换算法问题
（二）、目的与要求：
1、目的：
（1）要求学生达到熟练掌握java语言的基本知识和技能；
（2）基本掌握面向对象程序设计的基本思路和方法；
（3）能够利用所学的基本知识和技能，解决简单的面向对象程序设计问题。
2、基本要求：
（1）要求利用面向对象的方法以及java的编程思想来完成系统的设计；
（2）要求在设计的过程中，建立清晰的类层次；
（3）在系统中定义类，每个类中要有各自的属性和方法；
（4）在系统的设计中，至少要用到面向对象的一种机制。
3、创新要求：
在基本要求达到后，可进行创新设计，如根据查找结果进行修改的功能。
4、写出设计说明书
（三）、设计方法和基本原理：
1、问题描述（功能要求）：
页面置换算法问题能实现1）最佳置换算法2）先进先出算法3）最近最久未被使用算法4）clock置换算法
要求：
（1）界面友好，能自由选择算法
（2）能实现初始页面的设置
（3）随机生成访问页面（包括数量和页面号）
2、问题的解决方案：
根据系统功能要求，可以将问题解决分为以下步骤：
（1）分析系统中的各个实体之间的关系及其属性和行为；
（2）根据问题描述，设计系统的类层次；
（3）完成类层次中各个类的描述（包括属性和方法）；
（4）完成类中各个成员函数的定义；
（5）完成系统的应用模块；
（6）功能调试；
（7）完成系统总结报告以及系统使用说明书

目 录

1 系统需求分析
1.1 关于页面置换算法
1.1.1页面置换算法及其分类
在地址映射过程中，若在页面中发现所要访问的页面不再内存中，则产生缺页中断。当发生缺页中断时操作系统必须在内存选择一个页面将其移出内 存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。
　　常见的置换算法有：
　　（1）最佳置换算法（OPT）（理想置换算法）
　　（2）先进现出置换算法（FIFO）：
　　（3）最近最久未使用（LRU）算法
　　（4）Clock置换算法（LRU算法的近似实现）
　　（5）最少使用（LFU）置换算法
　　（6）页面缓冲置换算法
1.1.2关于页面置换算法模拟程序问题的产生
在各种存储器管理方式中，有一个共同的特点，即它们都要求将一个作业全部装入内存方能运行，但是有两种情况：
（1） 有的作业很大，不能全部装入内存，致使作业无法运行；
（2） 有大量作业要求运行，但内存容量不足以容纳所有这些作业。而虚拟内存技术正式从逻辑上扩充内存容量，将会解决以上两个问题。
从内存中调出一页程序或数据送磁盘的对换区中，通常，把选择换出的页面的算法称为页面置换算法（Page-Replacement Algorithms）。进而页面置换算法模拟程序能客观的将其工作原理展现在我们面前。

2 总体设计
2.1总体设计图

主函数

输入物理块和页面数

选择最近最久未使用算法
选择最佳置换算法
选择lock置换算法
选择先进先出置换算法

输出缺页率

图 2.1 总体设计图

2.2 各函数之间的调用关系
主函数调用开始函数getin（）,通过选择再调用最佳置换算法opt()、先进先出置换算法fifo()、最近最久未使用置换算法lru（）、clock置换算法。

主函数
Getin函数
选择
O
P
T
函数
F
I
F
函数
L
R
U
函数
L
O
C
K
函数

图2.2 各函数之间的调用关系

3 详细设计
3.1 主要函数以及其思想流程图
3.1.1 最佳置换算法；void OPT()
设计原理：需要进行页面置换，把内存中以后一段时间都不使用或是使用时间离现在最远的页面换出。

开始

页面走向存入数组yms []中，内存块用wlk[]表示初始化为0

当前yms[]是否装满？

n y

装满，并累积缺页
个数。

当前页面是否在内存中？

n y

不缺页

把wlk[]中以后一段时间都不使用或是使用时间离现在最远的换出

统计缺页

Ym[]数组是否读完？

n

输出缺页率
y

结束

图3.1 OPT 流程图
3.1.2 先进先出置换算法；void FIFO()
设计原理：需要进行页面置换，即把内存中装入最早的那个页面淘汰，换入当前的页面。

开始

页面走向存入数组yms []中，内存块用wlk[]表示初始化为0

当前yms[]是否装满？

n y

装满，并累积缺页
个数。

当前页面是否在内存中？

n y
按页面加载的先后顺序，换出最先进入的，用max记录。

不缺页

统计缺页

Ym[]数组是否读完？
n

输出缺页率

y
结束

图3.2 fifo流程图

3.1.3 最近最久未使用置换算法void LRU()
设计原理：当需要淘汰某一页时，选择离当前时间最近的一段时间内最久没有使用过的页先淘汰该算法的主要出发点是，如果某页被访问了，则它可能马上还要被访问。或者反过来说如果某页很长时间未被访问，则它在最近一段时间也不会被访问。

开始

页面走向存入数组yms []中，内存块用wlk[]表示初始化为0

当前yms[]是否装满？

n y

装满，并累积缺页
个数。

当前页面是否在内存中？

n y
按页面加载的先后顺序，换出最先进入的，用max记录。

不缺页

统计缺页

Ym[]数组是否读完？
n

输出缺页率
y

结束

图3.3 lru流程图

3.1.4 简单的lock置换算法lock()
设计原理：只需为每页设置以为访问位，再将内存中的所有页面都通过链接指针链成一个循环队列。当某页被访问时，其访问位被置1。置换算法在选择一页淘汰时。如果访问位是0，换出此页，若为1，则重新将它置为0，暂不换出。在按照fifo算法检查下一个页面。当检查到队列中的最后一个页面时，若其访问位仍为1，则返回到队首去检查第一个页面。

开始

页面走向存入数组yms []中，内存块用wlk[]表示初始化为0

当前yms[]是否装满？

n y

装满，并累积缺页
个数。

当前页面是否在内存中？

n y
循环队列，将当前页面的访问位置1，并将访问位为1的，置0。Front前进一位

置换访问位为0的页面，
将访问位为1的访问位置0。Front前进一位。

统计缺页

Ym[]数组是否读完？
n

输出缺页率

y
结束

图3.4 lock流程图

4 系统调试及运行结果
4.1 主界面
程序运行，如图4.1所示

图4.1 主界面
说明：首先键入你说要设置的内存个数，页面个数。再输入页面的内容。随后选择算法。
4.2 选择OPT算法
程序运行，如图4.2所示。

图4.2 OPT算法
说明：当选择1，即最佳置换算法时。输出置换过程，和标记缺页。最后计算出缺页率。

4.3 选择FIFO算法
程序运行，如图4.3所示。

图4.3 FIFO算法
说明：当选择2，即先进先出置换算法时。输出置换过程，和标记缺页。最后计算出缺页率。
4.4 选择LRU算法
程序运行，如图4.4所示。

图4.4 LRU算法

说明：当选择3，即最近最久置换算法时。输出置换过程，和标记缺页。最后计算出缺页率。

4.5选择CLOCK算法
运行程序，如图4.5所示：

图4.5 CLOCK算法
说明：当选择4，即简单的lock置换算法时。输出置换过程，和标记缺页。最后计算出缺页率。

5 程序调试
5.1 调试结果

图5.1 调试1
原因：swich语句后面未加“}”。

图5.2 调试2

原因：定义数组未明确个数。
6 心得体会
页面置换算法，是关乎系统性能的一个因素。因此理解好页面置换算法，对理解操作系统有很大的帮助。什么事页面置换算法，在进程运行过程中，若所要访问的页面不在内存而需要把它们调入内存，但内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据送磁盘的对换区中。这就需要用到页面置换算法来选择哪页调出。
在这个计算机系统与系统软件课程设计时，我选择了用c++来编程。以前是习惯用C语言编的。因此这对我充满挑战性，我使用了两个数组，一个是内存块用wk[]表示，一个是页面用ym[]表示。并设为全局变量，以便后面的程序调用。之后，以面向对象的方法，定义了五个子函数，分opt(),fifo(),lru(),lock(),getin()。中间遇到了不少问题，比方说wk[]，ym[]两个数组的初始化。
在这次课设中学习到了很多东西，锻炼了自己的设计思维，在程序终于告结的之后，感谢李老师和所以帮助我的同学，没有他们的帮助就不会这么顺利的完成这次课设。

7 附录
7.1 源代码
#include <iostream>
using namespace std;
int wk[10]={-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};
int ym[20]={0};
class ymzh{
private:
int wlk, yms;
public:
ymzh(int w,int y);
void getin(); //输入函数。
void opt(); //最佳置换算法
void fifo(); //先来先置换算法
void lru(); //最近最久置换算法
void lock(); //简单的lock置换算法
};

ymzh::ymzh(int w,int y)
{
wlk=w;
yms=y;
}

void ymzh::getin()
{
cout<<"请输入页面的内容"<<endl;
for(int i=0;i<yms;i++)
{
cin>>ym[i];
/*if(ym[i]<0)
{
cout<<"您输入有误，请重新输入！"
}*/
}
cout<<"共有"<<i<<"个数字"<<endl;
/*if(i!=yms)
{
cout<<"你输入的数字个数与你设置的个数不一致，请重来！";
exit(0);
}*/
cout<<"输入成功";
}

void ymzh::opt()
{
int i,j,ii,max1,max2,jj=0,log,qy=0;
int wk[10]={-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};
cout<<"您选用的页面置换算法为最佳置换算法，置换过程如下："<<endl;
for(i=0;i<yms;i++)
{
cout<<ym[i]<<"\t\t";
if(i<wlk)
{
wk[jj]=ym[i];
for(j=0;j<wlk&&wk[j]!=-1;j++)
{
cout<<wk[j]<<" ";
}
jj++;
qy++;
cout<<"\t\t\t缺页"<<endl;//判断物理块中有所在页面。
}
else
{
for(j=0,log=0;j<wlk;j++)
{
if(wk[j]==ym[i])
{log=1;break;}
else
log=0;
}
if(log==0)
{
for(j=0,max1=0,max2=i;j<wlk;j++)
{
ii=i;
while(ii<yms&&wk[j]!=ym[ii])
{
ii++;
}
if(ii<=yms&&ii>max2)
{max1=j;max2=ii;}
}
wk[max1]=ym[i];
for(j=0;j<wlk;j++)
cout<<wk[j]<<" ";
qy++;
cout<<"\t\t\t缺页"<<endl;
}
else
cout<<"\t\t\t不缺页"<<endl;
}
}
cout<<"缺页率为"<<(qy/(yms/1.0))<<endl;
}

void ymzh::fifo()
{
int i,j,jj=0,log,front=0,qy=0;
int wk[10]={-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};
cout<<"您选用的页面置换算法为先进先出置换算法，置换过程如下："<<endl;
for(i=0;i<yms;i++)
{
cout<<ym[i]<<"\t\t";
if(i<wlk)
{
wk[jj]=ym[i];
for(j=0;j<wlk&&wk[j]!=-1;j++)
{
cout<<wk[j]<<" ";
}
jj++;
qy++;
cout<<"\t\t\t缺页"<<endl;//判断物理块中有所在页面。
}
else
{
for(j=0,log=0;j<wlk;j++)
{
if(wk[j]==ym[i])
{log=1;break;}
else
log=0;
}
if(log==0)
{
wk[front]=ym[i];
front=(front+1)%wlk;
for(j=0;j<wlk;j++)
cout<<wk[j]<<" ";
qy++;
cout<<"\t\t\t缺页"<<endl;
}
else
cout<<"\t\t\t不缺页"<<endl;
}
}
cout<<"缺页率为"<<(qy/(yms/1.0))<<endl;
}

void ymzh::lru()
{
int i,j,ii,min1,min2,jj=0,log,qy=0;
int wk[10]={-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};
cout<<"您选用的页面置换算法为最近最久未使用置换算法，置换过程如下："<<endl;
for(i=0;i<yms;i++)
{
cout<<ym[i]<<"\t\t";
if(i<wlk)
{
wk[jj]=ym[i];
for(j=0;j<wlk&&wk[j]!=-1;j++)
{
cout<<wk[j]<<" ";
}
jj++;
qy++;
cout<<"\t\t\t缺页"<<endl;//判断物理块中有所在页面。
}
else
{
for(j=0,log=0;j<wlk;j++)
{
if(wk[j]==ym[i])
{log=1;break;}
else
log=0;
}
if(log==0)
{
for(j=0,min1=0,min2=i;j<wlk;j++)
{
ii=i;
while(wk[j]!=ym[ii])
{
ii--;
}
if(ii<min2)
{min1=j;min2=ii;}
}
wk[min1]=ym[i];
for(j=0;j<wlk;j++)
cout<<wk[j]<<" ";
qy++;
cout<<"\t\t\t缺页"<<endl;
}
else
cout<<"\t\t\t不缺页"<<endl;
}
}
cout<<"缺页率为"<<(qy/(yms/1.0))<<endl;
}

void ymzh::lock()
{
int i,j,jj=0,log,front=0,qy=0;
int bj[10]={1,1,1,1,1,1,1,1,1,1};
int wk[10]={-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};
cout<<"您选用的页面置换算法为简单的lock置换算法，置换过程如下："<<endl;
for(i=0;i<yms;i++)
{
cout<<ym[i]<<"\t\t";
if(i<wlk)
{
wk[jj]=ym[i];
for(j=0;j<wlk&&wk[j]!=-1;j++)
{
cout<<wk[j]<<" ";
}
jj++;
qy++;
cout<<"\t\t\t缺页"<<endl;//判断物理块中有所在页面。
}
else
{
for(j=0,log=0;j<wlk;j++)
{
if(wk[j]==ym[i])
{log=1;break;}
else
log=0;
}
if(log==0)
{
while(bj[front]==1)
{
bj[front]=0;
front=(front+1)%wlk;
}
wk[front]=ym[i];
bj[front]=1;
front=(front+1)%wlk;
for(j=0;j<wlk;j++)
cout<<wk[j]<<" ";
qy++;
cout<<"\t\t\t缺页"<<endl;
}
else
{
while(bj[front]==1)
{
bj[front]=0;
front=(front+1)%wlk;
if(wk[front]==ym[i])
{
bj[front]=1;
front=(front+1)%wlk;
break;
}
}
cout<<"\t\t\t不缺页"<<endl;
}
}
}
cout<<"缺页率为"<<(qy/(yms/1.0))<<endl;
}

int main()
{
int wlk,yms,choose;
char zf='y';
cout<<"\t\t\t欢迎来到linx设计的模拟页面置换算法"<<endl;
cout<<"请输入你要的物理块和页面"<<endl;
cin>>wlk;
cin>>yms;
ymzh p(wlk,yms);
p.getin();
while(zf=='y')
{
cout<<"请选择:\n 1.最佳置换算法\n 2.先来先置换\n 3.最近最久未使用算法\n 4.简单的lock置换算法"<<endl;
cin>>choose;
switch(choose){
case 1:p.opt();break;
case 2:p.fifo();break;
case 3:p.lru();break;
case 4:p.lock();break;
default:cout<<"输入有误";break;

cout<<"是否重来？y/n\t";
cin>>zf;
}
return 0;
}
8 参考文献
[1] 汤小丹，梁红兵，等.计算机操作系统.西安电子科技大学出版社，2007.
[2] 郑莉，董洁，何江丹。清华大学出版社，2010.

9 评分表
计算机与通信学院课程设计评分表

课程名称： 计算机系统与系统软件
项 目
评 价
设计方案的合理性与创造性

设计与调试结果

设计说明书的质量

答辩陈述与回答问题情况

课程设计周表现情况

综合成绩

教师签名：
日 期：

22