操作系統(tǒng)課程設(shè)計(jì)-頁(yè)面置換算法c語(yǔ)言

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

操作系統(tǒng)課程設(shè)計(jì)-頁(yè)面置換算法c語(yǔ)言_第1頁(yè)

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

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

文檔簡(jiǎn)介

1、　　頁(yè)面置換算法的演示　　一．題目要求：　　設(shè)計(jì)一個(gè)虛擬存儲(chǔ)區(qū)和內(nèi)存工作區(qū)，編程序演示下述算法的具體實(shí)現(xiàn)過(guò)程，并計(jì)算訪(fǎng)問(wèn)命中率：　　要求設(shè)計(jì)主界面以靈活選擇某算法，且以下算法都要實(shí)現(xiàn)<p&g

2、t;　　1) 最佳置換算法(OPT)：將以后永不使用的或許是在最長(zhǎng)(未來(lái))時(shí)間內(nèi)不再被訪(fǎng)問(wèn)的頁(yè)面換出。　　2) 先進(jìn)先出算法(FIFO)：淘汰最先進(jìn)入內(nèi)存的頁(yè)面，即選擇在內(nèi)存中駐留時(shí)間最久的頁(yè)面予以淘汰。　　3) 最近最久未使用算法(LRU)：淘汰最近最久未被使用的頁(yè)面。　　4) 最不經(jīng)常使用算法(LFU)<

3、;/p>　　二．實(shí)驗(yàn)?zāi)康模?lt;/b>　　1、用C語(yǔ)言編寫(xiě)OPT、FIFO、LRU，LFU四種置換算法。　　2、熟悉內(nèi)存分頁(yè)管理策略。　　3、了解頁(yè)面置換的算法。　　4、掌握一般常用的調(diào)度算法。

4、　　5、根據(jù)方案使算法得以模擬實(shí)現(xiàn)。　　6、鍛煉知識(shí)的運(yùn)用能力和實(shí)踐能力。　　三．相關(guān)知識(shí)：　　1．虛擬存儲(chǔ)器的引入：　　局部性原理：程序在執(zhí)行時(shí)在一較短時(shí)間內(nèi)僅限于某個(gè)部分；相應(yīng)的，它所訪(fǎng)問(wèn)的存儲(chǔ)空間也局限于某個(gè)區(qū)

5、域，它主要表現(xiàn)在以下兩個(gè)方面：時(shí)間局限性和空間局限性。　　2．虛擬存儲(chǔ)器的定義：　　虛擬存儲(chǔ)器是只具有請(qǐng)求調(diào)入功能和置換功能，能從邏輯上對(duì)內(nèi)存容量進(jìn)行擴(kuò)充的一種存儲(chǔ)器系統(tǒng)。　　3．虛擬存儲(chǔ)器的實(shí)現(xiàn)方式：　　分頁(yè)請(qǐng)求系統(tǒng)，它是在分頁(yè)系統(tǒng)的基礎(chǔ)上，增加了請(qǐng)求調(diào)頁(yè)功能、頁(yè)面置換

6、功能所形成的頁(yè)面形式虛擬存儲(chǔ)系統(tǒng)。　　請(qǐng)求分段系統(tǒng)，它是在分段系統(tǒng)的基礎(chǔ)上，增加了請(qǐng)求調(diào)段及分段置換功能后，所形成的段式虛擬存儲(chǔ)系統(tǒng)。　　4．頁(yè)面分配：　　平均分配算法，是將系統(tǒng)中所有可供分配的物理塊，平均分配給各個(gè)進(jìn)程。　　按比例分

7、配算法，根據(jù)進(jìn)程的大小按比例分配物理塊。　　考慮優(yōu)先的分配算法，把內(nèi)存中可供分配的所有物理塊分成兩部分：一部分按比例地分配給各進(jìn)程；另一部分則根據(jù)個(gè)進(jìn)程的優(yōu)先權(quán)，適當(dāng)?shù)脑黾悠湎鄳?yīng)份額后，分配給各進(jìn)程。　　5．頁(yè)面置換算法：　　常用的頁(yè)面置換算法有OPT、FIFO、LRU、Cl

