實驗12 存儲管理

1、實驗12 存儲管理 存儲管理的重要功能之一是合理地分配存儲空間，請求頁式管理是一種常用的虛擬存儲管理技術(shù)。本實驗的目的是模擬設(shè)計請求頁式管理中頁面置換算法，由此了解虛擬存儲技術(shù)的特點，掌握請求頁式存儲管理的頁面置換算法。 實驗內(nèi)容實驗內(nèi)容1、通過隨機(jī)數(shù)產(chǎn)生一個指令序列，共320條指令。指令的地址按下述原則生成：1）50%的指令是順序執(zhí)行的；2）25%的指令均勻分布在前地址部分；3）25%的指令均勻分布在后地址部分。具體實施方法是：1）在0, 319的指令地址之間隨機(jī)選取一個起點m；2）順序執(zhí)行一條指令，即執(zhí)行地址為m+1的指令；3）在前地址端0, m+1中隨機(jī)選取一條指令并執(zhí)行，該指令地址為m

2、； 4）順序執(zhí)行一條指令，其指令地址為m+1 ；5）在后地址端m+2, 319隨機(jī)選取一條指令并執(zhí)行； 6）重復(fù)步驟15，直到執(zhí)行完320條指令。2、將指令序列變換為頁地址流，設(shè)1）頁面大小為1K；2）用戶內(nèi)存容量為4頁到32頁；3）用戶虛存容量為32K。在用戶虛存中排列虛存地址（每K存放10條指令），即320條指令在虛存中的方法位置為：第0頁 第0條第9條指令，對應(yīng)虛擬地址為0, 9第1頁 第10條19條指令，對應(yīng)虛擬地址10, 19第31頁 第310條319條指令，對應(yīng)虛址310,319按以上方法，用戶指令組成32頁。 3、計算并輸出下述各種算法在不同內(nèi)容容量下的命中率：1）先進(jìn)先出算法（

3、FIFO）；2）最佳淘汰算法（OPT）；3）最近最少使用算法（LRU）；命中率=1-頁面失效次數(shù)/頁地址流長度本實驗中，頁地址流長度為320，頁面失效次數(shù)為每次訪問相應(yīng)地址時，該地址所對應(yīng)的頁不在內(nèi)存中的次數(shù)。 為達(dá)到實現(xiàn)要求，程序先用函數(shù)srand（）、rand（）定義和生成指令序列，然后將指令序列變換成相應(yīng)的頁地址流，并針對不同算法計算出命中率。有關(guān)定義如下：1）數(shù)據(jù)結(jié)構(gòu)頁面類型typedef struct int pn;/*頁號*/ int pfn; /*頁面號*/ int time; /*訪問時間*/ pl_type;頁面控制結(jié)構(gòu) struct pfc_struct int pn, p

4、fn; struct pfc_struct *next; typedef pfc_struct pfc_type; pfc_type pfctotal_vp;/*進(jìn)程虛頁控制結(jié)構(gòu)*/ pfc_type *freepf_head, *busypf_head, busypf_tail;2）函數(shù)定義 void initialize（）：初始化函數(shù)，給每個相關(guān)頁面賦值 void FIFO（）：計算使用FIFO算法時的命中率 void LRU（）：計算使用LRU算法時的命中率 void OPT（）：計算使用OPT算法時的命中率3）變量定義 int atotal_instruction：指令流數(shù)組 int

5、 pagetotal_instruction：每條指令所屬頁號 int offsettotal_instruction：每頁裝入10條指令模運算得到每條指令在該頁內(nèi)的偏移量int total_pf：用戶進(jìn)程的內(nèi)存頁面數(shù)int diseffect：頁面失效次數(shù)#define TRUE 1#defineFALSE0#define INVALID -1 #definetotal_instruction320#define total_vp32 typedef struct/*頁描述子結(jié)構(gòu)*/ int pn;/*頁號*/int pfn;/*頁面號*/int time;/*訪問時間*/ pl_type;

6、typedef struct pfc_struct/*內(nèi)存頁面控制結(jié)構(gòu)*/int pn, pfn;struct pfc_struct *next; pfc_type;pl_type pl32;pfc_type pfctotal_vp;/*進(jìn)程虛頁控制結(jié)構(gòu)*/pfc_type *freepf_head, *busypf_head, *busypf_tail;int atotal_instruction;/*指令流數(shù)組*/int pagetotal_instruction;/*每條指令所屬頁號*/int offsettotal_instruction;/*指令的頁內(nèi)偏移量*/int diseffe

