計算機操作系統(tǒng)-實驗三頁面置換算法模擬實驗

1、精選優(yōu)質(zhì)文檔-傾情為你奉上淮海工學院計算機工程學院實驗報告書課程名： 操作系統(tǒng)原理A 題 目： 虛擬存儲器管理 頁面置換算法模擬實驗 班 級： Z計121 學 號： 姓 名： 薛慧君 評語：成績： 指導教師： 批閱時間： 年 月 日專心-專注-專業(yè)一、實驗?zāi)康呐c要求1. 目的：請求頁式虛存管理是常用的虛擬存儲管理方案之一。通過請求頁式虛存管理中對頁面置換算法的模擬，有助于理解虛擬存儲技術(shù)的特點，并加深對請求頁式虛存管理的頁面調(diào)度算法的理解。2. 要求：本實驗要求使用C語言編程模擬一個擁有若干個虛頁的進程在給定的若干個實頁中運行、并在缺頁中斷發(fā)生時分別使用FIFO和LRU算法進行頁面置換的情形。

2、其中虛頁的個數(shù)可以事先給定（例如10個），對這些虛頁訪問的頁地址流（其長度可以事先給定，例如20次虛頁訪問）可以由程序隨機產(chǎn)生，也可以事先保存在文件中。要求程序運行時屏幕能顯示出置換過程中的狀態(tài)信息并輸出訪問結(jié)束時的頁面命中率。程序應(yīng)允許通過為該進程分配不同的實頁數(shù)，來比較兩種置換算法的穩(wěn)定性。二、實驗說明1設(shè)計中虛頁和實頁的表示本設(shè)計利用C語言的結(jié)構(gòu)體來描述虛頁和實頁的結(jié)構(gòu)。pnpfntimepnpfnnext 虛頁結(jié)構(gòu) 實頁結(jié)構(gòu)在虛頁結(jié)構(gòu)中，pn代表虛頁號，因為共10個虛頁，所以pn的取值范圍是09。pfn代表實頁號，當一虛頁未裝入實頁時，此項值為-1；當該虛頁已裝入某一實頁時，此項值為所

3、裝入的實頁的實頁號pfn。time項在FIFO算法中不使用，在LRU中用來存放對該虛頁的最近訪問時間。在實頁結(jié)構(gòu)中中，pn代表虛頁號，表示pn所代表的虛頁目前正放在此實頁中。pfn代表實頁號，取值范圍（0n-1）由動態(tài)指派的實頁數(shù)n所決定。next是一個指向?qū)嶍摻Y(jié)構(gòu)體的指針，用于多個實頁以鏈表形式組織起來，關(guān)于實頁鏈表的組織詳見下面第4點。2關(guān)于缺頁次數(shù)的統(tǒng)計為計算命中率，需要統(tǒng)計在20次的虛頁訪問中命中的次數(shù)。為此，程序應(yīng)設(shè)置一個計數(shù)器count，來統(tǒng)計虛頁命中發(fā)生的次數(shù)。每當所訪問的虛頁的pfn項值不為-1，表示此虛頁已被裝入某實頁內(nèi)，此虛頁被命中，count加1。最終命中率=count/

4、20*100%。3LRU算法中“最近最久未用”頁面的確定為了能找到“最近最久未用”的虛頁面，程序中可引入一個時間計數(shù)器countime，每當要訪問一個虛頁面時，countime的值加1，然后將所要訪問的虛頁的time項值設(shè)置為增值后的當前countime值，表示該虛頁的最后一次被訪問時間。當LRU算法需要置換時，從所有已分配實頁的虛頁中找出time值為最小的虛頁就是“最近最久未用”的虛頁面，應(yīng)該將它置換出去。4算法中實頁的組織因為能分配的實頁數(shù)n是在程序運行時由用戶動態(tài)指派的，所以應(yīng)使用鏈表組織動態(tài)產(chǎn)生的多個實頁。為了調(diào)度算法實現(xiàn)的方便，可以考慮引入free和busy兩個鏈表：free鏈表用于

