请求页式管理缺页中断模拟设计--LRU、OPT
学 号:
请求页式管理缺页中断模拟设计--LRU、OPT 题 目
计算机科学与技术学院 学 院
专 业
班 级
姓 名
指导教师
武汉理工大学《操作系统》课程设计
课程设计任务书
学生姓名:
指导教师: 工作单位: 计算机科学与技术学院 题 目: 请求页式管理缺页中断模拟设计-- LRU、OPT 初始条件:
1(预备内容:阅读操作系统的内存管理章节内容,了解有关虚拟存储器、页式存储管理等概
念,并体会和了解缺页和页面置换的具体实施方法。
2(实践准备:掌握一种计算机高级语言的使用。
要求完成的主要任务: (包括课程设计工作量及其技术要求,以及
说明书
房屋状态说明书下载罗氏说明书下载焊机说明书下载罗氏说明书下载GGD说明书下载
撰写等具体要求)
1(实现指定淘汰算法。能够处理以下的情形:
? 能够输入给作业分配的内存块数;
? 能够输入给定的页面,并计算发生缺页的次数以及缺页率;
? 缺页时,如果发生页面置换,输出淘汰的页号。
2(设计
报告
软件系统测试报告下载sgs报告如何下载关于路面塌陷情况报告535n,sgs报告怎么下载竣工报告下载
内容应说明:
? 需求分析;
? 功能设计(数据结构及模块说明);
? 开发平台及源程序的主要部分;
? 测试用例,运行结果与运行情况分析;
? 自我评价与总结:
i)你认为你完成的设计哪些地方做得比较好或比较出色;
ii)什么地方做得不太好,以后如何改正;
iii)从本设计得到的收获(在编写,调试,执行过程中的经验和教训);
iv)完成本题是否有其他方法(如果有,简要说明该方法);
时间安排:
设计安排一周:周1、周2:完成程序分析及设计。
周2、周3:完成程序调试及测试。
周4、周5:验收、撰写课程设计报告。
(注意事项:严禁抄袭,一旦发现,一律按0分记)
指导教师签名: 年 月 日 系主任(或责任教师)签名: 年 月 日
武汉理工大学《操作系统》课程设计
请求页式管理缺页中断模拟设计
----LRU、OPT 1 设计目的与功能
1.1 设计目的
巩固并加深对虚拟存储器、请求页式存储管理等概念的理解,掌握请求页式管理中的置换算法的基本思想。并针对LRU(最近最久未使用页面置换算法),以及OPT(理想型淘汰算法)两种算法,利用高级语言,设计出相应的模拟程序。
结合设计的程序,在理论联系实际的基础上,分析各个页面置换算法的优缺点。以及在对课程的整体把握上,提升对操作系统这门课程的全面认识。
1.2 设计功能
本次课程设计需要实现LRU和OPT两种置换算法。能够实现以下功能:
) 能够输入给作业分配的内存块数; 1
2) 能够输入给定的页面,并计算发生缺页的次数以及缺页率;
3) 缺页时,如果发生页面置换,输出淘汰的页号。
2 设计需求分析
2.1 需求分析
2.1.1 请求页式管理的实现
请求页式管理是在静态页式管理的基础上发展起来的,它允许只装入部分页面的程序和数据,便启动运行。此后,再通过调页功能和页面置换功能,陆续把即将要运行的页面调入内存,同时把暂时不运行的页面换出到外存上,置换时以页面为单位。
为了能实现请求调页和置换功能,系统必须提供必要的硬件支持和相应的软件。其中硬件支持包括:
1) 请求分页的页表机制,它是在纯分页的页表机制上增加若干项而形成的,作为
请求分页的数据结构;
2) 缺页中断机构,当要访问的页面尚未调入内存时,便产生一缺页中断,以请求
OS将所缺的页调入内存;
3) 地址变换机构,它同样是在纯分页地址变换机构的基础上形成的。 2.1.2 置换算法分析
武汉理工大学《操作系统》课程设计
请求页式管理中的置换算法在内存中没有空闲页时被调用,它的目的是选出一个被淘汰的页面。如果内存中有足够的空闲页面存放调入的页,则不必使用置换算法。本次设计使用最近最久未使用页面置换算法(least recently used,LRU)和理想型淘汰算法(optional replacement algorithm,OPT)。
LRU置换算法:
最近最久未使用页面置换算法(least recently used,LRU),该算法的基本思想是:当需要淘汰某一页时,选择离当前时间最近的一段时间内最久没有使用过的页先淘汰。该算法的主要出发点是,如果某页被访问了,则它可能马上还要被访问,或者如果某页很长时间未被访问,则它在最近一段时间也不会被访问。
OPT置换算法:
理想型淘汰算法(optional replacement algorithm,OPT),该算法淘汰在访问串中将来再也不出现的或者是在离当前最远的位置上出现的页,这样淘汰掉该页将不会造成因需要访
实现,因为它要求必须预先知道每一个进程问该页又立即把它调入的现象。这种算法难以
的访问串。
2.2 数据结构及功能框图
- - - - - - - - - - 基本数据变量说明- - - - - - - - - - - - -
int input; //输入的页面数
int num; //内存块允许装入页面数
int *in; //准备调入的页面序列
int *memory; //用来记录进入内存的页面信息
struct page
{
int Pnumber; //页面的页号
int Mnumber; //在内存中对应的块号
int stayin; //是否在内存中
};
page Ptotal[N]; //对N个页面进行操作
- - - - - - - - - - - 基本操作的函数原型说明- - - - - - - - - - - - -
void LRU(); //实现LRU算法的函数
武汉理工大学《操作系统》课程设计
void OPT(); //实现OPT算法的函数
开始
Y
请求页面序列 结束 是否结束 N
选择要调入页面
Y
页面是否在内
存中
N
N
放入未被占用的内内存块是否已满 存块中,修改页表
Y
利用算法,选择应该 替换的页面并修改
请求页式管理实现过程
3 源程序的主要部分
3.1 源程序简介
本次设计中LRU以及OPT算法中页面置换的思想,分别对照页框的内容,向前查找最久未被使用的页面号和向后查找最后被使用的页面号,将其替换之。在设计的思想上可以转化为以当前即将调入的页面为中心,LRU为向前查找离中心最远的页号,而OPT为向后查找离中心最远的页号。
3.2 源程序核心代码
3.2.1 main函数代码
main函数实现对各输入数据及待数据结构的初始化,以及通过选择来调用LRU或OPT
武汉理工大学《操作系统》课程设计
算法。伪代码如下:
int main()
{ …… //页号、块号、页面顺序的输入,以及初始化等工作。
while(true)
{ …… //部分全局变量的初始化工作,每次循环需重新开始
char chose;
cout<<"请您选择:1、LRU算法"<
>chose;
if(chose!='1'&&chose!='2')break;
switch(chose)
{
case '1':LRU();break;
case '2':OPT();break;
}
cout<<"*********************************************"<=0,<); //get宏,传递的参数为-,>=0,<等
return getNum; //返回页框号
}
int getOPT(int page)
{ get(+,); //get宏,传递的参数为+,等
return getNum; //返回页框号
}
3.2.5 get(smblx,smbly,smblz)宏的代码
getLRU和getOPT的搜索算法在思想上相似,即前者向前搜索页第一次出现的申请序号,而后者是向后搜索接下来第一次出现的申请序号,所以用get宏来对相同代码进行公操作,伪代码如下:
#define get(smblx,smbly,smblz)\
for(i=0;i in[i]=temp;
#include }
using namespace std; cout<<"***************************
int input,num,*in,*memory; ******************"<>input; cout<<"******************************
cout<<"请输入物理块数目"<>num; cin>>chose;
in= new int[input]; if(chose!='1'&&chose!='2')break;
memory=new int[num]; switch(chose)
cout<<"请依次输入"<>temp; cout<<"******************************
武汉理工大学《操作系统》课程设计
***************"<=0,<);
for(int j=0;j<10;j++){\ return getNum;
}
if( Ptotal[j].Mnumber==replace){\
武汉理工大学《操作系统》课程设计
int getOPT(int page) LO(LRU); { }
get(+,); void OPT()
return getNum; {
} cout<<"OPT替换算法过程如
:"<
方案
气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载
正确性、可行性、创造性
4 40 设计结果正确性
5 10 设计报告的
规范
编程规范下载gsp规范下载钢格栅规范下载警徽规范下载建设厅规范下载
性
6 10 设计验收
总得分/等级 评语:
注:最终成绩以五级分制记。优(90-100分)、良(80-89分)、中(70-79分)、 及格(60-69分)、60分以下为不及格
指导教师签名:
20 年 月 日