8、ock、LFU、PBA等。　　四．設(shè)計(jì)思想：　　選擇置換算法，先輸入所有頁(yè)面號(hào)，為系統(tǒng)分配物理塊，依次進(jìn)行置換：　　OPT基本思想：　　是用一維數(shù)組page[pSIZE]存儲(chǔ)頁(yè)面號(hào)序列，memer

9、y[mSIZE]是存儲(chǔ)裝入物理塊中的頁(yè)面。數(shù)組next[mSIZE]記錄物理塊中對(duì)應(yīng)頁(yè)面的最后訪(fǎng)問(wèn)時(shí)間。每當(dāng)發(fā)生缺頁(yè)時(shí)，就從物理塊中找出最后訪(fǎng)問(wèn)時(shí)間最大的頁(yè)面，調(diào)出該頁(yè)，換入所缺的頁(yè)面。　　【特別聲明】　　若物理塊中的頁(yè)面都不再使用，則每次都置換物理塊中第一個(gè)位置的頁(yè)面。&l

10、t;b>　　FIFO基本思想：　　是用隊(duì)列存儲(chǔ)內(nèi)存中的頁(yè)面，隊(duì)列的特點(diǎn)是先進(jìn)先出，與該算法是一致的，所以每當(dāng)發(fā)生缺頁(yè)時(shí)，就從隊(duì)頭刪除一頁(yè)，而從隊(duì)尾加入缺頁(yè)?；蛘呓柚o助數(shù)組time[mSIZE]記錄物理塊中對(duì)應(yīng)頁(yè)面的進(jìn)入時(shí)間，每次需要置換時(shí)換出進(jìn)入時(shí)間最小的頁(yè)面。　　LRU基本思想：<

11、/p>　　是用一維數(shù)組page[pSIZE]存儲(chǔ)頁(yè)面號(hào)序列，memery[mSIZE]是存儲(chǔ)裝入物理塊中的頁(yè)面。數(shù)組flag[10]標(biāo)記頁(yè)面的訪(fǎng)問(wèn)時(shí)間。每當(dāng)使用頁(yè)面時(shí)，刷新訪(fǎng)問(wèn)時(shí)間。發(fā)生缺頁(yè)時(shí)，就從物理塊中頁(yè)面標(biāo)記最小的一頁(yè)，調(diào)出該頁(yè)，換入所缺的頁(yè)面。　　五．流程圖：

12、如下頁(yè)所示　　六．源代碼：　　如下頁(yè)所示【使用C語(yǔ)言】　　#include <stdio.h>　　#include <stdlib.h><b&

13、gt;　　/*全局變量*/　　int mSIZE; /*物理塊數(shù)*/　　int pSIZE; /*頁(yè)面號(hào)引用串個(gè)數(shù)*/　　static int memery[10]={0}; /*物理塊中的頁(yè)號(hào)*/　　static int page[100]={0};

14、 /*頁(yè)面號(hào)引用串*/　　static int temp[100][10]={0}; /*輔助數(shù)組*/　　/*置換算法函數(shù)*/　　void FIFO();　　void LRU();　　void OPT();

15、　　/*輔助函數(shù)*/　　void print(unsigned int t);　　void designBy();　　void download();　　void mDelay(unsigned int Delay)

