(精校版)頁面置換算法的實驗報告

1、（完整word版）頁面置換算法的實驗報告（完整word版）頁面置換算法的實驗報告編輯整理：尊敬的讀者朋友們：這里是精品文檔編輯中心，本文檔內容是由我和我的同事精心編輯整理后發(fā)布的，發(fā)布之前我們對文中內容進行仔細校對，但是難免會有疏漏的地方，但是任然希望（完整word版）頁面置換算法的實驗報告）的內容能夠給您的工作和學習帶來便利。同時也真誠的希望收到您的建議和反饋，這將是我們進步的源泉，前進的動力。本文可編輯可修改，如果覺得對您有幫助請收藏以便隨時查閱，最后祝您生活愉快業(yè)績進步，以下為（完整word版）頁面置換算法的實驗報告的全部內容。操作系統(tǒng)課程設計報告院（系）：衡陽師范學院專業(yè)：計算機科學與

2、技術姓名：陳建元齊歡班級：1103班學號：1119030111190316題目：頁面置換算法指導教師：王玉奇2013年12月10日至12月28日TOC o 1-5 h z摘要4 HYPERLINK l bookmark7 第一章設計任務和需求51。1課程設計任務51。2課程設計需求5 HYPERLINK l bookmark9 第二章概要設計52。1系統(tǒng)分析5調頁策略6.1何時調入頁面6。2請求調頁策略62。2。3從何處調入頁面72。3模塊設計7 HYPERLINK l bookmark11 第三章詳細設計83。1系統(tǒng)設計8算法思想及流程圖83。2.1主程序流程圖83。2。2先進先出（FIFO

3、）頁面置換算法93.2.3最佳頁面置換置換算法（OPT）103。2。4最近最久未使用頁面置換算法（LRU）11 HYPERLINK l bookmark15 第四章源程序結構分析12 HYPERLINK l bookmark17 程序結構12 HYPERLINK l bookmark19 源代碼分析13 HYPERLINK l bookmark21 第五章調試22 HYPERLINK l bookmark27 第六章體會與自我評價24 HYPERLINK l bookmark29 第七章參考文獻25操作系統(tǒng)(英語；OperatingSystem,簡稱OS)是一管理電腦硬件與軟件資源的程序，同時

4、也是計算機系統(tǒng)的內核與基石.操作系統(tǒng)身負諸如管理與配置內存、決定系統(tǒng)資源供需的優(yōu)先次序、控制輸入與輸出設備、操作網絡與管理文件系統(tǒng)等基本事務。操作系統(tǒng)是管理計算機系統(tǒng)的全部硬件資源包括軟件資源及數據資源;控制程序運行；改善人機界面；為其它應用軟件提供支持等，使計算機系統(tǒng)所有資源最大限度地發(fā)揮作用，為用戶提供方便的、有效的、友善的服務界面。操作系統(tǒng)是一個龐大的管理控制程序，大致包括5個方面的管理功能:進程與處理機管理、作業(yè)管理、存儲管理、設備管理、文件管理。在地址映射過程中,若在頁面中發(fā)現所要訪問的頁面不再內存中，則產生缺頁中斷。當發(fā)生缺頁中斷時操作系統(tǒng)必須在內存選擇一個頁面將其移出內存,以便為

5、即將調入的頁面讓出空間.而用來選擇淘汰哪一頁的規(guī)則叫做頁面置換算法(PageReplacementAlgorithms)。關鍵詞：操作系統(tǒng)；OPT頁面置換算法；FIFO先進先出的算法；LRU最近最久未使用夜面置換算法第一章設計任務和需求1.1課程設計任務深入掌握內存調度算法的概念原理和實現方法。編寫程序實現：(1)先進先出頁面置換算法(FIFO)(2)最近最久未使用頁面置換算法(LRU)(3)最佳置換頁面置換算法(OPT)設計一個虛擬存儲區(qū)和內存工作區(qū)，編程序演示以上三種算法的具體實現過程，并計算訪問命中率。演示頁面置換的三種算法。通過隨機數產生一個指令序列，將指令序列轉換成為頁地址流。計算并

