請求頁式存儲管理中常用頁面置換算法模擬

1、計(jì)算機(jī)操作系統(tǒng)實(shí) 驗(yàn) 報(bào) 告課程名稱計(jì)算機(jī)操作系統(tǒng)實(shí)驗(yàn)項(xiàng)目名稱請求頁式存儲管理中常用頁面置換算法模擬學(xué)號20111214034班級計(jì)1103姓名韓瑤專業(yè)計(jì)算機(jī)科學(xué)與技術(shù)實(shí)驗(yàn)地點(diǎn)12j-661實(shí)驗(yàn)室 濟(jì)南大學(xué)信息科學(xué)與技術(shù)學(xué)院2013年xx月xx日一、實(shí)驗(yàn)概述1. 實(shí)驗(yàn)名稱 請求頁式存儲管理中常用頁面置換算法管理2. 實(shí)驗(yàn)?zāi)康模?）了解內(nèi)存分頁管理策略（2）掌握調(diào)頁策略（3）掌握一般常用的調(diào)度算法 （4）學(xué)會各種存儲分配算法的實(shí)現(xiàn)方法。（5）了解頁面大小和內(nèi)存實(shí)際容量對命中率的影響3. 實(shí)驗(yàn)內(nèi)容（1）采用頁式分配存儲方案，通過分別計(jì)算不同算法的命中率來比較算法的優(yōu)劣，同時(shí)也考慮頁面大小及內(nèi)存實(shí)際

2、容量對命中率的影響；（2）實(shí)現(xiàn)opt 算法 (最優(yōu)置換算法)、lru 算法 (least recently)、 fifo 算法 (first in first out)的模擬；（3）使用某種編程語言模擬頁面置換算法。二、實(shí)驗(yàn)環(huán)境c語言三、實(shí)驗(yàn)過程1. 設(shè)計(jì)思路和流程圖選擇置換算法，先輸入所有頁面號，為系統(tǒng)分配物理塊，依次進(jìn)行置換將頁號放入物理塊中，編號加1引用串編號大于物理塊數(shù)?載入頁號序列，從第0個(gè)得到頁號開始頁號在物理塊中?根據(jù)選擇的置換算法完成置換頁號序列載完?結(jié)束是否是是是是2. 算法實(shí)現(xiàn)（1）opt基本思想：是用一維數(shù)組pagepsize存儲頁面號序列，memerymsize是存儲裝

3、入物理塊中的頁面。數(shù)組nextmsize記錄物理塊中對應(yīng)頁面的最后訪問時(shí)間。每當(dāng)發(fā)生缺頁時(shí)，就從物理塊中找出最后訪問時(shí)間最大的頁面，調(diào)出該頁，換入所缺的頁面。（2）fifo基本思想：是用隊(duì)列存儲內(nèi)存中的頁面，隊(duì)列的特點(diǎn)是先進(jìn)先出，與該算法是一致的，所以每當(dāng)發(fā)生缺頁時(shí)，就從隊(duì)頭刪除一頁，而從隊(duì)尾加入缺頁?；蛘呓柚o助數(shù)組timemsize記錄物理塊中對應(yīng)頁面的進(jìn)入時(shí)間，每次需要置換時(shí)換出進(jìn)入時(shí)間最小的頁面。(3)lru基本思想：是用一維數(shù)組pagepsize存儲頁面號序列，memerymsize是存儲裝入物理塊中的頁面。數(shù)組flag10標(biāo)記頁面的訪問時(shí)間。每當(dāng)使用頁面時(shí)，刷新訪問時(shí)間。發(fā)生缺頁時(shí)

4、，就從物理塊中頁面標(biāo)記最小的一頁，調(diào)出該頁，換入所缺的頁面。3.源程序并附上注釋#include #include /*全局變量*/int msize; /*物理塊數(shù)*/int psize; /*頁面號引用串個(gè)數(shù)*/static int memery10=0; /*物理塊中的頁號*/static int page100=0; /*頁面號引用串*/static int temp10010=0; /*輔助數(shù)組*/*置換算法函數(shù)*/void fifo();void lru();void opt();/*輔助函數(shù)*/void print(unsigned int t);void designby();

