實(shí)驗(yàn)六 請(qǐng)求分頁(yè)存儲(chǔ)管理

1、實(shí)驗(yàn)六：實(shí)驗(yàn)六：請(qǐng)求分頁(yè)存儲(chǔ)管理一實(shí)驗(yàn)?zāi)康囊粚?shí)驗(yàn)?zāi)康纳钊肜斫庹?qǐng)求頁(yè)式存儲(chǔ)管理的基本概念和實(shí)現(xiàn)方法，重點(diǎn)認(rèn)識(shí)其中的地址變換、缺頁(yè)中斷、置換算法等實(shí)現(xiàn)思想。二實(shí)驗(yàn)屬性二實(shí)驗(yàn)屬性該實(shí)驗(yàn)為綜合性、設(shè)計(jì)性實(shí)驗(yàn)。三實(shí)驗(yàn)儀器設(shè)備及器材三實(shí)驗(yàn)儀器設(shè)備及器材普通 PC386 以上微機(jī)四實(shí)驗(yàn)要求四實(shí)驗(yàn)要求本實(shí)驗(yàn)要求 2 學(xué)時(shí)完成。本實(shí)驗(yàn)要求完成如下任務(wù)：（1） 建立相關(guān)的數(shù)據(jù)結(jié)構(gòu)：頁(yè)表、頁(yè)表寄存器、存儲(chǔ)塊表等；（2） 指定分配給進(jìn)程的內(nèi)存物理塊數(shù)，設(shè)定進(jìn)程的頁(yè)面訪問(wèn)順序； （3） 設(shè)計(jì)頁(yè)面置換算法，可以選擇 OPT、FIFO、LRU 等，并計(jì)算相應(yīng)的缺頁(yè)率，以比較它們的優(yōu)劣；（4） 編寫地址轉(zhuǎn)換函數(shù)地址轉(zhuǎn)換函數(shù)，

2、實(shí)現(xiàn)通過(guò)查找頁(yè)表完成邏輯地址到物理地址的轉(zhuǎn)換；若發(fā)生缺頁(yè)則選擇某種置換算法（OPT、FIFO、LRU 等）完成頁(yè)面的交換； （5） 將整個(gè)過(guò)程可視化顯示出來(lái)。實(shí)驗(yàn)前應(yīng)復(fù)習(xí)實(shí)驗(yàn)中所涉及的理論知識(shí)和算法，針對(duì)實(shí)驗(yàn)要求完成基本代碼編寫并完成預(yù)習(xí)報(bào)告、實(shí)驗(yàn)中認(rèn)真調(diào)試所編代碼并進(jìn)行必要的測(cè)試、記錄并分析實(shí)驗(yàn)結(jié)果。實(shí)驗(yàn)后認(rèn)真書(shū)寫符合規(guī)范格式的實(shí)驗(yàn)報(bào)告（參見(jiàn)附錄 A） ，并要求用正規(guī)的實(shí)驗(yàn)報(bào)告紙和封面裝訂整齊，按時(shí)上交。三、設(shè)計(jì)過(guò)程3.1 算法原理分析OPT 算法是未來(lái)最遠(yuǎn)出現(xiàn)，當(dāng)當(dāng)前內(nèi)存中沒(méi)有正要訪問(wèn)的頁(yè)面時(shí)，置換出當(dāng)前頁(yè)面中在未來(lái)的訪問(wèn)頁(yè)中最遠(yuǎn)出現(xiàn)的頁(yè)面或再也不出現(xiàn)的頁(yè)面。FIFO 算法是先進(jìn)先出，當(dāng)當(dāng)

3、前內(nèi)存中沒(méi)有正要訪問(wèn)的頁(yè)面時(shí)，置換出最先進(jìn)來(lái)的頁(yè)面。LRU 算法是最近最久未使用，當(dāng)當(dāng)前內(nèi)存中沒(méi)有正要訪問(wèn)的頁(yè)面時(shí)，置換出在當(dāng)前頁(yè)面中最近最久沒(méi)有使用的頁(yè)面。3.2 數(shù)據(jù)定義int length,num_page,count,seed; /length 記錄訪問(wèn)串的長(zhǎng)度，num_page 頁(yè)面數(shù)，count 記錄缺頁(yè)次數(shù)int result2030,order30,a10; /result 記錄結(jié)果,order 存儲(chǔ)訪問(wèn)串,a 存儲(chǔ)當(dāng)前頁(yè)面中的值int pos1,flag1,flag2,flag3; /pos1 位置變量，flag1 等為標(biāo)志變量char result130; /記錄缺頁(yè)數(shù)組

4、void opt() /最佳void fifo() /先進(jìn)先出 bool search(int n) /查找當(dāng)前內(nèi)存中是否已存在該頁(yè)3.3 流程圖與運(yùn)行截圖否是是否開(kāi)始得到執(zhí)行的指令指令是否在內(nèi)存中最先存入指令被淘汰下面是否還有指令結(jié)束得出命中率圖 6.1 FIFO（）函數(shù)流程圖;開(kāi)始輸入內(nèi)存中分配頁(yè)數(shù)據(jù)第一個(gè)訪問(wèn)頁(yè)初始化第一列值還有請(qǐng)求訪問(wèn)頁(yè)？直接復(fù)制前一列內(nèi)容內(nèi)存中是否已存在？?jī)?nèi)存有空頁(yè)？直接插入替換內(nèi)存中將來(lái)不出現(xiàn)或離當(dāng)前最遠(yuǎn)的頁(yè)輸出全部頁(yè)面變化情況結(jié)束否是否是否是圖 2.2 OPT 算法流程圖四、小結(jié)本次課程設(shè)計(jì)目的是通過(guò)請(qǐng)求頁(yè)式管理中頁(yè)面置換算法模擬設(shè)計(jì)，了解虛擬存儲(chǔ)技術(shù)的特點(diǎn)，掌握

