存儲管理程序的設(shè)計報告

1、一、課程設(shè)計的目的和要求存儲管理的主要功能之一是合理地分配空間。請求頁式管理是一種常用的虛擬存儲管理技術(shù)。本課程設(shè)計的目的是通過請求頁式存儲管理中頁面置換算法模擬設(shè)計，了解虛擬存儲技術(shù)的特點，掌握請求頁式管理的頁面置換算法。1.過隨機(jī)數(shù)產(chǎn)生一個指令序列，共320條指令。其地址按下述原則生成：50%的指令是順序執(zhí)行的；25%的指令是均勻分布在前地址部分；25%的指令是均勻分布在后地址部分；#具體的實施方法是：A. 在0,B.319的指C.令地址之間隨機(jī)選區(qū)一起點M;B. 順序執(zhí)行一條指E.令，F(xiàn).即執(zhí)行地址為M+1的指G.令；C. 在前地址0,I.M+1中隨機(jī)選取一條指J.令并執(zhí)行，K.該指L.

2、令的地址為M；D. 順序執(zhí)行一條指N.令，O.其地址為M+1;E. 在后地址M'+2,Q.319中隨機(jī)選取一條指R.令并執(zhí)行；F. 重復(fù)T.A-E,U.直到執(zhí)行320次指V.令。G. 指令序列變換成頁地址流設(shè)：（1）頁面大小為1K;（2）用戶存容量為4頁到32頁；（3）用戶虛存容量為32K。在用戶虛存中，按每K存放10條指令排列虛存地址，即320條指令在虛存中的存放方式為：第0條一第9條指令為第0頁（對應(yīng)虛存地址為0,9）;第10條一第19條指令為第1頁（對應(yīng)虛存地址為10,19）;000000000000000000000第310條一第319條指令為第31頁（對應(yīng)虛存地址為310,3

3、19）;按以上方式，用戶指令可組成32頁。H. 計算并輸出下述各種算法在不同存容量下的命中率A. FIFO先進(jìn)先出的算法B. LRR最近最少使用算法C. OPT最佳淘汰算法（先淘汰最不常用的頁地址）D. LFR最少訪問頁面算法E. NUR最近最不經(jīng)常使用算法二、課程設(shè)計環(huán)境要求1、硬件環(huán)境PC機(jī)一臺，0.99G存，2.00GHZ主頻2、軟件環(huán)境WindowsXP/2000系統(tǒng)，編程軟件VC+三、設(shè)計任務(wù)介紹及系統(tǒng)需求分析本課程設(shè)計主要的目的是編制頁面置換算法FIFO、LRULFUNURffiOPTB模擬程序，并模擬其在存的分配過程。同時根據(jù)頁面走向，分別采用FIFO、LRULFUNURf口OP

4、TH法進(jìn)行頁面置換，統(tǒng)計命中率；為簡化操作，在淘汰一頁時，只將該頁在頁表中抹去，而不再判斷它是否被改寫過，也不將它寫回到輔存。本程序?qū)崿F(xiàn)了操作系統(tǒng)中頁式虛擬存儲管理中缺頁中斷理想型淘汰算法，該算法在訪問申中將來再也不出現(xiàn)的或是在離當(dāng)前最遠(yuǎn)的位置上出現(xiàn)的頁淘汰掉。這樣，淘汰掉該頁將不會造成因需要訪問該頁又立即把它調(diào)入的現(xiàn)象。該程序能按要求隨機(jī)確定存大小，隨機(jī)產(chǎn)生頁面數(shù)，進(jìn)程數(shù)，每個進(jìn)程的頁數(shù)，給進(jìn)程分配的頁數(shù)等，然后運用理想型淘汰算法對每個進(jìn)程進(jìn)行計算缺頁數(shù)，缺頁率，被淘汰的序列等功能。四、概要設(shè)計系統(tǒng)分為4個子模塊：初始化模塊，F(xiàn)IFOLRULFUNURf口OPTB五個算法模塊。初始化模塊：i

