請求頁式存儲管理的頁面置換算法

1、精選優(yōu)質(zhì)文檔-傾情為你奉上操作系統(tǒng)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)五 請求頁式存儲管理的頁面置換算法實(shí)驗(yàn)?zāi)康模和ㄟ^請求頁式存儲管理中頁面置換算法模擬程序，了解虛擬存儲技術(shù)的特點(diǎn)，掌握請求頁式存儲管理的頁面置換算法。實(shí)驗(yàn)屬性：設(shè)計(jì)實(shí)驗(yàn)內(nèi)容：1.通過隨機(jī)數(shù)產(chǎn)生一個(gè)指令序列，共320條指令，指令的地址按下述原則生產(chǎn)：50的指令是順序執(zhí)行的；25的指令是均勻分布在前地址部分；25的指令是均勻分布在后地址部分。2.將指令序列變換成為頁地址流：設(shè)頁面大小為1K；用戶內(nèi)存容量為4頁到32頁；用戶虛存容量為32K。在用戶虛存中，按每K存放10條指令排列虛存地址，即320條指令在虛存中的存放方式為：第0條至第9條指令為第0頁；第1

2、0條至19條指令為第1頁；第310條至319條指令為第31頁。3.計(jì)算并輸出下述各種算法在不同內(nèi)存容量下的命中率。(1) 先進(jìn)先出算法（FIFO） (2) 最近最少使用算法（LRU）(3) 最佳使用算（OPT） 命中率頁面失效次數(shù)頁地址流長度本實(shí)驗(yàn)中，頁地址流長度為320，頁面失效次數(shù)為每次訪問相應(yīng)指令時(shí)，該指令所對應(yīng)的頁不在內(nèi)存的次數(shù)。實(shí)驗(yàn)思路：關(guān)于隨機(jī)數(shù)的產(chǎn)生辦法，首先要初始化設(shè)置隨機(jī)數(shù)，產(chǎn)生序列的開始點(diǎn)，可通過下列語句實(shí)現(xiàn)： srand ( 400 ) ； (1) 計(jì)算隨機(jī)數(shù)，產(chǎn)生320條指令序列 m160；for (i0；i80；i+ ji4； ajm； aj+1m+1； aj+2aj

3、 1.0 rand( )/32767； aj+3aj+2+1 maj+3+(319-aj+3) 1.0rand( )/32767； (2) 將指令序列變換成為頁地址流 for ( k0；k320；k+) ptak/10； pd= ak%10； (3) 計(jì)算不同算法的命中率 rate1-1.0U/320 ； 其中U為缺頁中斷次數(shù)，320是頁地址流長度。 (4) 輸出格式 k fifo 1ru 4 0.23 0.25 32 1.0 1.0實(shí)驗(yàn)內(nèi)容：實(shí)現(xiàn)程序：主要的數(shù)據(jù)結(jié)構(gòu)：void build();int searchpb();int searchpro();void Optimal();void

4、 FIFO();void LRU();void empty();void main();主程序:#include<stdio.h>#include<stdlib.h>#include<string.h>#define bsize 4 /物理塊大小#define psize 16 /進(jìn)程大小int phbbsize=0; /物理塊標(biāo)號int propsize=0; /進(jìn)程序列號int flagbsize = 0; /進(jìn)程等待次數(shù)(存放最久未被使用的進(jìn)程標(biāo)志)int i = 0, j = 0,k = 0; /i表示進(jìn)程序列號,j表示物理塊號int m = -1,

5、 n = -1; /物理塊空閑和進(jìn)程是否相同判斷標(biāo)志int max = -1,maxflag = 0; /標(biāo)記替換物理塊進(jìn)程下標(biāo)int count = 0; /統(tǒng)計(jì)頁面缺頁次數(shù)/隨機(jī)產(chǎn)生序列號函數(shù)void build()printf("隨機(jī)產(chǎn)生一個(gè)進(jìn)程序列號為：n");int i = 0; for(i=0; i<psize; i+) proi = 10*rand()/(RAND_MAX+1)+1; printf("%d ",proi); printf("n");/查找空閑物理塊int searchpb()for(j=0; j&l

6、t;bsize; j+) if(phbj = 0) m = j; return m; break; return -1;/查找相同進(jìn)程int searchpro()for(j = 0; j < bsize; j+) if(phbj = proi) n = j; return j; return -1;/初始化內(nèi)存void empty()for(i=0;i<bsize;i+)phbi=0; count=0; /計(jì)數(shù)器置零/先進(jìn)先出頁面置換算法void FIFO() for(i = 0; i<psize; i+) m=searchpb(); n=searchpro();/找fla

7、g值最大的 for(j = 0; j < bsize;j+) if(flagj>maxflag) maxflag = flagj; max = j; if(n = -1) /不存在相同進(jìn)程 if(m != -1) /存在空閑物理塊 phbm = proi; /進(jìn)程號填入該空閑物理塊 count+; flagm = 0; for(j = 0;j <= m; j+) flagj+; m = -1; else /不存在空閑物理塊 phbmax = proi; flagmax = 0; for(j = 0;j < bsize; j+) flagj+; max = -1; max

8、flag = 0; count+; else /存在相同的進(jìn)程 phbn = proi; for(j = 0;j < bsize; j+) flagj+; n = -1; for(j = 0 ;j < bsize; j+) printf("%d ",phbj); printf("n"); printf("缺頁次數(shù)為：%dn",count);printf("n");/主函數(shù)*void main()int sel;do printf("ttt-ttt");printf("ttt

9、 -歡迎進(jìn)入操作系統(tǒng)界面- ttt");printf("ttt-tttn");printf("tttttt"); printf("ttt 虛擬內(nèi)存 ttt");printf("ttt-ttt"); printf("ttt 1、產(chǎn)生隨機(jī)序列 ttt");printf("ttt-ttt"); printf("ttt 2、最佳置換算法(OPT) ttt");printf("ttt-ttt"); printf("ttt 3、

10、先進(jìn)先出(FIFO) ttt");printf("ttt-ttt"); printf("ttt 4、最久未使用(LRU) ttt");printf("ttt-ttt");printf("ttt 5、三種算法的比較 ttt");printf("ttt-ttt");printf("ttt 0、退出(Exit) ttt"); printf("ttttttn"); printf("請選擇所要執(zhí)行的操作(0/1/2/3/4/5):");

11、 scanf("%d",&sel); switch(sel) case0:printf("ttt-再見！- tttn");system("pause");break; case 1:build();break; case 2:printf(最佳置換算法n");Optimal();empty();break; case 3:printf("先進(jìn)先出算法n");FIFO();empty();break; case 4:printf("最久未使用算法n");LRU();empty()

12、;break; case 5: printf("最佳置換算法n");Optimal();empty();printf("先進(jìn)先出算法n");FIFO();empty();printf("最久未使用算法n");LRU();empty();break;default: printf("請輸入正確的選項(xiàng)號！");printf("nn");break;while(sel!=0);實(shí)驗(yàn)結(jié)果：圖1圖2圖3實(shí)驗(yàn)總結(jié)：1請求頁式存儲管理的實(shí)現(xiàn)原理：請求分頁虛擬存儲管理是將進(jìn)程信息的副本存放在副主存儲器中，當(dāng)它被

13、調(diào)度投入運(yùn)行時(shí)，并不把程序和數(shù)據(jù)全部裝入主存，僅裝入當(dāng)前使用的頁面，進(jìn)程執(zhí)行過程中訪問不在主存的頁面時(shí)，再把所需信息動態(tài)地裝入。當(dāng)需要執(zhí)行某條指令或使用某個(gè)數(shù)據(jù)而發(fā)現(xiàn)他們不在主存時(shí)，產(chǎn)生缺頁異常，系統(tǒng)從磁盤中把此指令或數(shù)據(jù)所在的頁面裝入，保證用不到的頁面不會被裝入主存。2寫出這三種頁面置換算法的實(shí)現(xiàn)思想。(1) 最佳置換算法(OPT):當(dāng)要調(diào)入一頁而必須淘汰舊頁時(shí)應(yīng)該淘汰以后不再訪問的頁或距現(xiàn)在最長時(shí)間后要訪問的頁面。(2) 先進(jìn)先出(FIFO):基于程序總是按線性順序來訪問物理空間這一假設(shè)，總是淘汰最先調(diào)入主存的頁面，即淘汰在主存中駐留時(shí)間最長的頁面，認(rèn)為駐留時(shí)間最長的頁不再使用的可能性較大。(3) 最久未使用(LRU):最近最少使用頁面替換算法淘汰的頁面是在最近一段時(shí)間內(nèi)最久未被訪問的那一頁，基于程序的局部性原理來考慮，認(rèn)為那些剛被使用過的頁面可能還要立即被使用，而那些在較長時(shí)間內(nèi)未被使用的頁面可能不會立即使用。3對不同算法的性能進(jìn)行評價(jià)。(1) 最佳置換算法(OPT): 這種算法產(chǎn)生的缺頁數(shù)最少，卻