頁面置換算法模擬程序課程設(shè)計

1、<p><b>　　****學院 </b></p><p><b>　　計算機科學系</b></p><p><b>　　課程設(shè)計報告</b></p><p>　　設(shè)計名稱： 軟件課程設(shè)計 </p><p>　　設(shè)計題目：

2、 頁面置換算法模擬程序 </p><p>　　學生學號： **** </p><p>　　專業(yè)班級： </p><p>　　學生姓名： </p>

3、;<p>　　學生成績： </p><p>　　指導教師（職稱）： </p><p>　　課題工作時間： </p><p><b>　　摘 要</b></p><p>　　操作系統(tǒng)（英語；Operat

4、ing System，簡稱OS）是一管理電腦硬件與軟件資源的程序，同時也是計算機系統(tǒng)的內(nèi)核與基石。操作系統(tǒng)身負諸如管理與配置內(nèi)存、決定系統(tǒng)資源供需的優(yōu)先次序、控制輸入與輸出設(shè)備、操作網(wǎng)絡(luò)與管理文件系統(tǒng)等基本事務(wù)。操作系統(tǒng)是管理計算機系統(tǒng)的全部硬件資源包括軟件資源及數(shù)據(jù)資源;控制程序運行;改善人機界面;為其它應用軟件提供支持等，使計算機系統(tǒng)所有資源最大限度地發(fā)揮作用，為用戶提供方便的、有效的、友善的服務(wù)界面。操作系統(tǒng)是一個龐大的管理控制程

5、序，大致包括5個方面的管理功能:進程與處理機管理、作業(yè)管理、存儲管理、設(shè)備管理、文件管理。</p><p>　　在地址映射過程中，若在頁面中發(fā)現(xiàn)所要訪問的頁面不再內(nèi)存中，則產(chǎn)生缺頁中斷。當發(fā)生缺頁中斷時操作系統(tǒng)必須在內(nèi)存選擇一個頁面將其移出內(nèi) 存，以便為即將調(diào)入的頁面讓出空間。而用來選擇淘汰哪一頁的規(guī)則叫做頁面置換算法（Page-Replacement Algorithms）。 </p><p

6、>　　關(guān)鍵詞：操作系統(tǒng)；OPT頁面置換算法; FIFO先進先出的算法；LRR最近最少使用算;LFR最少訪問頁面算法;NUR最近最不經(jīng)常使用算法</p><p><b>　　Abstract</b></p><p>　　Operating system (in English; Operating System, referred to as OS) is a c

7、omputer hardware and software resources management procedures, but also the core and foundation of the computer system. Who are charged with operating systems such as memory management and allocation, supply and demand d

8、etermine the priority of system resources, control input and output devices, operation and management of network file systems and other basic services. The operating system is managing all the hardware resou</p>&

9、lt;p>　　In the address mapping process, if found to be in the page to access the page no longer in memory, then generate a page fault. When a page fault occurs the operating system must select a page in memory of their

10、 out of memory in order to be transferred to the page to make room. The page used to select out what the rules are called page replacement algorithm (Page-Replacement Algorithms).</p><p>　　Keywords：Operating

11、 system; First Input First Output; Least Recently Used;OPT; Least Frequently Used;NUR</p><p><b>　　目 錄</b></p><p>　　第一章 課題背景…………………………………………………………………………..x</p><p>　　1.1

12、關(guān)于頁面置換算法……………………………………………………………………...x</p><p>　　第二章設(shè)計簡介及設(shè)計方案論述 ……………………………………………………….. x</p><p>　　2.1 程序運行平臺……………………………………..………………………….………..x </p><p>　　2.2 程序的主要功能………………….……………….

13、.………………………….…x </p><p>　　2.3 XXXX ……………………………………………………..………………………….…x </p><p>　　第三章詳細設(shè)計…………………………………………………………..……………….. x</p><p>　　3.1 XXXX ……………………………………………………..………………………….…x &l

14、t;/p><p>　　3.1 XXXX ……………………………………………………..………………………….…x </p><p>　　第四章設(shè)計結(jié)果及分析…………………………………………………..……………….. x</p><p>　　4.1 XXXX …………………………………………….………………………………..….…x </p><p&

15、gt;　　4.2 XXXX ….…………………………………………………..………………………….…x </p><p>　　4.3 XXXX …….………………………………………………..………………………….…x </p><p>　　總 結(jié) …….……………………………………………………..………………………….…x </p><p>　　致 謝 …….……

