頁面置換算法的實驗報告

1、 操作系統(tǒng)課程設(shè)計報告院 （系）： 衡陽師范學(xué)院 專 業(yè)： 計算機(jī)科學(xué)與技術(shù) 姓 名: 陳建元 齊歡 班 級： 1103班 學(xué) 號: 11190301 11190316 題 目： 頁面置換算法 指導(dǎo)教師: 王玉奇 2013年12月10日至12月28日 目 錄摘 要3第一章 設(shè)計任務(wù)和需求41.1課程設(shè)計任務(wù)41.2課程設(shè)計需求4第二章 概要設(shè)計42.1系統(tǒng)分析42.2調(diào)頁策略52.2.1何時調(diào)入頁面52.2.2請求調(diào)頁策略52.2.3從何處調(diào)入頁面52.3模塊設(shè)計6第三章 詳細(xì)設(shè)計63.1系統(tǒng)設(shè)計63.2算法思想及流程圖73.2.1 主程序流程圖73.2.2先進(jìn)先出(FIFO)頁面置換算法83

2、.2.3最佳頁面置換置換算法（OPT）93.2.4最近最久未使用頁面置換算法（LRU）10第四章 源程序結(jié)構(gòu)分析104.1程序結(jié)構(gòu)104.2 源代碼分析11第五章 調(diào)試16第六章 體會與自我評價17第七章 參考文獻(xiàn)18摘 要 操作系統(tǒng)（英語；Operating System，簡稱OS）是一管理電腦硬件與軟件資源的程序，同時也是計算機(jī)系統(tǒng)的內(nèi)核與基石。操作系統(tǒng)身負(fù)諸如管理與配置內(nèi)存、決定系統(tǒng)資源供需的優(yōu)先次序、控制輸入與輸出設(shè)備、操作網(wǎng)絡(luò)與管理文件系統(tǒng)等基本事務(wù)。操作系統(tǒng)是管理計算機(jī)系統(tǒng)的全部硬件資源包括軟件資源及數(shù)據(jù)資源;控制程序運(yùn)行;改善人機(jī)界面;為其它應(yīng)用軟件提供支持等，使計算機(jī)系統(tǒng)所有資

3、源最大限度地發(fā)揮作用，為用戶提供方便的、有效的、友善的服務(wù)界面。操作系統(tǒng)是一個龐大的管理控制程序，大致包括5個方面的管理功能:進(jìn)程與處理機(jī)管理、作業(yè)管理、存儲管理、設(shè)備管理、文件管理。 在地址映射過程中，若在頁面中發(fā)現(xiàn)所要訪問的頁面不再內(nèi)存中，則產(chǎn)生缺頁中斷。當(dāng)發(fā)生缺頁中斷時操作系統(tǒng)必須在內(nèi)存選擇一個頁面將其移出內(nèi) 存，以便為即將調(diào)入的頁面讓出空間。而用來選擇淘汰哪一頁的規(guī)則叫做頁面置換算法（Page-Replacement Algorithms）。 關(guān)鍵詞：操作系統(tǒng)；OPT頁面置換算法；FIFO先進(jìn)先出的算法；LRU最近最久未使用夜面置換算法第一章 設(shè)計任務(wù)和需求1.1課程設(shè)計任務(wù)深入掌握內(nèi)

4、存調(diào)度算法的概念原理和實現(xiàn)方法。編寫程序?qū)崿F(xiàn)：（1）先進(jìn)先出頁面置換算法（FIFO）（2）最近最久未使用頁面置換算法（LRU）（3）最佳置換頁面置換算法（OPT）設(shè)計一個虛擬存儲區(qū)和內(nèi)存工作區(qū)，編程序演示以上三種算法的具體實現(xiàn)過程，并計算訪問命中率。演示頁面置換的三種算法。通過隨機(jī)數(shù)產(chǎn)生一個指令序列，將指令序列轉(zhuǎn)換成為頁地址流。計算并輸出各種算法在不同內(nèi)存容量下的缺頁率。1.2課程設(shè)計需求在各種存儲器管理方式中，有一個共同的特點，即它們都要求將一個作業(yè)全部裝入內(nèi)存方能運(yùn)行，但是有兩種情況：（1） 有的作業(yè)很大，不能全部裝入內(nèi)存，致使作業(yè)無法運(yùn)行；（2） 有大量作業(yè)要求運(yùn)行，但內(nèi)存容量不足以容納

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

