一、 实验目的：
通过模拟页面调度策略，感性认识操作系统对内存的调度管理。
二、 实验工具：
有Linux操作系统的计算机。
三、 预备知识：
FIFO 在内存中被替换出去的页面永远是最优先进入的页面。
四、 实验编程：FIFO调度的策略。
（1） 进入Linux操作系统。
（2） 打开终端，进入vi编辑器。
（3） 输入程序源代码。
（4） 按ESC键进入命令模式，再输入“：wq文件名”后就可以运行程序。
程序源代码：
#define TRUE1
#defineFALSE 0
#defineINVALID -1
#define NULL0
#define total_instruction 320 /*指令流长*/
#definetotal_vp 32 /*虚页长*/
#defineclear_period 50 /*清0周期*/
typedef struct /*页面结构*/
{
intpn,pfn,counter,time;
}
pl_type;
pl_typepl[total_vp]; /*页面结构数组*/
structpfc_struct
{ /*页面控制结构*/
int pn,pfn;
struct pfc_struct *next;
};
typedefstruct pfc_struct pfc_type;
pfc_typepfc[total_vp],*freepf_head,*busypf_head,*busypf_tail;
intdiseffect, a[total_instruction];
intpage[total_instruction], offset[total_instruction];
int initialize(int);
intNUR(int);
int main()
{
int s,i,j;
srand(10*getpid());/*由于每次运行时进程号不同，故可用来作为初始化随机数队列的"种子"*/
s=(float)319*rand()/32767/32767/2+1; //
for(i=0;i<total_instruction;i+=4)/*产生指令队列*/
{
if(s<0||s>319)
{
printf("Wheni==%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 ands==%d\n",i,a[i+2],s);
}
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("---%2dpage frames---\n",i);
NUR(i);
}
return 0;
}
int initialize(total_pf) /*初始化相关数据结构*/
inttotal_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=0;i<total_pf-1;i++)
{
pfc[i].next=&pfc[i+1];
pfc[i].pfn=i;
} /*建立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]*/
return 0;
}
intNUR(total_pf) /*最近未使用算法*/
inttotal_pf;
{inti,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("NUR:%6.4f\n",1-(float)diseffect/320);
return 0;
}
运行后截图：
程序代码所表示的流程图：
一、 心得体会。
是用队列存储内存中的页面，队列的特点是先进先出，与该算法是一致的，所以每当发生缺页时，就从队头删除一页，而从队尾加入缺页。或者借助辅助数组time[mSIZE]记录物理块中对应页面的进入时间，每次需要置换时换出进入时间最小的页面。所以fifo需要进行页面置换，即把内存中装入最早的那个页面淘汰，换入当前的页面。总的来说使用FIFO算法，总是淘汰最先进入内存的页面，即即选择在内存中驻留时间最久的页面予以淘汰。通过这个实验我体会到了编程的思路流程，结构流程图的作用。一个程序如果一开始计划的好，结构设计完善，才可能顺利进行。