1、實驗報告實驗八實驗名稱：存儲管理模擬實驗目的：1 .掌握請求分頁存儲管理系統(tǒng)的基本原理2 .實現(xiàn)一個模擬的虛擬分頁存儲管理系統(tǒng)實驗要求：編寫一個程序，模擬一個虛擬分頁存儲管理系統(tǒng)。其中，由系統(tǒng)隨機產(chǎn)生進程；進程大小、進程到達次序、時間、進程執(zhí)行軌跡（頁面訪問順序）也隨機生成，但進程之間必須有并發(fā)存在，進程執(zhí)行時間需有限，進程調(diào)度采用時間片輪轉(zhuǎn)算法（以頁面模擬）；rss駐留集大小物理塊分配策略采取固定分配局部置換；分配算法采用按比例分配算法；調(diào)頁采用請求調(diào)頁方式；置換分別采用FIFO、LRU（一直沒用）訪問次數(shù)和簡單CLOCK算法（循環(huán)鏈表）標志有沒有被訪問；駐留集大小可調(diào)，觀察駐留集大小對缺頁

2、率的影響。算法思想：FIFO先進先出法LRU最久未使用算法CLOCK簡單時鐘算法命中率=1一頁面失效次數(shù)/頁地址流（序列）長度駐留集大小可調(diào)，觀察駐留集大小對缺頁率的影響。結(jié)構(gòu)體定義單位時間訪問次數(shù)頁框號上次訪問時間頁面號頁面控制結(jié)構(gòu)頁框號指針頁面控制表表結(jié)構(gòu)包含鏈表：空閑頁面表忙頁面表包含數(shù)組：進程數(shù)組頁面號數(shù)組是否完成?頁號在物理塊內(nèi)？引用塊編號:于物理塊?分配物理塊流程圖隨機得到進程指令序列開始為其分配頁號是選才iFIFOLRUCLOCK置換算法置換結(jié)束實驗結(jié)果分析：觀察數(shù)據(jù)可看出：橫向：三種替換算法的命中率由高到底排列應該是LRU>CLOCK>FIFO縱向：進程的駐留級越大

3、，其缺頁率就越低。5*190661牙J69B3DD.匕1.12311rifidliMtruCElNHquetie-*.強191判號17ivntv;竄cBeQMthQkriaJbuHtu:-5./A2ST12117>織上墀17717S2542555529?212?1ST4743的644445312311上G卻¥9110加2131打12f3g求IF2Z1Z2931L123124conparethethreemethods:FIFOLRUCLOCK35960,5060.5060.52Z0,5220,5192*5470.5410.5470.5560*55(504553645750.57

4、2645780.5810.597e.5910.5919.6060,6000.6090.6160.6160.616CL6280.6220*6470.6370*6440*G590.4530*O5&9.6660.6660,672日*6780+672Qt67G0.7130.69704703.7190.713047220.7440*7190t7O90.7690,7220.7470.7720.744CL769Q.7S10.7720.7810.7&40.7940.7910.8228.8960.7940.8220,8190,8220+825CL841Q+825.8660.8530*8340.S

5、6&®8590*8590.8668.8668.8690,8790,8Q40,834O+90OU.8948.9004567890123456789011111111112實驗體會:1 .內(nèi)存中進程的多少會影響駐留集大小和缺頁中斷率。如果內(nèi)存中進程太多，將導致每個進程的駐留集太小，發(fā)生缺頁中斷的概率很大。相應地，系統(tǒng)發(fā)生抖動的可能性就會很大。如果在內(nèi)存中保持太少的活動進程，那么所有活動進程同時處于阻塞狀態(tài)的可能性就會很大，從而降低處理機的利用率。2 .置換算法的好壞將直接影響系統(tǒng)的性能，不適當?shù)闹脫Q算法可能導致系統(tǒng)出現(xiàn)“抖動現(xiàn)象。常用的頁面置換算法：最佳置換算法、最近最少使用算法