6、輸出各種算法在不同內存容量下的缺頁率。1.2課程設計需求在各種存儲器管理方式中，有一個共同的特點,即它們都要求將一個作業(yè)全部裝入內存方能運行，但是有兩種情況：(1)有的作業(yè)很大,不能全部裝入內存,致使作業(yè)無法運行；(2)有大量作業(yè)要求運行,但內存容量不足以容納所有這些作業(yè)。而虛擬內存技術正式從邏輯上擴充內存容量,將會解決以上兩個問題。從內存中調出一頁程序或數據送磁盤的對換區(qū)中，通常，把選擇換出的頁面的算法稱為頁面置換算法(PageReplacementAlgorithms)。進而頁面置換算法程序能客觀的將其工作原理展現在我們面前。第二章概要設計2。1系統(tǒng)分析由于分區(qū)式管理盡管實現方式較為簡單，

7、但存在著嚴重的碎片問題使得內存的利用率不高.再者,分區(qū)式管理時，由于各作業(yè)或進程對應于不同的分區(qū)以及在分區(qū)內各作業(yè)或進程連續(xù)存放，進程的大小或內存可用空間的限制。而且分區(qū)式管理也不利于程序段和數據段的共享。頁式管理正是為了減少碎片以及為了只在內存存放那些反復執(zhí)行或即將執(zhí)行的程序段與數據部分，而把那些不經常執(zhí)行的程序段和數據存放于外存待執(zhí)行時調入，以提高內存利用率而提出來的頁式管理有動態(tài)頁式管理和靜態(tài)頁式管理之分，動態(tài)頁式管理是在靜態(tài)頁式管理的基礎上發(fā)展起來的。請求頁式管理屬于動態(tài)頁式管理中的一種,它的地址變換過程與靜態(tài)頁式管理時的相同，也是通過頁表查出相應的頁面號，由頁面號與頁內相對地址相加而

8、得到實際物理地址。有關的地址變換部分是由硬件自動完成的.當硬件變換機構發(fā)現所要求的頁不在內存時，產生缺頁中斷信號,由中斷處理程序做出相應的處理。中斷處理程序是由軟件實現的.除了在沒有空閑頁面時要按照置換算法選擇出被淘汰頁面之外，還要從外存讀入所需要的虛頁。這個過程要啟動相應的外存和涉及到文件系統(tǒng)。因此,請求頁式管理是一個十分復雜的過程，內存利用率的提高是以犧牲系統(tǒng)開銷的代價換來的。這里用到了置換算法。它是在內存中沒有空閑頁面時被調用。目的是選出一個被淘汰的頁面。如果內存中有足夠的空閑頁面存放所調入的頁，則不必使用置換算法。把內存和外存統(tǒng)一管理的真正目的是把那些被訪問概率非常高的頁存放在內存中.

9、因此，置換算法應該置換那些被訪問概率低的頁，將它們移出內存.2.2調頁策略何時調入頁面如果進程的許多頁是存放在外存的一個連續(xù)區(qū)域中，則一次調入若干個相鄰的頁，會比一次調入一頁的效率更高效一些。但如果調入的一批頁面中的大多數都未被訪問,則又是低效的。可采用一種以預測為基礎的預調頁策略,將那些預計在不久之后便會被訪問的頁面，預先調入內存。如果預測較準確，那么，這種策略顯然是很有吸引力的。但目前預調頁的成功率僅為50%。且這種策略主要用于進程的首次調入時,由程序員指出應該先調入哪些頁。2。2.2請求調頁策略當進程在運行中需要訪問某部分程序和數據時，若發(fā)現其所在的頁面不在內存，便即提出請求，由OS將其

10、所需頁面調入內存。由請示調頁策略所確定調入的頁，是一定會被訪問的，再加之請求調頁策略比較易于實現，故在目前的虛擬存儲器中,大多采用此策略.但這種策略每次僅調入一頁，故須花費較大的系統(tǒng)開銷，增加了磁盤I/O的啟用頻率。從何處調入頁面在請求分頁系統(tǒng)中的外存分為兩部分:用于存放文件的文件區(qū)和用于存放對換頁面的對換區(qū).通常，由于對換區(qū)是采用連續(xù)分配方式，而事件是采用離散分配方式，故對換區(qū)的磁盤I/O速度比文件區(qū)的高。這樣，每當發(fā)生缺頁請求時，系統(tǒng)應從何處將缺頁調入內存，可分成如下三種情況：系統(tǒng)擁有足夠的對換區(qū)空間,這時可以全部從對換區(qū)調入所需頁面,以提高調頁速度。為此，在進程運行前，便須將與該進程有關

