OS實(shí)驗(yàn)4(DOC)

1、實(shí)驗(yàn)四 存儲(chǔ)管理實(shí)驗(yàn)內(nèi)容一、分區(qū)存儲(chǔ)管理模擬二、請(qǐng)求頁(yè)式存儲(chǔ)管理模擬注：以上內(nèi)容任選其一， 運(yùn)行環(huán)境、 開(kāi)發(fā)工具不限實(shí)驗(yàn)學(xué)時(shí)：2+2學(xué)時(shí)實(shí)驗(yàn)性質(zhì)：綜合設(shè)計(jì)性一、分區(qū)存儲(chǔ)管理模擬【實(shí)驗(yàn)?zāi)康摹吭O(shè)計(jì)一個(gè)虛擬內(nèi)存工作區(qū)，并使用下述算法分配回收 內(nèi)存。1)最先適應(yīng)分配算法(First Fit)2)最差適應(yīng)分配算法(Worst Fit)3)最佳適應(yīng)分配算法( Best Fit)二、請(qǐng)求頁(yè)式存儲(chǔ)管理模擬【實(shí)驗(yàn)?zāi)康摹?設(shè)計(jì)一個(gè)虛擬存儲(chǔ)區(qū)和內(nèi)存工作區(qū)，并使用下述算法 計(jì)算訪(fǎng)問(wèn)命中率。（1）（2）（3）（4）（5）命中率=先進(jìn)先出的算法（FIFO） 最近最久未用算法（LRU） 最近最不經(jīng)常使用算法（NUR）*最佳

2、淘汰算法（OPT）*最少訪(fǎng)問(wèn)頁(yè)面算法（LFU）* 1-頁(yè)面失效次數(shù)/頁(yè)面地址流長(zhǎng)度程序設(shè)計(jì)中，首先用Srand（）和Rand（）函數(shù)定義和產(chǎn) 生指令序列，然后將指令序列變換成相應(yīng)的頁(yè)地址 流，針對(duì)不同的算法計(jì)算出相應(yīng)的命中率。報(bào)告格式：統(tǒng)一封皮（學(xué)院統(tǒng)一格式）（）（一頁(yè)）目錄（一頁(yè)）實(shí)驗(yàn)題目實(shí)驗(yàn)要求（一頁(yè)）正文（另起一頁(yè)）一、方案設(shè)計(jì)（技術(shù)方案、功能設(shè)計(jì)）二、結(jié)構(gòu)設(shè)計(jì)1、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)2、程序結(jié)構(gòu)設(shè)計(jì)（主函數(shù)、 子函數(shù)結(jié)構(gòu)設(shè)計(jì)或類(lèi)結(jié)構(gòu)設(shè)計(jì)）三、程序設(shè)計(jì)程序流程 （方法或函數(shù)流程）四、編碼調(diào)試（主要問(wèn)題及其解決辦法）五、實(shí)驗(yàn)總結(jié)六、程序清單（如程序太長(zhǎng)，只附關(guān)鍵代碼）排版要求:標(biāo)題 黑體四號(hào) 居左

3、正文 宋體五號(hào) 首行縮進(jìn)請(qǐng)求頁(yè)式存儲(chǔ)管理模擬參考代碼數(shù)據(jù)結(jié)構(gòu)】(1) 頁(yè)面類(lèi)型 typedef struct int pn pfn,counter ,time;pl-type;其中 pn 為頁(yè)號(hào)， pfn 為一個(gè)周期內(nèi)訪(fǎng)問(wèn)該頁(yè)面的次數(shù)， time 為訪(fǎng)問(wèn)時(shí)間。2) 頁(yè)面控制結(jié)構(gòu)pfc_structint pn,pfn;struct pfc_struct *next;typedef struct pfc_struct pfc_type;pfc_type pfctotle_vp, freepf_heed ,*busypf_head;pfc_type *busypf_tail;freepf_heed

4、 為空頁(yè)面頭的指針，busypf_head 為忙頁(yè)面頭的指針，busypf_tail 為忙頁(yè)面尾的指針。3) 函數(shù)定義1)void initialize( ):初始化函數(shù)，給每個(gè)相關(guān)的網(wǎng)頁(yè)賦值。2) void FIFO(): 計(jì)算使用 FIFO 算法時(shí)的命中率。3) void LRU(): 計(jì)算使用 LRU 算法時(shí)的命中率。4) void OPT():計(jì)算使用 OPT 算法時(shí)的命中率。5) void LFU():計(jì)算使用 LFU 算法時(shí)的命中率。6) void NUR():計(jì)算使用 NUF 算法時(shí)的命中率。4)變量定義1) int atotal_instruction:指令流數(shù)據(jù)組。2) in

