操作系統(tǒng)課程設(shè)計--請求頁式存儲管理

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：docx 頁數(shù)：17 大?。?48.35KB 人氣指數(shù)：12 舉報 版權(quán)申訴

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

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進(jìn)行舉報或認(rèn)領(lǐng)

文檔簡介

1、　　操作系統(tǒng)課程設(shè)計　　請求頁式存儲管理　　學(xué)院：　　學(xué)號：　　姓名：</b&

2、gt;　　輔導(dǎo)老師：　　設(shè)計四：　　1.設(shè)計目的　　請求頁式管理是一種常用的虛擬存儲管理技術(shù)。本設(shè)計通過請求頁式存儲管理中頁面置換算法模擬設(shè)計，了解虛擬存儲技

3、術(shù)的特點，掌握請求頁式管理的頁面置換算法。　　2.設(shè)計內(nèi)容：　　通過隨機數(shù)產(chǎn)生一個指令序列，共320條指令。指令的地址按下述原則生成：　?、?50% 的指令是順序執(zhí)行的；　?、?25% 的指令是均勻分布在前地址部分；

4、;　　③ 25% 的指令是均勻分布在后地址部分。　　具體的實施方法是：　?、僭?[0,319] 的指令地址之間隨機選取一起點 m；　?、陧樞驁?zhí)行一條指令；　　③在前地址[0,m+1]中隨機選取一條指令并執(zhí)行，該指

5、令的地址為 m′； 　?、茼樞驁?zhí)行一條指令，其地址為 m′+1；　?、菰诤蟮刂?[m′+2,319] 中隨機選取一條指令并執(zhí)行；　　⑥重復(fù)上述步驟② ~ ⑤ ，直到執(zhí)行 320 次指令。　　將指令序列變換成為頁地址流　　設(shè)：①

6、頁面大小為 1K；　?、谟脩魞?nèi)存容量為 4 頁到 32 頁；　?、塾脩籼摯嫒萘繛?32K 。　　在用戶虛存中，按每 K 存放 10 條指令排列虛存地址，即 320 條指令在虛存中的存放方式為：　　第 0 條 ~ 第 9 條指令為第 0 頁 ( 對應(yīng)虛存地址為 [0,9]

7、)；　　第 10 條 ~ 第 19 條指令為第 1 頁 ( 對應(yīng)虛存地址為 [10,19] ) ；　　┇　　┇　　第 310 條 ~ 第 319 條指令為第 31 頁 ( 對應(yīng)虛存地址為 [310

8、,319]) 。　　按以上方式，用戶指令可組成 32 頁。　　計算并輸出下述各種算法在不同內(nèi)存容量下的命中率。　　先進(jìn)先出的算法 (FIFO)；最近最少使用算法 (LRR)；　　最少訪問頁面算法 (LFR)；最近最不經(jīng)常使用算法 (NUR)。<

9、;p>　　3．實驗環(huán)境　　每個學(xué)生一臺微機，需要安裝windows98或windows2000操作系統(tǒng)，配備VC、VB、java或C編程語言，每個學(xué)生上機時間不少于24個小時。　?。?）、分頁請求系統(tǒng)　　為了能實現(xiàn)請求調(diào)頁和置換功能，系統(tǒng)必須提供必要的硬件支持，其中，最

10、重要的是：　　（1）請求分頁的頁表機制。它是在分頁的頁表機制上增加若干個項而形成的，作為請求分頁的數(shù)據(jù)結(jié)構(gòu)；　　（2）缺頁中斷機構(gòu)。每當(dāng)用戶程序要訪問的頁面尚未調(diào)入內(nèi)存時，便產(chǎn)生一缺頁中斷，以請求OS將所缺的頁面調(diào)入內(nèi)存；　?。?）地址變換機構(gòu)。它同樣是在分頁的地址變換機構(gòu)的基礎(chǔ)上發(fā)展形成的。

11、　　為了實現(xiàn)請求調(diào)頁還須得到OS的支持，在實現(xiàn)請求調(diào)頁功能時，石油OS將所需的頁從外存調(diào)入內(nèi)存；在實現(xiàn)置換功能時，也是由OS將內(nèi)存的某些頁調(diào)至外存。　　4．實驗提示　　提示：A.命中率=1-頁面失效次數(shù)/頁地址流長度　　B.本實驗中，頁地址流長度為320

