操作系統(tǒng)課程設計報告--頁面置換算法模擬程序設計

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

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

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

文檔簡介

1、　　操作系統(tǒng)課程設計報告　　題目：頁面置換算法模擬程序設計 　　專業(yè)：軟件工程 　　院系：信息管理學院 　　年級：大三軟件Q1141

2、 　　學號： 　　姓名： 　　指導教師： 　　職稱：副教授

3、 　　目錄　　第一部分概述　　第二部分設計的基本概念和原理　　第三部分總體設計&l

4、t;b>　　3.1算法流程圖　　3.2算法的簡要實現(xiàn)方法　　3.2.1 OPT頁面置換算法　　3.2.2 FIFO頁面置換算法　　3.2.3 LRU頁面置換算法　　3.2.4 LFU頁面置換算法</

5、p>　　第四部分詳細設計　　4.1 main函數(shù)　　4.2 OPT函數(shù)　　4.2 FIFO函數(shù)　　4.3 LRU函數(shù)

6、　4.5 LFU函數(shù)　　4.6輔助函數(shù)　　4.6.1 Designer函數(shù)　　4.6.2 mDelay函數(shù)　　4.6.3 Download函數(shù)　　4.6.4 Compute函數(shù)</p&

7、gt;　　4.6.5 showTable函數(shù)　　第五部分實現(xiàn)源代碼　　第六部分簡要的使用說明及主要運行界面　　第七部分總結(jié)　　第八部分參考文獻

8、　　第一部分概述　　設計任務：　　頁面置換算法是虛擬存儲管理實現(xiàn)的關(guān)鍵，通過本次課程設計理解內(nèi)存頁面調(diào)度的機制，在模擬實現(xiàn)OPT、FIFO、LRU和LFU幾種經(jīng)典頁面置換算法的基礎(chǔ)上，比較各種置換算法的效率及優(yōu)缺點，從而了解虛擬存儲實現(xiàn)的過程。</p&g

9、t;　　第二部分設計的基本概念和原理　　(1)．頁面淘汰機制　　頁面淘汰又稱為頁面置換。若請求調(diào)頁程序要調(diào)進一個頁面，而此時該作業(yè)所分得的主存塊已全部用完，則必須淘汰該作業(yè)已在主存中的一個頁。這時，就產(chǎn)生了在諸頁面中淘汰哪個頁面的問題，這就是淘汰算法（或稱為置換算法）。　　置換算法可描述為

10、，當要索取一個頁面并送入主存時，必須將該作業(yè)已在主存中的某一頁面淘汰掉，用來選擇淘汰哪一頁的規(guī)則就叫做置換算法。　　(2)．各種頁面置換算法的實現(xiàn)思想　　OPT算法是當要調(diào)入一新頁而必須先淘汰一舊業(yè)時，所淘汰的那一頁應是以后不要再用的或是以后很長時間才會用到的頁。　　FIFO算法的實質(zhì)是，總是選擇在主存中居留時間

11、最長（即最老）的一頁淘汰。其理由是最先調(diào)入主存的頁面，其不再被使用的可能性比最近調(diào)入主存的頁的可能性大。　　LRU算法的實質(zhì)是，當需要置換一頁時，選擇最長時間未被使用的那一頁淘汰。如果某一頁被訪問了，它很可能馬上還要被訪問；相反，如果它很長時間未曾用過，看起來在最近的未來是不大需要的。　　LFU即最不經(jīng)常使用頁置換算法，要求在頁置換時置換在一定時期內(nèi)引用

12、計數(shù)最小的頁，因為經(jīng)常使用的頁應該有一個較大的引用次數(shù)。本次設計取整個頁面訪問時期為計算周期，實際問題中應根據(jù)頁面數(shù)量多少來確定周期。　　第三部分總體設計　　3.1算法流程圖　　3.2算法的簡要實現(xiàn)方法<p

13、>　　選擇置換算法，先輸入所有頁面號，為系統(tǒng)分配物理塊，依次進行置換：　　最佳置換算法（OPT）：　　是用一維數(shù)組page[PSIZE]存儲頁面號序列，memery[MSIZE]是存儲裝入物理塊中的頁面，用pflag[PSIZE]數(shù)組標記缺頁中斷處。數(shù)組next[MSIZE]記錄物理塊中對應頁面的最后訪問時間。每當發(fā)生缺頁時，就從物理塊中找出最后訪

