操作系統(tǒng)課程設(shè)計(jì) 頁(yè)面置換算法

1、 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院操作系統(tǒng)課程設(shè)計(jì)報(bào)告 （2013/2014學(xué)年 第一學(xué)期）學(xué)生姓名： 學(xué)生專(zhuān)業(yè)： 網(wǎng)絡(luò)工程學(xué)生班級(jí)： 網(wǎng)絡(luò)工程112001學(xué)生學(xué)號(hào)： 指導(dǎo)教師： 2013年12月20日 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院課程設(shè)計(jì)任務(wù)書(shū)課程設(shè)計(jì)名稱(chēng)操作系統(tǒng)課程設(shè)計(jì)課程設(shè)計(jì)題目頁(yè)面置換算法學(xué)生姓名賈正正專(zhuān)業(yè)班級(jí)網(wǎng)絡(luò)工程112001班學(xué)號(hào)201120030109課程設(shè)計(jì)任務(wù)內(nèi)容問(wèn)題描述 設(shè)計(jì)一個(gè)虛擬存儲(chǔ)區(qū)和內(nèi)存工作區(qū)，并使用最佳淘汰算法（OPT）、先進(jìn)先出算法（FIFO）、最近最久未使用算法（LRU）計(jì)算訪問(wèn)命中率?；疽?（1）分析設(shè)計(jì)要求，給出解決方案（2）設(shè)計(jì)合適的測(cè)試用例，對(duì)得到的運(yùn)行結(jié)果要有分析

2、。 指導(dǎo)教師：趙建 時(shí) 間： 2013年 12月 10日 目 錄 第一章 問(wèn)題的提出31.1關(guān)于頁(yè)面置換算法模擬程序問(wèn)題的產(chǎn)生31.2 任務(wù)分析3第二章 需求分析42.1需求說(shuō)明42.2操作界面和操作方法4第三章 設(shè)計(jì)描述53.1方案設(shè)計(jì)53.2主要的函數(shù)5第四章 算法描述64.1主函數(shù)流程圖64.2FIFO（先進(jìn)先出）頁(yè)面置換算法74.3LRU(最近最久未使用)頁(yè)面置換算法94.4OPT（最佳置換算法）114.5實(shí)現(xiàn)結(jié)果14第五章 程序測(cè)試175.1 設(shè)計(jì)測(cè)試數(shù)據(jù)175.2 測(cè)試結(jié)果及分析17結(jié) 論18參考文獻(xiàn)19代碼：20 第一章 問(wèn)題的提出1.1關(guān)于頁(yè)面置換算法模擬程序問(wèn)題的產(chǎn)生在各種存

3、儲(chǔ)器管理方式中，有一個(gè)共同的特點(diǎn)，即它們都要求將一個(gè)作業(yè)全部裝入內(nèi)存方能運(yùn)行，但是有兩種情況：（1） 有的作業(yè)很大，不能全部裝入內(nèi)存，致使作業(yè)無(wú)法運(yùn)行；（2） 有大量作業(yè)要求運(yùn)行，但內(nèi)存容量不足以容納所有這些作業(yè)。而虛擬內(nèi)存技術(shù)正式從邏輯上擴(kuò)充內(nèi)存容量，將會(huì)解決以上兩個(gè)問(wèn)題。從內(nèi)存中調(diào)出一頁(yè)程序或數(shù)據(jù)送磁盤(pán)的對(duì)換區(qū)中，通常，把選擇換出的頁(yè)面的算法稱(chēng)為頁(yè)面置換算法（Page-Replacement Algorithms）。進(jìn)而頁(yè)面置換算法模擬程序能客觀的將其工作原理展現(xiàn)在我們面前。1.2 任務(wù)分析首先，定義宏變量，設(shè)置所占最大內(nèi)存長(zhǎng)度。編輯以時(shí)間為種子，初始化隨即發(fā)生器。進(jìn)行相關(guān)頁(yè)面輸入程序的編

