操作系統(tǒng)課程設(shè)計---頁面置換算法的模擬

1、<p><b>　　操作系統(tǒng)</b></p><p><b>　　課程設(shè)計報告</b></p><p>　　計算機(jī)科學(xué)與技術(shù)學(xué)院</p><p><b>　　目錄</b></p><p><b>　　一、設(shè)計目的3</b></p>

2、<p><b>　　二、設(shè)計內(nèi)容3</b></p><p><b>　?。?）概述3</b></p><p><b>　?。?）設(shè)計原理3</b></p><p>　　（3）詳細(xì)設(shè)計及編碼4</p><p>　?。?）運行結(jié)果分析12</p>

3、<p>　?。?）設(shè)計小結(jié)15</p><p>　?。?）參考文獻(xiàn)16</p><p>　　題目：頁面置換算法的模擬實現(xiàn)一</p><p><b>　　一、設(shè)計目的</b></p><p>　　本課程設(shè)計是學(xué)習(xí)完“操作系統(tǒng)原理”課程后進(jìn)行的一次全面的綜合訓(xùn)練，通過課程設(shè)計，更好地掌握操作系統(tǒng)的原理及實現(xiàn)方

4、法，加深對操作系統(tǒng)基礎(chǔ)理論和重要算法的理解，加強(qiáng)學(xué)生的動手能力。增加對linux系統(tǒng)的認(rèn)識和基本的命令語句。</p><p><b>　　二、設(shè)計內(nèi)容</b></p><p><b>　　（1）概述</b></p><p>　　設(shè)計一個虛擬存儲區(qū)和內(nèi)存工作區(qū),編程序演示下述算法的具體實現(xiàn)過程，并計算訪問命中率。用C語言實現(xiàn)

5、，要求設(shè)計主界面以靈活選擇某算法，且以下算法都要實現(xiàn)</p><p>　　1、先進(jìn)先出算法（FIFO）；</p><p>　　2、最近最久未使用算法（LRU）</p><p><b>　?。?）設(shè)計原理</b></p><p>　　存儲管理的主要功能之一是合理地分配空間。請求頁式管理是一種常用的虛擬存儲管理技術(shù)。本實驗的

6、目的是通過請求頁式管理中頁面置換算法模擬設(shè)計，了解虛擬存儲技術(shù)的特點，掌握請求頁式存儲管理的頁面置換算法。</p><p>　　通過計算不同算法的命中率比較算法的優(yōu)劣。同時也考慮了用戶內(nèi)存容量對命中率的影響。頁面失效次數(shù)為每次訪問相應(yīng)指令時，該指令所對應(yīng)的頁不在內(nèi)存中的次數(shù)。</p><p>　　1、先進(jìn)先出算法（FIFO）；如果內(nèi)存中含有該頁面則不用淘汰頁面。而內(nèi)存中不存在該頁面先進(jìn)先出

7、的算法主要是先進(jìn)入棧的先后進(jìn)行葉面淘汰算法，及通過計入頁面失效的次數(shù)而計算出命中率。</p><p>　　2、最近最久未使用算法（LRU）；如果內(nèi)存中含有該頁面則不用淘汰頁面。而內(nèi)存中不存在該頁面最近最久未被使用時在同一時間內(nèi)優(yōu)先淘汰在內(nèi)存中最近最久未被使用的頁面淘汰掉。通過計入頁面失效的次數(shù)而計算出命中率。</p><p>　?。?）詳細(xì)設(shè)計及編碼</p><p>

8、;　　一、實現(xiàn)該功能的程序流程圖如下：</p><p>　　頁面置換算法的中流程圖：</p><p>　　1、 FIFO 頁面置換算法的流程圖：</p><p>　　2、LRU頁面置換算法</p><p>　　二、先進(jìn)先出（FIFO）和最近最久未使用算法（LRU）的頁面置換算法代碼如下：</p><p>　　#incl

9、ude<stdio.h></p><p>　　#include<stdlib.h></p><p>　　#include<time.h> //windows下面運行則用#include<process.h></p><p>　　#define RRUE 1</p><p>　　#d

10、efine FALSE 0</p><p>　　#define INVALID - 1</p><p>　　#define NULL 0</p><p>　　#define total_instruction 320 //指令</p><p>　　#define total_vp 32 //頁面</p&g