14、問時間最大的頁面，調(diào)出該頁，換入所缺的頁面，然后初始化next[MSIZE]，便于下次使用。　　【特別聲明】　　若物理塊中的頁面都不再使用，則每次都置換物理塊中第一個位置的頁面。　　先進先出置換算法（FIFO）：　　是用一維數(shù)組pag

15、e[PSIZE]存儲頁面號序列，memery[MSIZE]是存儲裝入物理塊中的頁面，用pflag[PSIZE]數(shù)組標記缺頁中斷處。采用隊列的思想，總是把最先進入物理塊中的頁面放在第一個位置，當發(fā)生缺頁時，就從隊頭刪除一頁，而從隊尾加入缺頁。　　最久未使用置換算法（LRU）：　　是用一維數(shù)組page[PSIZE]存儲頁面號序列，memery[mSIZE]是

16、存儲裝入物理塊中的頁面，用pflag[PSIZE]數(shù)組標記缺頁中斷處?？偸前炎铋L時間內(nèi)未被使用的頁放在最后一塊，當發(fā)生缺頁時，就刪掉最后一頁，將當前所缺頁面放入第一塊。　　最不經(jīng)常使用淘汰算法（LFU）：　　是用一維數(shù)組page[PSIZE]存儲頁面號序列，memery[mSIZE]是存儲裝入物理塊中的頁面，用pflag[PSIZE]數(shù)組標記缺頁中斷處。

17、用use[MSIZE]數(shù)組記錄當前各頁已使用次數(shù)，其中use[0]中存放使用次數(shù)最少的頁的次數(shù)，當發(fā)生缺頁時，就在已放入物理塊的頁中查找當前使用次數(shù)最少的頁，將之刪掉，并引入當前缺頁頁面。　　第四部分詳細設計　　main函數(shù)：　　voi