6、些反復(fù)執(zhí)行或即將執(zhí)行的程序段與數(shù)據(jù)部分，而把那些不經(jīng)常執(zhí)行的程序段和數(shù)據(jù)存放于外存待執(zhí)行時調(diào)入，以提高內(nèi)存利用率而提出來的頁式管理有動態(tài)頁式管理和靜態(tài)頁式管理之分，動態(tài)頁式管理是在靜態(tài)頁式管理的基礎(chǔ)上發(fā)展起來的。請求頁式管理屬于動態(tài)頁式管理中的一種，它的地址變換過程與靜態(tài)頁式管理時的相同，也是通過頁表查出相應(yīng)的頁面號，由頁面號與頁內(nèi)相對地址相加而得到實際物理地址。有關(guān)的地址變換部分是由硬件自動完成的。當(dāng)硬件變換機(jī)構(gòu)發(fā)現(xiàn)所要求的頁不在內(nèi)存時，產(chǎn)生缺頁中斷信號，由中斷處理程序做出相應(yīng)的處理。中斷處理程序是由軟件實現(xiàn)的。除了在沒有空閑頁面時要按照置換算法選擇出被淘汰頁面之外，還要從外存讀入所需要的虛

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

8、低效的?？刹捎靡环N以預(yù)測為基礎(chǔ)的預(yù)調(diào)頁策略，將那些預(yù)計在不久之后便會被訪問的頁面，預(yù)先調(diào)入內(nèi)存。如果預(yù)測較準(zhǔn)確，那么，這種策略顯然是很有吸引力的。但目前預(yù)調(diào)頁的成功率僅為50%。且這種策略主要用于進(jìn)程的首次調(diào)入時，由程序員指出應(yīng)該先調(diào)入哪些頁。 2.2.2請求調(diào)頁策略 當(dāng)進(jìn)程在運(yùn)行中需要訪問某部分程序和數(shù)據(jù)時，若發(fā)現(xiàn)其所在的頁面不在內(nèi)存，便即提出請求，由OS將其所需頁面調(diào)入內(nèi)存。由請示調(diào)頁策略所確定調(diào)入的頁，是一定會被訪問的，再加之請求調(diào)頁策略比較易于實現(xiàn)，故在目前的虛擬存儲器中，大多采用此策略。但這種策略每次僅調(diào)入一頁，故須花費較大的系統(tǒng)開銷，增加了磁盤I/O的啟用頻率。 2.2.3從何處調(diào)

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

10、的文件都放在文件區(qū)，故凡是未運(yùn)行過的頁面，都應(yīng)從文件區(qū)調(diào)入。而對于曾經(jīng)運(yùn)行過但又被換出的頁面，由于是被放在對換區(qū)，因此在下次調(diào)入時，應(yīng)從對換區(qū)調(diào)入。由于UNIX系統(tǒng)允許頁面共享，因此，某進(jìn)程所請求的頁面有可能已被其它進(jìn)程調(diào)入內(nèi)存，此時也就無須再從對換區(qū)調(diào)入。2.3模塊設(shè)計 運(yùn)行程序頁面置換算法的主界面輸入頁面序列和物理塊數(shù)OPTLRUFIFO 缺頁次數(shù)和缺頁率 第三章 詳細(xì)設(shè)計3.1系統(tǒng)設(shè)計在進(jìn)程運(yùn)行過程中，若其所要訪問的頁面不在內(nèi)存而需把它們調(diào)入內(nèi)存，但內(nèi)存已無空閑空間時，為了保證該進(jìn)程能正常運(yùn)行，系統(tǒng)必須從內(nèi)存中調(diào)出一頁程序或數(shù)據(jù)，送磁盤的對換區(qū)中。但應(yīng)將哪個頁面調(diào)出，須根據(jù)一定的算法來確

11、定。通常，把選擇換出頁面的算法稱為頁面置換算法(Page_ReplacementAlgorithms)。一個好的頁面置換算法，應(yīng)具有較低的頁面更換頻率。從理論上講，應(yīng)將那些以后不再會訪問的頁面換出，或?qū)⒛切┰谳^長時間內(nèi)不會再訪問的頁面調(diào)出。3.2算法思想及流程圖3.2.1 主程序流程圖如圖（321）所示輸入頁面序列輸入物理塊數(shù)調(diào)用各種置換算法，OPT，LRU，F(xiàn)IFO頁面置換算法計算缺頁次數(shù)和缺頁率結(jié)束開始主流程圖（圖321）3.2.2先進(jìn)先出(FIFO)頁面置換算法算法的基本思想：這是最早出現(xiàn)的置換算法。該算法總是淘汰最先進(jìn)入內(nèi)存的頁面，即選擇在內(nèi)存中駐留時間最久的頁面予以淘汰。該算法實現(xiàn)簡

