頁面淘汰算法實驗報告

操作系統(tǒng)實驗報告課題：頁面淘汰算法專業(yè)：班級：學號：姓名：年月日目錄HYPERLINK一實驗目的 ……………………3HYPERLINK二實驗要求 ……………………3HYPERLINK三背景知識 ……………………3四HYPERLINK總體設計 ……………………4HYPERLINK五詳細設計 ……………………7HYPERLINK六運行結(jié)果分析 ………………9HYPERLINK七心得體會 ………13HYPERLINK八參考文獻………14HYPERLINK附：源代碼………15一、實驗目的本實驗主要對操作系統(tǒng)中請求分頁式內(nèi)存管理及其應用的一些關(guān)鍵算法進行模擬。學生通過設計與實現(xiàn)Clock算法，能夠加強對相應理論的理解，并對了解操作系統(tǒng)內(nèi)部的基本處理原理與過程也有很多益處。利用簡單的數(shù)據(jù)結(jié)構(gòu)，模擬實現(xiàn)操作系統(tǒng)中的頁面置換機制，通過寫程序模擬實現(xiàn)上述三種內(nèi)存頁面置換算法，使學生進一步掌握內(nèi)存頁面置換的方法。對操作系統(tǒng)中內(nèi)存的管理有一個實踐上的認識。1、用C語言編寫OPT、FIFO、LRU三種置換算法。2、熟悉內(nèi)存分頁管理策略。3、了解頁面置換的算法。4、掌握一般常用的調(diào)度算法。5、根據(jù)方案使算法得以模擬實現(xiàn)。6、鍛煉知識的運用能力和實踐能力。二、實驗要求設計隨機頁面序號產(chǎn)生程序，并說明隨機的性能和其性能可能對算法的影響編寫頁面淘汰算法(FIFO、OPT、LRU)結(jié)果數(shù)據(jù)的顯示或提取結(jié)果數(shù)據(jù)的分析幾點說明：設計并繪制算法流程，附加說明所需的數(shù)據(jù)結(jié)構(gòu)如何標記時間的先后、最久的將來、最久未被使用描述Clock算法的基本原理、必要的數(shù)據(jù)結(jié)構(gòu)、算法執(zhí)行流程圖、編碼實現(xiàn)。1）初始化：輸入作業(yè)可占用的總頁框數(shù)，初始化置空。2）輸入請求序列：輸入一個作業(yè)頁號訪問請求序列，依次占用相應頁框，直至全部占用；3）Clock算法：當頁框全部占用后，對于后續(xù)新的頁號訪問請求，執(zhí)行Clock算法，淘汰1個頁面后裝入新的頁號。4）顯示當前分配淘汰序列：顯示淘汰的頁號序列。三、背景知識：在操作系統(tǒng)當中，在進程運行過程中，若其訪問的頁面不在內(nèi)存中而需把他們調(diào)入內(nèi)存，但內(nèi)存已無空閑空間時，為了保證該進程能夠正常的運行，系統(tǒng)必須從內(nèi)存中調(diào)出一頁程序或數(shù)據(jù)送到磁盤的兌換區(qū)中，但是應該是哪個頁面被調(diào)出，需根據(jù)一定的算法來確定。通常，我們把這一類的算法稱為“頁面置換算法”，頁面置換算法執(zhí)行效率的高低，往往直接影響到操作系統(tǒng)的性能。內(nèi)存頁面置換算法：<1>先進先出調(diào)度算法（FIFO）先進先出調(diào)度算法根據(jù)頁面進入內(nèi)存的時間先后選擇淘汰頁面。本算法實現(xiàn)時需要將頁面按進入內(nèi)存的時間先后組成一個隊列，每次置換掉最早進入的頁面。這是最早出現(xiàn)的置換算法，該算法總是淘汰最先進入內(nèi)存的頁面，即選擇在內(nèi)存中駐留時間最長的頁面換出，予以淘汰。該算法實現(xiàn)簡單只需把一個進程已調(diào)入內(nèi)存的頁面，按先后次序鏈接成一個隊列，并設置一個指針，稱為替換指針，使它總是指向最老的頁面。但該算法與進程實際運行的規(guī)律不相適應，因為在進程中，有些頁面經(jīng)常被訪問，比如，含有全局變量、常用函數(shù)、例程等的頁面，F(xiàn)IFO算法并不能保證這些頁面不被淘汰。<2>最近最久未使用的置換算法（LRU）最近最久未使用的置換算法，是根據(jù)頁面調(diào)入內(nèi)存后的使用情況進行決策的。由于無法預測各頁面將來的使用情況，只能利用“最近的過去”作為“最近的將來”的近似，因此，LRU置換算法是選擇最近最久未使用的頁面予以淘汰。該算法賦予每個頁面一個訪問字段，用來記錄一個頁面自上次被訪問以來所經(jīng)歷的時間t,，當須淘汰一個頁面時，選擇現(xiàn)有頁面中其t值最大的，即最近最久未使用的頁面予以淘汰。<3>最佳置換算法（OPT）最佳置換算法是可以說的一種理想的頁面置換算法，它是由Belady于1966年提出的一種理論上的算法。其所選擇的被淘汰頁面，將是以后永不使用的或許是在最長(未來)時間內(nèi)不再被訪問的頁面。采用最佳置換算法，通?？杀ＷC獲得最低的缺頁率。但由于人目前還無法預知一個進程在內(nèi)存的若干個頁面中，哪一個頁面是未來最長時間內(nèi)不再被訪問的，因而該算法是無法實現(xiàn)的，但可以利用此算法來評價其它算法。<4>時鐘頁面置換算法時鐘頁面置換算法是把所有的頁面都保存在一個類似鐘面的環(huán)形鏈表中，一個表針指向最老的頁面，如圖所示。當發(fā)生缺頁中斷時，算法首先檢查表針指向的頁面，如果它的R位是0就淘汰該頁面，并把新的頁面插入這個位置，然后把表針前移一個位置；如果R位是1就清除R位并把表針前移一個位置，重復這個過程直到找到了一個R位為0的頁面為止。總體設計根據(jù)要求設計頁面淘汰算法的活動圖運行程序進入主頁面，在正上方，已經(jīng)通過隨機生成函數(shù)生成了頁面號，在其下方，顯示可選項：0、退出程序1、FIFO算法2、OPT算法3、LRU算法。根據(jù)需要，選擇相應的法，程序自動生成頁面淘汰的先后順序，以及置換次數(shù)和缺頁次數(shù)，并打印在下方，執(zhí)行完以后，再次進入主頁面，到輸入0，退出程序。算法流程圖FIFO算法流程圖：OPT算法流程圖LRU算法流程圖：詳細設計（一）、設計思想最佳置換算法(OPT)用數(shù)組Temppages[]存儲當前物理塊中頁面信息，數(shù)組TimeArry[]存儲當前在物理塊中的頁面的獲得內(nèi)存時的時間，當頁面不在內(nèi)存中時，根據(jù)當前已獲得物理塊數(shù)的頁面在所有的頁面當中將來不在請求內(nèi)存或者很少請求內(nèi)存的情況進行置換先進先出算法(FIFO)用數(shù)組Temppages[]存儲當前物理塊中頁面信息，變量temp記錄內(nèi)存中物理塊頁面置換狀態(tài)，每進行一次置換，頁面置換狀態(tài)變化，便于下一次的置換。最近最久未使用算法(LRU)用數(shù)組Temppages[]存儲當前物理塊中頁面信息，數(shù)組TimeArry[]存儲當前在物理塊中的頁面的獲得內(nèi)存時的時間，當頁面不在內(nèi)存中時，選擇TimeArry[]數(shù)組中值最小并且對應物理塊中的頁面進行置換。（二）、設計步驟首先根據(jù)程序要求，我們分別定義兩個宏，用以存放我們的物理塊數(shù)目以及頁面數(shù)目，再定義一個結(jié)構(gòu)體，用以物理塊的存儲，代碼如下：#defineMemPageCount4#defineInstructionCount20structpage{ intserial;//頁面號 inttime;//時間計數(shù)}mempage[MemPageCount];其次，建立主函數(shù)，根據(jù)程序需要，定義相應的變量，建立switch語句，用以算法的選擇，部分定義如下：inti,j,k,m,n; //指令頁面集合,可以考慮讓頁面指令集合隨機生成 intinstruction[InstructionCount]; intmem_counter;//內(nèi)存頁面集合計數(shù)器 intswitch_counter;//置換次數(shù)最后，根據(jù)算法流程圖，實現(xiàn)相應算法的代碼編寫。（三）、算法流程設計主函數(shù)流程:STEP1:輸入分配的頁框數(shù)，頁面訪問次數(shù)和要訪問的頁面號序列STEP2:內(nèi)存頁面初始化。內(nèi)存中頁面的數(shù)據(jù)結(jié)構(gòu)為單循環(huán)鏈表，含有頁號值yehao和訪問位值a。開始時頁號均為-1，訪問位為0.STEP3：測試數(shù)據(jù)。具體算法是依要訪問的頁面號，調(diào)用find()函數(shù)查找是否已經(jīng)存在于內(nèi)存中。若存在，則修改其訪問位為1.若不存在，觸發(fā)缺頁中斷，調(diào)用tihuan()函數(shù)。最后，打印當前內(nèi)存狀態(tài)。如此循環(huán)直至測試串都訪問完畢。主要函數(shù)實現(xiàn)Makenode(double)函數(shù)：用于初始化一個節(jié)點。Find（double）函數(shù)：依據(jù)輸入的頁號，查詢內(nèi)存中是否已存在此頁面。若存在返回值1，不存在返回值0.Tihuan（double）函數(shù)：在發(fā)生缺頁中斷時，時鐘指針查找訪問位為0的頁面進行替換，指針掃過的頁面訪問位置0，新加入的頁面訪問位置1。替換后指針下移。Print_state()函數(shù)：打印當前內(nèi)存中存在的頁面的狀態(tài)以及當前時鐘指針所指向的頁面位置。測試數(shù)據(jù)估計輸入：輸入分配的頁框數(shù)3輸入頁面訪問次數(shù)15輸入要訪問的頁面號序列342643743634846 輸出（僅最后一項）：結(jié)果分析以下是clock算法對應輸入頁面號序列342643743634846的分析表運行結(jié)果分析：開始界面采用隨機數(shù)產(chǎn)生的結(jié)果2、采用自定義頁面信息產(chǎn)生結(jié)果自定義頁面數(shù)為：15物理塊數(shù)為：4頁面序列為：123456789456708根據(jù)結(jié)果，我們不難發(fā)現(xiàn)，OPT算法，是三種算法中性能最好的，它的置換次數(shù)最少，LRU次之，，不過性能最差的還是FIFO，由于缺頁率=缺頁次數(shù)/總的頁面數(shù)，所以我們不難發(fā)現(xiàn)，隨著物理塊數(shù)的增加，缺頁率都相應有所增加，但是OPT算法的增加較為明顯，即產(chǎn)生了belady現(xiàn)象。七、心得體會：這次課程設計，讓我對算法的編寫更加的熟練，同時更加了解頁面置換的相關(guān)算法，也提高了我對算法設計的嚴密性，對以后的程序設計有很大幫助。我們不僅對常用的算法進行了編寫，還對一些理想的算法也進行了編寫，并且通過適當?shù)姆椒?，得以了驗證。就該程序而言，隨機性使得程序出現(xiàn)了更多的可能性，為我們驗證算法提供很大的方便，電腦自動分配，大大的節(jié)約了我們的時間，但是我們通過實驗不難發(fā)現(xiàn)，如果所設的頁面項目過大，也會影響我們算法的性能執(zhí)行效率。對我們所涉及的算法，讓我有很大的感觸。在FIFO算法中，無論有無發(fā)生缺頁或者置換，都需要對每個在內(nèi)存中的頁面的time值進行增加操作，以保持最先進入的那個頁面的time值是最大的；一個新進來的頁面，其time值設置為0。當然，該算法也可以通過隊列結(jié)構(gòu)來實現(xiàn)，利用隊列的先進先出（FIFO）特性完成，無需設置time字段。distance用于記錄內(nèi)存物理塊集合中每個頁面距離再次被使用的頁面跨度，缺省值為9999，如果某個頁面在后續(xù)指令集合中不再出現(xiàn)，則用最大值9999缺省取代；如果頁面再次被使用，則兩次使用所跨的頁面數(shù)，為頁面跨度。用最大頁面跨度表示以后永不使用或未來最長時間內(nèi)不再被訪問。在LRU算法中，無論是否發(fā)生缺頁或者置換，除了命中（剛剛被訪問過的頁面）頁面time值清零之外，其它所有內(nèi)存中的頁面的time值都加一，以保證最近剛剛被訪問的頁面的time值最小，相應time值最大的頁面就是最近最久沒有被訪問的頁面。上述兩種算法，是我們在進程調(diào)度中使用最多的兩種，你可能會問？為什么要使用進程調(diào)度，因為當我們的程序在運行時，若所訪問的頁面不再內(nèi)存而需把它調(diào)入內(nèi)存，但內(nèi)存已無空閑空間，這時，為了保證該程序能正常運行，系統(tǒng)就必須從內(nèi)存中調(diào)出一頁程序或數(shù)據(jù)送到磁盤的兌換區(qū)中，但應將那個頁面調(diào)出，我們就必須根據(jù)一定的算法來實現(xiàn)。所以，一個頁面置換算法的好壞，將直接影響到我們系統(tǒng)的性能。相比較而言，我們最常用的是LRU算法，因為它是根據(jù)頁面調(diào)入內(nèi)存后的使用情況就行決策的，比FIFO算法要好很多。通過與其他算法的比較，加深對clock算法的理解,也了解了他們的異同之處。Clock算法其實是一種改進的第二次機會算法，它通過設置訪問位，找到最早最不常訪問的頁面，即標號為0的頁面。之所以叫clock算法，依我理解是將內(nèi)存中的排列順序附上時間的概念，clock指針掃過的頁面要將他們1置0就是基于這個思想，因為他們都是沒被訪問的，且在時鐘上的排列按照訪問時間順序。這樣就保證了每次替換的都是最早進來的且不最常訪問的頁面。八、參考文獻【1】《計算機操作系統(tǒng)》（第三版）湯小丹、梁紅兵、湯子瀛、哲鳳屏等西安電子科技大學出版社2007-05

