操作系統(tǒng)實驗：頁面置換算法實驗

1、淮海工學院計算機科學系實驗報告書課程名： 操作系統(tǒng)原理 題 目虛擬存儲器管理頁面置換算法模擬實驗班 級：學 號：姓 名：評語:成績： 指導(dǎo)教師： 批閱時間:一、實驗?zāi)康呐c要求1. 目的：請求頁式虛存管理是常用的虛擬存儲管理方案之一。通過請求頁式虛存管理中對頁面置換算法的模擬，有助于理解虛擬存儲技術(shù)的特點，并加深對請求頁式虛存管理的頁面調(diào)度算法的 理解。2. 要求：本實驗要求使用 C語言編程模擬一個擁有若干個虛頁的進程在給定的若干個實頁中運行、并在缺頁中斷發(fā)生時分別使用FIFO和LRU算法進行頁面置換的情形。其中虛頁的個數(shù)可以事先給定（例如10個），對這些虛頁訪問的頁地址流（其長度可以事先給定，

2、例如20次虛頁訪問）可以由程序隨機產(chǎn)生，也可以事先保存在文件中。要求程序運行時屏幕能顯示出置換過程 中的狀態(tài)信息并輸出訪問結(jié)束時的頁面命中率。程序應(yīng)允許通過為該進程分配不同的實頁數(shù)， 來比較兩種置換算法的穩(wěn)定性。二、實驗說明1 .設(shè)計中虛頁和實頁的表示本設(shè)計利用C語言的結(jié)構(gòu)體來描述虛頁和實頁的結(jié)構(gòu)。在虛頁結(jié)構(gòu)中，pn代表虛頁號，因為共10個虛頁，所以pn的取值范圍是09。pfn代表實 頁號，當一虛頁未裝入實頁時，此項值為-1 ;當該虛頁已裝入某一實頁時，此項值為所裝入的實頁的實頁號pfn。time項在FIFO算法中不使用，在 LRU中用來存放對該虛頁的最近訪問時間。在實頁結(jié)構(gòu)中中，pn代表虛頁

3、號，表示pn所代表的虛頁目前正放在此實頁中。pfn代表實頁號，取值范圍（0n-1 ）由動態(tài)指派的實頁數(shù) n所決定。next是一個指向?qū)嶍摻Y(jié)構(gòu)體的指針，用于多個 實頁以鏈表形式組織起來，關(guān)于實頁鏈表的組織詳見下面第4點。2 .關(guān)于缺頁次數(shù)的統(tǒng)計為計算命中率，需要統(tǒng)計在20次的虛頁訪問中命中的次數(shù)。為此，程序應(yīng)設(shè)置一個計數(shù)器 count ,來統(tǒng)計虛頁命中發(fā)生的次數(shù)。每當所訪問的虛頁的pfn項值不為-1 ,表示此虛頁已被裝入某實頁內(nèi)，此虛頁被命中，count力口 1。最終命中率 =count/20*100%。3. LRU算法中“最近最久未用”頁面的確定為了能找到“最近最久未用”的虛頁面，程序中可引入

4、一個時間計數(shù)器countime，每當要訪問一個虛頁面時，countime的值加1，然后將所要訪問的虛頁的time項值設(shè)置為增值后的當前countime值，表示該虛頁的最后一次被訪問時間。當LRU算法需要置換時，從所有已分配實頁的虛頁中找出time值為最小的虛頁就是“最近最久未用”的虛頁面，應(yīng)該將它置換出去。4 算法中實頁的組織因為能分配的實頁數(shù) n是在程序運行時由用戶動態(tài)指派的，所以應(yīng)使用鏈表組織動態(tài)產(chǎn)生的多個實頁。為了調(diào)度算法實現(xiàn)的方便，可以考慮引入free和busy兩個鏈表：free鏈表用于組織未分配出去的實頁，首指針為free_head ,初始時n個實頁都處于free鏈表中；busy鏈表

5、用于組織已分配出 去的實頁，首指針為 busy_head，尾指針為busy_tail ，初始值都為null。當所要訪問的一個虛頁 不在實頁中時，將產(chǎn)生缺頁中斷。此時若free鏈表不為空，就取下鏈表首指針所指的實頁，并分配給該虛頁。若free鏈表為空，則說明 n個實頁已全部分配出去，此時應(yīng)進行頁面置換：對于FIFO算法要將busy_head所指的實頁從busy鏈表中取下，分配給該虛頁，然后再將該實頁插入到busy鏈表尾部；對于LRU算法則要從所有已分配實頁的虛頁中找出time值為最小的虛頁，將該虛頁從裝載它的那個實頁中置換出去，并在該實頁中裝入當前正要訪問的虛頁。三、程序流程圖1.FIFO算法2