4、寫(xiě)以及頁(yè)面的打印。爾后，尋找最近最近最久未使用的頁(yè)面 、記錄當(dāng)前內(nèi)存塊中頁(yè)面離下次使用間隔長(zhǎng)度等相關(guān)程序的代碼編寫(xiě)。最后，進(jìn)行)FIFO 、LRU、 OPT三種算法的編寫(xiě)。 第二章 需求分析2.1需求說(shuō)明1. 用隨機(jī)數(shù)方法產(chǎn)生頁(yè)面走向，頁(yè)面走向長(zhǎng)度為L(zhǎng)。2. 根據(jù)頁(yè)面走向，分別采用FIFO和LRU算法進(jìn)行頁(yè)面置換，統(tǒng)計(jì)缺頁(yè)率；為簡(jiǎn)化操作，在淘汰一頁(yè)時(shí)，只將該頁(yè)在頁(yè)表中抹去,而不再判斷它是否被改寫(xiě)過(guò)，也不將它寫(xiě)回到輔存。3. 假定可用內(nèi)存塊和頁(yè)表長(zhǎng)度 (作業(yè)的頁(yè)面數(shù))分別為m和k，初始時(shí)，作業(yè)頁(yè)面都不在內(nèi)存。2.2操作界面和操作方法 *頁(yè)面置換算法算法演示* 請(qǐng)首先輸入頁(yè)面走向長(zhǎng)度L: 請(qǐng)首先輸

5、入頁(yè)面數(shù): 根據(jù)提示進(jìn)入算法界面： 在如上的操作界面中分別按照提示進(jìn)行輸入，按回車(chē)鍵表示當(dāng)前輸入完畢，然后進(jìn)行下個(gè)步驟的輸入或者得到最終結(jié)果。第3章 設(shè)計(jì)描述3.1方案設(shè)計(jì)首先，定義宏變量，設(shè)置所占最大內(nèi)存長(zhǎng)度。編輯以時(shí)間為種子，初始化隨即發(fā)生器。進(jìn)行相關(guān)頁(yè)面輸入程序的編寫(xiě)以及頁(yè)面的打印。其次，尋找最近最近最久未使用的頁(yè)面 、記錄當(dāng)前內(nèi)存塊中頁(yè)面離下次使用間隔長(zhǎng)度等相關(guān)程序的代碼編寫(xiě)。最后，進(jìn)行FIFO 、LRU、 OPT三種算法的編寫(xiě)。3.2主要的函數(shù)Input(int m,Pro pL)（打印頁(yè)面走向狀態(tài)）；void print(Pro *page1)（打印當(dāng)前的頁(yè)面）；int Searc

6、h(int e,Pro *page1 )（尋找內(nèi)存塊中與e相同的塊號(hào)）； int Max(Pro *page1)（尋找最近最長(zhǎng)未使用的頁(yè)面）；int Count(Pro *page1,int i,int t,Pro pL)（記錄當(dāng)前內(nèi)存塊中頁(yè)面離下次使用間隔長(zhǎng)度）；int main()（主函數(shù)）；隨機(jī)數(shù)發(fā)生器 #include <stdlib.h> #include <time.h> /準(zhǔn)備用時(shí)鐘函數(shù)調(diào)用庫(kù)函數(shù)t=time(NULL);/取時(shí)鐘時(shí)間并存入t調(diào)用庫(kù)函數(shù)srand(t);/用時(shí)間t初始化隨機(jī)數(shù)發(fā)生器調(diào)用庫(kù)函數(shù)x=rand( )%10+1;/返回一個(gè)110之間

7、的隨機(jī)數(shù)第4章 算法描述 開(kāi)始4.1主函數(shù)流程圖輸入頁(yè)面走向長(zhǎng)度LNL是否在范圍 結(jié)束YYYNNN 結(jié)束始 OPT頁(yè)面置換算法是否為3 LRU頁(yè)面置換算法是否為2 FIFO頁(yè)面置換算法NY是否為1輸入13頁(yè)面數(shù)是否在范圍輸入當(dāng)前頁(yè)面數(shù) 隨機(jī)產(chǎn)生L個(gè)數(shù)字Y564.2FIFO（先進(jìn)先出）頁(yè)面置換算法N i>L輸出當(dāng)前頁(yè)面信息YNY輸出當(dāng)前內(nèi)存塊狀 結(jié)束 設(shè)計(jì)原理： 結(jié)束需要進(jìn)行頁(yè)面置換，即把內(nèi)存中裝入最早的那個(gè)頁(yè)面淘汰，換入當(dāng)前的頁(yè)面。0 6代碼：if(c=1)/FIFO頁(yè)面置換 n=0;cout<<" * "<<endl;cout<<