11、t;<p>　　typedef struct</p><p><b>　　{</b></p><p><b>　　int pn;</b></p><p><b>　　int pfn;</b></p><p>　　int counter;</p>&l

12、t;p><b>　　int time;</b></p><p><b>　　}pl_type;</b></p><p>　　pl_type pl[32]; //構(gòu)造頁面類型</p><p>　　typedef struct pfc_struct</p><

13、p><b>　　{</b></p><p><b>　　int pn;</b></p><p><b>　　int pfn;</b></p><p>　　struct pfc_struct *next;</p><p>　　}pfc_type;</p>&l

14、t;p>　　pfc_type pfc[32]; //頁面控制結(jié)構(gòu)</p><p>　　pfc_type *freepf_head;</p><p>　　pfc_type *busypf_head;</p><p>　　pfc_type *busypf_tail;</p><p>　　int disef

15、fect;</p><p>　　int a[total_instruction];</p><p>　　int page[total_instruction];</p><p>　　int offset[total_instruction];</p><p>　　void initialize();//初始化函數(shù)，給頁面

16、賦初始值</p><p>　　void FIFO(int total_pf);//先進(jìn)先出頁面置換算法 </p><p>　　void LRU(int total_pf);//最近最久未被使用頁面置換算法</p><p>　　void main()</p><p><b>　　{</b></p>

17、<p><b>　　int s,i;</b></p><p>　　srand(10*getpid());/*由于每次運行時進(jìn)程號不同，顧客用來</p><p>　　作為初始化隨機(jī)數(shù)隊列的“種子”。*/</p><p>　　s = (int)((float)319*rand()/32767/32767/2)+1;//隨機(jī)

18、命令地址</p><p>　　for(i = 0;i<total_instruction;i+= 4) //產(chǎn)生指令隊列</p><p><b>　　{</b></p><p>　　if(s<0 || s>319)</p><p><b>　　{</b></p>

19、<p>　　printf("When i == %d,Error,s == %d\n",i,s);</p><p><b>　　exit(0);</b></p><p><b>　　}</b></p><p>　　a[i] = s;//任選一指令訪問點m</p>

20、<p>　　a[i+1] = a[i]+1;//順序執(zhí)行一條指令</p><p>　　a[i+2] = (int)((float)a[i]*rand()/32767/32767/2); //執(zhí)行前地址指令m'</p><p>　　a[i+3] = a[i+2]+1;//順序執(zhí)行一條指令</p><p>　　s=(int)(

21、(float)(318 - a[i+2])*rand()/32767/32767/2 + a[i+2]) + 2;//可以在windows下面運行的話則將/32767/32767改成%320</p><p>　　if((a[i+2]>318) || (s>319))</p><p>　　printf("a[%d+2],a number which is : %d an

22、d s == %d\n",i,a[i+2],s);</p><p><b>　　}</b></p><p>　　/*for(i = 0;i<total_instruction;i++)</p><p><b>　　{</b></p><p>　　printf(" %d&q

23、uot;,a[i]);</p><p><b>　　}</b></p><p><b>　　*/</b></p><p>　　for(i = 0;i<total_instruction;i++)//將指令變換成頁地址流</p><p><b>　　{</b><

24、/p><p>　　page[i] = a[i]/10;</p><p>　　offset[i] = a[i]%10;</p><p><b>　　}</b></p><p>　　for(i =4;i<=32;i++)//用戶內(nèi)存工作區(qū)從4個頁面到32個頁面</p><p><