6、、先進先出算法和時鐘算法等。最佳置換算法難以實現(xiàn)但可以成為核對其他算法的標準。3 .也應注意負載問題，解決系統(tǒng)應當保持多少個活動進程駐留在內(nèi)存的問題，即控制多道程序系統(tǒng)的度。當內(nèi)存中的活動進程數(shù)太少時，負載控制將增加新進程或激活一些掛起進程進入內(nèi)存；反之，當內(nèi)存中的進程數(shù)太多時，負載控制將暫時掛起一些進程，減少內(nèi)存中的活動進程數(shù)。實驗代碼：#include<stdio.h>#include<stdlib.h>#include<unistd.h>#include<string.h>#defineTRUE1#defineFALSE0#defineIN

7、VALID-1#definetotal_instruction320#definetotal_vp32#defineclear_period50typedefstructintpn,pfn,counter,time;pl_type;pl_typepltotal_vp;structpfc_structintpn,/pfn;structpfc_struct*next;/;typedefstructpfc_structpfc_type;pfc_typepfctotal_vp,/指令流長/頁長/頁面結(jié)構(gòu)/頁面序號/頁面所在內(nèi)存區(qū)的頁框號/單位時間內(nèi)訪問次數(shù)/上次訪問的時間/頁面結(jié)構(gòu)數(shù)組/頁面控制結(jié)構(gòu)頁

8、面號/內(nèi)存區(qū)頁面的頁框號頁面指針，用于維護內(nèi)存緩沖區(qū)的鏈式結(jié)構(gòu)/主存區(qū)頁面控制結(jié)構(gòu)別名/主存區(qū)頁面控制結(jié)構(gòu)數(shù)組*freepf_head,*busypf_head,*busypf_tail;intdiseffect;誤intatotal_instruction;intpagetotal_instruction;intoffsettotal_instruction;intinitialize(int);intFIFO(int);intLRU(int);intCLOCK(int);intmain()ints;/隨機數(shù)/主存區(qū)頁面控制結(jié)構(gòu)的空閑頁面頭指針/主存區(qū)頁面控制結(jié)構(gòu)的忙頁面頭指針/主存區(qū)頁面控

9、制結(jié)構(gòu)的忙頁面尾指針/頁錯誤計數(shù)器，初次把頁面載入主存時也當做頁錯/隨即指令流數(shù)組/指令對應的頁面號/指令所在頁面中的偏移量/初始化頁面結(jié)構(gòu)數(shù)組和頁面控制結(jié)構(gòu)數(shù)組/先進先出算法/最近最久未使用算法/簡單時鐘(鐘表)算法inti;"種子srand(10*getpid();/*每次運行時進程號不同，用來作為初始化隨機數(shù)隊列的"*/s=(int)(float)(total_instruction-1)*(rand()/(RAND_MAX+1.0);printf("nrandinstructionsqueuen");for(i=0;i<total_inst

10、ruction;i+=4)/產(chǎn)生指令隊列ai=s;/任選一指令訪問點mai+1=ai+1;/順序執(zhí)行一條指令ai+2=(int)(float)ai*(rand()/(RAND_MAX+1.0);執(zhí)行前地址指令m'ai+3=ai+2+1;順序執(zhí)行一條指令printf("%6d%6d%6d%6dn",ai,ai+1,ai+2,ai+3);s=(int)(float)(total_instruction-1)-ai+2)*(rand()/(RAND_MAX+1.0)+ai+2;printf("n");for(i=0;i<total_instruc

11、tion;i+)/將指令序列變換成頁地址流pagei=ai/10;offseti=ai%10;printf("comparethethreemethods:");printf("nn");printf("RsstFIFOtLRUtCLOCK'n");for(i=4;i<=32;i+)/用戶內(nèi)存工作區(qū)從4個頁面到32個頁面printf("%2dt",i);FIFO(i);LRU(i);CLOCK(i);printf("n");)return0;)/初始化頁面結(jié)構(gòu)數(shù)組和頁面控制結(jié)構(gòu)數(shù)組

12、/total_pf;用戶進程的內(nèi)存頁面數(shù)intinitialize(inttotal_pf)inti;diseffect=0;for(i=0;i<total_vp;i+)pli.pn=i;pli.pfn=INVALID;存中pli.counter=0;pli.time=-1;)for(i=0;i<total_pf-1;i+)pfci.next=&pfci+1;pfci.pfn=i;)pfctotal_pf-1.next=NULL;pfctotal_pf-1.pfn=total_pf-1;freepf_head=&pfc0;/置頁面所在主存區(qū)的幀號為-1.表示該頁不在