8、endl; cout<<" FIFO算法頁(yè)面置換情況如下: "<<endl;cout<<endl; cout<<" * "<<endl; while(i<m) if(Search(pi.num,page)>=0)/當(dāng)前頁(yè)面在內(nèi)存中 cout<<pi.num<<" "/輸出當(dāng)前頁(yè)pi.numcout<<"不缺頁(yè)"<<endl;i+;/i加1 else /當(dāng)前頁(yè)不在內(nèi)存中 if(t=M)t=0; el

9、se n+;/缺頁(yè)次數(shù)加1 paget.num=pi.num; /把當(dāng)前頁(yè)面放入內(nèi)存中 cout<<pi.num<<" " print(page); /打印當(dāng)前頁(yè)面 t+; /下一個(gè)內(nèi)存塊i+; /指向下一個(gè)頁(yè)面 cout<<"缺頁(yè)次數(shù)："<<n<<" 缺頁(yè)率："<<n/m<<endl; 8 64.3LRU(最近最久未使用)頁(yè)面置換算法 i+Page是否有空當(dāng)前p中第i個(gè)元素是否已在內(nèi)存頁(yè)面走向存入數(shù)組p中，內(nèi)存塊用page表示初始化為0 開(kāi)始 開(kāi)始

10、開(kāi)始 開(kāi)始 開(kāi)始 YNYN把pi的內(nèi)容直接裝入最上面一個(gè)空內(nèi)存塊，i+把page中最近最久未使用的頁(yè)面置換出去.i+輸出當(dāng)前頁(yè)面信息N i>L 結(jié)束Y輸出當(dāng)前內(nèi)存塊狀 結(jié)束9 設(shè)計(jì)原理：當(dāng)需要淘汰某一頁(yè)時(shí)，選擇離當(dāng)前時(shí)間最近的一段時(shí)間內(nèi)最久沒(méi)有使用過(guò)的頁(yè)先淘汰該算法的主要出發(fā)點(diǎn)是，如果某頁(yè)被訪問(wèn)了，則它可能馬上還要被訪問(wèn)。或者反過(guò)來(lái)說(shuō)如果某頁(yè)很長(zhǎng)時(shí)間未被訪問(wèn)，則它在最近一段時(shí)間6也不會(huì)被訪問(wèn)。代碼：if(c=2)/LRU頁(yè)面置換 n=0; cout<<" * "<<endl;cout<<endl; cout<<"

11、; LRU算法頁(yè)面置換情況如下: "<<endl; cout<<endl;cout<<" * "<<endl; while(i<m) int a; t=Search(pi.num,page); if(t>=0) /如果已在內(nèi)存塊中 paget.time=0; /把與它相同的內(nèi)存塊的時(shí)間置0for(a=0;a<M;a+)if(a!=t)pagea.time+; /其它的時(shí)間加1 cout<<pi.num<<" "cout<<"不缺頁(yè)&q

12、uot;<<endl; else /如果不在內(nèi)存塊中 n+; /缺頁(yè)次數(shù)加1 t=Max(page); /返回最近最久未使用的塊號(hào)賦值給t paget.num=pi.num; /進(jìn)行替換 paget.time=0; /替換后時(shí)間置為0 cout<<pi.num<<" "print(page);for(a=0;a<M;a+)if(a!=t)pagea.time+; /其它的時(shí)間加1 i+; cout<<"缺頁(yè)次數(shù)："<<n<<" 缺頁(yè)率："<<n/

