1、蘭州大學(xué)操作系統(tǒng)實(shí)驗(yàn)八存儲(chǔ) 管理模擬題目和答案-實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)八實(shí)驗(yàn)名稱：存儲(chǔ)管理模擬實(shí)驗(yàn)?zāi)康模?掌握請求分頁存儲(chǔ)管理系統(tǒng)的基本原理.實(shí)現(xiàn)一個(gè)模擬的虛擬分頁存儲(chǔ)管理系統(tǒng) 實(shí)驗(yàn)要求：編寫一個(gè)程序，模擬一個(gè)虛擬分頁存儲(chǔ)管理系 統(tǒng)。其中，由系統(tǒng)隨機(jī)產(chǎn)生進(jìn)程；進(jìn)程大小、進(jìn)程到達(dá)次序、時(shí)間、進(jìn)程執(zhí)行軌 跡（頁面訪問順序）也隨機(jī)生成，但進(jìn)程之間 必須有并發(fā)存在，進(jìn)程執(zhí)行時(shí)間需有限，進(jìn)程 調(diào)度采用時(shí)間片輪轉(zhuǎn)算法（以頁面模擬）；rss 駐留集大小物理塊分配策略采取固定分配局 部置換；分配算法采用按比例分配算法；調(diào)頁 采用請求調(diào)頁方式；置換分別采用FIFO、LRU（ 一直沒用）訪問次數(shù) 和簡單CLOCK算

2、 法（循環(huán)鏈表）標(biāo)志 有沒有被訪問； 駐留集大小可調(diào)，觀察駐留集大小對缺頁率的 影響。算法思想：FIFO先進(jìn)先出法LRU最久未使用算法CLOCK簡單時(shí)鐘算法命中率=1 -頁面失效次數(shù)/頁地址流（序列）長度駐留集大小可調(diào)，觀察駐留集大小對缺頁率的影 響。結(jié)構(gòu)體定義頁面序號(hào)頁頁框號(hào)頁框號(hào)包含鏈表：空閑頁面表 忙頁面表包含數(shù)組：進(jìn)程數(shù)組頁面號(hào)數(shù)組流程圖:開始引用塊否C頁號(hào)在/ 是是選擇 FIFO LRU CLOCK結(jié)束實(shí)驗(yàn)結(jié)果分析：觀察數(shù)據(jù)可看出：橫向：三種替換算法的命中率 由高到底排列應(yīng)該是 LRUCLOCKFIFO 。縱向：進(jìn)程的駐留級越大，其缺頁率就越低息tngkxqa1biiotLi ：_/

3、香|atnstructlonSb 利e3$砧州 211恰16931321S141幅 2721t3J 3B2舞21729301B1ias1611ine i1必133iM 77262ZM ZS12499IK 163177171M X151154H 54176IS 11421U 61;21227575029a2912M 之日寫362ii lit粉7M2m i2i，濫22617717H2542552 豳29792122107let42*3S1M AS3123132&Z2E3JSft州。m no31251Sm i213D6-JOTZZfl Z29311312123124compare the three

4、 methods:RssFIFOLRU40,5660,50650.522O.SZZ60.547 .5417白.5550.S5680*5750,572gCL 5810,597100.5910 . 606110*6690.616129.6150,628130.5470,637140.6590.653150.(56016046780.672170,7130,697180.7190.713190.7440.71920047090.722210*7720,744220.7810.77223CL 784CL 794243.8220.806Z504819260.8250.841270.866Q + 8532

5、80.8660.859290.8650.865300.87rB0,684310.9090 . 894320 . 9006.960CLOCK O,50G .519 0.547 6.553 6,578 0 + 591 0.600 6.616 0*622 0.644 0.656 04672 0.6780,7030,722%Fl、77G d9-T i丸,7T,6r9,781隊(duì)、7919.0.9,B,7,8,8,8Q9223 c4Z54Q d3,3. B,0.,Q ,8 ，呼 ,96& 06J940實(shí)驗(yàn)體會(huì)：.內(nèi)存中進(jìn)程的多少會(huì)影響駐留集大小和缺頁中斷率。如果內(nèi)存中進(jìn)程太多，將導(dǎo)致每個(gè)進(jìn) 程的駐留集太小

6、，發(fā)生缺頁中斷的概率很 大。相應(yīng)地，系統(tǒng)發(fā)生抖動(dòng)的可能性就會(huì)很 大。如果在內(nèi)存中保持太少的活動(dòng)進(jìn)程， 那么所有活動(dòng)進(jìn)程同時(shí)處于阻塞狀態(tài)的可能性 就會(huì)很大，從而降低處理機(jī)的利用率。.置換算法的好壞將直接影響系統(tǒng)的性能，不適當(dāng)?shù)闹脫Q算法可能導(dǎo)致系統(tǒng)出現(xiàn)“抖動(dòng)”現(xiàn)象。常用的頁面置換算法：最佳置換算法、最近最 少使用算法、先進(jìn)先出算法和時(shí)鐘算法等。最 佳置換算法難以實(shí)現(xiàn)但可以成為核對其他算 法的標(biāo)準(zhǔn)。.也應(yīng)注意負(fù)載問題，解決系統(tǒng)應(yīng)當(dāng)保持多少個(gè) 活動(dòng)進(jìn)程駐留在內(nèi)存的問題，即控制多道程序 系統(tǒng)的度。當(dāng)內(nèi)存中的活動(dòng)進(jìn)程數(shù)太少時(shí)，負(fù) 載控制將增加新進(jìn)程或激活一些掛起進(jìn)程進(jìn) 入內(nèi)存；反之，當(dāng)內(nèi)存中的進(jìn)程數(shù)太多時(shí)

