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

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

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

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

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

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

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

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

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

9、ude<stdio.h></p><p>　　#include<stdlib.h></p><p>　　#include<time.h> //windows下面運(yùn)行則用#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 //頁(yè)面</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)造頁(yè)面類型</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]; //頁(yè)面控制結(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ù)，給頁(yè)面

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

17、<p><b>　　int s,i;</b></p><p>　　srand(10*getpid());/*由于每次運(yùn)行時(shí)進(jìn)程號(hào)不同，顧客用來(lái)</p><p>　　作為初始化隨機(jī)數(shù)隊(duì)列的“種子”。*/</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)生指令隊(duì)列</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;//任選一指令訪問(wèn)點(diǎn)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下面運(yùn)行的話則將/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++)//將指令變換成頁(yè)地址流</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個(gè)頁(yè)面到32個(gè)頁(yè)面</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)存頁(yè)面數(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;//置頁(yè)面控制結(jié)構(gòu)中的頁(yè)號(hào)、頁(yè)面為空</p><p>　　pl[i].counter = 0;</p><p>　　pl[i].time = -1;//頁(yè)面控制結(jié)構(gòu)中的訪問(wèn)次數(shù)為0，時(shí)間為-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];//空頁(yè)面的頭指針為pfc[0]</p><p><b>

31、　　}</b></p><p>　　void FIFO(int total_pf)//先進(jìn)先出頁(yè)面置換算法</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;//忙頁(yè)面隊(duì)列頭，隊(duì)列尾鏈接</p><p>　　for(i = 0;i<total_instruction;i++)</p><p><b>　　{</b></p><

33、p>　　if(pl[page[i]].pfn == INVALID)//頁(yè)面失效</p><p><b>　　{</b></p><p>　　diseffect+= 1;//失效次數(shù)</p><p>　　if(freepf_head == NULL)//無(wú)空閑頁(yè)面</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;//釋放忙頁(yè)面隊(duì)列的第一個(gè)頁(yè)面</p><p>　　freep

35、f_head->next = NULL;</p><p>　　busypf_head = p;</p><p><b>　　}</b></p><p>　　p = freepf_head->next;//按隊(duì)列先進(jìn)先出順序添加新頁(yè)面</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;//釋放一個(gè)頁(yè)面</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頁(yè)面置換算法的命中率</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];//騰出一個(gè)單元</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;//有空閑頁(yè)面，改為有效頁(yè)面</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;//命中則增加該單元的訪問(wèn)次數(shù)</p><p>　　present_time++;</p><p><b>　　}</b></p><p>　　printf(" LRU:%6.4f",1 - (float)diseffect/320);//輸出LRU頁(yè)面置換算法的

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

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

49、算法（LRU）；在最近得時(shí)間內(nèi)最久未被使用的頁(yè)面進(jìn)行淘汰。頁(yè)面置換算法是隨著內(nèi)存頁(yè)面數(shù)的增加而使得缺頁(yè)數(shù)的減少?gòu)亩新噬摺?lt;/p><p><b>　?。?）設(shè)計(jì)小結(jié)</b></p><p>　　本次課程設(shè)計(jì)就頁(yè)面置換算法中的兩種算法進(jìn)行了編譯，而這次課程設(shè)計(jì)的主要是先進(jìn)先出（FIFO）和最近最久未被訪問(wèn)（LRU）的頁(yè)面置換算法進(jìn)行編譯。</p>&

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

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

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

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