12、，頁面失效次數(shù)為每次訪問相應(yīng)指令時，該指令所對應(yīng)的頁不在內(nèi)存的次數(shù)。　　C.關(guān)于隨機數(shù)產(chǎn)生方法，采用TC系統(tǒng)提供函數(shù)RAND()和RANDOMIZE()來產(chǎn)生。　　5.自己對算法的理解　　㈠ FIFO頁面置換算法　?、旁砗喪?lt;/b><

13、;/p>　?、僭诜峙鋬?nèi)存頁面數(shù)(AP)小于進(jìn)程頁面數(shù)(PP)時，當(dāng)然是最先運行的AP個頁面放入內(nèi)存。　　②這時有需要處理新的頁面，則將原來內(nèi)存中的AP個頁面最先進(jìn)入的調(diào)出(是以稱為FIFO)，然后將新頁面放入。　?、垡院笕绻儆行马撁嫘枰{(diào)入，則都按⑵的規(guī)則進(jìn)行。　　算法特點：所使用的

14、內(nèi)存頁面構(gòu)成一個隊列。　?、?LRU頁面置換算法　?、旁硭闶?lt;/b>　?、佼?dāng)分配內(nèi)存頁面數(shù)(AP)小于進(jìn)程頁面數(shù)(PP)時，當(dāng)然是把最先執(zhí)行的AP個頁面放入內(nèi)存。　?、诋?dāng)需要調(diào)頁面進(jìn)入內(nèi)存，而當(dāng)前分配的內(nèi)存頁面全部不空閑時，選擇將其中最長

15、時間沒有用到的那個頁面調(diào)出，以空出內(nèi)存來放置新調(diào)入的頁面(稱為LRU)。　　算法特點：每個頁面都有屬性來表示有多長時間未被CPU使用的信息。　?、鏛FU即最不經(jīng)常使用頁置換算法　　原理簡述　　要求在頁置換時置換引用計數(shù)最小的頁，因為經(jīng)

16、常使用的頁應(yīng)該有一個較大的引用次數(shù)。但是有些頁在開始時使用次數(shù)很多，但以后就不再使用，這類頁將會長時間留在內(nèi)存中，因此可以將引用計數(shù)寄存器定時右移一位，形成指數(shù)衰減的平均使用次數(shù)。　　LRU算法的硬件支持　　把LRU算法作為頁面置換算法是比較好的，它對于各種類型的程序都能適用，但實現(xiàn)起來有相當(dāng)大的難度，因為它要求系統(tǒng)具有較多的支持硬件。所要解決的問題有：

17、　　1.一個進(jìn)程在內(nèi)存中的各個頁面各有多久時間未被進(jìn)程訪問；　　2.如何快速地知道哪一頁最近最久未使用的頁面。為此，須利用以下兩類支持硬件：　?。?）寄存器　　用于記錄某進(jìn)程在內(nèi)存中各頁的使用情況。<p&

18、gt;　?。?）棧　　可利用一個特殊的棧來保存當(dāng)前使用的各個頁面的頁面號。每當(dāng)進(jìn)程訪問某頁面時，便將該頁面的頁面號從棧中移出，將它壓入棧頂。　　算法特點:LFU算法并不能真正反映出頁面的使用情況，因為在每一時間間隔內(nèi)，只是用寄存器的一位來記錄頁的使用情況，因此，訪問一次和訪問10000次是等效的。

19、　?、?NUR頁面置換算法　?、旁砗喪?lt;/b>　　所謂“最近未使用”，首先是要對“近”作一個界定，比如CLEAR_PERIOD=50，便是指在CPU最近的50次進(jìn)程頁面處理工作中，都沒有處理到的頁面。那么可能會有以下幾種情況：　?、偃绻@樣的頁面只有一個，就將

20、其換出，放入需要處理的新頁面。　?、谌绻羞@樣的頁面不止一個，就在這些頁面中任取一個換出(可以是下標(biāo)最小的，或者是下標(biāo)最大的)，放入需要處理的頁面。　　③如果沒有一個這樣的頁面，就隨意換出一個頁面(可以是下標(biāo)最小的，或者是下標(biāo)最大的)。　　算法特點：有一個循環(huán)周期，每到達(dá)這個周期，所有頁面存放是否被CPU處理的信

