存储管理的主要功能之一是合理地分配空间。

请求页式管理是一种常用的虚拟存储管理技术。

本课程设计的目的是通过请求页式存储管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页式管理的页面置换算法。

1．过随机数产生一个指令序列，共320条指令。

其地址按下述原则生成：①50％的指令是顺序执行的；②25％的指令是均匀分布在前地址部分；③25％的指令是均匀分布在后地址部分；#具体的实施方法是：A. 在[0，B. 319]的指C. 令地址之间随机选区一起点M;B. 顺序执行一条指E. 令，F. 即执行地址为M+1的指G. 令；C. 在前地址[0，I. M+1]中随机选取一条指J. 令并执行，K. 该指L. 令的地址为M’;D. 顺序执行一条指N. 令，O. 其地址为M’+1；E. 在后地址[M’+2，Q. 319]中随机选取一条指R. 令并执行；F. 重复T. A—E，U. 直到执行320次指V. 令。

2．指令序列变换成页地址流设：（1）页面大小为1K；（2）用户存容量为4页到32页；（3）用户虚存容量为32K。

在用户虚存中，按每K存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为：第0条—第9条指令为第0页（对应虚存地址为[0，9]）；第10条—第19条指令为第1页（对应虚存地址为[10，19]）；。

第310条—第319条指令为第31页（对应虚存地址为[310，319]）；按以上方式，用户指令可组成32页。

3. 计算并输出下述各种算法在不同存容量下的命中率。

A. FIFO先进先出的算法B. LRR最近最少使用算法C. OPT最佳淘汰算法（先淘汰最不常用的页地址）D. LFR最少访问页面算法E. NUR最近最不经常使用算法二、课程设计环境要求1、硬件环境PC机一台，0.99G存，2.00GHZ 主频2、软件环境Windows XP/2000系统，编程软件VC++。

三、设计任务介绍及系统需求分析本课程设计主要的目的是编制页面置换算法FIFO、LRU、LFU、NUR和OPT的模拟程序,并模拟其在存的分配过程。

同时根据页面走向，分别采用FIFO、LRU、LFU、NUR和OPT算法进行页面置换，统计命中率；为简化操作，在淘汰一页时，只将该页在页表中抹去,而不再判断它是否被改写过，也不将它写回到辅存。

本程序实现了操作系统中页式虚拟存储管理中缺页中断理想型淘汰算法，该算法在访问串中将来再也不出现的或是在离当前最远的位置上出现的页淘汰掉。

这样，淘汰掉该页将不会造成因需要访问该页又立即把它调入的现象。

该程序能按要求随机确定存大小，随机产生页面数，进程数，每个进程的页数，给进程分配的页数等，然后运用理想型淘汰算法对每个进程进行计算缺页数，缺页率，被淘汰的序列等功能。

四、概要设计系统分为4个子模块：初始化模块，FIFO、LRU、LFU、NUR和OPT的五个算法模块。

初始化模块：initialize( )初始化函数，给每个相关的页面赋值。

FIFO算法模块：计算使用FIFO算法时的命中率。

LRU算法模块：计算使用LRU算法时的命中率。

LFU算法模块：计算使用OPT算法时的命中率。

NUR算法模块：计算使用LFU算法时的命中率。

OPT算法模块：计算使用NUR算法时的命中率。

五、详细设计本实验的程序设计基本上按照实验容进行。

即首先用srand()和rand()函数定义和产生指令序列，然后将指令序列变换成相应的页地址流，并针对不同的算法计算出相应的命中率。

相关定义如下：1 数据结构(1)页面类型typedef struct{int pn,pfn,count,time;}pl-type;其中pn 为页号,pfn为面号, count为一个周期访问该页面的次数, time为访问时间.(2) 页面控制结构pfc-struct{int pn,pfn;struct pfc_struct *next;}typedef struct pfc_struct pfc_type;pfc_type pfc_struct[xy],*free_head,*busy_head;pfc_type *busy_tail;其中pfc[xy]定义用户进程虚页控制结构,*free_head为空页面头的指针,*busy_head为忙页面头的指针,*busy_tail为忙页面尾的指针.2．函数定义（1）Void initialize( ):初始化函数,给每个相关的页面赋值.（2）Void FIFO( ):计算使用FIFO算法时的命中率.（3）Void LRU( ):计算使用LRU算法时的命中率.（4）Void OPT( ):计算使用OPT算法时的命中率.（5）Void LFU( ):计算使用LFU算法时的命中率.（6）Void NUR( ):计算使用NUR算法时的命中率.3.变量定义(1)int a[zl]: 指令流数据组.(2)int page[zllc]: 每条指令所属的页号.(3)int offset[zllc]: 每页装入10条指令后取模运算页号偏移值.(4)int pf: 用户进程的存页面数.(5)int disaffect: 页面失效次数.先进先出算法，即FIFO算法（First-InFirst-Outalgorithm）。