16、………………………………………………..………………………….…x </p><p>　　參考文獻 …….………………..………………………………..………………………….…x </p><p>　　附錄 主要程序代碼 ………...………………………………..………………………….…x </p><p><b>　　第一章 課題背景</b>

17、</p><p>　　1.1 關(guān)于頁面置換算法</p><p>　　1.1.1頁面置換算法及其分類</p><p>　　在地址映射過程中，若在頁面中發(fā)現(xiàn)所要訪問的頁面不再內(nèi)存中，則產(chǎn)生缺頁中斷。當發(fā)生缺頁中斷時操作系統(tǒng)必須在內(nèi)存選擇一個頁面將其移出內(nèi) 存，以便為即將調(diào)入的頁面讓出空間。而用來選擇淘汰哪一頁的規(guī)則叫做頁面置換算法。 </p><p&

18、gt;　　常見的置換算法有： </p><p>　　1．最佳置換算法（OPT）（理想置換算法） </p><p>　　2．先進現(xiàn)出置換算法（FIFO）： </p><p>　　3．最近最久未使用（LRU）算法 </p><p>　　4．Clock置換算法（LRU算法的近似實現(xiàn)） </p><p>　　5．最少使用（LF

19、U）置換算法 </p><p>　　6．頁面緩沖置換算法</p><p>　　1.1.2關(guān)于頁面置換算法模擬程序問題的產(chǎn)生</p><p>　　在各種存儲器管理方式中，有一個共同的特點，即它們都要求將一個作業(yè)全部裝入內(nèi)存方能運行，但是有兩種情況：（1） 有的作業(yè)很大，不能全部裝入內(nèi)存，致使作業(yè)無法運行；（2） 有大量作業(yè)要求運行，但內(nèi)存容量不足以容納所有這些作業(yè)。而

20、虛擬內(nèi)存技術(shù)正式從邏輯上擴充內(nèi)存容量，將會解決以上兩個問題。從內(nèi)存中調(diào)出一頁程序或數(shù)據(jù)送磁盤的對換區(qū)中，通常，把選擇換出的頁面的算法稱為頁面置換算法（Page-Replacement Algorithms）。進而頁面置換算法模擬程序能客觀的將其工作原理展現(xiàn)在我們面前。</p><p>　　第二章 設(shè)計簡介及設(shè)計方案論述</p><p><b>　　2.1程序運行平臺</

21、b></p><p><b>　　VC++6.0</b></p><p>　　具體操作如下：在VC++6.0的環(huán)境下準備用時鐘函數(shù)調(diào)用庫函數(shù)（#include <time.h>）、 取時鐘時間并存入t調(diào)用庫函數(shù)（t=time(NULL)）、 用時間t初始化隨機數(shù)發(fā)生器調(diào)用 庫函數(shù)（srand(t)返回一個1~10之間的隨機數(shù)（x=rand( )%10

22、+1） 。編寫三種算法。</p><p>　　2.2程序的主要功能</p><p>　　2.2.1隨機產(chǎn)生頁面</p><p>　　用隨機數(shù)方法產(chǎn)生頁面走向，頁面走向長度為L。</p><p>　　2.2.2 FIFO算法</p><p>　　該算法總是淘汰最先進入內(nèi)存的頁面，既選擇在內(nèi)存中駐留時間最久的頁面予以淘汰。

23、</p><p>　　2.2.3 LRU算法</p><p>　　在前面幾條指令中使用頻繁的頁面很可能在后面的幾條指令中頻繁使用。反過來說，已經(jīng)很久沒有使用的頁面很有可能在未來較長的一段時間內(nèi)不會被用到。這個思想提示了一個可以實現(xiàn)的算法：在缺頁發(fā)生時，淘汰掉最久未使用的頁。</p><p>　　2.2.4LFR算法</p><p>　　在缺頁

24、中斷發(fā)生時，置換未使用時間最長的頁面。這個策略稱為LRU（Least Recently Used，最近最少使用）頁面置換算法</p><p>　　2.2.5NUR算法</p><p>　　NRU在需要淘汰某一頁時，從那些最近一個時期內(nèi)未被訪問的頁中任選一頁淘汰。只要在頁表中增設(shè)一個訪問位即可實現(xiàn)。當某頁被訪問時，訪問位置1。否則， 訪問位置0。系統(tǒng)周期性地對所有引用位清零。當需淘汰一頁時，

