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

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

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

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

文檔簡介

1、　　信息科學與工程學院　　課程設(shè)計任務(wù)書　　請求頁式存儲管理的頁面置換算法　　專業(yè)：計算機科學與技術(shù) 　　課程：計算機操作系

2、統(tǒng) 　　指導教師：劉彩霞 　　完成時間： 2012年5月----2012年 6月　　課程設(shè)計任務(wù)書及成績評定　　目錄 <p&

3、gt;　　一．設(shè)計目的1　　二．設(shè)計內(nèi)容1　　三．設(shè)計思路1　　1. 計算隨機數(shù)，產(chǎn)生320條指令序列1　　2. 將指令序列變換成為頁地址流2<

4、;/p>　　3. 計算不同算法的命中率2　　4.輸出格式2　　四．實驗報告2　　1．寫出你編寫的C語言程序。2　　2．總結(jié)體會請求頁式存儲管理的實現(xiàn)原理。10

5、　　3. 寫出這三種頁面置換算法的實現(xiàn)思想。10　　4．對不同算法的性能進行評價。10　　五.總結(jié)10　　一．設(shè)計目的　　通過請求頁式存儲管理中頁面

6、置換算法模擬程序，了解虛擬存儲技術(shù)的特點，掌握請求頁式存儲管理的頁面置換算法。　　二．設(shè)計內(nèi)容　　1.通過隨機數(shù)產(chǎn)生一個指令序列，共320條指令，指令的地址按下述原則生產(chǎn)：　　50％的指令是順序執(zhí)行的；　　25％的指令是均勻分布在前地

7、址部分；　　25％的指令是均勻分布在后地址部分。　　2.將指令序列變換成為頁地址流　　設(shè)頁面大小為1K；用戶內(nèi)存容量為4頁到32頁；用戶虛存容量為32K。　　在用戶虛存中，按每K存放10條指令排列虛存地址，即320條指令在虛存中的存放方式為：第0條至第9條指令為第0頁；第

8、10條至19條指令為第1頁；…第310條至319條指令為第31頁。　　3.計算并輸出下述各種算法在不同內(nèi)存容量下的命中率。　　(1) 先進先出算法（FIFO） 　　(2) 最近最少使用算法（LRU）　　(3) 最佳使用算（OPT）

9、　　命中率＝１－頁面失效次數(shù)／頁地址流長度　　本實驗中，頁地址流長度為320，頁面失效次數(shù)為每次訪問相應(yīng)指令時，該指令所對應(yīng)的頁不在內(nèi)存的次數(shù)。　　三．設(shè)計思路 　　1.計算隨機數(shù)，產(chǎn)生320條指令序列　　關(guān)于隨機數(shù)的產(chǎn)生辦法。首先要

10、初始化設(shè)置隨機數(shù)，產(chǎn)生序列的開始點，例如，通過下列語句實現(xiàn)：　　srand ( 400 ) ；　　m＝160；　　for (i＝0；i＜80；i++＝　　{

11、;　　j＝i﹡4；　　a[j]＝m；　　a[j+1]＝m+1；　　a[j+2]＝a[j] ﹡1.0﹡ rand( )/32767；　　a[j+3]＝a[j+2]+1<

12、p>　　m＝a[j+3]+(319-a[j+3]) ﹡1.0﹡rand( )/32767；　　}　　2.將指令序列變換成為頁地址流　　for ( k＝0；k＜320；k++)　　{ pt＝a[k]/10；

13、　　pd= a[k]%10；　　…　　}　　3.計算不同算法的命中率　　rate＝1-1.0﹡U/320 ；　　其中U為缺頁中斷次數(shù)，3

14、20是頁地址流長度。　　4. 輸出格式　　k fifo 1ru　　4 0.23 0.25　　…　　32 1.0 1.0</p&g

15、t;　　四．實驗報告　　1．寫出你編寫的C語言程序。　　#include<conio.h> 　　#include<stdio.h>　　#include<stdlib.h><

16、;/p>　　#include<string.h>　　#define Myprintf printf("|---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---|\n") /*表格控制*/ 　　#define bsiz

17、e 4 //物理塊大小　　#define psize 16 //進程大小　　typedef struct page 　　{ 　　int num; /*記錄頁面號*/ 　　in

18、t time; /*記錄調(diào)入內(nèi)存時間*/ 　　}Page; /* 頁面邏輯結(jié)構(gòu)，結(jié)構(gòu)為方便算法實現(xiàn)設(shè)計*/ 　　Page b[bsize]; /*內(nèi)存單元數(shù)*/ 　　int c[bsize][psize]; /*暫保存內(nèi)存當前的狀態(tài)：緩沖區(qū)*/ &l