5、請(qǐng)求頁(yè)式存儲(chǔ)管理的頁(yè)面置換算法。要求設(shè)計(jì)隨機(jī)頁(yè)面產(chǎn)生程序，并說(shuō)明隨機(jī)的性能和其性能可能對(duì)算法的影響，對(duì)隨機(jī)性要有一定的參數(shù)控制能力；計(jì)算并輸出 FIFO 及LRU 算法在不同內(nèi)存容量下的命中率。由于上學(xué)期做過(guò)頁(yè)面置換的實(shí)驗(yàn)，內(nèi)容包括先進(jìn)先出算法（FIFO） 、最近最久未使用頁(yè)面置換算法（LRU）和理想淘汰算法（OPT） ，3 種算法思想簡(jiǎn)單明確，選好數(shù)據(jù)結(jié)構(gòu)，思路清晰便基本沒(méi)問(wèn)題了。所以相對(duì)來(lái)說(shuō)，這次操作系統(tǒng)的課程設(shè)計(jì)容易許多，只是在之前實(shí)驗(yàn)基礎(chǔ)上，要附加設(shè)計(jì)隨機(jī)頁(yè)面產(chǎn)生程序，對(duì)隨機(jī)性要有一定的參數(shù)控制能力。對(duì)于隨機(jī)頁(yè)面產(chǎn)生程序，我們之前沒(méi)做過(guò)，在網(wǎng)上查閱資料，使用了庫(kù)函數(shù) srand（）和

6、rand（） ，實(shí)現(xiàn)了簡(jiǎn)單的隨機(jī)頁(yè)面產(chǎn)生程序，功能基本完成。我們知識(shí)所限，沒(méi)有使用漂亮可視化界面編程實(shí)現(xiàn)功能，用簡(jiǎn)單的 C 語(yǔ)言編程實(shí)現(xiàn)的。不管怎么樣，最終還是實(shí)現(xiàn)的本次課程設(shè)計(jì)要求的。五、源程序#include#includeusing namespace std;int length,num_page,count,seed;int result2030,order30,a10;int pos1,flag1,flag2,flag3;char result130;void init()memset(a,-1,sizeof(a); int i;coutlength;coutseed;srand(

7、seed);cout產(chǎn)生的隨機(jī)訪問(wèn)串:;for(i=0;ilength;i+)orderi=rand()%10;coutorderi endl; coutnum_page;void print()int i,j;cout表示缺頁(yè)endl;for( j=0;jlength;j+)printf(%2d ,orderj); coutendl;for( i=0;inum_page;i+)for( j=0;jlength;j+)if(resultij=-1) printf( );else printf(%2d ,resultij);coutendl;for( j=0;jlength;j+)printf(

8、%2c ,result1j); coutendl;cout缺頁(yè)率：count/length;printf(=%.1lf,(count*1.0)/(length*1.0)*100);cout%endl;bool search(int n) /查找當(dāng)期內(nèi)存是否已存在int i;for(i=0;inum_page;i+)if(ai=n)return true;return false;void opt() /最佳int i,pos10,flag10;while(1) flag1=flag2=0;for(i=0;ilength;i+)if(!search(orderi)count+;result1i=

9、*;if(anum_page-1!=-1) /表示當(dāng)前頁(yè)面已滿要淘汰一個(gè)memset(pos,-1,sizeof(pos);memset(flag,0,sizeof(flag);int j,k;for( j=i;jlength;j+)/找出當(dāng)前頁(yè)中的值在將來(lái)訪問(wèn)串中對(duì)應(yīng)的最近位置for( k=0;knum_page;k+)if(orderj=ak&flagk=0)posk=j; flagk=1;coutendl;int max=-10,max_pos;for( k=0;knum_page;k+)/找出位置最遠(yuǎn)的那個(gè)值if(posk=-1)/未出現(xiàn)則跳出，替換該值max_pos=k;br

10、eak;else if(maxposk)max=posk;max_pos=k;amax_pos=orderi;else /還有空頁(yè)for(int j=0;jnum_page;j+)if(aj=-1)aj=orderi; break;else result1i= ;for(int j=0;jnum_page;j+)resultji=aj;print(); if(flag1=0&flag2=0)break;void fifo() /先進(jìn)先出int i,thisn=0;while(1)count=0; flag1=flag2=0;for(i=pos1;i=num_page)thisn=0;elsefor(int j=0;jnum_page;j+)if(aj=-1)aj=orderi; break;else result1i= ;for(int j=0;jnum_page;j+)resultji=aj; print(); if(flag1=0&flag2=0)break;void main() /主函數(shù) int m;printf( 1.OPT.n);printf( 2.FIFO.n);printf( 0.退