5、nitialize()初始化函數(shù)，給每個相關(guān)的頁面賦值。FIFO算法模塊：計算使用FIFO算法時的命中率。LRU算法模塊：計算使用LFU算法模塊：計算使用NU曲法模塊：計算使用OPTJJ法模塊：計算使用LRU算法時的命中率。OPT算法時的命中率。LFU算法時的命中率。NURJJ法時的命中率。五、詳細(xì)設(shè)計本實驗的程序設(shè)計基本上按照實驗容進(jìn)行。即首先用srand()和rand()函數(shù)定義和產(chǎn)生指令序列，然后將指令序列變換成相應(yīng)的頁地址流，并針對不同的算法計算出相應(yīng)的命中率。相關(guān)定義如下：1數(shù)據(jù)結(jié)構(gòu)(1)頁面類型typedefstructintpn,pfn,count,time;pl-type;其中

6、pn為頁號,pfn為面號，count為一個周期訪問該頁面的次數(shù),time為訪問時間.(2)頁面控制結(jié)構(gòu)pfc-structintpn,pfn;structpfc_struct*next;typedefstructpfc_structpfc_type;pfc_typepfc_structxy,*free_head,*busy_head;pfc_type*busy_tail;其中pfcxy定義用戶進(jìn)程虛頁控制結(jié)構(gòu)，*free_head為空頁面頭的指針，*busy_head為忙頁面頭的指針，*busy_tail為忙頁面尾的指針.2 .函數(shù)定義(1) Voidinitialize。：初始化函數(shù)，給每個

7、相關(guān)白頁面賦值.(2) VoidFIFO():計算使用FIFO算法時的命中率.(3) VoidLRU():計算使用LRU#法時的命中率.(4) VoidOPT():計算使用OPTT法時的命中率.(5) VoidLFU():計算使用LFU算法時的命中率.(6) VoidNUR():計算使用NURJ法時的命中率.3 .變量定義(1)intazl:指令流數(shù)據(jù)組.intpagezllc:每條指令所屬的頁號.(3)intoffsetzllc:每頁裝入10條指令后取模運算頁號偏移值.intpf:用戶進(jìn)程的存頁面數(shù).(5)intdisaffect:頁面失效次數(shù).先進(jìn)先出算法，即FIFO算法(First-In

8、First-Outalgorithm)。這種算法選擇最先調(diào)入主存儲器的頁面作為被替換的頁面。它的優(yōu)點是比較容易實現(xiàn)，能夠利用主存儲器中頁面調(diào)度情況的歷史信息，但是，沒有反映程序的局部性。因為最先調(diào)入主存的頁面，很可能也是經(jīng)常要使用的頁面。近期最少使用算法，即LFU算法(LeastFrequentlyUsedalgorithm)。這種算法選擇近期最少訪問的頁面作為被替換的頁面。顯然，這是一種非常合理的算法，因為到目前為止最少使用的頁面，很可能也是將來最少訪問的頁面。該算法既充分利用了主存中頁面調(diào)度情況的歷史信息，又正確反映了程序的局部性。但是，這種算法實現(xiàn)起來非常困難，它要為每個頁面設(shè)置一個很長

9、的計數(shù)器，并且要選擇一個固定的時鐘為每個計數(shù)器定時計數(shù)。在選擇被替換頁面時，要從所有計數(shù)器中找出一個計數(shù)值最大的計數(shù)器。因此，通常采用如下一種相對比較簡單的方法。最久沒有使用算法，即LRU算法(LeastRecentlyUsedalgorithm)。這種算法把近期最久沒有被訪問過的頁面作為被替換的頁面。它把LFU算法中要記錄數(shù)量上的"多"與"少，簡化成判斷"有"與"無"，因此，實現(xiàn)起來比較容易。NUFRT法NURft需要淘汰某一頁時,從那些最近一個時期未被訪問的頁中任選一頁淘汰。只要在頁表中增設(shè)一個訪問位即可實現(xiàn)。當(dāng)某頁被訪

