OS存储管理——FIFO,LRU,OPT命中率

课程设计课题

存储管理程序设计

摘 要

虚拟存储器作为现代操作系统中存储管理的一项重要技术，实现了内存扩充功能。而分页请求分页系统正好可以完美的支持虚拟存储器功能，它具有请求调页功能和页面置换功能。在进程运行过程中。若其所访问的页面不存在，而需把他们调入内存，但内存无空闲时间时，为了保证该程序能够正常运行，系统必须从内存中调出一页程序或数据送到磁盘的兑换区中，通常，把选择换出页面的算法称为页面置换算法。一个好的置换算法应该具有较低的页面更换频率，所以本次实验中用了FIFO,LRU,OPT三种重要的置换算法。

关键词：分页；虚拟存储；FIFO；LRU;OPT;

一、课程设计的目的和要求

1、目的：存储管理的主要功能之一是合理地分配空间。请求页式管理是一种常用的虚拟存储管理技术。本次设计的目的是通过请求页式存储管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页式管理的页面置换算法。

2、要求：

（1）．过随机数产生一个指令序列，共320条指令。其地址按下述原则生成：

①50%的指令是顺序执行的；

②25%的指令是均匀分布在前地址部分；

③25%的指令是均匀分布在后地址部分；

（2）. 指令序列变换成页地址流

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

二、系统需求分析与总体设计

存储管理程序是可以进行合理的分配空间，而请求页式管理是一种常用的虚拟存储管理技术，通过这种技术用三种不同的算法来分配地址空间，算出这三种算法的命中率。

1、定义页面的结构（既然用到了分页式管理就要先定义页面）

2、函数定义

3、写主函数用来调用三种算法

4、写好三种算法分别为：

（1）       FIFO（先进先出算法）这个算法的基本思想是：总是先淘汰一些驻留在内存时间最长的页面，即先进入内存的页面先被置换掉

（2）       LRU（最近最少使用算法）本算法的基本思想是：如果某一页被访问了，那么它很可能马上又被访问；反之，如果某一页很长时间没有被访问，那么最近也不太可能会被访问。

（3）       OPT（最优算法）这是最理想的页面置换算法：从内存中移出以后不再使用的页面；如无这样的页面，则选择以后最长时间内不需要访问的页面。

5、程序总体设计框图

Main( )

Initialize（pf） 框架初始化函数

FIFO 算法

LRU 算法

OPT 算法

三、详细设计

本实验中，命中率=1-页面失效次数/页地址流长度；在本实验中，页地址流长度为320，页面失效次数为每次访问相应指令时，该指令所对应的页不在内存的次数；随机数产生办法，由系统提供函数strand()和rand(),分别进行初始化和产生随机数。

1、定义页面的结构  

 

Typedef struct

{

Int pn,pfn,count,time;

}

pl_type;  其中pn为页号,pfn为面号,count为个周期内访问该页面次数time为访问时间。

2、函数定义

(1)void initialize():初始化函数,给每个相关的页面赋值。

(2)void FIFO():计算使用FIFO算法时的命中率。

(3)void LRU():计算使用LRU算法时的命中率。

(4)void OPT():计算使用OPT算法时的命中率。

3、主函数Main()

开始

（1）.先找出是否有指令，产生指令队列（2）.再按照要求的方法执行指令(3).将指定指令列转换成页地址流（题目中要求的是每页十个指令）(4).依次执行三种算法得出命中率

4、三种算法

（1）FIFO这个算法的基本思想是：总是

先淘汰一些驻留在内存时间最长的页面，

是否有指令

即先进入内存的页面先被置换掉。作业

只要把进入内存的各个页面按进入的时

计算出页号

间次序用链表链接起来，设定一个链表

首指针指向进入内存最早的一个页面，

新进入的页面放在链表的尾部，需要淘

汰某一个页面时，总是淘汰替换指针所

在实存队列查找该页号

指向的页面即可。先进先出算法在程序

按线性顺序访问逻辑地址空间时比较理

是否找到

想，否则效率不高。特别是在遇到循环

执行的程序段时，往往会把频繁访问的

页面，因其在内存驻留时间过长，                                                                                 yes

而周期性地淘汰掉。

no

新页号按序列加入实存序列

FIFO算法

计算出命中率

结束

开始

(2)LRU算法: 他的的基本思想是：如果某一页

被访问了，那么它很可能马上又被访问；反之，

如果某一页很长时间没有被访问，那么最近也不

是否有指令