13、m<<endl; 101664.4OPT（最佳置換算法） 開(kāi)始 開(kāi)始 開(kāi)始 頁(yè)面走向存入數(shù)組p中，內(nèi)存塊用page表示初始化為0當(dāng)前p中第i個(gè)元素是否已在內(nèi)存Yi+NPage是否有空NYN把page中以后一段時(shí)間都不使用或是使用時(shí)間離現(xiàn)在最遠(yuǎn)的換出.i+把pi的內(nèi)容直接裝入最上面一個(gè)空內(nèi)存塊，i+輸出當(dāng)前頁(yè)面信息N i>LY輸出當(dāng)前內(nèi)存塊狀 結(jié)束11 設(shè)計(jì)原理：需要進(jìn)行頁(yè)面置換，把內(nèi)存中以后一段時(shí)間都不使用或是使用時(shí)間離現(xiàn)在最遠(yuǎn)的頁(yè)面換出。 結(jié)束 代碼： if(c=3) /OPT頁(yè)面置換 n=0;cout<<" * "<<endl;

14、cout<<endl;cout<<" OPT算法置換情況如下:"<<endl;cout<<endl;cout<<" * "<<endl; while(i<m)if(Search(pi.num,page)>=0) /如果已在內(nèi)存塊中 cout<<pi.num<<" "cout<<"不缺頁(yè)"<<endl;i+;else /如果不在內(nèi)存塊中int a=0; for(t=0;t<M;t+

15、)if(paget.num=0)a+; /記錄空的內(nèi)存塊數(shù)if(a!=0) /有空內(nèi)存塊int q=M;for(t=0;t<M;t+)if(paget.num=0&&q>t)q=t; /把空內(nèi)存塊中塊號(hào)最小的找出來(lái)pageq.num=pi.num;n+; cout<<pi.num<<" "print(page);i+;elseint temp=0,s;for(t=0;t<M;t+) /尋找內(nèi)存塊中下次使用離現(xiàn)在最久的頁(yè)面if(temp<Count(page,i,t,p)temp=Count(page,i,t,p

16、);s=t; /把找到的塊號(hào)賦給spages.num=pi.num; n+; cout<<pi.num<<" " print(page); i+;cout<<"缺頁(yè)次數(shù)："<<n<<" 缺頁(yè)率："<<n/m<<endl;4.5實(shí)現(xiàn)結(jié)果程序在運(yùn)行的情況下，進(jìn)入主界面輸入菜單，如圖3-3所示：輸入10：圖4-5 輸入10后的輸出圖輸入22：圖5-6輸入數(shù)據(jù)22后輸出圖輸入數(shù)據(jù)16：圖5-7 輸入數(shù)據(jù)16后的輸出圖輸入數(shù)據(jù)：圖5-8輸出圖選1，進(jìn)入FIFO頁(yè)

17、面置換：圖5-9 FIFO的輸出圖選2，進(jìn)入LRU頁(yè)面置換：圖5-10 LRU的輸出圖輸入3，進(jìn)入OPT頁(yè)面置換： 第五章 程序測(cè)試5.1 設(shè)計(jì)測(cè)試數(shù)據(jù)A 10 22 16 ；1 6 5 ；B 1C 2 D 35.2 測(cè)試結(jié)果及分析1）測(cè)試A結(jié)果及分析 進(jìn)入主菜單后輸入10、22，顯示輸入不滿(mǎn)足要求。輸入16 顯示相關(guān)信息;輸入1 、6不滿(mǎn)足要求，輸入5 顯示出相關(guān)信息。2）測(cè)試結(jié)果及分析顯示出FIFO頁(yè)面置換算法的缺頁(yè)信息及缺頁(yè)率。3）測(cè)試C結(jié)果及分析顯示出LRU頁(yè)面置換算法的缺頁(yè)信息及缺頁(yè)率。4）測(cè)試D結(jié)果及分析顯示出OPT頁(yè)面置換算法的缺頁(yè)信息及缺頁(yè)率結(jié) 論通過(guò)本次課程設(shè)計(jì)，讓我深入的了

18、解了頁(yè)面置換算法。OPT算法總是選擇被淘汰頁(yè)面將是以后永遠(yuǎn)不使用的或者在最長(zhǎng)時(shí)間內(nèi)不再被訪問(wèn)的頁(yè)面。先找出所需頁(yè)面在磁盤(pán)的位置，再找出可用內(nèi)存塊，然后將所需頁(yè)面裝入內(nèi)存，修改相應(yīng)的數(shù)據(jù)結(jié)構(gòu)。最佳頁(yè)面置換算法可以先寫(xiě)一個(gè)結(jié)構(gòu)體，包括編號(hào)和使用次數(shù)2個(gè)內(nèi)容，然后動(dòng)態(tài)生成一個(gè)數(shù)組。然后另外寫(xiě)2個(gè)函數(shù)。一個(gè)計(jì)算中斷次數(shù)，一個(gè)進(jìn)行頁(yè)面置換。在檢測(cè)是否中斷的時(shí)候，可以循環(huán)遍歷上面動(dòng)態(tài)生成的數(shù)組。如果數(shù)組滿(mǎn)了且有頁(yè)面中斷的時(shí)候，才調(diào)用頁(yè)面置換的函數(shù)，否則只要把數(shù)據(jù)放入數(shù)組就可以，不用進(jìn)行頁(yè)面置換。此外還得寫(xiě)一個(gè)用于尋找內(nèi)存塊中下次使用離現(xiàn)在最久的頁(yè)面和一個(gè)用于記錄當(dāng)前內(nèi)存塊中頁(yè)面離下次使用時(shí)間間隔長(zhǎng)度的函數(shù)

19、。最佳淘汰算法是一種理想情況下的頁(yè)面置換算法，但實(shí)際上是不可能實(shí)現(xiàn)的，操作系統(tǒng)無(wú)法知道各個(gè)頁(yè)面下一次是在什么時(shí)候被訪問(wèn)。雖然這個(gè)算法不可能實(shí)現(xiàn)，但是可用于對(duì)可實(shí)現(xiàn)算法的性能進(jìn)行衡量比較。參考文獻(xiàn)面向?qū)ο蟪绦蛟O(shè)計(jì)與VisualC+6.0教程 陳天華編著C程序設(shè)計(jì)（第三版） 譚浩強(qiáng)編著C+入門(mén)經(jīng)典面向?qū)ο蟪绦蛟O(shè)計(jì)與C+實(shí)現(xiàn) 劉晉萍編著計(jì)算機(jī)操作系統(tǒng)教程 徐甲同等編著 操作系統(tǒng) 羅宇等編著 操作系統(tǒng)實(shí)驗(yàn)教程 張麗芬, 劉利雄, 王全玉編著 計(jì)算機(jī)操作系統(tǒng) 梁紅兵、哲風(fēng)屏、湯子瀛 編著操作系統(tǒng)教程 陳向群、楊芙清 編著代碼：#include<iostream.h>#include <

