存儲(chǔ)管理模擬實(shí)現(xiàn)

1、一、實(shí)驗(yàn)?zāi)康拇鎯?chǔ)管理的主要功能之一是合理地分配空間。請求頁式管理是一種常用的虛擬存儲(chǔ)管理技術(shù)。本實(shí)驗(yàn)的目的是通過請求頁式存儲(chǔ)管理中頁面置換算法模擬設(shè)計(jì)，了解虛擬存儲(chǔ)技術(shù)的特點(diǎn)，掌握 請求頁式管理的頁面置換算法。二、實(shí)驗(yàn)內(nèi)容編程實(shí)現(xiàn)頁面置換算法，要求輸出頁面的置換過程，具體可以編程實(shí)現(xiàn) OPT FIFO和LRU算法。1過隨機(jī)數(shù)產(chǎn)生一個(gè)指令序列，共320 條指令。其地址按下述原則生成： 50%的指令是順序執(zhí)行的； 25%的指令是均勻分布在前地址部分； 25%的指令是均勻分布在后地址部分；#具體的實(shí)施方法是：A. 在0， 319的指令地址之間隨機(jī)選區(qū)一起點(diǎn) M;B. 順序執(zhí)行一條指令，即執(zhí)行地址為

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

3、10條第 319條指令為第 31頁（對應(yīng)虛存地址為 310， 319）； 按以上方式，用戶指令可組成 32頁。3. 計(jì)算并輸出下述各種算法在不同內(nèi)存容量下的命中率。B. LRU最近最少使用算法C. LFU最少訪問頁面算法三、實(shí)驗(yàn)要求1、需寫出設(shè)計(jì)說明；2、設(shè)計(jì)實(shí)現(xiàn)代碼及說明3、運(yùn)行結(jié)果；四、主要實(shí)驗(yàn)步驟1、分析算法結(jié)構(gòu)； 畫出算法的流程圖，即設(shè)計(jì)說明； 根據(jù)畫出的流程圖使用 C語言編寫相應(yīng)的代碼(代碼過長，放到最后) 程序主要由 main 函數(shù)和以下幾個(gè)函數(shù)組成： void initialization();初始化內(nèi)存數(shù)據(jù)void FIFO();FIFO 先進(jìn)先出算法； void LRU();

4、LRU 最久未使用算法； void LFU();LFU 最近最久未使用算法：流程圖如下：頁面置換算法整體結(jié)構(gòu)開始FIFO頁面置換算法LRU頁面置換算法LFU頁面置換算法2、設(shè)計(jì)說明及源代碼FIFO算法設(shè)計(jì)說明：按照所要求的產(chǎn)生隨機(jī)指令序列，存放在order320這個(gè)數(shù)組中。通過循環(huán)產(chǎn)生這些隨機(jī)指令，每產(chǎn)生一條都要進(jìn)行下列判斷：是否和內(nèi)存中即mem_volume4中存放的頁面相同，如果相同則不做任何操作，如果不相同，則產(chǎn)生缺頁，相應(yīng)的缺頁次數(shù)加一，按照 fcfs 將最先進(jìn)入內(nèi)存的頁數(shù)淘汰，并將該頁寫到內(nèi)存中去。重復(fù)上面的操作直到完成這 320 條指令。 源代碼：/ 儲(chǔ)存管理 .cpp : 定義控

5、制臺(tái)應(yīng)用程序的入口點(diǎn)。 /#include "stdafx.h"int _tmain(int argc, _TCHAR* argv) return 0;#include <stdio.h>#include <stdlib.h>#include <time.h>#define N 5 / 總共運(yùn)行的次數(shù) void main()int order320,mem_volume4=100,100,100,100;/ 使得 mem_volume 的值大于 100>32，這樣我們便可使其在開始就產(chǎn)生缺頁 / 定義 add 為缺頁次數(shù) sign

