實(shí)驗(yàn)三 頁(yè)面調(diào)度算法

1、陜西理工孽侏Shaanxi University of Technology實(shí)驗(yàn)報(bào)告院（系）:數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院專業(yè)班級(jí)：學(xué) 號(hào)：姓 名：實(shí)驗(yàn)地點(diǎn)：實(shí)驗(yàn)日期： 年 月 日課程名稱實(shí)驗(yàn)項(xiàng)目名稱實(shí)驗(yàn)學(xué)時(shí)實(shí)驗(yàn)類型操作系統(tǒng)頁(yè)面調(diào)度算法2設(shè)計(jì)一、實(shí)驗(yàn)?zāi)康募耙笸ㄟ^本實(shí)驗(yàn)可以加深理解有關(guān)虛擬存儲(chǔ)器的工作原理，進(jìn)一步體會(huì)和了解頁(yè) 面替換算法的具體實(shí)現(xiàn)方法。二、實(shí)驗(yàn)環(huán)境PC /Windows 系統(tǒng)/Visual C+6.0三、實(shí)驗(yàn)內(nèi)容實(shí)現(xiàn)三種算法：先進(jìn)先出；OPT； LRU頁(yè)面序列從指定的文本文件(TXT文件)中取出輸出：第一行：每次淘汰的頁(yè)面號(hào)，第二行：顯示缺頁(yè)的總次數(shù)/*全局變量*/int mSIZE;

2、 /* 物理塊數(shù)*/int pSIZE; /*頁(yè)面號(hào)引用串個(gè)數(shù)*/static int memery10 = 0; /* 物理塊中的頁(yè)號(hào)*/static int page100 = 0; /* 頁(yè)面號(hào)引用串 */static int temp10010 = 0; /* 輔助數(shù)組*/*置換算法函數(shù)*/void FIFO();void LRU();void OPT();/*輔助函數(shù)*/void print(unsigned int t);void designBy();void download();void mDelay(unsigned int Delay);/*先進(jìn)先出頁(yè)面置換算法*/voi

