實驗六 請求分頁存儲管理

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

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

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

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

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

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