【2】《C++Primer中文版》（第4版）（美）StanleyB.Lippman

等著

李師賢等譯.人民郵電出版社,2006-03-01【3】《C++Primer習題解答》（第4版）蔣愛軍，李師賢，梅曉勇

著人民郵電出版社2007-02-01【4】《現(xiàn)代操作系統(tǒng)》（原書第3版）塔嫩鮑姆（Tanenbaum.A.S），陳向群，馬洪兵

著機械工業(yè)出版社2009-07-01【5】《計算機操作系統(tǒng)教程》張堯?qū)W，史美林，張高清華大學出版社2006-10-01【6】《數(shù)據(jù)結(jié)構(gòu)（STL框架）》王曉東

著清華大學出版社2009-09-01附：源代碼#include<stdio.h>#include<stdlib.h>#include<time.h>#defineM_size100intpageNum=0;///全局變量頁面數(shù)intpages[M_size];///存儲頁號intTemppages[M_size];///輔助數(shù)組intTimeArry[M_size];//記錄頁在內(nèi)存中的時間intmethod;///產(chǎn)生結(jié)果的方法intAlgorithmStyle;//輔助變量，用于選擇算法類型intBlock;//記錄物理塊數(shù)intstart;//輔助變量voidInition()//初始化函數(shù){ inti; intt=time(NULL);///產(chǎn)生隨機數(shù)種子 srand(t);///用t初始化隨機數(shù)種子 pageNum=rand()%10+8;///隨機產(chǎn)生4-14之內(nèi)的整數(shù)，保證頁面數(shù)在4-14之內(nèi) for(i=0;i<pageNum;i++) { pages[i]=rand()%10+1;///初始化頁號，初始值在1-10之內(nèi) } Block=4;//初始化物理塊數(shù)位3}voidprintDefaltResult()///缺省參數(shù)顯示{ inti; printf("缺省頁面數(shù)為:%d\n",pageNum); printf("缺省頁號分別為:"); for(i=0;i<pageNum;i++) { printf("%d",pages[i]); } printf("\n"); printf("可用物理塊數(shù)為:%d\n",Block); printf("按任意鍵繼續(xù):"); getchar(); }voidPrintCustomInfo()//顯示用戶自定義參數(shù){ inti; printf("自定義頁面數(shù)為:%d\n",pageNum); printf("自定義頁號分別為:"); for(i=0;i<pageNum;i++) { printf("%d",pages[i]); } printf("\n"); printf("可用物理塊數(shù)為:%d\n",Block); printf("按任意鍵繼續(xù):\n"); getchar();}voidprintUserInfo()///顯示個人信息{ system("color0B"); printf("┏━━━━━━━━━━━━━━━━━━━━━━━━━┓\n"); printf("┃頁面淘汰算法┃\n"); printf("┃學號：┃\n"); printf("┃班級：┃\n"); printf("┃姓名：┃\n"); printf("┣━━━━━━━━━━━━━━━━━━━━━━━━━┫\n"); printf("按任意鍵開始操作:"); getchar(); system("cls"); system("color0B");}voidChioceDealmethod()//選擇解決問題的方法"1"選擇缺省值，"2"選擇自定義值{ printf("┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓\n"); printf("┃1、使用默認值產(chǎn)生結(jié)果2、自定義頁數(shù)和頁號┃\n"); printf("┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛\n請輸入你的選擇:\n"); scanf("%d",&method); system("color0F");}voidPrintNotWithoutPages()//顯示一定不用換頁的部分{ start=Block; inti,j,k=0,key=0; for(i=0;i<start;i++) { intflag=0; for(j=0;j<=i-1;j++) { if(Temppages[j]==pages[i]) { TimeArry[j]=i; flag=1; start=start+1; key++; } } if(flag==0) { TimeArry[k]=i; Temppages[k]=pages[i]; k++; for(j=0;j<=i-key;j++) { printf("%-7d",Temppages[j]); } printf("\n"); } }}voidPrintResult()//顯示每次換頁后的結(jié)果{ inti; for(i=0;i<Block;i++) { printf("%-7d",Temppages[i]); } printf("\n");}voidFIFODealQuestion()//先進先出算法{ inti,j; intWithOutPages=0;//記錄缺頁數(shù) printf("FIFO(先進先出算法)結(jié)果顯示：\n"); PrintNotWithoutPages(); inttemp=0; for(i=start;i<pageNum;i++) { if(temp==Block) { temp=0; } intkey=0; for(j=0;j<Block;j++)//判斷該頁是否在物理塊中 { if(Temppages[j]==pages[i]) { key=1; break; } } if(key==0)//如果不在 { Temppages[temp]=pages[i]; temp++; WithOutPages++; PrintResult(); } } printf("置換次數(shù)為：%d,頁面總數(shù)為：%d,置換率為:",WithOutPages,pageNum); doublere=((double)WithOutPages)/((double)pageNum); printf("%.2lf\n",re); printf("缺頁次數(shù)為：%d,頁面總數(shù)為：%d,缺頁率為:",WithOutPages+Block,pageNum); re=((double)(WithOutPages+Block))/((double)pageNum); printf("%.2lf\n",re);}voidLRUDealQuestion()//最近最久未使用算法{ inti,j; intWithOutPages=0;//記錄缺頁數(shù) printf("LRU(最近最久未使用算法)結(jié)果顯示：\n"); PrintNotWithoutPages(); for(i=start;i<pageNum;i++) { intkey=0; for(j=0;j<Block;j++)//判斷該頁是否在物理塊中 { if(Temppages[j]==pages[i]) { key=1; TimeArry[j]=i;//更新時間 break; } } if(key==0)//若該頁不在內(nèi)存中 { WithOutPages++; intmin=TimeArry[0]; intflag=0; for(j=1;j<Block;j++) { if(min>TimeArry[j]) { min=TimeArry[j];//找到最久的頁面 flag=j; } } TimeArry[flag]=i;//記錄時間 Temppages[flag]=pages[i]; PrintResult(); } } printf("置換次數(shù)為：%d,頁面總數(shù)為：%d,置換率為:",WithOutPages,pageNum); doublere=((double)WithOutPages)/((double)pageNum); printf("%.2lf\n",re); printf("缺頁次數(shù)為：%d,頁面總數(shù)為：%d,缺頁率為:",WithOutPages+Block,pageNum); re=((double)(WithOutPages+Block))/((double)pageNum); printf("%.2lf\n",re);}voidOPTDealQuestion(){ inti,j,l; intWithOutPages=0;//記錄缺頁數(shù) printf("OPT(最佳置換算法)結(jié)果顯示：\n"); PrintNotWithoutPages(); for(i=start;i<pageNum;i++) { intkey=0; for(j=0;j<Block;j++)//判斷該頁是否在內(nèi)存中 { if(Temppages[j]==pages[i]) { TimeArry[j]=i; key=1; break; } } if(key==0)//如果該頁不在內(nèi)存中 { WithOutPages++;//缺頁數(shù)加1 //得到各物理塊下一次訪問的時間 for(j=0;j<Block;j++) { for(l=i+1;l<pageNum;l++) { if(Temppages[j]==pages[l]) { break; } } TimeArry[j]=l; } //得到下一次訪問時間最長的一個頁面，將當前頁與其換掉 intmin=TimeArry[0]; intflag=0; for(j=1;j<Block;j++) { if(TimeArry[j]>min) { min=TimeArry[j]; flag=j; } } Temppages[flag]=pages[i]; TimeArry[flag]=i; PrintResult(); } } printf("置換次數(shù)為：%d,頁面總數(shù)為：%d,置換率為:",WithOutPages,pageNum); doublere=((double)WithOutPages)/((double)pageNum); printf("%.2lf\n",re); printf("缺頁次數(shù)為：%d,頁面總數(shù)為：%d,缺頁率為:",WithOutPages+Block,pageNum); re=((double)(WithOutPages+Block))/((double)pageNum); printf("%.2lf\n",re);}voidChioceAlgorithm(intAlgorithmStyle){ switch(AlgorithmStyle) { case1: FIFODealQuestion();//先進先出算法解決問題 break; case2: LRUDealQuestion();//最近最久未使用算法解決問題 break; case3: OPTDealQuestion();//最佳置換算法解決問題 break; case4: FIFODealQuestion();//先進先出算法解決問題 LRUDealQuestion();//最近最久未使用算法解決問題 OPTDealQuestion();//最佳置