C語言實現頁面置換算法(FIFO、LRU)
1.實現效果
2.實現源代碼
#include<iostream> #include<process.h> #include<stdlib.h> #include<ctime> #include<conio.h> #include<stdio.h> #include<string.h> using namespace std; #define Myprintf printf("|---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---|\n")/*表格控制*/ #define bsize 4 //物理塊大小 #define psize 16 //進程大小 void chushihua();//初始化函數 void ymzh(); void yemianzhihuan (); void changeaddr(struct Page p[], int logaddr); void dizhizhuanhuan(); void menu(); int wang(); int yemianliu[32]={0};//全局變量數組,地址流 int p; struct Page { int pno;//頁號 int flag;//標志位 int cno;//主存號 int modf;//修改位 int addr;//外存地址 }Page; //全局變量p是一共有多少地址流 typedef struct pagel { int num; /*記錄頁面號*/ int time; /*記錄調入內存時間*/ }Pagel; /*頁面邏輯結構,方便算法實現*/ Pagel b[bsize]; /*內存單元數*/ int c[bsize][psize];/*保存內存當前的狀態:緩沖區*/ int queue[100];/*記錄調入隊列*/ int k;/*調入隊列計數變量*/ int phb[bsize]={0};//物理塊標號 int pro[psize]={0};//進程序列號 int flag[bsize]={0};//進程等待次數(存放最久未被使用的進程標志)*/ int i=0,j=0;//i表示進程序列號,j表示物理塊號*/ int m =-1,n =-1;//物理塊空閑和進程是否相同判斷標志*/ int mmax=-1, maxflag=0;//標記替換物理塊進程下標*/ int count =0; //統計頁面缺頁次數 void chushihua() //初始化函數 { int t; srand(time(0));//隨機產生指令序列 p=12+rand()%32; cout<<"地址流序列:"; cout<<endl; for(i=0; i<p; i++) { t=1+rand()%9; yemianliu[i]=t;//將隨機產生的指令數存入頁面流 } for (i=p-1;i>=0;i--) { cout<<yemianliu[i]<<" "; } cout<<endl; } void ymzh() { chushihua(); yemianzhihuan(); } void yemianzhihuan() { int a; printf("----------------------------------\n"); printf("☆☆歡迎使用分頁模擬實驗系統☆☆\n"); printf("----------------------------------"); printf("☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆\n"); printf("☆☆1.進入硬件地址變換算法 ☆☆\n"); printf("☆☆------------------------☆☆\n"); printf("☆☆2.進入頁面置換算法 ☆☆\n"); printf("☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆\n"); printf("請輸入您的選擇:"); switch(a) { case 1: ymzh(); break; case 2: wang(); break; default: cout<<"輸入有誤,請重新輸入!"<<endl; break; } } void changeaddr(struct Page p[], int logaddr){//地址變換 int j=logaddr/64;//對應的塊號 int k=logaddr%64; //對應的偏移量 int flag=0; int addr; for(int i=0;i<8;i++) { if(p[i].pno==j)//找到對應的頁號 { if(p[i].flag==1)//頁面標志為1 { addr=p[i].cno*64+k; cout<<"物理地址為:"<<addr<<endl; cout<<"詳細信息:"<<"\t頁面號:"<<p[i].pno<<"\t 主存號:"<<p[i].cno<<"\t偏移量:"<<k<<endl; flag=1; break; } } } if(flag==0) cout<<"該頁不在主存,產生缺頁中斷"<<endl; } void dizhizhuanhuan() { int a; int ins;//指令邏輯地址 struct Page p[8]; p[0].pno=0;p[0].flag=1;p[0].cno=5;p[0].modf=1;p[0].addr=011; p[1].pno=1;p[1].flag=1;p[1].cno=8;p[1].modf=1;p[1].addr=012; p[2].pno=2;p[2].flag=1;p[2].cno=9;p[2].modf=0;p[2].addr=013; p[3].pno=3;p[3].flag=1;p[3].cno=10;p[3].modf=0;p[3].addr=015; p[4].pno=4;p[4].flag=0;p[4].addr=017; p[5].pno=5;p[5].flag=0;p[5].addr=025; p[6].pno=6;p[6].flag=0;p[6].addr=212; p[7].pno=7;p[7].flag=0;p[7].addr=213; printf("\t\t\t--------------------------------\n"); printf("\t\t\t☆☆歡迎使用分頁模擬實驗系統☆☆\n"); printf("\t\t\t---------------------------------\n"); printf("\t\t\t☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆\n"); printf("\t\t\t☆☆1.輸入指令 ☆☆\n"); printf("\t\t\t☆☆------------------------☆☆\n"); printf("\t\t\t☆☆2.進入頁面置換算法 ☆☆\n"); printf("\t\t\t☆☆------------------------☆☆\n"); printf("\t\t\t☆☆0.EXIT ☆☆\n"); printf("\t\t\t☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆\n"); while(a!=0) { cout<<endl<<"請輸入您的選擇:"; cin>>a; cout<<"頁號"<<"標記位"<<"外存地址"<<"主存號"<<endl; for(int i=0;i<8;i++) { cout<<p[i].pno<<"\t"<<p[i].flag<<"\t"<<p[i].addr<<"\t"; if(p[i].flag) cout<<p[i].cno; cout<<endl; } switch(a) { case 0:printf("\t\t\t再見!\t\t\t\n"); break; case 1: cout<<"請輸入指令的邏輯地址:"; cin>>ins; changeaddr(p, ins);break; case 2: system("CLS"); a=wang();break; default:cout<<"輸入有誤,請重新輸入!"<<endl;break; } } } void menu() { int a; printf("\t\t\t--------------------------------\n"); printf("\t\t\t☆☆歡迎使用分頁模擬實驗系統☆☆\n"); printf("\t\t\t---------------------------------\n"); printf("\t\t\t☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆\n"); printf("\t\t\t☆☆1.輸入指令 ☆☆\n"); printf("\t\t\t☆☆------------------------☆☆\n"); printf("\t\t\t☆☆2.進入頁面置換算法 ☆☆\n"); printf("\t\t\t☆☆------------------------☆☆\n"); printf("\t\t\t☆☆0.EXIT ☆☆\n"); printf("\t\t\t☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆\n"); printf("請選擇所要執行的操作:"); scanf("%d",&a); switch(a) { case 0: printf("\t\t\t-再見!-\t\t\t\n");break; case 1: dizhizhuanhuan (); break; case 2: wang (); break; default:cout<<"輸入有誤,請重新輸入!"<<endl;break; } } int main() { menu(); } //****************隨機產生序列號函數 int* build() { printf("隨機產生一個進程序列號為:\n"); int i=0; for(i=0; i<psize; i++) { pro[i]=10*rand()/(RAND_MAX+1)+1; printf("%d ", pro[i]); } printf("\n"); return(pro); } //***************************************查找空閑物理塊 int searchpb() { for (j=0;j<bsize; j++) { if(phb[j] == 0) { m=j; return m; break; } } return -1; } //************************************查找相同進程 int searchpro() { for(j=0;j< bsize;j++) { if(phb[j] =pro[i]) { n=j; return j; } } return -1; } //*************************初始化內存 void empty() { for(i=0;i<bsize;i++) phb[i]=0; count=0; //計數器置零 } //******先進先出頁面置換算法 void FIFO() { for( i=0; i<psize; i++) { // m=searchpb(); // n=searchpro(); //找到第一個空閑的物理快 for(j=0;j<bsize;j++) { if(phb[j] == 0){ m=j; break; } } //找與進程相同的標號 for(j=0;j<bsize;j++) { if(phb[j] == pro[i]){ n=j; } } //找flag值最大的 for(j=0;j<bsize;j++) { if(flag[j]>maxflag) { maxflag = flag[j]; mmax = j; } } if(n == -1)//不存在相同進程 { if(m != -1)//存在空閑物理塊 { phb[m]=pro[i];//進程號填入該空閑物理塊 // count++; flag[m]=0; for (j=0;j<=m; j++) { flag[j]++; } m=-1; } else//不存在空閑物理塊 { phb[mmax] =pro[i]; flag[mmax] =0; for (j=0;j<bsize;j++) { flag[j]++; } mmax = -1; maxflag = 0; count++; } } else//存在相同的進程 { phb[n] = pro[i]; for(j=0;j<bsize;j++) { flag[j]++; } n=-1; } for(j=0;j < bsize;j++) { printf("%d ", phb[j]); } printf("\n"); } printf("缺頁次數為:%d\n",count); printf("缺頁率 :%16. 6f",(float)count/psize); printf("\n"); } /*初始化內存單元、緩沖區*/ void Init(Pagel *b,int c[bsize][psize]) { int i,j; for (i=0;i<psize;i++) { b[i].num=-1; b[i].time=psize-i-1; } for(i=0;i<bsize;i++) for(j=0;j<psize;j++) c[i][j]=-1; } /*取得在內存中停留最久的頁面,默認狀態下為最早調入的頁面*/ int GetMax(Pagel *b) { int i; int max=-1; int tag=0; for(i=0;i<bsize;i++) { if(b[i].time>max) { max=b[i].time; tag= i; } } return tag; } /*判斷頁面是否已在內存中*/ int Equation(int fold, Pagel *b) { int i; for(i=0;i<bsize;i++) { if(fold==b[i]. num) return i; } return -1; } /*LRU核心部分*/ void Lruu(int fold, Pagel *b) { int i; int val; val=Equation(fold, b); if (val>=0) { b[val].time=0; for(i=0;i<bsize;i++) if (i!=val) b[i].time++; } else { queue[++k]=fold;/*記錄調入頁面*/ val=GetMax(b); b[val].num=fold; b[val].time=0; for (i=0;i<bsize;i++){ // URLcount++; if (i!=val) b[i].time++; } } } void LRU() { int i,j; k=0; Init(b, c); for(i=0; i<psize; i++) { Lruu(pro[i],b); c[0][i]=pro[i]; /*記錄當前的內存單元中的頁面*/ for(j=0;j<bsize;j++) c[j][i]=b[j].num; } /*結果輸出*/ printf("內存狀態為:\n"); Myprintf; for(j=0;j<psize;j++) printf("|%2d", pro[j]); printf("|\n"); Myprintf; for(i=0;i<bsize;i++) { for(j=0; j<psize; j++) { if(c[i][j]==-1) printf("|%2c",32); else printf("|%2d",c[i][j]); } printf("|\n"); } Myprintf; // printf("\n調入隊列為:"); // for(i=0;i<k;i++) // printf("%3d", queue[i]); printf("\n缺頁次數為:%6d\n 缺頁率 :%16. 6f", k+1,(float)(k+1)/psize); } //********主函數 int wang() { int sel; do{ printf("\t\t\t--------------------------------\n"); printf("\t\t\t☆☆歡迎使用分頁模擬實驗系統☆☆\n"); printf("\t\t\t---------------------------------\n"); printf("\t\t\t☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆\n"); printf("\t\t\t☆☆ 虛擬內存 ☆☆\n"); printf("\t\t\t☆☆------------------------☆☆\n"); printf("\t\t\t☆☆1.產生隨機序列 ☆☆\n"); printf("\t\t\t☆☆------------------------☆☆\n"); printf("\t\t\t☆☆2.最近最久未使用 ☆☆\n"); printf("\t\t\t☆☆------------------------☆☆\n"); printf("\t\t\t☆☆3.先進先出 ☆☆\n"); printf("\t\t\t☆☆------------------------☆☆\n"); printf("\t\t\t☆☆0.退出 ☆☆\n"); printf("\t\t\t☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆\n"); printf("請選擇所要執行的操作:"); scanf("%d",&sel); switch(sel) { case 0: printf("\t\t\t再見!t\t\t\n"); break; case 1: build(); break; case 2: printf("最近最久未使用\n"); LRU();empty(); printf("\n");break; case 3: printf("先進先出算法\n"); FIFO();empty();printf("\n");break; default:printf("請輸入正確的選項號!");printf("\n\n");break; } }while(sel !=0 ); return sel; }
到此這篇關於C語言實現頁面置換算法(FIFO、LRU)的文章就介紹到這瞭,更多相關C語言 頁面置換算法內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!