21、息的屬性均被置于初始態(tài)(沒有被訪問)。　　6．實驗流程圖 　　7. 實驗運行結(jié)果　　等等。　　8. 實驗源程序</

22、p>　　#include<iostream>　　#include<time.h>　　using namespace std;　　const int MaxNum=320;//指令數(shù)　　const int M=5;//內(nèi)存

23、容量　　int PageOrder[MaxNum];//頁面請求　　int Simulate[MaxNum][M];//頁面訪問過程　　int PageCount[M],LackNum;//PageCount用來記錄LRU算法中最久未使用時間,LackNum記錄缺頁數(shù)

24、float PageRate;//命中率　　int PageCount1[32];　　bool IsExit(int i)//FIFO算法中判斷新的頁面請求是否在內(nèi)存中　　{　　bool f=false;<

25、;p>　　for(int j=0;j<M;j++)　　{　　if(Simulate[i-1][j]==PageOrder[i])//在前一次頁面請求過程中尋找是否存在新的頁面請求　　{ <p

26、>　　f=true;　　}　　}　　return f;　　}</p&g

27、t;　　int IsExitLRU(int i)//LRU算法中判斷新的頁面請求是否在內(nèi)存中　　{　　int f=-1;　　for(int j=0;j<M;j++)&l

28、t;b>　　{　　if(Simulate[i-1][j]==PageOrder[i])　　{ 　　f=j;　　}</p&

29、gt;　　}　　return f;　　}　　int Compare()//LRU算法找出內(nèi)存中需要置換出來的頁面　　{

30、　　int p,q;　　p=PageCount[0];　　q=0;　　for(int i=1;i<M;i++)

31、　　{　　if(p<PageCount[i])　　{　　p=PageCount[i];　　q=i;　　}<

32、;/b>　　}　　return q;　　}　　void Init() //初始化頁框　　{

33、　　for(int k=0;k<MaxNum;k++)　　{　　int n=rand()%320;//隨機數(shù)產(chǎn)生320次指令　　PageOrder[k]=n/10;//根據(jù)指令產(chǎn)生320次頁面請求</p

34、>　　}　　for(int i=0;i<MaxNum;i++)//初始化頁面訪問過程　　{　　for(int j=0;j<M;j++)

35、{　　Simulate[i][j]=-1;　　}　　}　　for(int q=0;q<M;q++)//初始化最久未使用數(shù)組<

36、;b>　　{　　PageCount[q]=0;　　}　　}　　void OutPut()//輸出　　{<

37、/b>　　int i,j;　　cout<<"頁面訪問序列:"<<endl;　　for(j=0;j<MaxNum;j++)　　{</p&

38、gt;　　cout<<PageOrder[j]<<" ";　　}　　cout<<endl;　　cout<<"頁面訪問過程(只顯示前10個):"<<endl

39、;　　for(i=0;i<10;i++)　　{　　for(j=0;j<M;j++)　　{　　if(Simulate[i][j]==-1)<

40、;/p>　　cout<<" ";　　else　　cout<<Simulate[i][j]<<" ";　　}&

41、lt;p>　　cout<<endl;　　}　　cout<<"缺頁數(shù)= "<<LackNum<<endl;　　cout<<"命中率= "<<PageRate&l

42、t;<endl;　　cout<<"--------------------------------------------------------------"<<endl;　　}　　void FIFO()//FIFO算法&l

43、t;/p>　　{　　int j,x=0,y=0;　　LackNum=0,　　Init();　　for(j=0;j<M;j++)//將前五個頁面請求直接放入內(nèi)存中&

44、lt;/p>　　{　　for(int k=0;k<=j;k++)　　{　　if(j==k)　　Simulate[j][k]=

45、PageOrder[j];　　else　　Simulate[j][k]=Simulate[j-1][k]; 　　}　　//LackNum++;<

46、p>　　}　　for(x=M;x<MaxNum;x++)　　{　　for(int t=0;t<M;t++)//先將前一次頁面訪問過程賦值給新的頁面訪問過程　　{

47、　　Simulate[x][t]=Simulate[x-1][t];　　}　　if(!IsExit(x))//根據(jù)新訪問頁面是否存在內(nèi)存中來更新頁面訪問過程　　{</p&

48、gt;　　LackNum++;　　Simulate[x][y%M]=PageOrder[x];　　y++;　　}　　}