13、主/置頁面結(jié)構(gòu)中的訪問次數(shù)為0/置頁面結(jié)構(gòu)中的上次訪問的時間為-1/建立pfci-1和pfci之間的鏈接/初始化主存區(qū)頁面的頁框號/主存區(qū)頁面控制結(jié)構(gòu)的空閑頁面頭指針指向pfc0return0;/最近最久未使用算法/inttotal_pf;用戶進程的內(nèi)存頁面數(shù)intLRU(inttotal_pf)intMinT;intMinPn;inti,j;intCurrentTime;initialize(total_pf);數(shù)組/最小的訪問時間，即很久沒被訪問過/擁有最小的訪問時間的頁的頁號/系統(tǒng)當前時間/初始化頁面結(jié)構(gòu)數(shù)組和頁面控制結(jié)構(gòu)CurrentTime=0;diseffect=0;for(i=0

14、;i<total_instruction;i+)/頁面失效if(plpagei.pfn=INVALID)diseffect+;if(freepf_head=NULL)/頁錯誤次數(shù)加無空閑頁面/找出time的最小值，表明該頁很MinT=100000;for(j=0;j<total_vp;j+)久沒被訪問過if(MinT>plj.time&&plj.pfn!=INVALID)MinT=plj.time;MinPn=j;)freepf_head=&pfcplMinPn.pfn;plMinPn.pfn=INVALID;/最久沒被訪問過的頁被釋放/最久沒被訪問過

15、的頁被換出主plMinPn.time=-1;/最久沒被訪問過的頁的訪問時間置為無效freepf_head->next=NULL;主存，并把)plpagei.pfn=freepf_head->pfn;pfn改為相應的頁框號plpagei.time=CurrentTime;freepf_head=freepf_head->next;/有空閑頁面，把相應的頁面換入/令訪問時間為當前系統(tǒng)時間/減少一個空閑頁面)/命中則刷新該單元的訪問時間/系統(tǒng)當前時間加elseplpagei.time=CurrentTime;CurrentTime+;)printf("%6.3付”,1-(

16、float)diseffect/320);return0;)/簡單時鐘算法/inttotal_pf;用戶進程的內(nèi)存頁面數(shù)intCLOCK(inttotal_pf)inti;/使用位intusetotal_vp;intswap;swap=0;/發(fā)生替換initialize(total_pf);pfc_type*pnext;/時鐘指針pfc_type*head;/隊列頭指針/初始化使用位為/頁面失效，不在主存中/頁錯誤次數(shù)加/無空閑頁面pnext=freepf_head;head=freepf_head;for(i=0;i<total_vp;i+)usei=0;diseffect=0;for

17、(i=0;i<total_instruction;i+)if(plpagei.pfn=INVALID)diseffect+;if(freepf_head=NULL)while(usepnext->pfn=1)/若時鐘指針指向的頁的使用位為，則改為并跳過usepnext->pfn=0;pnext=pnext->next;if(pnext=NULL)pnext=head;/如果時鐘指針到達隊列尾部，重新返回頭部/換出被替換的頁plpnext->pn.pfn=INVALID;swap=1;/頁面結(jié)構(gòu)中要標記頁框號/頁面控制結(jié)構(gòu)中要標記頁號/重置使用位為/時鐘指針下移/如

18、果時鐘指針到達隊列尾部,if(usepnext->pfn=0)/如果使用便為，則換入相應的頁plpagei.pfn=pnext->pfn;pnext->pn=pagei;usepnext->pfn=1;pnext=pnext->next;if(pnext=NULL)pnext=head;重新返回頭部if(swap=0)freepf_head=freepf_head->next;else/頁面在主存中useplpagei.pfn=1;/刷新使用位為)printf("%6.3ft",1-(float)diseffect/320);return0;/先進先出算法版本/inttotal_pf;用戶進程的內(nèi)存頁面數(shù)/實現(xiàn)細節(jié)由CLOCK算法退化而來，與FIFO同效果intFIFO(inttotal_pf)inti;intusetotal_vp;intswap=0;initialize(total_pf);pfc_