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

1、精選優(yōu)質(zhì)文檔-傾情為你奉上淮海工學(xué)院計算機科學(xué)系實驗報告書課程名： 操作系統(tǒng)原理 題 目： 虛擬存儲器管理 頁面置換算法模擬實驗 班 級： 學(xué) 號： 姓 名： 評語：成績： 指導(dǎo)教師： 批閱時間： 年 月 日專心-專注-專業(yè)一、實驗?zāi)康呐c要求1. 目的：請求頁式虛存管理是常用的虛擬存儲管理方案之一。通過請求頁式虛存管理中對頁面置換算法的模擬，有助于理解虛擬存儲技術(shù)的特點，并加深對請求頁式虛存管理的頁面調(diào)度算法的理解。2. 要求：本實驗要求使用C語言編程模擬一個擁有若干個虛頁的進程在給定的若干個實頁中運行、并在缺頁中斷發(fā)生時分別使用FIFO和LRU算法進行頁面置換的情形。其中虛頁的個數(shù)可以事先給

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

3、。time項在FIFO算法中不使用，在LRU中用來存放對該虛頁的最近訪問時間。在實頁結(jié)構(gòu)中中，pn代表虛頁號，表示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ù)。每當(dāng)所訪問的虛頁的pfn項值不為-1，表示此虛頁已被裝入某實頁內(nèi)，此虛頁被命中，count加1。最終命中率=count/20*100%。3LRU

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

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

6、在該實頁中裝入當(dāng)前正要訪問的虛頁。三、程序流程圖1.FIFO算法2.LRU算法四、主要程序清單#include<stdlib.h>#include<stdio.h>#include<conio.h>#include <time.h>#include<iostream.h>#define M 10 /10個虛頁#define N 20 /20個頁面的訪問序列#define S 100 /實頁個數(shù)/定義虛頁的結(jié)構(gòu)typedef struct VirtualPageint pn;int pfn; int time; VirtualPage;

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

8、虛頁面時，countime的值加1，然后將所要訪問的虛頁的time項值設(shè)置為增值后的當(dāng)前countime值int MemoryStatusSN; /記錄當(dāng)訪問每一個虛頁時，內(nèi)存中的5個實頁的詳細信息。int NotInMemoryN; /表示每次虛頁訪問是否在內(nèi)存struct Page *Free,*Free_head,*Busy,*Busy_tail,*Busy_head,*temp; int sn;void init()int i,j;count=0; countime=0;/初始化10個虛頁 for(i=0;i<M;i+) vpi.pn=i; vpi.pfn=-1; vpi.tim

9、e=0;/初始化5個實頁，并將其串成鏈表形式 for(i=0;i<sn;i+) ppi.pn=-1; ppi.pfn=i; ppi.next=NULL;/將5個實頁依次相連，形成Free鏈表Free=&pp0; for(i=0;i<sn-1;i+)ppi.next=&ppi+1;ppsn-1.next=NULL;Free_head=Free; /初始化Busy鏈表Busy=NULL;Busy_head=NULL;Busy_tail=NULL;/初始化MemoryStatus數(shù)組for(i=0;i<sn;i+)for(j=0;j<N;j+)MemorySt

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

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

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

13、oryStatuski-1; MemoryStatustemp->pfni=currentpage; /虛頁currentpage裝入了temp->pfn表示的那個實頁里 else /如果Free鏈表為空，需要置換一頁出去 /將Busy首元素取出，賦給temp temp=Busy; Busy_head=Busy->next; Busy=Busy_head; /將當(dāng)前虛頁currentpage裝入temp指向的實頁，修改其信息 vptemp->pn.pfn=-1; vpcurrentpage.pfn=temp->pfn; temp->pn=currentpag

14、e; temp->next=NULL; Busy_tail->next=temp; Busy_tail=temp; /修改內(nèi)存狀態(tài) for(k=0;k<sn;k+) MemoryStatuski=MemoryStatuski-1; MemoryStatustemp->pfni=currentpage; /虛頁currentpage裝入了temp->pfn表示的那個實頁里 void LRU() int i,j,k,currentpage; for(i=0;i<N;i+) currentpage=queuei; if(vpcurrentpage.pfn!=-1)

15、 /該虛頁已經(jīng)在內(nèi)存for(j=0;j<sn;j+) MemoryStatusji=MemoryStatusji-1;NotInMemoryi=0; else /虛頁不在內(nèi)存 count=count+1; if(Free!=NULL) /還有空閑的實頁 temp=Free_head; Free_head=Free_head->next; Free=Free_head; vpcurrentpage.pfn=temp->pfn; temp->pn=currentpage; temp->next=NULL; if(Busy=NULL) Busy=temp; Busy_h

16、ead=Busy; Busy_tail=Busy; else Busy_tail->next=temp; Busy_tail=temp; for(k=0;k<sn;k+) MemoryStatuski=MemoryStatuski-1; MemoryStatustemp->pfni=currentpage; else int min=vppp0.pn.time; temp=&pp0; for(int k=1;k<sn;k+) if(vpppk.pn.time<min) min=vpppk.pn.time; temp=&ppk; vptemp->

17、;pn.pfn=-1; vpcurrentpage.pfn=temp->pfn; temp->pn=currentpage; for(k=0;k<sn;k+) MemoryStatuski=MemoryStatuski-1; MemoryStatustemp->pfni=currentpage; countime+;vpcurrentpage.time=countime;void main()int i,j,f=1;while(f)cout<<"$頁面置換算法程序$"<<endl; cout<<"請輸入實

18、頁數(shù)："<<endl; cin>>sn; init(); cout<<"FIFO算法結(jié)果為："<<endl; for(i=0;i<N;i+) queuei=rand()%10; printf("|%3d",queuei); printf("n"); FIFO(); /顯示依次訪問20個虛頁時對應(yīng)的內(nèi)存狀態(tài)，即MemoryStatus數(shù)組的值。 for(i=0;i<sn;i+) for(j=0;j<N;j+) if(NotInMemoryj=1) /當(dāng)訪問的這個虛頁不在內(nèi)存時，顯示將其調(diào)入內(nèi)存后的詳細內(nèi)存信息 printf("|%3d",MemoryStatusij); else printf("|%3c",32); /當(dāng)訪問的這個虛頁在內(nèi)存時，內(nèi)存狀態(tài)未發(fā)生改變，故無需再顯示一遍 printf("n 缺頁數(shù)為：%3dn",count); float qyl=count/(float)N; cout<<"缺頁率為："<<qyl*100.0<<&