#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#define TRUE 1
#define FALSE 0
#define INVALID -1
#define NUL 0
#define total_instruction 320 /*指令流长*/
#define total_vp 32 /*虚页长*/
#define clear_period 50 /*清零周期*/

typedef struct{ /*页面结构*/
int pn,pfn,counter,time;
}pl_type;
pl_type pl[total_vp]; /*页面结构数组*/
struct pfc_struct{ /*页面控制结构*/
int pn,pfn;
struct pfc_struct *next;
};
typedef struct pfc_struct pfc_type;
pfc_type pfc[total_vp],*freepf_head,*busypf_head,*busypf_tail;
int diseffect,a[total_instruction];
int page[total_instruction], offset[total_instruction];
void initialize();
void FIFO();
void LRU();
void NUR();
int main()
{
int S,i;
srand((int)getpid());

S=(int)rand()%390;

for(i=0;i<total_instruction;i+=1) /*产生指令队列*/
{
a[i]=S; /*任选一指令访问点*/
a[i+1]=a[i]+1; /*顺序执行一条指令*/
a[i+2]=(int)rand()%390; /*执行前地址指令m’*/
a[i+3]=a[i+2]+1; /*执行后地址指令*/
S=(int)rand()%390;
}
for(i=0;i<total_instruction;i++) /*将指令序列变换成页地址流*/
{
page[i]=a[i]/10;
offset[i]=a[i]%10;
}
for(i=4;i<=32;i++) /*用户内存工作区从4个页面到32个页面*/
{
printf("%2d page frames",i);
FIFO(i);
LRU(i);
NUR(i);
printf("\n");
}
return 0;
}
void FIFO(total_pf) /*FIFO(First in First out)ALGORITHM*/
int total_pf; /*用户进程的内存页面数*/
{
int i;
pfc_type *p, *t;
initialize(total_pf); /*初始化相关页面控制用数据结构*/
busypf_head=busypf_tail=NUL; /*忙页面队列头，对列尾链接*/
for(i=0;i<total_instruction;i++)
{
if(pl[page[i]].pfn==INVALID) /*页面失效*/
{
diseffect+=1; /*失效次数*/
if(freepf_head==NUL) /*无空闲页面*/
{
p=busypf_head->next;
pl[busypf_head->pn].pfn=INVALID; /*释放忙页面队列中的第一个页面*/
freepf_head=busypf_head;
freepf_head->next=NUL;
busypf_head=p;
}
p=freepf_head->next; /*按方式调新页面入内存页面*/
freepf_head->next=NUL;
freepf_head->pn=page[i];
pl[page[i]].pfn=freepf_head->pfn;
if(busypf_tail==NUL)
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(total_pf)
int total_pf;
{
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==NUL) /*无空闲页面*/
{
min=32767;
for(j=0;j<total_vp;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=-1;
freepf_head->next=NUL;
}
pl[page[i]].pfn=freepf_head->pfn;
pl[page[i]].time=present_time;
freepf_head=freepf_head->next;
}
else
pl[page[i]].time=present_time;
present_time++;
}
printf("LRU:%6.4f",1-(float)diseffect/320);
}
void NUR(total_pf)
int total_pf;
{
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==NUL) /*无空闲页面*/
{
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=NUL;
}
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("NUR:%6.4f",1-(float)diseffect/320);
}
void initialize(total_pf) /*初始化相关数据结构*/
int total_pf; /*用户进程的内存页面数*/
{
int i;
diseffect=0;

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。