6、.LRU算法開始四、主要程序清單#in clude<stdlib.h>#in clude<stdio.h>#in clude<c oni o.h>#in clude <time.h>#in clude<iostream.h>#defi ne M 101110個虛頁個頁面的訪問序列實頁個數(shù)#defi ne N 2020#defi ne S 100/定義虛頁的結(jié)構(gòu)typedef struct VirtualPageint pn;int pfn;int time;VirtualPage;/定義實頁的結(jié)構(gòu)typedef struct Page

7、int pn;int pfn;struct Page* n ext;Page;struct Page ppS; II定義一個存放5個實頁的數(shù)組，在底下還要將其串成鏈表struct VirtualPage vpM; II定義存放10個虛頁的數(shù)組int queueN; II定義一個數(shù)組，存放隨機生成的20個數(shù)，表示訪問虛頁的次序，里面的數(shù)值不能超過9int count; II存放缺頁次數(shù)，用來統(tǒng)計缺頁率。本算法沒有考慮預(yù)調(diào)頁，只要該頁不在內(nèi)存，就認為缺頁一次。int countime; II用于LRU算法中，找出要淘汰的頁。每當要訪問一個虛頁面時，countime的值加1,然后將所要訪問的虛頁的t

8、ime項值設(shè)置為增值后的當前countime值int MemoryStatusSN; II記錄當訪問每一個虛頁時，內(nèi)存中的5個實頁的詳細信息。int NotI nM emoryN; II表示每次虛頁訪問是否在內(nèi)存struct Page *Free,*Free_head,*Busy,*Busy_tail,*Busy_head,*temp;int sn;void in it()int i,j;coun t=0;coun time=0;/初始化10個虛頁for(i=0;i<M;i+)vpi.p n=i;vpi.pfn=-1;vpi.time=0;/初始化5個實頁，并將其串成鏈表形式for(i=

9、0;i<s n;i+)ppi.p n=-1;ppi.pfn=i;ppi. next=NULL;/將5個實頁依次相連，形成Free鏈表Free=&ppO;for(i=0;i<s n_1;i+)ppi. next=&ppi+1;pps n-1. next=NULL;Free_head=Free;/初始化Busy鏈表Busy=NULL;Busy_head=NULL;Busy_tail=NULL;/初始化Memorystatus數(shù)組for(i=0;i<s n;i+)for(j=0;j<N;j+)MemoryStatusij=-1;/初始化 NotlnMemory

10、數(shù)組for(i=0;i<N;i+)NotI nM emoryi=1; 表示不再內(nèi)存void FIFO()int i,j,k,curre ntpage;for(i=0;i<N;i+) /這是主循環(huán)，每次處理一個虛頁訪問。直到把 20個虛頁處理完為止。curre ntpage=queuei;/判斷該虛頁是否已經(jīng)調(diào)入內(nèi)存if(vpcurre ntpage.pfn!=-1) /表示該頁已經(jīng)在內(nèi)存中，可以直接訪問。同時記錄訪問該頁時對應(yīng)的實頁信息(和前一頁相同)for(j=0;j<s n;j+)MemoryStatusji=MemoryStatusji-1;NotI nM emoryi

11、=0;else II該頁不在內(nèi)存，需要請求調(diào)頁coun t=co un t+1;if(Free!=NULL) / 如果Free鏈表不為空，表示內(nèi)存中還有空的實頁temp=Free_head; /本程序中用Free表示鏈表的起始地址，F(xiàn)ree_head表示鏈表中的第一個元素地址。實際上兩者的值永遠相等。Free_head=Free_head->n ext;Free=Free_head;/ 將虛頁currentpage 裝入temp指向的實頁，該實頁的編號為temp->pfnvpcurre ntpage.pfn=temp_>pfn;temp->p n=curre ntpag

