实验七请求页式存储管理中常用页面置换算法模拟实验七请求页式存储管理中常用页面置换算法模拟实验学时:4实验类型:设计实验要求:必修一、实验目的(1)了解内存分页管理策略(2)掌握调页策略(3)掌握一般常用的调度算法(4)学会各种存储分配算法的实现方法。
(5)了解页面大小和内存实际容量对命中率的影响。
二、实验内容(1)采用页式分配存储方案，通过分别计算不同算法的命中率来比较算法的优劣，同时也考虑页面大小及内存实际容量对命中率的影响;(2)实现OPT 算法 (最优置换算法) 、LRU 算法 (Least Recently) 、 FIFO 算法 (First IN First Out)的模拟;(3)会使用某种编程语言。
三、实验原理分页存储管理将一个进程的逻辑地址空间分成若干大小相等的片，称为页面或页。
在进程运行过程中，若其所要访问的页面不在内存而需把它们调入内存，但内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据，送磁盘的对换区中。
但应将哪个页面调出，须根据一定的算法来确定。
通常，把选择换出页面的算法称为页面置换算法(Page_Replacement Algorithms)。
一个好的页面置换算法，应具有较低的页面更换频率。
从理论上讲，应将那些以后不再会访问的页面换出，或将那些在较长时间内不会再访问的页面调出。
1、最佳置换算法OPT(Optimal)它是由Belady于1966年提出的一种理论上的算法。
其所选择的被淘汰页面，将是以后永不使用的或许是在最长(未来)时间内不再被访问的页面。
采用最佳置换算法，通常可保证获得最低的缺页率。
但由于人目前还无法预知一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，便可以利用此算法来评价其它算法。
2、先进先出(FIFO)页面置换算法这是最早出现的置换算法。
该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。
该算法实现简单只需把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。
3、最近最久未使用置换算法(1)LRU(Least Recently Used)置换算法的描述FIFO置换算法性能之所以较差，是因为它所依据的条件是各个页面调入内存的时间，而页面调入的先后并不能反映页面的使用情况。
最近最久未使用(LRU)置换算法，是根据页面调入内存后的使用情况进行决策的。
由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU置换算法是选择最近最久未使用的页面予以淘汰。
该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t,，当须淘汰一个页面时，选择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰。
(2)LRU置换算法的硬件支持LRU置换算法虽然是一种比较好的算法，但要求系统有较多的支持硬件。
为了了解一个进程在内存中的各个页面各有多少时间未被进程访问，以及如何快速地知道哪一页是最近最久未使用的页面，须有以下两类硬件之一的支持:a)寄存器为了记录某个进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位寄存器，可表示为R=RRR……RRR当进程访问某物理块时，要将相应寄存器的Rn-1位置成1。
n-1n-2n-3210此时，定时信号将每隔一定时间(例如100ms)将寄存器右移一位。
如果我们把n位寄存器的数看作是一个整数，那么具有最小数值的寄存器所对应的页面，就是最近最久未使用的页面。
如图1示出了某进程在内存中具有8个页面，为每个内存页面配置一个8位寄存器时的LRU访问情况。
这里，把8个内存页面的序号分别定为1――,8。
由图可以看出，第7个内存页面的R值最小，当发生缺页时首先将它置换出去。
R7 R6 R5 R4 R3 R2 R1 R01 0 1 0 1 0 0 1 02 1 0 1 0 1 1 0 03 0 0 0 0 0 1 0 04 0 1 1 0 1 0 1 15 1 1 0 1 0 1 1 06 0 0 1 0 1 0 1 17 0 0 0 0 0 1 1 18 0 1 1 0 1 1 0 1b)栈可利用一个特殊的栈来保存当前使用的各个页面的页面号。
每当进程访问某页面时，便将页面的页面号从栈中移出，将它压入栈顶。
因此，栈顶始终是最新被访问页面的编号民，而栈底则是最近最久未使用的页面的页面号。
四、程序清单参考实验步骤如下:// 现定义数据结构和全局变量。
#include<stdio.h>#include<conio.h>#define M 4#define N 17#define Myprintf printf("|---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---|\n") /*表格控制*/typedef struct page{ int num; /*记录页面号*/int time; /*记录调入内存时间*/}Page; /* 页面逻辑结构，结构为方便算法实现设计*/Page b[M]; /*内存单元数*/int c[M][N]; /*暂保存内存当前的状态:缓冲区*/ int queue[100]; /*记录调入队列*/int K; /*调入队列计数变量*///初始化内存单元、缓冲区void Init(Page *b,int c[M][N]){ int i,j;for(i=0;i<N;i++){ b[i].num=-1;b[i].time=N-i-1; }for(i=0;i<M;i++)for(j=0;j<N;j++)c[i][j]=-1;}//取得在内存中停留最久的页面,默认状态下为最早调入的页面 int GetMax(Page *b) { int i;int max=-1;int tag=0;for(i=0;i<M;i++){ if(b[i].time>max){ max=b[i].time;tag=i; } }return tag;}//判断页面是否已在内存中int Equation(int fold,Page *b){ int i;for(i=0;i<M;i++)if (fold==b[i].num) return i;return -1;}//LRU算法void Lru(int fold,Page *b) { int i;int val;val=Equation(fold,b);if (val>=0){ b[val].time=0;for(i=0;i<M;i++)if (i!=val) b[i].time++;}else{ queue[++K]=fold;/*记录调入页面*/val=GetMax(b);b[val].num=fold;b[val].time=0;for(i=0;i<M;i++)if (i!=val) b[i].time++;}}//FIFO与OPT的算法描述省略。
//主程序void main(){int a[N]={1,0,1,0,2,4,1,0,0,8,7,5,4,3,2,3,4}; int i,j;start:K=-1;Init(b, c);for(i=0;i<N;i++){ Lru(a[i],b);c[0][i]=a[i];/*记录当前的内存单元中的页面*/for(j=0;j<M;j++)c[j][i]=b[j].num;}/*结果输出*/printf("内存状态为:\n");Myprintf;for(j=0;j<N;j++)printf("|%2d ",a[j]);printf("|\n");Myprintf;for(i=0;i<M;i++){ for(j=0;j<N;j++)if(c[i][j]==-1) printf("|%2c ",32); elseprintf("|%2d ",c[i][j]);printf("|\n");}Myprintf;printf("\n调入队列为:");for(i=0;i<K+1;i++)printf("%3d",queue[i]);printf("\n缺页次数为:%6d\n缺页率:%16.6f",K+1,(float)(K+1)/N); printf("\nAre you continuing!\ty?");if(getche()=='y') goto start; }六、思考题(1)补充完成FIFO与OPT的算法。
(2)为什么在实际的系统中不用LRU置换算法，而用它的近似算法,(3)OPT算法为什么难以实现,。