操作系統(tǒng)實(shí)驗(yàn)報(bào)告6-頁面置換算法模擬

1、實(shí) 驗(yàn) 報(bào) 告（ 2013 / 2014學(xué)年 第1學(xué)期）課程名稱操作系統(tǒng)原理實(shí)驗(yàn)名稱實(shí)驗(yàn)6：頁面置換算法模擬實(shí)驗(yàn)時(shí)間2013年12月 10日指導(dǎo)單位軟件工程系指導(dǎo)教師 楊 健學(xué)生姓名班級(jí)學(xué)號(hào)學(xué)院(系)軟件工程系專 業(yè)計(jì)算機(jī)軟件與服務(wù)外包實(shí)驗(yàn)名稱實(shí)驗(yàn)1：Linux操作、使用、編程與進(jìn)程創(chuàng)建指導(dǎo)教師楊健實(shí)驗(yàn)類型實(shí)驗(yàn)實(shí)驗(yàn)學(xué)時(shí)2實(shí)驗(yàn)時(shí)間2013.12.10一、 實(shí)驗(yàn)?zāi)康?通過模擬實(shí)現(xiàn)幾種基本頁面置換的算法，了解虛擬存儲(chǔ)技術(shù)的特點(diǎn)。2掌握虛擬存儲(chǔ)請(qǐng)求頁式存儲(chǔ)管理中幾種基本頁面置換算法的基本思想，并至少用三種算法來模擬實(shí)現(xiàn)。3通過對(duì)幾種置換算法頁面的比較，來對(duì)比他們的優(yōu)缺點(diǎn)，并通過比較更換頻率來對(duì)比它們的

2、效率。二、實(shí)驗(yàn)環(huán)境(實(shí)驗(yàn)設(shè)備)Windows 2000 Visual Studio三、實(shí)驗(yàn)內(nèi)容設(shè)計(jì)一個(gè)虛擬存儲(chǔ)區(qū)和內(nèi)存工作區(qū)，并使用下述算法來模擬實(shí)現(xiàn)頁面的置換：1. 先進(jìn)先出的算法（FIFO）2. 最近最久未使用算法（LRU）3. 最佳置換算法（OPT）實(shí)驗(yàn)分析在進(jìn)程運(yùn)行過程中，若其所訪問的頁面不存在內(nèi)存而需要把它們調(diào)入內(nèi)存，但內(nèi)存已無空閑時(shí)，為了保證該進(jìn)程能夠正常運(yùn)行，系統(tǒng)必須從內(nèi)存中調(diào)出一頁程序或數(shù)據(jù)送磁盤的對(duì)換區(qū)中。但應(yīng)調(diào)出哪個(gè)頁面，需根據(jù)一定的算法來確定，算法的好壞，直接影響到系統(tǒng)的性能。一個(gè)好的頁面置換算法，應(yīng)該有較低的頁面更換頻率。 假設(shè)分給一作業(yè)的物理塊數(shù)為3 ，頁面數(shù)為20個(gè)

3、。頁面號(hào)為(20個(gè))：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，11先進(jìn)先出(FIFO)置換算法的思路該算法總是淘汰最先進(jìn)入內(nèi)存的頁面，即選擇在內(nèi)存中駐留時(shí)間最久的頁面予以淘汰。該算法實(shí)現(xiàn)簡(jiǎn)單，只需把一個(gè)進(jìn)程已調(diào)入內(nèi)存的頁面，按照先后次序連接成一個(gè)隊(duì)列，并設(shè)置一個(gè)替換指針，使它總指向最老的頁面。2最近久未使用(LRU)置換算法的思路最近久未使用置換算法的替換規(guī)則，是根據(jù)頁面調(diào)入內(nèi)存后的使用情況來進(jìn)行決策的。該算法賦予每個(gè)頁面一個(gè)訪問字段，用來記錄一個(gè)頁面自上次被訪問以來所經(jīng)歷的時(shí)間，當(dāng)需淘汰一個(gè)頁面的時(shí)候選擇現(xiàn)有頁面中其時(shí)間值最大的進(jìn)行淘汰。3.最佳（OPT）