25、從那些訪問位為零的頁中選一頁進行淘汰。如果引用位全0或全1，NRU算法退化為FIFO算 法。</p><p><b>　　2.3總體設(shè)計</b></p><p><b>　　2.31結(jié)構(gòu)圖</b></p><p>　　4.2 主要的函數(shù)</p><p>　　Input(int m,Pro p[L]

26、)（打印頁面走向狀態(tài)）；</p><p>　　void print(Pro *page1)（打印當前的頁面）；</p><p>　　int Search(int e,Pro *page1 )（尋找內(nèi)存塊中與e相同的塊號）； </p><p>　　int Max(Pro *page1)（尋找最近最長未使用的頁面）；</p><p>　　i

27、nt Count(Pro *page1,int i,int t,Pro p[L])（記錄當前內(nèi)存塊中頁面離下次使用間隔長度）；</p><p>　　int main()（主函數(shù)）；</p><p><b>　　.隨機數(shù)發(fā)生器 </b></p><p>　　#include <stdlib.h></p><p&

28、gt;　　#include <time.h> //準備用時鐘函數(shù)調(diào)用庫函數(shù)</p><p>　　t=time(NULL);//取時鐘時間并存入t調(diào)用庫函數(shù)</p><p>　　srand(t);//用時間t初始化隨機數(shù)發(fā)生器調(diào)用庫函數(shù)</p><p>　　x=rand( )%10+1;//返回一個1~10之間的隨機數(shù)</p><p&

29、gt;<b>　　第三章 詳細設(shè)計</b></p><p>　　4.1 FIFO（先進先出）</p><p>　　設(shè)計原理：需要進行頁面置換，即把內(nèi)存中裝入最早的那個頁面淘汰，換入當前的頁面。</p><p><b>　　算法流程圖</b></p><p><b>　　Y</b&g

30、t;</p><p><b>　　N</b></p><p><b>　　N</b></p><p><b>　　Y</b></p><p>　　圖4-1FIFO算法流程圖</p><p>　　代碼：if(c==1)//FIFO頁面置換</p>

31、;<p><b>　　{</b></p><p><b>　　n=0;</b></p><p>　　cout<<" ****************************************** "<<endl;</p><p>　　co

32、ut<<endl;</p><p>　　cout<<" FIFO算法頁面置換情況如下: "<<endl;</p><p>　　cout<<endl;</p><p>　　cout<<" ******************

33、************************ "<<endl;</p><p>　　while(i<m)</p><p><b>　　{</b></p><p>　　if(Search(p[i].num,page)>=0)//當前頁面在內(nèi)存中</p><p>　　{ co

34、ut<<p[i].num<<" ";//輸出當前頁p[i].num</p><p>　　cout<<"不缺頁"<<endl;</p><p><b>　　i++;//i加1</b></p><p><b>　　}</b></p&

35、gt;<p>　　else //當前頁不在內(nèi)存中</p><p><b>　　{ </b></p><p>　　if(t==M)t=0;</p><p><b>　　else </b></p><p><b>　　{</b></p><p&g

36、t;　　n++;//缺頁次數(shù)加1</p><p>　　page[t].num=p[i].num; //把當前頁面放入內(nèi)存中</p><p>　　cout<<p[i].num<<" ";</p><p>　　print(page); //打印當前頁面</p><p>　　t+

37、+; //下一個內(nèi)存塊</p><p>　　i++; //指向下一個頁面</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p&

38、gt;　　cout<<"缺頁次數(shù)："<<n<<" 缺頁率："<<n/m<<endl; </p><p><b>　　}</b></p><p>　　4.2 LRU（最近最久未使用）</p><p>　　設(shè)計原理：當需要淘汰某一頁

39、時，選擇離當前時間最近的一段時間內(nèi)最久沒有使用過的頁先淘汰該算法的主要出發(fā)點是，如果某頁被訪問了，則它可能馬上還要被訪問。或者反過來說如果某頁很長時間未被訪問，則它在最近一段時間也不會被訪問。</p><p><b>　　算法流程圖：</b></p><p><b>　　Y</b></p><p><b>　　N

40、</b></p><p>　　Y N</p><p>　　圖4-2 LRU算法流程圖</p><p>　　代碼：if(c==2)//LRU頁面置換</p><p><b>　　{</b></p><p><b>　

