計(jì)算機(jī)操作系統(tǒng)實(shí)驗(yàn)?zāi)M比較頁面置換頁算法及缺頁率.doc

1、 成績計(jì)算機(jī)操作系統(tǒng)實(shí)驗(yàn)?zāi)M比較頁面置換頁算法及缺頁率學(xué) 號200510020220姓 名喬 峰班 級信息052實(shí)驗(yàn)名稱： 模擬比較頁面置換頁算法及缺頁率實(shí)驗(yàn)?zāi)康模?（1）掌握先進(jìn)先出頁面置換算法；（2）掌握最近未用頁面置換算法；(3)了解最近最久未使用頁面置換算法以及其他頁面置換算法;（4）熟悉C/C+編程。實(shí)驗(yàn)學(xué)時(shí): 6學(xué)時(shí) 實(shí)驗(yàn)內(nèi)容： 編寫程序，設(shè)置不同的頁面數(shù)，使用不同的頁面替換策略算法進(jìn)行模擬頁面替換。先進(jìn)先出，最近未用頁面置換算法等,并計(jì)算缺頁率。實(shí)驗(yàn)環(huán)境：(1）PC微機(jī)(2)Windows 操作系統(tǒng)(3）C/C+開發(fā)環(huán)境實(shí)驗(yàn)原理及算法參考程序段:#include <coni

2、o。h#include <stdio。h#include dos。h>include <stdlib。hinclude <math。h>int add256/*地址/,page256/*頁面*/;int k，j，ram,t；float rate;/*缺頁率*/struct s1 int page； int free； int tag； fifo33，opt33，lru33；struct s2 int time;void address（)；float FIFO(int ram）；/*先進(jìn)先出/float LRU(int ram)；/*最近最久未使用頁面置換*/vo

3、id address() /產(chǎn)生指令地址*/ int i； add0=1000; for (i=1; i=255; i+) int x=random（1024); if (（x>=0）&（x<512） addi=addi-1+1； if （(x>=512）&&(x768)） addi=random（addi1-1)+1; if (x=768）（x<1024） addi=addi1+random(30*1024addi-11）+1； float FIFO(int ram) int absent=0,t=0，i，z，l，yn; for (i=0； i

4、<ram； i+) fifoi。page=-1； fifoi。free=1; fifoi.tag=0； i=0; while （i<j) yn=0； for (z=0; z<ram； z+) /*the page is in the ram？/if （fifoz。page=pagei) yn=1; for (z=0; z<ram； z+) if （fifoz.free=0) fifoz.tag+=1; if （yn！=1） absent+=1； /*count the absent page/ l=0; while （lram)&&(fifol.free

5、=0) l+； if （(lram）&（fifol。free=1)） /*any free ram？*/ fifol。page=pagei； fifol。free=0； for (l=0; l<ram; l+) if (fifol.free=0 ) fifol。tag+=1; else /there is no free ram/ t=0; for （l=0； l<ram； l+）if ( fifol.tagfifot.tag） t=l; fifot.page=pagei; fifot.free=0； fifot。tag=1； l=0； i+； rate=(float）ab

6、sent/j100； return rate;float LRU(int ram） int absent=0,yn,t,i，l，z，now=0; struct s2 P250； for (i=0；i<j；i+) Pi.time=0； for (i=0; iram; i+) lrui.page=1； lrui.free=1; i=0； while(ij) for(l=0; lram; l+) yn=0; for（z=0； z<ram; z+） if （lruz.page=pagei) now+=1; Plruz。page。time=now; yn=1; if （yn!=1） abse

7、nt+=1; now+=1； l=0; while (（l<=ram）&（lrul.free=0） l+； if （(l<=ram）(lrul。free=1)） /*any free ram?*/ lrul.page=pagei; Plrul。page。time=now； lrul。free=0; else /there is no ram/ t=0； for (l=0; l<ram； l+） if ( Plrul。page。timePlrut。page。time) t=l； lrut.page=pagei； Plrut。page.time=now; i+； rate

8、=(float）absent/j*100； return rate；void main（) int i,p256；/*頁號*/ clrscr()； address(）; for （k=1; k<=8;） /頁面大小: 1k，2k,4k，8K*/ printf（”the size of a page is %d kn ”,k）； printf("the page num is 。.。n")； for (i=0； i<256； i+) pi=addi/(k*1024）；/將指令地址生成相應(yīng)的頁號/ printf（”d ”,pi); j=0; for （i=0； i&

9、lt;256； i+) while (pi=pi+1） i+; pagej=pi； j+； printf(”nafter connect the same pages the page num is：n"); for （i=0； i<j; i+） printf(”d ”,pagei）； printf("n”）； getch()； for （ram=1; ram=32； ram+) if (ram=10) getch()； printf("nblock=d pages= %d，absent rate： ”,ram，j)； printf（"FIFO=0

10、.2f%",FIFO（ram）; printf("LRU =0。2f%",LRU（ram）； printf（"OPT =%0.2f%"，OPT（ram); k=k*2； getch(); 實(shí)驗(yàn)小結(jié)：通過本次實(shí)驗(yàn)掌握了先進(jìn)先出和最近最久未使用頁面置換算法，同時(shí)也對其他的頁面置換算法也更加熟悉。在實(shí)驗(yàn)過程中熟悉了C語言的編程環(huán)境,并能夠用C編程模擬比較也面置換算法，對編程也有一定的提高。代碼：#include ”stdio。h”include ”stdlib。h”include "conio.h”include "ctype.h

11、”/定義頁,采用雙向鏈表存儲(chǔ)結(jié)構(gòu)struct pageunsigned int number;/頁號unsigned int baseaddress;/頁開始地址/其它信息struct page *nextpage，*priorpage;/下一頁和前一頁;/定義頁表struct pagetableunsigned int pid;/進(jìn)程號unsigned int pagenum;/頁表大小unsigned int pagetablesize；/頁表最大表目struct page *head；/頁表頭指針，指向頭結(jié)點(diǎn)，頭結(jié)點(diǎn)指向第一頁；/FIFO頁面訪問程序，函數(shù)調(diào)用時(shí)要傳遞過來頁表pt,要訪問

12、的頁面號accesspage,返回是否發(fā)生缺頁中斷（1是0否）int access（struct pagetable *pt， unsigned int accesspage）struct page newpage；/新頁面struct page currentpage=pt->head-nextpage；/當(dāng)前頁struct page * replacedpage;/要淘汰的頁/在當(dāng)前頁中尋找要訪問的頁號while(currentpagecurrentpagenumber！=accesspage)currentpage=currentpagenextpage；/找到頁號則打印，并返回0

13、if(currentpage!=NULL&currentpage>number=accesspage）printf（”"）；return 0；/沒找到則判斷頁表是否已經(jīng)滿了,沒滿則調(diào)入新頁并打印×返回1else if（pt>pagenum<pt->pagetablesize)newpage=(struct page *)malloc（sizeof(struct page)；newpage-number=accesspage;newpage-nextpage=newpage->priorpage=NULL;newpage>nextp

14、age=pt>head>nextpage；if（pt>head>nextpage)pt->headnextpage ->priorpage=newpage；ptheadnextpage=newpage;newpage-priorpage=pthead;pt-pagenum+;printf（”×”）；return 1;/如頁表已經(jīng)滿,則采用fifo算法進(jìn)行淘汰選擇elsecurrentpage=pt-head>nextpage;replacedpage=NULL;while(currentpagenextpage)currentpage=cur

15、rentpagenextpage;replacedpage=currentpage；if(replacedpage->nextpage）replacedpage>nextpagepriorpage=replacedpage->priorpage；replacedpage-priorpage>nextpage=replacedpage-nextpage;free(replacedpage）;newpage=（struct page ）malloc(sizeof（struct page)；newpage-number=accesspage;newpage>nextpa

16、ge=newpage-priorpage=NULL；newpage-nextpage=pt>head>nextpage; if（pthead->nextpage）pt-headnextpage->priorpage=newpage;pt-head->nextpage=newpage；newpage>priorpage=pthead;printf(”×"）；return 1；main(）struct pagetable pt；unsigned int totalabsence=0，totalpagenum=10;unsigned int r

17、estpage100；unsigned int i=0；pt。pagenum=0;pt。pagetablesize=3；pt。head=（struct page*）malloc(sizeof（struct page）);pt.head>nextpage=pt.head>priorpage=NULL;/從文件獲取要讀入的頁面流FILE fp；fp=fopen（”IN.dat","r”)；if(fp=NULL）printf（”can not open file IN。DAT！”)；return;while（!feof（fp）)fscanf（fp,"%d",restpagei）；i+;fclose（fp);totalpagenum=i；printf（”this program for fifo nn"）；/打印要訪問的頁for（i=0;itotalp