12、單只需把一個進(jìn)程已調(diào)入內(nèi)存的頁面，按先后次序存入一個時間數(shù)組，并將其中時間值最大的頁面進(jìn)行淘汰，并替換入新的頁面就可以實現(xiàn)。算法流程圖：如圖（322）所示 入口初始化數(shù)據(jù)i指向下一個頁面頁面是否存在物理塊是否有空閑選擇最先進(jìn)入的頁面作為淘汰頁計算缺頁率，并輸出數(shù)據(jù) 結(jié)束輸出當(dāng)前頁,i+將頁面放到空閑的物理塊處i頁面長度YYYNNNFIFO置換算法（圖322）3.2.3最佳頁面置換置換算法（OPT）算法的基本思想：其所選擇的被淘汰頁面，將是永不使用的，或者是在最長時間內(nèi)不再被訪問的頁面。可保證獲得最低的缺頁率。但由于人們目前還無法預(yù)知一個進(jìn)程在內(nèi)存的若干個頁面中，哪一個頁面是未來最長時間內(nèi)不再被

13、訪問的，因而該算法也是無法實現(xiàn)的。但是可利用該算法去評價其它算法。算法流程圖：如圖（323）所示 入口初始化數(shù)據(jù)i指向下一個頁面頁面是否存在物理塊是否有空閑選擇以后最長時間內(nèi)（未來）不在被訪問的頁面作為淘汰頁計算缺頁率，并輸出數(shù)據(jù) 結(jié)束輸出當(dāng)前頁, i+將頁面放到空閑的物理塊處i頁面長度YYYNNNOPT頁面置換算法（圖323）3.2.4最近最久未使用頁面置換算法LRU算法的基本思想：當(dāng)需要淘汰某一頁時，選擇離當(dāng)前時間最近的一段時間內(nèi)最久沒有使用過的頁先淘汰。該算法的主要出發(fā)點是，如果某頁被訪問了，則它可能馬上還被訪問?；蛘叻催^來說，如果某頁很長時間未被訪問，則它在最近一段時間不會被訪問。算法

14、流程圖：如圖（324）所示 入口初始化數(shù)據(jù)i指向下一個頁面頁面是否存在物理塊是否有空閑選擇最近最久未使用的頁面作為淘汰頁計算缺頁率，并輸出數(shù)據(jù) 結(jié)束輸出當(dāng)前頁,i+將頁面放到空閑的物理塊處i頁面長度YYYNNNLRU頁面置換算法（圖324）第四章 源程序結(jié)構(gòu)分析4.1程序結(jié)構(gòu) Input(int m,Pro pL)/打印頁面走向狀態(tài) srand(j);/以時鐘時間j為種子，初始化隨機(jī)數(shù)發(fā)生器 void print(Pro *page1)/打印當(dāng)前的頁面 int Search(int e,Pro *page1 )/尋找內(nèi)存塊中與e相同的塊號int Max(Pro *page1)/尋找最近最長未使

15、用的頁面int Count(Pro *page1,int i,int t,Pro pL)/記錄當(dāng)前內(nèi)存塊中頁面離下次使用間隔長度4.2 源代碼分析#include #include #include #include #define L 20 /頁面長度最大為20 int M; /內(nèi)存塊struct Pro/定義一個結(jié)構(gòu)體 int num,time; ; Input(int m,Pro pL)/打印頁面走向狀態(tài) coutm; if(m20|m10) coutendl;cout頁面長度必須在1020之間endlendl;cout請重新輸入L：; else break; while(1); int

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

17、Search(int e,Pro *page1 )/尋找內(nèi)存塊中與e相同的塊號 Pro *page=new ProM; page=page1; for(int i=0;iM;i+)if(e=pagei.num)return i;/返回i值return -1; int Max(Pro *page1)/尋找最近最長未使用的頁面 Pro *page=new ProM; page=page1; int e=page0.time,i=0; while(iM) /找出離現(xiàn)在時間最長的頁面 if(epagei.time) e=pagei.time; i+; for( i=0;iM;i+)if(e=pagei

18、.time)return i;/找到離現(xiàn)在時間最長的頁面返回其塊號return -1; int Count(Pro *page1,int i,int t,Pro pL)/記錄當(dāng)前內(nèi)存塊中頁面離下次使用間隔長度Pro *page=new ProM; page=page1;int count=0; for(int j=i;jL;j+) if(paget.num=pj.num )break;/當(dāng)前頁面再次被訪問時循環(huán)結(jié)束else count+;/否則count+1 return count;/返回count的值 int main() int c;int m=0,t=0; float n=0;Pro

