存儲(chǔ)器管理實(shí)驗(yàn)Word版

1、實(shí)驗(yàn)七 存儲(chǔ)器管理實(shí)驗(yàn)1實(shí)驗(yàn)?zāi)康模豪斫獠僮飨到y(tǒng)虛擬存儲(chǔ)管理的原理，理解程序執(zhí)行局部性的概念。2實(shí)驗(yàn)內(nèi)容：設(shè)計(jì)一個(gè)虛擬存儲(chǔ)區(qū)和內(nèi)存工作區(qū),并使用下列算法計(jì)算訪問命中率。（1） 進(jìn)先出的算法（FIFO）（2） 最近最少使用的算法（LRU）（3） 最佳淘汰算法(OPT)命中率=(1-頁面失效次數(shù))/頁地址流長度u 實(shí)驗(yàn)要求1、 理解FIFO,LRU算法原理，理解參考程序的原理和實(shí)現(xiàn)思路。2、 完成程序的設(shè)計(jì)，重點(diǎn)完成FIFO,LRU算法3、 分析運(yùn)算結(jié)果，在分配不同的物理塊情況下，各算法的缺頁情況有什么規(guī)律？3.實(shí)驗(yàn)指導(dǎo)FIFO（先進(jìn)先出）頁面置換算法原理闡述這是最早出現(xiàn)的置換算法。該算法總是淘汰最

2、先進(jìn)入內(nèi)存的頁面，即選擇在內(nèi)存中駐留時(shí)間最久的頁面予以淘汰。該算法實(shí)現(xiàn)簡單只需把一個(gè)進(jìn)程已調(diào)入內(nèi)存的頁面，按先后次序鏈接成一個(gè)隊(duì)列，并設(shè)置一個(gè)指針，稱為替換指針，使它總是指向最老的頁面。2 / 11（1）在分配內(nèi)存頁面數(shù)（AP）小于進(jìn)程頁面數(shù)（PP）時(shí)，當(dāng)然是最先的AP個(gè)頁面放入內(nèi)存；（2）這時(shí)有需要處理新的頁面，則將原理在內(nèi)存中的AP個(gè)頁面中最先進(jìn)入的調(diào)出（是以稱為FIFO），然后放入新頁面；（3）以后如果有新頁面需要調(diào)入，按（2）之規(guī)則進(jìn)行。算法特點(diǎn)：所使用的內(nèi)存頁面構(gòu)成一個(gè)隊(duì)列。圖標(biāo)描述假設(shè)某個(gè)進(jìn)程在硬盤上被化為5個(gè)頁面（PP=5），以1、2、3、4、5分別表示，而下面是處理機(jī)調(diào)用它們的

3、順序（這取決于進(jìn)程本身）：1、4、2、5、3、3、2、4、2、5而內(nèi)存可以控制的頁面數(shù)為3（AP3），那么在使用FIFO算法時(shí)，這3個(gè)頁面的內(nèi)存使用情況應(yīng)該是這樣的：隊(duì)列第1位1425333425隊(duì)列第2位142555342隊(duì)列第3位14222534頁面5進(jìn)入，而最先進(jìn)入的頁面1被調(diào)出頁面3進(jìn)入，而此時(shí)3個(gè)頁面中最先進(jìn)入的頁面4被調(diào)出雖然有頁面需要處理，但是頁面本身以在內(nèi)存中，不需再調(diào)入了圖 11 不難看出本例共換入頁面8次，diseffect=8。算法設(shè)計(jì)void FIFO(int total_pf) int i,j; pp_type *p,*t; initialize(total_pf);

4、 busy_pp_head=busy_pp_tail=NULL; for(i=0;i<NUMBER_OF_INSTRUCTION;i+) if(vp_arraypage_of_instructioni.no_of_pp=INVALID) counter_page_default+=1; if(free_pp_head=NULL) p=busy_pp_head->next;vp_arraybusy_pp_head->no_of_vp.no_of_pp=INVALID;free_pp_head=busy_pp_head;free_pp_head->next=NULL;bus