12、e;/將temp指向的實頁插入 Busy鏈表的末尾temp->n ext=NULL;if(Busy=NULL) /如果是第一次把虛頁裝入實頁，則temp就是Busy鏈表的第個元素。Busy=temp;Busy_head=Busy;Busy_tail=Busy;else /如果不是第一次把虛頁裝入實頁，則將temp插入Busy鏈表的隊尾。Busy_tail->n ext=temp;Busy_tail=temp;/修改內(nèi)存狀態(tài)for(k=0;k<s n;k+) /復(fù)制訪問前一頁時的內(nèi)存狀態(tài)MemoryStatuski=MemoryStatuski-1;temp->pfn表示

13、的那個實頁里else / 如果Free鏈表為空，需要置換一頁出去/ 將Busy首元素取出，賦給 temptemp=Busy;Busy_head=Busy->n ext;Busy=Busy_head; 將當前虛頁currentpage 裝入temp指向的實頁，修改其信息vptemp->p n.pfn=_1;vpcurre ntpage.pfn=temp_>pfn;temp->p n=curre ntpage;temp->n ext=NULL;Busy_tail->n ext=temp;Busy_tail=temp;/修改內(nèi)存狀態(tài)for(k=0;k<s n

14、; k+)MemoryStatuski=MemoryStatuski-1;裝入了MemoryStatustemp->pfni=currentpage;/ 虛頁 currentpagetemp->pfn表示的那個實頁里 void LRU()int i,j,k,curre ntpage;for(i=0;i<N;i+)curre ntpage=queuei;if(vpcurre ntpage.pfn!=-1) /該虛頁已經(jīng)在內(nèi)存for(j=0;j<s n;j+)MemoryStatusji=MemoryStatusji-1;NotI nM emoryi=0;else /虛頁不

15、在內(nèi)存coun t=co un t+1;if(Free!=NULL) /還有空閑的實頁temp=Free_head;Free_head=Free_head->n ext;Free=Free_head;vpcurre ntpage.pfn=temp_>pfn;temp->p n=curre ntpage;temp->n ext=NULL;if(Busy=NULL)Busy=temp;Busy_head=Busy;Busy_tail=Busy; elseBusy_tail->n ext=temp;Busy_tail=temp;for(k=0;k<s n; k+)

16、MemoryStatuski=MemoryStatuski-1;MemoryStatustemp->pfni=curre ntpage; elseint min=vpppO.p n.time;temp=&pp0;for(i nt k=1;k<s n; k+)if(vpppk.p n.time< min)min=vpppk.p n.time;temp=&ppk; vptemp->p n.pfn=_1;vpcurre ntpage.pfn=temp_>pfn;temp->p n=curre ntpage;MemoryStatuski=Memory

17、Statuski-1;MemoryStatustemp->pfni=curre ntpage;coun time+;vpcurre ntpage.time=co un time;void mai n()int i,j,f=1;while(f)cout<<"$ 頁 面 置 換 算 法 $"<<endl;cout<<"請輸入實頁數(shù)："<<e ndl;cin»sn;init();cout<<"FIFO算法結(jié)果為："<<e ndl;for(i=0;i<

18、;N;i+)queuei=ra nd()%10;prin tf("|%3d",queuei);prin tf("n");FIFO();/顯示依次訪問20個虛頁時對應(yīng)的內(nèi)存狀態(tài)，即MemoryStatus數(shù)組的值。for(j=0;j<N;j+) if(Notl nM emoryj=1)/當訪問的這個虛頁不在內(nèi)存時，顯示將其調(diào)入內(nèi)存后的詳細內(nèi)存信息prin tf("|%3d",MemoryStatusij);elseprin tf("|%3c",32);/當訪問的這個虛頁在內(nèi)存時，內(nèi)存狀態(tài)未發(fā)生改變，故無需再顯示

19、一遍prin tf("n缺頁數(shù)為：%3dn",cou nt);float qyl=cou nt/(float)N;cout<<" 缺頁率為："<<qyl*100.0<<'%'<<e ndl;qyl=0;init();cout<<e ndl;cout<<"LRU算法結(jié)果為："<<e ndl;for(i=0;i<N;i+)prin tf("|%3d",queuei);prin tf("n");LRU();for(i=0;i<s n;i+)if(NotI nM emoryj=1)prin tf("|%3d",MemoryStatusij);elseprin tf("|%3c",32);prin tf("n缺頁數(shù)為：%3dn",cou nt);qyl=cou nt/(float)N;cout<<"缺頁率為："<<qyl*100.0<<'%'