虛擬存儲(chǔ)器管理 頁面置換算法模擬實(shí)驗(yàn)

1、淮海工學(xué)院計(jì)算機(jī)工程學(xué)院實(shí)驗(yàn)報(bào)告書課程名： 操作系統(tǒng)原理A 題 目： 虛擬存儲(chǔ)器管理 頁面置換算法模擬實(shí)驗(yàn) 班 級(jí)： 軟件* 學(xué) 號(hào)： 20*1228* 姓 名： * 評(píng)語：成績： 指導(dǎo)教師： 批閱時(shí)間： 年 月 日一、實(shí)驗(yàn)?zāi)康呐c要求1. 目的：請(qǐng)求頁式虛存管理是常用的虛擬存儲(chǔ)管理方案之一。通過請(qǐng)求頁式虛存管理中對(duì)頁面置換算法的模擬，有助于理解虛擬存儲(chǔ)技術(shù)的特點(diǎn)，并加深對(duì)請(qǐng)求頁式虛存管理的頁面調(diào)度算法的理解。2. 要求：本實(shí)驗(yàn)要求使用C語言編程模擬一個(gè)擁有若干個(gè)虛頁的進(jìn)程在給定的若干個(gè)實(shí)頁中運(yùn)行、并在缺頁中斷發(fā)生時(shí)分別使用FIFO和LRU算法進(jìn)行頁面置換的情形。其中虛頁的個(gè)數(shù)可以事先給定（例如

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

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

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

5、ree_head，初始時(shí)n個(gè)實(shí)頁都處于free鏈表中；busy鏈表用于組織已分配出去的實(shí)頁，首指針為busy_head，尾指針為busy_tail，初始值都為null。當(dāng)所要訪問的一個(gè)虛頁不在實(shí)頁中時(shí)，將產(chǎn)生缺頁中斷。此時(shí)若free鏈表不為空，就取下鏈表首指針?biāo)傅膶?shí)頁，并分配給該虛頁。若free鏈表為空，則說明n個(gè)實(shí)頁已全部分配出去，此時(shí)應(yīng)進(jìn)行頁面置換：對(duì)于FIFO算法要將busy_head 所指的實(shí)頁從busy鏈表中取下，分配給該虛頁，然后再將該實(shí)頁插入到busy鏈表尾部；對(duì)于LRU算法則要從所有已分配實(shí)頁的虛頁中找出time值為最小的虛頁，將該虛頁從裝載它的那個(gè)實(shí)頁中置換出去，并在該實(shí)頁

6、中裝入當(dāng)前正要訪問的虛頁。3、 程序流程圖 FIFO算法 LRU算法4、 主要程序清單#include#include#include#include #define M 10 /10個(gè)虛頁#define N 20 /20個(gè)頁面的訪問序列/定義虛頁的結(jié)構(gòu)typedef struct VirtualPageint pn;int pfn; int time; VirtualPage; /定義實(shí)頁的結(jié)構(gòu)typedef struct Pageint pn;int pfn; struct Page* next; Page; struct VirtualPage vpM; / 定義存放10個(gè)虛頁的數(shù)組in

7、t queueN; /定義一個(gè)數(shù)組，存放隨機(jī)生成的20個(gè)數(shù)，表示訪問虛頁的次序，里面的數(shù)值不能超過9 int count; /存放缺頁次數(shù)， 用來統(tǒng)計(jì)缺頁率。本算法沒有考慮預(yù)調(diào)頁，只要該頁不在內(nèi)存，就認(rèn)為缺頁一次。int countime; /用于LRU算法中，找出要淘汰的頁。每當(dāng)要訪問一個(gè)虛頁面時(shí)，countime的值加1，然后將所要訪問的虛頁的time項(xiàng)值設(shè)置為增值后的當(dāng)前countime值int NotInMemoryN; /表示每次虛頁訪問是否在內(nèi)存struct Page *Free,*Free_head,*Busy,*Busy_tail,*Busy_head,*temp; void

8、init(Page pp,int MemoryStatusN,int L) int i,j;count=0;countime=0;/初始化10個(gè)虛頁 for(i=0;iM;i+) vpi.pn=i; vpi.pfn=-1; vpi.time=0;/初始化5個(gè)實(shí)頁，并將其串成鏈表形式 for(i=0;iL;i+) ppi.pn=-1; ppi.pfn=i; ppi.next=NULL;/將5個(gè)實(shí)頁依次相連，形成Free鏈表Free=&pp0;for(i=0;iL-1;i+)ppi.next=&ppi+1;ppL-1.next=NULL;Free_head=Free; /初始化Busy鏈表Busy

9、=NULL;Busy_head=NULL;Busy_tail=NULL;/初始化MemoryStatus數(shù)組for(i=0;iL;i+)for(j=0;jN;j+)MemoryStatusij=-1;/初始化NotInMemory數(shù)組for(i=0;iN;i+) NotInMemoryi=1;void FIFO(int L,int MemoryStatusN) /先入先出算法的具體實(shí)現(xiàn)。count=0; int i,j,k,currentpage; /一些臨時(shí)變量for(i=0;iN;i+) /這是主循環(huán)，每次處理一個(gè)虛頁訪問。直到把20個(gè)虛頁處理完為止。 /當(dāng)前訪問的虛頁是哪一頁？ 由數(shù)組q

