請求頁式管理缺頁中斷模擬設(shè)計--+LRU隨機(jī)淘汰算法

1、學(xué) 號： 0120610340231課 程 設(shè) 計題 目請求頁式管理缺頁中斷模擬設(shè)計- LRU、隨機(jī)淘汰算法學(xué) 院計算機(jī)學(xué)院專 業(yè)計算機(jī)科學(xué)與技術(shù)班 級計算機(jī)0602姓 名朱 林指導(dǎo)教師王 紅 霞2009年01月08日課程設(shè)計任務(wù)書學(xué)生姓名： 朱 林 專業(yè)班級： 計算機(jī)0602 指導(dǎo)教師： 王紅霞 工作單位： 計算機(jī)科學(xué)與技術(shù)學(xué)院 題 目:請求頁式管理缺頁中斷模擬設(shè)計- LRU、隨機(jī)淘汰算法初始條件：1預(yù)備內(nèi)容：閱讀操作系統(tǒng)的內(nèi)存管理章節(jié)內(nèi)容，了解有關(guān)虛擬存儲器、頁式存儲管理等概念，并體會和了解缺頁和頁面置換的具體實施方法。2實踐準(zhǔn)備：掌握一種計算機(jī)高級語言的使用。要求完成的主要任務(wù): （包括

2、課程設(shè)計工作量及其技術(shù)要求，以及說明書撰寫等具體要求）1實現(xiàn)指定淘汰算法。能夠處理以下的情形： 能夠輸入給作業(yè)分配的內(nèi)存塊數(shù)； 能夠輸入給定的頁面，并計算發(fā)生缺頁的次數(shù)以及缺頁率； 缺頁時，如果發(fā)生頁面置換，輸出淘汰的頁號。2設(shè)計報告內(nèi)容應(yīng)說明： 需求分析； 功能設(shè)計（數(shù)據(jù)結(jié)構(gòu)及模塊說明）； 開發(fā)平臺及源程序的主要部分； 測試用例，運行結(jié)果與運行情況分析； 自我評價與總結(jié)：i）你認(rèn)為你完成的設(shè)計哪些地方做得比較好或比較出色；ii）什么地方做得不太好，以后如何改正；iii）從本設(shè)計得到的收獲（在編寫，調(diào)試，執(zhí)行過程中的經(jīng)驗和教訓(xùn)）；iv）完成本題是否有其他方法（如果有，簡要說明該方法）；v）對實

3、驗題的評價和改進(jìn)意見，請你推薦設(shè)計題目。時間安排：設(shè)計安排一周：周1、周2：完成程序分析及設(shè)計。周2、周3：完成程序調(diào)試及測試。周4、周5：驗收、撰寫課程設(shè)計報告。（注意事項：嚴(yán)禁抄襲，一旦發(fā)現(xiàn)，一律按0分記）指導(dǎo)教師簽名： 年 月 日系主任（或責(zé)任教師）簽名： 年 月 日請求頁式管理缺頁中段模擬設(shè)計 LRU、隨機(jī)淘汰算法1需求分析 用一種計算機(jī)高級語言來實現(xiàn)請求頁式管理缺頁中段模擬設(shè)計的LRU和隨機(jī)淘汰算法，設(shè)計要求如下： 能夠輸入給作業(yè)分配的內(nèi)存塊數(shù)； 能夠輸入給定的頁面，并計算發(fā)生缺頁的次數(shù)以及缺頁率； 缺頁時，如果發(fā)生頁面置換，輸出淘汰的頁號。 請求分頁流程圖： 2功能設(shè)計 2.1數(shù)據(jù)

4、結(jié)構(gòu) （1）用結(jié)構(gòu)體定義頁表表項： struct page int page_num; /頁面號 int memory_num; /頁面對應(yīng)的內(nèi)存物理塊號 int flag; /狀態(tài)標(biāo)志，判斷頁面是否在內(nèi)存 ; (2)算法中涉及到的主要變量： int page_size; /給定的頁面數(shù) int memory_size; /給定的內(nèi)存物理塊數(shù) int *page_array, /存放頁面的輸入序列 int *memory; /存放內(nèi)存物理塊的序列 int lacktime; /缺頁次數(shù) int page; /當(dāng)前頁面號 int *save； /保存被淘汰的頁面號(隨機(jī)算法中) int *cha

