.摘 要 在linux中，為了提高內存利用率，提供了內外存進程對換機制，內存空間的分配和回收均以頁為單位進行，一個進程只需要將其一部分調入內存便可運行；當操作系統發生缺頁中斷時，必須在內存選擇一個頁面將其移出內存，以便為即將調入的頁面讓出空間。因而引入一種用來選擇淘汰哪一頁的算法頁面置換算法。頁面置換算法是操作系統中虛擬存儲管理的一個重要部分。頁面置換算法在具有層次結構存儲器的計算機中，為用戶提供一個比主存儲器容量大得多的可隨機訪問的地。常見的頁面置換算法有先來先服務算法(FIFO)，最近最久未使用算法(LRU)和最佳適應算法(OPT)。關鍵字：操作系統；FIFO；LRU；OPT；Linux.目 錄1 緒論11.1 設計任務11.2設計思想11.3設計特點11.4基礎知識21.4.1 先進先出置換算法(FIFO)21.4.2 最近最久未使用算法(LRU)31.4.3最佳置換算法(OPT)32 各模塊偽代碼算法42.1偽代碼概念42.2偽代碼算法42.2.1主函數偽代碼算法42.2.2延遲時間函數偽代碼算法62.2.3 FIFO算法的偽代碼72.2.4 LRU算法的偽代碼72.2.5 OPT算法的偽代碼103 函數調用關系圖123.1函數聲明123.1.1主要算法函數123.1.2輔助函數123.2程序函數調用關系圖134 測試結果144.1數據初始化144.2頁面調度算法144.2.1先進先出算法154.2.2最近最久未使用LRU154.2.3最佳置換算法OPT175 源程序186 設計總結30參考文獻31致 謝321 緒論1.1 設計任務 1、了解UNIX的命令及使用格式，熟悉UNIX/LINUX的常用基本命令，練習并掌握UNIX提供的vi編輯器來編譯C程序，學會利用gcc、gdb編譯、調試C程序。 2、設計一個虛擬存儲區和內存工作區，并使用最佳淘汰算法（OPT）、先進先出算法（FIFO）、最近最久未使用算法（LRU）計算訪問命中率。（命中率頁面失效次數頁地址流長度=1-缺頁率）1.2設計思想 在進程運行過程中，若期所有要訪問的頁面不在內存，而需把它們調入內存，但內存已無空閑空間時，為了保證進程正常進行，系統必須從內存中調出一頁程序或數據送到磁盤的對換區中。但應將哪個頁面調出，須根據一定的算法來確定。通常，把選擇換出頁面的算法稱為頁面置換算法。置換算法的好壞將直接影響到系統的性能。 不適當的算法可能會導致進程發生“抖動”，即剛被換出的頁很快又要被訪問，需要將它重新調入，此時又需要再選一頁調出；而此剛被調出的頁很快又被訪問，有需將它調入，如此頻繁地更換頁面，以致一個進程在運行中把大部分的時間都花費在頁面置換工作上。通過模擬實現請求頁式存儲管理的幾種基本頁面置換算法，了解虛擬存儲技術的特點，掌握虛擬存儲請求頁式存儲管理中幾種基本頁面置換算法的基本思想和實現過程，并比較它們的效率。改進頁面置換算法,可以降低頁面失敗率,從而有效地提高系統性能。從理論上講，應將那些以后不再會訪問的頁面置換出來，或把那些在較長時間內不會再訪問的頁面調出。目前已有多種置換算法，它們都試圖更接近于理論上的目標。1.3設計特點 本設計作品主要用C語言編寫而成，結構簡單，語言易懂，條理清晰。本作品兼容性也非常的高，可以在各種可以編譯C語言的編譯軟件上運行，并能夠在cygwin中運行，經多次調試，暫時未發現有何不足。本程序的另一個優點是，程序可以計算大數量數據。如，本程序可以計算的最大物理塊個數達到了10000個，用戶輸入的頁面引用串個數也能達到10000個以上。但是，實際生活中系統的物理塊個數一般不會達到10000個。因此，我們在提示用戶輸入頁面引用串個數是，只提示最大輸入100個。但是代碼不足在于使用到了較多的static全局變量使得整個代碼質量不是很好，而且也只是簡單的根據算法設計來模擬實現整個過程。我通過先查找該頁面是否在頁幀中存在，若不存在則需要頁面置換，通過刷新每個頁幀的time值來得到每次的最小值來進行頁面的置換，最小值即代表著最近最少使用的頁面。 經過測試，這個系統已經達到了題目中的全部要求。這個程序有很多優點有一個是界面簡明，簡潔明了的程序菜單；一個是智能化的模塊設計，減少了許多人工操作，如功能模塊操作結束后，均會返回主菜單進行下一模板的運行，并提示是否再進行類似的操作，這樣給用戶帶來了操作的方便，大大提高了學生選課的效率還有就是提示語言既簡潔又明確，層次分明等等；當然也有缺點如程序仍然存在不合理的地方，例如程序某些部分輸入錯誤不能立刻返回改正；信息表達方式不豐富，比較單一，缺少圖片、音樂等元化表達方式。 FIFO算法總是選擇在內存駐留時間最長的一頁將其淘汰。這種算法基于CPU按線性順序訪問地址空間的這個假設上，許多時候，CPU不是按吸納型順序訪問地址空間的。所以，那些在內存中停留時間最長的頁往往被訪問到。這就造成FIFO算法的缺頁率不太理想。并且，FIFO還有一個缺點就是Belady奇異現象。實現FIFO算法無需硬件提供新的幫助，只采用循環數組管理駐留集即可。OPT算法被譽為“最佳算法”，因為他淘汰下次訪問距當前最遠的那些頁中序號最小的一頁。所以，OPT算法得出的缺頁率是最小的。但是，OPT算法在使用前必須先得知整個訪問串，這很難實現。因此，OPT算法知識一種概念中的算法。LRU算法的實現耗費較高，并且需要硬件的支持，但是效果較好。就缺頁率而言，OPT算法最佳，FIFO算法最差。1.4基礎知識1.4.1 先進先出置換算法(FIFO) FIFO算法是最早出現的算法。該算法總是淘汰最先進入內存的頁面，即選擇在內存駐留時間最久的頁面予以淘汰。該算法實現簡單，只需要把一個進程已調入內存的頁面按先來后次序鏈接成一個隊列，并設置一個指針，稱為替換指針，使它總是指向最老的頁面。但是該算法與進程實際運行的規律不相符合，因為在進程中，有些頁面經常被訪問。1.4.2 最近最久未使用算法(LRU) 選擇最近一段時間最長時間沒有被訪問過的頁面予以淘汰。LRU算法是根據頁面調入內存后的使用情況進行決策。由于無法預測各頁面將來的使用情況，采取“最近的過去”作為“最近的將來”的近似。選擇最近最久未使用的頁面予以淘汰。實現：賦予每個頁面一個方位字段，用來記錄一個頁面自上次被訪問以來所經歷的時間T，當要淘汰一個頁面的，選擇現有頁面中其T值最大的，即最近最久未使用的頁面予以淘汰。1.4.3最佳置換算法(OPT)最佳置換算法所選擇的被淘汰掉的頁面，將是以后永久不再使用的，或許是在最長（未來）時間內不再被訪問的頁面。采用最佳置算法，通常可保證獲得最低的缺頁率。本模擬算法中，最佳頁面置換算法實現所采用的思想是：循環讀入每個頁表項，若該頁表在內存中，則讀取下一個頁表項。若頁表不存在內存中：一種情況是內存不滿，則將頁表放入內存中；若內存塊已滿，剛分別計算內存中各個頁表再次被使用的時間，并將最久不被訪問的調出，放入當前讀入頁表項。.2 各模塊偽代碼算法 根據程序提示，用戶先將需要計算的頁面號引用串，物理塊數量和引用串個數輸入到文件流中。待程序加載數據完成后，用戶繼續選擇頁面置換算法的類型，程序根據用戶輸入的信息來判斷采用哪一種算法進行計算。結構如圖2.1所示。圖 2.1 總體結構圖2.1偽代碼概念 偽代碼（英語：pseudocode），又稱為虛擬代碼，是高層次描述算法的一種方法。使用偽代碼的目的是讓被描述的算法可以容易地以任何一種編程語言（Pascal，C，Java，etc）實現。因此，偽代碼必須結構清晰、代碼簡單、可讀性好，介于自然語言與編程語言之間。以編程語言的書寫形式指明算法職能。使用偽代碼，不用拘泥于具體實現。它是半角式化、不標準的語言。可以把整個算法運行過程的結構用接近自然語言的形式（可以使用任何一種你熟悉的文字，關鍵是把程序的意思表達出來）描述出來。2.2偽代碼算法2.2.1主函數偽代碼算法 該程序是按自上而下，自頂向下的設計思想進行設計的。程序各個功能的實現之間的聯系采用函數調用與函數嵌套。main()函數是整個程序的入口，程序的開始就是從這里開始的，然后通過main()函數調用其他函數來實現各個功能。具體流程如圖2.2所示。圖2.2 主函數流程圖Begin /*算法開始*/調用designBy()顯示出設計者信息Scanf mSIZE，pSIZE，page100 /*mSIZE表示物理塊，pSIZE表示頁面號引用串個數，page100表示一個引用串的頁面號*/do Printf pageiScanf code /*code是一個標記，用來判斷用戶輸入是否符合要求*/Switch(code)case 1: FIFO() /*先進先出算法*/case 2: LRU() /*最近最久未使用算法*/case 3: OPT() /*最佳置換算法*/case 4: exit(0) /*退出程序*/default: 重新輸入while(code!=4)Getch（用戶輸入）End2.2.2延遲時間函數偽代碼算法begin變量定義while delay0while i124退格end圖2.3 延遲時間函數流程圖 延遲時間函數主要由兩個for循環構成。延遲時間函數在程序中主要起延遲時間的作用，相當于一個定時器，給程序數據加載，數據處理等提供時間保證。使程序能夠正常的進行。其具體流程如圖2.3所示。2.2.3 FIFO算法的偽代碼 begin 定義變量 while imSIZEpagei0memeryi, itimeiwhile jmSIZEmemeryjtempij while ipSIZEwhile jmSIZEif 新頁面號不在物理塊中k+if k=mSIZE 則，計算換出頁，記錄該頁進入物理塊的時間否則，tempij=memeryjprint 置換次數End FIFO算法是操作系統中最簡單最容易實現的一種頁面置換算法，它的實現主要運用了兩個循環結構。第一個循環的功能是將頁面串中的前mSIZE頁面直接放入物理塊中；第二個循環主要判斷當前頁面是否在物理塊中，若在物理塊中，則繼續讀取下一個頁面。否則，將最先進入物理塊的頁面寫入到物理塊中。其主要執行流程如圖2.4所示。2.2.4 LRU算法的偽代碼 LRU算法是將最近進入物理塊且未使用的頁面首先換出物理塊。LRU函數主要也運用了兩個循環來實現其算法，首先將前mSIZE個頁面置換到物理塊中，然后再按具體算法進行置換頁面。其執行流程如圖2.5所示。圖2.4 FIFO流程圖 begin 定義變量 while imSIZE pageimemeryi, itimeiwhile jmSIZEmemeryjtempij while imSIZE前mSIZE個數直接放入while ipSIZE while jmSIZEif 新頁面號不在物理塊中k+判斷新頁面號是否在物理塊中if k=mSIZE 則，計算換出頁，記錄該頁進入物理塊的時間否則，max=flag0flag1?0:1memeryjtempij調用 print(置換次數)End圖2.5 LRU流程圖2.2.5 OPT算法的偽代碼 begin 定義變量 while imSIZEpageimemeryi, itimeiwhile jmSIZEmemeryjtempij 前mSIZE個數直接放入 while ipSIZEwhile jmSIZEif memeryj!=pagei判斷新頁面號是否在物理塊中k+if k=mSIZE 則，計算換出頁，記錄該頁進入物理塊的時間否則，max=flag0flag1?0:1tempij=memeryj得到物理塊中各頁下一次訪問時間if memerym=page1退出循環nextm=1調用 print(置換次數)End OPT算法是將內存中最長時間內不會用的頁面置換出去，這種算法的優點是系統利用率，內存利用率都非常的高。但是這種算法目前無法實現，因為實際中，系統根本無法預知哪一個頁面最先執行，哪一個頁面最后執行，各個頁面的執行順序都無法確定根本就不能確定頁面換出的次序。OPT算法主要用于對其他算法效率的評估。OPT函數的執行情況如圖2.6所示。圖2.6 OPT流程圖3 函數調用關系圖3.1函數聲明3.1.1主要算法函數主要算法函數包括FIFO()、LRU()和OPT()三種，它們都是無返回值類型，不帶任何參數。各個函數的具體聲明情況如下：void FIFO(); /*先來先服務調度算法函數*/返回值類型：無返回值形參：無void LRU(); /*最近最久未使用算法函數*/返回值類型：無返回值形參：無void OPT(); /*最佳調度算法函數*/返回值類型：無返回值形參：無3.1.2輔助函數輔助函數是為了實現某些功能而特意設置的一些輔助函數。本程序主要有顯示引用串函數、顯示設計者信息函數、數據加載函數和延遲時間函數，它們有的有形式參數，有的沒有，但是它們都是無返回值類型的函數。各個函數的具體聲明情況如下：void print(unsigned int t); /*顯示引用串函數*/返回值類型：無返回值形參：無符號整型void designBy(); /*顯示設計者信息*/返回值類型：無返回值形參：無void download(); /*數據加載*/返回值類型：無返回值形參：無void mDelay(unsigned int Delay); /*延遲時間*/返回值類型：無返回值形參：無符號整型3.2程序函數調用關系圖 程序以main( )函數為入口，通過主函數main( )進行調用其他函數，以此實現函數的各個功能。在本程序中，main( )函數調用了designBy( )函數，用以顯示設計者信息；main( )函數還分別調用了FIFO( )、LRU( )和OPT( )三種算法函數，實現三種算法。FIFO( )、LRU( )和OPT( )又分別調用了print( )和compute( )函數，print( )顯示了用戶輸入的頁面引用串，compute( )則主要計算了用戶選擇的算法的結果。在計算過程中，為了保證邏輯上合理，我們在compute( )函數中調用了mDelay( )時間延遲函數；main( )函數也調用了download( )數據加載函數，主要功能是加載用戶輸入的數據以供各種算法使用。在調用download( )過程中，也調用了時間延遲函數mDelay( )。具體函數調用關系如圖3.1所示。圖3.1 函數調用關系4 測試結果4.1數據初始化 用戶根據程序提示，按照要求輸入相應的數據。例如，本次測試中我們設置物理塊個數為4，頁面引用串個數為20，一個頁面號引用串中各個頁面號之間用空格(“ ”)隔開。值得注意的是，物理塊個數可以是幾個，幾十個，甚至幾百個，但是考慮到系統的效率，一般取物理塊個數在10個以內；頁面號引用串個數也和物理塊個數一樣，頁面引用串個數取100個以內。用戶輸入情況如圖4.1所示。圖 4.1 界面初始化4.2頁面調度算法 選擇一個合適的頁面置換算法對提高內存的利用率會有很大的幫助。當用戶將數據初始化結束后，就要進行頁面調度算法的選擇了。下面本書將逐一說明先進先出算法FIFO、最近最久未使用LRU和最佳置換算法的具體調試情況。 用戶輸入的頁面引用串為：2 12 43 2 15 23 21 2 4 23 21 20 32 3 21 23 20 2 32 12，物理塊個數為：4，頁面號引用串個數為：20。FIFO算法的缺頁次數為19，置換次數為16，缺頁率為19/20，訪問率為5%；LRU算法的缺頁次數為19，置換次數為16,缺頁率為19/20,訪問率為5%；OPT算法的缺頁次數為14,置換次數為16,缺頁率為14/20，訪問率為30%。4.2.1先進先出算法 由操作系統維護一個所有當前在內存中的頁面的鏈表，最新進入的頁面放在表尾，最久進入的頁面放在表頭。當發生缺頁中斷時，淘汰表頭的頁面并把新調入的頁面加到表尾。具體計算結果如圖4.2所示。圖 4.2 FIFO算法4.2.2最近最久未使用LRU 用一維數組pagepSIZE存儲頁面號序列，memerymSIZE是存儲裝入物理塊中的頁面。數組temp10標記頁面的訪問時間。每當使用頁面時，刷新訪問時間。發生缺頁時，就從物理塊中頁面標記最小的一頁，調出該頁，換入所缺的頁面。具體計算結果如圖4.3所示。圖 4.3 LRU算法圖 4.4 OPT算法4.2.3最佳置換算法OPT 用一維數組pagepSIZE存儲頁面號序列，memerymSIZE是存儲裝入物理塊中的頁面。數組tempmSIZE記錄物理塊中對應頁面的最后訪問時間。每當發生缺頁時，就從物理塊中找出最后訪問時間最大的頁面，調出該頁，換入所缺的頁面。具體計算結果如圖4.4所示。5 源程序#include #include #include /*全局變量*/int mSIZE; /*物理塊數*/int pSIZE; /*頁面號引用串個數*/static int memery10=0; /*物理塊中的頁號*/static int page100=0; /*頁面號引用串*/static int temp10010=0; /*輔助數組*/*置換算法函數*/void FIFO();/先進先出置換算法void LRU();/最近最久未使用算法void OPT();/最佳置換算法/*輔助函數*/void print(unsigned int t);void designBy();/顯示設計者信息void download();/數據加載void mDelay(unsigned int Delay);/延遲時間/*主函數*/void main() int i,k,code;system(color 0F);designBy();printf(請按任意鍵進行初始化操作. n);printf(n);printf( );getchar();system(cls);system(color 0B);printf(請輸入物理塊的個數：);scanf(%d,&mSIZE);printf(請輸入頁面號引用串的個數(P=100)：);scanf(%d,&pSIZE);puts(請依次輸入頁面號引用串(請用 隔開)：);for(i=0;ipSIZE;i+) scanf(%5d,&pagei);download();system(cls);system(color 0E); do puts(輸入的頁面號引用串為：);for(k=0;k=(pSIZE-1)/20;k+)for(i=20*k;(ipSIZE)&(i);getch();system(cls); while (code!=4);getch();/*載入數據*/void download()int i;system(color 0D);printf(n);printf( 能不能給我一首歌的時間。 n);printf(n);printf(Loading.n);printf( );for(i=0;i51;i+)printf(b);for(i=0;i);printf(nFinish.nOK!已唱完.按任意鍵進入置換算法選擇界面：);getch();/*設置延遲*/void mDelay(unsigned int Delay) unsigned int i; for(;Delay0;Delay-) for(i=0;i124;i+) printf( b); /*顯示設計者信息*/ void designBy()printf(n);printf( 研究題目：頁面置換算法 n);printf( 許可證號：13480144 n);printf( 版權所有：朱 強 n);printf(n);/*顯示頁面號引用串*/void print(unsigned int t)int i,j,k,l;int flag;for(k=0;k=(pSIZE-1)/20;k+)for(i=20*k;(ipSIZE)&(i20*(k+1);i+)if(i+1)%20=0)|(i+1)%20)&(i=pSIZE-1)printf(%dn,pagei);elseprintf(%d ,pagei);for(j=0;jmSIZE;j+)for(i=20*k;(imSIZE+20*k)&(i=j)printf( |%d|,tempij);elseprintf( | |);for(i=mSIZE+20*k;(ipSIZE)&(i20*(k+1);i+)for(flag=0,l=0;lmSIZE;l+)if(tempil=tempi-1l)flag+;if(flag=mSIZE)/*頁面在物理塊中*/printf( );elseprintf( |%d|,tempij);/*每行顯示20個*/if(i%20=0)continue;printf(n);printf(-n);printf(缺頁次數：%dtt,t+mSIZE);printf(缺頁率：%d/%dn,t+mSIZE,pSIZE);printf(置換次數：%dtt,t);printf(訪問命中率：%d%n,(pSIZE-(t+mSIZE)*100/pSIZE);printf(-n);/*計算過程延遲*/void compute()int i;printf(正在玩命計算，請稍候);for(i=1;i20;i+)mDelay(15);if(i%4=0)printf(bbbbbb bbbbbb);elseprintf(.);for(i=0;i+30;printf(b);for(i=0;i+30;printf( );for(i=0;i+30;printf(b);/*先進先出頁面置換算法*/void FIFO() int memery10=0; int time10=0; /*記錄進入物理塊的時間*/ int i,j,k,m; int max=0; /*記錄換出頁*/ int count=0; /*記錄置換次數*/*前mSIZE個數直接放入*/ for(i=0;imSIZE;i+) memeryi=pagei; timei=i; for(j=0;jmSIZE;j+)tempij=memeryj; for(i=mSIZE;ipSIZE;i+) /*判斷新頁面號是否在物理塊中*/ for(j=0,k=0;jmSIZE;j+) if(memeryj!=pagei) k+; if(k=mSIZE) /*如果不在物理塊中*/ count+;/*計算換出頁*/ max=time0time1?0:1;for(m=2;mmSIZE;m+)if(timemtimemax)max=m; memerymax=pagei; timemax=i; /*記錄該頁進入物理塊的時間*/ 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; /*記錄頁面的訪問時間*/ int i,j,k,m; int max=0; /*記錄換出頁*/ int count=0; /*記錄置換次數*/*前mSIZE個數直接放入*/ for(i=0;imSIZE;i+) memeryi=pagei; flagi=i; for(j=0;jmSIZE;j+)tempij=memeryj; for(i=mSIZE;ipSIZE;i+) /*判斷新頁面號是否在物理塊中*/ for(j=0,k=0;jmSIZE;j+) if(memeryj!=pagei) k+; else flagj=i; /*刷新該頁的訪問時間*/ if(k=mSIZE) /*如果不在物理塊中*/ count+;/*計算換出頁*/ max=flag0flag1?0:1;for(m=2;mmSIZE;m+)if(flagmflagmax)max=m; memerymax=pagei; flagmax=i; /*記錄該頁的訪問時間*/ for(j=0;jmSIZE;j+)tempij=memeryj; else for(j=0;jmSIZE;j+)tempij=memeryj; compute();print(count);/*最佳置換算法*/void OPT() int memery10=0; int next10=0; /*記錄下一次訪問時間*/ int i,j,k,l,m; int max; /*記錄換出頁*/ int count=0; /*記錄置換次數*/*前mSIZE個數直接放入*/ for(i=0;imSIZE;i+) memeryi=pagei; for(j=0;jmSIZE;j+)tempij=memeryj; for(i=mSIZE;ipSIZE;i+) /*判斷新頁面號是否在物理塊中*/ for(j=0,k=0;jmSIZE;j+) if(memeryj!=pagei) k+; if(k=mSIZE) /*如果不在物理塊中*/ count+;/*得到物理快中各頁下一次訪問時間*/for(m=0;mmSIZE;m+)for(l=i+1;l=next1?0:1;for(m=2;mnextmax)max=m;/*下一次訪問時間都為p