7、，負(fù) 載控制將暫時(shí)掛起一些進(jìn)程，減少內(nèi)存中的活 動(dòng)進(jìn)程數(shù)。實(shí)驗(yàn)代碼：#include #include #include #include #define TRUE 1#define FALSE 0 #define INVALID -1#define total_instruction 320 指令流長#define total_vp 32#define clear_periodtypedef struct構(gòu)int pn, pfn,內(nèi)存區(qū)的頁框號(hào)counter, time;pl_type;pl_type pltotal_vp;頁長50頁面結(jié)構(gòu)數(shù)組struct pfc_struct制結(jié)構(gòu)int

8、pn, pfn;struct pfc_struct *next;頁面序號(hào)頁面所在單位時(shí)間內(nèi)訪問次數(shù)上次訪問的時(shí)間頁面結(jié)頁面控頁面號(hào)內(nèi)存區(qū)頁面的頁框號(hào)頁面指針，用于維護(hù)內(nèi)存緩沖區(qū)的鏈?zhǔn)浇Y(jié)構(gòu);typedef struct pfc_struct pfc_type;主存區(qū)頁面控制結(jié)構(gòu)別名pfc_type pfctotal_vp,制結(jié)構(gòu)數(shù)組*freepf_head,構(gòu)的空閑頁面頭指針*busypf_head,構(gòu)的忙頁面頭指針*busypf_tail;構(gòu)的忙頁面尾指針主存區(qū)頁面控主存區(qū)頁面控制結(jié)主存區(qū)頁面控制結(jié)主存區(qū)頁面控制結(jié)頁錯(cuò)誤計(jì)數(shù)器，初int diseffect;次把頁面載入主存時(shí)也當(dāng)做頁錯(cuò)誤int