20、stdlib.h>#include <time.h>#include <stdio.h>#define L 20/頁(yè)面走向長(zhǎng)度最大為20int M; /內(nèi)存塊struct Pro/定義一個(gè)結(jié)構(gòu)體 int num,time; Input(int m,Pro pL)/打印頁(yè)面走向狀態(tài) cout<<"請(qǐng)輸入實(shí)際頁(yè)面走向長(zhǎng)度L(15<=L<=20)：" do cin>>m; if(m>20|m<15)cout<<"實(shí)際頁(yè)面長(zhǎng)度須在1520之間;請(qǐng)重新輸入L： " else

21、break; while(1); int i,j; j=time(NULL);/取時(shí)鐘時(shí)間 srand(j);/以時(shí)鐘時(shí)間x為種子，初始化隨機(jī)數(shù)發(fā)生器cout<<"輸出隨機(jī)數(shù): " for(i=0;i<m;i+) pi.num=rand( )%10+1;/產(chǎn)生1到10之間的隨即數(shù)放到數(shù)組p中 pi.time=0;cout<<pi.num<<" " cout<<endl; return m;void print(Pro *page1)/打印當(dāng)前的頁(yè)面 Pro *page=new ProM; page=p

22、age1; for(int i=0;i<M;i+) cout<<pagei.num<<" " cout<<endl;int Search(int e,Pro *page1 )/尋找內(nèi)存塊中與e相同的塊號(hào) Pro *page=new ProM; page=page1; for(int i=0;i<M;i+)if(e=pagei.num)return i;/返回i值 return -1;int Max(Pro *page1)/尋找最近最長(zhǎng)未使用的頁(yè)面 Pro *page=new ProM; page=page1; int e=pa

