專業(yè)課程設計I報告模板

1、通達學院專業(yè)課程設計I（2012/2013學年 第2學期）題 目： 虛擬存儲中頁面調(diào)度算法的模擬實現(xiàn) 專 業(yè) 計算機科學與技術(shù)（專轉(zhuǎn)本） 學 生 姓 名 印佳 班 級 學 號 指 導 教 師 徐小龍 指 導 單 位 計算機學院計算機科學與技術(shù)系日 期 2013年6月28日 南京郵電大學專業(yè)課程設計I指導教師成績評定表題目虛擬存儲中頁面調(diào)度算法的模擬實現(xiàn)學生姓名印佳班級學號專業(yè)計算機科學與技術(shù)評分內(nèi)容評分標準優(yōu)秀良好中等差平時成績認真對待課程設計，遵守實驗室規(guī)定，上機不遲到早退，不做和設計無關(guān)的事。設計成果設計的科學、合理性功能豐富、符合設題目要求 界面友好、外觀漂亮、大方設計的原創(chuàng)性設計報告設

2、計報告正確合理、反映系統(tǒng)設計流程文檔內(nèi)容詳實程度文檔格式規(guī)范、排版美觀答辯簡練、準確闡述設計內(nèi)容，能準確有條理回答各種問題，系統(tǒng)演示順利。評分等級優(yōu)秀、 良好、 中等、 及格、 不及格指導教師簽名或簽章日期2013-6-28備注評分等級有五種：優(yōu)秀、良好、中等、及格、不及格摘 要在地址映射過程中，若在頁面中發(fā)現(xiàn)所要訪問的頁面不再內(nèi)存中，則產(chǎn)生缺頁中斷。當發(fā)生缺頁中斷時操作系統(tǒng)必須在內(nèi)存選擇一個頁面將其移出內(nèi)存，以便為即將調(diào)入的頁面讓出空間。而用來選擇淘汰哪一頁的規(guī)則叫做頁面置換算法。在進程運行過程中，若其所要訪問的頁面不在內(nèi)存需把它們調(diào)入內(nèi)存，但內(nèi)存已無空閑空間時，為了保證該進程能正常運行，系

3、統(tǒng)必須從內(nèi)存中調(diào)出一頁程序或數(shù)據(jù)，送磁盤的對換區(qū)中。但應將哪個頁面調(diào)出，所以需要根據(jù)一定的算法來確定。常用的算法有先進先出置換算法（FIFO）, 最近最久未使用置換算法（LRU）和最佳置換算法（OPT），該設計是在VC+6.0環(huán)境下分別用LRU和FIFO來實現(xiàn)頁面置換算法的模擬程序，并測試。關(guān)鍵詞：頁面置換算法模擬程序、FIFO、LRU、OPT。1設計內(nèi)容1.1頁面置換算法及其分類在地址映射過程中，若在頁面中發(fā)現(xiàn)所要訪問的頁面不再內(nèi)存中，則產(chǎn)生缺頁中斷。當發(fā)生缺頁中斷時操作系統(tǒng)必須在內(nèi)存選擇一個頁面將其移出內(nèi) 存，以便為即將調(diào)入的頁面讓出空間。而用來選擇淘汰哪一頁的規(guī)則叫做頁面置換算法。 常見

4、的置換算法有： 1最佳置換算法（OPT）（理想置換算法） 2先進現(xiàn)出置換算法（FIFO）： 3最近最久未使用（LRU）算法 4Clock置換算法（LRU算法的近似實現(xiàn)） 5最少使用（LFU）置換算法 6頁面緩沖置換算法1.2關(guān)于頁面置換算法模擬程序問題的產(chǎn)生在各種存儲器管理方式中，有一個共同的特點，即它們都要求將一個作業(yè)全部裝入內(nèi)存方能運行，但是有兩種情況：（1） 有的作業(yè)很大，不能全部裝入內(nèi)存，致使作業(yè)無法運行；（2） 有大量作業(yè)要求運行，但內(nèi)存容量不足以容納所有這些作業(yè)。而虛擬內(nèi)存技術(shù)正式從邏輯上擴充內(nèi)存容量，將會解決以上兩個問題。從內(nèi)存中調(diào)出一頁程序或數(shù)據(jù)送磁盤的對換區(qū)中，通常，把選擇換

5、出的頁面的算法稱為頁面置換算法（Page-Replacement Algorithms）。進而頁面置換算法模擬程序能客觀的將其工作原理展現(xiàn)在我們面前。2設計目的與要求2.1掌握查看實時查看內(nèi)存、內(nèi)存回收的方法。2.2進一步掌握虛擬存儲器的實現(xiàn)方法。2.3掌握各種頁面置換算法。2.4比較各種頁面置換算法的優(yōu)缺點。2.5鍛煉知識的運用能力和實踐能力。3設計環(huán)境或器材、原理與說明3.1軟件環(huán)境Microsoft Visual C+ 6.03.2設計原理由于人們需要的內(nèi)存容量遠遠大于物理內(nèi)存容量，因而有各種策略來解決這個問題，其中最成功的是虛擬內(nèi)存技術(shù)。Linux虛擬內(nèi)存的實現(xiàn)需要6種機制的支持：地址