5、nge_page; /保存被淘汰的頁面號(LRU算法中) int *weight; /記錄內(nèi)存中頁面的存在次數(shù)(LRU算法中) bool in; /標(biāo)志頁面是否在內(nèi)存中(LRU算法中) 2.2模塊說明 (3)LRU淘汰算法 void LRU() 用一個整形指針change_page保存被淘汰的頁面號； 用一個整形指針weight記錄內(nèi)存中各頁面的存在次數(shù)； a.若當(dāng)前頁在內(nèi)存中，置in的值為1； b.若當(dāng)前頁不在內(nèi)存中且內(nèi)存已滿，lacktime加1，比較內(nèi)存中的頁面的weight值，weight值最大的那個頁面即為將要被淘汰的頁，然后將當(dāng)前頁裝入內(nèi)存，并修改當(dāng)前頁和被淘汰頁的頁表內(nèi)容； c.

6、若當(dāng)前頁不在內(nèi)存中且內(nèi)存未滿，lacktime加1，將此頁裝入內(nèi)存，并修改頁表表項的內(nèi)容； 輸出lacktime的值，缺頁率和被淘汰的頁面號； (4)隨機(jī)淘汰算法 void random() 用一個整形指針save保存被淘汰的頁面號； do a.若當(dāng)前頁面在內(nèi)存中，輸出相關(guān)信息； b.若當(dāng)前頁面不在內(nèi)存中，lacktime加1，將此頁面裝入內(nèi)存，并修 改頁表表項的相應(yīng)內(nèi)容； while(內(nèi)存未滿) 當(dāng)內(nèi)存已滿時： a.若當(dāng)前頁面在內(nèi)存中，輸出相關(guān)信息； b.若當(dāng)前頁面不在內(nèi)存中，lacktime加1，隨機(jī)淘汰內(nèi)存中的一個頁面，將被淘汰的頁面號保存在save中，并修改被淘汰和當(dāng)前頁面 在頁表中的

7、相應(yīng)內(nèi)容； 輸出lacktime的值，缺頁率和被淘汰的頁面號； 3開發(fā)平臺及源程序主要部分 3.1開發(fā)平臺 （1）使用系統(tǒng)：Windows XP （2）使用語言：C+ （3）開發(fā)工具：Visual C+ 6.0 3.2源程序主要部分 隨機(jī)淘汰算法： void random() cout<<"-隨機(jī)-"<<endl;init();int *save=new intpage_size;int count=0;cout<<"隨機(jī)替換算法:"<<endl;int lackTime=0;int replace=0;

8、int is_full=0;int page=0;do if(page_tablepage_arraypage.flag =1) cout<<page_arraypage<<" is in memory"<<endl;page+;if(page=page_size)break;else continue; elselackTime+; cout<<page_arraypage<<"is not in memory!"<<endl; memoryis_full=page_arraypa

9、ge; page_tablepage_arraypage.flag=1;page_tablepage_arraypage.memory_num=is_full; is_full+;page+;if(page=page_size)break;while(is_full!=memory_size); for( int i=page;i<page_size;i+) if(page_tablepage_arrayi.flag =1) cout<<page_arrayi<<" is in memory"<<endl;continue; els

10、e lackTime+; replace=rand()%memory_size; for(int j=0;j<10;j+) if( page_tablej.memory_num=replace) cout<<page_arrayi<<"is not in memory!take place of page "<<j<<endl; savecount+=j; page_tablej.memory_num=-1; page_tablej.flag=0; break; memoryreplace=page_arrayi; pa

11、ge_tablepage_arrayi.flag=1;page_tablepage_arrayi.memory_num=replace; cout<<"缺頁次數(shù)："<<lackTime<<endl;cout<<"缺頁率： "<<double(lackTime)/page_size*100<<"%"<<endl;cout<<"淘汰頁號的序列為："for(int i=0;i<count;i+) cout<<

12、savei<<"->"cout<<"結(jié)束"<<endl;cout<<"-"<<endl;LRU淘汰算法：void LRU()cout<<"-LRU-"<<endl;init();int *change_page=new intpage_size;int *weight=new int memory_size;int i;for(i=0;i<memory_size;i+) memoryi=-1; for(i=0;i<

13、page_size;i+) change_pagei=0; int lackTime=0;int k=0,l=0; bool in=0; int max=0;int q; for(q=0;q<memory_size;q+)cout<<memoryq<<" "cout<<endl; for(i=0;i<page_size;i+) in=0;for(q=0;q<memory_size;q+) if (page_arrayi=memoryq)in=1;break; if(in=0 && memorymemory

14、_size-1!=-1)lackTime+;for(q=0;q<memory_size;q+)weightq=0;for(q=0;q<memory_size;q+)for(int p=i-1;p>=0;p-) weightq+;if(memoryq=page_arrayp)break; max=0; for(q=0;q<memory_size;q+) if(weightq>max) max=weightq;for(q=0;q<memory_size;q+)if (max=weightq) break; change_pagek+=memoryq; memor

