操作系統(tǒng)頁面置換算法課程設(shè)計論文

1、操作系統(tǒng)課程設(shè)計任務(wù)書題目：常用頁面置換算法模擬實驗學(xué)生姓名： 學(xué)號： 班級： 題目類型：軟件工程（r） 指導(dǎo)教師： 一、設(shè)計目的學(xué)生通過該題目的設(shè)計過程，掌握常用頁面置換算法的原理、軟件開發(fā)方法并提高解決實際問題的能力。二、設(shè)計任務(wù)1、了解unix的命令及使用格式，熟悉unix/linux的常用基本命令，練習(xí)并掌握unix提供的vi編輯器來編譯c程序，學(xué)會利用gcc、gdb編譯、調(diào)試c程序。2、設(shè)計一個虛擬存儲區(qū)和內(nèi)存工作區(qū)，并使用最佳淘汰算法（opt）、先進先出算法（fifo）、最近最久未使用算法（lru）計算訪問命中率。（命中率頁面失效次數(shù)頁地址流長度）三、設(shè)計要求1、 分析設(shè)計要求，給

2、出解決方案（要說明設(shè)計實現(xiàn)所用的原理、采用的數(shù)據(jù)結(jié)構(gòu)）。2、 設(shè)計合適的測試用例，對得到的運行結(jié)果要有分析。3、 設(shè)計中遇到的問題，設(shè)計的心得體會。4、文檔：課程設(shè)計打印文檔每個學(xué)生一份，并裝在統(tǒng)一的資料袋中。 5、光盤：每個學(xué)生的文檔和程序資料建在一個以自己學(xué)號和姓名命名的文件夾下，刻錄一張光盤，裝入資料袋中。四、 提交的成果1. 設(shè)計說明書一份，內(nèi)容包括：1) 中文摘要100字；關(guān)鍵詞3-5個；2) 設(shè)計思想；3）各模塊的偽碼算法；4）函數(shù)的調(diào)用關(guān)系圖；5）測試結(jié)果；6）源程序（帶注釋）；7）設(shè)計總結(jié)；8) 參考文獻、致謝等。2. 刻制光盤一張。五、 主要參考文獻1. 湯子瀛，哲鳳屏.計算

3、機操作系統(tǒng).西安電子科技大學(xué)學(xué)出版社.2. 王清，李光明.計算機操作系統(tǒng).冶金工業(yè)出版社.3.孫鐘秀等. 操作系統(tǒng)教程. 高等教育出版社4.曾明. linux操作系統(tǒng)應(yīng)用教程. 陜西科學(xué)技術(shù)出版社. 5. 張麗芬，劉利雄.操作系統(tǒng)實驗教程. 清華大學(xué)出版社.6. 孟靜，操作系統(tǒng)教程原理和實例分析. 高等教育出版社7. 周長林，計算機操作系統(tǒng)教程. 高等教育出版社8. 張堯?qū)W，計算機操作系統(tǒng)教程，清華大學(xué)出版社9. 任滿杰，操作系統(tǒng)原理實用教程，電子工業(yè)出版社10.張坤.操作系統(tǒng)實驗教程，清華大學(xué)出版社六、 各階段時間安排（共2周）周次日期內(nèi)容地點第1周星期一二教師講解設(shè)計要求查找參考資料教室圖

4、書館星期三五算法設(shè)計，編程實現(xiàn)教室第2周星期一三算法設(shè)計，編程實現(xiàn)教室星期四五檢查程序，答辯教室 2013年12月9日摘 要操作系統(tǒng)是管理計算機系統(tǒng)的全部硬件資源包括軟件資源及數(shù)據(jù)資源,控制程序運行改善人機界面,為其它應(yīng)用軟件提供支持等，使計算機系統(tǒng)所有資源最大限度地發(fā)揮作用，為用戶提供方便的、有效的、友善的服務(wù)界面。操作系統(tǒng)是一個龐大的管理控制程序，大致包括5個方面的管理功能:進程與處理機管理、作業(yè)管理、存儲管理、設(shè)備管理、文件管理。在地址映射過程中，若在頁面中發(fā)現(xiàn)所要訪問的頁面不再內(nèi)存中，則產(chǎn)生缺頁中斷。當發(fā)生缺頁中斷時操作系統(tǒng)必須在內(nèi)存選擇一個頁面將其移出內(nèi)存，以便為即將調(diào)入的頁面讓出空

