操作系統(tǒng)課程實驗報告編程模擬頁面置換算法

湖南師范大學樹達學院操作系統(tǒng)課程實驗報告題目編程模擬頁面置換算法理工系09級電子商務專業(yè)姓名學號指導教師張楚才2011年

實驗題目：編程模擬頁面置換算法實驗要求：利用C語言分別實現(xiàn)先進先出置換算法FIFO、最佳置換算法OPT、最近最久未使用置換算法LRU。要求在任意給定的頁面訪問序列和內(nèi)存的物理塊數(shù)下，輸出每種算法下的缺頁率。例如，假定系統(tǒng)為某進程分配了3個物理塊，進程運行時的頁面走向為7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1，開始時3個物理塊均為空，分別求出每種算法下的缺頁率。#include<stdio.h>voidPrint(intbc[],intblockCount){for(inti=0;i<blockCount;i++){printf("%d",bc[i]);}printf("\n");}boolTravel(intbc[],intblockCount,intx){boolis_found=false;inti;for(i=0;i<blockCount;i++){if(bc[i]==x){is_found=true;break;}}returnis_found;}voidFIFO(intpc[],intbc[],intpageCount,intblockCount){printf("0：FIFO置換算法\n");inti;if(pageCount<=blockCount){printf("缺頁次數(shù)為0\n");printf("缺頁率為0\n");}else{intnoPage=0;intp=0;for(i=0;i<pageCount;i++){//printf("引用頁：%d\n",pc[i]);if(!Travel(bc,blockCount,pc[i])){if(i<blockCount){bc[i]=pc[i];}else{if(p==blockCount){p=0;}bc[p]=pc[i];p++;}noPage++;//printf("物理塊情況：\n");//Print(bc,blockCount);}//printf("\n");}printf("FIFO缺頁次數(shù)為:%d\n",noPage);printf("FIFO缺頁率為:%.2f%%\n",(float)noPage/pageCount*100);}}intFoundMaxNum(inta[],intn){intk,j;k=a[0];j=0;for(inti=0;i<n;i++){if(a[i]>=k){k=a[i];j=i;}}returnj;}voidLRU(intpc[],intbc[],intpageCount,intblockCount){printf("1：LRU置換算法\n");if(pageCount<=blockCount){printf("缺頁次數(shù)為0\n");printf("缺頁率為0\n");}else{intnoPage=0;inti,j,m;intbc1[100];for(i=0;i<blockCount;i++){bc1[i]=0;}for(i=0;i<pageCount;i++){//printf("引用頁：%d\n",pc[i]);if(!Travel(bc,blockCount,pc[i])){if(i<blockCount){bc[i]=pc[i];for(intp=0;p<=i;p++){bc1[p]++;}}else{for(j=0;j<blockCount;j++){bc1[j]++;}intk=FoundMaxNum(bc1,blockCount);bc[k]=pc[i];bc1[k]=1;}noPage++;//printf("物理快情況：\n");//Print(bc,blockCount);}elseif(Travel(bc,blockCount,pc[i])){if(i<blockCount){for(j=0;j<=i;j++){bc1[j]++;}for(m=0;m<=i;m++){if(bc[m]==pc[i]){break;}}bc1[m]=1;bc[m]=pc[i];}else{for(j=0;j<blockCount;j++){bc1[j]++;}for(m=0;m<blockCount;m++){if(bc[m]==pc[i]){break;}}bc1[m]=1;bc[m]=pc[i];}}//printf("\n");}printf("LRU缺頁次數(shù)為:%d\n",noPage);printf("LRU缺頁率為:%.2f%%\n",(float)noPage/pageCount*100);}}voidOptiomal(intpc[],intbc[],intpageCount,intblockCount){printf("2：最佳置換算法\n");if(pageCount<=blockCount){printf("缺頁次數(shù)為0\n");printf("缺頁率為0\n");}else{intnoPage=0;inti,j,k;for(i=0;i<pageCount;i++){//printf("引用頁：%d\n",pc[i]);if(!Travel(bc,blockCount,pc[i])){if(i<blockCount){bc[i]=pc[i];}else{intmax=0;intblockIndex;;for(j=0;j<blockCount;j++){for(k=i;k<pageCount;k++){if(bc[j]==pc[k]){break;}}if(k>=max){max=k;blockIndex=j;}}bc[blockIndex]=pc[i];}noPage++;//printf("物理快情況：\n");//Print(bc,blockCount);}//printf("\n");}