5、t pagetotal_instruction:每條指令所屬頁(yè)號(hào)。3) int offsettotal_instruction:每頁(yè)裝入 10 條指令后取模運(yùn)算頁(yè)號(hào)偏移值。4) int total_pf:用戶(hù)進(jìn)程的內(nèi)存頁(yè)面數(shù)。5) int disaffect:頁(yè)面失效次數(shù)?！緟⒖汲绦颉?include #include #include #define TRUE 1 #define FALSE 0其中 pfctotle_vp定義用戶(hù)進(jìn)程虛頁(yè)控制結(jié)構(gòu)，#define INVALID -1#define NULL 0#define total_instruction 320#define tota

6、l_vp 32#define clear_period 50typedef struct /int pn,pfn,counter,time; /pnpl_type;pl_type pltotal_vp;struct pfc_struct /int pn,pfn;struct pfc_struct *next;typedef struct pfc_struct pfc_type;/ 指令流長(zhǎng) / 虛頁(yè)長(zhǎng) / 清零周期頁(yè)面類(lèi)型是頁(yè)號(hào)， pfn 是頁(yè)面號(hào)， counter 是 個(gè)周期內(nèi)訪(fǎng)問(wèn)頁(yè)面次數(shù)， time 為訪(fǎng)問(wèn)時(shí)間/ 頁(yè)面結(jié)構(gòu)數(shù)組頁(yè)面控制結(jié)構(gòu)pfc_type pfctotal_vp,*free

