頁(yè)面淘汰算法課程設(shè)計(jì)

****學(xué)院

計(jì)算機(jī)科學(xué)系課程設(shè)計(jì)報(bào)告設(shè)計(jì)名稱： 軟件課程設(shè)計(jì) 設(shè)計(jì)題目： 頁(yè)面置換算法模擬程序?qū)W生學(xué)號(hào)： ****專業(yè)班級(jí)：學(xué)生姓名:學(xué)生成績(jī):指導(dǎo)教師（職稱）：課題工作時(shí)間：摘要操作系統(tǒng)(英語(yǔ)；OperatingSystem,簡(jiǎn)稱OS)是一管理電腦硬件與軟件資源的程序，同時(shí)也是計(jì)算機(jī)系統(tǒng)的內(nèi)核與基石。操作系統(tǒng)身負(fù)諸如管理與配置內(nèi)存、決定系統(tǒng)資源供需的優(yōu)先次序、控制輸入與輸出設(shè)備、操作網(wǎng)絡(luò)與管理文件系統(tǒng)等基本事務(wù)。操作系統(tǒng)是管理計(jì)算機(jī)系統(tǒng)的全部硬件資源包括軟件資源及數(shù)據(jù)資源;控制程序運(yùn)行;改善人機(jī)界面;為其它應(yīng)用軟件提供支持等,使計(jì)算機(jī)系統(tǒng)所有資源最大限度地發(fā)揮作用,為用戶提供方便的、有效的、友善的服務(wù)界面。操作系統(tǒng)是一個(gè)龐大的管理控制程序,大致包括5個(gè)方面的管理功能:進(jìn)程與處理機(jī)管理、作業(yè)管理、存儲(chǔ)管理、設(shè)備管理、文件管理。在地址映射過程中,若在頁(yè)面中發(fā)現(xiàn)所要訪問的頁(yè)面不再內(nèi)存中,則產(chǎn)生缺頁(yè)中斷。當(dāng)發(fā)生缺頁(yè)中斷時(shí)操作系統(tǒng)必須在內(nèi)存選擇一個(gè)頁(yè)面將其移出內(nèi)存,以便為即將調(diào)入的頁(yè)面讓出空間。而用來(lái)選擇淘汰哪一頁(yè)的規(guī)則叫做頁(yè)面置換算法(ReplacementAlgorithms)。A.關(guān)鍵詞：操作系統(tǒng)；OPT頁(yè)面置換算法；FIFO先進(jìn)先出的算法；LRR最近最