15、yq=page_arrayi; if(in=0 && memorymemory_size-1=-1) lackTime+; memoryl+=page_arrayi; for(int q=0;q<memory_size;q+) cout<<memoryq<<" "cout<<endl; cout<<"缺頁次數(shù)："<<lackTime<<endl; cout<<"缺頁率："<<double(lackTime)/page_

16、size*100<<"%"<<endl; cout<<"淘汰頁號：" for(int m=0;m<k;m+) cout<<change_pagem<<"->" cout<<"結(jié)束"<<endl; cout<<"-LRU-"<<endl;main()函數(shù)int main() int select1;int select2;char choice;cout<<"

17、;輸入給定的頁面數(shù)："<<endl;cin>>page_size;cout<<"輸入給作業(yè)分配內(nèi)存的物理塊數(shù)"<<endl;cin>>memory_size;page_array=new intpage_size;memory=new intmemory_size; loop:cout<<"0.用戶輸入請求序列 1.隨機(jī)生成請求序列"<<endl; cin>>select1;if(select1=1) cout<<"隨機(jī)生成頁面

18、請求序列（0-10）"<<endl;int temp1;for(int i=0;i<page_size;i+) temp1=rand()%10; cout<<temp1<<" "page_arrayi=temp1; cout<<endl;else if(select1=0) int temp2;cout<<"輸入"<<page_size<<"個請求頁面號（0-10）"<<endl;for(int i=0;i<page_

19、size;i+) cin>>temp2;page_arrayi=temp2;else exit(0); cout<<"請選擇使用那種替換算法：0、退出 1、LRU 2、隨機(jī)"<<endl;cin>>select2;if(select2=1) LRU();else if(select2=2) random();else exit(0); cout<<"是否繼續(xù)？（Y/y or N/n）"cin>>choice;if(choice='Y' | choice='y&

20、#39;) goto loop;else exit(0);delete page_array;delete memory;return 0;4調(diào)試報告 4.1測試用例 隨機(jī)淘汰算法： 輸入的頁面號序列為：1 3 2 4 2 1 2 1 3 4 ，給定內(nèi)存物理塊數(shù)為3。 LRU淘汰算法：輸入的頁面號序列為：4 2 1 2 3 5 4 3 1 2，給定內(nèi)存物理塊數(shù)為3。 4.2運行結(jié)果及分析 隨機(jī)淘汰算法的運行結(jié)果如下： 結(jié)果分析，如下表： 1 3 2 4 2 1 2 1 3 4 1 1 1 1 1 1 1 1 1 1 3 3 4 4 4 4 4 3 3 2 2 2 2 2 2 2 4 LRU淘汰

21、算法的運行結(jié)果如下： 結(jié)果分析，如下表： 4 2 1 2 3 5 4 3 1 2 4 4 4 4 3 3 3 3 3 3 2 2 2 2 2 4 4 4 2 1 1 1 5 5 5 1 15總結(jié)在本次操作系統(tǒng)課程設(shè)計，我采用C+實現(xiàn)請求頁式管理缺頁中段模擬設(shè)計的隨機(jī)和LRU淘汰算法。首先，應(yīng)了解虛擬存儲器和頁式存儲管理的有關(guān)內(nèi)容，并掌握隨機(jī)和LRU淘汰算法的核心思想及具體的流程。然后，在這個基礎(chǔ)上，結(jié)合所掌握的C+編程方法和技巧，編寫正確的算法。 隨機(jī)淘汰算法比較容易實現(xiàn)，當(dāng)需要調(diào)入一個新頁面進(jìn)入內(nèi)存時，用rand()函數(shù)產(chǎn)生一個0memory_size-1的隨機(jī)數(shù)，作為將要被淘汰的內(nèi)存物理塊

22、號，然后修改頁表內(nèi)容即可。LRU算法就顯得復(fù)雜一些，其核心問題在于怎樣找到內(nèi)存中最近最少使用的那個頁面。最初設(shè)計這個算法時，出現(xiàn)了一點問題，在某種情況下，會淘汰剛剛被訪問過的頁面。經(jīng)過修改，彌補(bǔ)了這個不足之處，算法的運行結(jié)果正確。 從這次的課程設(shè)計中，我有很大收獲。首先，鞏固了所學(xué)的有關(guān)頁式存儲管理的相關(guān)知識，更深層次地理解并掌握了LRU和隨機(jī)淘汰算法的精髓。通過使用C+語言模擬LRU和隨機(jī)算法實現(xiàn)請求頁式管理，進(jìn)一步提高了我的編程能力，并且有助于將操作系統(tǒng)和C+有機(jī)地結(jié)合起來，使我更加明白了學(xué)科之間是緊密聯(lián)系的。 此外，經(jīng)過這次課程設(shè)計，我更加感悟到了，僅僅學(xué)習(xí)書本上的理論知識是不夠的，要在

23、平時多進(jìn)行實際操作，這樣才能融會貫通，更加牢固地掌握所學(xué)知識。在以后的學(xué)習(xí)過程中，我應(yīng)該更加深入學(xué)習(xí)有關(guān)C+的內(nèi)容，提高自己的動手能力。 附錄：F1參考文獻(xiàn)1張堯?qū)W，史美林編著計算機(jī)操作系統(tǒng)教程（第三版）清華大學(xué)出版社2006 2閔聯(lián)營，何克右C+程序設(shè)計教程武漢理工大學(xué)出版社2005F2源代碼#include<iostream>using namespace std;struct page int page_num; int memory_num; int flag; ;page page_table10;int page_size,memory_size;int *page_a