16、;　　/*主函數(shù)*/　　void main()　　{　　int i,k,code;　　system("color 0A");</

17、p>　　designBy();　　printf("┃請(qǐng)按任意鍵進(jìn)行初始化操作... ┃\n");　　printf("┗━━━━━━━━━━━━━━━━━━━━━━━━━┛\n");　　printf(&q

18、uot; >>>");　　getch();　　system("cls");　　system("color 0B");　　printf("請(qǐng)輸入物理塊的個(gè)數(shù)(

19、M<=10)：");　　scanf("%d",&mSIZE);　　printf("請(qǐng)輸入頁(yè)面號(hào)引用串的個(gè)數(shù)(P<=100)：");　　scanf("%d",&pSIZE);

20、　puts("請(qǐng)依次輸入頁(yè)面號(hào)引用串(連續(xù)輸入，無(wú)需隔開(kāi))：");　　for(i=0;i<pSIZE;i++)　　scanf("%1d",&page[i]);　　download();　　system("cl

21、s");　　system("color 0E");　　do{ 　　puts("輸入的頁(yè)面號(hào)引用串為：");　　for(k=0;k<=(pSIZE-1)/20;k++)</p

22、>　　{　　for(i=20*k;(i<pSIZE)&&(i<20*(k+1));i++)　　{　　if(((i+1)%20==0)||(((i+1)%20)&&(i

23、==pSIZE-1)))　　printf("%d\n",page[i]);　　else　　printf("%d ",page[i]);　　}</p

24、>　　}　　printf("* * * * * * * * * * * * * * * * * * * * * * *\n");　　printf("* 請(qǐng)選擇頁(yè)面置換算法：\t\t\t *\n");

25、printf("* ----------------------------------------- *\n");　　printf("* 1.先進(jìn)先出(FIFO) 2.最近最久未使用(LRU) *\n");　　printf("* 3.最佳(OPT) 4.退出

26、 *\n");　　printf("* * * * * * * * * * * * * * * * * * * * * * *\n");　　printf("請(qǐng)選擇操作：[ ]\b\b");　　scanf("%d",&code);&l

27、t;/p>　　switch(code)　　{　　case 1:　　FIFO();　　break;</b&g

28、t;　　case 2:　　LRU();　　break;　　case 3:<

29、;b>　　OPT();　　break;　　case 4:　　system("cls");　　system("color 0A");

30、　　designBy(); /*顯示設(shè)計(jì)者信息后退出*/　　printf("┃謝謝使用頁(yè)面置換算法演示器! 正版授權(quán) ㊣┃\n");　　printf("┗━━━━━━━━━━━━━━━━━━━━━━━━━┛\n");<p&

31、gt;　　exit(0);　　default:　　printf("輸入錯(cuò)誤，請(qǐng)重新輸入：");　　}　　printf("按任意鍵

32、重新選擇置換算法：>>>");　　getch();　　system("cls");　　}while (code!=4);　　getch();<

33、/p>　　}　　/*載入數(shù)據(jù)*/　　void download()　　{　　int i;&l

34、t;/p>　　system("color 0D");　　printf("╔════════════╗\n");　　printf("║正在載入數(shù)據(jù)，請(qǐng)稍候 !!!║\n");　　printf("╚═══════════

35、═╝\n");　　printf("Loading...\n");　　printf(" O");　　for(i=0;i<51;i++)&l

36、t;p>　　printf("\b");　　for(i=0;i<50;i++)　　{　　mDelay((pSIZE+mSIZE)/2);　　printf(">");</p&

37、gt;　　}　　printf("\nFinish.\n載入成功，按任意鍵進(jìn)入置換算法選擇界面：>>>");　　getch();　　}<

38、/p>　　/*設(shè)置延遲*/　　void mDelay(unsigned int Delay)　　{ 　　unsigned int i; 　　for(;Delay>

39、0;Delay--) 　　{ 　　for(i=0;i<124;i++) 　　{　　printf(" \b");<b&g

40、t;　　} 　　} 　　}　　/*顯示設(shè)計(jì)者信息*/ 　　void designBy()　　{&

41、lt;/p>　　printf("┏━━━━━━━━━━━━━━━━━━━━━━━━━┓\n");　　printf("┃㊣課題三：頁(yè)面置換算法㊣┃\n");　　printf("┃ 學(xué)號(hào)：081001

42、117 ┃\n");　　printf("┃ 姓名：邢磊 <Visual C++ 6.0>┃\n");　　printf("┣━━━━━━━━━━━━━━━━━━━━━━━━━┫\n");<

43、;p>　　}　　void print(unsigned int t)　　{　　int i,j,k,l;　　int flag;&l

44、t;p>　　for(k=0;k<=(pSIZE-1)/20;k++)　　{　　for(i=20*k;(i<pSIZE)&&(i<20*(k+1));i++)　　{<p&

45、gt;　　if(((i+1)%20==0)||(((i+1)%20)&&(i==pSIZE-1)))　　printf("%d\n",page[i]);　　else　　printf("%d ",page[i]);<

46、;/p>　　}　　for(j=0;j<mSIZE;j++)　　{　　for(i=20*k;(i<mSIZE+20*k)&&(i<pSIZE);i++)&

47、lt;p>　　{　　if(i>=j)　　printf(" |%d|",temp[i][j]);　　else　　printf(&

48、quot; | |");　　}　　for(i=mSIZE+20*k;(i<pSIZE)&&(i<20*(k+1));i++)　　{　　for(flag=0,l

49、=0;l<mSIZE;l++)　　if(temp[i][l]==temp[i-1][l])　　flag++;　　if(flag==mSIZE)/*頁(yè)面在物理塊中*/　　printf(" ");</

50、p>　　else　　printf(" |%d|",temp[i][j]);　　}　　/*每行顯示20個(gè)*/　　if(i%20==0)</p&g

51、t;　　continue;　　printf("\n");　　}　　}　　printf("---------

52、-------------------------------\n");　　printf("缺頁(yè)次數(shù)：%d\t\t",t+mSIZE);　　printf("缺頁(yè)率：%d/%d\n",t+mSIZE,pSIZE);　　printf("置換次數(shù)：%d\t\t

53、",t);　　printf("訪(fǎng)問(wèn)命中率：%d%%\n",(pSIZE-(t+mSIZE))*100/pSIZE);　　printf("----------------------------------------\n");　　}</b

54、>　　/*計(jì)算過(guò)程延遲*/　　void compute()　　{　　int i;　　printf("正在進(jìn)行相關(guān)計(jì)算，請(qǐng)稍候")

55、;　　for(i=1;i<20;i++)　　{　　mDelay(15);　　if(i%4==0)　　printf("\b\b\b\b\b\b \b\b\b\b\b\b

56、");　　else　　printf("Θ");　　}　　for(i=0;i++<30;printf("\b"));&

57、lt;p>　　for(i=0;i++<30;printf(" "));　　for(i=0;i++<30;printf("\b"));　　}　　/*先進(jìn)先出頁(yè)面置換算法*/　　v

58、oid FIFO()　　{　　int memery[10]={0};　　int time[10]={0}; /*記錄進(jìn)入物理塊的時(shí)間*/　　int i,j,k,m;　　int max=0; /

59、*記錄換出頁(yè)*/　　int count=0; /*記錄置換次數(shù)*/　　/*前mSIZE個(gè)數(shù)直接放入*/　　for(i=0;i<mSIZE;i++)　　{　　memery[i]=page[

60、i];　　time[i]=i;　　for(j=0;j<mSIZE;j++)　　temp[i][j]=memery[j];　　}　　for(i=mSIZE;i<pSIZE;i++)&

61、lt;/p>　　{　　/*判斷新頁(yè)面號(hào)是否在物理塊中*/　　for(j=0,k=0;j<mSIZE;j++)　　{　　if(memery[j]!=page[i])

62、　　k++;　　}　　if(k==mSIZE) /*如果不在物理塊中*/　　{　　count++;

63、　　/*計(jì)算換出頁(yè)*/　　max=time[0]<time[1]?0:1;　　for(m=2;m<mSIZE;m++)　　if(time[m]<time[max])<

64、p>　　max=m;　　memery[max]=page[i];　　time[max]=i; /*記錄該頁(yè)進(jìn)入物理塊的時(shí)間*/　　for(j=0;j<mSIZE;j++)　　temp[i][j]=memery[j];<

65、;/p>　　}　　else　　{　　for(j=0;j<mSIZE;j++)　　temp[i][j]=memery[j];&

66、lt;/p>　　} 　　}　　compute();　　print(count);　　}

67、　/*最近最久未使用置換算法*/　　void LRU()　　{　　int memery[10]={0};　　int flag[10]={0}; /*記錄頁(yè)面的訪(fǎng)問(wèn)時(shí)間*/　　int i,j,k

68、,m;　　int max=0; /*記錄換出頁(yè)*/　　int count=0; /*記錄置換次數(shù)*/　　/*前mSIZE個(gè)數(shù)直接放入*/　　for(i=0;i<mSIZE;i++)　　{

69、　　memery[i]=page[i];　　flag[i]=i;　　for(j=0;j<mSIZE;j++)　　temp[i][j]=memery[j];　　}&

70、lt;p>　　for(i=mSIZE;i<pSIZE;i++)　　{　　/*判斷新頁(yè)面號(hào)是否在物理塊中*/　　for(j=0,k=0;j<mSIZE;j++)　　{</p&

71、gt;　　if(memery[j]!=page[i])　　k++;　　else 　　flag[j]=i; /*刷新該頁(yè)的訪(fǎng)問(wèn)時(shí)間*/　　}

72、;　　if(k==mSIZE) /*如果不在物理塊中*/　　{　　count++;　　/*計(jì)算換出頁(yè)*/　　max=

73、flag[0]<flag[1]?0:1;　　for(m=2;m<mSIZE;m++)　　if(flag[m]<flag[max])　　max=m;　　memery[max]=page[i];&

74、lt;p>　　flag[max]=i; /*記錄該頁(yè)的訪(fǎng)問(wèn)時(shí)間*/　　for(j=0;j<mSIZE;j++)　　temp[i][j]=memery[j];　　}　　else</

75、p>　　{　　for(j=0;j<mSIZE;j++)　　temp[i][j]=memery[j];　　}　　}</p

76、>　　compute();　　print(count);　　}　　/*最佳置換算法*/　　void OPT()　　{</

77、p>　　int memery[10]={0};　　int next[10]={0}; /*記錄下一次訪(fǎng)問(wèn)時(shí)間*/　　int i,j,k,l,m;　　int max; /*記錄換出頁(yè)*/　　int count=0; /*記錄置換次數(shù)*/</

78、p>　　/*前mSIZE個(gè)數(shù)直接放入*/　　for(i=0;i<mSIZE;i++)　　{　　memery[i]=page[i];　　for(j=0;j<mSIZE;j++)

79、　　temp[i][j]=memery[j];　　}　　for(i=mSIZE;i<pSIZE;i++)　　{　　/*判斷新頁(yè)面號(hào)是否在物理塊中*/

80、　　for(j=0,k=0;j<mSIZE;j++)　　{　　if(memery[j]!=page[i])　　k++;　　}<

81、;/p>　　if(k==mSIZE) /*如果不在物理塊中*/　　{　　count++;　　/*得到物理快中各頁(yè)下一次訪(fǎng)問(wèn)時(shí)間*/　　for(m=0;m<mSIZ

82、E;m++)　　{　　for(l=i+1;l<pSIZE;l++)　　if(memery[m]==page[l])　　break;　　next[m]

83、=l;　　}　　/*計(jì)算換出頁(yè)*/　　max=next[0]>=next[1]?0:1;　　for(m=2;m<mSIZE;m++)　　if(

84、next[m]>next[max])　　max=m;　　/*下一次訪(fǎng)問(wèn)時(shí)間都為pSIZE,則置換物理塊中第一個(gè)*/　　memery[max]=page[i];　　for(j=0;j<mSIZE;j++)

85、　　temp[i][j]=memery[j];　　}　　else {　　for(j=0;j<mSIZE;j++)　　temp[i][j]=memery[j];</

86、p>　　}　　}　　compute();　　print(count);　　}<b&

87、gt;　　七．運(yùn)行結(jié)果：　　【運(yùn)行環(huán)境——Visual C++ 6.0】　　1. 按任意鍵進(jìn)行初始化：　　2. 載入數(shù)據(jù)：　　3. 進(jìn)入置換算法選擇界面：　　4.運(yùn)算中延遲

88、操作：　　5.三種算法演示結(jié)果：　　6.退出界面：　　八．參考文獻(xiàn)：　　1. 嚴(yán)蔚敏, 吳偉民. 數(shù)據(jù)結(jié)構(gòu). 清華大學(xué)出版社, 2005.11　　2. 譚

眾賞文庫(kù)> 全部分類(lèi)> 畢業(yè)設(shè)計(jì)

溫馨提示

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

操作系統(tǒng)課程設(shè)計(jì)-頁(yè)面置換算法c語(yǔ)言

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

操作系統(tǒng)課程設(shè)計(jì)-頁(yè)面置換算法c語(yǔ)言

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

免費(fèi)下載