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

1、實驗五：頁面調(diào)度算法模擬實驗學(xué)時：2學(xué)時一、 實驗?zāi)康?、熟悉操作系統(tǒng)頁面調(diào)度算法2、編寫程序模擬先進(jìn)先出、LRU等頁面調(diào)度算法，體會頁面調(diào)度算法原理二、實驗基本原理1、頁面的含義：分頁存儲管理將一個進(jìn)程的邏輯地址空間分成若干大小相等的片，稱為頁面或頁。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_Replacement Algorithms)。3、置換算

2、法一個好的頁面置換算法，應(yīng)具有較低的頁面更換頻率。從理論上講，應(yīng)將那些以后不再會訪問的頁面換出，或?qū)⒛切┰谳^長時間內(nèi)不會再訪問的頁面調(diào)出。常見置換算法：最佳置換算法(Optimal)：它是由Belady于1966年提出的一種理論上的算法。其所選擇的被淘汰頁面，將是以后永不使用的或許是在最長(未來)時間內(nèi)不再被訪問的頁面。采用最佳置換算法，通常可保證獲得最低的缺頁率。但由于人目前還無法預(yù)知一個進(jìn)程在內(nèi)存的若干個頁面中，哪一個頁面是未來最長時間內(nèi)不再被訪問的，因而該算法是無法實現(xiàn)的，便可以利用此算法來評價其它算法。 先進(jìn)先出(FIFO)頁面置換算法：這是最早出現(xiàn)的置換算法。該算法總是淘汰最先進(jìn)入內(nèi)

3、存的頁面，即選擇在內(nèi)存中駐留時間最久的頁面予以淘汰。該算法實現(xiàn)簡單只需把一個進(jìn)程已調(diào)入內(nèi)存的頁面，按先后次序鏈接成一個隊列，并設(shè)置一個指針，稱為替換指針，使它總是指向最老的頁面。 LRU置換算法：LRU置換算法是選擇最近最久未使用的頁面予以淘汰。 二、 實驗參考程序先進(jìn)先出頁面調(diào)度算法模擬/*-程序說明：1、main函數(shù)在調(diào)用時會先產(chǎn)生一串隨機(jī)數(shù)列，并存放在listN中；2、然后mian函數(shù)調(diào)用IsInBuf函數(shù)，把當(dāng)前讀到的單詞x和bufi中的內(nèi)容進(jìn)行比較。如果x在buf中，則返回其位置j;如果x不在buf中，則返回-1。3、當(dāng)x在buf中的時候，不發(fā)生缺頁中斷。并且開始讀list中的下一個

4、單詞； 當(dāng)x不在buf中的時候，發(fā)生缺頁中斷，輸出被淘汰的頁面的內(nèi)容bufi。把listi放到bufold中，并且old開始循環(huán)指向下一個buf的位置。FIFO算法說明：1、把數(shù)列中的數(shù)字依次放入內(nèi)存中；2、數(shù)字的存放是按照先進(jìn)先出的方式，即循環(huán)存儲?？梢杂胦ld=(old+1)%(int)B來實現(xiàn)。-*/#include <stdio.h>#include <stdlib.h>/#include <conio.h>#include <time.h>#define N 10/*隨機(jī)數(shù)列的長度*/#define B 3/*內(nèi)存頁面數(shù)*/*-函數(shù)名：

5、IsInBuf()功能：返回某個數(shù)x有沒有在Buf中，若在，返回其位置；若不在，則返回-1-*/int IsInBuf(int buf,int x)int i,j=-1;for(i=0;i<B;i+)if(bufi=x)/*當(dāng)x在buf中，返回其位置*/j=i;break;else if(bufi=-1)/*當(dāng)x不在buf中，且bufi為空，則把x填入buf，并返回其位置*/bufi=x;j=i;break;return j;/*-函數(shù)名：main功能：、隨機(jī)產(chǎn)生list中的數(shù)字、頁面中斷次數(shù)的打印、退出程序-*/main()int listN;int bufB,i,fN,j;int o

6、ld=0;int change=0;/*生成隨機(jī)數(shù)，并且初始化*/srand(int)time(NULL);for(i=0;i<B;i+)bufi=fi=-1;printf("n*");printf("nThe Random List:");for(i=0;i<N;i+)listi=(int) rand()%10;printf("%2d",listi);printf("n*");/*顯示淘汰頁面的序列*/printf("nn");printf("nthe lost in FIFO:");change=0;/*中斷的次數(shù)*/for(i=0;i<N;i+)j=IsInBuf(buf,listi);if(j=-1)/*若中沒有則直接插入*/printf(" %2d",bufold);bufold=listi;old=(old+1)%(int)B;/*數(shù)據(jù)在中的儲存是循環(huán)的*/change+;elseprintf(&qu