1、太原工业学院计算机工程系实 验 报 告课程名称操作系统班级1120542实验日期2013-12-06姓 名聂建建学号06实验成绩实验名称存储器管理实验目的以及要求编程模拟实现存储器页面置换的常用算法，调试分析相关存储器管理程序，加深对存储器页面置换常用算法的理解和实现技巧实验环境Microsoft Visual Studio实验内容1、自定义存储器管理有关的数据结构；2、依据最佳置换算法（OPTIMAL）、先进先出置换算法（FIFO）、最近最久未使用算法（LRU）原理，编写对应函数，模拟系统的存储器页面置换功能；3、为了更好地模拟和评价算法的性能，允许用户自行指定可用页块数并输入需访问的页面号
2、序列；4、统计以上算法实际需要的总页面数、缺页中断次数以及它们的缺页率；5、比较/分析以上算法的置换性能，并作出自己的评价。算法描述及实验步骤 最佳置换算法（OPTIMAL） main（ ）先进先出置换算法（FIFO） 最近最久未使用算法（LRU）在进程运行过程中，若其所访问的页面不存在内存而需要不他们调入内存，但内存已无空闲时，为了保证该进程能够正常运行，系统必须从内存中调出一页程序或数据送磁盘的对换区中。但应掉出哪个页面需根据一定的算法来确定，算法的好坏，直接影响到系统的性能。一个好的页面置换法，应该有较低的页面更换频率。假设分给一个作业的物理块数为3，页面数为20个。页面号为（20个）：
3、1,2,5,6,0,3,6,5,3,6,5,6,0,4,2,7,0,4,3,51、 最佳置换算法（OPTIMAL）的思路：最佳置换算法：int pagepro:OPT() 其所选择的被淘汰页面，将是以后永不使用的，或许是在最长（未来）时间内不再被访问的页面，采用最佳置换算法，通常可以保证获得最低的缺页率。2、 先进先出置换算法（FIFO）的思路：先进先出算法：int pagepro:FIFO() 该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法只需把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。3、
4、最近最久未使用算法（LRU）的思路：最近最久未使用算法：int pagepro:LRU() 最近最久未使用的页面置换算法，是根据页面调入内存后的使用情况进行决策的。由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此最近最久未使用置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t，当须淘汰一个页面时，选择现有页面中其t值最大的，及最近最久未使用的页面予以淘汰。调试过程及实验结果最近最久未使用算法（LRU）：先进先出置换算法（FIFO）：最佳置换算法（OPTIMAL）：总结这个程序的主要思想
5、主题就是实现换页、怎样输出淘汰的序列、计算缺页数和缺页率。在程序中主要就是将在访问串中将来再也不出现的或现在离当前最远的位置上出现的页淘汰掉。当距离相等的时候就比较使用的次数，淘汰使用次数较少的那页。该过程共有三个函数即实现最佳置换算法（OPTIMAL）、FIFO的函数和实现LRU的函数，当主函数调用任意其中函数时来实现其算法。通过这次试验，能够熟练的掌握一些关于分配内存管理的一些算法。在调试过程中也出现的大多是关于内存分配和数组地址越界的问题，比如关于循环时各个事故的递增，还有就是显示给各个数组的内容等问题。就是因为这些问题，多次造成了淘汰序列出错。在以后的实验中应该多加注意。附录#incl
6、udeusing namespace std;#define Bsize 3 /进程页块数#define Psize 20 /访问序列长度struct Pageint num; /页面号int timer; /计时;class pagepropublic:pagepro(int pstr);int findspace(); /若内存块中有空，返回该位置int findhave(int p); /若内存块中已有页，返回内存块中位置int findreplace(); /找到替换页的位置(for LRU)int findreplace(int i); /找到替换页的位置(for OPT)void
7、clear(); /清理内存块void display(); /打印内存块信息int LRU(); /最近最久未使用算法int FIFO(); /先进先出算法int OPT(); /最佳置换算法Page *block; /内存块Page *page; /页面号串;pagepro:pagepro(int pstr)int i=0;block=new PageBsize;for(i=0;iBsize;i+)blocki.num=-1;blocki.timer=0;page=new PagePsize;for(i=0;iPsize;i+)pagei.num=pstri;pagei.timer=0;i
8、nt pagepro:findspace()for(int i=0;iBsize;i+)if(blocki.num=-1)return i;return -1;int pagepro:findreplace(int i)int pos3=0;int postion=0;for(int j=0;jBsize;j+)for(int k=i;kPsize;k+)if(blockj.num=pagek.num)break;elseposj+;for(j=1;j pospostion)postion=j;return postion;int pagepro:findhave(int p)for(int
9、i=0;iBsize;i+)if(blocki.num=pagep.num)return i;return -1;void pagepro:display()for(int i=0;iBsize;i+)if(blocki.num !=-1)coutblocki.num ;coutendl;int pagepro:findreplace()int pos=0;for(int i=1;i blockpos.timer)pos = i;return pos;void pagepro:clear()for(int i=0;iBsize;i+)blocki.num=-1;blocki.timer=0;i
10、nt pagepro:LRU()int have,space,pos;int count=0; /不缺页计数for(int i=0;iPsize;i+)have=findhave(i);if(have != -1)count+;blockhave.timer=-1;coutpage find in block!endl;elsespace=findspace();if(space != -1)blockspace=pagei;display();elsepos=findreplace();blockpos=pagei;display();for(int i=0;iBsize;i+)blocki
11、.timer+;return count;int pagepro:FIFO()int have;int j=0; /j%3 记录替换位置int count=0;for(int i=0;iPsize;i+)have=findhave(i);if(have!=-1)count+;coutpage find in block!endl;elseblockj%3=pagei;j+;display();return count;int pagepro:OPT()int have,space;int count=0;for(int i=0;iPsize;i+)have=findhave(i);if(hav
12、e!=-1)coutpage find in block!endl;count+;elsespace=findspace();if(space!=-1)blockspace=pagei;display();elseblockfindreplace(i)=pagei;display(); return count;int main()int pstr20=1,2,5,6,0,3,6,5,3,6,5,6,0,4,2,7,0,4,3,5;/ int pstr20=7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,1,7,0;pagepro p1(pstr);int c=0,sele
13、ct=0;cout*页面置换算法模拟*endl;cout 1.LRU endl;cout 2.FIFOendl;cout 3.OPT endl;cout 0.exitendl;cout*endl;while(1)coutselect;switch(select)case 1:c=p1.LRU();couttotal:20nfind:cendl;p1.clear();break;case 2:c=p1.FIFO();couttotal:20nfind:cendl;p1.clear();break;case 3: c=p1.OPT();couttotal:20nfind:cendl;p1.clear();break;default: exit(0);return 0;
