页面置换算法的模拟
课程设计报告
课程名称:操作系统
实验题目:页面置换算法的模拟
日期:2010.07.01
目录
一、课程设计分析 .............................................................................................................................. 1 二、相关知识 ...................................................................................................................................... 1 三、功能设计分析 .............................................................................................................................. 2 四、程序设计 ...................................................................................................................................... 2 五、运行截图 ...................................................................................................................................... 4 六、参考程序 ...................................................................................................................................... 6 七、结果分析 .................................................................................................................................... 14 八、心得体会 .................................................................................................................................... 14
一、课程设计分析
编写程序实现页面置换算法中常用的FIFO、LRU。
FIFO页面置换算法:FIFO淘汰算法是最先使用的页面最先被淘汰。该算 法总是淘汰最先进入内存的页面,即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单只需把一个进程已调入内存的页面,按先后次序链接成一个队列,并设置一个指针,称为替换指针,使它总是指向最老的页面。先进先出(FIFO)页面置换算法,是根据页面调入内存后的使用情况进行决策的。该算法是选择在内存中驻留时间最久的页面予以淘汰。该算法赋于请求调入页面一个空间(工作集),淘汰掉最先调入的页,取而代之的是紧随它进来的页,这样就基本上实现了对最先进入内存的页面的淘汰。
LRU页面置换算法:该算法淘汰的页面是在最近一段时间里较久未被访问的那一页,它是根据程序执行时的局部性原理而设计的。
二、相关知识
1.虚拟存储器的引入
局部性原理:程序在执行时在一较短时间内仅限于某个部分;相应的,它所访问的存储空间也局限于某个区域,它主要表现在以下两个方面:时间局限性和空间局限性。
2.虚拟存储器的定义
虚拟存储器是只具有请求调入功能和置换功能,能从逻辑上对内存容量进行扩充的一种存储器系统。 3.虚拟存储器的实现方式
分页请求系统,它是在分页系统的基础上,增加了请求调页功能、页面置换功能所形成的页面形式虚拟存储系统。
请求分段系统,它是在分段系统的基础上,增加了请求调段及分段置换功能后,所形成的段式虚拟存储系统。 4.页面分配
平均分配算法,是将系统中所有可供分配的物理块,平均分配给各个进程。 按比例分配算法,根据进程的大小按比例分配物理块。
考虑优先的分配算法,把内存中可供分配的所有物理块分成两部分:一部分按比例地分配给各进程;另一部分则根据个进程的优先权,适当的增加其相应份额后,分配给各进程。 5.页面置换算法
先进先出页面置换算法,该算法总是淘汰最先进入内存的页面,即选择在内存中驻
留时间催久的页面予以淘汰。 6.最近最久未使用LRU置换算法
个页面时,选择现有页面中T最大的,即最近最久未使用的页面予以淘汰
三、功能设计分析
在掌握基本的算法理论原理的基础上,能够选取合适的语言和开发工具,编写程序将虚拟存储管理中页面置换算法的机制动态的演示出来。具体功能主要包括:
①数据结构的定义:采用合适的数据结构描述页表;
②页面置换:采用选定的页面置换算法来模拟管理页表中页的置换过程; ③界面设计:要求有图形界面,能够直观的了解页面置换的过程,能够给出当前被置换出的页号,以及总的缺页次数。
四、程序设计
①FIFO页面置换算法:
√ √ √ √
定义一个二维数组,行数表示系统分配给该作业的页架数,列数表示作业的页面访问序列的次数。算法可以设计:二维数组中每列的第一个数字表示的页面是当前最先进入主存的页面,意思就是说如果发生缺页中断,就应该将该页面移出,方法是将本列下面的两个数据前移,然后将移入的页面置入本列最后的位置。
算法的伪代码描述形式: while (I
if(要访问的页面在当前第I列中) 不做任何处理,该列内容保持不变;
else (要访问的页面不在当前第I列中) 做页面置换处理;} 打印二维数组中的内容。 ② LRU页面置换算法:
√ √ √ √
定义一个二维数组,行数表示系统分配给该作业的页架数,列数表示作业的页面访问序列的次数。算法可以设计:二维数组中每列的第一个数字表示的页面是当前最近最少用的页面,意思就是说如果发生缺页中断,就应该将该页面移出,方法是将本列下面的两个数据前移,然后将移入的页面置入本列最后的位置。
算法的伪代码描述形式: while (I
if(要访问的页面在当前第I列中)
将该页面前移至该列最后一个位置,其余页面数字向前移动一位; else (要访问的页面不在当前第I列中) 做页面置换处理;} 打印二维数组中的内容。
五、运行截图
六、参考程序
#include #define Bsize 3 #define Psize 20 struct pageInfor { }; class PRA { public: PRA(void);
int content; //页面号 int timer; //被访问标记
int findSpace(void); //查找是否有空闲内存 int findExist(int curpage); //查找内存中是否有该页面 int findReplace(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]; }
int PRA::findSpace(void) {
for(int i=0; i
if(block[i].content == -1) for(int i=0; i
page = new pageInfor[Psize]; for(i=0; i
page[i].content = QString[i]; page[i].timer = 0; block[i].content = -1; block[i].timer = 0;
}
return -1;
int PRA::findExist(int curpage) { }
int PRA::findReplace(void) { }
void PRA::display(void) { }
void PRA::Optimal(void) {
for(int i=0; i
if(block[i].content != -1)
cout
int pos = 0;
for(int i=0; i
if(block[i].timer >= block[pos].timer)
pos = i;//找到应予置换页面,返回BLOCK中位置
for(int i=0; i
if(block[i].content == page[curpage].content)
return i;//找到内存中有该页面,返回BLOCK中位置
return -1;
return pos;
cout
for(int i=0; i
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
} else { space = findSpace(); if(space != -1) { } else block[space] = page[i]; display();
} } } } 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
} } } } display(); for(int j=0; j
void PRA::BlockClear(void)
{
}
void main(void)
{
cout
cout
cout
cout
cout
|"
cout
cout
cout
cout应用LRU算法"应用FIFO算法"应用Optimal算法"退出">select; switch(select) { case 0: break; case 1: cout
} } test.FIFO(); test.BlockClear(); cout
七、结果分析
程序可以设计为动态输入作业的页面访问序列,或将二维数组设计为动态数组,这样可以通过调整页面访问序列的次数或系统分配给作业的页架数,考察对缺页中断率的影响。
八、心得体会
通过两周的课程设计,加深了对操作系统的认识,了解了操作系统中各种资源分配算法的实现,特别是对虚拟存储,页面置换有了深入的了解,并能够用高级语言进行模拟演示。在这短短的两周时间里,通过浏览、阅读有关的资料,学到了很多东西,同时也发现仅仅书本的知识是远远不够的,需要把知识运用到实践中去,能力才能得到提高。有如下几点体会:
1.通过查阅相关资料对VC编程工具有了一定的了解,基本掌握了VC++ MFC
应用程序编写的基本方法。
2.使用MFC可视化编程极大的减少了编写的代码量,直观的界面设计,不但
便于修改,而且简化了界面程序代码的编写,便于集中精力到主算法的编写上。
3.两种页面置换算法FIFO和LRU理解起来相当容易,但在实际编程实现的时
候需要注意各种细节,需要耐心细致,实际编程中遇到一些细节上的小问题确实需要仔细考虑才行。
4. 因为需要用户输入后才能知道实际内存块和最大页面数的大小,所以用到
了动态数组函数CArray,在LRU算法中时间权值数组myb是关键,必须与页面变化同步。
另外,使我体会最深的是:任何一门知识的掌握,仅靠学习理论知识是远远不够的,要与实际动手操作相结合才能达到功效。
通过这次的课程设计使自己的VC编程能力加强了不少,对页面置换有更深一层的了解。使我对操作系统特别是页面置换这一部分的认识有了很大的加深。一分耕耘,一分收获,这次的课程设计让我受益匪浅。虽然自己所做的很少也不够完善,但毕竟也是努力的结果。主要有以下几点收获:
1. 通过对上网和看书查阅相关资料,使自己对VC MFC语言的基本框架
有新的了解,加深了对可视化程序的认识。
2. 在使用VC语言来实现功能时,不像以往用的其他语言,它比较简练,
更容易理解,实用性很强。
3. 先进先出页面置换和LRU算法两者各有特点,但是实践起来却很大,
使自己对页面置换算法有了新的认识。
两周的课程设计就要结束了,不但对专业知识有了更深的理解,更使的自己认识到实践的重要性,理论、实践相结合才能达到很好的学习效果,特别是程序语言的学习。