1、頁面置換算法的實驗報告操作系統課程設計報告院（系）：衡陽師范學院專業：計算機科學與技術姓 名：陳建元 齊歡班級：1103班學 號:11190301 11190316題 目:頁面置換算法扌指導教師：王玉奇2013年12月10日至12月28日摘要5第一章設計任務和需求61.1課程設計任務61.2課程設計需求6第二章概要設計72.2調頁策略221何時調入頁面222請求調頁策略2.2.3從何處調入頁面.2.3模塊設計第三章詳細設計3.1系統設計3.2算法思想及流程圖3.2.1主程序流程圖322先講先出（FIFO）頁面置換算法3.2.3最佳頁面置OPT778889 99901 -1 1第四章源程序結構分

2、析4.1程序結構.4.2源代碼分析第五章調試第六章 體會與自我評價第七章參考文獻3.2.4最近最久未使用頁面置換算法（LRU ）121 31 314252 72 8操作系統（英語；Operating System，簡稱 OS）是一管理電腦硬件與軟件資源的程序， 同時也是計算機系統的內核與基石。操作系 統身負諸如管理與配置內存、決定系統資源 供需的優先次序、控制輸入與輸出設備、操 作網絡與管理文件系統等基本事務。操作系 統是管理計算機系統的全部硬件資源包括 軟件資源及數據資源；控制程序運行；改善人 機界面；為其它應用軟件提供支持等，使計 算機系統所有資源最大限度地發揮作用，為 用戶提供方便的、有

3、效的、友善的服務界面。 操作系統是一個龐大的管理控制程序，大致 包括5個方面的管理功能：進程與處理機管 理、作業管理、存儲管理、設備管理、文件 管理。 在地址映射過程中，若在頁面中發 現所要訪問的頁面不再內存中，則產生缺頁 中斷。當發生缺頁中斷時操作系統必須在內 存選擇一個頁面將其移出內 存，以便為即 將調入的頁面讓出空間。而用來選擇淘汰哪 一頁的規則叫做頁面置換算法(Page-Replacement Algorithms)。關鍵詞：操作系統；OPT頁面置換算法；FIFO先進先出的算法；LRU最近 最久未使用夜面置換算法第一章設計任務和需求i.i課程設計任務深入掌握內存調度算法的概念原理和實現

4、方法。編寫程序實現：（1）先進先出頁面置換算法（FIFO ）（2）最近最久未使用頁面置換算法（LRU）（3）最佳置換頁面置換算法（OPT）設計一個虛擬存儲區和內存工作區，編程序演示以上三種算法的具體實現過程， 并計算訪問命中率。演示頁面置換的三種算法。通過隨機數產生一個指令序列， 將指令序列轉換成為頁地址流。計算并輸出各種算法在不同內存容量下的缺頁 率。1.2課程設計需求在各種存儲器管理方式中，有一個共同的特點，即它們都要求將一個作業 全部裝入內存方能運行，但是有兩種情況：（1）有的作業很大，不能全部裝入 內存，致使作業無法運行；（2）有大量作業要求運行，但內存容量不足以容納 所有這些作業。而

5、虛擬內存技術正式從邏輯上擴充內存容量，將會解決以上兩個問題。從內存中調出一頁程序或數據送磁盤的對換區中，通常，把選擇換出的頁面的算法稱為頁面置換算法( Page-Replacement Algorithms )。進而頁面置換算法程序能客觀的將其工作原理展現在我們面前。第二章概要設計2.1系統分析由于分區式管理盡管實現方式較為簡單，但存在著嚴重的碎片問題使得內 存的利用率不高。再者，分區式管理時，由于各作業或進程對應于不同的分區 以及在分區內各作業或進程連續存放，進程的大小或內存可用空間的限制。而 且分區式管理也不利于程序段和數據段的共享。頁式管理正是為了減少碎片以 及為了只在內存存放那些反復執

6、行或即將執行的程序段與數據部分，而把那些 不經常執行的程序段和數據存放于外存待執行時調入，以提高內存利用率而提 出來的頁式管理有動態頁式管理和靜態頁式管理之分，動態頁式管理是在靜態 頁式管理的基礎上發展起來的。請求頁式管理屬于動態頁式管理中的一種，它 的地址變換過程與靜態頁式管理時的相同，也是通過頁表查出相應的頁面號， 由頁面號與頁內相對地址相加而得到實際物理地址。有關的地址變換部分是由 硬件自動完成的。當硬件變換機構發現所要求的頁不在內存時，產生缺頁中斷 信號，由中斷處理程序做出相應的處理。中斷處理程序是由軟件實現的。除了 在沒有空閑頁面時要按照置換算法選擇出被淘汰頁面之外，還要從外存讀入所