23、ge0.time,i=0; while(i<M) /找出離現(xiàn)在時(shí)間最長(zhǎng)的頁(yè)面 if(e<pagei.time) e=pagei.time; i+; for( i=0;i<M;i+)if(e=pagei.time)return i;/找到離現(xiàn)在時(shí)間最長(zhǎng)的頁(yè)面返回其塊號(hào) return -1;int Count(Pro *page1,int i,int t,Pro pL)/記錄當(dāng)前內(nèi)存塊中頁(yè)面離下次使用間隔長(zhǎng)度 Pro *page=new ProM; page=page1; int count=0; for(int j=i;j<L;j+) if(paget.num=pj.nu

24、m )break;/當(dāng)前頁(yè)面再次被訪問(wèn)時(shí)循環(huán)結(jié)束 else count+;/否則count+1 return count;/返回count的值 int main() int c; int m=0,t=0;float n=0;Pro pL; m=Input(m,p);/調(diào)用input函數(shù)，返回m值 cout<<"請(qǐng)輸入可用內(nèi)存頁(yè)面數(shù)m(35): " do cin>>M;if(M>5|M<3)cout<<"內(nèi)存塊m須在35之間，請(qǐng)重新輸入m： "else break;while(1); Pro *page=ne

25、w ProM; do for(int i=0;i<M;i+)/初試化頁(yè)面基本情況 pagei.num=0; pagei.time=m-1-i; i=0; cout<<"1:FIFO頁(yè)面置換"<<endl; cout<<"2:LRU頁(yè)面置換"<<endl; cout<<"3:OPT頁(yè)面置換"<<endl; cout<<"按其它鍵結(jié)束程序；"<<endl; cin>>c; system("cls&

26、quot;); if(c=1)/FIFO頁(yè)面置換 n=0;cout<<" * "<<endl;cout<<endl; cout<<" FIFO算法頁(yè)面置換情況如下: "<<endl;cout<<endl; cout<<" * "<<endl; while(i<m) if(Search(pi.num,page)>=0) /當(dāng)前頁(yè)面在內(nèi)存中 cout<<pi.num<<" " /輸出當(dāng)前頁(yè)

27、pi.numcout<<"不缺頁(yè)"<<endl;i+; /i加1 else /當(dāng)前頁(yè)不在內(nèi)存中 if(t=M)t=0; else n+; /缺頁(yè)次數(shù)加1 paget.num=pi.num; /把當(dāng)前頁(yè)面放入內(nèi)存中 cout<<pi.num<<" " print(page); /打印當(dāng)前頁(yè)面 t+; /下一個(gè)內(nèi)存塊i+; /指向下一個(gè)頁(yè)面 cout<<"缺頁(yè)次數(shù)："<<n<<" 缺頁(yè)率："<<n/m<<endl

28、; if(c=2)/LRU頁(yè)面置換 n=0; cout<<" * "<<endl;cout<<endl; cout<<" LRU算法頁(yè)面置換情況如下: "<<endl; cout<<endl;cout<<" * "<<endl; while(i<m) int a; t=Search(pi.num,page); if(t>=0)/如果已在內(nèi)存塊中 paget.time=0;/把與它相同的內(nèi)存塊的時(shí)間置0for(a=0;a<M

29、;a+)if(a!=t)pagea.time+;/其它的時(shí)間加1 cout<<pi.num<<" "cout<<"不缺頁(yè)"<<endl; else /如果不在內(nèi)存塊中 n+; /缺頁(yè)次數(shù)加1 t=Max(page); /返回最近最久未使用的塊號(hào)賦值給t paget.num=pi.num; /進(jìn)行替換 paget.time=0; /替換后時(shí)間置為0 cout<<pi.num<<" "print(page);for(a=0;a<M;a+)if(a!=t)pagea.time+;