太可能会被访问。这种算法考虑了程序设计的局

把新页放入队列，同时向下移动其余页号

部性原理。其实质是：当需要置换一页时，选择

最近一段时间内最久未使用的页面予以淘汰。

计算出页号

在实存队列中查找该页号

是否找到

新页进入队列，老页号移出

N

计算出命中率

结束

（3）OPT算法：这是最理想的页面置换算法：从内存中移出以后不再使用的页面；如无这样的页面，则选择以后最长时间内不需要访问的页面。本算法因为页面访问的顺序是很难预知的，所以不是一种实际的方法。

开始

是否有指令

计算出页号

Yes

在页面中查找是否存在

是否找到

将该页面导入空闲页面

no

是否有空闲页面

yes

no

计算出命中率

结束

按照指令队列查找以后指令找出每一页命中的距离，找出最大的或没命中的当前空闲页面

 

 

 

四、测试、调试过程

1、实验过程中遇到的问题：

起初开始接触题目的时候除了知道三种算法是怎么进行之外对于存储是一无所知，尤其是页式虚拟存储，后来经过网上查找资料才知道请求页式管理的调入方式是，当需要执行某指令二又发现它不在内存时或当执行某条指令需要访问其他数据或指令时，这些指令和数据不在内存中，从而发生缺页中断，系统将外出中相应的页面调入内存。

还有开始的时候需要生成随机数，后来进过查找才知道原来随机数还可以通过系统提供函数进行初始化和产生随机数

2、实验截图

 

五、结论与体会

通过切实的实验与分析，巩固了所学的有关页式存储管理的相关知识，更深层次地理解并掌握了LRU和随机淘汰算法的精髓。通过使用C语言模拟LRU和随机算法实现请求页式管理，进一步提高了我的编程能力，并且有助于将操作系统和C有机地结合起来，使我更加明白了学科之间是紧密联系的。此外，经过这次课程设计，我更加感悟到了，仅仅学习书本上的理论知识是不够的，要在平时多进行实际操作，这样才能融会贯通，更加牢固地掌握所学知识。在以后的学习过程中，我应该更加深入学习有关C的内容，提高自己的动手能力。我对于存储系统的了解大大的加深了，所有的东西都再是纸上谈兵，从基础的三种算法的实现：先进先出（FIFO）、最近最少使用（LRU）、最佳淘汰（OPT）、，可以清晰看出操作系统中一些原理性的东西，他的运行，他的工作方式，不只是靠自己对着课本的文字去想想了。

        而通过最优、最先、最差三种适应算法来对主存实现分配的过程中，更是深刻的体会到其中的微妙。分页管理中的运行结果出现之后一目了然，队列方式也是方便自如。是让书上不动的文字活了起来。

        整个实验下来，无论是翻课本查原理，还是上百度搜代码，都是促进我们学习实践的一大助力，让课堂上一些死板的知识流转在手指之间，跃现在荧屏上面。

 

 

 

六、参考文献

【1】 计算机操作系统  西安电子科技大学出版社。汤子瀛、哲凤屏、汤小丹编著

【2】VC++深入详解  电子工业出版社 。孙鑫 余安萍编著

【3】张尧学，史美林编著．计算机操作系统教程（第三版）．清华大学出版社．2006

【4】http://www.baidu.com

。。。。。。

 

 

 

 

 

 

 

附录：源程序

#include<stdio.h>

#include<stdlib.h>

#include<time.h>

#define TRUE 1

#define FALSE 0

#define INVALID -1

#define NULL 0

#define  zllc 320

#define  xy 32

#define  clear 100

/*以下统一解释  pn:page number,pfn:page frame number,pfc:page frame control*/

typedef struct /*页面结构*/

{

int pn; //页号

int pfn; //页面框架号

int 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  OPT(int);

/*初始化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)

{

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("A.FIFO:%6.6f",1-(float)zhihuan/320);

return 0;

}

/*最近最久未使用算法least recently used*/

int LRU (int pf)

{

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("B.LRU:%6.6f",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;

else

dist[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("C.OPT:%6.6f\n",1-(float)zhihuan/320);

return 0;

}

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;  /*任选一指令访问点m*/

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;  /*题目中的要求每页大小10指令*/

offset[i]=a[i]%10;

}

for(i=4;i<=32;i++)  /*用户内存工作区从4个页面到32个页面*/

{

printf("%2d page frames:\n",i);

FIFO(i);

LRU(i);

OPT(i);

}

return 0;

}