7、 需要的虛頁。這個過程要啟動相應的外存和涉及到文件系統。因此，請求頁式 管理是一個十分復雜的過程，內存利用率的提高是以犧牲系統開銷的代價換來 的。這里用到了置換算法。它是在內存中沒有空閑頁面時被調用。目的是選出 一個被淘汰的頁面。如果內存中有足夠的空閑頁面存放所調入的頁，則不必使 用置換算法。把內存和外存統一管理的真正目的是把那些被訪問概率非常高的 頁存放在內存中。因此，置換算法應該置換那些被訪問概率低的頁，將它們移 出內存。2.2調頁策略 2.2.1何時調入頁面如果進程的許多頁是存放在外存的一個連續區域中，則一次調入若干個相 鄰的頁，會比一次調入一頁的效率更高效一些。但如果調入的一批頁面中的

8、大 多數都未被訪問，則又是低效的。可采用一種以預測為基礎的預調頁策略，將 那些預計在不久之后便會被訪問的頁面，預先調入內存。如果預測較準確，那 么，這種策略顯然是很有吸引力的。但目前預調頁的成功率僅為50%且這種策略主要用于進程的首次調入時，由程序員指出應該先調入哪些頁。2.2.2請求調頁策略當進程在運行中需要訪問某部分程序和數據時，若發現其所在的頁面不在 內存，便即提出請求，由OS將其所需頁面調入內存。由請示調頁策略所確定調 入的頁，是一定會被訪問的，再加之請求調頁策略比較易于實現，故在目前的 虛擬存儲器中，大多采用此策略。但這種策略每次僅調入一頁，故須花費較大 的系統開銷，增加了磁盤I/O

9、的啟用頻率。223從何處調入頁面在請求分頁系統中的外存分為兩部分：用于存放文件的文件區和用于存放 對換頁面的對換區。通常，由于對換區是采用連續分配方式，而事件是采用離 散分配方式，故對換區的磁盤I/O速度比文件區的高。這樣，每當發生缺頁請 求時，系統應從何處將缺頁調入內存，可分成如下三種情況： 系統擁有足夠的對換區空間，這時可以全部從對換區調入所需頁面，以提高調頁速度。為此，在進程運行前，便須將與該進程有關的文件，從文件區拷貝到對換區。 系統缺少足夠的對換區空間，這時凡是不會被修改的文件，都直接從文件區 調入；而當換出這些頁面時，由于它們未被修改而不必再將它們換出時，以 后需要時，再從對換區調

10、入。 UNIX方式。由于與進程有關的文件都放在文件區，故凡是未運行過的頁面，都應從文件區調入。而對于曾經運行過但又被換出的頁面，由于是被放在對 換區，因此在下次調入時，應從對換區調入。由于UNIX系統允許頁面共享，因此，某進程所請求的頁面有可能已被其它進程調入內存，此時也就無須再從對換區調入。2.3模塊設計運行程頁面置£換算法3. J7v jrr1 3輸入頁面U序列和彳刖丿、戈* l-t-17 J z U d HOLF卡缺頁次數第三章詳細設計3.1系統設計在進程運行過程中，若其所要訪問的頁面不在內存而需把它們調入內存，但內存已無空閑空間時，為了保證該進程能正常運行，系統必須從內存中調

11、出一頁程序或數據，送磁盤的對換區中。但應將哪個頁面調出，須根據一定的算法來確定。通常，把選擇換出頁面的算法稱為頁面置換算法(Page_Replacement Algorithms)。一個好的頁面置換算法，應具有較低的頁面更 換頻率。從理論上講，應將那些以后不再會訪問的頁面換出，或將那些在較長 時間內不會再訪問的頁面調出。3.2算法思想及流程圖3.2.1主程序流程圖如圖(32 1)所示輸入頁調用各種置換算法，計算缺頁次主流程圖（圖32 1）322先進先出（FIFO）頁面置換算法算法的基本思想：這是最早出現的置換算法。該算法總是淘汰最先進入內存 的頁面，即選擇在內存中駐留時間最久的頁面予以淘汰。該

