操作系統(tǒng)課程設計--頁面置換算法的模擬實現(xiàn)_

1、<p>　　操作系統(tǒng)課程設計報告</p><p>　　題目： 頁面置換算法的模擬實現(xiàn)_</p><p>　　信 息 工 程 學 院</p><p>　專業(yè)計算機科學與技術(shù)</p><p>　學生姓名</p><p>　班級</p><p>　學號</p><p>

2、;　指導教師</p><p>　發(fā)放日期</p><p><b>　　目 錄</b></p><p><b>　　1 概述1</b></p><p><b>　　2 設計原理1</b></p><p>　　2.1 先進先出（FIFO）算法1&

3、lt;/p><p>　　2.2 最近最久未使用（LRU）算法1</p><p>　　3 詳細設計與編碼2</p><p>　　3.1 模塊設計2</p><p>　　3.2 系統(tǒng)詳細設計2</p><p><b>　　4 結(jié)果與分析4</b></p><p>　　4.

4、1 測試方案4</p><p>　　4.2 測試結(jié)果5</p><p>　　4.3測試結(jié)果分析8</p><p><b>　　5 設計小結(jié)8</b></p><p><b>　　6 參考文獻9</b></p><p><b>　　附錄 程序代碼9<

5、/b></p><p>　　頁面置換算法的模擬實現(xiàn)</p><p><b>　　1 概述</b></p><p>　　在進程運行過程中，若其所要訪問的頁面不在內(nèi)存所需把他們調(diào)入內(nèi)存，但內(nèi)存已無空閑時，為了保證進程能夠正常運行，系統(tǒng)必須從內(nèi)存中調(diào)入一頁程序或數(shù)據(jù)送磁盤的對換區(qū)中。但應將那個頁面調(diào)出，需要根據(jù)一定的算法來確定。通常，把選擇換出

6、頁面的算法稱為頁面置換算法。置換算法的好壞，將直接影響到系統(tǒng)的性能。</p><p>　　一個好的頁面置換算法，應具有較低的頁面更換頻率。從理論上將講，應將那些以后不再訪問的頁面換出，或把那些較長時間內(nèi)不再訪問的頁面調(diào)出。目前存在著不同的算法，他們都試圖更接近與理論上的目標。</p><p>　　擁有頁面交換機制的操作系統(tǒng)總是把當前進程中急需處理的部分頁面換入到內(nèi)存當中，而把更多暫時不需要

7、處理的頁面放置在外存當中。由于進程需要處理的頁面順序不同，因此必須要在內(nèi)存與外存之間進行頁面交換，頁面置換算法也就應運而生。</p><p><b>　　2 設計原理</b></p><p>　　2.1 先進先出（FIFO）算法</p><p>　　這是最早出現(xiàn)的置換算法。該算法總是淘汰最先進入內(nèi)存的頁面，即選擇在內(nèi)存停留時間最久的給予淘汰。該

8、算法實現(xiàn)簡單，只需把一個進程已調(diào)入內(nèi)存的頁面，按先后次序鏈接成一個隊列，并設置一個指針，稱為替代指針，使它總是指向最老的頁面。但該算法與進程實際運行的規(guī)律不相適應，因為在incheng中，有些頁面經(jīng)常被訪問，比如，含有全局變量，常用函數(shù)，例程等方面，F(xiàn)IFO</p><p>　　算法并不能保證這些頁面不被淘汰。當需要選擇一個頁面淘汰時，總是選擇最先進入內(nèi)存空間的那一個頁面。只要在系統(tǒng)中建立一個FIFO隊列，以反映

9、頁面的活動情況。被選擇的頁面總是處于隊首的頁面，而最近調(diào)入的頁面永遠存放在隊列的尾部。</p><p>　　2.2 最近最久未使用（LRU）算法</p><p>　　FIFO置換算法的性能之所以較差，是因為它所依據(jù)的條件是各個頁面調(diào)入內(nèi)存的時間，而頁面調(diào)入的先后不能反映頁面的使用情況。最近最久未使用（LRU）的頁面置換算法，是根據(jù)頁面調(diào)入內(nèi)存后的使用情況進行決策的。由于無法預測各個頁面將來

10、的使用情況，只能利用“最近的過去”，作為“最近的將來”的近似。該算法的基本思想是用最近的過去估計最近的將來。假定在內(nèi)存中的某個頁面，在最近一段時間內(nèi)未被使用的時間最長，那么在最近的將來也可能不再被使用。</p><p><b>　　3 詳細設計與編碼</b></p><p><b>　　3.1 模塊設計</b></p><p&