5、void download();void mdelay(unsigned int delay);/*主函數(shù)*/void main() int i,k,code;system(color 0a);designby();printf(請按任意鍵進(jìn)行初始化操作. n);printf(n);printf( );getch();system(cls);system(color 0b);printf(請輸入物理塊的個(gè)數(shù)(m=10)：);scanf(%d,&msize);printf(請輸入頁面號引用串的個(gè)數(shù)(p=100)：);scanf(%d,&psize);puts(請依次輸入頁面號引用串(連續(xù)輸入，無

6、需隔開)：);for(i=0;ipsize;i+) scanf(%1d,&pagei);download();system(cls);system(color 0e); do puts(輸入的頁面號引用串為：);for(k=0;k=(psize-1)/20;k+)for(i=20*k;(ipsize)&(i);getch();system(cls); while (code!=4);getch();/*載入數(shù)據(jù)*/void download()int i;system(color 0d);printf(n);printf(正在載入數(shù)據(jù)，請稍候 !n);printf(n);printf(load

7、ing.n);printf( o);for(i=0;i51;i+)printf(b);for(i=0;i);printf(nfinish.n載入成功，按任意鍵進(jìn)入置換算法選擇界面：);getch();/*設(shè)置延遲*/void mdelay(unsigned int delay) unsigned int i; for(;delay0;delay-) for(i=0;i124;i+) printf( b); /*顯示設(shè)計(jì)者信息*/ void designby()printf(n);printf( 課題三：頁面置換算法 n);printf( 學(xué)號：20111214034 n);printf( 姓名

8、：韓瑤 n);printf(n);void print(unsigned int t)int i,j,k,l;int flag;for(k=0;k=(psize-1)/20;k+)for(i=20*k;(ipsize)&(i20*(k+1);i+)if(i+1)%20=0)|(i+1)%20)&(i=psize-1)printf(%dn,pagei);elseprintf(%d ,pagei);for(j=0;jmsize;j+)for(i=20*k;(imsize+20*k)&(i=j)printf( |%d|,tempij);elseprintf( | |);for(i=msize+20*

9、k;(ipsize)&(i20*(k+1);i+)for(flag=0,l=0;lmsize;l+)if(tempil=tempi-1l)flag+;if(flag=msize)/*頁面在物理塊中*/printf( );elseprintf( |%d|,tempij);/*每行顯示20個(gè)*/if(i%20=0)continue;printf(n);printf(-n);printf(缺頁次數(shù)：%dtt,t+msize);printf(缺頁率：%d/%dn,t+msize,psize);printf(置換次數(shù)：%dtt,t);printf(訪問命中率：%d%n,(psize-(t+msize)*

10、100/psize);printf(-n);/*計(jì)算過程延遲*/void compute()int i;printf(正在進(jìn)行相關(guān)計(jì)算，請稍候);for(i=1;i20;i+)mdelay(15);if(i%4=0)printf(bbbbbb bbbbbb);elseprintf();for(i=0;i+30;printf(b);for(i=0;i+30;printf( );for(i=0;i+30;printf(b);/*先進(jìn)先出頁面置換算法*/void fifo() int memery10=0; int time10=0; /*記錄進(jìn)入物理塊的時(shí)間*/ int i,j,k,m; int

11、max=0; /*記錄換出頁*/ int count=0; /*記錄置換次數(shù)*/*前msize個(gè)數(shù)直接放入*/ for(i=0;imsize;i+) memeryi=pagei; timei=i; for(j=0;jmsize;j+)tempij=memeryj; for(i=msize;ipsize;i+) /*判斷新頁面號是否在物理塊中*/ for(j=0,k=0;jmsize;j+) if(memeryj!=pagei) k+; if(k=msize) /*如果不在物理塊中*/ count+;/*計(jì)算換出頁*/ max=time0time1?0:1;for(m=2;mmsize;m+)i

12、f(timemtimemax)max=m; memerymax=pagei; timemax=i; /*記錄該頁進(jìn)入物理塊的時(shí)間*/ for(j=0;jmsize;j+)tempij=memeryj; else for(j=0;jmsize;j+)tempij=memeryj; compute();print(count);/*最近最久未使用置換算法*/void lru() int memery10=0; int flag10=0; /*記錄頁面的訪問時(shí)間*/ int i,j,k,m; int max=0; /*記錄換出頁*/ int count=0; /*記錄置換次數(shù)*/*前msize個(gè)數(shù)直

13、接放入*/ for(i=0;imsize;i+) memeryi=pagei; flagi=i; for(j=0;jmsize;j+)tempij=memeryj; for(i=msize;ipsize;i+) /*判斷新頁面號是否在物理塊中*/ for(j=0,k=0;jmsize;j+) if(memeryj!=pagei) k+; else flagj=i; /*刷新該頁的訪問時(shí)間*/ if(k=msize) /*如果不在物理塊中*/ count+;/*計(jì)算換出頁*/ max=flag0flag1?0:1;for(m=2;mmsize;m+)if(flagmflagmax)max=m;

14、memerymax=pagei; flagmax=i; /*記錄該頁的訪問時(shí)間*/ for(j=0;jmsize;j+)tempij=memeryj; else for(j=0;jmsize;j+)tempij=memeryj; compute();print(count);/*最佳置換算法*/void opt() int memery10=0; int next10=0; /*記錄下一次訪問時(shí)間*/ int i,j,k,l,m; int max; /*記錄換出頁*/ int count=0; /*記錄置換次數(shù)*/*前msize個(gè)數(shù)直接放入*/ for(i=0;imsize;i+) memeryi=pagei; for(j=0;jmsize;j+)tempij=memeryj; for(i=msize;ipsize;i+) /*判斷新頁面號是否在物理塊中*/ for(j=0,k=0;jmsize;j+) if(memeryj!=pagei) k+; if(k=msize) /*如果不在物理塊中*/ count+;/*得到物理快中各頁下一次訪問時(shí)間*/for(m=0;mmsize;m+)for(l=i+1;l=next1?0:1;for(m=2;mnextmax)max=m;/*下一次訪問時(shí)間都為psize,則