12、算法實現簡單只需 把一個進程已調入內存的頁面，按先后次序存入一個時間數組，并將其中時間 值最大的頁面進行淘汰，并替換入新的頁面就可以實現。算法流程圖：如圖（3 2 2）所示323最佳頁面置換置換算法（OPT）算法的基本思想：其所選擇的被淘汰頁面，將是永不使用的，或者是在最 長時間內不再被訪問的頁面。可保證獲得最低的缺頁率。但由于人們目前還無 法預知一個進程在內存的若干個頁面中，哪一個頁面是未來最長時間內不再被 訪問的，因而該算法也是無法實現的。但是可利用該算法去評價其它算法。算法流程圖：如圖（3 2 3）所示OPT頁面置換算法（圖32 3）324最近最久未使用頁面置換算法 LRU算法的基本思想

13、：當需要淘汰某一頁時，選擇離當前時間最近的一段時間 內最久沒有使用過的頁先淘汰。該算法的主要出發點是，如果某頁被訪問了， 則它可能馬上還被訪問。或者反過來說，如果某頁很長時間未被訪問，則它在 最近一段時間不會被訪問。算法流程圖：如圖（3 2 4）所示-i指、曰YN塊是曰輸出當選擇最近最將頁面N、計LRU頁面置換算法(圖324)第四章 源程序結構分析4.1程序結構In put(i nt m,Pro pL) 打印頁面走向狀態 srand(j);/以時鐘時間j為種子，初始化隨機數 發生器void print(Pro *page1)/ 打印當前的頁面int Search(int e,Pro *page

14、1 )/尋找內存塊中 與e相同的塊號int Max(Pro *page1)尋找最近最長未使用 的頁面int Cou nt(Pro *page1,i nt i,i nt t,Pro pL)記錄當前內存塊中頁面離下次使用間隔長度4.2源代碼分析#in clude<iostream.h>#in clude <stdlib.h>#in clude <time.h>#in clude <stdio.h>#define L 20/頁面長度最大為 20int M; /內存塊struct Pro/定義一個結構體int n um,time;Inp ut(int m

15、,Pro pL)/ 打印頁面走向狀態cout<<"請輸入頁面長度(1020):"docin»m;if(m>20|m<10)cout«e ndl;coutvv"頁面長度必須在1020之間 "<<e ndl«e ndl;cout<<"請重新輸入L :"else break;while(1);int i,j;j=time(NULL); 取時鐘時間srand(j);以時鐘時間j為種子，初始化隨機數 發生器cout<<e ndl;cout<<&

16、quot;輸出隨機數:"<<endl;cout<<e ndl;for(i=0;i<m;i+)pi.num=rand( )%10; 產生 0到 9之間的隨機數放到數組p中pi.time=0;cout<<pi. num<<""cout<<e ndl<<e ndl;return m;void print(Pro *page1)打印當前的頁面Pro *page=new ProM;page=page1;for(int i=0;i<M;i+) cout«pagei. nu m<

17、<""cout«e ndl;int Search(int e,Pro *page1 )/ 尋找內存塊中與相同的塊號Pro *page=new ProM;page=page1;for(i nt i=O;i<M;i+)if(e=pagei. nu m)return i;/返回i值return -1;int Max(Pro *page1)/尋找最近最長未使用的頁Pro *page=new ProM; page=page1;int e=pageO.time,i=O;while(ivM)/找出離現在時間最長的頁面if(e<pagei.time) e=pag

18、ei.time;i+；for( i=O;i<M;i+)if(e=pagei.time)return i;/找到離現在時間最長的頁面返回其塊號return -1;int Count(Pro *page1,int i,int t,Pro pL)/ 記錄當前內存塊中頁面離下次使用間隔長度Pro *page=new ProM;page=page1;int coun t=0;for(i nt j=i;j<L;j+)if(paget.num=pj.num )break; 當前頁面再次被訪問時循環結束else count+;/否貝V count+1return count;/ 返回 count

19、的值int mai n()in t c;int m=0,t=0;float n=0;Pro pL;m=I nput(m,p); 調用in put函數，返回 m 值 coutvv"請輸入分配的物理塊 m(26):" cout«e ndl«e ndl;doci n»M;if(M>6|M<2)cout«e ndl;coutvv"物理塊 m 必須在26之間"<<e ndlvve ndl;coutvv"請重新輸入m:"else break;while(1);Pro *page=ne

20、w ProM;dofor(i nt i=0;i<M;i+) 初始化頁面基本情況 pagei. num=O; pagei.time=m-1-i;i=0;cout«e ndl;cout«"1:FIFO 頁面置換"<<endl«endl; cout<v"2:LRU 頁面置換"<<endl«endl; cout«"3:OPT 頁面置換"<<endl«endl;cout<<"請選擇頁面置換算法： "<