18、d main()　　{　　int i, k, code;　　int mSize, pSize, page[PSIZE];　　system("color 0A");　　Des

19、igner();　　printf("┃請按任意鍵繼續(xù)... ┃\n");　　printf("┖─────────────────────────┚\n");　　printf(" >>>

20、; ");　　getchar();　　system("cls"); //DOS命令，清除屏幕上的所有文字　　system("color 0B"); //改變控制臺的前景和背景色　　printf("請

21、輸入物理塊的個數(shù)[mSize <= 10]：");　　scanf("%d", &mSize);　　printf("請輸入頁面數(shù)[pSize <= 50]：");　　scanf("%d", &pSize);</p

22、>　　printf("請輸入頁面序列[1~10之間]：\n");　　for (i = 0; i < pSize; i ++)　　scanf("%d", &page[i]);　　Download(pSize, mSize);</

23、p>　　system("cls");　　system("color 0E");　　do　　{　　printf("即將進

24、入物理塊的頁面序列為:\n");　　for (i = 0; i < pSize; i ++)　　printf("%3d", page[i]);　　printf("\n");　　printf("* * * *

25、 * * * * * * * * * * * * * * * * * * * * * * * * *\n");　　printf("* 請選擇頁面置換算法： *\n");　　printf("* ━━━━━━━━━━━━━━━━━━━━━━━━━━━*\

26、n");　　printf("* 1.最佳(OPT) 2.先進先出(FIFO) 3.最近最久未使用(LRU)*\n");　　printf("* 4.最不經(jīng)常使用(LFU,當前使用次數(shù)最少) 5.退出 *\n");　　printf(&quo

27、t;* * * * * * * * * * * * * * * * * * * * * * * * * * * * *\n");　　printf("請選擇操作：[ ]\b\b");　　scanf("%d",&code);　　switch (code)<

28、;/p>　　{　　case 1:　　OPT(page, pSize, mSize);　　break;　　case

29、 2:　　FIFO(page, pSize, mSize);　　break;　　case 3:　　LRU(page, pSize, mSize);<

30、;p>　　break;　　case 4:　　LFU(page, pSize, mSize);　　break;　　case 5:<

31、/b>　　system("cls");　　system("color 0A");　　Designer(); //顯示設計者信息后退出　　printf("┃謝謝使用頁面置換算法演示器! 正版授權(quán)

32、㊣┃\n");　　printf("┗━━━━━━━━━━━━━━━━━━━━━━━━━┛\n");　　exit(0);　　default:　　printf(&quo

33、t;輸入錯誤，請重新輸入：");　　}　　//printf("按任意鍵重新選擇置換算法：>>>");　　getchar();　　system("pause"); /

34、/凍結(jié)屏幕　　system("cls");　　} while (code != 5);　　getchar ();　　}　　OPT函數(shù)：

35、;　　void OPT(int page[], int pSize, int mSize)　　{　　int i, j, k;　　int count = 0; //計數(shù)器　　int memery

36、[MSIZE] = {0}; //存儲裝入物理塊中的頁面　　int next[MSIZE] = {0}; //記錄物理塊中對應頁面的最后訪問時間　　sum = 0;　　for (i = 0; i < pSize; i ++)<p

37、>　　{　　j = 0;　　while ((j < mSize) && (page[i] != memery[j])) //查頁表，看是否缺頁　　j ++;</p

38、>　　if (j == mSize) 　　{　　flag = '*'; //缺頁，則置標志flag為'*'　　sum += 1; //記錄缺頁次數(shù)　　i

39、f (sum <= mSize) //如果物理塊中有空余，則將當前頁面直接放入　　{　　for (j = 0; j < mSize; j ++)　　{　　if (memery[j]

40、 == 0)　　{　　memery[j] = page[i];　　break;　　}　　}<

41、/b>　　}　　else //物理塊已滿的情況下　　{　　for (j = i + 1; j < pSize; j ++) //查找以后不再使用或在最長時間以后才會用到的頁&l

42、t;/p>　　{　　for (k = 0; k < mSize; k ++)　　{　　if (page[j] == memery[k])　　{&

43、lt;/b>　　next[k] += 1; //記錄將被使用的次數(shù)，可以不用累加　　count ++; //記錄物理塊中以后將即被使用的頁面?zhèn)€數(shù)　　break;　　}&l

44、t;/p>　　}　　if (count == mSize - 1) break; //如果已有mSize-1個頁面即將被使用，則剩下最后一個頁面一定是最長時間后才會用到的頁　　}　　if (count =

45、= 0)　　memery[0] = page[i];　　else　　{　　count = 0;　　for (k = 0; k < mSize; k

46、++)　　{　　if (next[k] == 0) //總是置換出第一個可以換出的頁　　memery[k] = page[i];　　next[k] = 0; //初始化next[]數(shù)組<

47、p>　　}　　}　　}　　}　　else flag = ' ';<

48、p>　　pflag[i] = flag; //記錄當前頁的缺頁情況　　for (k = 0; k < mSize; k ++) //記錄每一次的置換情況　　table[k][i] = memery[k];　　}

49、Compute();　　showTable(page, pSize, mSize);　　}　　FIFO函數(shù)：　　void FIFO(int page[], int pSize, int mSize

50、)　　{　　int i, j;　　int memery[MSIZE] = {0}; //存儲裝入物理塊中的頁面　　sum = 0;

51、　　for(i = 0; i < pSize; i++) //查頁表，看是否缺頁　　{ 　　j = 0;　　while ((j < mSize) && (page[i] != memery[

52、j])) 　　j++;　　if (j == mSize) 　　{　　flag = '*'; //缺頁，則置標志flag為'*'<

53、p>　　sum += 1;　　for (j = mSize-1; j > 0; j --) //淘汰最先調(diào)入的頁面，并調(diào)入當前頁面　　memery[j] = memery[j-1];　　memery[0] = page[i];<p&

54、gt;　　}　　else flag = ' ';　　pflag[i] = flag;　　for (j = 0; j < mSize; j++) 　　table[j][i] = meme

55、ry[j];　　}　　Compute();　　showTable(page, pSize, mSize);　　}　　LRU函數(shù)：&l