6、作為標(biāo)識(shí)符判斷所調(diào)頁數(shù)是否在內(nèi)存中int l=0,i=0,j,num=0,cx,sign=0,add=0;float value=O,sum=O; /定義 sum為缺頁率 srand(time(NULL);總共運(yùn)行 N 次產(chǎn)生隨機(jī)數(shù)放 order 中for(cx=0;cx<N;cx+) /while(i<320)orderi=rand()%320; / for(j=0;j<4;j+)if(orderi+1)/10=mem_volumej)sign=1; / 通過 sign 標(biāo)識(shí)判斷所調(diào)頁數(shù)是否在內(nèi)存塊中if(sign)sign=0;elsel+;if(mem_volume3=

7、100)mem_volume3=(orderi+1)/10;/保證第一次調(diào)入的頁面都產(chǎn)生缺頁elsemem_volumenum=(orderi+1)/10; / 將所缺頁調(diào)入到內(nèi)存塊中 num=(num+1)%4;/num 值為下次所要置換出去的內(nèi)存塊中對應(yīng)的頁數(shù)i+;orderi=rand()%(orderi-1+2);for(j=0;j<4;j+)if(orderi/10=mem_volumej)sign=1;if(sign)sign=0;elsel+;if(mem_volume2=100) mem_volume2=orderi/10;elsemem_volumenum=orderi

8、/10;num=(num+1)%4;i+;orderi=orderi-1+1;for(j=0;j<4;j+)if(orderi/10=mem_volumej)sign=1;if(sign)sign=0;elsel+;if(mem_volume1=100) mem_volume1=orderi/10;elsemem_volumenum=orderi/10;num=(num+1)%4;i+; orderi=rand()%(319-orderi-1-2)+(orderi-1+2); for(j=0;j<4;j+)if(orderi/10=mem_volume0)sign=1;if(sig

9、n)sign=0;elsel+;if(mem_volume0=100)mem_volume0=(orderi+1)/10;else mem_volumenum=orderi/10; num=(num+1)%4;i+; value=l/320.0*100; add=add+l; sum=sum+value;頁面置換算法 最后一次指令序列*n");*");printf( "* FIFOprintf( "* for(i=0;i<320;i+) if(i%10=0) printf("n");printf("%5d",

10、orderi);printf("n");printf( "*n");printf("tt%d 次 的 平 均 缺 頁 數(shù) 為 %dntt%d 次 的 平 均 缺 頁 率 為 .3f%n",N,add/N,N,sum/N);printf("n");LRU頁面置換算法設(shè)計(jì)說明：這個(gè)算法同F(xiàn)CFS算法的不同之處在于，每產(chǎn)生一條隨機(jī)指令，如果和 4 個(gè)內(nèi)存塊中的某一個(gè)頁數(shù)相同的話，就要對這 4 個(gè)內(nèi)存塊中的頁數(shù)重新排序，將每次要置換 出去的頁數(shù)放在 mem_volume3中，這樣，在每次產(chǎn)生缺頁的時(shí)候，都先將所缺頁數(shù)寫入到

11、該內(nèi)存 塊，然后再排序，將其放到 mem_volume0 中去。源代碼：/ 儲(chǔ)存管理 .cpp : 定義控制臺(tái)應(yīng)用程序的入口點(diǎn)。/#include "stdafx.h"int _tmain(int argc, _TCHAR* argv)return 0;#include <stdio.h>#include <stdlib.h>#include <time.h>#define N 5int main(void)int order320,mem_volume4=100,100,100,100;int l=0,i=0,j,cx;int num,

12、temp=0,ex_chan=0,add=0;float value=0,sum=0;srand(time(NULL);for(cx=0;cx<N;cx+)while(i<320)orderi=rand()%320;if(orderi+1)/10=mem_volume0); / 如果所調(diào)頁數(shù)同第一個(gè)內(nèi)存塊中頁數(shù)相同，則執(zhí)行空操作 else if(orderi+1)/10=mem_volume1)temp=mem_volume1;mem_volume1=mem_volume0;mem_volume0=temp;/ 如果所調(diào)頁數(shù)同第二個(gè)內(nèi)存塊相同，則排序只需交換一次 else if(o

13、rderi+1)/10=mem_volume2)for(j=2;j>0;j-)temp=mem_volumej;mem_volumej=mem_volumej-1;mem_volumej-1=temp;else if(orderi+1)/10=mem_volume3)for(j=3;j>0;j-)temp=mem_volumej;mem_volumej=mem_volumej-1;mem_volumej-1=temp; / 如果所調(diào)頁數(shù)同第 3、4 個(gè)內(nèi)存塊中頁數(shù)相同，則通過循環(huán)進(jìn)行排序 else l+;if(mem_volume3=100) mem_volume3=(orderi

14、+1)/10;/ 保證剛開始調(diào)入內(nèi)存塊中就產(chǎn)生缺頁 elsemem_volume3=(orderi+1)/10;for(num=3;num>0;num-) ex_chan=mem_volumenum; mem_volumenum=mem_volumenum-1;mem_volumenum-1=ex_chan; / 寫人后重新排序 i+; orderi=rand()%(orderi-1+2); if(orderi/10=mem_volume0)Jelse if(orderi/10=mem_volume1) temp=mem_volume1; mem_volume1=mem_volume0;

