【注：根据课程设计大纲第四项具体要求撰写课程设计报告】
存储管理程序设计 一、实验目的
存储管理的主要功能之一是合理地分配空间。请求页式管理是一种常用的虚拟存储管理技术。
本实验的目的是通过请求页式存储管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页式管理的页面置换算法。
二．实验要求
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. 常用的页地址）
D LFR最少访问页面算法
E. NUR最近最不G. 经常使用算法
三、流程图
1. 页面调度模拟算法流程示例图
2. 页面调度模拟算法示例图
四．实验内容
本实验的程序设计基本上按照实验内容进行。即首先用srand()和rand()函数定义和产生指令序列，然后将指令序列变换成相应的页地址流，并针对不同的算法计算出相应的命中率。相关定义如下：
1 数据结构
(1)页面类型
typedef struct{
int pn,pfn,counter,time;
}pl-type;
其中pn 为页号,pfn 为面号, counter 为一个周期内访问该页面的次数, time 为访问时间.
(2) 页面控制结构
pfc-struct{
int pn,pfn;
struct pfc_struct *next;
}
typedef struct pfc_struct pfc_type;
pfc_type pfc_struct[total_vp],*freepf_head,*busypf_head;
pfc_type *busypf_tail;
其中pfc[total_vp]定义用户进程虚页控制结构,
*freepf_head为空页面头的指针,
*busypf_head为忙页面头的指针,
*busypf_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[total_instruction]: 指令流数据组.
(2)int page[total_instruction]: 每条指令所属的页号.
(3)int offset[total_instruction]: 每页装入10条指令后取模运算页号偏移值.
(4)int total_pf: 用户进程的内存页面数.
(5)int disaffect: 页面失效次数.
4．源程序代码
#define TRUE 1
#define FALSE 0
#define INVALID -1
#define NULL 0
#define total_instruction 320 /*指令流长*/
#define total_vp 32 /*虚页长*/
#define clear_period 50 /*清0周期*/
typedef struct /*页面结构*/
{
int pn; //页号 logic number
int pfn; //页面框架号 physical frame number
int counter; //计数器
int time; //时间
}pl_type;
pl_type pl[total_vp]; /*页面线性结构---指令序列需要使用地址*/
typedef struct pfc_struct /*页面控制结构，调度算法的控制结构*/
{
int pn;
int pfn;
struct pfc_struct *next;
}pfc_type;
pfc_type pfc[total_vp], *freepf_head, *busypf_head, *busypf_tail;
int diseffect, a[total_instruction]; /* a[]为指令序列*/
int page[total_instruction], offset[total_instruction];/*地址信息*/
int initialize(int);
int FIFO(int);
int LRU(int);
int LFU(int);
int NUR(int); //not use recently
int OPT(int);
int main( )
{
int s,i,j;
srand(10*getpid()); /*由于每次运行时进程号不同，故可用来作为初始化随机数队列的“种子”*/
s=(float)319*rand( )/32767/32767/2+1; /*正态分布*/
for(i=0;i
if(s319)
{
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]=(float)a[i]*rand( )/32767/32767/2; /*执行前地址指令m*/ a[i+3]=a[i+2]+1; /*顺序执行一条指令*/
s=(float)(318-a[i+2])*rand( )/32767/32767/2+a[i+2]+2; 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
page[i]=a[i]/10;
offset[i]=a[i]%10;
}
for(i=4;i
printf("---%2d page frames---\n",i);
FIFO(i);
LRU(i);
LFU(i);
NUR(i);
OPT(i);
}
return 0;
}
/*初始化相关数据结构 total_pf表示内存的块数 */
int initialize(int total_pf)
{
int i;
diseffect=0;
for(i=0;i
{
pl[i].pfn=INVALID; /*置页面控制结构中的页号，页面为空*/ pl[i].counter=0; /*页面控制结构中的访问次数为0*/ pl[i].time=-1; /*访问的时间*/
}
for(i=0;i
pfc[i].next=&pfc[i+1];
pfc[i].pfn=i;
}
pfc[total_pf-1].next=NULL;
pfc[total_pf-1].pfn=total_pf-1;
freepf_head=&pfc[0]; /*空页面队列的头指针为pfc[0]*/ return 0;
}
int FIFO(int total_pf) /*先进先出算法total_pf:用户进程的内存页面数*/
{
int i,j;
pfc_type *p; /*中间变量*/
initialize(total_pf); /*初始化相关页面控制用数据结构*/ busypf_head=busypf_tail=NULL; /*忙页面队列头，队列尾链接*/ for(i=0;i
{
if(pl[page[i]].pfn==INVALID) /*页面失效*/
{
diseffect+=1; /*失效次数*/
if(freepf_head==NULL) /*无空闲页面*/
{
p=busypf_head->next;
pl[busypf_head->pn].pfn=INVALID;
freepf_head=busypf_head; /*释放忙页面队列的第一个页面*/
freepf_head->next=NULL; /*表明还是缺页*/
busypf_head=p;
}
p=freepf_head->next;
freepf_head->pn=page[i];
pl[page[i]].pfn=freepf_head->pfn;
freepf_head->next=NULL; /*使busy 的尾为null*/
if(busypf_tail==NULL)
{
busypf_tail=busypf_head=freepf_head;
}
else
{
busypf_tail->next=freepf_head;
busypf_tail=freepf_head;
}
freepf_head=p;
}
}
printf("FIFO:%6.4f\n",1-(float)diseffect/320);
return 0;
int LRU (int total_pf) /*最近最久未使用算法least recently used*/ {
int min,minj,i,j,present_time; /*minj为最小值下标*/
initialize(total_pf);
present_time=0;
for(i=0;i
{
if(pl[page[i]].pfn==INVALID) /*页面失效*/ {
diseffect++;
if(freepf_head==NULL) /*无空闲页面*/ {
min=32767; /*设置最大值*/
for(j=0;j
{
if(min>pl[j].time&&pl[j].pfn!=INVALID)
{
min=pl[j].time;
minj=j;
}
}
freepf_head=&pfc[pl[minj].pfn]; //腾出一个单元 pl[minj].pfn=INVALID;
pl[minj].time=0;
freepf_head->next=NULL;
}
pl[page[i]].pfn=freepf_head->pfn; //有空闲页面, 改为有效 pl[page[i]].time=present_time;
freepf_head=freepf_head->next; //减少一个free 页面 }
else
{
pl[page[i]].time=present_time; //命中则增加该单元的访问次数
present_time++;
}
}
printf("LRU:%6.4f\n",1-(float)diseffect/320);
return 0;
}
int NUR(int total_pf ) /*最近未使用算法Not Used recently count表示*/
{
int i,j,dp,cont_flag,old_dp;
pfc_type *t;
initialize(total_pf);
dp=0;
for(i=0;i
{
if (pl[page[i]].pfn==INVALID) /*页面失效*/
{
diseffect++;
if(freepf_head==NULL) /*无空闲页面*/
{
cont_flag=TRUE;
old_dp=dp;
while(cont_flag)
{
if(pl[dp].counter==0&&pl[dp].pfn!=INVALID)
cont_flag=FALSE;
else
{
dp++;
if(dp==total_vp)
dp=0;
if(dp==old_dp)
for(j=0;j
pl[j].counter=0;
}
}
freepf_head=&pfc[pl[dp].pfn];
pl[dp].pfn=INVALID;
freepf_head->next=NULL;
}
pl[page[i]].pfn=freepf_head->pfn;
freepf_head->pn=page[i];
freepf_head=freepf_head->next;
}
else
pl[page[i]].counter=1;
if(i%clear_period==0)
for(j=0;j
pl[j].counter=0;
}
printf("NUR:%6.4f\n",1-(float)diseffect/320);
return 0;
}
int OPT(int total_pf) /*最佳置换算法*/
{
int i,j, max,maxpage,d,dist[total_vp];
pfc_type *t;
initialize(total_pf);
for(i=0;i
{
if(pl[page[i]].pfn==INVALID) /*页面失效*/ {
diseffect++;
if(freepf_head==NULL) /*无空闲页面*/ {
for(j=0;j
{
if(pl[j].pfn!=INVALID)
dist[j]=32767;
else
dist[j]=0;
}
for(j=0;j
{
if((pl[j].pfn!=INVALID)&&(dist[j]==32767)) {
dist[j]=j;
}
}
max=0;
for(j=0;j
if(max
{
max=dist[j];
maxpage=j;
}
freepf_head=&pfc[pl[maxpage].pfn];
freepf_head->next=NULL;
pl[maxpage].pfn=INVALID;
}
pl[page[i]].pfn=freepf_head->pfn;
freepf_head=freepf_head->next;
}
}
printf("OPT:%6.4f\n",1-(float)diseffect/320);
return 0;
}
/*该算法时根据已知的预测未知的，least frequency Used是最不经常使用置换法*/
int LFU(int total_pf)
{
int i,j,min,minpage;
pfc_type *t;
initialize(total_pf);
for(i=0;i
{
if(pl[page[i]].pfn==INVALID) /*页面失效*/
{
diseffect++;
if(freepf_head==NULL) /*无空闲页面*/
{
min=32767;
/*获取counter 的使用用频率最小的内存*/
for(j=0;j
{
if(min>pl[j].counter&&pl[j].pfn!=INVALID) {
min=pl[j].counter;
minpage=j;
}
}
freepf_head=&pfc[pl[minpage].pfn];
pl[minpage].pfn=INVALID;
pl[minpage].counter=0;
freepf_head->next=NULL;
}
pl[page[i]].pfn=freepf_head->pfn; //有空闲页面, 改为有效 pl[page[i]].counter++;
freepf_head=freepf_head->next; //减少一个free 页面
}
else
{
pl[page[i]].counter;
pl[page[i]].counter=pl[page[i]].counter+1;
}
}
printf("LFU:%6.4f\n",1-(float)diseffect/320);
return 0;
}
5. 程序运行结果
实验运行结果截图：
6．实验分析
从上述结果可知，在内存页面数较少（4~5页）时，五种算法的命中率差别不大，都是30%左右。在内存页面为7~18个页面之间时，5种算法的访内命中率大致在35%~60%之间变化。但是，FIFO 算法与OPT 算法之间的差别一般在6~10个百分点左右。在内存页面为25~32个页面时，由于用户进程的所有指令基本上都已装入内存，使命中率增加，从而算法之间的差别不大。
比较上述5种算法，以OPT 算法的命中率最高，NUR 算法次之，再就是LFU 算法和LRU 算法，其次是FIFO 算法。就本问题，在15页之前，FIFO 的命中率比LRU 的高。
7．时间分配：
8. 参考资料及网站
1、《计算机操作系统》汤子赢等 西安电子科技大学出版社
2、《操作系统教程题解与实验指导》孟静 高等教育出版社 2003年
五．实验心得和体会
通过该课程设计，全面系统的理解了存储构造的一般原理和基本实现方法。把死板的课本知识变得生动有趣，激发了学习的积极性。把学过的计算机操作系统的知识强化，能够把课堂上学的知识通过自己设计的程序表示出来，加深了对理论知识的理解。以前对与计算机操作系统的认识是模糊的，概念上的，现在通过自己动手做实验，从实践上认识了操作系统是如何处理命令的，如何协调计算机内部各个部件运行，对计算机操作系统的认识更加深刻。
这次操作系统的课程设计，让我对实验原理有更深的理解，通过把该算法的内容，算法的执行顺序在计算机上实现，知道和理解了该理论在计算机中是怎样执行的， 对该理论在实践中的应用有深刻的理解。并且这次课程设计把各个学科之间的知识融合起来 ，把各门课程的知识联系起来，对计算机整体的认识更加深刻。
【注：根据课程设计大纲第四项具体要求撰写课程设计报告】
存储管理程序设计 一、实验目的
存储管理的主要功能之一是合理地分配空间。请求页式管理是一种常用的虚拟存储管理技术。
本实验的目的是通过请求页式存储管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页式管理的页面置换算法。
二．实验要求
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. 常用的页地址）
D LFR最少访问页面算法
E. NUR最近最不G. 经常使用算法
三、流程图
1. 页面调度模拟算法流程示例图
2. 页面调度模拟算法示例图
四．实验内容
本实验的程序设计基本上按照实验内容进行。即首先用srand()和rand()函数定义和产生指令序列，然后将指令序列变换成相应的页地址流，并针对不同的算法计算出相应的命中率。相关定义如下：
1 数据结构
(1)页面类型
typedef struct{
int pn,pfn,counter,time;
}pl-type;
其中pn 为页号,pfn 为面号, counter 为一个周期内访问该页面的次数, time 为访问时间.
(2) 页面控制结构
pfc-struct{
int pn,pfn;
struct pfc_struct *next;
}
typedef struct pfc_struct pfc_type;
pfc_type pfc_struct[total_vp],*freepf_head,*busypf_head;
pfc_type *busypf_tail;
其中pfc[total_vp]定义用户进程虚页控制结构,
*freepf_head为空页面头的指针,
*busypf_head为忙页面头的指针,
*busypf_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[total_instruction]: 指令流数据组.
(2)int page[total_instruction]: 每条指令所属的页号.
(3)int offset[total_instruction]: 每页装入10条指令后取模运算页号偏移值.
(4)int total_pf: 用户进程的内存页面数.
(5)int disaffect: 页面失效次数.
4．源程序代码
#define TRUE 1
#define FALSE 0
#define INVALID -1
#define NULL 0
#define total_instruction 320 /*指令流长*/
#define total_vp 32 /*虚页长*/
#define clear_period 50 /*清0周期*/
typedef struct /*页面结构*/
{
int pn; //页号 logic number
int pfn; //页面框架号 physical frame number
int counter; //计数器
int time; //时间
}pl_type;
pl_type pl[total_vp]; /*页面线性结构---指令序列需要使用地址*/
typedef struct pfc_struct /*页面控制结构，调度算法的控制结构*/
{
int pn;
int pfn;
struct pfc_struct *next;
}pfc_type;
pfc_type pfc[total_vp], *freepf_head, *busypf_head, *busypf_tail;
int diseffect, a[total_instruction]; /* a[]为指令序列*/
int page[total_instruction], offset[total_instruction];/*地址信息*/
int initialize(int);
int FIFO(int);
int LRU(int);
int LFU(int);
int NUR(int); //not use recently
int OPT(int);
int main( )
{
int s,i,j;
srand(10*getpid()); /*由于每次运行时进程号不同，故可用来作为初始化随机数队列的“种子”*/
s=(float)319*rand( )/32767/32767/2+1; /*正态分布*/
for(i=0;i
if(s319)
{
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]=(float)a[i]*rand( )/32767/32767/2; /*执行前地址指令m*/ a[i+3]=a[i+2]+1; /*顺序执行一条指令*/
s=(float)(318-a[i+2])*rand( )/32767/32767/2+a[i+2]+2; 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
page[i]=a[i]/10;
offset[i]=a[i]%10;
}
for(i=4;i
printf("---%2d page frames---\n",i);
FIFO(i);
LRU(i);
LFU(i);
NUR(i);
OPT(i);
}
return 0;
}
/*初始化相关数据结构 total_pf表示内存的块数 */
int initialize(int total_pf)
{
int i;
diseffect=0;
for(i=0;i
{
pl[i].pfn=INVALID; /*置页面控制结构中的页号，页面为空*/ pl[i].counter=0; /*页面控制结构中的访问次数为0*/ pl[i].time=-1; /*访问的时间*/
}
for(i=0;i
pfc[i].next=&pfc[i+1];
pfc[i].pfn=i;
}
pfc[total_pf-1].next=NULL;
pfc[total_pf-1].pfn=total_pf-1;
freepf_head=&pfc[0]; /*空页面队列的头指针为pfc[0]*/ return 0;
}
int FIFO(int total_pf) /*先进先出算法total_pf:用户进程的内存页面数*/
{
int i,j;
pfc_type *p; /*中间变量*/
initialize(total_pf); /*初始化相关页面控制用数据结构*/ busypf_head=busypf_tail=NULL; /*忙页面队列头，队列尾链接*/ for(i=0;i
{
if(pl[page[i]].pfn==INVALID) /*页面失效*/
{
diseffect+=1; /*失效次数*/
if(freepf_head==NULL) /*无空闲页面*/
{
p=busypf_head->next;
pl[busypf_head->pn].pfn=INVALID;
freepf_head=busypf_head; /*释放忙页面队列的第一个页面*/
freepf_head->next=NULL; /*表明还是缺页*/
busypf_head=p;
}
p=freepf_head->next;
freepf_head->pn=page[i];
pl[page[i]].pfn=freepf_head->pfn;
freepf_head->next=NULL; /*使busy 的尾为null*/
if(busypf_tail==NULL)
{
busypf_tail=busypf_head=freepf_head;
}
else
{
busypf_tail->next=freepf_head;
busypf_tail=freepf_head;
}
freepf_head=p;
}
}
printf("FIFO:%6.4f\n",1-(float)diseffect/320);
return 0;
int LRU (int total_pf) /*最近最久未使用算法least recently used*/ {
int min,minj,i,j,present_time; /*minj为最小值下标*/
initialize(total_pf);
present_time=0;
for(i=0;i
{
if(pl[page[i]].pfn==INVALID) /*页面失效*/ {
diseffect++;
if(freepf_head==NULL) /*无空闲页面*/ {
min=32767; /*设置最大值*/
for(j=0;j
{
if(min>pl[j].time&&pl[j].pfn!=INVALID)
{
min=pl[j].time;
minj=j;
}
}
freepf_head=&pfc[pl[minj].pfn]; //腾出一个单元 pl[minj].pfn=INVALID;
pl[minj].time=0;
freepf_head->next=NULL;
}
pl[page[i]].pfn=freepf_head->pfn; //有空闲页面, 改为有效 pl[page[i]].time=present_time;
freepf_head=freepf_head->next; //减少一个free 页面 }
else
{
pl[page[i]].time=present_time; //命中则增加该单元的访问次数
present_time++;
}
}
printf("LRU:%6.4f\n",1-(float)diseffect/320);
return 0;
}
int NUR(int total_pf ) /*最近未使用算法Not Used recently count表示*/
{
int i,j,dp,cont_flag,old_dp;
pfc_type *t;
initialize(total_pf);
dp=0;
for(i=0;i
{
if (pl[page[i]].pfn==INVALID) /*页面失效*/
{
diseffect++;
if(freepf_head==NULL) /*无空闲页面*/
{
cont_flag=TRUE;
old_dp=dp;
while(cont_flag)
{
if(pl[dp].counter==0&&pl[dp].pfn!=INVALID)
cont_flag=FALSE;
else
{
dp++;
if(dp==total_vp)
dp=0;
if(dp==old_dp)
for(j=0;j
pl[j].counter=0;
}
}
freepf_head=&pfc[pl[dp].pfn];
pl[dp].pfn=INVALID;
freepf_head->next=NULL;
}
pl[page[i]].pfn=freepf_head->pfn;
freepf_head->pn=page[i];
freepf_head=freepf_head->next;
}
else
pl[page[i]].counter=1;
if(i%clear_period==0)
for(j=0;j
pl[j].counter=0;
}
printf("NUR:%6.4f\n",1-(float)diseffect/320);
return 0;
}
int OPT(int total_pf) /*最佳置换算法*/
{
int i,j, max,maxpage,d,dist[total_vp];
pfc_type *t;
initialize(total_pf);
for(i=0;i
{
if(pl[page[i]].pfn==INVALID) /*页面失效*/ {
diseffect++;
if(freepf_head==NULL) /*无空闲页面*/ {
for(j=0;j
{
if(pl[j].pfn!=INVALID)
dist[j]=32767;
else
dist[j]=0;
}
for(j=0;j
{
if((pl[j].pfn!=INVALID)&&(dist[j]==32767)) {
dist[j]=j;
}
}
max=0;
for(j=0;j
if(max
{
max=dist[j];
maxpage=j;
}
freepf_head=&pfc[pl[maxpage].pfn];
freepf_head->next=NULL;
pl[maxpage].pfn=INVALID;
}
pl[page[i]].pfn=freepf_head->pfn;
freepf_head=freepf_head->next;
}
}
printf("OPT:%6.4f\n",1-(float)diseffect/320);
return 0;
}
/*该算法时根据已知的预测未知的，least frequency Used是最不经常使用置换法*/
int LFU(int total_pf)
{
int i,j,min,minpage;
pfc_type *t;
initialize(total_pf);
for(i=0;i
{
if(pl[page[i]].pfn==INVALID) /*页面失效*/
{
diseffect++;
if(freepf_head==NULL) /*无空闲页面*/
{
min=32767;
/*获取counter 的使用用频率最小的内存*/
for(j=0;j
{
if(min>pl[j].counter&&pl[j].pfn!=INVALID) {
min=pl[j].counter;
minpage=j;
}
}
freepf_head=&pfc[pl[minpage].pfn];
pl[minpage].pfn=INVALID;
pl[minpage].counter=0;
freepf_head->next=NULL;
}
pl[page[i]].pfn=freepf_head->pfn; //有空闲页面, 改为有效 pl[page[i]].counter++;
freepf_head=freepf_head->next; //减少一个free 页面
}
else
{
pl[page[i]].counter;
pl[page[i]].counter=pl[page[i]].counter+1;
}
}
printf("LFU:%6.4f\n",1-(float)diseffect/320);
return 0;
}
5. 程序运行结果
实验运行结果截图：
6．实验分析
从上述结果可知，在内存页面数较少（4~5页）时，五种算法的命中率差别不大，都是30%左右。在内存页面为7~18个页面之间时，5种算法的访内命中率大致在35%~60%之间变化。但是，FIFO 算法与OPT 算法之间的差别一般在6~10个百分点左右。在内存页面为25~32个页面时，由于用户进程的所有指令基本上都已装入内存，使命中率增加，从而算法之间的差别不大。
比较上述5种算法，以OPT 算法的命中率最高，NUR 算法次之，再就是LFU 算法和LRU 算法，其次是FIFO 算法。就本问题，在15页之前，FIFO 的命中率比LRU 的高。
7．时间分配：
8. 参考资料及网站
1、《计算机操作系统》汤子赢等 西安电子科技大学出版社
2、《操作系统教程题解与实验指导》孟静 高等教育出版社 2003年
五．实验心得和体会
通过该课程设计，全面系统的理解了存储构造的一般原理和基本实现方法。把死板的课本知识变得生动有趣，激发了学习的积极性。把学过的计算机操作系统的知识强化，能够把课堂上学的知识通过自己设计的程序表示出来，加深了对理论知识的理解。以前对与计算机操作系统的认识是模糊的，概念上的，现在通过自己动手做实验，从实践上认识了操作系统是如何处理命令的，如何协调计算机内部各个部件运行，对计算机操作系统的认识更加深刻。
这次操作系统的课程设计，让我对实验原理有更深的理解，通过把该算法的内容，算法的执行顺序在计算机上实现，知道和理解了该理论在计算机中是怎样执行的， 对该理论在实践中的应用有深刻的理解。并且这次课程设计把各个学科之间的知识融合起来 ，把各门课程的知识联系起来，对计算机整体的认识更加深刻。