19、t;/p>　　int queue[100]; /*記錄調(diào)入隊列*/ 　　int K; /*調(diào)入隊列計數(shù)變量*/ 　　int phb[bsize]={0}; //物理塊標號　　int pro[psize]={0}; //進程序列號</p&g

20、t;　　int flag[bsize] = {0}; //進程等待次數(shù)(存放最久未被使用的進程標志)　　int i = 0, j = 0,k = 0; //i表示進程序列號,j表示物理塊號　　int m = -1, n = -1; //物理塊空閑和進程是否相同判斷標志　　i

21、nt max = -1,maxflag = 0; //標記替換物理塊進程下標　　int count = 0; //統(tǒng)計頁面缺頁次數(shù)　　//**************************************************************//　　//*********

22、*****************************************************//隨機產(chǎn)生序列號函數(shù)　　//**************************************************************　　int* build()　　{&

23、lt;/b>　　printf("隨機產(chǎn)生一個進程序列號為：\n");　　int i = 0;　　for(i=0; i<psize; i++)　　{　　pro[i

24、] = 10*rand()/(RAND_MAX+1)+1;　　printf("%d ",pro[i]);　　}　　printf("\n");　　return(pro);

25、　　}　　//**************************************************************//查找空閑物理塊　　//**************************************************************</p

26、>　　int searchpb()　　{　　for(j=0; j<bsize; j++)　　{　　if(phb[j] == 0)<p

27、>　　{　　m = j; 　　return m; 　　break;　　}<

28、p>　　}　　return -1;　　}　　//**************************************************************//查找相同進程

29、　//**************************************************************　　int searchpro()　　{　　for(j = 0; j < bsize; j++)&

30、lt;b>　　{　　if(phb[j] == pro[i])　　{　　n = j;　　return j;&l

31、t;p>　　}　　}　　return -1;　　}　　//***********************************************

32、***************//初始化內(nèi)存　　//**************************************************************　　void empty()　　{　　for(i=0;i&

33、lt;bsize;i++)　　phb[i]=0;　　count=0; //計數(shù)器置零　　}　　//**********************************

34、****************************//先進先出頁面置換算法　　//**************************************************************　　void FIFO()　　{ &

35、lt;p>　　for(i = 0; i<psize; i++)　　{ 　　m=searchpb();　　n=searchpro();　　//找flag值最大的　　for

36、(j = 0; j < bsize;j++)　　{　　if(flag[j]>maxflag)　　{　　maxflag = flag[j];&l

37、t;b>　　max = j;　　}　　} 　　if(n == -1) //不存在相同進程　　{<

38、;/p>　　if(m != -1) //存在空閑物理塊　　{　　phb[m] = pro[i]; //進程號填入該空閑物理塊　　count++;

39、;　　flag[m] = 0;　　for(j = 0;j <= m; j++)　　{　　flag[j]++;　　}　　m = -1

40、;　　}　　else //不存在空閑物理塊　　{　　phb[max] = pro[i];　　flag[m

41、ax] = 0;　　for(j = 0;j < bsize; j++)　　{　　flag[j]++;　　}　　max = -1;&

42、lt;/b>　　maxflag = 0;　　count++;　　}　　}　　else

43、 //存在相同的進程　　{　　phb[n] = pro[i];　　for(j = 0;j < bsize; j++)　　{　　flag[

44、j]++;　　}　　n = -1;　　}　　for(j = 0 ;j < bsize; j++)<b&g

45、t;　　{　　printf("%d ",phb[j]);　　}　　printf("\n");　　}<p&

46、gt;　　printf("缺頁次數(shù)為：%d\n",count);　　printf("\n");　　}　　//**************************************************************&l