5、組織未分配出去的實頁，首指針為free_head，初始時n個實頁都處于free鏈表中；busy鏈表用于組織已分配出去的實頁，首指針為busy_head，尾指針為busy_tail，初始值都為null。當所要訪問的一個虛頁不在實頁中時，將產(chǎn)生缺頁中斷。此時若free鏈表不為空，就取下鏈表首指針所指的實頁，并分配給該虛頁。若free鏈表為空，則說明n個實頁已全部分配出去，此時應(yīng)進行頁面置換：對于FIFO算法要將busy_head 所指的實頁從busy鏈表中取下，分配給該虛頁，然后再將該實頁插入到busy鏈表尾部；對于LRU算法則要從所有已分配實頁的虛頁中找出time值為最小的虛頁，將該虛頁從裝載它

6、的那個實頁中置換出去，并在該實頁中裝入當前正要訪問的虛頁。三、程序流程圖四、主要程序清單#include <stdio.h> #include <stdlib.h>/*全局變量*/ int mSIZE; /*物理塊數(shù)*/int pSIZE; /*頁面號引用串個數(shù)*/ static int memery10=0;/*物理塊中的頁號*/ static int page100=0; /*頁面號引用串*/ static int temp10010=0; /*輔助數(shù)組*/ /*置換算法函數(shù)*/void FIFO(); void LRU(); void OPT(); /*輔助函數(shù)*