7、ct;/*頁面失效次數(shù)*/void initialize( int );void FIFO( int );void LRU( int );void OPT( int );void main()int s, i, j;srand(10*getpid();/*每次運行時進(jìn)程號用作初始化隨機(jī)數(shù)隊列的種子*/ s = rand()%320;for( i =0; i total_instruction; i +=4)/*產(chǎn)生指令執(zhí)行序列* /if(s319)printf(“When i = %d, Error, s = %dn”,i ,s );exit(0);a i = s; /*任選一指令訪問點m*/

8、a i +1 = a i +1; /*順序執(zhí)行一條指令*/a i +2 = rand()%ai;/*執(zhí)行前地址指令m*/a i +3 = a i +2 +1 ;/*順序執(zhí)行一條指令*/s = rand()%(319-ai+3) +ai+3+1;/*取后地址*/if(a i +2318 ) |(s319)printf(“a%d +2, a number which is: %d and s= %dn”,i , a i +2,s);/*end for*/for( i =0; i total_instruction; i +) /*將指令序列變成頁地址流*/page i =a i /10;offse

9、t i = a i %10;for( i =4; i =32; i+)/*用戶內(nèi)存工作區(qū)從4個頁面到32個*/printf(“%2d page frames”, i );FIFO( i );LRU( i );OPT( i );printf(“n”);void initialize( int total_pf)/*初始化相關(guān)數(shù)據(jù)結(jié)構(gòu)*/*total_pf用戶進(jìn)程的內(nèi)存頁面數(shù)*/int i;diseffect =0;for(i =0; i total_vp; i +)/*初始化頁表*/pl i .pn = i ;pl i .pfn = INVALID;/*頁面為空*/pl i .time =-1;

10、/*時間為-1*/for(i =0; i total_pf-1; i +)/*初始化內(nèi)存頁面控制表*/pfci.next=&pfci +1;pfci.pfn=i ;pfctotal_pf-1.next=NULL;pfctotal_pf-1.pfn= total_pf-1;freepf_head=&pfc0;void FIFO(int total_pf )/*分配得total_pf個內(nèi)存頁面時的FIFO算法*/int i, j;pfc_type* p;initialize(total_pf);busypf_head=busypf_tail=NULL; for( i =0; i n

11、ext;plbusypf-head-pn.pfn= INVALID;freepf_head-next = NULL;/*釋放忙頁面隊列的1st*/busypf_head= p; p=freepf_head-next;/*按FIFO方式調(diào)頁面入內(nèi)存頁面*/ freepf_head-next=NULL; freepf_head-pn=pagei; plpagei.pfn=freepf_head-next-pfn; if(busypf_tail = NULL) busypf_head=busypf_tail=freepf_head; elsebusypf_tail-next=freepf_head;

12、busypf_tail=freepf_head; freepf_head=p;/* if結(jié)束*/*for結(jié)束*/printf(“FIFO: %6.4f”, 1-(float)diseffect/320);void LRU( int total_pf )/*最近最久未使用頁面置換算法*/ int min, minj, i,j,present_time;initialize(total_pf);present_time=0; for( i =0; i total_instruction; i +) if(plpagei.pfn = INVALID)/*頁面失效*/diseffect +=1;if(

13、freepf_head) = NULL)/*無空閑頁面，需頁面淘汰*/ m=32676; for(j=0;jplj.time & plj.pfn!=INVALID)min=plj.time;minj=j;/* if 結(jié)束*/ freepf_head = &plplminj.pfn; plminj.pfn=INVALID; plminj.time=-1; freepf_head-next=NULL;/* if 結(jié)束*/ plpagei.pfn=freepf_head-next-pfn; plpagei.time=present_time; freepf_head=freepf_h

14、ead-nex; elseplpagei.time=present_time; present_time+;/*for結(jié)束*/printf(“LRU: %6.4f”, 1-(float)diseffect/320); /*函數(shù)結(jié)束*/void OPT( int total_pf )/*理想型淘汰算法*/int i,j,max,maxpage,d,disttotal_vp;pfc_type* t;initialize(total_pf);for( i =0; i total_instruction; i +) if(plpagei.pfn = INVALID)/*頁面失效*/diseffect +=1;if(freepf_head) = NULL) for(j=0;jtotal_vp; j+)if(plj.pfn!=INVALID) distj=32676; else distj=0; d=1; for( j =i+1; j total_instruction; j +)if(plpagej.pfn !=INVALID)distpagej=d;d+; max=-1; for(j=0;jtota