實驗三頁面置換算法實驗

1、操作系統(tǒng)原理實驗報告實驗三 頁面置換算法實驗專業(yè)：計算機(jī)科學(xué)與技術(shù)學(xué)號：姓名：簡鄲實驗日期：2010-5-22一、實驗?zāi)康耐ㄟ^模擬實現(xiàn)請求頁式存儲管理的幾種基本頁面置換算法，了解虛擬存儲技術(shù)的特點(diǎn)，掌握虛擬存儲請求頁式存儲管理中幾種基本頁面置換算法的基本思想和實現(xiàn)過程，并比較它們的效率。二、實驗要求設(shè)計一個虛擬存儲區(qū)和內(nèi)存工作區(qū)，并使用下述算法計算訪問命中率。1最佳淘汰算法（OPT）2先進(jìn)先出的算法（FIFO）3最近最久未使用算法（LRU）三、實驗方法內(nèi)容1. 算法設(shè)計思路1假設(shè)分給一作業(yè)的內(nèi)存塊數(shù)為 4 ，每條指令占一個存儲單元，每個頁面中可存放 10 條指令；2設(shè)計一個程序，模擬一作業(yè)的執(zhí)

2、行過程。設(shè)該作業(yè)共有 160 條指令，即它的地址空間為16頁，最初作業(yè)的所有頁面都還未調(diào)入內(nèi)存。在模擬過程中，如果所訪問的指令已經(jīng)在內(nèi)存，則顯示其物理地址，并轉(zhuǎn)下一條指令。如果所訪問的指令尚未裝入內(nèi)存，則發(fā)生缺頁，此時需記錄缺頁的次數(shù)，并將相應(yīng)頁調(diào)入內(nèi)存。如果 4 個內(nèi)存塊中均已裝入該作業(yè)的虛頁面，則需進(jìn)行頁面置換；在所有 160條指令執(zhí)行完畢后，請計算并顯示作業(yè)運(yùn)行過程中發(fā)生的缺頁率。 3 作業(yè)中指令的訪問次序要求按下述原則生成：具體的實施辦法是： (1)在0，159之間隨機(jī)選取一條起始執(zhí)行指令，其序號為 m ； (2)順序執(zhí)行兩條指令，即序號為 m+1、m+2 的指令； (3)通過隨機(jī)數(shù)，

3、跳轉(zhuǎn)到前地址部分0，m-1中的某條指令處，其序號為 m1 ； (4)順序執(zhí)行兩條指令，即序號為 m1+1 ，m1+2的指令； (5)通過隨機(jī)數(shù)，跳轉(zhuǎn)到后地址部分 m1+3，159 中的某條指令處，其序號為 m2 ； (6)順序執(zhí)行兩條指令，即序號為 m2+1，m2+2 的指令；若m2+2159只執(zhí)行一條指令；(7)重復(fù)“跳轉(zhuǎn)到前地址部分、順序執(zhí)行、跳轉(zhuǎn)到后地址部分、順序執(zhí)行”的過程，直至執(zhí)行完全部160條指令2. 算法流程圖3. 算法中用到的數(shù)據(jù)結(jié)構(gòu)4. 主要的常量變量5. 主要模塊四、實驗代碼#include#include#include #include#define total_ins

4、truction 200 /*指令流長*/#define M 16 /*實際頁數(shù)*/#define N 4 /可用頁面數(shù)struct Proint num,time;int atotal_instruction;int pageN;void Input(Pro ptotal_instruction) int m,i,m1,m2; srand( (unsigned int )time(NULL); m=rand( )%160; / for(i=0;itotal_instruction;) /*產(chǎn)生指令隊列*/ if(m159) printf(When i=%d,Error,m=%dn,i,m);

5、 exit(0); ai=m; /*任選一指令訪問點(diǎn)m*/ ai+1=ai+1; ai+2=ai+2; /*順序執(zhí)行兩條指令*/ int m1=rand( )%m; /*執(zhí)行前地址指令m1 */ ai+3=m1; ai+4=m1+1; ai+5=m1 + 2;/*順序執(zhí)行兩條指令*/ / s=(158-ai+5)*rand( )/32767/32767/2+ai+5+2; m2 = rand()%(157-m1)+m1+3; ai+6=m2; if( (m2+2) 159 ) ai+7 = m2+1; i +=8; else ai+7 = m2+1; ai+8 = m2+2; i = i+9;

6、 m = rand()%m2; for (i=0;itotal_instruction;i+) /*將指令序列變換成頁地址流*/ pi.num=ai/10; pi.time = 0; void print(Pro *page1)/打印當(dāng)前的頁面 Pro *page=new ProN; page=page1; for(int i=0;iN;i+) coutpagei.num ; coutendl;int Search(int e,Pro *page1 ) Pro *page=new ProN; page=page1; for(int i=0;iN;i+)if(e=pagei.num)return

7、 i; return -1;int Max(Pro *page1) Pro *page=new ProN; page=page1; int e=page0.time,i=0; while(iN)/找出離現(xiàn)在時間最長的頁面 if(epagei.time)e=pagei.time; i+; for( i=0;iN;i+)if(e=pagei.time)return i; return -1;int Compfu(Pro *page1,int i,int t,Pro pM) Pro *page=new ProN; page=page1; int count=0; for(int j=i;jM;j+)

8、 if(paget.num=pj.num )break; else count+; return count;int main() Pro ptotal_instruction; Pro *page=new ProN; char c; int t=0; float n=0; Input(p); do for(int i=0;iN;i+)/初試化頁面基本情況 pagei.num=0; pagei.time=2-i; i=0; coutf:FIFO頁面置換endl; coutl:LRU頁面置換endl; couto:OPT頁面置換endl; cout按其它鍵結(jié)束c; if(c=f)/FIFO頁面置

9、換 n=0; cout頁面置換情況: endl; while( i=0) i+;/找到相同的頁面 else if(t=N)t=0; else n+;/ paget.num=pi.num; print(page); t+; cout缺頁次數(shù)：n 缺頁率：n/total_instructionendl; if(c=l)/LRU頁面置換 n=0; cout頁面置換情況: endl; while(i=0) paget.time=0; else n+; t=Max(page); paget.num=pi.num; paget.time=0; if(t=0)paget+1.time+;paget+2.time+; if(t=1)page2.time+;page0.time+; if(t=2)page1.time+;page0.time+; if(k=-1) print(page); i+; cout缺頁次數(shù)：n 缺頁率：n/total_instructionendl; if(c=o)/OPT頁面置換 n=0; while(i=0)i+; else int temp=0,cn; for(t=0;tN;t+) if(tempCompfu(page