10、問時，訪問位置1。否則，訪問位置0。系統(tǒng)周期性地對所有引用位泊零。當(dāng)需淘汰一頁時，從那些訪問位為零的頁中選一頁進(jìn)行淘汰。如果引用位全0或全1,NRUB法退化為FIFO算法。最優(yōu)替換算法，即OP1W法(OPTimalreplacementalgorithm)。上面介紹的幾種頁面替換算法主要是以主存儲器中頁面調(diào)度情況的歷史信息為依據(jù)的，它假設(shè)將來主存儲器中的頁面調(diào)度情況與過去一段時間主存儲器中的頁面調(diào)度情況是相同的。顯然，這種假設(shè)不總是正確的。最好的算法應(yīng)該是選擇將來最久不被訪問的頁面作為被替換的頁面，這種替換算法的命中率一定是最高的，它就是最優(yōu)替換算法。要實現(xiàn)OPTW法，唯一的辦法是讓程序先執(zhí)行

11、一遍，記錄下實際的頁地址流情況。根據(jù)這個頁地址流才能找出當(dāng)前要被替換的頁面。顯然，這樣做是不現(xiàn)實的。因此，OPTB法只是一種理想化的算法，然而，它也是一種很有用OPTT法最接近，那的算法。實際上，經(jīng)常把這種算法用來作為評價其它頁面替換算法好壞的標(biāo)準(zhǔn)。在其它條件相同的情況下，哪一種頁面替換算法的命中率與么，它就是一種比較好的頁面替換算法。1 .頁面調(diào)度模擬算法流程示例圖2 .頁面調(diào)度模擬算法示例圖六、調(diào)試過程程序結(jié)果:匚二PC霸群文件夾口獨呻!（。耳3標(biāo)片-nX1GpageframesBF1FO；0J7031IBU：0.6969LFU：0.730dNUB；B.7031OPT：0.6781f17p

12、agefravnesFIFO;0.7094LFU：R；7fli63LFU：0.7350MIRiB.71560PT：M.i969!18pageframesFlFO;0_740fiLRU=0-7312LPU:fl.74踞MJRrfl.72190PT:«.71Gfi19pageFramesFIFO;0.7594LRU:B.7531LPU:fi.7G94MJR:fl.74£9OPT:0.731220pagfef*aeib號FIFO;0.7G88LRU：0J7594LPU：0.77E0MJR=Q.7E0Q0PT：0.7E?l21pagE£iB-a.nie&FIFO;

13、0.7719LRU：0.7t88LFUt0.7375HUR=0.7EQBOPT：0.7G5622paig毋fi"-a.niesF(FO;0.77S0LHU=8.7813LFU=a.?G?Hun=a-7cae0PT：0.7B1323pLgfcFFAineFlFOjB.7675LRU.7844LFU：0.8994HUR：a-7719OFT=0.7937|24pagefro.mc$F(FO;0.7937LRU：0.7?G9LFUI0.S258MJR：0reQ310FT：6.8e31Z5pdge¥寫FlFOiB-8094LEU品以8156LFU：0.8406NUR=0r8217Or

14、T：O.80?426pagefrancsFIF5；0,B281LFU現(xiàn)*83例LFU0843sNUR；E.8qgon：0.828127pageframesriF9；0.BJ75LFU；e.8U8LHJ：0.a&25NUR；*85?qQFI：«.843B-ZUpageframes從上述結(jié)果可知，在存頁面數(shù)較少（45頁）時，五種算法的命中率差別不大，都是30流右。在存頁面為718個頁面之間時，5種算法的訪命中率大致在35%60無間變化。但是，F(xiàn)IFO算法與OPT算法之間的差別一般在610個百分點左右。在存頁面為2532個頁面時，由于用戶進(jìn)程的所有指令基本上都已裝入存，使命中率增加

15、，從而算法之間的差別不大。比較上述5種算法，以O(shè)PT算法的命中率最高，NURT法次之，再就是LFU算法和LRU算法，其次是FIFO算法。就本問題，在15頁之前，F(xiàn)IFO的命中率比LRU的高。七、結(jié)論與體會這個程序基本完成了存儲管理程序設(shè)計的目的與要求。不過其中也有一些不足之處，例如算法有點麻煩，有些句子不是很能理解。但是我通過上網(wǎng)查找資料，去圖書館借閱相關(guān)書籍解決了這些不足之處。本次課程設(shè)計主要可以分為兩個階段，在第一個階段中，要了解五種算法的執(zhí)行原理，存的分配策略，存調(diào)頁策略；第二個階段主要是編制程序和運行改善程序。通過編寫程序可以更深入的理解算法和算法的特點。這次操作系統(tǒng)的課程設(shè)計，讓我對