49、;　　PageRate=1-((float)LackNum/(float)MaxNum);//算出命中率　　OutPut();　　}　　void LRU()//LRU算法&l

50、t;b>　　{　　int j,x=0,y=0;　　LackNum=0,　　Init();　　for(j=0;j<M;j++)//將前五個頁面請求直接放入內(nèi)存中&

51、lt;b>　　{　　for(int k=0;k<=j;k++)　　{　　PageCount[k]++;　　if(j==k)

52、　　Simulate[j][k]=PageOrder[j];　　else　　Simulate[j][k]=Simulate[j-1][k]; 　　}　　LackNum++;

53、 　　}　　for(x=M;x<MaxNum;x++)　　{　　for(int t=0;t<M;t++)//先將前一次頁面訪問過程賦值給新的頁面訪問過程&

54、lt;p>　　{　　Simulate[x][t]=Simulate[x-1][t];　　}　　int p=IsExitLRU(x);　　if(p==-1)//根據(jù)反回的p值來更新頁面訪問過程

55、　　{　　int k;　　k=Compare();　　for(int w=0;w<M;w++)　　{</

56、p>　　if(w!=k)　　PageCount[w]++;　　else　　PageCount[k]=1;　　}

57、　　Simulate[x][k]=PageOrder[x];　　LackNum++;　　}　　else　　{&l

58、t;p>　　for(int w=0;w<M;w++)　　{　　if(w!=p)　　PageCount[w]++;　　else

59、　　PageCount[p]=1;　　}　　}　　}　　PageRate=1-((float)LackNum/(float)MaxNum)

60、;//算出命中率　　OutPut();　　}　　//最近最不常用調(diào)度算法(LFU)　　void LFU(){}　　void NUR(){}</p&g

61、t;　　void YourChoice(int choice)　　{　　switch(choice)　　{　　case 1:</p

62、>　　cout<<"----------------------------------------------------------"<<endl;　　cout<<"FIFO算法結(jié)果如下："<<endl;　　FIFO(

63、);　　break;　　case 2:　　cout<<"----------------------------------------------------------"<&l

64、t;endl;　　cout<<"LRU算法結(jié)果如下："<<endl;　　LRU();　　break;　　case 3:</b&g

65、t;　　cout<<"----------------------------------------------------------"<<endl;　　cout<<"LFU算法結(jié)果如下："<<endl;

66、　　//LFU();　　break;　　case 4:　　cout<<"----------------------------------------------------------&quo

67、t;<<endl;　　cout<<"NUR算法結(jié)果如下："<<endl;　　//NUR();　　break;　　case

68、5:　　break;　　default:　　cout<<"重新選擇算法：1--FIFO 2--LRU 3--LFU 4--NUR 5--退出 "<<endl;</p&

69、gt;　　cin>>choice;　　YourChoice(choice);　　}　　}　　void main()<

70、;b>　　{　　int choice,i=1;　　while(i)　　{　　cout<<"請選擇算法：1--FIFO 2--LRU 3--LFU

71、4--NUR 5--退出 "<<endl;　　cin>>choice;　　if(choice==5)　　{　　i=0;&

72、lt;b>　　} 　　else 　　{ 　　YourChoice(choice);　　}

73、　　}　　}　　9. 實驗體會　　通過上面的截圖可以發(fā)現(xiàn)，實驗中指令是由隨機函數(shù)產(chǎn)生的,然后根據(jù)產(chǎn)生的指令算出需要訪問的頁面.在本次實驗中我寫了四個頁面置換算法—(先進(jìn)先出)FIFO算法和(最久未使用

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

溫馨提示

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

操作系統(tǒng)課程設(shè)計--請求頁式存儲管理

文檔簡介

溫馨提示

最新文檔

評論

操作系統(tǒng)課程設(shè)計--請求頁式存儲管理

文檔簡介

溫馨提示

最新文檔

評論

免費下載