yuandaima.rar_LFU_LFU NUR _OPT_OPT FIFO LRU LFU

// 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