15、 mem_volume0=temp;else if(orderi/10=mem_volume2) for(j=2;j>0;j-) temp=mem_volumej; mem_volumej=mem_volumej-1; mem_volumej-1=temp;else if(orderi/10 = mem_volume3) for(j=3;j>0;j-) temp=mem_volumej; mem_volumej=mem_volumej-1; mem_volumej-1=temp;else l+; if(mem_volume2=100) mem_volume2=orderi/10;e

16、lsemem_volume3=orderi/10; for(num=3;num>0;num-) ex_chan=mem_volumenum; mem_volumenum=mem_volumenum-1; mem_volumenum-1=ex_chan; i+;orderi=orderi-1+1; if(orderi/10= mem_volume0)else if(orderi/10 = mem_volume1)temp=mem_volume1; mem_volume1=mem_volume0;mem_volume0=temp;else if(orderi/10 = mem_volume2

17、)for(j=2;j>0;j-) temp=mem_volumej; mem_volumej=mem_volumej-1; mem_volumej-1=temp;else if(orderi/10=mem_volume3)for(j=3;j>0;j-) temp=mem_volumej; mem_volumej=mem_volumej-1; mem_volumej-1=temp;elsel+;if(mem_volume1=100)mem_volume1=orderi/10;elsemem_volume3=orderi/10;for(num=3;num>0;num-) ex_c

18、han=mem_volumenum; mem_volumenum=mem_volumenum-1; mem_volumenum-1=ex_chan;i+; orderi=rand()%(319-orderi-1-2)+(orderi-1+2); if(orderi/10=mem_volume0)Jelse if(orderi/10=mem_volume1) temp=mem_volume1; mem_volume1=mem_volume0; mem_volume0=temp;else if(orderi/10=mem_volume2)for(j=2;j>0;j-)temp=mem_vol

19、umej;mem_volumej=mem_volumej-1; mem_volumej-1=temp;else if(orderi/10= mem_volume3) for(j=3;j>0;j-) temp=mem_volumej; mem_volumej=mem_volumej-1; mem_volumej-1=temp;else l+;if(mem_volume0=100)mem_volume0=orderi/10;elsemem_volume3=orderi/10;for(num=3;num>0;num-)ex_chan=mem_volumenum;mem_volumenum