5、y_pp_head=p; p=free_pp_head->next; free_pp_head->next=NULL; free_pp_head->no_of_vp=page_of_instructioni; vp_arraypage_of_instructioni.no_of_pp=free_pp_head->no_of_pp; if(busy_pp_tail=NULL)busy_pp_head=busy_pp_tail=free_pp_head; else busy_pp_tail->next=free_pp_head; busy_pp_tail=free_p

6、p_head; free_pp_head=p; printf("FIFO缺頁率：%6.4f ",(float)counter_page_default/320); return;LRU（最近最少使用）頁面置換算法原理闡述在采用該算法時(shí)，應(yīng)為在內(nèi)存中的每個(gè)頁面設(shè)置一個(gè)移位寄存器骼來記錄該頁面被訪問的頻率。該置換算法選擇在最近時(shí)期使用最少的頁面為淘汰頁。 在分配內(nèi)存頁面數(shù)（AP）小于進(jìn)程頁面數(shù)（PP）時(shí)，當(dāng)然是最先的AP個(gè)頁面放入內(nèi)存； 然則當(dāng)需要調(diào)頁面進(jìn)入內(nèi)存，而當(dāng)前分配的內(nèi)存頁面全部不空閑時(shí)，選擇其中最長時(shí)間沒有用到那個(gè)頁面調(diào)出，以空出內(nèi)存來放置新調(diào)入的頁面（是以稱為LRU

7、）；算法特點(diǎn)：每個(gè)頁面都有屬性表示有多長時(shí)間未被CPU使用的信息。圖表描述為了便于比較學(xué)習(xí)，例子和前面的一樣。某進(jìn)程在硬盤上被劃為5個(gè)頁面，用1、2、3、4、5表示，而處理機(jī)處理它們的順序?yàn)椋?、4、2、5、3、3、2、4、2、5而內(nèi)存可以控制的頁面數(shù)為3（AP3），那么在使用FIFO算法時(shí)，這3個(gè)頁面的內(nèi)存使用情況應(yīng)該是這樣的：最近1步使用1425332425最近2步使用142553242雖然頁面的位置發(fā)生改變，但是沒有發(fā)生頁面交換最近3步使用14225334圖 41 不難看出頁面換入共7次，diseffect=7。算法設(shè)計(jì)void LRU(int total_pf) int min,min

8、j,i,j,present_time;/訪問時(shí)刻 initialize(total_pf); present_time=0; for(i=0;i<NUMBER_OF_INSTRUCTION;i+) if(vp_arraypage_of_instructioni.no_of_pp=INVALID) counter_page_default+; if(free_pp_head=NULL) /無空閑頁面 min=MAXI;for(j=0;j<NUMBER_OF_VP;j+)if(min>vp_arrayj.time&&vp_arrayj.no_of_pp!=INVA

9、LID)min=vp_arrayj.time;minj=j;free_pp_head=&pp_controlvp_arrayminj.no_of_pp;vp_arrayminj.no_of_pp=INVALID;vp_arrayminj.time=-1;free_pp_head->next=NULL; vp_arraypage_of_instructioni.no_of_pp=free_pp_head->no_of_pp;/vp_arraypage_of_instructioni.time=present_time; free_pp_head=free_pp_head-&g

10、t;next; else vp_arraypage_of_instructioni.time=present_time;/ 使用 present_time+; printf("LRU缺頁率：%6.4f ",(float)counter_page_default/320); return ;參考程序：采用C+程序?qū)崿F(xiàn)：#include <windows.h>#include <stdio.h>#include <process.h>#define TRUE 1#define FALSE 0#define INVALID -1#define

11、NULL 0#define NUMBER_OF_INSTRUCTION 320 /指令流的指令條數(shù)#define NUMBER_OF_VP 32 /進(jìn)程的虛頁頁數(shù)/#define LINEAR_ADDRESS /有選擇性的打開該宏開關(guān) typedef struct int no_of_vp; /虛擬頁號(hào) int no_of_pp; /物理頁號(hào) int counter_in_period; /一周期內(nèi)訪問的次數(shù) int time; /訪問時(shí)間vp_struct; /頁面類型vp_struct vp_arrayNUMBER_OF_VP; /頁面結(jié)構(gòu)數(shù)組struct pp_struct /物理頁面結(jié)

