1、精選優質文檔-傾情為你奉上操作系統課程設計專題：頁面置換算法任務：設計一個虛擬存儲區和內存工作區,編程序演示下述算法的具體實現過程,并計算訪問命中率：要求設計主界面以靈活選擇某算法，且以下算法都要實現1）先進先出算法（FIFO）2）最近最久未使用算法（LRU）3）最佳置換算法（OPT）思想：1. 最佳置換算法：最佳置換算法是一種理論上的算法，其所選擇的被淘汰頁面，將是以后永不使用的，或者是在最長（未來）時間內不再被訪問的頁面。采用最佳置換算法，通常可保證獲得最低的缺頁率。7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 177722224440000000777000

2、00333222221111100001111000333332222212. 先進先出頁面置換算法:這是最早出現的置換算法。該算法總是淘汰最先進入內存的頁面，即使選擇在內存中駐留時間最久的頁面予以淘汰。該算法實現簡單，只需把一個進程已調入內存的頁面，按先后次序連接成一個隊列，并設置一個指針，成為替換指針，使它總是指向最老的頁面。但該算法與進程實際運行的規律不相適應，因為在進程中，有些頁面經常被訪問，所以先進先出算法并不能保證這些頁面不被淘汰。7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 17772222444000111111100000000033333300

3、000001113332222222227773. 最近最久未使用置換算法：最久最久未使用的頁面置換算法，是根據頁面調入的先后的使用情況進行決策的。該算法賦予每個頁面一個訪問字段，用來記錄一個頁面自上次被訪問以來經歷的時間t，當須淘汰一個頁面時，選擇現有頁面中其t值最大的，即使最近最久未使用的頁面予以淘汰。最近最久未使用算法7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1777222222222222227770000000444000000000000111333333331111111任務目的：1通過模擬實現請求頁式存儲管理的幾種基本頁面置換算法，了解虛擬儲技

4、術的特點。2通過對頁面、頁表、地址轉換和頁面置換過程的模擬，加深對請求調頁系統的原理和實現過程的理解。3掌握虛擬存儲請求頁式存儲管理中幾種基本頁面置換算法的基本思想和實現過程，并比較它們的效率。方案：輸入頁面序列，缺頁時按FIFO、LRU、OPT的策略進行頁面置換，輸出置換情況和缺頁次數。假設頁面數不超過pSIZE。process20表示簡化了的頁表，只包含頁號序列。mSIZE表示分配給該進程的塊數。Count用來表示置換次數。初始化：輸入分配的塊數mSIZE，輸入頁面序列，存放于數組process20中。按照循環，依次查找頁面是否存在于頁表中，不存在則置換頁面，初始為0，變化同上。格式化依次

5、輸出訪問下一個頁面后的頁表，然后輸出缺頁中斷總次數框圖：程序：#include #include #define mSIZE 3#define pSIZE 20static int memerymSIZE=0,0,0;static int processpSIZE=0;void FIFO();void LRU();void OPT();int main() int code,password; get(); do printf(-n); printf(| * * * |n); printf(| 1.FIFO * * * * * |n); printf(| * * |n); printf(| 2

6、.LRU * * * * * * * |n); printf(| * * * * * * * * |n); printf(| 3.OPT * * * * * * |n); printf(| * * * * * * * |n); printf(| 4.EXIT * * * * * * |n); printf(-*-n); printf(enter your choice:); scanf(%d,&code); switch(code) case 1: FIFO(); break; case 2: LRU(); break; case 3: OPT(); break; case 4:break;

7、while (code!=4); system(PAUSE); return 0;get() int i,n; for(i=0;i20;i+) printf(process%d=,i); scanf(%d,&processi) ; printf(n); void FIFO() int memerymSIZE=0,0,0; int timemSIZE=0,0,0; int i,j,k; int max=0; int count=0; for(i=0;ipSIZE;i+) printf(%d ,processi); printf(n); for(i=0;imSIZE;i+) memeryi=pro

8、cessi; timei=i; for(j=0;jmSIZE;j+) printf(%d ,memeryj); printf(n); /*前mSIZE個數直接放入*/ for(i=mSIZE;ipSIZE;i+) for(j=0,k=0;jmSIZE;j+) if(memeryj!=processi) k+; /*判斷新頁面號是否在物理塊中*/ if(k=mSIZE)/*如果都不在物理塊中*/ count+; if(time0time1) max=0; else max=1; if(time2timemax) max=2; memerymax=processi; timemax=i; for(

9、j=0;jmSIZE;j+) printf(%d ,memeryj); printf(n); else for(j=0;jmSIZE;j+) printf(%d ,memeryj); printf(n); printf(time:%dn,count); printf(min zhong lv=%d%,(20-count)*100/20); getch();void LRU() int memerymSIZE=0,0,0; int flagmSIZE=0,0,0; int i,j,k; int max=0,maxflag=0; int count=0; for(i=0;ipSIZE;i+) pr

10、intf(%d ,processi); printf(n); for(i=0;imSIZE;i+) memeryi=processi; flagi=i; for(j=0;jmSIZE;j+) printf(%d ,memeryj); printf(n); /*前mSIZE個數直接放入*/ for(i=mSIZE;ipSIZE;i+) for(j=0,k=0;jmSIZE;j+) if(memeryj!=processi) k+; else flagj=i; /*判斷新頁面號是否在物理塊中*/ if(k=mSIZE)/*如果都不在物理塊中*/ count+; if(flag0flag1) max

11、=0; else max=1; if(flag2flagmax) max=2; memerymax=processi; flagmax=i; for(j=0;jmSIZE;j+) printf(%d ,memeryj); printf(n); else for(j=0;jmSIZE;j+) printf(%d ,memeryj); printf(n); printf(time:%dn,count); printf(min zhong lv=%d%,(20-count)*100/20); getch();void OPT() int memerymSIZE = 0,0,0; int nextmS

12、IZE=0; int i,j,k,l; int count=0,maxnext,max; for(i=0;ipSIZE;i+) printf(%d ,processi); printf(n); for(i=0;imSIZE;i+) memeryi=processi; for(j=0;jmSIZE;j+) printf(%d ,memeryj); printf(n); /*前mSIZE個數直接放入*/ for(i=mSIZE;ipSIZE;i+) for(j=0,k=0;jmSIZE;j+) if(memeryj!=processi) k+; /*判斷新頁面號是否在物理塊中*/ if(k=mSI

13、ZE)/*如果都不在物理塊中*/ count+; for(l=i+1;lpSIZE;l+) if(memery0=processl) next0=l; goto lin1; next0=l; goto lin1; lin1:for(l=i+1;lpSIZE;l+) if(memery1=processl) next1=l; goto lin2; next1=l; goto lin2; lin2:for(l=i+1;l=next1) max=0; else max=1; if(next2=nextmax) max=2; memerymax=processi; for(j=0;jmSIZE;j+) printf(%d ,memeryj); printf(n); else for(j=0;jmSIZE;j+) printf(%d ,memeryj); printf(n); printf(time=%dn,count); printf(min zhong lv=%d%,(20-count)*100/20);getch()