47、t;/p>　　//**************************************************************　　/*初始化內(nèi)存單元、緩沖區(qū)*/ 　　void Init(Page *b,int c[bsize][psize]) 　　{

48、　　int i,j; 　　for(i=0;i<psize;i++) 　　{ 　　b[i].num=-1; 　　b[i].time

49、=psize-i-1; 　　} 　　for(i=0;i<bsize;i++) 　　for(j=0;j<psize;j++) 　　c[i][j]=-1; 　　} &

50、lt;/b>　　/*取得在內(nèi)存中停留最久的頁面,默認狀態(tài)下為最早調(diào)入的頁面*/ 　　int GetMax(Page *b) 　　{ 　　int i;

51、;　　int max=-1;　　int tag=0;　　for(i=0;i<bsize;i++) 　　{ 　　if(b[i].time>max) 　　{ <

52、/b>　　max=b[i].time; 　　tag=i; 　　} 　　} 　　return tag; <

53、/p>　　}　　/*判斷頁面是否已在內(nèi)存中*/ 　　int Equation(int fold,Page *b) 　　{ 　　int i; <

54、;/b>　　for(i=0;i<bsize;i++) 　　{ 　　if (fold==b[i].num) 　　return i; 　　} &l

55、t;/p>　　return -1; 　　} 　　/*LRU核心部分*/ 　　void Lruu(int fold,Page *b) 　　{ &l

56、t;p>　　int i; 　　int val; 　　val=Equation(fold,b); 　　if (val>=0) 　　{ </p&

57、gt;　　b[val].time=0; 　　for(i=0;i<bsize;i++) 　　if (i!=val) 　　b[i].time++; 　　} <b&

58、gt;　　else 　　{ 　　queue[++K]=fold;/*記錄調(diào)入頁面*/ 　　val=GetMax(b); 　　b[val].num=fold; 　　b[val

59、].time=0; 　　for(i=0;i<bsize;i++) 　　if (i!=val) 　　b[i].time++; 　　} 　　}</

60、p>　　void LRU()　　{ 　　int i,j; 　　K=-1; 　　Init(b, c); &l

61、t;p>　　for(i=0;i<psize;i++) 　　{ 　　Lruu(pro[i],b); 　　c[0][i]=pro[i]; 　　/*記錄當前的內(nèi)存單元中的頁面*/ 　　f

62、or(j=0;j<bsize;j++) 　　c[j][i]=b[j].num; 　　} 　　/*結(jié)果輸出*/ 　　printf("內(nèi)存狀態(tài)為：\n"); </p&g

63、t;　　Myprintf; 　　for(j=0;j<psize;j++) 　　printf("|%2d ",pro[j]); 　　printf("|\n"); 　　Myprintf;

64、　　for(i=0;i<bsize;i++) 　　{ for(j=0;j<psize;j++) 　　{ 　　if(c[i][j]==-1) 　　printf("|%2c "

65、,32); 　　else 　　printf("|%2d ",c[i][j]); 　　} 　　printf("|\n"); <p

66、>　　} 　　Myprintf; 　　printf("\n調(diào)入隊列為:"); 　　for(i=0;i<K+1;i++) 　　printf("%3d",queue[i]); </

67、p>　　printf("\n缺頁次數(shù)為：%6d\n缺頁率：%16.6f",K+1,(float)(K+1)/psize); 　　}　　//**************************************************************//主函

68、數(shù)　　//**************************************************************　　void main()　　{　　int sel ;&