5、間。而用來選擇淘汰哪一頁的規(guī)則叫做頁面置換算法（page-replacement algorithms）。本次課程設(shè)計應(yīng)用請求分頁調(diào)度算法opt、fifo和lru模擬頁面調(diào)度算法，并提供性能比較分析功能。 關(guān)鍵詞：操作系統(tǒng)；頁面置換算法；lru算法；opt算法；fifo算法目 錄1 緒論11.1問題的提出11.2國內(nèi)外研究的現(xiàn)狀11.3設(shè)計思想12 偽碼算法32.1先進先出頁面置換算法32.2最近最久未使用置換算法42.3最佳置換算法63 函數(shù)調(diào)用關(guān)系圖84 運行結(jié)果95 結(jié)論11參考文獻12致 謝13附錄141緒論1.1問題的提出 在存儲器管理方式中，有一個特點，就是當要求作業(yè)全部裝入內(nèi)存才

6、能運行。但是這樣就存在兩種情況：（1）有的作業(yè)很大，不能全部裝入內(nèi)存，致使作業(yè)無法進行。（2）有大量作業(yè)要求運行時，內(nèi)存容量不足容納所有作業(yè)，而虛擬內(nèi)存技術(shù)正是在邏輯上擴充內(nèi)存容量，將會解決以上兩個問題。所以，可以當進程開始運行時，先將一部分程序裝入內(nèi)存，另一部分暫時留在外存；當要執(zhí)行的指令不在內(nèi)存時，由系統(tǒng)自動完成將它們從外存調(diào)入內(nèi)存的工作；當沒有足夠的內(nèi)存空間時系統(tǒng)自動選擇部分內(nèi)存空間，將其中原有的內(nèi)容交換到磁盤上，并釋放這些內(nèi)存空間供其它進程使用。通常，把選擇換出頁面的算法稱為頁面置換算法，模擬頁面置換算法用以客觀解決內(nèi)存不足的矛盾。 1.2國內(nèi)外研究的現(xiàn)狀 1961年英國曼徹斯特大學(xué)推

7、出了“虛擬存儲”管理技術(shù)，并在atras計算機上實現(xiàn)這一技術(shù)，70年代以后，這一技術(shù)才真正廣泛使用，目前許多大型計算機均采用此技術(shù)。虛擬存儲管理技術(shù)的關(guān)鍵在于頁面置換算法的選擇。1966年belady在理論上提出最優(yōu)頁面置換算法(optimal replacement algorithm, opt)，此外還有先進先出置換算法(first input first output, fifo) ，最近最少使用頁面置換算法(least recently used, lru)，最少使用頁面置換算法(least frequent used, lfu，或最不常用算法），時鐘置換算法（clock，或稱最近未使

8、用頁面置換算法(not used recently, nur)），頁面緩沖（page buffering）置換算法等。1.3設(shè)計思想選擇置換算法，先輸入所有頁面號，為系統(tǒng)分配物理塊，依次進行置換: 1.先進先出頁面置換算法(fifo)：這是最早出現(xiàn)的置換算法。該算法總是淘汰最先進入內(nèi)存的頁面，即選擇在內(nèi)存中駐留時間最久的頁面予以淘汰。該算法實現(xiàn)簡單只需把一個進程已調(diào)入內(nèi)存的頁面，按先后次序存入一個時間數(shù)組，并將其中時間值最大的頁面進行淘汰，并替換入新的頁面就可以實現(xiàn)。2.最近最久未使用頁面置換算法(lru)：算法的基本思想：當需要淘汰某一頁時，選擇離當前時間最近的一段時間內(nèi)最久沒有使用過的頁先

9、淘汰。該算法的主要出發(fā)點是，如果某頁被訪問了，則它可能馬上還被訪問?；蛘叻催^來說，如果某頁很長時間未被訪問，則它在最近一段時間不會被訪問。3.最佳頁面置換置換算法(opt)：其所選擇的被淘汰頁面，將是永不使用的，或者是在最長時間內(nèi)不再被訪問的頁面?？杀ＷC獲得最低的缺頁率。但由于人們目前還無法預(yù)知一個進程在內(nèi)存的若干個頁面中，哪一個頁面是未來最長時間內(nèi)不再被訪問的，因而該算法也是無法實現(xiàn)的。但是可利用該算法去評價其它算法。2偽碼算法2.1先進先出頁面置換算法void fifo() int memery10=0; int time10=0; /*記錄進入物理塊的時間*/ int i,j,k,m;

10、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) /*如果不在物理塊中*/ count+;/*計算換出頁*/max=time0time1?0:1;for(m=2;mmsize;m

11、+)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);2.2最近最久未使用置換算法void lru() int memery10=0; int flag10=0; /*記錄頁面的訪問時間*/ int i,j,k,m; int max=0; /*記錄換出頁*/ int count=0; /*記錄置換次數(shù)*/*前msize個