19、pL; m=Input(m,p);/調(diào)用input函數(shù)，返回m值cout請輸入分配的物理塊m(26): ; coutendlM; if(M6|M2) coutendl;cout物理塊m必須在26之間endlendl;cout請重新輸入m： ; else break; while(1); Pro *page=new ProM; do for(int i=0;iM;i+)/初始化頁面基本情況 pagei.num=0; pagei.time=m-1-i; i=0;coutendl;cout1:FIFO頁面置換endlendl; cout2:LRU頁面置換endlendl; cout3:OPT頁面置換

20、endlendl; cout請選擇頁面置換算法：endlc; system(cls); if(c=1)/FIFO頁面置換 n=0; cout FIFO算法頁面置換情況如下: endl; coutendl; while(i=0) /當(dāng)前頁面在內(nèi)存中 coutpi.num ; /輸出當(dāng)前頁pi.num cout不缺頁endl; i+; /i加1 else /當(dāng)前頁不在內(nèi)存中 if(t=M)t=0; else n+; /缺頁次數(shù)加1 paget.num=pi.num; /把當(dāng)前頁面放入內(nèi)存中coutpi.num ; print(page); /打印當(dāng)前頁面t+; /下一個內(nèi)存塊 i+; /指向下一個

21、頁面 coutendl;cout缺頁次數(shù)：n 缺頁率：n/mendlendl; if(c=2)/LRU頁面置換 n=0; cout LRU算法頁面置換情況如下: endl; coutendl; while(i=0)/如果已在內(nèi)存塊中 paget.time=0;/把與它相同的內(nèi)存塊的時間置0 for(a=0;aM;a+) if(a!=t)pagea.time+;/其它的時間加1 coutpi.num ; cout不缺頁endl; else /如果不在內(nèi)存塊中 n+; /缺頁次數(shù)加1 t=Max(page); /返回最近最久未使用的塊號賦值給t paget.num=pi.num; /進(jìn)行替換pag

22、et.time=0; /替換后時間置為0 coutpi.num ; print(page); for(a=0;aM;a+) if(a!=t) pagea.time+; /其它的時間加1 i+; coutendl;cout缺頁次數(shù)：n 缺頁率：n/mendlendl; if(c=3)/OPT頁面置換 n=0; cout OPT算法置換情況如下:endl; coutendl; while(i=0)/如果已在內(nèi)存塊中 coutpi.num ; cout不缺頁endl; i+; else/如果不在內(nèi)存塊中int a=0; for(t=0;tM;t+) if(paget.num=0)a+;/記錄空的內(nèi)存

23、塊數(shù)if(a!=0) /有空內(nèi)存 int q=M; for(t=0;tt)q=t;/把空內(nèi)存塊中塊號最小的找出來pageq.num=pi.num; n+;coutpi.num ; print(page); i+;else int temp=0,s; for(t=0;tM;t+)/尋找內(nèi)存塊中下次使用離現(xiàn)在最久的頁面if(tempCount(page,i,t,p) temp=Count(page,i,t,p); s=t; /把找到的塊號賦給s pages.num=pi.num; n+; coutpi.num ; print(page); i+; coutendl;cout缺頁次數(shù)：n 缺頁率：n

24、/mendlendl; while(c=1|c=2|c=3); return 0; 第五章 調(diào)試 程序在運(yùn)行的情況下，進(jìn)入主界面輸入菜單，如圖（41）所示：頁面長度：輸入16，分配的物理塊：輸入4， 主界面（圖41）選1，進(jìn)入FIFO算法頁面置換，如圖（42）所示 FIFO算法置換（圖42）選2，進(jìn)入LRU算法頁面置換，如圖（43）所示 LRU算法置換（圖43） 選3，進(jìn)入OPT算法頁面置換，如圖（44）所示 OPT算法置換（圖44） 第六章 體會與自我評價這次操作系統(tǒng)課程設(shè)計，讓我們對操作系統(tǒng)有了更深的認(rèn)識，首先操作系統(tǒng)是一管理電腦硬件與軟件資源的程序，同時也是計算機(jī)系統(tǒng)內(nèi)核與基石。操作系統(tǒng)是一個龐大的管理控制程序，大致包括5個方面的管理功能：進(jìn)程與處理機(jī)管理、作業(yè)管理、存儲管理、設(shè)備管理、文件