11、的文件，從文件區(qū)拷貝到對換區(qū).系統(tǒng)缺少足夠的對換區(qū)空間，這時凡是不會被修改的文件,都直接從文件區(qū)調入；而當換出這些頁面時，由于它們未被修改而不必再將它們換出時，以后需要時，再從對換區(qū)調入。UNIX方式。由于與進程有關的文件都放在文件區(qū)，故凡是未運行過的頁面，都應從文件區(qū)調入。而對于曾經運行過但又被換出的頁面，由于是被放在對換區(qū)，因此在下次調入時，應從對換區(qū)調入。由于UNIX系統(tǒng)允許頁面共享,因此，某進程所請求的頁面有可能已被其它進程調入內存，此時也就無須再從對換區(qū)調入。2。3模塊設計第三章詳細設計3。1系統(tǒng)設計在進程運行過程中，若其所要訪問的頁面不在內存而需把它們調入內存，但內存已無空閑空間時

12、,為了保證該進程能正常運行，系統(tǒng)必須從內存中調出一頁程序或數據，送磁盤的對換區(qū)中。但應將哪個頁面調出，須根據一定的算法來確定。通常，把選擇換出頁面的算法稱為頁面置換算法（Page_ReplacementAlgorithms）。一個好的頁面置換算法,應具有較低的頁面更換頻率.從理論上講，應將那些以后不再會訪問的頁面換出，或將那些在較長時間內不會再訪問的頁面調出。3.2算法思想及流程圖3。2.1主程序流程圖如圖（321）所示主流程圖（圖321）3.2.2先進先出(FIFO)頁面置換算法算法的基本思想：這是最早出現的置換算法。該算法總是淘汰最先進入內存的頁面，即選擇在內存中駐留時間最久的頁面予以淘汰

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

14、換算法LRU算法的基本思想：當需要淘汰某一頁時,選擇離當前時間最近的一段時間內最久沒有使用過的頁先淘汰。該算法的主要出發(fā)點是，如果某頁被訪問了，則它可能馬上還被訪問.或者反過來說，如果某頁很長時間未被訪問，則它在最近一段時間不會被訪問.算法流程圖：如圖(324)所示LRU頁面置換算法(圖324)第四章源程序結構分析4.1程序結構Input(intm,PropL)/打印頁面走向狀態(tài)srand(j)；/以時鐘時間j為種子，初始化隨機數發(fā)生器voidprint(Pro*page1)打印當前的頁面intSearch(inte,Pro*page1)/尋找內存塊中與e相同的塊號intMax(Pro*pag

15、e1)尋找最近最長未使用的頁面intCount(Pro*page1,inti,intt,PropL)記錄當前內存塊中頁面離下次使用間隔長度4.2源代碼分析includeiostream.h#include#includetime。h#includestdio.h#defineL20/頁面長度最大為20intM;/內存塊structPro/定義個結構體intnum,time；;Input（intm,PropL）打印頁面走向狀態(tài)cout請輸入頁面長度（1020）：；docinm；if（m2011m10）coutendl；cout”頁面長度必須在1020之間endlendl;cout請重新輸入1：”

16、；coutendl;coutendl;elsebreak;while(1)；inti，j;j=time(NULL);/取時鐘時間srand(j)；/以時鐘時間j為種子，初始化隨機數發(fā)生器coutendl；cout”輸出隨機數：endl；coutendl;for(i=0;im；i+)pi.num=rand()%10;/產生0到9之間的隨機數放到數組p中pi.time=0；coutpi.num”；coutendlendl;returnm；voidprint(Pro*page1)/打印當前的頁面Pro*page=newProM；page=page1;for(inti=0；iM；i+)coutpage