12、數(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(flagmflagmax)ma

13、x=m; memerymax=pagei; flagmax=i; /*記錄該頁的訪問時間*/ for(j=0;jmsize;j+) tempij=memeryj; else for(j=0;jmsize;j+) tempij=memeryj; compute();print(count);2.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+)

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

15、(j=0;jmsize;j+)tempij=memeryj; else for(j=0;jmsize;j+) tempij=memeryj; compute();print(count);3函數(shù)調(diào)用關(guān)系圖 頁面置換算法流程圖如下：開始載入頁號序列，從第0號得到頁號將頁號放入物理塊中，編號加1引用串編號大于物理塊數(shù)？nyy頁號在物理塊?y根據(jù)選擇的置換算法完成置換y頁序列號載完？y結(jié)束圖3.1頁面置換算法流程圖4運行結(jié)果圖4.1初始化操作圖4.2數(shù)據(jù)載入圖4.3選擇界面圖4.4 fifo算法圖4.5 lru算法圖4.6 opt算法圖4.7選擇退出界面圖4.8退出界面5結(jié)論頁面置換算法是操作系統(tǒng)中

16、對虛擬存儲技術(shù)中必不可少的一種置換算法,由于本次設(shè)計中要求用先進先出（fifo）、最近最久未使用頁面置換（lru）和最佳頁面置換（opt）算法來模擬，因此對其他的一些算法就沒有涉及到，但是在學(xué)習(xí)操作系統(tǒng)的時候，都有涉及一些其他的算法，這是在完成課程同時需要掌握的內(nèi)容。頁面走向是根據(jù)用戶輸入頁面走向長度和頁表長度隨機上的布局產(chǎn)生的，在編寫程序的時候要確保自己把算法寫對了，就要多次進行數(shù)據(jù)驗證有時fifo、lru和opt產(chǎn)生的缺頁數(shù)和缺頁率會相同，這都是可以存在的。本次設(shè)計中對于界面的設(shè)計點不是很漂亮，需要進一步的改進。通過這次課程設(shè)計的實現(xiàn)操作，真切的感受到文件系統(tǒng)對一個操作系統(tǒng)的重要性，其作用

17、領(lǐng)域幾乎涵蓋了操作系統(tǒng)的所有文件，所有屬性等，對各種文件的操作都是基于文件系統(tǒng)來完成的，體現(xiàn)出了文件系統(tǒng)在目前任何操作系統(tǒng)的意義和重要性。另外在本次課程設(shè)計的過程中，通過向指導(dǎo)老師請教，在網(wǎng)上以及圖書館搜索相關(guān)信息大大的加深了對操作系統(tǒng)文件管理的理解和認識，并對操作系統(tǒng)某些領(lǐng)域的產(chǎn)生了興趣，為以后的繼續(xù)深研操作系統(tǒng)打下了理論、實踐和興趣基礎(chǔ)，收益很大！參考文獻1 嚴蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)(c語言版).清華大學(xué)出版社. 2005.2 湯小丹，梁紅兵，哲鳳屏，湯子嬴.計算機操作系統(tǒng)（第三版）.西安電子科技大學(xué)出版社. 2007.3湯子瀛，哲鳳屏.計算機操作系統(tǒng).西安電子科技大學(xué)出版社.2005.4