41、　n=0;</b></p><p>　　cout<<" ****************************************** "<<endl;</p><p>　　cout<<endl;</p><p>　　cout<<"

42、 LRU算法頁面置換情況如下: "<<endl; </p><p>　　cout<<endl;</p><p>　　cout<<" ****************************************** "<<endl;</p><p>

43、;　　while(i<m)</p><p><b>　　{</b></p><p><b>　　int a;</b></p><p>　　t=Search(p[i].num,page);</p><p>　　if(t>=0) //如果已在內(nèi)存

44、塊中</p><p><b>　　{</b></p><p>　　page[t].time=0; //把與它相同的內(nèi)存塊的時間置0</p><p>　　for(a=0;a<M;a++)</p><p>　　if(a!=t)page[a].time++; //其它的時間

45、加1</p><p>　　cout<<p[i].num<<" ";</p><p>　　cout<<"不缺頁"<<endl;</p><p><b>　　}</b></p><p>　　else

46、 //如果不在內(nèi)存塊中</p><p><b>　　{ </b></p><p>　　n++; //缺頁次數(shù)加1</p><p>　　t=Max(page); //返回最近最久未使用的塊號賦值給t</p><p>　　page[t].num=p[i].num; /

47、/進行替換</p><p>　　page[t].time=0; //替換后時間置為0</p><p>　　cout<<p[i].num<<" ";</p><p>　　print(page);</p><p>　　for(a=0;a<M;a++)</p>

48、<p>　　if(a!=t)page[a].time++; //其它的時間加1</p><p><b>　　} </b></p><p><b>　　i++; </b></p><p><b>　　}</b></p><p>　　cout

49、<<"缺頁次數(shù)："<<n<<" 缺頁率："<<n/m<<endl; </p><p><b>　　}</b></p><p>　　4.3 OPT（最佳置換算法）</p><p>　　設(shè)計原理：需要進行頁面置換，把內(nèi)存中以后一段時間都不使用或

50、是使用時間離現(xiàn)在最遠的頁面換出。</p><p><b>　　流程圖：</b></p><p><b>　　Y</b></p><p><b>　　N</b></p><p>　　Y N</p><

51、;p>　　圖4-3 OPT 流程圖</p><p>　　代碼： if(c==3) //OPT頁面置換</p><p><b>　　{</b></p><p><b>　　n=0;</b></p><p>　　cout<<" ***********

52、******************************* "<<endl;</p><p>　　cout<<endl;</p><p>　　cout<<" OPT算法置換情況如下:"<<endl;</p><p>　　cout<<endl;&l

53、t;/p><p>　　cout<<" ****************************************** "<<endl;</p><p>　　while(i<m)</p><p><b>　　{</b></p><p>　　if(Search

54、(p[i].num,page)>=0) //如果已在內(nèi)存塊中</p><p><b>　　{</b></p><p>　　cout<<p[i].num<<" ";</p><p>　　cout<<"不缺頁"<<endl;</p>

55、<p><b>　　i++;</b></p><p><b>　　}</b></p><p>　　else //如果不在內(nèi)存塊中</p><p><b>　　{</b></p><p><b>　　int a=0;&

56、lt;/b></p><p>　　for(t=0;t<M;t++)</p><p>　　if(page[t].num==0)a++; //記錄空的內(nèi)存塊數(shù)</p><p>　　if(a!=0) //有空內(nèi)存塊</p><p><b>　　{</b></p>

57、<p><b>　　int q=M;</b></p><p>　　for(t=0;t<M;t++)</p><p>　　if(page[t].num==0&&q>t)q=t; //把空內(nèi)存塊中塊號最小的找出來</p><p>　　page[q].num=p[i].num;</p>&

58、lt;p><b>　　n++;</b></p><p>　　cout<<p[i].num<<" ";</p><p>　　print(page);</p><p><b>　　i++;</b></p><p><b>　　}</b&

59、gt;</p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　int temp=0,s;</p><p>　　for(t=0;t<M;t++) //尋找內(nèi)存塊中下次使用離現(xiàn)在最久的頁面</p&g

60、t;<p>　　if(temp<Count(page,i,t,p))</p><p><b>　　{</b></p><p>　　temp=Count(page,i,t,p);</p><p><b>　　s=t;</b></p><p>　　} //把找到的塊號賦給