9、 atotal_instruction;int pagetotal_instruction;號(hào)int offsettotal_instruction;中的偏移量int initialize(int);隨即指令流數(shù)組指令對應(yīng)的頁面指令所在頁面初始化頁面結(jié)構(gòu)數(shù)int FIFO(int);先進(jìn)先出算法組和頁面控制結(jié)構(gòu)數(shù)組intLRU(int);最近最久未使用算法int CLOCK(int);簡單時(shí)鐘(鐘表)算法int main()int s; 隨機(jī)數(shù)int i;srand(10*getpid(); /*每次運(yùn)行時(shí)進(jìn)程號(hào)不 同，用來作為初始化隨機(jī)數(shù)隊(duì)列的種子*/s=(int)(float)(total

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

11、ai+2)*(rand()/ (RAND_MAX+1.0) + ai+2;printf(n);for (i=0;itotal_instruction;i+)將指令序列變換成頁地址流pagei=ai/10;offseti=ai%10;printf(compare the three methods:);printf(nn);printf( Rsst FIFOt LRUt CLOCKn); for(i=4;i=32;i+) 用戶內(nèi)存工作區(qū)從 4 個(gè)頁面到32個(gè)頁面printf( %2d t,i);FIFO(i)；LRU(i);CLOCK(i);printf(n);return 0;初始化頁面結(jié)構(gòu)數(shù)

12、組和頁面控制結(jié)構(gòu)數(shù)組/total_pf;用戶進(jìn)程的內(nèi)存頁面數(shù)int initialize(int total_pf)int i;diseffect=0;for(i=0;itotal_vp;i+)pli.pn=i;pli.pfn=INV ALID;置頁面所在主存區(qū)的幀號(hào)為-1.表示該頁不在主存中pli.counter=0;置頁面結(jié)構(gòu)中的訪問次數(shù)為0pli.time=-1;置頁面結(jié)構(gòu)中的上次訪問的時(shí)間為-1for(i=0;itotal_pf-1;i+)pfci.next=&pfci+1; 建立 pfci-1和 pfci之間的鏈接pfci.pfn=i;初始化主存區(qū)頁面的頁框號(hào)pfctotal_pf-

13、1.next=NULL;pfctotal_pf-1.pfn=total_pf-1;fre叩f_head=&pfc0;/主存區(qū)頁面控制結(jié)構(gòu)的空閑頁面頭指針指向pfc0return 0;最近最久未使用算法/int total_pf;用戶進(jìn)程的內(nèi)存頁面數(shù)int LRU (int total_pf) int MinT;最小的訪問時(shí)間，即很久沒被訪問過int MinPn;擁有最小的訪問時(shí)間的頁的頁號(hào)int i,j；int CurrentTime;/ 系統(tǒng)當(dāng)前時(shí)間initialize(total_pf);初始化頁面結(jié)構(gòu)數(shù)組和頁面控制結(jié)構(gòu)數(shù)組CurrentTime=0;diseffect=0;for(i=0

14、;itotal_instruction;i+)if(plpagei.pfn=INV ALID)頁面失效diseffect+;/頁錯(cuò)誤次數(shù)加if(freepf_head=NULL)無空閑頁面MinT=100000;for(j=0;jplU.time&plj.pfn!=INV ALID) MinT=plj.time; MinPn=j; freepf_head=&pfcplMinPn.pfn;最久沒被訪問過的頁被釋放plMinPn.pfn=INV ALID;/最久沒被訪問過的頁被換出主存plMinPn.time=-1;最久沒被訪問過的頁的訪問時(shí)間置為無效 freepf_head-next=NULL;

15、 plpagei.pfn=freepf_head-pfn;有空閑頁面，把相應(yīng)的頁面換入主存，并把 pfn 改為相應(yīng)的頁框號(hào)plpagei.time=CurrentTime;令訪問時(shí)間為當(dāng)前系統(tǒng)時(shí)間freepf_head=freepf_head-next;減少一個(gè)空閑頁面elseplpagei.time=CurrentTime;命中則刷新該單元的訪問時(shí)間CurrentTime+;系統(tǒng)當(dāng)前時(shí)間加printf(%6.3ft”,1-(float)diseffect/320);return 0;簡單時(shí)鐘算法/int total_pf;用戶進(jìn)程的內(nèi)存頁面數(shù)int CLOCK(int total_pf)in

16、t i;int usetotal_vp;使用位int swap;swap=0;發(fā)生替換initialize(total_pf);pfc_type *pnext; 時(shí)鐘指針pfc_type *head;隊(duì)列頭指針pnext=freepf_head;head=freepf_head;for(i=0;itotal_vp;i+)usei=0;初始化使用位為diseffect=0;for(i=0;ipfn=1) 若時(shí)鐘指針指向的頁的使用位為，則改為并跳過usepnext-pfn=0;pnext=pnext-next;if(pnext=NULL) pnext=head; /如果時(shí)鐘指針到達(dá)隊(duì)列尾部，重新返

17、回頭部換出被替換的頁plpnext-pn.pfn=INV ALID;swap=1;if(usepnext-pfn=0) 如果使用位為，則換入相應(yīng)的頁plpagei.pfn=pnext-pfn;頁面結(jié)構(gòu)中要標(biāo)記頁框號(hào)pnext-pn=pagei;/頁面控制結(jié)構(gòu)中要標(biāo)記頁號(hào)usepnext-pfn=1;重置使用位為pnext=pnext-next;/ 時(shí) 鐘 指針下移if(pnext=NULL) pnext=head; / 如果時(shí)鐘指針到達(dá)隊(duì)列尾部，重新返回頭部if(swap=0) freepf_head=freepf_head-next;else頁面在主存中useplpagei.pfn=1;刷新

18、使用位為printf(%6.3ft”,1-(float)diseffect/320);return 0;先進(jìn)先出算法版本/int total_pf;用戶進(jìn)程的內(nèi)存頁面數(shù)實(shí)現(xiàn)細(xì)節(jié)由CLOCK算法退化而來，與FIFO 同效果int FIFO(int total_pf)int i;int usetotal_vp;int swap=0;initialize(total_pf);pfc_type *pnext,*head;pnext=freepf_head;head=freepf_head;for(i=0;itotal_vp;i+)usei=0;diseffect=0;for(i=0;ipfn=1)usepnext-pfn=0;pnext=pnext-next;if(pnext=NULL) pnext=hea