實驗五：頁面調(diào)度算法模擬實驗報告

23/23《計算機(jī)操作系統(tǒng)》實驗報告實驗五：頁面調(diào)度算法模擬學(xué)校：╳╳╳院系：╳╳╳班級：╳╳╳某：╳╳╳學(xué)號：╳╳╳指導(dǎo)教師：╳╳╳目錄TOC\o"1-3"\h\u18510一、實驗題目319322二、實驗學(xué)時325689三、指導(dǎo)老師32309四、實驗日期32522五、實驗?zāi)康?17597六、實驗原理3322856.1頁面的含義3279886.2頁面置換算法的含義33406.3置換算法3177506.3.1最佳置換算法(Optimal)3190656.3.2先進(jìn)先出(FIFO)頁面置換算法351296.3.3LRU置換算法41827七、實驗步驟及結(jié)果4282617.1驗證最佳置換算法4100197.1.1實驗截圖4247777.1.2實驗分析4148217.2驗證先進(jìn)先出(FIFO)頁面置換算法5182627.2.1實驗截圖550907.2.2實驗分析5210127.3驗證LRU置換算法6257727.3.1實驗截圖6233737.3.2實驗分析627227八、報告書寫人610697附錄一最佳置換算法(Optimal)75479附錄二先進(jìn)先出(FIFO)頁面置換算法1017864附錄三LRU置換算法13實驗五：頁面調(diào)度算法模擬一、實驗題目頁面調(diào)度算法模擬二、實驗學(xué)時2學(xué)時三、指導(dǎo)老師╳╳╳四、實驗日期2018年12月10日星期一五、實驗?zāi)康?1)熟悉操作系統(tǒng)頁面調(diào)度算法(2)編寫程序模擬先進(jìn)先出、LRU等頁面調(diào)度算法，體會頁面調(diào)度算法原理六、實驗原理6.1頁面的含義分頁存儲管理將一個進(jìn)程的邏輯地址空間分成若干大小相等的片，稱為頁面或頁。6.2頁面置換算法的含義在進(jìn)程運行過程中，若其所要訪問的頁面不在內(nèi)存而需把它們調(diào)入內(nèi)存，但內(nèi)存已無空閑空間時，為了保證該進(jìn)程能正常運行，系統(tǒng)必須從內(nèi)存中調(diào)出一頁程序或數(shù)據(jù)，送磁盤的對換區(qū)中。但應(yīng)將哪個頁面調(diào)出，須根據(jù)一定的算法來確定。通常，把選擇換出頁面的算法稱為頁面置換算法(Page_ReplacementAlgorithms)。6.3置換算法一個好的頁面置換算法，應(yīng)具有較低的頁面更換頻率。從理論上講，應(yīng)將那些以后不再會訪問的頁面換出，或?qū)⒛切┰谳^長時間內(nèi)不會再訪問的頁面調(diào)出。6.3.1最佳置換算法(Optimal)它是由Belady于1966年提出的一種理論上的算法。其所選擇的被淘汰頁面，將是以后永不使用的或許是在最長(未來)時間內(nèi)不再被訪問的頁面。采用最佳置換算法，通常可保證獲得最低的缺頁率。但由于人目前還無法預(yù)知一個進(jìn)程在內(nèi)存的若干個頁面中，哪一個頁面是未來最長時間內(nèi)不再被訪問的，因而該算法是無法實現(xiàn)的，便可以利用此算法來評價其它算法。6.3.2先進(jìn)先出(FIFO)頁面置換算法這是最早出現(xiàn)的置換算法。該算法總是淘汰最先進(jìn)入內(nèi)存的頁面，即選擇在內(nèi)存中駐留時間最久的頁面予以淘汰。該算法實現(xiàn)簡單只需把一個進(jìn)程已調(diào)入內(nèi)存的頁面，按先后次序成一個隊列，并設(shè)置一個指針，稱為替換指針，使它總是指向最老的頁面。6.3.3LRU置換算法LRU置換算法是選擇最近最久未使用的頁面予以淘汰。七、實驗步驟及結(jié)果7.1驗證最佳置換算法7.1.1實驗截圖7.1.2實驗分析in727710440804b1777744b222228b31111b4000out727.2驗證先進(jìn)先出(FIFO)頁面置換算法7.2.1實驗截圖7.2.2實驗分析in103380812056b11111222b2000055b333336b48888out1037.3驗證LRU置換算法7.3.1實驗截圖7.3.2實驗分析in968773712670b1999933366b266661110b38888222b4777777out96831八、報告書寫人╳╳╳附錄一最佳置換算法(Optimal)#include<stdio.h>#include<stdlib.h>#include<time.h>#defineN12/*隨機(jī)數(shù)列的長度*/#defineB4/*內(nèi)存頁面數(shù)*/intIsInBuf(intbuf[],intlist[],intnum){inti,j=-1;intmax_p;intmax_d=0;for(i=0;i<B;i++){if(buf[i]==list[num])//當(dāng)x在buf中，返回-1return-1;elseif(buf[i]==-1)//當(dāng)x不在buf中，且buf[i]為空，則把x填入buf，并返回-1{buf[i]=list[num];return-2;}}for(i=0;i<B;i++){for(j=num+1;j<N;j++){if(buf[i]==list[j]){if(max_d<j){max_d=j;//buf[i]在list[]中的最近距離max_p=i;//list[j]在buf[]的位置}break;}}if(j==N)//如果buf滿，并且buf[i]不在list[]的后半部分，返回位置ireturni;}returnmax_p;//返回距離最遠(yuǎn)的buf[]的位置}intmain(){intlist[N];//={4,3,2,1,4,3,5,4,3,2,1,5};intbuf[B],i,f[N],j,m,bufuse=0,tmp;intchange=0;//置換次數(shù)intinterrupt=0;//中斷次數(shù)intsuccessfully=0;//訪問成功次數(shù)srand((int)time(NULL));for(i=0;i<B;i++)buf[i]=f[i]=-1;printf("\n\n");printf("TheOptimalList:");for(i=0;i<N;i++){list[i]=(int)rand()%10;printf("%2d",list[i]);}printf("\n");printf("\nthelostinOptimal:\n");for(i=0;i<N;i++){j=IsInBuf(buf,list,i);if(j==-1){successfully++;for(m=0;m<=B;m++){printf("");/*成功的打印*/}printf("in<--%dsuccessfully\n",list[i]);/*成功的打印*/}elseif(j==-2){bufuse++;interrupt++;printf("newbuf=");for(m=0;m<bufuse;m++){printf("%d",buf[m]);/*缺頁中斷次數(shù)的打印*/}for(m;m<B;m++){printf("");/*缺頁中斷的打印*/}printf("in<--%dinterrupt\n",list[i]);/*缺頁中斷的打印*/}else{tmp=buf[j];buf[j]=list[i];change++;printf("newbuf=");for(m=0;m<bufuse;m++){printf("%d",buf[m]);/*缺頁置換的打印*/}for(m;m<B;m++){printf("");/*缺頁置換的打印*/}printf("in<--%dchange%d-->out\n",list[i],tmp);/*缺頁置換的打印*/}}printf("\n\n");printf("interrupt=%d\n",interrupt);printf("change=%d\n",change);printf("successfully=%d\n",successfully);return0;}附錄二先進(jìn)先出(FIFO)頁面置換算法#include<stdio.h>#include<stdlib.h>#include<time.h>#defineN12/*隨機(jī)數(shù)列的長度*/#defineB4/*內(nèi)存頁面數(shù)*/intIsInBuf(intbuf[],intx){inti;for(i=0;i<B;i++){if(buf[i]==x)/*當(dāng)x在buf中，返回其位置*/return-1;elseif(buf[i]==-1)/*當(dāng)x不在buf中，且buf[i]為空，則把x填入buf，并返回其位置*/{buf[i]=x;return-2;}}return0;}intmain(){intlist[N];//={4,3,2,1,4,3,5,4,3,2,1,5};intbuf[B],i,f[N],j,m,bufuse=0,tmp;intold=0;intchange=0;//置換次數(shù)intinterrupt=0;//中斷次數(shù)intsuccessfully=0;//訪問成功次數(shù)srand((int)time(NULL));for(i=0;i<B;i++)buf[i]=f[i]=-1;printf("\n\n");printf("TheFIFOList:");for(i=0;i<N;i++){list[i]=(int)rand()%10;printf("%2d",list[i]);}printf("\n");printf("\nthelostinFIFO:\n");for(i=0;i<N;i++){j=IsInBuf(buf,list[i]);if(j==-1){successfully++;for(m=0;m<=B;m++){printf("");/*成功的打印*/}printf("in<--%dsuccessfully\n",list[i]);/*成功的打印*/}elseif(j==-2){bufuse++;interrupt++;printf("newbuf=");for(m=0;m<bufuse;m++){printf("%d",buf[m]);/*缺頁中斷次數(shù)的打印*/}for(m;m<B;m++){printf("");/*缺頁中斷的打印*/}printf("in<--%dinterrupt\n",list[i]);/*缺頁中斷的打印*/}else{tmp=buf[old];buf[old]=list[i];old=(old+1)%(int)B;/*數(shù)據(jù)在ｂｕｆ中的儲存是循環(huán)的*/change++;printf("newbuf=");for(m=0;m<bufuse;m++){printf("%d",buf[m]);/*缺頁置換的打印*/}for(m;m<B;m++){printf("");/*缺頁置換的打印*/}printf("in<--%dchange%d-->out\n",list[i],tmp);/*缺頁置換的打印*/}}printf("\n\n");printf("interrupt=%d\n",interrupt);printf("change=%d\n",change);printf("successfully=%d\n",successfully);return0;}附錄三LRU置換算法#include<stdio.h>#include<stdlib.h>#include<time.h>#defineN12/*隨機(jī)數(shù)列的長度*/#defineB4/*內(nèi)存頁面數(shù)*/intIsInBuf(intbuf[],intlist[],intnum){inti,j=-1;for(i=0;i<B;i++){if(buf[i]==list[num])/*當(dāng)x在buf中，返回其位置*/{j=i;break;}elseif(buf[i]==-1)/*當(dāng)x不在buf中，且buf[i]為空，則把x填入buf，并返回其位置*/{buf[i]=list[num];j=-2;break;}}returnj;}intGet(intbuf[],intlist[],intnum){intbuff[B];intbuffuse=0;inti,j,k,m;for(m=0;m<B;m++)buff[m]=-1;for(i=num-1;i>=0;i--){for(j=0;j<B;j++){if(list[i]==buf[j]){for(k=0;k<buffuse;k++){if(list[i]==buff[k])break;}if(k==buffuse){buff[buffuse]=list[i];buffuse++;if(buffuse==B)returnj;}break;}}}return0;}intmain(){intlist[N];//intlist[12]=intbuf[B],i,f[N],j,m,bufuse=0,tmp;intold=0;intchange=0;intinterrupt=0;intsuccessfully=0;srand((int)time(NULL));for(i=0;i<B;i++)buf[i]=f[i]=-1;printf("TheRandomList:");for(i=0;i<N;i++){list[i]=(int)rand()%10;printf("%2d",list[i]);}printf("\n\n");printf("\nthelostinLRU:\n");change=0;/*中斷的次數(shù)*/for(i=0;i<N;i++)