21、<e ndl<<e ndl;cin> >c;system("cls");if(c=1)/FIFO 頁面置換n=0;cout<<" FIFO算法頁面置換情況如下: "<<e ndl;cout<<e ndl;while(i<m) if(Search(pi. num,page)>=0) / 當前頁 面在內存中pi. numcout«"不缺頁"<<endl;i+; /i 加 1else 當前頁不在內存中if(t=M)t=O;elsen+; /缺

22、頁次數加1 paget. num=pi. num; / 把當前頁面放入內存中cout«pi. nu m<<""print(page);/打印當前頁面 t+; /下一個內存塊i+; /指向下一個頁面cout«e ndl;coutvv"缺頁次數："<<nvv" 缺頁率："<<n/m<<e ndl«e ndl;if(c=2)/LRU 頁面置換n=0;coutvv" LRU算法頁面置換情況如下"<<e ndl;cout«e

23、ndl;while(ivm)int a;t=Search(pi. nu m,page);if(t>=0)/如果已在內存塊中 paget.time=0;/把與它相同的內存塊的時間置0for(a=0;a<M;a+) if(a!=t)pagea.time+; 其它的時間加1cout«pi. nu m<<"" coutvv"不缺頁"<<endl;else /如果不在內存塊中n+; /缺頁次數加1t=Max(page); /返回最近最久未使 用的塊號賦值給tpaget. nu m=pi. num ;進行替換 paget

24、.time=0; /替換后時間置為0 cout«pi. num<<""prin t(page);for(a=0;a<M;a+)if(a!=t) pagea.time+; /其它的時間加1i+;cout«e ndl;coutvv"缺頁次數："<<nvv" 缺頁率："<<n/m<<e ndl«e ndl;if(c=3)/OPT 頁面置換n=0;cout<<" OPT 算法置換情況女口 下:"<<e ndl;cou

25、t<<e ndl;while(i<m)if(Search(pi.num,page)>=0) 女口果已 在內存塊中 cout«pi. num<<"" cout«"不缺頁"<<endl; i+；else/如果不在內存塊中int a=0;for(t=0;t<M;t+)if(paget.num=0)a+; 記錄空的內存塊數if(a!=0) /有空內存int q=M;for(t=0;t<M;t+)if(paget. num=0&&q>t)q=t; 把空內存塊中塊號

26、最小的找出來pageq. nu m=pi. num;n+;cout«pi. nu m<<""prin t(page);i+；elseint temp=0,s;for(t=0;t<M;t+) 尋找內存塊中下次使用離現在最久的頁面if(temp<Co un t(page,i,t,p)temp=Co un t(page,i,t,p); s=t; /把找到的塊號賦給spages. num=pi. num;n+;cout«pi. num<<""prin t(page);i+;cout«e ndl;c

27、outvv"缺頁次數："<<nvv" 缺頁率："<<n/m<<e ndl«e ndl;while(c=1|c=2|c=3);return 0;第五章調試程序在運行的情況下，進入主界面輸入菜單，如圖（4 1）所示:頁面長度：輸入16,分配的物理塊：輸入4，El "F ；C+曲直書胃去亡炬"請輸入頁面艮度"0 -畑：直 咕出晞機數：情輸入分配的物理塊E主界面（圖4 1）選1,進入FIFO算法頁面置換，如圖（42）所示*F：C+3e 3ug 口直晝妻茸法自芒*FIFO算迭頁面置換情況如

28、T； 3000P 3 6 0 0E 3 6 E 07 3 G 5 71 5 7占不缺頁9 19 5 70 19 0 72 19 021不缺帀6 6 9 0 24 & 4 Q 2£不缺頁1 G 4 1 27 6 4 1 73 3 4 1 7FIFO算法置換（圖42選2,進入LRU算法頁面置換，如圖（43）所示3 3 0 0 0 G 3 6 0 0E 3 6 5 0 7 3 b S 7 116 5 7P不缺頁V 1 *? 5> 7 U 1 V b M 2 2 9 5 0 12 9 10p不獻貢1不缺員7 ? 61 43 7 613觸頁次數：±3缺頁率:LRU算法置換（圖4選3,進入OPT算法頁面置換，如圖（44）所示缺頁飲數；13缺頁率；嚇:+ + Debug W4®.exe'7 7帥優06 3600S36507 365711657p不缺頁9 1 G 9 7OPT具怎直腴70616fetw6wwwfiKrK'Kr 3銭貝挨數：10缺頁率：乩能5OPT算法置換（圖44）第