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

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數(shù)：15 大小：245.50KB 人氣指數(shù)：12 舉報 版權申訴

已閱讀1頁，還剩14頁未讀，繼續(xù)免費閱讀

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

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

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

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

4、1 測試方案4　　4.2 測試結果5　　4.3測試結果分析8　　5 設計小結8　　6 參考文獻9　　附錄程序代碼9<

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

43、　　#define M 40　　int N;　　struct Pro//結構體　　{　　int num,time;<b&g

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

60、t;f:FIFO頁面置換"<<endl;　　cout<<"l:LRU頁面置換"<<endl;　　cout<<"按其它鍵結束"<<endl;　　cin>>c;

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

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

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

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

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

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

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

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

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

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

71、dl;　　}　　}while(c=='f'||c=='l'||c=='o');　　return 0;　　}&l

眾賞文庫> 全部分類> 畢業(yè)設計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網頁內容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內容本身不做任何修改或編輯，并不能對任何下載內容負責。
6. 下載文件中如有侵權或不適當內容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

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

文檔簡介

溫馨提示

最新文檔

評論

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

文檔簡介

溫馨提示

最新文檔

評論

免費下載