11、gt;　　(1) 進入系統(tǒng)模塊。進入登陸界面，輸入內(nèi)存頁面數(shù)和實際頁數(shù)</p><p>　　(2) 頁面號打印模塊。打印輸入的頁面號。</p><p>　　(3) 菜單選擇模塊。選擇相應的頁面的置換方式，選擇相應的字母，進入相應的功能。</p><p>　　(4) 算法模塊。選擇相應的頁面置換算法。</p><p>　　(5) 顯現(xiàn)輸出模塊。

12、顯示頁面被置換的情況。</p><p>　　(6) 缺頁次數(shù)和缺頁率模塊。計算頁面號輸入的計算結(jié)果。</p><p>　　(7) 退出系統(tǒng)模塊。退出置換頁面。</p><p>　　3.2 系統(tǒng)詳細設計</p><p>　　(1) 系統(tǒng)主界面設計（包含登陸模塊設計）</p><p>　　首先貫穿全局的全局需要一系列的函數(shù)

13、來實現(xiàn)本操作系統(tǒng)的各種功能。需要函數(shù)自帶的文件stdafx.h 和iostream.h 首先輸入的頁數(shù)自定義最大值為40程序用#define M 40實現(xiàn)。為了防止輸入的頁數(shù)太多，超出自定義40個數(shù)的范圍，通過輸入函數(shù)實現(xiàn)：int Input(int m,Pro p[M]) //輸入函數(shù)。</p><p><b>　　(2) 系統(tǒng)模塊</b></p><p>

14、　　首先通過打印當前的頁面 </p><p>　　void print(Pro *page1) //打印當前的頁面</p><p><b>　　{</b></p><p>　　Pro *page=new Pro[N];</p><p>　　page=page1;</p><p>　　f

15、or(int i=0;i<N;i++)cout<<page[i].num<<" ";</p><p>　　cout<<endl;</p><p><b>　　} </b></p><p>　　查找內(nèi)存中是否存在要調(diào)入的頁面</p><p>　　int S

16、earch(int e,Pro *page1 ) {</p><p>　　Pro *page=new Pro[N];</p><p>　　page=page1;</p><p>　　for(int i=0;i<N;i++)if(e==page[i].num)return i;</p><p>　　return -1;}</p&g

17、t;<p>　　找出離現(xiàn)在時間最長的頁面</p><p>　　int Max(Pro *page1) {</p><p>　　Pro *page=new Pro[N];</p><p>　　page=page1;</p><p>　　int e=page[0].time,i=0;</p><p>　　wh

18、ile(i<N)</p><p>　　{ if(e<page[i].time)e=page[i].time;</p><p><b>　　i++;</b></p><p><b>　　}</b></p><p>　　for( i=0;i<N;i++)if(e==page[i].ti

19、me)return i;</p><p>　　return -1;</p><p><b>　　}</b></p><p>　　//找到最久不使用的頁面</p><p>　　int Compfu(Pro *page1,int i,int t,Pro p[M])</p><p>　　{ Pro

20、*page=new Pro[N];</p><p>　　page=page1;</p><p>　　int count=0;</p><p>　　for(int j=i;j<M;j++)</p><p>　　{ if(page[t].num==p[j].num )break;</p><p>　　else cou

21、nt++;</p><p><b>　　}</b></p><p>　　return count;</p><p><b>　　}</b></p><p>　　(3) FIFO頁面置換和缺頁次數(shù)及缺頁率模塊實現(xiàn)如下：</p><p>　　if(c=='1')/

22、/FIFO頁面置換</p><p><b>　　{n=1;</b></p><p>　　cout<<"頁面置換情況: "<<endl;</p><p>　　while(i<m)</p><p>　　{if(Search(p[i].num,page)>=0)i++

23、;//找到相同的頁面</p><p><b>　　else </b></p><p>　　{ if(t==N)t=0;</p><p><b>　　else </b></p><p><b>　　{ n++;</b></p><p>　　page[t

24、].num=p[i].num;</p><p>　　print(page);</p><p><b>　　t++;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</

25、b></p><p>　　cout<<"缺頁次數(shù)："<<n<<" 缺頁率："<<n/m<<endl; </p><p><b>　　}</b></p><p>　　(4) LRU頁面置換和缺頁次數(shù)及缺頁率模塊實現(xiàn)如下：<

