c++实现 存储器管理

#include<stdio.h> #include<stdlib.h> #include<windows.h> #define TRUE 1 #define FALSE 0 #define INVALID -1 //失效 #define NULL 0 #define total_instruction 320 //指令长度 #define total_vp 32 //虚页长 typedef struct //页面结构 { int pn,pfn,counter,time;//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; //*freepf_head为空页面头指针；*busypf_head,*busypf_tail分别为满页面头、尾指针。 int diseffect; //页面失效数 int a[total_instruction]; //指令流数据组 int page[total_instruction]; //每条指令所属页号 int offset[total_instruction]; //每页装入10条指令后取模运算页号偏移值 void initialize(int); void FIFO(int);//先进先出算法 void LRU(int);//最近最少使用算法 void OPT(int);//最佳淘汰算法 void LFR(int);//最少访问页面算法 void main() { int S,i,j; srand(GetTickCount()); S=rand()%319; for(i=0;i<total_instruction;i+=4) //产生指令队列 { a[i]=S; a[i+1]=a[i]+1; a[i+2]=rand()%a[i+1]; a[i+3]=a[i+2]+1; S=a[i+2]+2+rand()%(318-a[i+2]);//产生a-b之间随机数：a + rand() % (b-a+1) 就表示　ａ～ｂ之间的一个随机数 } for(i=0;i<total_instruction;i++) { page[i]=a[i]/10; offset[i]=a[i]%10; } printf("页号/算法 FIFO LRU OPT LFR\n"); printf(" \n"); for(i=4;i<=32;i++) { printf(" %2d : ", i); FIFO(i); LRU(i); OPT(i); LFR(i); printf("\n"); } } void initialize(int 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; } for(i=1;i<total_pf;i++)//连接pfc[i-1]和pfc[i]，形成链表 { pfc[i-1].next=&pfc[i]; pfc[i-1].pfn=i-1; } pfc[total_pf-1].next=NULL; pfc[total_pf-1].pfn=total_pf-1; freepf_head=&pfc[0]; } void FIFO(int total_pf) //total_pf:用户进程的内存页面数 { int i,j; pfc_type *p,*t; initialize(total_pf); busypf_head=busypf_tail=NULL; for(i=0;i<total_instruction;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->next=NULL; freepf_head->pn=page[i]; pl[page[i]].pfn=freepf_head->pfn; if(busypf_tail==NULL) { busypf_head=busypf_tail=freepf_head; } else { busypf_tail->next=freepf_head; busypf_tail=freepf_head; } freepf_head=p; } } printf(" %6.4f ",1-(float)diseffect/320); } void LRU(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==NULL) { 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=NULL; } 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(" %6.4f ",1-(float)diseffect/320); } void OPT(int total_pf) { int i,j,max,maxpage,d,dist[total_vp]; pfc_type *t; initialize(total_pf); for(i=0;i<total_instruction;i++) { if(pl[page[i]].pfn==INVALID) { diseffect++; if(freepf_head==NULL) { for(j=0;j<total_instruction;j++) { if(pl[j].pfn!=INVALID) dist[j]=32767; else dist[j]=0; } d=1; for(j=i+1;j<total_instruction;j++) { if(pl[page[j]].pfn!=INVALID) dist[page[j]]=d; d++; } max=-1; for(j=0;j<total_vp;j++) if(max<dist[j]) { 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(" %6.4f ",1-(float)diseffect/320); } void LFR(int total_pf) { 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[pl[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(" %6.4f ",1-(float)diseffect/320); }