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

1、實(shí)驗(yàn)六：實(shí)驗(yàn)六：請(qǐng)求分頁存儲(chǔ)管理一實(shí)驗(yàn)?zāi)康囊粚?shí)驗(yàn)?zāi)康纳钊肜斫庹?qǐng)求頁式存儲(chǔ)管理的基本概念和實(shí)現(xiàn)方法，重點(diǎn)認(rèn)識(shí)其中的地址變換、缺頁中斷、置換算法等實(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)：頁表、頁表寄存器、存儲(chǔ)塊表等；（2） 指定分配給進(jìn)程的內(nèi)存物理塊數(shù)，設(shè)定進(jìn)程的頁面訪問順序； （3） 設(shè)計(jì)頁面置換算法，可以選擇 OPT、FIFO、LRU 等，并計(jì)算相應(yīng)的缺頁率，以比較它們的優(yōu)劣；（4） 編寫地址轉(zhuǎn)換函數(shù)地址轉(zhuǎn)換函數(shù)，

2、實(shí)現(xiàn)通過查找頁表完成邏輯地址到物理地址的轉(zhuǎn)換；若發(fā)生缺頁則選擇某種置換算法（OPT、FIFO、LRU 等）完成頁面的交換； （5） 將整個(gè)過程可視化顯示出來。實(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)真書寫符合規(guī)范格式的實(shí)驗(yàn)報(bào)告（參見附錄 A） ，并要求用正規(guī)的實(shí)驗(yàn)報(bào)告紙和封面裝訂整齊，按時(shí)上交。三、設(shè)計(jì)過程3.1 算法原理分析OPT 算法是未來最遠(yuǎn)出現(xiàn)，當(dāng)當(dāng)前內(nèi)存中沒有正要訪問的頁面時(shí)，置換出當(dāng)前頁面中在未來的訪問頁中最遠(yuǎn)出現(xiàn)的頁面或再也不出現(xiàn)的頁面。FIFO 算法是先進(jìn)先出，當(dāng)當(dāng)

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

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

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

6、rand（） ，實(shí)現(xiàn)了簡(jiǎn)單的隨機(jī)頁面產(chǎn)生程序，功能基本完成。我們知識(shí)所限，沒有使用漂亮可視化界面編程實(shí)現(xiàn)功能，用簡(jiǎn)單的 C 語言編程實(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ī)訪問串:;for(i=0;ilength;i+)orderi=rand()%10;coutorderi endl; coutnum_page;void print()int i,j;cout表示缺頁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缺頁率：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)前頁面已滿要淘汰一個(gè)memset(pos,-1,sizeof(pos);memset(flag,0,sizeof(flag);int j,k;for( j=i;jlength;j+)/找出當(dāng)前頁中的值在將來訪問串中對(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 /還有空頁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.退