26、;/p><p>　　if(c=='2')//LRU頁面置換</p><p><b>　　{ n=1;</b></p><p>　　cout<<"頁面置換情況: "<<endl; </p><p>　　while(i<m)</p><

27、;p>　　{ int k;</p><p>　　k=t=Search(p[i].num,page);</p><p><b>　　if(t>=0)</b></p><p>　　page[t].time=0;</p><p><b>　　else</b></p><

28、p><b>　　{ n++; </b></p><p>　　t=Max(page);</p><p>　　page[t].num=p[i].num;</p><p>　　page[t].time=0;</p><p><b>　　}</b></p><p>　　if(t

29、==0){page[t+1].time++;page[t+2].time++;}</p><p>　　if(t==1){page[2].time++;page[0].time++;}</p><p>　　if(t==2){page[1].time++;page[0].time++;}</p><p>　　if(k==-1) print(page);<

30、;/p><p><b>　　i++;</b></p><p><b>　　}</b></p><p>　　cout<<"缺頁次數(shù)："<<n<<" 缺頁率："<<n/m<<endl; </p><p>

31、;<b>　　}</b></p><p><b>　　4 結(jié)果與分析</b></p><p><b>　　4.1 測試方案</b></p><p>　　(1) 測試方案(一) </p><p>　　輸入可用頁面為4，實際頁數(shù)是10，各個頁面號1 5 7 0 5 1 0 8 0

32、1（課本例題）選擇實驗要求FIFO頁面置換，然后選擇LRU算法。最后選擇OPT（對比）。</p><p>　　(2) 測試方案（二)</p><p>　　輸入可用頁面為4，實際頁數(shù)是10，各個頁面號1 3 9 1 9 9 4 8 0 7選擇實驗要求FIFO頁面置換，然后選擇LRU算法。最后選擇OPT（對比1）</p><p>　　(3) 測試方案（三) </p

33、><p>　　輸入可用頁面為5，實際頁數(shù)是10，各個頁面號1 5 7 0 5 1 0 8 0 1（課本例題）選擇實驗要求FIFO頁面置換，然后選擇LRU算法。最后選擇OPT（對比）</p><p><b>　　4.2 測試結(jié)果 </b></p><p>　　(1) 測試方案（一)結(jié)果。</p><p>　　輸入可用頁面為4，

34、實際頁數(shù)是10，各個頁面號1 5 7 0 5 1 0 8 0 1 測試成功。見圖（圖4-1輸入頁面登陸與輸入）選擇FIFO頁面置換時顯示頁面置換情況、缺頁次數(shù)和缺頁率（見圖4-2 FIFO頁面置換界面）。</p><p>　　圖4-1 輸入頁面登陸與輸入</p><p>　　圖4-2 FIFO頁面置換界面</p><p>　　選擇LRU頁面置換時顯示頁面置換情況、缺

35、頁次數(shù)和缺頁率（見圖4-3 LRU頁面置換界面）</p><p>　　圖4-3 LRU頁面置換界面</p><p>　　(2) 測試方案（二)結(jié)果。輸入可用頁面為4，實際頁數(shù)是10，各個頁面號1 3 9 1 9 9 4 8 0 7測試成功。見圖（圖4-4輸入頁面登陸與輸入）選擇FIFO頁面置換時顯示頁面置換情況、缺頁次數(shù)和缺頁率（見圖4-5 FIFO頁面置換界面） </p>

36、<p>　　圖4-4 輸入頁面登陸與輸入</p><p>　　選擇LRU頁面置換時顯示頁面置換情況、缺頁次數(shù)和缺頁率（見圖4-5 LRU頁面置換界面）</p><p>　　圖4-5 LRU頁面置換界面</p><p>　　(3) 測試方案（三)結(jié)果。</p><p>　　輸入可用頁面為5，實際頁數(shù)是10，各個頁面號1 5 7 0

37、5 1 0 8 0 1測試成功。見圖（圖4-1輸入頁面登陸與輸入）選擇FIFO頁面置換時顯示頁面置換情況、缺頁次數(shù)和缺頁率（見圖4-6FIFO頁面置換界面）</p><p>　　圖4-6 FIFO頁面置換界面</p><p>　　選擇LRU頁面置換時顯示頁面置換情況、缺頁次數(shù)和缺頁率（見圖4-7LRU頁面置換界面）</p><p>　　圖4-7 LRU頁面置換界面&

