實(shí)驗(yàn)五：頁(yè)面調(diào)度算法模擬實(shí)驗(yàn)報(bào)告

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