操作系統(tǒng)實(shí)驗(yàn)5 頁面置換算法
操作系統(tǒng)實(shí)驗(yàn)報(bào)告計(jì)算機(jī)0703班200729實(shí)驗(yàn)5 頁面置換算法一、 實(shí)驗(yàn)題目:頁面置換算法(請(qǐng)求分頁)二、 實(shí)驗(yàn)?zāi)康模?進(jìn)一步理解父子進(jìn)程之間的關(guān)系。1) 理解內(nèi)存頁面調(diào)度的機(jī)理。2) 掌握頁面置換算法的實(shí)現(xiàn)方法。3) 通過實(shí)驗(yàn)比較不同調(diào)度算法的優(yōu)劣。4) 培養(yǎng)綜合運(yùn)用所學(xué)知識(shí)的能力。 頁面置換算法是虛擬存儲(chǔ)管理實(shí)現(xiàn)的關(guān)鍵,通過本次試驗(yàn)理解內(nèi)存頁面調(diào)度的機(jī)制,在模擬實(shí)現(xiàn)FIFO、LRU等經(jīng)典頁面置換算法的基礎(chǔ)上,比較各種置換算法的效率及優(yōu)缺點(diǎn),從而了解虛擬存儲(chǔ)實(shí)現(xiàn)的過程。將不同的置換算法放在不同的子進(jìn)程中加以模擬,培養(yǎng)綜合運(yùn)用所學(xué)知識(shí)的能力。三、 實(shí)驗(yàn)內(nèi)容及要求 這是一個(gè)綜合型實(shí)驗(yàn),要求在掌握父子進(jìn)程并發(fā)執(zhí)行機(jī)制和內(nèi)存頁面置換算法的基礎(chǔ)上,能綜合運(yùn)用這兩方面的知識(shí),自行編制程序。程序涉及一個(gè)父進(jìn)程和兩個(gè)子進(jìn)程。父進(jìn)程使用rand()函數(shù)隨機(jī)產(chǎn)生若干隨機(jī)數(shù),經(jīng)過處理后,存于一數(shù)組Acess_Series中,作為內(nèi)存頁面訪問的序列。兩個(gè)子進(jìn)程根據(jù)這個(gè)訪問序列,分別采用FIFO和LRU兩種不同的頁面置換算法對(duì)內(nèi)存頁面進(jìn)行調(diào)度。要求:1) 每個(gè)子進(jìn)程應(yīng)能反映出頁面置換的過程,并統(tǒng)計(jì)頁面置換算法的命中或缺頁情況。設(shè)缺頁的次數(shù)為diseffect??偟捻撁嬖L問次數(shù)為total_instruction。缺頁率 = disaffect/total_instruction命中率 = 1- disaffect/total_instruction2)將為進(jìn)程分配的內(nèi)存頁面數(shù)mframe 作為程序的參數(shù),通過多次運(yùn)行程序,說明FIFO算法存在的Belady現(xiàn)象。四、程序流程圖 五、 程序源代碼、文檔注釋及文字說明#include<stdio.h>#include<sys/types.h>#include<stdlib.h>#include<sys/stat.h>#include<fcntl.h>#include<error.h>#include<wait.h>#include<unistd.h>main()int p1,p2;int i,j,k,t,m,kk,r1,r2;int temp1,temp2,temp3;int diseffect1=0;int diseffect2=0; int k1=0;int k2=0; int f1=0;int f2=0;float f; int Access_series8; struct one_frame int page_no; char flag; ; int mframe=5; struct one_frame M_Frame5;for(i=0;i<mframe;i+) M_Framei.page_no=-1; printf("yemian: "); for(i=0;i<8;i+) /產(chǎn)生隨機(jī)數(shù) Access_seriesi=rand()%8+1; printf("%d ",Access_seriesi);printf("n"); while(p1=fork()=-1); if(p1=0) for(j=0;j<8;j+) r1=Access_seriesj; /讀入一個(gè)邏輯頁面 for(k=0;k<k1;k+) /查找頁面是否已存在于物理頁面 if(r1!=M_Framek.page_no) continue; else printf("have found!n");for(i=0;i<k1;i+) /存在則顯示,并標(biāo)記,返回讀入邏輯頁面 printf("%d ",M_Framei);printf("n");f1=1;break; if(f1=0) diseffect1+; /若不存在,發(fā)生缺頁,則失效率加1 if(k1<mframe) /物理頁面沒有分配滿 M_Framek1.page_no=r1; /分配一個(gè)空的物理頁面 M_Framek1.flag='Y' k1+; for(i=0;i<8;i+)printf("%d ",Access_seriesi);printf("n"); printf("diseffect!");printf(" %dn",diseffect1); for(i=0;i<k1;i+) printf("%d ",M_Framei);printf("n"); else temp1=M_Frame0.page_no; /物理頁面表已滿 for(i=1;i<5;i+) M_Framei-1=M_Framei;M_Frame4.page_no=r1; /淘汰最早進(jìn)入的M_Frame0 /并將所讀的邏輯頁面調(diào)入 for(i=0;i<8;i+)printf("%d ",Access_seriesi);printf("n"); printf("diseffect! %dn",diseffect1); printf("lose %dn",temp1); for(i=0;i<k1;i+) printf("%d ",M_Framei);printf("n"); f1=0; f=diseffect1/8.0; /統(tǒng)計(jì)缺頁率 printf("diseffect rate of FIFO %fn",f); exit(0); wait(0); for(i=0;i<mframe;i+) M_Framei.page_no=-1; while(p2=fork()=-1) ; /創(chuàng)建子進(jìn)程2 if(p2=0) for(m=0;m<8;m+) r2=Access_seriesm; /讀入邏輯頁 for(kk=0;kk<k2;kk+) if(r2!=M_Framekk.page_no) /首先在物理頁面中查找 continue; else printf("have found!n"); /找到 for(t=kk+1;t<k2;t+) /調(diào)整數(shù)組順序,使剛被訪問的頁面在最后的位置 M_Framet-1.page_no=M_Framet.page_no; M_Framet-1.page_no=r2; for(i=0;i<k2;i+) printf("%d ",M_Framei.page_no);printf("n"); f2=1; break; if(f2=0) /沒有找到,發(fā)生缺頁 diseffect2+; /缺頁率加1 if(k2<mframe) /物理頁面還沒有分配完 M_Framek2.page_no=r2; /選擇空頁面分配 M_Framek2.flag='Y'k2+; for(i=0;i<8;i+)printf("%d ",Access_seriesi);printf("n"); printf("diseffect! %dn",diseffect2); for(i=0;i<k2;i+) printf("%d ",M_Framei);printf("n"); else /淘汰最近最久未訪問的M_Frame0 temp3=M_Frame0.page_no; for(i=1;i<mframe;i+) M_Framei-1.page_no=M_Framei.page_no; M_Framemframe-1.page_no=r2; /將當(dāng)前頁調(diào)入for(i=0;i<8;i+)printf("%d ",Access_seriesi);printf("n"); printf("diseffect %dn",diseffect2); printf("lose %dn",temp3); for(i=0;i<k2;i+) printf("%d ",M_Framei);printf("n"); f2=0; f=diseffect2/8.0; /統(tǒng)計(jì)失效率 printf("diseffect rate of LRU %fn",f);exit(0); 六、 運(yùn)行結(jié)果及其說明FIFO:8,7,2,4缺頁調(diào)入,2,8命中,3缺頁調(diào)入,5缺頁淘汰8,調(diào)入5;LRU:8,7,2,4缺頁調(diào)入,訪問2,把2移到數(shù)組尾,訪問8,把8移到數(shù)組尾,3缺頁調(diào)入,5缺頁,淘汰7,調(diào)入5。 七、回答以下問題: 父進(jìn)程、子進(jìn)程之間的并發(fā)執(zhí)行的過程 通過完成實(shí)驗(yàn),根據(jù)你的體會(huì),闡述虛擬存儲(chǔ)器的原理。 寫出FIFO算法中出現(xiàn)Belady現(xiàn)象的內(nèi)存頁面訪問序列。