// test_1.cpp : 定义控制台应用程序的入口点。
//
/**************************************************************
*此程序为页面调度程序，用于模拟虚存与主存之间的页面置换
*并同时采用FIFO,LRU,OPT,LFT,NUR几种算法
*并比较在不同算法下及不同的主存页面状态下，主存的命中率的高低
**************************************************************
*/
#include "stdlib.h"
#include "stdio.h"
#include "time.h"
#define TRUE 1
#define FALSE 0
#define INVALID -1 /*页面失效符*/
#define null 0
#define total_instruction 320 /*指令流长*/
#define total_vp 32 /*虚页长*/
#define clear_period 50 /*清零周期*/
typedef struct{ /*页面结构*/
int pn,pfn,counter,time;
}pl_type;
/*--pn为页面队列号,pfn为页面控制结构中的页号，counter为访问次数--*/
pl_type pl[total_vp]; /*页面结构数组;建立虚存页面空间*/
/*******************************************************
*此程序有两种结构，一种是页面结构，用于页面的实际转换
*即将某一页面的实际参数作改变
*另一种是页面控制结构，用于控制页面的调度
******************************************************/
struct pfc_struct{ /*页面控制结构;主存中的页面调度结构*/
int pn,pfn;
struct pfc_struct *next;
};
typedef struct pfc_struct pfc_type;
/*--p272 c语言书;;用于将定义语句struct pfc_struct 改成 pfc_type--*/
/*--pfc[total_vp]为用户进程虚页控制结构；freepf_head 闲页面头指针；
*--busypf_head 忙页面头指针；busypf_tail 忙页面尾指针*/
pfc_type pfc[total_vp],*freepf_head,*busypf_head,*busypf_tail;
int diseffect,a[total_instruction]; /*定义页面缺失次数diseffect和指令序列表a*/
int page[total_instruction],offset[total_instruction];/*定义每条指令分别在哪一页page[i]以及在此页中的偏移量offset[i]*/
void initialize();
void FIFO();
void LRU();
void OPT();
void LFU();
void NUR();
void initialize(int total_pf) /*初始化相关数据;total_pf 用户进程的内存页面数 */
{ int i;
diseffect=0;
for (i=0;i<total_vp;i++) /*虚存页面设初值*/
{ pl[i].pn=i;
pl[i].pfn=INVALID; /*置页面控制结构中的页号，页面为空*/
pl[i].counter=0;
pl[i].time=-1; /*页面控制结构中的访问次数为0，时间为-1*/
}
for (i=1;i<total_pf;i++) /*主存页面设初值*/
{ pfc[i-1].next=&pfc[i];
pfc[i-1].pfn=i-1; /*建立pfc[i-1]和pfc[i]之间的链接*/
}
pfc[total_pf-1].next=NULL;
pfc[total_pf-1].pfn=total_pf-1;
freepf_head=&pfc[0]; /*空页面队列的头指针为pfc[0]*/
}
void FIFO(int total_pf) /*FIFO(First In First Out) ALGORITHM*/
{
/*该算法中freepf_head用于指示主存页面中空闲页面的头位置,而并没有创建新的队列
*同样,busypf_head及busypf_tail也没有创建新的队列,而是用于指示主存结构中忙页面的头尾
*而且由于是纯算法,所以并没有考虑页面自己消掉的可能性,而纯粹由调度结构控制
*因此,当页面满后,只有命中不命中目标,只有当释放页面时,会暂时性地产生一个free页面
*/
int i,j;
pfc_type *p,*t;
initialize(total_pf); /*利用子程序初始化相关页面控制用数据结构*/
busypf_head=busypf_tail=NULL; /*忙页面队列头，队列尾链接*/
for (i=0;i<total_instruction;i++)
{
/*通过查看虚存中页面的pfn是否为INVALID来判断该页面是否在主存中
*若则应存在一个值
*/
if (pl[page[i]].pfn==INVALID) /*页面失效*/
{ diseffect++; /*失效次数*/
if (freepf_head==NULL) /*无空闲页面*/
{ p=busypf_head->next;
pl[busypf_head->pn].pfn=INVALID; /*将释放出的页面的pfn改为INVALID*/
freepf_head=busypf_head; /*释放忙页面队列中的第一个页面*/
freepf_head->next=NULL; /*因为只有一个空闲页面,所以next必为NULL*/
busypf_head=p; /*忙页面头指向下一个*/
}
p=freepf_head->next; /*按FIFO方式调新页面入内存页面*/
freepf_head->next=NULL; /*当前空闲页面将被占用,因此其next必为NULL*/
freepf_head->pn=page[i]; /*这里的freepf_head指的是当前将被占用的页面*/
pl[page[i]].pfn=freepf_head->pfn; /*仅仅是存放一个值而已,用以区分页面不在主存中的INVALID*/
if (busypf_tail==NULL)
busypf_head=busypf_tail=freepf_head;/*当主存页面为空的情况下,处理尾部*/
else
{ busypf_tail->next=freepf_head;
busypf_tail=freepf_head;
}
freepf_head=p; /*空闲页面指向下一个*/
}
}
printf("FIFO:%6.4f---",1-(float)diseffect/320);
}
void LRU(int total_pf) /*LRU(Last Recently Used) ALGORITHM */
/*此处LRU算法并未用到pfc队列
*而是用是否为INVALID来判断该页面是否被载入内存
*若未被载入内存,则被载入,同时在有空闲页面的情况下将freepf_head指向下一个
*若没有空闲页面,则在pl[page[i]].pfn!=INVALID的页中选出时间最小的,将之替换出去
*/
{ int min,minj,i,j,present_time;
initialize(total_pf);
present_time=0;
for (i=0;i<total_instruction;i++)
{
if (pl[page[i]].pfn==INVALID) /*页面失效*/
{ diseffect++; /*失效次数*/
if (freepf_head==NULL) /*无空闲页面*/
{ min=32767;
/*找出主存中时间最小的页面*/
for(j=0;j<total_vp;j++)
{
if(pl[j].pfn!=INVALID&&min>pl[j].time) //在pl中的页面凡是标注有值的均是在主存中的页面！！
{ min=pl[j].time;
minj=j;
}
}
/*freepf_head=&pfc[pfc[minj].pfn];*/ //！！！！错误！minj取值会大于total_pf
pl[minj].pfn=INVALID;
pl[minj].time=-1;
pl[page[i]].pfn=page[i]; //为了表示命中,换入的页面的pfn值应不为INVALID
}
else //有空闲页面时,首先将新页面填入,然后freepf_head指向下一个
{
pl[page[i]].pfn=page[i]; //标志此页面被载入内存
freepf_head=freepf_head->next; //freepf_head指向下一个
}
}
else
{pl[page[i]].time=present_time; /*页面有效则将命中的页面的time增大，以确保不被最先置换*/
}
present_time++;
}
printf("LRU:%6.4f---",1-(float)diseffect/320);
}
void NUR(int total_pf) /*NUR最近不经常使用算法 ALGORITHM */
{ int i,j,dp,cont_flag,old_dp;
pfc_type *t;
initialize(total_pf);
dp=0;
for (i=0;i<total_instruction;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<total_vp;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=freepf_head->next;
}
else
pl[page[i]].counter=1;
if(i%clear_period==0)
for(j=0;j<total_vp;j++) pl[j].counter=0;
}
printf("NRU:%6.4f",1-(float)diseffect/320);
}
void LFU(int total_pf) /*LFU(Leat Frequently Used) ALGORITHM */
{ int i,j,min,minpage;
pfc_type *t;
initialize(total_pf);
for (i=0;i<total_instruction;i++)
{
if (pl[page[i]].pfn==INVALID) /*页面失效*/
{ diseffect++; /*失效次数*/
if (freepf_head==NULL) /*无空闲页面*/
{ min=32767;
for(j=0;j<total_vp;j++)
{if(min>pl[j].counter&&pl[j].pfn!=INVALID)
{ min=pl[j].counter;
minpage=j;
}
pl[j].counter=0;
}
freepf_head=&pfc[pfc[minpage].pfn];
pl[minpage].pfn=INVALID;
freepf_head->next=NULL;
}
pl[page[i]].pfn=freepf_head->pfn;
freepf_head=freepf_head->next;
}
else
pl[page[i]].counter++;
}
printf("LFU:%6.4f---",1-(float)diseffect/320);
}
void OPT(int total_pf) /*OPT(Optimal Replacement) ALGORITHM*/
{ int i,j,max,maxpage,d,dist[total_vp];
p
yuandaima.rar （1个子文件） 
yuandaima.CPP 10KB资源评论
邓凌佳
- 粉丝: 76
- 资源: 1万+