17、i.num;intSearch(inte,Pro*page1)/尋找內存塊中與e相同的塊號Propage=newProM;page=page1;for(inti=0;iM;i+)if(e=pagei。num)returni;/返回i值return1；intMax(Pro*page1)/尋找最近最長未使用的頁面Pro*page=newProM；page=page1;inte=page0。time,i=0;while(iM)/找出離現在時間最長的頁面if(epagei.time)e=pagei.time;i+；for(i=0;iM;i+)if(e=pagei.time)returni;/找到離現在

18、時間最長的頁面返回其塊號return-1;intCount(Pro*page1,inti,intt,PropL)記錄當前內存塊中頁面離下次使用間隔長度Pro*page=newProM；page=page1;intcount=0；for(intj=i;jL；j+)if(paget.num=pj.num)break;/當前頁面再次被訪問時循環(huán)結束elsecount+;/否則count+1returncount;/返回count的值intmain()intc；intm=0，t=0；floatn=0；PropL;m=Input(m,p);/調用input函數，返回m值cout”請輸入分配的物理塊m(2

19、6)：”；coutendlM；if(M6I|M2)coutendl；coutendl；coutendl；cout”物理塊m必須在26之間”endlendl；cout請重新輸入巾：；elsebreak;while(1)；Pro*page=newProM;dofor(inti=0;iM;i+)/初始化頁面基本情況pagei.num=0;page門。time=m-1-i;i=0;coutendl;cout”1:FIFO頁面置換endlendl;cout”2:LRU頁面置換endlendl；cout3：OPT頁面置換endlendl;cout”請選擇頁面置換算法：endlc；system(cls”)；

20、if(c=1)/FIFO頁面置換n=0;cout”FIFO算法頁面置換情況如下：endl;while(im)if(Search(pi。num,page)=0)/當前頁面在內存中coutpi。num”；/輸出當前頁pi.numcout不缺頁”endl;i+;/i加1else/當前頁不在內存中if(t=M)t=0；elsen+；/缺頁次數加1paget.num=pi。num;/把當前頁面放入內存中coutpi.num”；print(page)；/打印當前頁面t+；/下一個內存塊i+；/指向下一個頁面coutendl;cout”缺頁次數：n缺頁率：n/mendlendl;if(c=2)/LRU頁面置

21、換n=0;cout”LRU算法頁面置換情況如下：endl；cout=0)如果已在內存塊中paget0time=0;/把與它相同的內存塊的時間置0for(a=0；aM;a+)if(a!=t)pagea.time+;/其它的時間加1coutpionum”;cout不缺頁endl;else/如果不在內存塊中n+;/缺頁次數加1t=Max(page)；返回最近最久未使用的塊號賦值給tpaget.num=pi.num；/進行替換pagetotime=0；/替換后時間置為0coutpionum;print(page);for(a=0；aM；a+)if(a!=t)pagea。time+；其它的時間加1i+；

22、coutendl;cout缺頁次數：n缺頁率：n/mendlendl；if(c=3)/OPT頁面置換n=0；cout”O(jiān)PT算法置換情況如下：endl；cout=0)/如果已在內存塊中coutpionum”；cout不缺頁endl；i+;else/如果不在內存塊中inta=0；for(t=0;tt)q=t;/把空內存塊中塊號最小的找出來pageq.num=pi。num;n+；coutpi。num”；print(page);i+;elseinttemp=0，s；for(t=0;tM;t+)尋找內存塊中下次使用離現在最久的頁面if(tempCount(page，i,t,p)temp=Count(p

23、age,i，t，p);s=t;把找到的塊號賦給spages.num=pionum；n+;(完整word版)頁面置換算法的實驗報告coutpionum“；print(page);i+；)coutendI;cout缺頁次數:“n缺頁率：n/mendI6#的-&3i不工11不不1不不不36571590Z1G4617做頁次數：10缺頁率：0.625OPT算法置換（圖4-4）第六章體會與自我評價這次操作系統(tǒng)課程設計，讓我們對操作系統(tǒng)有了更深的認識，首先操作系統(tǒng)是一管理電腦硬件與軟件資源的程序，同時也是計算機系統(tǒng)內核與基石。操作系統(tǒng)是一個龐大的管理控制程序，大致包括5個方面的管理功能:進程與處理機管理、作業(yè)管理、存儲管理、設備管理、文件管理。我們這次課程設計的題目是頁面置換算