56、t;/b>　　void LRU(int page[], int pSize, int mSize)　　{　　int i, j, k;　　int memery[MSIZE] = {0}; //存儲裝入物理塊中的頁面</p

57、>　　sum = 0;　　for (i = 0; i < pSize; i ++)　　{　　j = 0;　　while ((

58、j < mSize) && (page[i] != memery[j])) //查頁表，看是否缺頁　　j ++;　　if (j == mSize) 　　{　　flag

59、= '*'; //缺頁，則置標志flag為'*'　　sum += 1; 　　k = j - 1;　　}　　else &

60、lt;b>　　{　　flag = ' ';　　k = j;　　}　　pflag[i] = flag; //記錄當前頁的缺頁情況

61、　　while (k > 0) //總是把最長時間內(nèi)未被使用的頁放在最后一頁　　{　　memery[k] = memery[k-1];　　k --;

62、　}　　memery[0] = page[i]; //調(diào)入當前頁面　　for (k = 0; k < mSize; k ++) //記錄每一次的置換情況　　table[k][i] = memery[k];　　}</b&g

63、t;　　Compute();　　showTable(page, pSize, mSize);　　}　　LFU函數(shù)：　　void LFU(int page[

64、], int pSize, int mSize)　　{　　int i, j, replace; //replace標記使用次數(shù)最少的頁　　int use[MSIZE] = {0}; //記錄當前各頁已使用次數(shù), 其中use[0]中存放使用次數(shù)最少的頁的次數(shù)</p&g

65、t;　　int memery[MSIZE] = {0}; //存儲裝入物理塊中的頁面　　sum = 0;　　for (i = 0; i < pSize; i ++)　　{<p&

66、gt;　　use[page[i]] += 1; //下標即為頁號　　j = 0;　　while ((j < mSize) && (page[i] != memery[j])) //查頁表，看是否缺頁　　j ++;

67、;　　if (j == mSize) 　　{　　flag = '*'; //缺頁，則置標志flag為'*'　　sum += 1; 　　if (sum <

68、= mSize) //如果物理塊中有空余，則將當前頁面直接放入　　{　　for (j = 0; j < mSize; j ++)　　{　　if (memery[j] == 0)</

69、p>　　{　　memery[j] = page[i];　　break;　　}　　}</

70、p>　　}　　else //物理塊已滿的情況下　　{　　use[0] = 100;　　for (j = 0; j < mSize; j ++) //在已放

71、入物理塊的頁中查找當前使用次數(shù)最少的頁　　{　　if (use[memery[j]] < use[0])　　{　　use[0] = use[memery[j]];&l

72、t;p>　　replace = j; //標記頁號　　}　　}　　memery[replace] = page[i];　　}

73、　　}　　else 　　flag = ' ';　　pflag[i] = flag; //記錄當前頁的缺頁情況　　for (j = 0; j <

74、mSize; j ++) //記錄每一次的置換情況　　table[j][i] = memery[j];　　}　　Compute();　　showTable(page, pSize, mSize);<p&