12、構(gòu) int no_of_vp; int no_of_pp; struct pp_struct *next;typedef struct pp_struct pp_type;pp_type pp_controlNUMBER_OF_VP,*free_pp_head,*busy_pp_head,*busy_pp_tail;int counter_page_default;int address_of_instructionNUMBER_OF_INSTRUCTION;int page_of_instructionNUMBER_OF_INSTRUCTION,offset_of_instructionNU

13、MBER_OF_INSTRUCTION;int MAXI = 2147483647; /(1<<30)-1)*2+1; /231-1 2147483647 void initialize(int);void FIFO(int); /先進(jìn)先出void LRU(int); /最近最久未使用頁面淘汰算法（least recently used）/void OPT(int); /最佳淘汰算法int main()int S,i;srand( (int)getpid() ); S=(int)rand() % 200;/#ifndef LINEAR_ADDRESS for(i=0;i<NU

14、MBER_OF_INSTRUCTION;i+) /*產(chǎn)生指令隊(duì)列*/address_of_instructioni=S; /*任選一指令訪問點(diǎn)*/address_of_instructioni+1=address_of_instructioni+1; /*順序執(zhí)行一條指令*/address_of_instructioni+2=(int)rand()%200; /*執(zhí)行前地址指令m'*/address_of_instructioni+3=address_of_instructioni+2+1; /*執(zhí)行后地址指令*/S=(int)rand()%200;/#else/ / for(i=0;

15、i<NUMBER_OF_INSTRUCTION;i+=1) /*產(chǎn)生指令隊(duì)列*/address_of_instructioni=i;/#endiffor(i=0;i<NUMBER_OF_INSTRUCTION;i+) /*將指令序列變換成頁地址流*/ page_of_instructioni=address_of_instructioni/10;offset_of_instructioni=address_of_instructioni%10;for(i=4;i<=32;i+) /*用戶內(nèi)存工作區(qū)從4個(gè)頁面到32個(gè)頁面*/printf("%2d 物理塊："

16、,i);FIFO(i);LRU(i);/OPT(i);printf("n");/getchar();return 0;/先進(jìn)先出淘汰算法void FIFO(int total_pf) int i,j; pp_type *p,*t; initialize(total_pf); busy_pp_head=busy_pp_tail=NULL; for(i=0;i<NUMBER_OF_INSTRUCTION;i+) if(vp_arraypage_of_instructioni.no_of_pp=INVALID) counter_page_default+=1; if(fre

17、e_pp_head=NULL) p=busy_pp_head->next;vp_arraybusy_pp_head->no_of_vp.no_of_pp=INVALID;free_pp_head=busy_pp_head;free_pp_head->next=NULL;busy_pp_head=p; p=free_pp_head->next; free_pp_head->next=NULL; free_pp_head->no_of_vp=page_of_instructioni; vp_arraypage_of_instructioni.no_of_pp=f

18、ree_pp_head->no_of_pp; if(busy_pp_tail=NULL)busy_pp_head=busy_pp_tail=free_pp_head; else busy_pp_tail->next=free_pp_head; busy_pp_tail=free_pp_head; free_pp_head=p; printf("FIFO缺頁率：%6.4f ",(float)counter_page_default/320); return;/最近最少淘汰使用算法void LRU(int total_pf) int min,minj,i,j,pre

19、sent_time;/訪問時(shí)刻 initialize(total_pf); present_time=0; for(i=0;i<NUMBER_OF_INSTRUCTION;i+) if(vp_arraypage_of_instructioni.no_of_pp=INVALID) counter_page_default+; if(free_pp_head=NULL) /無空閑頁面 min=MAXI;for(j=0;j<NUMBER_OF_VP;j+)if(min>vp_arrayj.time&&vp_arrayj.no_of_pp!=INVALID)min=v

20、p_arrayj.time;minj=j;free_pp_head=&pp_controlvp_arrayminj.no_of_pp;vp_arrayminj.no_of_pp=INVALID;vp_arrayminj.time=-1;free_pp_head->next=NULL; vp_arraypage_of_instructioni.no_of_pp=free_pp_head->no_of_pp;/vp_arraypage_of_instructioni.time=present_time; free_pp_head=free_pp_head->next; else vp_array