16、實驗原理有更深的理解，通過把該算法的容，算法的執(zhí)行順序在計算機(jī)上實現(xiàn)，知道和理解了該理論在計算機(jī)中是怎樣執(zhí)行的，對該理論在實踐中的應(yīng)用有深刻的理解。并且這次課程設(shè)計把各個學(xué)科之間的知識融合起來，把各門課程的知識聯(lián)系起來，對計算機(jī)整體的認(rèn)識更加深刻。八、參考文獻(xiàn)1、計算機(jī)操作系統(tǒng)湯子贏等電子科技大學(xué)2、操作系統(tǒng)教程題解與實驗指導(dǎo)孟靜高等教育2003年3、C語言程序設(shè)計田祥宏等電子科技大學(xué)4、軟件工程燕慧等5、數(shù)據(jù)結(jié)構(gòu)教程（第三版）謝希仁等電子工業(yè)附件：源程序清單#include<stdlib.h>#include<stdio.h>#include<time.h>

17、;#defineTRUE1#defineFALSE0#defineINVALID-1/*指令流長*/*虛頁長*/*清0周期*/#defineNULL0#definezllc320#definexy32typedefstruct(intpn;intpfn;intcount;inttime;pc；#defineclear50/*頁面結(jié)構(gòu)*/頁號logicnumber/頁面框架號physicalframenumber/計數(shù)器/時間/*頁面控制結(jié)構(gòu)，調(diào)度算法的控制結(jié)構(gòu)*/pcplxy;/*頁面線性結(jié)構(gòu)-指令序列需要使用地址*/typedefstructpfc_struct(.intpn;intpfn;