18、孟慶昌.牛欣源.linux教程（第2版）.北京電子工業(yè)出版社.2007.3張瓊.嵌入式linux應(yīng)用程序開發(fā)詳解.北京人民郵電出版社.2005. 4 李巖等.計算機操作系統(tǒng).北京中國電力出版社.2009.5 c#高級編程.李銘.清華大學(xué)出版社.2009.7 譚浩強.c語言程序設(shè)計.清華大學(xué)出版社.2005.8 于帆, 趙妮.程序設(shè)計基礎(chǔ)(c語言版).清華大學(xué)出版社.2006.致 謝首先感謝學(xué)校為我們安排的這次課程設(shè)計，通過這次課程設(shè)計，我收獲了很多，在很多方面得到了鍛煉提高。例如，對于計算機是如何利用很小的內(nèi)存空間運行很大的應(yīng)用程序，以前對這個概念是懵懵懂懂，但要自己真正的描述出來肯定是摸不著

19、頭腦的，只知道是利用了虛擬存儲技術(shù)。但是通過此次課程設(shè)計對虛擬存儲技術(shù)的描繪，模擬，深深理解了它的方式方法及其所有優(yōu)點、可行性，并通過不斷地調(diào)試加深了印象。同時也要感謝教我們的輔導(dǎo)老師郭老師和賈老師，沒有老師的悉心教導(dǎo)我是不可能順利的完成此次課程設(shè)計；同時，還要感謝幫助過我的同學(xué)，其實在沒有上機的時候我也在做課程設(shè)計，但此時也遇到一些問題不能及時請老師解決，所以我就請同學(xué)幫忙。我知道其他同學(xué)也很忙，也要做很多學(xué)習(xí)作業(yè)，但是他們還是很主動的幫助了我，真的很感謝他們，沒有他們，我也不可能這么順利地完成此次課程設(shè)計。附 錄本程序的源代碼如下所示（使用c語言）：#include #include /*

20、全局變量*/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();/*輔助函數(shù)*/void print(unsigned int t);void designby();void download();void mdelay(unsigned int delay);/*主函數(shù)*/int m

21、ain() int i,k,code;system(color 0a);designby();printf(請按任意鍵進行初始化操作. n);printf(*n);printf( );void getch();system(cls);system(color 0b);printf(請輸入物理塊的個數(shù)(m=10)：);scanf(%d,&msize);printf(請輸入頁面號引用串的個數(shù)(p=100)：);scanf(%d,&psize);puts(請依次輸入頁面號引用串(連續(xù)輸入，無需隔開)：);for(i=0;ipsize;i+) scanf(%1d,&pagei);download();

22、system(cls);system(color 0e); do puts(輸入的頁面號引用串為：);for(k=0;k=(psize-1)/20;k+)for(i=20*k;(ipsize)&(i);void getch();system(cls); while (code!=4); void getch();/*載入數(shù)據(jù)*/void download()int i;system(color 0d);printf(*n);printf(正在載入數(shù)據(jù)，請稍候 !n);printf(*n);printf(loading.n);printf( o);for(i=0;i51;i+)printf(b)

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

24、d 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*k;(ipsize)&(i20*(k+1);i+)for(flag=0

25、,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);printf(置換次數(shù)：%dtt,t);printf(訪問命中率：%d%n,(psize-(t+msize)*100/psize);printf(-n);/*計算過程延遲*/voi

26、d 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 memery10=0; int time10=0; /*記錄進入物理塊的時間*/ int i,j,k,m; int max=0; /*記錄換出頁*/ int count=0; /*記錄置

27、換次數(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(timemtimemax)max=m; memerymax=pa

28、gei; 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 max=0; /*記錄換出頁*/ int count=0; /*記錄置換次數(shù)*/*前msize個數(shù)直接放入*/ for(i=0;imsize;i+) memeryi=pagei; flagi=i; for(j=0