38、lt;/p><p>　　4.3 測試結(jié)果分析</p><p>　　從上述結(jié)果可知,在內(nèi)存頁面為2個頁面時, 由于用戶進程的所有指令基本上都沒裝入內(nèi)存，只裝入一小部分,從而算法之間的差別比較大。FIFO算法的訪內(nèi)命中率大致在50％至80％之間變化。LRU算法的訪內(nèi)命中率大致在50％至70％之間變化。但是,FIFO算法與LRU算法之間差別一般在10個百分點左右。比較上述兩種算法,以LRU算法的命中

39、率最高,其次是FIFO算法。</p><p><b>　　5 設計小結(jié)</b></p><p>　　一開始選題的時候我并沒有考慮太多，原以為題目難度都差不多，于是就選了個冷門的。但是沒想到本題的難度和完成的代碼量遠遠超出了我的預期。原以為本題看起來很簡單，也就不過是一個隨機數(shù)函數(shù)和兩種算法實現(xiàn)而已，但是事實證明我徹徹底底的錯了。首先是隨機數(shù)生成，來回看了好幾遍都沒弄

40、懂生成方法，最后經(jīng)同學指點一下才終于明白，然后就是頁式管理的原理和頁面置換算法等等，很多都忘記了，不得不再次打開課本。由于個人水平有限，光是理解原理及理清程序結(jié)構(gòu)就已經(jīng)花費了我很多寶貴的時間，加上本來時間就不充裕，于是我果斷選擇敏捷軟件開發(fā)模型用于完成此課程設計。依照軟件工程原則，分析需求，畫出程序結(jié)構(gòu)圖，將程序模塊化，進行概要設計和詳細設計，撰寫實驗報告同時編寫程序代碼，對編寫完模塊進行構(gòu)件化處理，完善好接口，進行功能測試，不斷發(fā)布

41、可執(zhí)行程序，然后組裝、完善……歷經(jīng)了5個Beta版本之后，程序終于都大功告成了。 本次實驗中體會最深刻的就是運用了構(gòu)件化的方法來測試模塊，否則面對如此可觀的代碼量，如果每次都是編寫完一點功能或者編寫完所有功能才進行測試，debug的話都不知道從哪兒找起了，特別是對于編程水平不高的自</p><p><b>　　6 參考文獻</b></p><p>　　[1]

42、嚴蔚敏，吳偉民. 數(shù)據(jù)結(jié)構(gòu)[M].清華大學出版社，1997.[2] 張堯?qū)W，史美林. 計算機操作系統(tǒng)教程[M].清華大學出版社，2000.[3] 孫靜宇. 計算機操作系統(tǒng)課程設計指導書[M].太原理工出版社，2006.</p><p><b>　　附錄 程序代碼</b></p><p>　　#include<iostream.h></p>

43、<p>　　#define M 40</p><p><b>　　int N;</b></p><p>　　struct Pro//結(jié)構(gòu)體</p><p><b>　　{</b></p><p>　　int num,time;</p><p><b&g

44、t;　　};</b></p><p>　　int Input(int m,Pro p[M])//輸入函數(shù)</p><p><b>　　{</b></p><p>　　cout<<"請輸入實際頁數(shù)：";</p><p><b>　　do</b></p&

45、gt;<p><b>　　{</b></p><p><b>　　cin>>m;</b></p><p>　　if(m>M)cout<<"數(shù)目太多，請重試"<<endl;</p><p>　　else break;</p><p

46、><b>　　}</b></p><p><b>　　while(1);</b></p><p>　　cout<<endl<<"請輸入各頁面號"<<endl;</p><p>　　for(int i=0;i<m;i++)</p><p&

47、gt;<b>　　{</b></p><p>　　cin>>p[i].num;</p><p>　　p[i].time=0;</p><p><b>　　}</b></p><p><b>　　return m;</b></p><p>&l

48、t;b>　　}</b></p><p>　　void print(Pro *page1)//打印當前的頁面</p><p><b>　　{</b></p><p>　　Pro *page=new Pro[N];</p><p>　　page=page1;</p><p>　　fo

49、r(int i=0;i<N;i++)cout<<page[i].num<<" ";</p><p>　　cout<<endl;</p><p><b>　　}</b></p><p>　　int Search(int e,Pro *page1 )//查找內(nèi)存中是否存在要調(diào)入的頁