61、s</p><p>　　page[s].num=p[i].num;</p><p><b>　　n++;</b></p><p>　　cout<<p[i].num<<" ";</p><p>　　print(page);</p><p><b&

62、gt;　　i++;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　cout<<"缺頁次數(shù)："<<n<<&q

63、uot; 缺頁率："<<n/m<<endl;</p><p><b>　　}</b></p><p>　　第四章 設(shè)計結(jié)果及分析</p><p><b>　　4.1實現(xiàn)結(jié)果</b></p><p>　　程序在運行的情況下，進入主界面輸入菜單，如圖3-3所示：

64、</p><p><b>　　輸入14：</b></p><p>　　圖4-5 輸入14后的輸出圖</p><p><b>　　輸入25：</b></p><p>　　圖5-6輸入數(shù)據(jù)25后輸出圖</p><p><b>　　輸入數(shù)據(jù)18：</b><

65、;/p><p>　　圖5-7 輸入數(shù)據(jù)18后的輸出圖</p><p><b>　　輸入數(shù)據(jù)：</b></p><p><b>　　圖5-8輸出圖</b></p><p>　　選1，進入FIFO頁面置換：</p><p>　　圖5-9 FIFO的輸出圖</p><

66、;p>　　選2，進入LRU頁面置換：</p><p>　　圖5-10 LRU的輸出圖</p><p>　　輸入3，進入OPT頁面置換：</p><p>　　圖5-11 OPT的輸出圖</p><p><b>　　總 結(jié)</b></p><p>　　通過對頁面置換算法模擬程序的程序設(shè)計，讓

67、我對虛擬頁式存儲管理有了更深的了解。剛開始拿到這個題目覺得很難，不知道該怎么下手，因為是自己第一次用C語言編寫操作系統(tǒng)程序。但是搞懂了頁面置換的思想以后，對編程就有了一定的思路。經(jīng)過幾天的編寫，程序也終于寫出來啊。但是卻遇到了許多困難，程序的調(diào)試也出現(xiàn)了許多的錯誤。但是經(jīng)過幾次上機操作，在老師的指導和幫助下，程序最終還是完成了。通過這次的程序設(shè)計，讓我對C語言有了更深一步的了解和認識，編程能力也有了提高，我認到學好計算機要重視實踐操作，

68、只有真正動手了才知道自己還有那些不足之處。</p><p><b>　　致 謝</b></p><p>　　本次課程設(shè)計能順利完成，感謝學校的大力支持,感謝計算機科學系為我們提供實練的機會,感謝老師的細心教導。</p><p>　　在這次課程設(shè)計中，我學到了很多東西，對C語言編寫操作系統(tǒng)有了一定的認識，自己的編程能力也有了提高。雖然在課程設(shè)

69、計中我遇到了很多的困難， 但是也得到了很多人的幫助，在他們的幫助下，我才能順利完成自己的課程設(shè)計。我要感謝我的老師和同學們，感謝他們的幫助，在我迷茫的時候給了我許多好的建議，有了他們的幫助，我的程序才能順利的完成。 </p><p><b>　　參考文獻</b></p><p>　　參考文獻采用順序編碼制格式著錄。主要責任者，三名以內(nèi)的，全部列出；超過三名時，后面加

70、“等.”字樣。</p><p>　　參考文獻類型及標識：</p><p>　　其他未作說明的文獻，建議采用單字母“Z”。</p><p>　　參考文獻編排格式（注意嚴格使用格式中的符號，特別注意區(qū)分“，”與“.”）：</p><p>　?。?）對于專著、論文集、學位論文、報告，格式如下：</p><p>　　[序號]

71、主要責任者．文獻題名[X]．出版地：出版者，出版年．起止頁碼．</p><p>　　其中X代表文獻類型標識。</p><p>　　（2）對于期刊文章，格式如下：</p><p>　　[序號] 主要責任者．文獻題名[J]．刊名，年，卷（期）：起止頁碼．</p><p>　　（3）對于報紙文章，格式如下：</p><p>

72、　　[序號] 主要責任者．文獻題名[N]．報紙名，出版日期（版次）．</p><p>　　（4）對于國際、國家標準，格式如下：</p><p>　　[序號] 標準編號，標準名稱[S]． </p><p>　　（5）對于專利，格式如下：</p><p>　　[序號] 專利所有者．專利題名[P]．專利國別：專利號，出版日期．</p>