69、lt;b>　　do{　　printf("\t\t\t--------------------------------------\t\t\t");　　printf("\t\t\t ☆☆^-^歡迎進入操作系統(tǒng)界面^-^☆☆ \t\t\t");

70、printf("\t\t\t--------------------------------------\t\t\t\n");　　printf("\t\t\t☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆\t\t\t");　　printf("\t\t\t☆ 虛擬內(nèi)存 ☆

71、 \t\t\t");　　printf("\t\t\t☆--------------------------------☆\t\t\t");　　printf("\t\t\t☆ 1、產(chǎn)生隨機序列 ☆ \t\t\t");　　printf(

72、"\t\t\t☆--------------------------------☆\t\t\t");　　printf("\t\t\t☆ 2、最久未使用(LRU) ☆ \t\t\t");　　printf("\t\t\t☆-------------------------------

73、-☆\t\t\t");　　printf("\t\t\t☆ 3、先進先出(FIFO) ☆ \t\t\t");　　printf("\t\t\t☆--------------------------------☆\t\t\t");　　prin

74、tf("\t\t\t☆ 4、最佳置換算法(OPT) ☆ \t\t\t");　　printf("\t\t\t☆--------------------------------☆\t\t\t");　　printf("\t\t\t☆ 5、三種算法的比較() ☆ \t

75、\t\t");　　printf("\t\t\t☆--------------------------------☆\t\t\t");　　printf("\t\t\t☆ 0、退出(Exit) ☆ \t\t\t");　　printf

76、("\t\t\t☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆\t\t\t\n");　　printf("請選擇所要執(zhí)行的操作(0/1/2/3/4/5):");　　scanf("%d",&sel);　　switch(sel)<p

77、>　　{　　case0:printf("\t\t\t^-^再見！^-^ \t\t\t\n");system("pause");break;　　case 1:build();break;　　case 2:printf("最

78、久未使用算\n");LRU();empty();printf("\n");break;　　case 3:printf("先進先出算\n");FIFO();empty();printf("\n");break;　　case 5:printf("先進先出算法\n");F

79、IFO();empty();　　printf("最久未使用算法\n");LRU();empty();break;　　default: printf("請輸入正確的選項號！");printf("\n\n");break;　　}</b

80、>　　}while(sel!=0);　　}　　產(chǎn)生的隨機序列：　　最近最少使用算法執(zhí)行結(jié)果如下：　　先進先出FIFO算法執(zhí)行結(jié)果：

81、;　　2．總結(jié)體會請求頁式存儲管理的實現(xiàn)原理。　　請求頁式管理的基本原理是將邏輯地址空間分成大小相同的頁，將存儲地址空間分塊，頁和塊的大小相等，通過頁表進行管理。頁式系統(tǒng)的邏輯地址分為頁號和頁內(nèi)位移量。頁表包括頁號和塊號數(shù)據(jù)項，它們一一對應(yīng)。根據(jù)邏輯空間的頁號，查找頁表對應(yīng)項找到對應(yīng)的塊號，塊號乘以塊長，加上位移量就行成存儲空間的物理地址。每個作業(yè)的邏輯地址空間是連續(xù)的，重

82、定位到內(nèi)存空間后就不一定連續(xù)了。　　3. 寫出這三種頁面置換算法的實現(xiàn)思想。　　FIFO算法總是淘汰最先調(diào)入主存的頁面，即淘汰在主存中駐留時間最長的頁面，認為駐留時間最長的頁不再使用的可能性較大。　　LRU算法淘汰的頁面是最近一段時間內(nèi)最久未被訪問的那一頁，它是基于程序局部性原理來考慮的，認為那些剛被使用過的頁面

83、可能還要立即被使用，而那些在較長時間內(nèi)未被使用的頁面可能不會立即使用。　　OPT算法，當要調(diào)入一頁而必須淘汰舊頁時，應(yīng)該淘汰以后不再訪問的頁，或距現(xiàn)在最長時間后要訪問的頁面。　　4．對不同算法的性能進行評價。　　FIFO算法較易實現(xiàn)，對具有線性順序特征的程序比較適用，而對具有其他特征的程序則效率不高，此算法還可能

84、出現(xiàn)抖動現(xiàn)象（Belady）異常。LRU算法基于程序的局部性原理，所以適用用大多數(shù)程序，此算實現(xiàn)必須維護一個特殊的隊列——頁面淘汰隊列。OPT算法雖然產(chǎn)生的缺頁數(shù)最少，然而，卻需要預測程序的頁面引用串，這是無法預知的，不可能對程序的運行過程做出精確的斷言，不過此理論算法可用做衡量各種具體算法的標準。　　五.總結(jié)　　經(jīng)

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

溫馨提示

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

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

文檔簡介

溫馨提示

最新文檔

評論

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

文檔簡介

溫馨提示

最新文檔

評論

免費下載