7、pf_head,*busypf_head,*busypf_tail;int diseffect;/ pfctotal_vp 定義用戶(hù)進(jìn)程虛頁(yè)面控制結(jié)構(gòu)/*freepf_head 為空頁(yè)面頭指針/*busypf_head 為忙頁(yè)面頭指針/*busypf_tail 為忙頁(yè)面尾指針/ 頁(yè)面失效次數(shù)intatotal_instruction;值int total_pf;void initialize(int); / voidFIFO(int);/void LRU(int);/void OPT(int);/void LFU(int);/void NUR(int);/void main()int S,i,

8、j;/ 指令流數(shù)據(jù)組/每條指令所屬頁(yè)號(hào)/每頁(yè)裝入 10 條指令后取模運(yùn)算頁(yè)號(hào)偏移/ 用戶(hù)進(jìn)程的內(nèi)存頁(yè)面數(shù)初始化函數(shù)，給每個(gè)相關(guān)的頁(yè)面賦值計(jì)算使用 FIFO 算法時(shí)的命中率計(jì)算使用 LRU 算法時(shí)的命中率計(jì)算使用 OPT 算法時(shí)的命中率計(jì)算使用 LFU 算法時(shí)的命中率計(jì)算使用 NUR 算法時(shí)的命中率srand(getpid()*10);/ 由于每次運(yùn)行時(shí)進(jìn)程號(hào)不同 , 故可用 來(lái)作為初始化隨機(jī)數(shù)隊(duì)列的 種子 S=(float)319*rand()/32767+1;for(i=0;itotal_instruction;i+=4)ai=S;ai+1=ai+1;/ 產(chǎn)生指令隊(duì)列/ 任選一指令訪(fǎng)問(wèn)點(diǎn)/

9、順序執(zhí)行一條指令ai+2=(float)ai*rand()/32767; / 執(zhí)行前地址指令 ai+3=ai+2+1; / 執(zhí)行后地址指令S=(float)rand()*(318-ai+2)/32767+ai+2+2;for(i=0;itotal_instruction;i+) / 將指令序列變換成頁(yè)地址流pagei=ai/10; /pagei:0- 32 之間的數(shù)，且當(dāng) i 為偶數(shù)時(shí)，pagei=pagei+1offseti=ai%10;for(i=4;ipn.pfn=INVALID; /pfn 置為無(wú)效 freepf_head=busypf_head;freepf_head-next=NU

10、LL;busypf_head=p;int i,j;pfc_type *p,*t;initialize(total_pf); /busypf_head=busypf_tail=NULL; /for(i=0;inext;初始化相關(guān)頁(yè)面控制用數(shù)據(jù)結(jié)構(gòu)忙頁(yè)面隊(duì)列頭 , 隊(duì)列尾鏈接/頁(yè)面失效/失效次數(shù)/無(wú)空閑頁(yè)面/p指向 busypf_head 的下p=freepf_head-next; / freepf_head-next=NULL; freepf_head-pn=pagei;plpagei.pfn=freepf_head-pfn;if(busypf_tail=NULL) /busypf_head=b

11、usypf_tail=freepf_head; elsebusypf_tail-next=freepf_head;/ 若不是第一個(gè)忙節(jié)點(diǎn)，則把新調(diào)入的頁(yè)min=32767;for(j=0;jplj.time&plj.pfn!=INVALID)按 FIFO 方式調(diào)新頁(yè)面入內(nèi)存頁(yè)面若是第一個(gè)忙節(jié)點(diǎn)，則把忙頭、指針指向第一個(gè)忙節(jié)點(diǎn)busypf_tail=freepf_head; /freepf_head=p;面鏈上忙尾指針指向最新的占用頁(yè)面/ 空閑頭指針下移printf(FIFO:%6.4f,1-(float)diseffect/320);/ 找出最近最久未被使用的頁(yè)并將其換出/LRU(La

12、st Recently Used)void LRU(int total_pf)int min,minj,i,j,present_time;initialize(total_pf);present_time=0;for(i=0;inext=NULL;pfnplpagei.pfn=freepf_head-pfn;/ 調(diào)入新頁(yè) plpagei.time=present_time;freepf_head=freepf_head-next;elseplpagei.time=present_time;present_time+;printf(LRU:%6.4f,1-(float)diseffect/320

13、);/ 從最近一個(gè)時(shí)期內(nèi)未被訪(fǎng)問(wèn)的頁(yè)中任選一頁(yè)淘汰(需增設(shè)訪(fǎng)問(wèn)位，當(dāng)某/ 頁(yè)被訪(fǎng)問(wèn)時(shí)，/ 訪(fǎng)問(wèn)位置 1，否則置 0)/NUR 最近不經(jīng)常使用算法void NUR(int total_pf)int i,j,dp,cont_flag,old_dp;pfc_type *t;initialize(total_pf);dp=0;for(i=0;itotal_instruction;i+)if(plpagei.pfn=INVALID) / 頁(yè)面失效diseffect+; if(freepf_head=NULL) / 無(wú)空閑頁(yè)面cont_flag=TRUE;old_dp=dp;/contflag 為 循環(huán)條

14、件，初始為真 while(cont_flag)if(pldp.counter=0&pldp.pfn!=INVALID)/ 找 counter 為 1 且有效的頁(yè)，作為釋放 的頁(yè)cont_flag=FALSE;else/ 若找不到則將所有頁(yè)的 counter 清 0，然后釋放任意一頁(yè)dp+;if(dp=total_vp)dp=0; if(dp=old_dp)for(j=0;jnext=NULL;plpagei.pfn=freepf_head-pfn;/ 調(diào)入頁(yè)面 freepf_head=freepf_head-next;elseplpagei.counter=1;/ 若被訪(fǎng)問(wèn)過(guò)則置 1i

15、f(i%clear_period=0)/ 定期清 0for(j=0;jtotal_vp;j+) plj.counter=0;printf(NUR:%6.4f,1-(float)diseffect/320);/ 尋找將來(lái)再也不出現(xiàn)或離當(dāng)前最遠(yuǎn)的位置上出現(xiàn)的頁(yè)/OPT(Optimal Replacement)void OPT(int total_pf)int i,j,max,maxpage,d,disttotal_vp;pfc_type *t;initialize(total_pf); for(i=0;itotal_instruction;i+)if(plpagei.pfn=INVALID)/ 頁(yè)

16、失效diseffect+; if(freepf_head=NULL)/ 無(wú)空閑頁(yè)for(j=0;jtotal_vp;j+)/ 尋找頁(yè)是否失效， 若失效則將 dist 數(shù)組置為 0，否則 只為 1if(plj.pfn!=INVALID)distj=32767;elsedistj=0;d=1; for(j=i+1;jtotal_instruction;j+)if(plpagej.pfn!=INVALID)/ 記錄從當(dāng)前位置以后出現(xiàn)的頁(yè)，并賦值給dist 數(shù)組 distpagej=d; d+;max=-1;for(j=0;jtotal_vp;j+) if(maxnext=NULL; plmaxpag

17、e.pfn=INVALID;plpagei.pfn=freepf_head-pfn;freepf_head=freepf_head-next;printf(OPT:%6.4f,1-(float)diseffect/320);/ 淘汰到當(dāng)前時(shí)間為止，被訪(fǎng)問(wèn)次數(shù)最少的頁(yè) /LFU(Leat Frequently Used) void LFU(int total_pf)int i,j,min,minpage; pfc_type *t;initialize(total_pf); for(i=0;itotal_instruction;i+)if(plpagei.pfn=INVALID)/ 頁(yè)失效dise

18、ffect+; if(freepf_head=NULL)/ 無(wú)空閑頁(yè)min=32767;for(j=0;jplj.counter&plj.pfn!=INVALID)/查 找 使 用 次 數(shù) 最 少 的 頁(yè) ， 并將counter 清 0min=plj.counter;minpage=j;plj.counter=0;freepf_head=&pfcplminpage.pfn;/ 釋放 plminpage.pfn=INVALID;freepf_head-next=NULL;plpagei.pfn=freepf_head-pfn;/ 調(diào)入新頁(yè) freepf_head=freepf_h

19、ead-next;elseplpagei.counter+;/記錄訪(fǎng)問(wèn)次數(shù)10 page frames FIFO:0.5844 LRU:0.5969 OPT:0.6594 LFU:0.6344 NUR:0.596911 page frames FIFO:0.5938 LRU:0.6094 OPT:0.6750 LFU:0.6469 NUR:0.6450【結(jié)果分析】從上述結(jié)果可知，在內(nèi)存頁(yè)面數(shù)較少（45 頁(yè)面）時(shí)，5 種算法的命中率差別不大，都是50%左右。在內(nèi)存頁(yè)面為 725 個(gè)頁(yè)面之間時(shí)，5 種算法的訪(fǎng)問(wèn)命中率大致在 52%87%之間 變化。但是，F(xiàn)IFO 算法與 OPT 算法之間的差別一般

20、在 610 個(gè)百分點(diǎn)左右。在內(nèi)存頁(yè)面為 25 32 個(gè)頁(yè)面時(shí)， 由于擁護(hù)進(jìn)程的所有指令基本上都已裝入內(nèi)存， 從而命中率已增加較大。 從而算法間的差別不大。比較上述 5 中算法，以 OPT 算法的命中率最高，NUF 次之，再就是 LFU 算法和 LRU 算法，其 次是FIFO 算法。printf(LFU:%6.4f,1-(float)diseffect/320);void initialize(int total_pf)/ 初始化相關(guān)數(shù)據(jù)結(jié)構(gòu)int i;diseffect=0;for(i=0;itotal_vp;i+)pli.pn=i;pli.pfn=INVALID;pli.counter=0;

21、pli.time=-1; /for(i=1;itotal_pf;i+)pfci-1.next=&pfci;pfci-1.pfn=i-1;/ 置頁(yè)面控制結(jié)構(gòu)中的頁(yè)號(hào) ,頁(yè)面為空頁(yè)面控制結(jié)構(gòu)中的訪(fǎng)問(wèn)次數(shù)為0, 時(shí)間為-1/ 建立 pfci-1 和 pfci 之間的鏈接pfctotal_pf-1.next=NULL;pfctotal_pf-1.pfn=total_pf-1;freepf_head=&pfc0; / 空頁(yè)面隊(duì)列的頭指針為 pfc0【運(yùn)行結(jié)果】4 page frames FIFO:0.4969LRU:0.5000OPT:0.5281 LFU:0.4969 NUR:0.50

22、005 page frames FIFO:0.51886 page frames FIFO:0.52187 page frames FIFO:0.5406LRU:0.5125LRU:0.5188LRU:0.55008 page frames FIFO:0.5500 LRU:0.57199 page frames FIFO:0.5625 LRU:0.5812OPT:0.5531 LFU:0.5125 NUR:0.5062OPT:0.5875 LFU:0.5344 NUR:0.5344OPT:0.6094 LFU:0.5625 NUR:0.5562OPT:0.6154 LFU:0.5875 NUR

23、:0.5531OPT:0.6438 LFU:0.6094 NUR:0.5781請(qǐng)求頁(yè)式存儲(chǔ)管理模擬參考代碼二/Untitled1.java/* Title: * Description: * Copyright: Copyright (c) 2007* Company: * author not attributable* version 1.0*/import java.util.Random;public class Untitled1 public static void main(String args) Untitled1 u = new Untitled1();/* int s =

24、 4, 3, 2, 1, 4, 3, 5, 4, 3, 2, 1, 5;System.out.print(FIFO + u.fifo(s, 3); System.out.print(tLRU + u.lru(s, 3) + n);System.out.print(FIFO + u.fifo(s, 4);System.out.print(tLRU + u.lru(s, 4) + n);*/int s;s = u.init(1000, 32);for (int i = 4; i 32; i+) System.out.print(FIFO + u.fifo(s, i)+t); System.out.print(LRU + u.lr