20、=mem_volumenum-1; mem_volumenum-1=ex_chan;i+;value=l/320.0*100; sum=sum+value; add=add+l;printf( "*頁面置換算法);printf(指令序列*");for(i=0;i<320;i+)if(i%10=0) printf("n");printf("%5d",orderi);printf("n");printf(H*n");printf("tt%d 次 的 平 均 缺 頁 數(shù) 為 %dntt%d 次

21、的 平 均 缺 頁 率 為 .3f%n",N,add/N,N,sum/N);printf("n");LFU 頁面置換算法設(shè)計(jì)說明： 該算法主要是將最近時(shí)期頁面使用最少的頁面作為淘汰頁。這里 通過設(shè)立 count32 這個(gè)計(jì)數(shù)數(shù)組記錄 32 頁的調(diào)用次數(shù)， 通過比較來確定要調(diào)出的頁面。 但如果沒產(chǎn)生缺頁就只需對所調(diào)頁數(shù)對應(yīng)的 count 值加 1 即可。 源代碼：/ 儲(chǔ)存管理 .cpp : 定義控制臺(tái)應(yīng)用程序的入口點(diǎn)。/#include "stdafx.h"int _tmain(int argc, _TCHAR* argv) return 0;#

22、include <stdio.h>#include <stdlib.h>#include <time.h>#define N 5 / 定義運(yùn)行次數(shù) void main()int order320,count32=0,compare4=0,mem_volume4=100,100,100,100; /compare 數(shù)組中存放了每次要比較的四個(gè)內(nèi)存塊中頁數(shù)的調(diào)用次數(shù) int l=0,i=0,j,k=0,cx=0;int min,num=0,n,sign=0,add=0;float value=0,sum=0; srand(time(NULL); for(cx=0

23、;cx<N;cx+) while(i<320) orderi=rand()%320; for(j=0;j<4;j+) if(orderi+1)/10=mem_volumej) n=(orderi+1)/10; countn+=1; sign=1; / 相同執(zhí)行加 1 操作 if(sign)sign=0;else l+; if(mem_volume3=100) mem_volume3=(orderi+1)/10; n=(orderi+1)/10; countn+=1;else min=1000;for(num=0;num<4;num+)k=mem_volumenum;co

24、mparenum=countk;if(comparenum<min)min=comparenum;j=num; / 通過比較確定最少使用的頁數(shù)，mem_volumej=(orderi+1)/10;i+;orderi=rand()%(orderi-1+2);for(j=0;j<4;j+)if(orderi/10=mem_volumej)n=orderi/10;countn+=1;sign=1;if(sign)sign=0;else l+;if(mem_volume2=100)mem_volume2=(orderi+1)/10;n=(orderi+1)/10;countn+=1;els

25、e min=1000;for(num=0;num<4;num+)k=mem_volumenum;comparenum=countk;if(comparenum<min)min=comparenum;j=num;mem_volumej=(orderi+1)/10;i+;orderi=orderi-1+1;for(j=0;j<4;j+)if(orderi/10= mem_volumej)n=orderi/10;countn+=1;sign=1;if(sign)sign=0;elsel+;if(mem_volume1=100)mem_volume1=(orderi+1)/10;n=

26、(orderi+1)/10;countn+=1;else min=1000;for(num=0;num<4;num+) k=mem_volumenum; comparenum=countk; if(comparenum<min) min=comparenum; j=num;mem_volumej=(orderi+1)/10;i+; orderi=rand()%(319-orderi-1-2)+(orderi-1+2); for(j=0;j<4;j+)if(orderi/10=mem_volume0)n=orderi/10;countn+=1;sign=1;if(sign)si

27、gn=0;else l+;if(mem_volume0=100)mem_volume0=(orderi+1)/10;n=(orderi+1)/10;countn+=1;else min=1000;for(num=0;num<4;num+) k=mem_volumenum; comparenum=countk; if(comparenum<min) min=comparenum; j=num; mem_volumej=(orderi+1)/10;i+;value=l/320.0*100;add=add+l;sum=sum+value;頁面置換算法 最后一次指令序列"* LF

28、U*n");*"); printf( printf( "* for(i=0;i<320;i+) if(i%10=0) printf("n");printf("%5d",orderi);printf("n");printf( "*n");printf("t%d 次 的 平 均 缺 頁 數(shù) 為 %dnt%d 次 的 平 均 缺 頁 率 為 .3f%",N,add/10,N,sum/10);printf("n");五、實(shí)驗(yàn)數(shù)據(jù)及處理結(jié)果FIFO頁面置換算法運(yùn)行結(jié)果： "G： vc6 Microsoft VisuaI StudiM MyProjects456Debug' 456,etc"913?78頁一FO后 3FI曰<9*1EH算序8310 189 112 161102 316112624114 1S 2 S3 1432295173 305 18018123G2?98282920512812? 128 1?3165 1081092692188788144 1542829 151230 1631&42232062021 143228 1531S4 200