少使用算；LFR最少訪問頁(yè)面算法;NUR最近最不經(jīng)常使用算法AbstractOperatingsystem(inEnglish;OperatingSystem,referredtoasOS)isacomputerhardwareandsoftwareresourcesmanagementprocedures,butalsothecoreandfoundationofthecomputersystem.Whoarechargedwithoperatingsystemssuchasmemorymanagementandallocation,supplyanddemanddeterminethepriorityofsystemresources,controlinputandoutputdevices,operationandmanagementofnetworkfilesystemsandotherbasicservices.Theoperatingsystemismanagingallthehardwareresourcesofcomputersystemsincludingsoftwareresourcesanddataresources;controlprogramisrunning;toimprovehuman-machineinterface;providesupportforotherapplications,sothatcomputersystemsplayaroleinmaximizingallresourcestoprovideuserswithconvenienteffective,friendlyserviceinterface.Operatingsystemisahugemanagementcontrolprocedures,includingthefiveaspectsofgeneralmanagementfunctions:processandprocessormanagement,operationsmanagement,storagemanagement,devicemanagement,documentmanagement.Intheaddressmappingprocess,iffoundtobeinthepagetoaccessthepagenolongerinmemory,thengenerateapagefault.Whenapagefaultoccurstheoperatingsystemmustselectapageinmemoryoftheiroutofmemoryinordertobetransferredtothepagetomakeroom.Thepageusedtoselectoutwhattherulesarecalledpagereplacementalgorithm(ReplacementAlgorithms).Keywords：Operatingsystem;FirstInputFirstOutput;LeastRecentlyUsed;OPT;LeastFrequentlyUsed;NUR目錄第一章課題背景…………..x關(guān)于頁(yè)面置換算法……………………...x第二章設(shè)計(jì)簡(jiǎn)介及設(shè)計(jì)方案論述………..x程序運(yùn)行平臺(tái)……..………….………..xTOC\o"1-5"\h\z程序的主要功能 xXXXX x第三章詳細(xì)設(shè)計(jì)…………..………………..xXXXX xXXXX x第四章設(shè)計(jì)結(jié)果及分析…………………..………………..xXXXX xXXXX xXXXX x總結(jié) x\o"CurrentDocument"致謝 x\o"CurrentDocument"參考文獻(xiàn) x附錄主要程序代碼 x第一章課題背景關(guān)于頁(yè)面置換算法頁(yè)面置換算法及其分類在地址映射過程中，若在頁(yè)面中發(fā)現(xiàn)所要訪問的頁(yè)面不再內(nèi)存中，則產(chǎn)生缺頁(yè)中斷。當(dāng)發(fā)生缺頁(yè)中斷時(shí)操作系統(tǒng)必須在內(nèi)存選擇一個(gè)頁(yè)面將其移出內(nèi)存，以便為即將調(diào)入的頁(yè)面讓出空間。而用來(lái)選擇淘汰哪一頁(yè)的規(guī)則叫做頁(yè)面置換算法。常見的置換算法有：1.最佳置換算法(OPT)(理想置換算法)2．先進(jìn)現(xiàn)出置換算法(FIFO)：最近最久未使用(LRU)算法Clock置換算法(LRU算法的近似實(shí)現(xiàn))5?最少使用(LFU)置換算法6.頁(yè)面緩沖置換算法關(guān)于頁(yè)面置換算法模擬程序問題的產(chǎn)生在各種存儲(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è)問題。從內(nèi)存中調(diào)出一頁(yè)程序或數(shù)據(jù)送磁盤的對(duì)換區(qū)中，通常，把選擇換出的頁(yè)面的算法稱為頁(yè)面置換算法(ReplacementAlgorithms)。進(jìn)而頁(yè)面置換算法模擬程序能客觀的將其工作原理展現(xiàn)在我們面前。第二章設(shè)計(jì)簡(jiǎn)介及設(shè)計(jì)方案論述2.1程序運(yùn)行平臺(tái)VC++6.0具體操作如下：在VC++6.0的環(huán)境下準(zhǔn)備用時(shí)鐘函數(shù)調(diào)用庫(kù)函數(shù)(#include<time.h>)、取時(shí)鐘時(shí)間并存入t調(diào)用庫(kù)函數(shù)(t二time(NULL))、用時(shí)間t初始化隨機(jī)數(shù)發(fā)生器調(diào)用庫(kù)函數(shù)(srand(t)返回一個(gè)1~10之間的隨機(jī)數(shù)(x=rand()%10+1)。編寫三種算法。2.2程序的主要功能隨機(jī)產(chǎn)生頁(yè)面用隨機(jī)數(shù)方法產(chǎn)生頁(yè)面走向，頁(yè)面走向長(zhǎng)度為L(zhǎng)。FIFO算法該算法總是淘汰最先進(jìn)入內(nèi)存的頁(yè)面，既選擇在內(nèi)存中駐留時(shí)間最久的頁(yè)面予以淘汰。LRU算法在前面幾條指令中使用頻繁的頁(yè)面很可能在后面的幾條指令中頻繁使用。反過來(lái)說(shuō)，已經(jīng)很久沒有使用的頁(yè)面很有可能在未來(lái)較長(zhǎng)的一段時(shí)間內(nèi)不會(huì)被用到。這個(gè)思想提示了一個(gè)可以實(shí)現(xiàn)的算法：在缺頁(yè)發(fā)生時(shí)，淘汰掉最久未使用的頁(yè)。2.2.4LFR算法在缺頁(yè)中斷發(fā)生時(shí)，置換未使用時(shí)間最長(zhǎng)的頁(yè)面。這個(gè)策略稱為L(zhǎng)RU（LeastRecentlyUsed，最近最少使用）頁(yè)面置換算法2.2.5NUR算法NRU在需要淘汰某一頁(yè)時(shí)，從那些最近一個(gè)時(shí)期內(nèi)未被訪問的頁(yè)中任選一頁(yè)淘汰。只要在頁(yè)表中增設(shè)一個(gè)訪問位即可實(shí)現(xiàn)。當(dāng)某頁(yè)被訪問時(shí)，訪問位置1。否則，訪問位置0。系統(tǒng)周期性地對(duì)所有引用位清零。當(dāng)需淘汰一頁(yè)時(shí)，從那些訪問位為零的頁(yè)中選一頁(yè)進(jìn)行淘汰。如果引用位全0或全1,NRU算法退化為FIFO算法。2.3總體設(shè)計(jì)2.31結(jié)構(gòu)圖入口入口輸入頁(yè)面數(shù)

輸入算法產(chǎn)生隨機(jī)數(shù)

J丿FIFO先進(jìn)< ALRRFIFO先進(jìn)< ALRR最近最OPT最佳淘LFR最少訪NUR最近最先出算法V 丿少使用算V 先出算法V 丿少使用算V J%[Ztr/rS_l—汰算法算L )問頁(yè)面算< )不經(jīng)常使輸出命中率4.2主要的函數(shù)k )4.2主要的函數(shù)Input(intm,Prop[L])(打印頁(yè)面走向狀態(tài));voidprint(Pro*page1)(打印當(dāng)前的頁(yè)面)；intSearch(inte,Pro*page1)(尋找內(nèi)存塊中與e相同的塊號(hào))；intMax(Pro*pagel)(尋找最近最長(zhǎng)未使用的頁(yè)面)；intCount(Pro*page1,inti,intt,Prop[L])(記錄當(dāng)前內(nèi)存塊中頁(yè)面離下次使用間隔長(zhǎng)度)；intmain()(主函數(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è)1~10之間的隨機(jī)數(shù)第三章詳細(xì)設(shè)計(jì)FIFO（先進(jìn)先出）設(shè)計(jì)原理：需要進(jìn)行頁(yè)面置換，即把內(nèi)存中裝入最早的那個(gè)頁(yè)面淘汰換入當(dāng)前的頁(yè)面。算法流程圖開始

開始示Yi++頁(yè)面走向存入數(shù)組p[]中，內(nèi)存塊用page[]表初始化為0當(dāng)刖p[]中弟i個(gè)元素是否已在內(nèi)存N示Yi++頁(yè)面走向存入數(shù)組p[]中，內(nèi)存塊用page[]表初始化為0當(dāng)刖p[]中弟i個(gè)元素是否已在內(nèi)存NPage[]是否有空卄Y把page[]中取先裝入的頁(yè)面置換出去.i++把p[i]的內(nèi)容直接裝入最上面一個(gè)空內(nèi)存塊，i++N輸出當(dāng)前內(nèi)存塊狀態(tài)結(jié)束圖4-1FIFO算法流程圖代碼：if(c==l)//FIFO頁(yè)面置換{n=0;******************************************cout<<""<<endl;******************************************cout<<endl;

cout<<"FIFOcout<<endl;

cout<<"FIFO算法頁(yè)面置換情況如下:"<<endl;cout<<endl;cout<<"cout<<endl;cout<<"******************************************"<<endl;while(i<m){if(Search(p[i].num,page)>=O)//當(dāng)前頁(yè)面在內(nèi)存中{cout<<p[i].num<<"";//輸出當(dāng)前頁(yè)p[i].num

存中cout<<"不缺頁(yè)"<<endl;存中i++；//i加1}else//當(dāng)前頁(yè)不在內(nèi)存中{if(t==M)t=0;else{n++;//缺頁(yè)次數(shù)加1page[t].num=p[i].num; //把當(dāng)前頁(yè)面放入內(nèi)cout<<p[i].num<<"";print(page); //打印當(dāng)前頁(yè)面t++; //下一個(gè)內(nèi)存塊i++; //指向下一個(gè)頁(yè)面}}}cout<〈"缺頁(yè)次數(shù)："〈〈n〈〈" 缺頁(yè)率："<<n/m<<endl;}LRU（最近最久未使用）設(shè)計(jì)原理：當(dāng)需要淘汰某一頁(yè)時(shí)，選擇離當(dāng)前時(shí)間最近的一段時(shí)間內(nèi)最久沒有使用過的頁(yè)先淘汰該算法的主要出發(fā)點(diǎn)是，如果某頁(yè)被訪問了，則它可能馬上還要被訪問?；蛘叻催^來(lái)說(shuō)如果某頁(yè)很長(zhǎng)時(shí)間未被訪問，則它在最近一段時(shí)間也不會(huì)被訪問。算法流程圖：

{{n=0;cout<<"******************************************"<<endl;cout<<endl;cout<<"LRU算法頁(yè)面置換情況如下:"<<endl;cout<<endl;cout<<"******************************************"<<endl;while(i<m){inta;t=Search(p[i].num,page);if(t>=0) //如果已在內(nèi)存塊中{page[t].time=0;{page[t].time=0;//把與它相同的內(nèi)存塊的時(shí)間置0////其它的時(shí)間加1

//如果不在內(nèi)存塊中//返回最近最久未使用的塊號(hào)//進(jìn)行替換//替換后時(shí)間置為0//其它的時(shí)間加1缺頁(yè)率："<<n/m<<endl;for(a=0;a<M;a++)if(a!=t)page[a].time++;cout<<p[i].num<<"";cout<<"不缺頁(yè)"<<endl;}else{n++;//缺頁(yè)次數(shù)加1t=Max(page);賦值給tpage[t].num=p[i].num;page[t].time=0;cout<<p[i].num<<""print(page);for(a=0;a<M;a++)if(a!=t)page[a].time++;}i++;}cout<〈"缺頁(yè)次數(shù)："<<n<<"}OPT（最佳置換算法）設(shè)計(jì)原理：需要進(jìn)行頁(yè)面置換，把內(nèi)存中以后一段時(shí)間都不使用或是使用時(shí)間離現(xiàn)在最遠(yuǎn)的頁(yè)面換出。

代碼：{"<<endl;"<<endl;圖4-3OPT代碼：{"<<endl;"<<endl;if(c==3)//OPT頁(yè)面置換n=0;cout<<"******************************************cout<<endl;cout<<" OPT算法置換情況如下："<<endl;cout<<endl;cout<<" ******************************************while(i<m){if(Search(p[i].num,page)>=0) //如果已在內(nèi)存塊中{cout<<p[i].num<<"";cout<<"不缺頁(yè)"<<endl;i++;}else //如果不在內(nèi)存塊中{inta=0;for(t=0;t<M;t++)if(page[t].num==0)a++; //記錄空的內(nèi)存塊數(shù)if(a!=0) //有空內(nèi)存塊{intq=M;for(t=0;t<M;t++)if(page[t].num==0&&q>t)q=t;//把空內(nèi)存塊中塊號(hào)最小的找出來(lái)page[q].num=p[i].num;n++;cout<<p[i].num<<"";print(page);i++;}else{inttemp=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);s=t;}//把找到的塊號(hào)賦給spage[s].num=p[i].num;n++;cout<<p[i].num<<"";

print(page);i++;}}cout<〈"缺頁(yè)次數(shù)："〈〈n〈〈" 缺頁(yè)率："<<n/m<<endl;}第四章設(shè)計(jì)結(jié)果及分析4.1實(shí)現(xiàn)結(jié)果程序在運(yùn)行的情況下，進(jìn)入主界面輸入菜單，如圖3-3所示輸入14：

X*C:\Docu>entsandSettIngs\AdAinistrator\桌面\Debug\os.eze輸入實(shí)際頁(yè)面走向長(zhǎng)度L<15<=IX=20〉：14際頁(yè)面長(zhǎng)度須在15—20之間;請(qǐng)重新輸入L:圖4-5輸入14后的輸出圖輸入25：CAC:\Docu>entsandSettings\Ad>inistrator\桌面\Debug\os.ezeCA「瞬|麟雅躥邂典25實(shí)際就面長(zhǎng)度須在15~20^;請(qǐng)重ffWAL：圖5-6輸入數(shù)據(jù)25后輸出圖輸入數(shù)據(jù)18：c**C:\Docu>entsandSettings\Ad?inistrator\桌面\Debug\os.eze面須須7存貝度度：內(nèi)際用賣E-E-機(jī)可只賁隨入W面須須7存貝度度：內(nèi)際用賣E-E-機(jī)可只賁隨入W際留輸走在在￥頁(yè)両1515151L<到；牙三00(醫(yī)229m<~~0麹■■■■4LL61I1AI1A820^^?=二B--二B-_<-0=L請(qǐng)請(qǐng)1:-J-J2XZ54012358211圖5-7輸入數(shù)據(jù)18后的輸出圖輸入數(shù)據(jù)：2518132104514LL62518132104514LL61入入864>:幫石0::27mm-二E--二E二\\<33027.7-=L請(qǐng)請(qǐng)1IE-E25>聾7>一>一_■33罷寫<3請(qǐng)請(qǐng)229m5E..WW1(11-重重229TZ0>15151黴可可55-序面須須7存~~換奐奐程際4^用雜頁(yè)面面機(jī)可血血頁(yè)體鍵天賈隨入塊塊FOUS誣它W際留聾存FILROP其塁島兩1:2:3:按圖5-8輸出圖進(jìn)入FIFO頁(yè)面置換：*C:\Docu>entsandSettin.gs\AdA±n.istrator\桌面ID71081010獻(xiàn)貢次數(shù)：15l：FIFO^EfLP=lru￥面胃^幹OPT頁(yè)面番險(xiǎn)其它犍纟彝FIFO算法頁(yè)面置換情況如下:3313缺貢率：0.8333337000790079100不缺貢9103191032103不缺頁(yè)12731276276不缺貢8578518515121021043圖5-9FIFO的輸出圖選2，進(jìn)入LRU頁(yè)面置換：710107810107000ocusentsamettings\AdMinistratorXDebugXoP7900711131104缺頁(yè)次數(shù)：1679100不缺頁(yè)791031910319231102311027610276108?不缺頁(yè)6586581：FIFO貝面e：lru￥面當(dāng)按其它鍵纟害缺頁(yè)率：0.888889LRU算法貢面置換情況如下:圖5-10LRU的輸出圖輸入3，進(jìn)入OPT頁(yè)面置換：圖5-11OPT的輸出圖通過對(duì)頁(yè)面置換算法模擬程序的程序設(shè)計(jì)，讓我對(duì)虛擬頁(yè)式存儲(chǔ)管理有了更深的了解。剛開始拿到這個(gè)題目覺得很難，不知道該怎么下手，因?yàn)槭亲约旱谝淮斡肅語(yǔ)言編寫操作系統(tǒng)程序。但是搞懂了頁(yè)面置換的思想以后，對(duì)編程就有了一定的思路。經(jīng)過幾天的編寫，程序也終于寫出來(lái)啊。但是卻遇到了許多困難，程序