75、gt;　　}　　輔助函數(shù)　　Designer函數(shù)：　　void Designer() 　　{　　printf(&

76、quot;┏━━━━━━━━━━━━━━━━━━━━━━━━━┓\n");　　printf("┃◎◎◎ 課題：頁面置換算法 ◎◎◎┃\n");　　printf("┃◎◎◎ 學號：11150038 ◎◎◎┃\n");</p

77、>　　printf("┃◎◎◎ 姓名：李艷平 ◎◎◎┃\n");　　printf("┃◎◎◎ <Visual C++ 6.0> ◎◎◎┃\n");　　printf("┗━━━━━

78、━━━━━━━━━━━━━━━━━━━━┛\n");　　}　　mDelay函數(shù)：　　void mDelay(unsigned int Delay) 　　{</

79、b>　　unsigned int i;　　while (Delay > 0)　　{　　for (i = 0; i < 125; i++)　　printf(" \b&

80、quot;);　　Delay--;　　}　　}　　Download函數(shù)：　　void Download(int pS

81、ize, int mSize)　　{　　int i;　　system("color 0D");　　printf("┏┅┅┅┅┅┅┅┅┅┅┅┅┓\n");&l

82、t;/p>　　printf("┇正在載入數(shù)據(jù)，請稍后... ┇\n");　　printf("┗┅┅┅┅┅┅┅┅┅┅┅┅┛\n");　　printf("Loading...\n");　　printf("

83、 0\n");　　for (i = 0; i < 51; i++)　　printf("\b");　　for (i = 0; i < 50; i++)<p&

84、gt;　　{　　mDelay((pSize+mSize)/2);　　printf(">");　　}　　printf("\nFinish.\n載入成功，按任意鍵進

85、入置換算法選擇界面：>>>");　　getchar();　　}　　Compute函數(shù)：　　void Compute()　　{&

86、lt;/p>　　int i;　　printf("正在進行相關(guān)計算，請稍候...\n");　　for(i=1;i<20;i++)　　{　　mDe

87、lay(15);　　if(i%4==0)　　printf("\b\b\b\b\b\b \b\b\b\b\b\b");　　else　　printf(">>>");<

88、;/p>　　}　　for(i=0;i++<30;printf("\b"));　　for(i=0;i++<30;printf(" "));　　for(i=0;i++<30;printf(&qu

89、ot;\b"));　　}　　showTable函數(shù)：　　void showTable(int page[], int pSize, int mSize) 　　{

90、　　int i, j;　　/*printf("即將進入物理塊的頁面序列為:\n");　　for (i = 0; i < pSize; i ++)　　printf("%3d", page[i]);

91、;　　printf("\n輸出置換過程，“*”標記缺頁中斷處\n");*/　　for (i = 0; i < mSize; i ++)　　{　　for (j = 0; j < pSize; j ++)

92、　　printf("%3d", table[i][j]);　　printf("\n");　　}　　for (i = 0; i < pSize; i ++)　　print

93、f("%3c", pflag[i]);　　printf("\n━━━━━━━━━━━━━━━━━━━━━━━━━━━━\n");　　printf("總的缺頁次數(shù)為：%d\n", sum);　　printf("缺頁中斷率為：%.2lf%%\n&q

94、uot;, 100.0 * sum / pSize);　　printf("◆ ◆ ◆ ◆ ◆ ◆ ◆ ◆ ◆ ◆ ◆ ◆ ◆ ◆ ◆ ◆ ◆ ◆ ◆ \n");　　}　　第五部分實現(xiàn)源代碼　　#include

95、<stdio.h>　　#include <stdlib.h>　　/*宏定義*/　　#define MSIZE 10 //最大物理塊數(shù)　　#define PSIZE 50 //最大頁面數(shù)</p&

96、gt;　　/*全局變量*/　　char flag, pflag[PSIZE]; //缺頁標志 　　int table[MSIZE][PSIZE]; //存放置換記錄　　int sum = 0; //記錄每個算法的缺頁次數(shù)</p&g

97、t;　　/*置換算法函數(shù)*/　　void OPT(int page[], int pSize, int mSize); //最佳置換算法　　void FIFO(int page[], int pSize, int mSize); //先進先出置換算法　　void LRU(int page[

98、], int pSize, int mSize); //最久未使用置換算法　　void LFU(int page[], int pSize, int mSize); //最不經(jīng)常使用淘汰算法(當前使用次數(shù)最少)　　/*輔助函數(shù)*/　　void Designer(); /

99、/顯示設計者信息　　void mDelay(unsigned int Delay); //設置延遲　　void Download(int pSize, int mSize); //載入數(shù)據(jù)　　void Compute(); //計算過程延遲　　void showT

100、able(int page[], int pSize, int mSize); //輸出置換過程 　　【主函數(shù)及其他函數(shù)詳見第四部分】　　第六部分簡要的使用說明及主要運行界面　　主要運行界面：　　【運行環(huán)境——Visual C+

101、+ 6.0】　　(1)按任意鍵繼續(xù)：　?。?）載入數(shù)據(jù)：　?。?）進入置換算法選擇界面：　?。?）運算中延遲操作：　?。?）四種算法演示結(jié)果：<

102、b>　　（6）退出界面：　　第七部分總結(jié)（特色、經(jīng)驗、教訓和感受）　　兩周的課程設計結(jié)束了，在這次的課程設計中不僅檢驗了我所學習的知識，也培養(yǎng)了我如何去把握一件事情，如何去做一件事情，如何去堅持一件事情，又如何完成一件事情。　　在這次設計過程中，體現(xiàn)出自己單獨設計模具的能力以及綜合運用

103、知識的能力，體會了學以致用、突出自己勞動成果的喜悅心情，從中發(fā)現(xiàn)自己平時學習的不足和薄弱環(huán)節(jié)，從而加以彌補，同時對頁面置換算法有了更深入的了解。雖然在寫算法的過程中遇到了一些麻煩，但經(jīng)過我的堅持不懈最終解決了問題。　　同時感謝對我?guī)椭^的同學們，謝謝你們對我的幫助和支持，讓我感受到同學的友誼。由于本人的設計能力有限，在設計過程中難免出現(xiàn)錯誤，懇請老師們多多指教,我十分樂意接受你們的批評與指正，本

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

溫馨提示

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)課程設計報告--頁面置換算法模擬程序設計

文檔簡介

溫馨提示

最新文檔

評論

操作系統(tǒng)課程設計報告--頁面置換算法模擬程序設計

文檔簡介

溫馨提示

最新文檔

評論

免費下載