页面置换算法实验报告
更新时间:2023-05-13 18:34:01 阅读量: 实用文档 文档下载
枣 庄 学 院 信息科学与工程学院 课程设计任务书
题目:
学 号: 0315 0307 姓 名: 王宇 刘志伟
专 业: 网络技术 课 程: 操作系统 指导教师: 燕孝飞 职称: 讲师
完成时间: 2013年 12 月----2014 年 1 月
枣庄学院信息科学与工程学院制
年 月 日
课程设计任务书及成绩评定
成绩:
指导教师签字:
日期:
硬件:win-7 系统笔记本 软件:win-tc
课程设计进度计划起至日期 工作内容 备注
2
13 年 12 月上旬 13 年 12 月中旬 13 年 12 月下旬
收集素材 制定计划方案 设计制作
参考文献、资料索引 序号 文献、资料名称 编著者 出版单位
《计算机操作系统》(第 3 版) 汤子瀛 西安电子科技大学 《计算机操作系统》 林果园 清华大学出版社 《计算机操作系统》 汤小丹 西安电子科技大学出版社
3
一、实验目的
1.通过模拟实现几种基本页面置换的算法,了解虚拟存储技术的特点。
2.掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想,并至少用三种算法来模拟实现。
3.通过对几种置换算法页面的比较,来对比他们的优缺点,并通过比较更换频率来对比它们的效率。
二、实验内容:
设计一个虚拟存储区和内存工作区,并使用下述算法来模拟实现页面的置换: 1. 先进先出的算法(FIFO) 2. 最近最久未使用算法(LRU) 3. 最佳置换算法(OPT)
三、实验分析
在进程运行过程中,若其所访问的页面不存在内存而需要把它们调入内存,但内存已无空闲时,为了保证该进程能够正常运行,系统必须从内存中调出一页程序或数据送磁盘的对换区中。但应调出哪个页面,需根据一定的算法来确定,算法的好坏,直接影响到系统的性能。
一个好的页面置换算法,应该有较低的页面更换频率。
假设分给一作业的物理块数为3 ,页面数为20个。 页面号为(20个):
7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1
1.先进先出(FIFO)置换算法的思路
该算法总是淘汰最先进入内存的页面,即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单,只需把一个进程已调入内存的页面,按照先后次序连接成一个队列,并设置一个替换指针,使它总指向最老的页面。
2.最近久未使用(LRU)置换算法的思路
最近久未使用置换算法的替换规则,是根据页面调入内存后的使用情况来进行决策的。该算法赋予每个页面一个访问字段,用来记录一个页面自上次被访问以来所经历的时间,当需淘汰一个页面的时候选择现有页面中其时间值最大的进 行淘汰。
3.最佳(OPT)置换算法的思路
其所选择的被淘汰的页面,奖是以后不使用的,或者是在未来时间内不再被访问的页面,采用最佳算法,通常可保证获得最低的缺页率。
4.数据结构
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 BlockClear(void);//BLOCK清空,以便用另一种方法重新演示 pageInfor * block; //物理块 pageInfor * page; //页面号串 private: };
5.FIFO页面置换算法
当需要访问一个新的页面时,首先调用findExist(i)函数来查看物理块中是否就有这个页面,若要查看的页面物理块中就有,则调用display函数直接显示,不需要替换页面;如果要查看的页面物理块中没有,就需要寻找空闲物理块放入,若存在有空闲物理块,则将页面放入;若没有空闲物理块,则调用findReplace函数替换页面。并将物理块中所有页面timer++。
6.LRU页面置换算法
当需要访问一个新的页面,首先调用findExist(i)函数查看物理块中是否就有这个页面。
7. OPT页面置换算法
当需要访问一个新的页面,首先调用findExist(i)函数来查看物理块中是否有这个页面。
8.寻找置换页面函数findReplace比较三个物理块中的时间标记timer,找到时间最久的。
四、源程序结构分析
1. 程序结构
程序共有以下九个部分:
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() //主程序
2. 源程序代码
#include <iostream.h>
#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<Bsize; i++) {
block[i].content = -1; block[i].timer = 0; }
page = new pageInfor[Psize]; for(i=0; i<Psize; i++) {
page[i].content = QString[i]; page[i].timer = 0; } }
int PRA::findSpace(void) {
for(int i=0; i<Bsize; i++) if(block[i].content == -1)
return i;//找到空闲内存,返回BLOCK中位置 return -1; }
int PRA::findExist(int curpage) {
for(int i=0; i<Bsize; 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<Bsize; i++)
if(block[i].timer >= block[pos].timer)
pos = i;//找到应予置换页面,返回BLOCK中位置 return pos; }
void PRA::display(void) {
for(int i=0; i<Bsize; i++) if(block[i].content != -1)
cout<<block[i].content<<" "; cout<<endl; }
void PRA::Optimal(void) {
int exist,space,position ;
for(int i=0; i<Psize; i++) {
exist = findExist(i); if(exist != -1)
{ cout<<"不缺页"<<endl; } else {
space = findSpace(); if(space != -1) {
block[space] = page[i]; display(); } else {
for(int k=0; k<Bsize; k++) for(int j=i; j<Psize; j++) {
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<Psize; i++) {
exist = findExist(i); if(exist != -1) {
cout<<"不缺页"<<endl;
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<Bsize; j++) block[j].timer++; } }
void PRA::FIFO(void) {
int exist,space,position ;
for(int i=0; i<Psize; i++) {
exist = findExist(i); if(exist != -1)
{cout<<"不缺页"<<endl;}
else {
space = findSpace(); if(space != -1) {
block[space] = page[i]; display(); } else {
position = findReplace(); block[position] = page[i]; display(); } }
for(int j=0; j<Bsize; j++)
block[j].timer++;//BLOCK中所有页面TIMER++ } }
void PRA::BlockClear(void) {
for(int i=0; i<Bsize; i++) {
block[i].content = -1; block[i].timer = 0; } }
void main(void) {
cout<<"|----------页 面 置 换 算 法----------|"<<endl;
cout<<"|---power by wangxinchuang(080501228)---|"<<endl; cout<<"|-------------------------------------|"<<endl;
cout<<"页面号引用串:7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1"<<endl; cout<<"----------------------------------------------------"<<endl; cout<<"选择<1>应用Optimal算法"<<endl; cout<<"选择<2>应用FIFO算法"<<endl; cout<<"选择<3>应用LRU算法"<<endl; cout<<"选择<0>退出"<<endl; int select; PRA test;
while(select) {
cin>>select; switch(select) {
case 0: break; case 1:
cout<<"Optimal算法结果如下:"<<endl; test.Optimal(); test.BlockClear();
cout<<"----------------------"<<endl; break; case 2:
cout<<"FIFO算法结果如下:"<<endl; test.FIFO();
test.BlockClear();
cout<<"----------------------"<<endl; break; case 3:
cout<<"LRU算法结果如下:"<<endl; test.LRU();
test.BlockClear();
cout<<"----------------------"<<endl; break; default:
cout<<"请输入正确功能号"<<endl; break; } } }
五 、实验结果
1运行后的初始界面
2 opt算法 3.FIFO算法 4LRU算法
正在阅读:
页面置换算法实验报告05-13
大学生闲置物回收再利用公益事业创业项目03-30
2018-2024年中国丙烯酸行业市场调研与投资前景评估报告(目录)08-25
西工大软件技术实验六报告04-07
小学危险品自查报告03-26
高中-物质结构与性质01-04
江南大学2018年上半年信息检索与利用第3阶段参考_ss05-20
- 教学能力大赛决赛获奖-教学实施报告-(完整图文版)
- 互联网+数据中心行业分析报告
- 2017上海杨浦区高三一模数学试题及答案
- 招商部差旅接待管理制度(4-25)
- 学生游玩安全注意事项
- 学生信息管理系统(文档模板供参考)
- 叉车门架有限元分析及系统设计
- 2014帮助残疾人志愿者服务情况记录
- 叶绿体中色素的提取和分离实验
- 中国食物成分表2020年最新权威完整改进版
- 推动国土资源领域生态文明建设
- 给水管道冲洗和消毒记录
- 计算机软件专业自我评价
- 高中数学必修1-5知识点归纳
- 2018-2022年中国第五代移动通信技术(5G)产业深度分析及发展前景研究报告发展趋势(目录)
- 生产车间巡查制度
- 2018版中国光热发电行业深度研究报告目录
- (通用)2019年中考数学总复习 第一章 第四节 数的开方与二次根式课件
- 2017_2018学年高中语文第二单元第4课说数课件粤教版
- 上市新药Lumateperone(卢美哌隆)合成检索总结报告
- 置换
- 算法
- 实验
- 页面
- 报告
- Kindergarten Level 01 Stories
- 员工手册公司管理制度
- Matlab如何添加新的工具箱
- 福建省永春县第一中学2017-2018学年高一上学期期末考试地理试题 Word版含答案
- 广东省湛江第一中学等四校2016届高三上学期第一次联考数学(文)试题(含答案)
- 不同价态金属离子对BSA结构的影响
- 外研版高二英语说课稿1
- 动物生物学 绪论
- 政治与经济常识第二章
- 近岸水产养殖对海洋渔业环境的影响
- 乌海市海南区小学英语四年级下册专项复习:连词成句
- 2015-2020年中国干手器市场全景调查与行业运营态势报告
- 2011年代维考试题V1
- 一种新的复杂网络聚类算法
- 南昌市业主大会议事规则(示范文本)
- 中心小学体育兴趣小组工作总结
- 精选个人述职报告范文集锦7篇
- 个性化服务与电信企业竞争力
- 《数字测图原理与方法-2》上机指导书
- 甘肃联合大学感动校园人物评选策划书