6、映射機制、內(nèi)存分配回收機制、緩存和刷新機制、請求頁機制、交換機制和內(nèi)存共享機制。內(nèi)存管理程序通過映射機制把用戶程序的邏輯地址映射到物理地址。當用戶程序運行時，如果發(fā)現(xiàn)程序需要的虛擬地址沒有對應的物理內(nèi)存，即發(fā)出請求頁要求。如果有空閑的內(nèi)存可供分配，就請求分配內(nèi)存（用到內(nèi)存的分配和回收），并把正在使用的物理頁記錄在緩存中（用到緩存機制）。如果沒有足夠的內(nèi)存可供分配，則調(diào)用交換機制，騰出一部分內(nèi)存。另外，在地址映射中要通過TLB（翻譯后緩存儲器）尋找物理頁；交換機制中用到交換緩存，并且把物理頁內(nèi)容交換到交換文件中，也要修改頁表來映射文件地址。3.3設計相關(guān)知識3.3.1虛擬存儲器的引入： 局部性原

7、理：程序在執(zhí)行時在一較短時間內(nèi)僅限于某個部分；相應的，它所訪問的存儲空間也局限于某個區(qū)域，它主要表現(xiàn)在以下兩個方面：時間局限性和空間局限性。3.3.2虛擬存儲器的定義： 虛擬存儲器是只具有請求調(diào)入功能和置換功能，能從邏輯上對內(nèi)存容量進行擴充的一種存儲器系統(tǒng)。3.3.3虛擬存儲器的實現(xiàn)方式： 分頁請求系統(tǒng)，它是在分頁系統(tǒng)的基礎(chǔ)上，增加了請求調(diào)頁功能、頁面置換功能所形成的頁面形式虛擬存儲系統(tǒng)。 請求分段系統(tǒng)，它是在分段系統(tǒng)的基礎(chǔ)上，增加了請求調(diào)段及分段置換功能后，所形成的段式虛擬存儲系統(tǒng)。3.3.4頁面分配： 平均分配算法，是將系統(tǒng)中所有可供分配的物理塊，平均分配給各個進程。 按比例分配算法，根據(jù)

8、進程的大小按比例分配物理塊。 考慮優(yōu)先的分配算法，把內(nèi)存中可供分配的所有物理塊分成兩部分：一部分按比例地分配給各進程；另一部分則根據(jù)個進程的優(yōu)先權(quán)，適當?shù)脑黾悠湎鄳蓊~后，分配給各進程。3.3.5頁面置換算法：常用的頁面置換算法有OPT、FIFO、LRU、Clock、LFU、PBA等。本設計主要實現(xiàn)OPT、FIFO、LRU算法。4.設計過程文檔4.1需求計劃學習虛擬存儲機制中頁面調(diào)度算法，通過編程模擬實現(xiàn)頁面調(diào)度的相關(guān)算法（FIFO、LRU和OPT算法），比較各種算法的性能。4.2需求設計選擇置換算法，先輸入所有頁面號，為系統(tǒng)分配物理塊，依次進行置換：OPT基本思想：是用一維數(shù)組pagepSI

9、ZE存儲頁面號序列，memerymSIZE是存儲裝入物理塊中的頁面。數(shù)組nextmSIZE記錄物理塊中對應頁面的最后訪問時間。每當發(fā)生缺頁時，就從物理塊中找出最后訪問時間最大的頁面，調(diào)出該頁，換入所缺的頁面?！咎貏e聲明】若物理塊中的頁面都不再使用，則每次都置換物理塊中第一個位置的頁面。FIFO基本思想：是用隊列存儲內(nèi)存中的頁面，隊列的特點是先進先出，與該算法是一致的，所以每當發(fā)生缺頁時，就從隊頭刪除一頁，而從隊尾加入缺頁。或者借助輔助數(shù)組timemSIZE記錄物理塊中對應頁面的進入時間，每次需要置換時換出進入時間最小的頁面。LRU基本思想：是用一維數(shù)組pagepSIZE存儲頁面號序列，meme

10、rymSIZE是存儲裝入物理塊中的頁面。數(shù)組flag10標記頁面的訪問時間。每當使用頁面時，刷新訪問時間。發(fā)生缺頁時，就從物理塊中頁面標記最小的一頁，調(diào)出該頁，換入所缺的頁面。4.3概要設計主要設計流程圖如下：將頁號放入物理塊中，編號加1引用串編號大于物理塊數(shù)?載入頁號序列，從第0個得到頁號開始頁號在物理塊中?根據(jù)選擇的置換算法完成置換頁號序列載完?結(jié)束是否是是是是4.4詳細設計（主要代碼）4.4.1FIFO（先進先出頁面置換算法）void FIFO() int memery10=0; int time10=0; /*記錄進入物理塊的時間*/ int i,j,k,m; int max=0; /