18、structpfc_struct*next;pfc_type;pfc_typepfcxy,*free_head,*busy_head,*busy_tail;intzhihuan,azllc;/*a為指令序列*/intpagezllc,offsetzllc;/*地址信息*/intinitialize(int);intFIFO(int);intLRU(int);intLFU(int);intNUR(int);intOPT(int);intmain()ints,i;srand(unsigned)time(NULL);s=rand()%320;for(i=0;i<zllc;i+=4)/*產(chǎn)生指令

19、隊列*/if(s<0|s>319)printf("Wheni=%d,Error,s=%dn”,i,s);exit(0);ai=s;ai+1=ai+1;ai+2=rand()%(ai+1+1);ai+3=ai+2+1;s=rand()%(319-ai+3)+ai+3+1;if(ai+2>318)|(s>319)printf("a%d+2,anumberwhichis:%dands=%dn",i,ai+2,s);for(i=0;i<zllc;i+)/*將指令序列變換成頁地址流*/pagei=ai/10;offseti=ai%10;for(

20、i=4;i<=32;i+)/*用戶存工作區(qū)從4個頁面到32個頁面*/printf("%2dpageframes:n",i);FIFO(i);LRU(i);LFU(i);NUR(i);OPT(i);)return0;)/*初始化相關(guān)數(shù)據(jù)結(jié)構(gòu)pf表示存的塊數(shù)*/intinitialize(intpf)(inti;zhihuan=0;for(i=0;i<xy;i+)(pli.pfn=INVALID;pli.count=0;pli.time=-1;)/*置頁面控制結(jié)構(gòu)中的頁號，頁面為空*/*頁面控制結(jié)構(gòu)中的訪問次數(shù)為0*/*訪問的時間*/for(i=0;i<pf-

21、1;i+)(pfci.next=&pfci+1;pfci.pfn=i;)/*建立pfci-1和pfci之間的*/pfcpf-1.next=NULL;pfcpf-1.pfn=pf-1;free_head=&pfc0;return0;)/*空頁面隊列的頭指針為pfc0*/intFIFO(intpf)/*先進(jìn)先出算法pf:用尸進(jìn)程的存頁面數(shù)*/(inti;pfc_type*p;initialize(pf);busy_head=busy_tail=NULL;for(i=0;i<zllc;i+)(if(plpagei.pfn=INVALID)(zhihuan+;if(free_he

22、ad=NULL)/*中間變量*/*初始化相關(guān)頁面控制用數(shù)據(jù)結(jié)構(gòu)*/*忙頁面隊列頭，隊列尾*/*頁面失效*/*失效次數(shù)*/*無空閑頁面*/p=busy_head->next;/保存忙頁面下一個頁面plbusy_head->pn.pfn=INVALID;/把這個頁面換出，更新它的數(shù)據(jù)成員一free_head=busy_head;/*釋放忙頁面隊列的第一個頁面*/free_head->next=NULL;/*表明還是缺頁*/busy_head=p;/更新忙頁面的隊頭指針p=free_head->next;free_head->pn=pagei;plpagei.pfn=f

23、ree_head->pfn;free_head->next=NULL;/*使busy的尾為null*/if(busy_tail=NULL).busy_tail=busy_head=free_head;一一一else/把剛剛換進(jìn)來的接在busy_tail后面busy_tail->next=free_head;busy_tail=free_head;一一free_head=p;/下一個空頁面.printf("FIFO:%6.4f",1-(float)zhihuan/320);intLRU(intpf)used*/return0;/*最近最久未使用算法least

24、recentlyintmin,minj,i,j,present_time;initialize(pf);present_time=0;for(i=0;i<zllc;i+)if(plpagei.pfn=INVALID)zhihuan+;if(free_head=NULL).min=32767;for(j=0;j<xy;j+)/*minj為最小值下標(biāo)*/*頁面失效*/*無空閑頁面*/*設(shè)置最大值*/*找出time的最小值*/(if(min>plj.time&&plj.pfn!=INVALID)(min=plj.time;minj=j;free_head=&

25、pfcplminj.pfn;plminj.pfn=INVALID;plminj.time=0;free_head->next=NULL;.plpagei.pfn=free_head->pfn;plpagei.time=present_time;free_head=free_head->next;一一else(plpagei.time=present_time;/present_time+;.printf("LRU:%6.4f",1-(float)zhihuan/320);/騰出一個單元/有空閑頁面，改為有效/減少一個free頁面命中則增加該單元的訪問次數(shù)r

26、eturn0;intNUR(intpf)表示*/(inti,j,dp,cont_flag,old_dp;initialize(pf);dp=0;for(i=0;i<zllc;i+)(if(plpagei.pfn=INVALID)(zhihuan+;if(free_head=NULL)(.cont_flag=TRUE;old_dp=dp;while(cont_flag)count為0的頁面(/*最近未使用算法NotUsedrecentlycount/這個算法中count用于訪問位/*頁面失效*/*無空閑頁面*/用cont_flag找到一個訪問位if(pldp.count=0&&am

27、p;pldp.pfn!=INVALID)cont_flag=FALSE;else/下一個頁面dp+;if(dp=xy)/32個頁面找完一遍重新開始一個循環(huán)dp=0;if(dp=old_dp)/dp累積上一次訪問到的地方old_dp,然后訪問位重新清零for(j=0;j<xy;j+)plj.count=0;free_head=&pfcpldp.pfn;pldp.pfn=INVALID;free_head->next=NULL;plpagei.pfn=free_head->pfn;free_head->pn=pagei;free_head=free_head->

28、;next;一一elseplpagei.count=1;if(i%clear=0)for(j=0;j<xy;j+)plj.count=0;printf("NUR:%6.4f",1-(float)zhihuan/320);return0;intOPT(intpf)/*最佳置換算法*/inti,j,max,maxpage,distxy;initialize(pf);for(i=0;i<zllc;i+)if(plpagei.pfn=INVALID)/*頁面失效*/zhihuan+;if(free_head=NULL)/*無空閑頁面*/.for(j=0;j<xy;j+)if(plj.pfn!=INVALID)/在主存中的頁面，即將找出一個被替換出去的distj=32767;elsedistj=0;/不在主存中的頁面for(j=0;j<xy;j+)if(plj.pfn!=INV