25、b>　　{</b></p><p>　　printf("%2d page frames",i);</p><p><b>　　FIFO(i);</b></p><p><b>　　LRU(i);</b></p><p>　　printf("\n&quo

26、t;);</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void initialize(int total_pf)//total_pf是用戶進(jìn)程的內(nèi)存頁面數(shù)</p><p><b>　　{</b></p>

27、;<p><b>　　int i;</b></p><p>　　diseffect = 0;</p><p>　　for(i =0;i<total_vp;i++)</p><p><b>　　{</b></p><p>　　pl[i].pn = i;</p><

28、;p>　　pl[i].pfn = INVALID;//置頁面控制結(jié)構(gòu)中的頁號、頁面為空</p><p>　　pl[i].counter = 0;</p><p>　　pl[i].time = -1;//頁面控制結(jié)構(gòu)中的訪問次數(shù)為0，時間為-1</p><p><b>　　}</b></p><p&

29、gt;　　for(i = 0;i<total_pf - 1;i++)</p><p><b>　　{</b></p><p>　　pfc[i].next = &pfc[i+1];</p><p>　　pfc[i].pfn = i;</p><p>　　}//建立pfc[i]和pfc[i

30、+1]的鏈接</p><p>　　pfc[total_pf - 1].next = NULL;</p><p>　　pfc[total_pf - 1].pfn = total_pf - 1;</p><p>　　freepf_head = &pfc[0];//空頁面的頭指針為pfc[0]</p><p><b>

31、　　}</b></p><p>　　void FIFO(int total_pf)//先進(jìn)先出頁面置換算法</p><p><b>　　{</b></p><p><b>　　int i;</b></p><p>　　pfc_type *p;</p><

32、p>　　initialize(total_pf);</p><p>　　busypf_head = busypf_tail = NULL;//忙頁面隊列頭，隊列尾鏈接</p><p>　　for(i = 0;i<total_instruction;i++)</p><p><b>　　{</b></p><

33、p>　　if(pl[page[i]].pfn == INVALID)//頁面失效</p><p><b>　　{</b></p><p>　　diseffect+= 1;//失效次數(shù)</p><p>　　if(freepf_head == NULL)//無空閑頁面</p><p><

34、b>　　{</b></p><p>　　p = busypf_head->next;</p><p>　　pl[busypf_head->pn].pfn = INVALID;</p><p>　　freepf_head = busypf_head;//釋放忙頁面隊列的第一個頁面</p><p>　　freep

35、f_head->next = NULL;</p><p>　　busypf_head = p;</p><p><b>　　}</b></p><p>　　p = freepf_head->next;//按隊列先進(jìn)先出順序添加新頁面</p><p>　　freepf_head->next = N

36、ULL;</p><p>　　freepf_head->pn = page[i];</p><p>　　pl[page[i]].pfn = freepf_head->pfn;</p><p>　　if(busypf_tail == NULL)</p><p>　　busypf_head = busypf_tail = freepf

37、_head;</p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　busypf_tail->next = freepf_head;//釋放一個頁面</p><p>　　busypf_tail = freepf_head;</p>

38、<p><b>　　}</b></p><p>　　freepf_head = p;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　printf(" FIFO:%6.4f",1-(flo

39、at)diseffect/320);//輸出FIFO頁面置換算法的命中率</p><p><b>　　}</b></p><p>　　void LRU(int total_pf)</p><p><b>　　{</b></p><p>　　int min,minj,i,j,present_time;

40、</p><p>　　initialize(total_pf);</p><p>　　present_time = 0;</p><p>　　for(i = 0;i<total_instruction;i++)</p><p><b>　　{</b></p><p>　　if(pl[page

41、[i]].pfn == INVALID)</p><p><b>　　{</b></p><p>　　diseffect++;</p><p>　　if(freepf_head == NULL)</p><p><b>　　{</b></p><p>　　min = 3276

42、7;</p><p>　　for(j = 0;j<total_vp;j++)//找出time的最小值</p><p>　　if(min>pl[j].time && pl[j].pfn!=INVALID)</p><p><b>　　{</b></p><p>　　min = pl[

43、j].time;</p><p><b>　　minj = j;</b></p><p><b>　　}</b></p><p>　　freepf_head = &pfc[pl[minj].pfn];//騰出一個單元</p><p>　　pl[minj].pfn = INVALID;<

44、/p><p>　　pl[minj].time = -1;</p><p>　　freepf_head->next = NULL;</p><p><b>　　}</b></p><p>　　pl[page[i]].pfn = freepf_head->pfn;//有空閑頁面，改為有效頁面</p>

45、<p>　　pl[page[i]].time = present_time;</p><p>　　freepf_head = freepf_head->next;</p><p><b>　　}</b></p><p><b>　　else</b></p><p>　　pl[page

46、[i]].time = present_time;//命中則增加該單元的訪問次數(shù)</p><p>　　present_time++;</p><p><b>　　}</b></p><p>　　printf(" LRU:%6.4f",1 - (float)diseffect/320);//輸出LRU頁面置換算法的

