发布时间 : 星期三 文章请求页式管理缺页中断模拟设计--FIFO、OPT更新完毕开始阅读6d192dea6137ee06eff91847
武汉理工大学《计算机操作系统教程》课程设计报告书
图1请求分页流程图
2.2设计说明
2.2.1算法分析
在进程运行过程中,若其所要访问的页面不在内存,需要把它们调入内存,但内存已无空闲已空闲空间时,为了保证该进程能正常运行,系统必须从内存中调出一页程序或数据,送磁盘的对换区。但应将哪个页面调出,必须根据替换算法来确定。
该设计采用的是常见置换算法中的先进先出(FIFO)、理想型淘汰算法OPT(Optimal Replacement Algorithm)。
详细算法原理如下:
FIFO(先进先出算法)基本思想:总是选择在内存驻留时间最长的一页将其淘汰,因为最早调入内存的页,不再被使用的可能性比近期调入内存的大。
4
4
武汉理工大学《计算机操作系统教程》课程设计报告书
该算法实现简单,只需要把一个进程调入内存的页面,按先后次序连结成一个队列,并设置一个指针,称为替换指针,使它总是指向最老的页面。但是该算法与进程实际运行的规律不相适应,因为在进程中,有些页面经常被访问,比如有全局变量、常用函数,例程等的页面,FIFO算法并不能保证这些页面不被淘汰。
使用FIFO替换算法效率比较低,可能会比理想型算法要多出一倍。低的原因是:基于处理器按线性顺序访问地址空间这一假设。事实上,许多时候,处理器不是按线性顺序访问地址空间的。例如,执行循环结构的程序段。
使用FIFO算法时,在未给进程或作业分配足够它所需要的页面数时,有时会出现分配的页面数增,缺页次数反而增加的现象(Belady现象)。 例如针对请求序列:1 2 3 4 1 2 5 1 2 3 4 5,若分配3个可用内存块,使用FIFO算法,一共会缺页9次,缺页率:75%;而如果分配4个可用内存块,则一共会缺页10次,缺页率:83.3%。
OPT(理想型淘汰算法)基本思想:当要调入一新页而必须淘汰一旧页时,所淘汰的页是以后不再使用的,或者是以后相当长的时间内不会使用的。采用理想型替换算法,通常可保证获得最低的缺页率。但是由于人们目前无法预知一个进程在内存的若干个页面中,哪个页面是未来最长时间内不再被访问的,因而该算法是无法实现的,但是在模拟设计中,由于是事先给定一个页面序列,即知道各个时刻以前和以后的页面出现情况,所以可实现该算法。在实际系统中,虽无法实现理想型淘汰算法,但是可用它来评价其他替换算法。 2.2.2数据结构
模拟设计时,页表没项记录的数据类型用结构体定义。整该页表用数组模拟。结构体有三个成员:int page_num 表示页面号;int memory_num表示页面所对应的内存块号;int is_in_memory是存在状态位标志,表示页面是否在内存,0表示不在内存,1表示在内存。在每一个算法函数中都要初始化页表,否则,后面的算法会受前面算法结果的影响。 struct page { int page_num; //表示页面号 int memory_num; //表示页面所对应的内存块号
int is_in_memory;// 是存在状态位标志,表示页面是否在内存,
5
5
武汉理工大学《计算机操作系统教程》课程设计报告书
0 表示不在内存,1表示在内存
};
page page_table[初始值];
for(int i=0;i<10;i++) //初始化页表:
{
page-table[i].page_num=i;
page_table[i].memory_num=-1; //初始化,内存块号为-1,即没在内存块中。 page_table[i].is_in_memory =0; //初始化时,各页面均不在内存 }
页面请求序列:int *page_array= new int[inputSize]。
内存在程序中模拟内存存放页面号:int *memory=new int[memorySize]
2.2.3函数实现
Control()函数是class control的构造函数,用来初始化页表、内存(调用
initial()函数)。提示并接受用户输入等待调入页面数page_size,可用物理块数memory_size,并随机生成请求页面,或用户自己输入。然后调用FIFO()、OPT()函数实现按不同替换算法调入页面进内存。
void FIFO()函数实现先进先出的替换算法调入页面。 void OPT()函数实现理想型替换算法。
3程序的主要模块说明
3.1 control类封装内存管理
3.1.1 FIFO替换算法实现伪函数
void control::FIFO(){
control::init(); 初始化页表等
do{
if(当前页在内存)
else(当前页不在内存,直接加载进入物理块){
缺页累积;
加载当前页进入内存;
修改页表置当前页在页表的是否在内存标志为1。 将该页在内存的位置对应。 }
}while(内存物理块没有加载满);
6
6
武汉理工大学《计算机操作系统教程》课程设计报告书
//内存物理块已经加载满了; }
for(剩下的页面循环){ }
输出缺页次,缺页率,淘汰页面次序。
if(当前页在内存) else(当前页不在内存){ }
缺页累积。 替换页面;
修改页表置当前页在页表的是否在内存标志为1。 将该页在内存的位置对应。 利用算法得到下次替换的物理块号。
3.1.2 OPT替换算法实现伪函数 void control::OPT()
{
control::init();//初始化页表等
for(对每个页表循环处理)
{
for(检查每个物理块) {
if (如果该页在内存物理块中)
置判别标志为1
}
if(如果该页不在内存,并且物理快放满) {
缺页累加并权值数组每个记录元素清零
for(物理块每个元素检查)
7
7