当前位置：首页 > 请求页式管理缺页中断模拟设计--FIFO、OPT
武汉理工大学《计算机操作系统教程》课程设计报告书
图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
本文作者：...共分享92篇相关文档