4、置換算法的思路其所選擇的被淘汰的頁面，獎(jiǎng)是以后不使用的，或者是在未來時(shí)間內(nèi)不再被訪問的頁面，采用最佳算法，通?？杀ＷC獲得最低的缺頁率。4FIFO頁面置換算法當(dāng)需要訪問一個(gè)新的頁面時(shí)，首先調(diào)用findExist(i)函數(shù)來查看物理塊中是否就有這個(gè)頁面，若要查看的頁面物理塊中就有，則調(diào)用display函數(shù)直接顯示，不需要替換頁面；如果要查看的頁面物理塊中沒有，就需要尋找空閑物理塊放入，若存在有空閑物理塊，則將頁面放入；若沒有空閑物理塊，則調(diào)用findReplace函數(shù)替換頁面。并將物理塊中所有頁面timer+。5LRU頁面置換算法當(dāng)需要訪問一個(gè)新的頁面，首先調(diào)用findExist(i)函數(shù)查看物理

5、塊中是否就有這個(gè)頁面。6. OPT頁面置換算法 當(dāng)需要訪問一個(gè)新的頁面，首先調(diào)用findExist(i)函數(shù)來查看物理塊中是否有這個(gè)頁面。7尋找置換頁面函數(shù)findReplace比較三個(gè)物理塊中的時(shí)間標(biāo)記timer，找到時(shí)間最久的。代碼#include<stdio.h>#include<stdlib.h>#include<time.h>#define BLOCK_MAX_SIZE 20/最?大洙?物?理?塊é大洙?小?enumFIFO=1,LRU,OPT;struct node_pageint address;/指?令?地?址·int p

6、age_num;/頁?面?號(hào)?int next_order;/下?一?次?訪?問ê的?次?序ò*page;/物?理?塊é定¨義?typedef struct BlockNodeint page_index;/page數(shù)簓組哩?的?下?標(biāo)括?struct BlockNode * next;BlockNode;structint length;/當(dāng)獺?前°物?理?塊é長(zhǎng)¤度èint miss_flag;/缺?頁?標(biāo)括?志?，?若?為a1，?則ò缺?頁?int miss_count;/缺?頁?次?數(shù)簓 Bloc

7、kNode*front; BlockNode*rear;Block;/本?程ì序ò中D全?局?變?量?名?均ù由?兩?個(gè)?單蹋?詞洙?組哩?成é，?且ò開a頭?字?母?大洙?寫int BlockSize = 5;/物?理?塊é大洙?小?int PageCount = 200;/頁?面?總哩?數(shù)簓int PageSize = 1024;/頁?面?大洙?小?int AddrRange = 8*1024;/訪?問ê地?址·范?圍§int get_num(int down,int up)/得?到?一?個(gè)?down

8、up之?間?的?整?數(shù)簓int num;char str111;while(1)fgets(str,111*sizeof(int),stdin);num=atoi(str);/把?字?符?串?中D的?數(shù)簓字?轉(zhuǎn)羇換?為a整?數(shù)簓if(num>=down&& num<=up) break;printf("輸?入?范?圍§有瓺誤ó,請(qǐng)?重?新?輸?入?:");/whilereturn num;void init_block()/構(gòu)1造ì一?個(gè)?空?的?物?理?塊é隊(duì)ó列Block.rear=Block