7、/ void print(unsigned int t);void designBy(); void download(); void mDelay(unsigned int Delay); /*主函數(shù)*/ void main() int i,k,code; printf("請輸入物理塊的個數(shù)(M<=10)："); scanf("%d",&mSIZE); printf("請輸入頁面號引用串的個數(shù)(P<=100)："); scanf("%d",&pSIZE); puts("請依次

8、輸入頁面號引用串(連續(xù)輸入，無需隔開)："); for(i=0;i<pSIZE;i+) scanf("%1d",&pagei); download(); do puts("輸入的頁面號引用串為："); for(k=0;k<=(pSIZE-1)/20;k+) for(i=20*k;(i<pSIZE)&&(i<20*(k+1);i+) if(i+1)%20=0)|(i+1)%20)&&(i=pSIZE-1) printf("%dn",pagei); else pri

9、ntf("%d ",pagei); printf("* * * * * * * * * * * * * * * * * * * * * * *n"); printf("* 請選擇頁面置換算法：ttt *n");printf("* -*n"); printf("* 1.先進先出(FIFO) 2.最近最久未使用(LRU) *n"); printf("* 3.退出 *n"); printf("* * * * * * * * * * * * * * * * * * * *

10、* * *n"); printf("請選擇操作： bb"); scanf("%d",&code); switch(code) case 1: FIFO(); break; case 2: LRU(); break; case 3: OPT(); break; case 4: system("cls"); /system("color 0A"); exit(0); default: printf("輸入錯誤，請重新輸入："); printf("按任意鍵重新選擇置換算法：

11、>>>"); getchar(); while (code!=4); getchar(); /*載入數(shù)據(jù)*/ void download() printf("nFinish.n載入成功!"); /*設(shè)置延遲*/ void mDelay(unsigned int Delay) unsigned int i; for(;Delay>0;Delay-) for(i=0;i<124;i+) printf(" b"); /*顯示設(shè)計者信息*/ void print(unsigned int t) int i,j,k,l; i

12、nt flag; for(k=0;k<=(pSIZE-1)/20;k+) for(i=20*k;(i<pSIZE)&&(i<20*(k+1);i+) if(i+1)%20=0)|(i+1)%20)&&(i=pSIZE-1) printf("%dn",pagei); else printf("%d ",pagei); for(j=0;j<mSIZE;j+) for(i=20*k;(i<mSIZE+20*k)&&(i<pSIZE);i+) if(i>=j) printf

13、(" |%d|",tempij); else printf(" | |"); for(i=mSIZE+20*k;(i<pSIZE)&&(i<20*(k+1);i+) for(flag=0,l=0;l<mSIZE;l+) if(tempil=tempi-1l) flag+; if(flag=mSIZE)/*頁面在物理塊中*/ printf(" "); else printf(" |%d|",tempij); /*每行顯示20個*/ if(i%20=0) continue; print

14、f("n"); printf("-n"); printf("缺頁次數(shù)：%dtt",t+mSIZE); printf("缺頁率：%d/%dn",t+mSIZE,pSIZE); printf("置換次數(shù)：%dtt",t); printf("訪問命中率：%d%n",(pSIZE-(t+mSIZE)*100/pSIZE); printf("-n"); /*計算過程延遲*/ void compute() int i; printf("正在進行相關(guān)計算，請稍

15、候"); for(i=0;i+<30;printf("b"); for(i=0;i+<30;printf(" "); for(i=0;i+<30;printf("b"); /*先進先出頁面置換算法*/ void FIFO() int memery10=0; int time10=0; /*記錄進入物理塊的時間*/ int i,j,k,m; int max=0; /*記錄換出頁*/ int count=0;/*記錄置換次數(shù)*/ /*前mSIZE個數(shù)直接放入*/ for(i=0;i<mSIZE;i+) m

16、emeryi=pagei; timei=i; for(j=0;j<mSIZE;j+) tempij=memeryj; for(i=mSIZE;i<pSIZE;i+) /*判斷新頁面號是否在物理塊中*/ for(j=0,k=0;j<mSIZE;j+) if(memeryj!=pagei) k+; if(k=mSIZE) /*如果不在物理塊中*/ count+; /*計算換出頁*/ max=time0<time1?0:1; for(m=2;m<mSIZE;m+) if(timem<timemax) max=m; memerymax=pagei; timemax=

17、i; /*記錄該頁進入物理塊的時間*/ for(j=0;j<mSIZE;j+) tempij=memeryj; else for(j=0;j<mSIZE;j+) tempij=memeryj; compute(); print(count); /*最近最久未使用置換算法*/ void LRU() int memery10=0;int flag10=0; /*記錄頁面的訪問時間*/ int i,j,k,m; int max=0; /*記錄換出頁*/ int count=0; /*記錄置換次數(shù)*/ /*前mSIZE個數(shù)直接放入*/ for(i=0;i<mSIZE;i+) meme

18、ryi=pagei; flagi=i; for(j=0;j<mSIZE;j+) tempij=memeryj; for(i=mSIZE;i<pSIZE;i+) /*判斷新頁面號是否在物理塊中*/ for(j=0,k=0;j<mSIZE;j+) if(memeryj!=pagei) k+; else flagj=i;/*刷新該頁的訪問時間*/ if(k=mSIZE)/*如果不在物理塊中*/ count+; /*計算換出頁*/ max=flag0<flag1?0:1; for(m=2;m<mSIZE;m+) if(flagm<flagmax) max=m; me

19、merymax=pagei; flagmax=i; /*記錄該頁的訪問時間*/ for(j=0;j<mSIZE;j+) tempij=memeryj; else for(j=0;j<mSIZE;j+) tempij=memeryj; compute(); print(count); /*最佳置換算法*/void OPT() int memery10=0; int next10=0; /*記錄下一次訪問時間*/ int i,j,k,l,m; int max;/*記錄換出頁*/ int count=0; /*記錄置換次數(shù)*/ /*前mSIZE個數(shù)直接放入*/ for(i=0;i<

20、mSIZE;i+) memeryi=pagei; for(j=0;j<mSIZE;j+) tempij=memeryj; for(i=mSIZE;i<pSIZE;i+) /*判斷新頁面號是否在物理塊中*/ for(j=0,k=0;j<mSIZE;j+) if(memeryj!=pagei) k+; if(k=mSIZE)/*如果不在物理塊中*/ count+; /*得到物理快中各頁下一次訪問時間*/ for(m=0;m<mSIZE;m+) for(l=i+1;l<pSIZE;l+) if(memerym=pagel) break; nextm=l; /*計算換出頁*/ max=next0>=next1?0:1; for(m=2;m<mSIZE;m+) if(nextm>nextmax) max=m;