10、ueuei中的值表示currentpage=queuei; /判斷該虛頁是否已經(jīng)調(diào)入內(nèi)存if(vpcurrentpage.pfn!=-1) /表示該頁已經(jīng)在內(nèi)存中，可以直接訪問。同時(shí)記錄訪問該頁時(shí)對(duì)應(yīng)的實(shí)頁信息（和前一頁相同）for(j=0;jnext; Free=Free_head; /將虛頁currentpage裝入temp指向的實(shí)頁，該實(shí)頁的編號(hào)為temp-pfn vpcurrentpage.pfn=temp-pfn; temp-pn=currentpage; /將temp指向的實(shí)頁插入Busy鏈表的末尾 temp-next=NULL; if(Busy=NULL) /如果是第一次把虛頁裝

11、入實(shí)頁，則temp就是Busy鏈表的第一個(gè)元素。 Busy=temp; Busy_head=Busy; Busy_tail=Busy; else /如果不是第一次把虛頁裝入實(shí)頁，則將temp插入Busy鏈表的隊(duì)尾。 Busy_tail-next=temp; Busy_tail=temp; /修改內(nèi)存狀態(tài) for(k=0;kpfni=currentpage; /虛頁currentpage裝入了temp-pfn表示的那個(gè)實(shí)頁里 else /如果Free鏈表為空，需要置換一頁出去。由于采用FIFO算法，故取busy鏈表的隊(duì)首元素，將其置換出去，修改信息后插入隊(duì)尾。 /將Busy首元素取出，賦給tem

12、p temp=Busy; Busy_head=Busy-next; Busy=Busy_head; /將當(dāng)前虛頁currentpage裝入temp指向的實(shí)頁，修改其信息 vptemp-pn.pfn=-1; /該頁被置換出去了，所以其pfn字段要設(shè)置成-1，表示其已經(jīng)不再內(nèi)存。 vpcurrentpage.pfn=temp-pfn; /currentpage被裝入內(nèi)存，更新其pfn字段為temp指向的實(shí)頁。 temp-pn=currentpage; /temp指向的實(shí)頁，裝入了currentpage虛頁 /將temp指向的實(shí)頁插入Busy鏈表的末尾,此時(shí)不用再考慮Busy是否為空了。 temp-

13、next=NULL; Busy_tail-next=temp; Busy_tail=temp; /修改內(nèi)存狀態(tài) for(k=0;kpfni=currentpage; /虛頁currentpage裝入了temp-pfn表示的那個(gè)實(shí)頁里 void LRU(Page pp,int MemoryStatusN,int L)int i,j,k,currentpage;for(i=0;iN;i+)currentpage=queuei;if(vpcurrentpage.pfn!=-1)for(j=0;jnext;Free=Free_head;vpcurrentpage.pfn=temp-pfn;temp-p

14、n=currentpage;temp-next=NULL;if(Busy=NULL)Busy=temp;Busy_head=Busy;Busy_tail=Busy;elseBusy_tail-next=temp;Busy_tail=temp; for(k=0;kpfni=currentpage; elseint min=vppp0.pn.time;temp=&pp0;for(k=1;kL;k+)if(vpppk.pn.timepn.pfn=-1;vpcurrentpage.pfn=temp-pfn;temp-pn=currentpage;for(k=0;kpfni=currentpage; c

15、ountime+;vpcurrentpage.time=countime;int main() int i,j,flag=1,L; while(flag)printf(請(qǐng)輸入實(shí)頁的個(gè)數(shù):);scanf(%d,&L);struct Page ppL; /定義一個(gè)存放5個(gè)實(shí)頁的數(shù)組 ，在底下還要將其串成鏈表 int MemoryStatusLN;init(pp,MemoryStatus,L);printf(FIFO算法：n);srand(time(0);for(i=0;iN;i+)queuei=rand()%10;printf(|%3d,queuei);printf(n);FIFO(L,Memor

16、yStatus); /運(yùn)行FIFO() 算法/顯示依次訪問20個(gè)虛頁時(shí)對(duì)應(yīng)的內(nèi)存狀態(tài)，即MemoryStatus數(shù)組的值。for(i=0;iL;i+) for(j=0;jN;j+) if(NotInMemoryj=1) /當(dāng)訪問的這個(gè)虛頁不在內(nèi)存時(shí)，顯示將其調(diào)入內(nèi)存后的詳細(xì)內(nèi)存信息printf(|%3d,MemoryStatusij); elseprintf(|%3c,32); /當(dāng)訪問的這個(gè)虛頁在內(nèi)存時(shí)，內(nèi)存狀態(tài)未發(fā)生改變，故無需再顯示一遍。本例用空格代替，其中 32 是空格的ASCII碼 printf(n 缺頁數(shù)為:%3d,count);float rate=count/(float)N*100;printf(缺頁率為：%g%n,rate);rate=0;init(pp,MemoryStatus,L);printf(n);printf(LRU算法：n);for(i=0;iN;i+)printf(|%3d,queuei);printf(n);LRU(pp,MemoryStatus,L);for(i=0;iL;i+) for(j=0;j繼續(xù) 0-停止n);scanf(%d,&flag);prin