11、*記錄換出頁*/ int count=0; /*記錄置換次數(shù)*/*前mSIZE個數(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+;/*計算換出頁*/ max=time0time1?0:1;for(m=2;mmSIZE;m+)if(timemt

12、imemax)max=m; memerymax=pagei; timemax=i; /*記錄該頁進入物理塊的時間*/ for(j=0;jmSIZE;j+)tempij=memeryj; else for(j=0;jmSIZE;j+)tempij=memeryj; compute();print(count);4.4.2LRU最近最久未使用置換算法void LRU() int memery10=0; int flag10=0; /*記錄頁面的訪問時間*/ int i,j,k,m; int max=0; /*記錄換出頁*/ int count=0; /*記錄置換次數(shù)*/*前mSIZE個數(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; /*刷新該頁的訪問時間*/ if(k=mSIZE) /*如果不在物理塊中*/ count+;/*計算換出頁*/ max=flag0flag1?0:1;for(m=2;mmSIZE;m+)if(flagmflagmax)max=m; meme

14、rymax=pagei; flagmax=i; /*記錄該頁的訪問時間*/ for(j=0;jmSIZE;j+)tempij=memeryj; else for(j=0;jmSIZE;j+)tempij=memeryj; compute();print(count);4.4.3最佳置換算法void OPT() int memery10=0; int next10=0; /*記錄下一次訪問時間*/ int i,j,k,l,m; int max; /*記錄換出頁*/ int count=0; /*記錄置換次數(shù)*/*前mSIZE個數(shù)直接放入*/ for(i=0;imSIZE;i+) memeryi=

15、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+;/*得到物理快中各頁下一次訪問時間*/for(m=0;mmSIZE;m+)for(l=i+1;l=next1?0:1;for(m=2;mnextmax)max=m;/*下一次訪問時間都為pSIZE,則置換物理塊中第一個*/memerymax=pagei;for(j=0;jmSIZ

16、E;j+)tempij=memeryj; else for(j=0;jmSIZE;j+)tempij=memeryj; compute();print(count);4.4.4源程序代碼#include #include /*全局變量*/int mSIZE; /*物理塊數(shù)*/int pSIZE; /*頁面號引用串個數(shù)*/static int memery10=0; /*物理塊中的頁號*/static int page100=0; /*頁面號引用串*/static int temp10010=0; /*輔助數(shù)組*/*置換算法函數(shù)*/void FIFO();void LRU();void OPT(

17、);/*輔助函數(shù)*/void print(unsigned int t);void designBy();void download();void mDelay(unsigned int Delay);/*主函數(shù)*/void main() int i,k,code;system(color 0A);designBy();printf(請按任意鍵進行初始化操作. n);printf(n);printf( );getch();system(cls);system(color 0B);printf(請輸入物理塊的個數(shù)(M=10)：);scanf(%d,&mSIZE);printf(請輸入頁面號引用串

18、的個數(shù)(P=100)：);scanf(%d,&pSIZE);puts(請依次輸入頁面號引用串(連續(xù)輸入，無需隔開)：);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);

19、printf(n);printf(正在載入數(shù)據(jù)，請稍候 !n);printf(n);printf(Loading.n);printf( O);for(i=0;i51;i+)printf(b);for(i=0;i);printf(nFinish.n載入成功，按任意鍵進入置換算法選擇界面：);getch();/*設置延遲*/void mDelay(unsigned int Delay) unsigned int i; for(;Delay0;Delay-) for(i=0;i124;i+) printf( b); /*顯示設計者信息*/ void designBy()printf(n);print

20、f( 課程設計：頁面置換算法 n);printf( 學號：10006404 n);printf( 姓名：印佳 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)pr

21、intf( |%d|,tempij);elseprintf( | |);for(i=mSIZE+20*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個*/if(i%20=0)continue;printf(n);printf(-n);printf(缺頁次數(shù)：%dtt,t+mSIZE);printf(缺頁率：%d/%dn,t+mSIZE,pSIZE);prin

22、tf(置換次數(shù)：%dtt,t);printf(訪問命中率：%d%n,(pSIZE-(t+mSIZE)*100/pSIZE);printf(-n);/*計算過程延遲*/void compute()int i;printf(正在進行相關(guān)計算，請稍候);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);/*先進先出頁面置換算法*/void FIFO() int memery1

23、0=0; int time10=0; /*記錄進入物理塊的時間*/ int i,j,k,m; int max=0; /*記錄換出頁*/ int count=0; /*記錄置換次數(shù)*/*前mSIZE個數(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) /*如果不在物理塊中*/ coun

24、t+;/*計算換出頁*/ max=time0time1?0:1;for(m=2;mmSIZE;m+)if(timemtimemax)max=m; memerymax=pagei; timemax=i; /*記錄該頁進入物理塊的時間*/ 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; /*記錄頁面的訪問時間*/ int i,j,k,m; int

25、 max=0; /*記錄換出頁*/ int count=0; /*記錄置換次數(shù)*/*前mSIZE個數(shù)直接放入*/ 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; /*刷新該頁的訪問時間*/ if(k=mSIZE) /*如果不在物理塊中*/ count+;/*計算換出頁*/ max=flag0flag1?0:1;for(m=2;mmSIZE;m+)if(flagmflagma