24、rray,*memory;void init() for(int i=0;i<10;i+) page_tablei.page_num=i;page_tablei.memory_num=-1;page_tablei.flag=0;for(int i=0;i<memory_size;i+)memoryi=-1;void random()cout<<"-隨機(jī)-"<<endl;init();int *save=new intpage_size;int count=0;cout<<"隨機(jī)替換算法:"<<e

25、ndl;int lackTime=0;int replace=0; int is_full=0;int page=0;do if(page_tablepage_arraypage.flag =1) cout<<page_arraypage<<" is in memory"<<endl;page+;if(page=page_size)break;else continue; else lackTime+; cout<<page_arraypage<<"is not in memory!"<&

26、lt;endl; memoryis_full=page_arraypage; page_tablepage_arraypage.flag=1;page_tablepage_arraypage.memory_num=is_full； is_full+;page+;if(page=page_size)break;while(is_full!=memory_size); for( int i=page;i<page_size;i+)if(page_tablepage_arrayi.flag =1) cout<<page_arrayi<<" is in memo

27、ry"<<endl;continue;else lackTime+; replace=rand()%memory_size; for(int j=0;j<10;j+) if( page_tablej.memory_num=replace) cout<<page_arrayi<<"is not in memory!take place of page "<<j<<endl; savecount+=j; page_tablej.memory_num=-1; page_tablej.flag=0; bre

28、ak; memoryreplace=page_arrayi; page_tablepage_arrayi.flag=1;page_tablepage_arrayi.memory_num=replace; cout<<"缺頁次數(shù)："<<lackTime<<endl;cout<<"缺頁率： "<<double(lackTime)/page_size*100<<"%"<<endl;cout<<"淘汰頁號的序列為："for(in

29、t i=0;i<count;i+) cout<<savei<<"->"cout<<"結(jié)束"<<endl;cout<<"-"<<endl;void LRU() cout<<"-LRU-"<<endl;init();int *change_page=new intpage_size;int *weight=new int memory_size;int i;for(i=0;i<memory_size;i+)

30、 memoryi=-1; for(i=0;i<page_size;i+) change_pagei=0; int lackTime=0; int k=0,l=0; bool in=0; int max=0;int q; for(q=0;q<memory_size;q+)cout<<memoryq<<" " cout<<endl; for(i=0;i<page_size;i+) in=0; for(q=0;q<memory_size;q+) if (page_arrayi=memoryq) in=1;break; i

31、f(in=0 && memorymemory_size-1!=-1) lackTime+; for(q=0;q<memory_size;q+)weightq=0; for(q=0;q<memory_size;q+) for(int p=i-1;p>=0;p-) weightq+; if(memoryq=page_arrayp)break; max=0; for(q=0;q<memory_size;q+) if(weightq>max) max=weightq; for(q=0;q<memory_size;q+) if (max=weightq

32、) break; change_pagek+=memoryq; memoryq=page_arrayi; if(in=0 && memorymemory_size-1=-1) lackTime+; memoryl+=page_arrayi; for(int q=0;q<memory_size;q+)cout<<memoryq<<" "<<endl;cout<<"缺頁次數(shù)："<<lackTime<<endl;cout<<"缺頁率："<<double(lackTime)/page_size*100<<"%"<<endl;cout<<"淘汰頁號："for(int m=0;m<k;m+) cout<<change_pagem<<"->"cout<<&quo