3、d FIFO()(int memery10 = 0;int time10 = 0; /*記錄進(jìn)入物理塊的時(shí)間*/int i,j,k,m;int max=0; /*記錄換出頁(yè)*/int count=0; /*記錄置換次數(shù)*/*前mSIZE個(gè)數(shù)直接放入*/for(i=0;imSIZE;i+)(memeryi=pagei;timei=i;for(j=0;jmSIZE;j+)tempij=memeryj;for(i=mSIZE;ipSIZE;i+)(/*判斷新頁(yè)面號(hào)是否在物理塊中*/for(j=0,k=0;jmSIZE;j+)(if(memeryj!=pagei)k+;if(k=mSIZE) /*如果

4、不在物理塊中*/(count+;/*計(jì)算換出頁(yè)*/max=time0time1?0:1;for(m=2;mmSIZE;m+)if(timemtimemax)max=m;memerymax=pagei;timemax=i; /*記錄該頁(yè)進(jìn)入物理塊的時(shí)間*/for(j=0;jmSIZE;j+)tempij=memeryj;else(for(j=0;jmSIZE;j+)tempij=memeryj;compute();print(count);/*最近最久未使用置換算法*/void LRU()(int memery10 = 0;int flag10 = 0; /*記錄頁(yè)面的訪問時(shí)間*/int i,j

5、,k,m;int max=0; /*記錄換出頁(yè)*/int count=0; /*記錄置換次數(shù)*/*前mSIZE個(gè)數(shù)直接放入*/for(i=0;imSIZE;i+)(memeryi=pagei;flagi=i;for(j=0;jmSIZE;j+)tempij=memeryj;for(i=mSIZE;ipSIZE;i+)(/*判斷新頁(yè)面號(hào)是否在物理塊中*/for(j=0,k=0;jmSIZE;j+)(if(memeryj!=pagei)k+;elseflagj=i; /*刷新該頁(yè)的訪問時(shí)間*/if(k=mSIZE) /*如果不在物理塊中*/(count+;/*計(jì)算換出頁(yè)*/max=flag0fla

6、g1?0:1;for(m=2;mmSIZE;m+)if(flagmflagmax)max=m;memerymax=pagei;flagmax=i; /*記錄該頁(yè)的訪問時(shí)間*/for(j=0;jmSIZE;j+)tempij=memeryj;elsefor(j=0;jmSIZE;j+)tempij=memeryj;compute();print(count);/*最佳置換算法*/void OPT()(int memery10 = 0;int next10 = 0; /*記錄下一次訪問時(shí)間*/int i,j,k,l,m;int max; /*記錄換出頁(yè)*/int count=0; /*記錄置換次數(shù)

7、*/*前mSIZE個(gè)數(shù)直接放入*/for(i=0;imSIZE;i+)(memeryi=pagei;for(j=0;jmSIZE;j+)tempij=memeryj;for(i=mSIZE;ipSIZE;i+)(/*判斷新頁(yè)面號(hào)是否在物理塊中*/for(j=0,k=0;jmSIZE;j+)(if(memeryj!=pagei)k+;if(k=mSIZE) /*如果不在物理塊中*/(count+;/*得到物理快中各頁(yè)下一次訪問時(shí)間*/ for(m=0;mmSIZE;m+)(for(l=i+1;l=next1?0:1;for(m=2;mnextmax)max=m;/*下一次訪問時(shí)間都為pSIZE，

8、則置換物理塊中第一個(gè)*/ memerymax=pagei;for(j=0;jmSIZE;j+)tempij=memeryj;elsefor(j=0;jmSIZE;j+)tempij=memeryj;compute();print(count);四、實(shí)驗(yàn)步驟頁(yè)面置換：在地址映射過程中，若在頁(yè)面中發(fā)現(xiàn)所要訪問的頁(yè)面不在內(nèi)存中，則產(chǎn)生缺頁(yè)中 斷。當(dāng)發(fā)生缺頁(yè)中斷時(shí)，如果操作系統(tǒng)內(nèi)存中沒有空閑頁(yè)面，則操作系統(tǒng)必須在內(nèi)存選擇一 個(gè)頁(yè)面將其移出內(nèi)存，以便為即將調(diào)入的頁(yè)面讓出空間。而用來(lái)選擇淘汰哪一頁(yè)的規(guī)則叫做頁(yè)面置換算法：最佳置換算法(OPT)(理想置換算法)：從主存中移出永遠(yuǎn)不再需要的頁(yè)面；如無(wú)這 樣的頁(yè)

9、面存在，則選擇最長(zhǎng)時(shí)間不需要訪問的頁(yè)面。于所選擇的被淘汰頁(yè)面將是以后永不使 用的，或者是在最長(zhǎng)時(shí)間內(nèi)不再被訪問的頁(yè)面，這樣可以保證獲得最低的缺頁(yè)率。先進(jìn)先出置換算法（FIFO）:是最簡(jiǎn)單的頁(yè)面置換算法。這種算法的基本思想是：當(dāng)需 要淘汰一個(gè)頁(yè)面時(shí)，總是選擇駐留主存時(shí)間最長(zhǎng)的頁(yè)面進(jìn)行淘汰，即先進(jìn)入主存的頁(yè)面先淘 汰。其理由是：最早調(diào)入主存的頁(yè)面不再被使用的可能性最大。最近最久未使用（LRU）算法：這種算法的基本思想是：利用局部性原理，根據(jù)一個(gè)作 業(yè)在執(zhí)行過程中過去的頁(yè)面訪問歷史來(lái)推測(cè)未來(lái)的行為。它認(rèn)為過去一段時(shí)間里不曾被訪問 過的頁(yè)面，在最近的將來(lái)可能也不會(huì)再被訪問。所以，這種算法的實(shí)質(zhì)是:當(dāng)需要淘汰一個(gè)頁(yè)