50、面</p><p><b>　　{</b></p><p>　　Pro *page=new Pro[N];</p><p>　　page=page1;</p><p>　　for(int i=0;i<N;i++)if(e==page[i].num)return i;</p><p>　　re

51、turn -1;</p><p><b>　　}</b></p><p>　　int Max(Pro *page1)//找出離現(xiàn)在時間最長的頁面</p><p><b>　　{</b></p><p>　　Pro *page=new Pro[N];</p><p>　　pag

52、e=page1;</p><p>　　int e=page[0].time,i=0;</p><p>　　while(i<N)</p><p><b>　　{</b></p><p>　　if(e<page[i].time)e=page[i].time;</p><p><b&g

53、t;　　i++;</b></p><p><b>　　}</b></p><p>　　for( i=0;i<N;i++)if(e==page[i].time)return i;</p><p>　　return -1;</p><p><b>　　}</b></p>

54、<p>　　int Compfu(Pro *page1,int i,int t,Pro p[M])//找到最久不使用的頁面</p><p><b>　　{</b></p><p>　　Pro *page=new Pro[N];</p><p>　　page=page1;</p><p>　　int count=

55、0;</p><p>　　for(int j=i;j<M;j++)</p><p><b>　　{</b></p><p>　　if(page[t].num==p[j].num )break;</p><p>　　else count++;</p><p><b>　　}</

56、b></p><p>　　return count;</p><p><b>　　}</b></p><p>　　int main()</p><p><b>　　{</b></p><p>　　cout<<"可用內(nèi)存頁面數(shù)"<&l

57、t;endl;</p><p><b>　　cin>>N;</b></p><p><b>　　Pro p[M];</b></p><p>　　Pro *page=new Pro[N];</p><p><b>　　char c;</b></p>&l

58、t;p>　　int m=0,t=0;</p><p>　　float n=0;</p><p>　　m=Input(m,p);</p><p><b>　　do{</b></p><p>　　for(int i=0;i<N;i++)//初試化頁面基本情況</p><p><b&g

59、t;　　{</b></p><p>　　page[i].num=0;</p><p>　　page[i].time=2-i;</p><p><b>　　}</b></p><p><b>　　i=0;</b></p><p>　　cout<<&quo

60、t;f:FIFO頁面置換"<<endl;</p><p>　　cout<<"l:LRU頁面置換"<<endl;</p><p>　　cout<<"按其它鍵結(jié)束"<<endl;</p><p><b>　　cin>>c;</b>

61、;</p><p>　　if(c=='f')//FIFO頁面置換</p><p><b>　　{</b></p><p><b>　　n=1;</b></p><p>　　cout<<"頁面置換情況: "<<endl;</p>

62、;<p>　　while(i<m)</p><p><b>　　{</b></p><p>　　if(Search(p[i].num,page)>=0)i++;//找到相同的頁面</p><p><b>　　else</b></p><p><b>　　{<

63、/b></p><p>　　if(t==N)t=0;</p><p><b>　　else</b></p><p><b>　　{</b></p><p><b>　　n++;//</b></p><p>　　page[t].num=p[i].nu

64、m;</p><p>　　print(page);</p><p><b>　　t++;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p&g

65、t;<p>　　cout<<"缺頁次數(shù)："<<n<<" 缺頁率："<<n/m<<endl;</p><p><b>　　}</b></p><p>　　if(c=='l')//LRU頁面置換</p><p>&

66、lt;b>　　{ n=1;</b></p><p>　　cout<<"頁面置換情況: "<<endl;</p><p>　　while(i<m)</p><p><b>　　{</b></p><p><b>　　int k;<

67、/b></p><p>　　k=t=Search(p[i].num,page);</p><p><b>　　if(t>=0)</b></p><p>　　page[t].time=0;</p><p><b>　　else</b></p><p><b&g

68、t;　　{</b></p><p><b>　　n++;</b></p><p>　　t=Max(page);</p><p>　　page[t].num=p[i].num;</p><p>　　page[t].time=0;</p><p><b>　　}</b>

69、;</p><p>　　if(t==0){page[t+1].time++;page[t+2].time++;}</p><p>　　if(t==1){page[2].time++;page[0].time++;}</p><p>　　if(t==2){page[1].time++;page[0].time++;}</p><p>　　if(

70、k==-1) print(page);</p><p><b>　　i++;</b></p><p><b>　　}</b></p><p>　　cout<<"缺頁次數(shù)："<<n<<" 缺頁率："<<n/m<<en

71、dl;</p><p><b>　　}</b></p><p>　　}while(c=='f'||c=='l'||c=='o');</p><p><b>　　return 0;</b></p><p><b>　　}</b>&l