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

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

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

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

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

5、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，這樣我們便可使其在開(kāi)始就產(chǎn)生缺頁(yè)/定義add為缺頁(yè)次數(shù) sign作為標(biāo)識(shí)符判斷所調(diào)頁(yè)數(shù)是否在內(nèi)存中int l=0,i=0,j,num=0,cx,sign=0,add=0;float value=

6、0,sum=0; /定義sum為缺頁(yè)率srand(time(NULL);for(cx=0;cx<N;cx+) /總共運(yùn)行N次while(i<320)orderi=rand()%320; /產(chǎn)生隨機(jī)數(shù)放order中for(j=0;j<4;j+)if(orderi+1)/10=mem_volumej)sign=1;/通過(guò)sign標(biāo)識(shí)判斷所調(diào)頁(yè)數(shù)是否在內(nèi)存塊中if(sign)sign=0;elsel+;if(mem_volume3=100)mem_volume3=(orderi+1)/10;/ 保證第一次調(diào)入的頁(yè)面都產(chǎn)生缺頁(yè)elsemem_volumenum=(orderi+1)/

7、10; /將所缺頁(yè)調(diào)入到內(nèi)存塊中num=(num+1)%4; /num值為下次所要置換出去的內(nèi)存塊中對(duì)應(yīng)的頁(yè)數(shù)i+; orderi=rand()%(orderi-1+2);for(j=0;j<4;j+)if(orderi/10=mem_volumej)sign=1;if(sign)sign=0;else l+;if(mem_volume2=100)mem_volume2=orderi/10;elsemem_volumenum=orderi/10;num=(num+1)%4;i+;orderi=orderi-1+1;for(j=0;j<4;j+)if(orderi/10=mem_vo

8、lumej)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(sign)sign=0;else l+;if(mem_volume0=100)mem_volume0=(orderi+1)/10;elsemem_volumenu

9、m=orderi/10;num=(num+1)%4; i+;value=l/320.0*100;add=add+l;sum=sum+value;printf("* FIFO頁(yè)面置換算法 *n");printf("* 最后一次指令序列 *");for(i=0;i<320;i+)if(i%10=0)printf("n");printf("%5d",orderi);printf("n");printf("*n");printf("tt%d次的平均缺頁(yè)數(shù)為%dntt%

10、d次的平均缺頁(yè)率為%.3f%n",N,add/N,N,sum/N);printf("n");LRU頁(yè)面置換算法設(shè)計(jì)說(shuō)明：這個(gè)算法同F(xiàn)CFS算法的不同之處在于，每產(chǎn)生一條隨機(jī)指令，如果和4個(gè)內(nèi)存塊中的某一個(gè)頁(yè)數(shù)相同的話，就要對(duì)這4個(gè)內(nèi)存塊中的頁(yè)數(shù)重新排序，將每次要置換出去的頁(yè)數(shù)放在mem_volume3中，這樣，在每次產(chǎn)生缺頁(yè)的時(shí)候，都先將所缺頁(yè)數(shù)寫(xiě)入到該內(nèi)存塊，然后再排序，將其放到mem_volume0中去。源代碼：/ 儲(chǔ)存管理.cpp : 定義控制臺(tái)應(yīng)用程序的入口點(diǎn)。/#include "stdafx.h"int _tmain(int arg

11、c, _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,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()%32

12、0;if(orderi+1)/10=mem_volume0);/如果所調(diào)頁(yè)數(shù)同第一個(gè)內(nèi)存塊中頁(yè)數(shù)相同，則執(zhí)行空操作else if(orderi+1)/10=mem_volume1)temp=mem_volume1;mem_volume1=mem_volume0;mem_volume0=temp;/如果所調(diào)頁(yè)數(shù)同第二個(gè)內(nèi)存塊相同，則排序只需交換一次else if(orderi+1)/10=mem_volume2)for(j=2;j>0;j-)temp=mem_volumej;mem_volumej=mem_volumej-1;mem_volumej-1=temp;else if(order

13、i+1)/10=mem_volume3)for(j=3;j>0;j-)temp=mem_volumej;mem_volumej=mem_volumej-1;mem_volumej-1=temp; /如果所調(diào)頁(yè)數(shù)同第3、4個(gè)內(nèi)存塊中頁(yè)數(shù)相同，則通過(guò)循環(huán)進(jìn)行排序elsel+;if(mem_volume3=100)mem_volume3=(orderi+1)/10;/保證剛開(kāi)始調(diào)入內(nèi)存塊中就產(chǎn)生缺頁(yè)elsemem_volume3=(orderi+1)/10;for(num=3;num>0;num-)ex_chan=mem_volumenum;mem_volumenum=mem_volum

14、enum-1;mem_volumenum-1=ex_chan;/寫(xiě)人后重新排序i+;orderi=rand()%(orderi-1+2);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)for(j=2;j>0;j-)temp=mem_volumej;mem_volumej=mem_volumej-1;mem_volumej-1=temp;else if

15、(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;elsemem_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

16、;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)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_v

17、olumej=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_chan=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);else if(order

18、i/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_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

19、 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=mem_volumenum-1;mem_volumenum-1=ex_chan;i+;value=l/320.0*100;sum=sum+value;add=add+l;printf("* LRU頁(yè)面置換算法 *n");printf("* 指令序列 *");for(i=0;i<320;i+)

20、if(i%10=0)printf("n");printf("%5d",orderi);printf("n");printf("*n");printf("tt%d次的平均缺頁(yè)數(shù)為%dntt%d次的平均缺頁(yè)率為%.3f%n",N,add/N,N,sum/N);printf("n");LFU頁(yè)面置換算法設(shè)計(jì)說(shuō)明：該算法主要是將最近時(shí)期頁(yè)面使用最少的頁(yè)面作為淘汰頁(yè)。這里通過(guò)設(shè)立count32這個(gè)計(jì)數(shù)數(shù)組記錄32頁(yè)的調(diào)用次數(shù)，通過(guò)比較來(lái)確定要調(diào)出的頁(yè)面。但如果沒(méi)產(chǎn)生缺頁(yè)就只需對(duì)所調(diào)頁(yè)數(shù)

21、對(duì)應(yīng)的count值加1即可。源代碼：/ 儲(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 5 /定義運(yùn)行次數(shù)void main()int order320,count32=0,compare4=0,mem_volume4=100,100,100,100;/compare數(shù)組中存放了每次要比

22、較的四個(gè)內(nèi)存塊中頁(yè)數(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;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;elsel+;if(mem_volume3=100)mem_volume3=(

23、orderi+1)/10;n=(orderi+1)/10;countn+=1; elsemin=1000;for(num=0;num<4;num+)k=mem_volumenum;comparenum=countk;if(comparenum<min)min=comparenum;j=num;/通過(guò)比較確定最少使用的頁(yè)數(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(s

24、ign)sign=0;else l+;if(mem_volume2=100)mem_volume2=(orderi+1)/10;n=(orderi+1)/10;countn+=1;elsemin=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=(orderi+1)/10;countn+=1;elsemin=1000;for(num=0;num<4;num+)k=mem_volumenum;compar