實驗六 請求分頁存儲管理

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

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

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

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

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

6、rand（） ，實現(xiàn)了簡單的隨機頁面產(chǎn)生程序，功能基本完成。我們知識所限，沒有使用漂亮可視化界面編程實現(xiàn)功能，用簡單的 C 語言編程實現(xiàn)的。不管怎么樣，最終還是實現(xiàn)的本次課程設(shè)計要求的。五、源程序#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)生的隨機訪問串:;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)前頁面已滿要淘汰一個memset(pos,-1,sizeof(pos);memset(flag,0,sizeof(flag);int j,k;for( j=i;jlength;j+)/找出當(dāng)前頁中的值在將來訪問串中對應(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+)/找出位置最遠的那個值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() /先進先出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.退