这种算法选择最先调入主存储器的页面作为被替换的页面。

它的优点是比较容易实现，能够利用主存储器中页面调度情况的历史信息，但是，没有反映程序的局部性。

因为最先调入主存的页面，很可能也是经常要使用的页面。

近期最少使用算法，即LFU算法（LeastFrequentlyUsedalgorithm）。

这种算法选择近期最少访问的页面作为被替换的页面。

显然，这是一种非常合理的算法，因为到目前为止最少使用的页面，很可能也是将来最少访问的页面。

该算法既充分利用了主存中页面调度情况的历史信息，又正确反映了程序的局部性。

但是，这种算法实现起来非常困难，它要为每个页面设置一个很长的计数器，并且要选择一个固定的时钟为每个计数器定时计数。

在选择被替换页面时，要从所有计数器中找出一个计数值最大的计数器。

因此，通常采用如下一种相对比较简单的方法。

最久没有使用算法，即LRU算法（LeastRecentlyUsedalgorithm）。

这种算法把近期最久没有被访问过的页面作为被替换的页面。

它把LFU算法中要记录数量上的"多"与"少"简化成判断"有"与"无"，因此，实现起来比较容易。

NUR算法NUR在需要淘汰某一页时，从那些最近一个时期未被访问的页中任选一页淘汰。

只要在页表中增设一个访问位即可实现。

当某页被访问时，访问位置1。

否则，访问位置0。

系统周期性地对所有引用位清零。

当需淘汰一页时，从那些访问位为零的页中选一页进行淘汰。

如果引用位全0或全1，NRU算法退化为FIFO算法。

最优替换算法，即OPT算法（OPTimalreplacementalgorithm）。

上面介绍的几种页面替换算法主要是以主存储器中页面调度情况的历史信息为依据的，它假设将来主存储器中的页面调度情况与过去一段时间主存储器中的页面调度情况是相同的。

显然，这种假设不总是正确的。

最好的算法应该是选择将来最久不被访问的页面作为被替换的页面，这种替换算法的命中率一定是最高的，它就是最优替换算法。

要实现OPT算法，唯一的办法是让程序先执行一遍，记录下实际的页地址流情况。

根据这个页地址流才能找出当前要被替换的页面。

显然，这样做是不现实的。

因此，OPT算法只是一种理想化的算法，然而，它也是一种很有用的算法。

实际上，经常把这种算法用来作为评价其它页面替换算法好坏的标准。

在其它条件相同的情况下，哪一种页面替换算法的命中率与OPT算法最接近，那么，它就是一种比较好的页面替换算法。

1.页面调度模拟算法流程示例图2.页面调度模拟算法示例图六、调试过程程序结果：从上述结果可知，在存页面数较少（4~5页）时，五种算法的命中率差别不大，都是30%左右。

在存页面为7~18个页面之间时，5种算法的访命中率大致在35%~60%之间变化。

但是，FIFO算法与OPT算法之间的差别一般在6~10个百分点左右。

在存页面为25~32个页面时，由于用户进程的所有指令基本上都已装入存，使命中率增加，从而算法之间的差别不大。

比较上述5种算法，以OPT算法的命中率最高，NUR算法次之，再就是LFU 算法和LRU算法，其次是FIFO算法。

就本问题，在15页之前，FIFO的命中率比LRU的高。

七、结论与体会这个程序基本完成了存储管理程序设计的目的与要求。

不过其中也有一些不足之处，例如算法有点麻烦，有些句子不是很能理解。

但是我通过上网查找资料，去图书馆借阅相关书籍解决了这些不足之处。

本次课程设计主要可以分为两个阶段，在第一个阶段中，要了解五种算法的执行原理，存的分配策略，存调页策略；第二个阶段主要是编制程序和运行改善程序。

通过编写程序可以更深入的理解算法和算法的特点。

这次操作系统的课程设计，让我对实验原理有更深的理解，通过把该算法的容，算法的执行顺序在计算机上实现，知道和理解了该理论在计算机中是怎样执行的，对该理论在实践中的应用有深刻的理解。