47、命中率</p><p><b>　　}</b></p><p><b>　?。?）運行結(jié)果分析</b></p><p><b>　　實驗結(jié)果截圖如下：</b></p><p>　　1、使用linux系統(tǒng)下面的運行過程：</p><p>　　2、使用lin

48、ux系統(tǒng)下的運行結(jié)果：</p><p>　　3、在windows下面的運行結(jié)果：</p><p>　　通過編譯可知道先進(jìn)先出算法（FIFO）；通過分析FIFO頁面置換算法，可以看出是先進(jìn)先出得頁面淘汰算法。會出現(xiàn)隨著內(nèi)存頁面的增加有可能出現(xiàn)belady現(xiàn)象。及隨著頁面數(shù)增加而缺頁數(shù)增加從而使得命中率降低。</p><p>　　通過兩個編譯的對比可以看出最近最久未使用

49、算法（LRU）；在最近得時間內(nèi)最久未被使用的頁面進(jìn)行淘汰。頁面置換算法是隨著內(nèi)存頁面數(shù)的增加而使得缺頁數(shù)的減少從而命中率升高。</p><p><b>　　（5）設(shè)計小結(jié)</b></p><p>　　本次課程設(shè)計就頁面置換算法中的兩種算法進(jìn)行了編譯，而這次課程設(shè)計的主要是先進(jìn)先出（FIFO）和最近最久未被訪問（LRU）的頁面置換算法進(jìn)行編譯。</p>&

50、lt;p>　　通過本次課程設(shè)計知道了存儲管理的主要功能之一是合理地分配空間。請求頁式管理是一種常用的虛擬存儲管理技術(shù)。本課程設(shè)計的了解了請求頁式管理中頁面置換算法的模擬，了解虛擬存儲技術(shù)的特點，掌握請求頁式存儲管理的頁面置換算法先進(jìn)先出（FIFO）和最近最久未被訪問（LRU）。本次課程設(shè)計開始設(shè)計時候出現(xiàn)一些小問題，（如：s = (int)(float)319*rand()/32767/32767/2+1;是一條隨機(jī)生成數(shù)據(jù)的方

51、法。rand()的取值范圍是0-32767之間）剛開始時由于編譯代碼有一部分是在書上找到的資料按照要求編譯進(jìn)去會出現(xiàn)一些沒有定義的字符和變量。以及各種函數(shù)的運用。當(dāng)出現(xiàn)問題時候主要是通過百度等網(wǎng)站去查詢所要的結(jié)果?；蛘呤菃柾瑢W(xué)，老師解決問題。將改程序放在linux系統(tǒng)下執(zhí)行，是我了解了基本的linux環(huán)境下編譯代碼和執(zhí)行命令的語句。以及一些linux的基本用途和基本的執(zhí)行命令。試驗中最常犯的是編譯代碼是忘記了變量的大小寫導(dǎo)致名字不一致。

52、另外在linux環(huán)境進(jìn)行生成可執(zhí)行文件時命令敲錯忘記命令的用處等問題。（如：srand(10*getpid());語句只能夠在linux系統(tǒng)</p><p>　　本人在這次課程設(shè)計的感受是一個人編程時要注意多上網(wǎng)查找錯誤的原因，只有自己查找出來的原因差能記得更加的長久。更加的了解網(wǎng)絡(luò)的用處所在和增強(qiáng)上網(wǎng)查找所需要的信息篩選。以及一些關(guān)鍵字的輸入方法。但是也不是說上網(wǎng)查找時主要的，其主要還是要問老師和同學(xué)畢竟他們了

53、解的可能比你多很多。就在身邊不會浪費時間去網(wǎng)上尋找一些無關(guān)的文件和篩選信息的時間。</p><p><b>　?。?）參考文獻(xiàn)</b></p><p>　　[1]計算機(jī)操作系統(tǒng)(第3版)，湯小丹，西安電子科技大學(xué)出版社，2007年7月</p><p>　　[2]計算機(jī)操作系統(tǒng)試驗指導(dǎo)（第3版），張堯?qū)W，清華大學(xué)出版社，2006年10月</