9、.front=(BlockNode*)malloc(sizeof(BlockNode);if(!Block.front)printf("內(nèi)ú存?分?配?失骸?敗悒?n"); exit(0);Block.length=0;Block.miss_count=0;Block.rear->next=NULL;void enqueue(int page_index)/入?隊(duì)óBlockNode*node=(BlockNode*)malloc(sizeof(BlockNode);if(!node)printf("內(nèi)ú存?分?配?失骸?敗悒?

10、n");exit(0);node->page_index=page_index;node->next=NULL;Block.length+;Block.rear->next=node;Block.rear=node;void dequeue()/出?隊(duì)óBlockNode*node;node=Block.front->next;Block.front->next=node->next;if(node= Block.rear)Block.rear=Block.front;free(node);Block.length-;void clear

11、_block()/清?空?物?理?塊éwhile(Block.rear=Block.front->next)Block.front->next=Block.rear->next; free(Block.rear);Block.length-;Block.rear=Block.front;Block.length=0;Block.miss_count=0;void destroy_block()/銷ú毀ù物?理?塊éwhile(Block.rear=Block.front)Block.front=Block.front->next;

12、free(Block.rear);free(page);void init_page()/初?始?化頁?面?系列int i,j;srand(time(NULL);/用?當(dāng)獺?前°系統(tǒng)?時(shí)骸?間?來?初?始?化隨?機(jī)ú種?子哩?page=(struct node_page*) malloc(PageCount*sizeof(struct node_page);for(i=0;i<PageCount;i+)pagei.address=rand()%AddrRange;pagei.page_num=pagei.address/PageSize;for(i=0;i<Pa

13、geCount;i+)for(j=i+1;j<PageCount;j+)if(pagei.page_num= pagej.page_num)pagei.next_order=j;break;/if/forif(j= PageCount)/說明÷pagei以?后ó都?不?會(huì)á再ù訪?問êpagei.next_order= PageCount;/forvoid print_page()/打洙?印?頁?面?系列int i;printf("n");printf("頁?面?系列為a：阰n");for(i=0;

14、i<PageCount;i+)printf("%-2d,%-4d",pagei.page_num,pagei.address%PageSize);if(i+1)%5= 0)printf("n");/ifprintf("n");void FIFO_Replace(int page_index)/FIFO置?換?BlockNode*node;if(!Block.length)enqueue(page_index);Block.miss_flag=0;return;node=Block.front;while(node=node-&g

15、t;next)if(pagenode->page_index.page_num=pagepage_index.page_num)Block.miss_flag=0;return;if(Block.length<BlockSize)enqueue(page_index);Block.miss_flag=0;return;dequeue();enqueue(page_index);Block.miss_flag=1;Block.miss_count+;void LRU_Replace(int page_index)/LRU置?換?BlockNode*node,*last_node;if

16、(!Block.length)enqueue(page_index);Block.miss_flag=0;return;last_node=node=Block.front;while(node=node->next)if(pagenode->page_index.page_num= pagepage_index.page_num)last_node->next=node->next;Block.length-;if(node= Block.rear)Block.rear=last_node;enqueue(node->page_index);free(node)

17、;Block.miss_flag=0;return;last_node=node;if(Block.length<BlockSize)enqueue(page_index);Block.miss_flag=0;return;dequeue();enqueue(page_index);Block.miss_flag=1;Block.miss_count+;void OPT_Replace(int page_index)/OPT置?換?BlockNode*node;BlockNode*max_node,*max_node_last;if(!Block.length)enqueue(page_

18、index);Block.miss_flag=0;return;node=Block.front;while(node=node->next)if(pagenode->page_index.page_num= pagepage_index.page_num)node->page_index=page_index;Block.miss_flag=0;return;if(Block.length<BlockSize)enqueue(page_index);Block.miss_flag=0;return;node=Block.front;max_node=node->

19、next;while(node=node->next)/尋°找òBlock中Dnext_order值最?大洙?的?節(jié)ú點(diǎn)?if(pagemax_node->page_index.next_order<pagenode->page_index.next_order)max_node=node;node=Block.front;max_node_last=node;while(node=node->next)/尋°找òBlock中Dnext_order值最?大洙?的?節(jié)ú點(diǎn)?的?上?一?個(gè)?節(jié)ú點(diǎn)?

20、if(node= max_node)break;max_node_last=node;max_node_last->next= max_node->next;Block.length-;if(max_node= Block.rear)Block.rear=max_node_last;free(max_node);enqueue(page_index);Block.miss_flag=1;Block.miss_count+;void page_replace(int num)int i,j; BlockNode*node;char str35="FIFO",&qu

21、ot;LRU ","OPT "printf("=%s=n",strnum-1);printf("頁?面?號(hào)?*");for(i=0;i< BlockSize;i+)printf(" ");printf("* 是?否?缺?頁? *n");printf("n");for(i=0;i<PageCount;i+)printf(" %-4d*",pagei.page_num);if(num= FIFO)FIFO_Replace(i);else

22、if(num = LRU)LRU_Replace(i);else if(num = OPT)OPT_Replace(i);node=Block.front;while(node=node->next)printf("%-2d",pagenode->page_index.page_num);for(j=Block.length;j<BlockSize;j+)printf(" ");printf("* %s *nn",(Block.miss_flag=1 ? "Yes" : "No"

23、;);printf("nn");printf("缺?頁?數(shù)簓:%d,缺?頁?率ê:%.2fnn",Block.miss_count,(float)Block.miss_count/PageCount *100);printf("按恪?回?車鍵ü繼ì續(xù)?!nn");getchar();void confige()/程ì序ò設(shè)?置?int num;while(1)printf("n*n");printf("* 程ì序ò設(shè)?置? *n&quo

24、t;);printf("*n");printf("* 1,設(shè)?置?物?理?塊é大洙?小?(默?認(rèn)?5) *n");printf("* 2,設(shè)?置?訪?問ê地?址·范?圍§ (默?認(rèn)?8K) *n");printf("* 3,設(shè)?置?頁?面?大洙?小?(默?認(rèn)?1K) *n");printf("* 4,設(shè)?置?頁?面?總哩?數(shù)簓(默?認(rèn)?200) *n");printf("* 5,顯?示?各÷項(xiàng)?設(shè)?置?值 *n");print

25、f("* 6,返?回? *n");printf("*n");printf("請(qǐng)?輸?入?您ú的?選?擇?:"); num=get_num(1,6);if(num=6)break;if(num=1)printf("請(qǐng)?輸?入?物?理?塊é大洙?小?(1%d):",BLOCK_MAX_SIZE);BlockSize=get_num(1,BLOCK_MAX_SIZE);printf("設(shè)?置?成é功|!nn");/ifelse if(num=2)printf("

26、請(qǐng)?輸?入?訪?問ê地?址·范?圍§(1%d)K: ",999);AddrRange=get_num(1,999)* 1024;printf("設(shè)?置?成é功|!nn");/elseifelse if(num=3)printf("請(qǐng)?輸?入?頁?面?大洙?小?(1%d)K: ",AddrRange/1024);PageSize=get_num(1,AddrRange/1024)* 1024;printf("設(shè)?置?成é功|!nn");/elseifelse if(num=4)

27、printf("請(qǐng)?輸?入?頁?面?總哩?數(shù)簓(1%d):",32767);PageCount=get_num(1,32767);printf("設(shè)?置?成é功|!nn");/elseifelse if(num=5)printf("-n");printf("*當(dāng)獺?前°物?理?塊é大洙?小?:%dn",BlockSize);printf("*當(dāng)獺?前°訪?問ê地?址·范?圍§:%d Kn",AddrRange/1024);pr

28、intf("*當(dāng)獺?前°頁?面?大洙?小?:%d Kn",PageSize/1024);printf("*當(dāng)獺?前°頁?面?總哩?數(shù)簓%dn",PageCount);printf("-n");free(page);init_page();void begin()int num;print_page();while(1)printf("n*n");printf("* 頁?面?置?換?算?法?*n");printf("*n");printf("* 1,先è進(jìn)?先è出?置?換?算?法?FIFO) *n");printf("* 2,最?近ü最?久?未使?用?置?換?算?法?LRU) *n");printf("* 3,最?佳?置?換?算?法?OPT) *n");printf("* 4,返?回? *n");printf("*n");printf("請(qǐng)?輸?入?您ú的?選?擇?:")