并且这次课程设计把各个学科之间的知识融合起来，把各门课程的知识联系起来，对计算机整体的认识更加深刻。

八、参考文献1、《计算机操作系统》汤子赢等电子科技大学2、《操作系统教程题解与实验指导》孟静高等教育 2003年3、《C语言程序设计》田祥宏等电子科技大学4、《软件工程》燕慧等5、《数据结构教程》（第三版）谢希仁等电子工业附件：源程序清单#include<stdlib.h>#include<stdio.h>#include<time.h>#define TRUE 1#define FALSE 0#define INVALID -1#define NULL 0#define zllc 320 /*指令流长*/#define xy 32 /*虚页长*/#define clear 50 /*清0周期*/typedef struct /*页面结构*/{int pn; //页号 logic numberint pfn; //页面框架号 physical frame numberint count; //计数器int time; //时间}pc;pc pl[xy]; /*页面线性结构---指令序列需要使用地址*/typedef struct pfc_struct /*页面控制结构，调度算法的控制结构*/ {int pn;int pfn;struct pfc_struct *next;}pfc_type;pfc_type pfc[xy], *free_head, *busy_head, *busy_tail;int zhihuan, a[zllc]; /* a[]为指令序列*/int page[zllc], offset[zllc]; /*地址信息*/int initialize(int);int FIFO(int);int LRU(int);int LFU(int);int NUR(int);int OPT(int);int main(){int s,i;srand((unsigned)time(NULL));s=rand()%320;for(i=0;i<zllc;i+=4) /*产生指令队列*/{if(s<0||s>319){printf("When i==%d,Error,s==%d\n",i,s);exit(0);}a[i]=s;a[i+1]=a[i]+1;a[i+2]=rand()%(a[i+1]+1);a[i+3]=a[i+2]+1;s=rand()%(319-a[i+3])+a[i+3]+1;if((a[i+2]>318)||(s>319))printf("a[%d+2],a number which is :%d and s==%d\n",i,a[i+2],s);}for(i=0;i<zllc;i++) /*将指令序列变换成页地址流*/{page[i]=a[i]/10;offset[i]=a[i]%10;}for(i=4;i<=32;i++) /*用户存工作区从4个页面到32个页面*/{printf("%2d page frames:\n",i);FIFO(i);LRU(i);LFU(i);NUR(i);OPT(i);}return 0;}/*初始化相关数据结构 pf表示存的块数 */int initialize(int pf){int i;zhihuan=0;for(i=0;i<xy;i++){pl[i].pfn=INVALID; /*置页面控制结构中的页号，页面为空*/pl[i].count=0; /*页面控制结构中的访问次数为0*/pl[i].time=-1; /*访问的时间*/}for(i=0;i<pf-1;i++) /*建立pfc[i-1]和pfc[i]之间的*/{pfc[i].next=&pfc[i+1];pfc[i].pfn=i;}pfc[pf-1].next=NULL;pfc[pf-1].pfn=pf-1;free_head=&pfc[0]; /*空页面队列的头指针为pfc[0]*/return 0;}int FIFO(int pf) /*先进先出算法pf:用户进程的存页面数*/{int i;pfc_type *p; /*中间变量*/initialize(pf); /*初始化相关页面控制用数据结构*/ busy_head=busy_tail=NULL; /*忙页面队列头，队列尾*/for(i=0;i<zllc;i++){if(pl[page[i]].pfn==INVALID) /*页面失效*/{zhihuan++; /*失效次数*/if(free_head==NULL) /*无空闲页面*/{p=busy_head->next; //保存忙页面下一个页面pl[busy_head->pn].pfn=INVALID; //把这个页面换出，更新它的数据成员free_head=busy_head; /*释放忙页面队列的第一个页面*/free_head->next=NULL; /*表明还是缺页*/busy_head=p; //更新忙页面的队头指针}p=free_head->next;free_head->pn=page[i];pl[page[i]].pfn=free_head->pfn;free_head->next=NULL; /*使busy的尾为null*/if(busy_tail==NULL){busy_tail=busy_head=free_head;}else{//把刚刚换进来的接在busy_tail后面busy_tail->next=free_head;busy_tail=free_head;}free_head=p; //下一个空页面}}printf("FIFO:%6.4f ",1-(float)zhihuan/320);return 0;}int LRU (int pf) /*最近最久未使用算法least recently used*/{int min,minj,i,j,present_time; /*minj为最小值下标*/initialize(pf);present_time=0;for(i=0;i<zllc;i++){if(pl[page[i]].pfn==INVALID) /*页面失效*/{zhihuan++;if(free_head==NULL) /*无空闲页面*/{min=32767; /*设置最大值*/for(j=0;j<xy;j++) /*找出time的最小值*/{if(min>pl[j].time&&pl[j].pfn!=INVALID){min=pl[j].time;minj=j;}}free_head=&pfc[pl[minj].pfn]; //腾出一个单元pl[minj].pfn=INVALID;pl[minj].time=0;free_head->next=NULL;}pl[page[i]].pfn=free_head->pfn; //有空闲页面,改为有效pl[page[i]].time=present_time;free_head=free_head->next; //减少一个free 页面}else{pl[page[i]].time=present_time;//命中则增加该单元的访问次数present_time++;}}printf("LRU:%6.4f ",1-(float)zhihuan/320);return 0;}int NUR(int pf ) /*最近未使用算法Not Used recently count 表示*/{int i,j,dp,cont_flag,old_dp; //这个算法中count用于访问位initialize(pf);dp=0;for(i=0;i<zllc;i++){if (pl[page[i]].pfn==INVALID) /*页面失效*/{zhihuan++;if(free_head==NULL) /*无空闲页面*/{cont_flag=TRUE;old_dp=dp;while(cont_flag) //用cont_flag找到一个访问位count为0的页面{if(pl[dp].count==0&&pl[dp].pfn!=INVALID)cont_flag=FALSE;else //下一个页面{dp++;if(dp==xy) //32个页面找完一遍重新开始一个循环dp=0;if(dp==old_dp) // dp累积上一次访问到的地方old_dp，然后访问位重新清零for(j=0;j<xy;j++)pl[j].count=0;}}free_head=&pfc[pl[dp].pfn];pl[dp].pfn=INVALID;free_head->next=NULL;}pl[page[i]].pfn=free_head->pfn;free_head->pn=page[i];free_head=free_head->next;}elsepl[page[i]].count=1;if(i%clear==0)for(j=0;j<xy;j++)pl[j].count=0;}printf("NUR:%6.4f ",1-(float)zhihuan/320);return 0;}int OPT(int pf) /*最佳置换算法*/{int i,j, max,maxpage,dist[xy];initialize(pf);for(i=0;i<zllc;i++){if(pl[page[i]].pfn==INVALID) /*页面失效*/{zhihuan++;if(free_head==NULL) /*无空闲页面*/{for(j=0;j<xy;j++){if(pl[j].pfn!=INVALID) //在主存中的页面，即将找出一个被替换出去的dist[j]=32767;elsedist[j]=0; //不在主存中的页面}for(j=0;j<xy;j++){if((pl[j].pfn!=INVALID)&&(dist[j]==32767)){dist[j]=j;}}max=0;for(j=0;j<xy;j++) //找最远距离的，因为在主存中的最后一页即是在虚存中的最后一页if(max<dist[j]){max=dist[j];maxpage=j;}free_head=&pfc[pl[maxpage].pfn];free_head->next=NULL;pl[maxpage].pfn=INVALID;}pl[page[i]].pfn=free_head->pfn;free_head=free_head->next;}}printf("OPT:%6.4f \n",1-(float)zhihuan/320);return 0;}/*该算法时根据已知的预测未知的，least frequency Used是最不经常使用置换法*/int LFU(int pf) //这个算法中count用于计数{int i,j,min,minpage;initialize(pf);for(i=0;i<zllc;i++){if(pl[page[i]].pfn==INVALID) /*页面失效*/{zhihuan++;if(free_head==NULL) /*无空闲页面*/{min=32767;/*获取count的使用用频率最小的存*/for(j=0;j<xy;j++){if(min>pl[j].count&&pl[j].pfn!=INVALID){min=pl[j].count;minpage=j;}}free_head=&pfc[pl[minpage].pfn];pl[minpage].pfn=INVALID;pl[minpage].count=0;free_head->next=NULL;}pl[page[i]].pfn=free_head->pfn; //有空闲页面,改为有效pl[page[i]].count++;free_head=free_head->next; //减少一个free 页面}else{pl[page[i]].count;pl[page[i]].count=pl[page[i]].count+1;}}printf("LFU:%6.4f ",1-(float)zhihuan/320);return 0;}。