1、操作系統(tǒng)課程設計報告書 Clock及改進Clock置換算法實現(xiàn)班 級 姓 名 學 號 指導老師 2014年3月12日 目 錄一 、課程設計目的 . 3 二、系統(tǒng)分析與設計 . .3 三、算法流程圖： . .4四、函數(shù)模塊:.6 五、系統(tǒng)調試與結果： . .7 六、設計心得與體會： . .9 七 、源程序代碼: .15 一、課程設計目的操作系統(tǒng)課程設計是為了對學習的操作系統(tǒng)課程更深刻的理解和鞏固，對操作系統(tǒng)的整體進行一個模擬。通過實踐加深對各個部分的管理功能的認識，還能進一步分析各個部分之間的聯(lián)系，最后達到對完整系統(tǒng)的理解。同時，可以提高運用操作系統(tǒng)知識解決實際問題的能力；鍛煉實際的編程能力、創(chuàng)

2、新能力及團隊組織、協(xié)作開發(fā)軟件的能力；還能提高調查研究、查閱技術文獻、資料以及編寫軟件設計文檔的能力。課程設計是自己獨立完成一項任務的過程，編程過程中要充分調動個人的積極性，提高自身解決實際問題的能力，發(fā)現(xiàn)自身的編程錯誤習慣，提高編寫程序的質量。同時，也為以后深入層次的學習及研究打基礎。編程中少不了難題，遇到難題時需要的是用程序員的思維方式去考慮問題解決問題，還需要很大的精力和耐心，對于我們來說都是磨練和提高。二、系統(tǒng)分析與設計 在采用請求分頁機制的操作系統(tǒng)中，當運行一個程序的時候，若要訪問的頁面不在內存中而需要把它們調入內存，但此時內存已無空閑空間，為了保證該進程能正常運行，需選擇內存中暫時

3、不用的頁面調出到磁盤交換區(qū)。選擇調出哪個頁面，由頁面算法決定。頁面置換算法的好壞，直接影響系統(tǒng)的性能，所以一個好的頁面置換算法，應盡可能選擇調出較長時間內不會再訪問的頁面，以保證較低的缺頁率。2.1 Clock頁面置換原理描述 Clock算法的思想：當某一頁首次裝入內存中時，則將該頁框的使用位設置為1；當該頁隨后被訪問到時（在訪問產(chǎn)生缺頁中斷之后），它的使用位也會被設置為1。對于頁面置換算法，用于置換算法，用于置換的候選頁框集合（當前進程：局部范圍；整個內存；全局范圍）被看做是一個循環(huán)緩沖區(qū)，并且有一個指針與之相關聯(lián)。當一頁被置換時，該指針被設置成指向緩沖區(qū)中的下一頁框。當需要置換一頁時，操作

4、系統(tǒng)掃描緩沖區(qū)，以查找使用位被置為0的一頁框。每當遇到一個使用位為1的頁框時，操作系統(tǒng)就將該位重新置為0；如果在這個過程開始時，緩沖區(qū)中所有頁框的使用位均為0時，則選擇遇到的第一個頁框置換；如果所有頁框的使用位均為1時，則指針在緩沖區(qū)中完整地循環(huán)一周，把所有使用位都置為0，并且停留在最初的位置上，置換該頁框中的頁。 2.2 改進型 Clock頁面置換原理描述 改進型的Clock算法的思想：在將一個頁面換出時，如果該頁已被修改過，便須將它重新寫到磁盤上；但如果該頁未被修改過，則不必將它拷回磁盤。同時滿足這兩條件的頁面作為首先淘汰的頁。由訪問位A和修改位M可以組合成下面四種類型的頁面：1 類（A=

5、0，M=0）：表示該頁最近既未被訪問、又未被修改，是最佳淘汰頁。2 類（A=0，M=1）：表示該頁最近未被訪問，但已被修改，并不是很好的淘汰頁。3 類（A=1，M=0）：最近已被訪問，但未被修改，該頁有可能再被訪問。4 類（A=1，M=1）：最近已被訪問且被修改，該頁有可能再被訪問。 在內存中的每個頁必定是這四類頁面之一，在進行頁面置換時，其執(zhí)行過程可分成以下三步：（1）從指針所指示的當前位置開始，掃描循環(huán)隊列，尋找A=0且M=0的第一類頁面，將所遇到的第一個頁面作為所選中的淘汰頁。在第一次掃描期間不改變訪問位A。 （2） 如果第一步失敗，即查找一周后未遇到第一類頁面，則開始第二輪掃描，尋找A

6、=0且M=1的第二類頁面，將所遇到的第一個這類頁面作為淘汰頁。在第二輪掃描期間，將所有經(jīng)過的頁面的訪問位置0。 （3） 如果第二步也失敗，即未找到第二類頁面，則將指針返回到開始的位置，并將所有的訪問位復0。然后，重復第一步，如果仍失敗，必要時再重復第二步，此時就一定能夠找到被淘汰的頁。三、算法流程圖：Clock置換算法流程圖：改進型置換算法流程圖：四、函數(shù)模塊主函數(shù)模塊函數(shù)名稱：int main()功能：顯示主菜單，調用函數(shù)檢測模塊函數(shù)名稱：bool inblock(int num) 、bool inblock2(int num)功能：檢測讀入的頁號是否存在內存中、檢測頁號是否在內存中并把訪問

7、位和修改位置1修改模塊函數(shù)名稱：bool change()、int whichpage()功能：判斷頁面是否已經(jīng)被修改、判斷內存中第幾個需要被置換Clock模塊函數(shù)名稱：void CLOCK(int num)功能：實現(xiàn)Clock置換算法，完成頁面置換改進型Clock模塊函數(shù)名稱：void LCOCK(int num)功能：實現(xiàn)改進的ClockL置換算法，完成頁面置換五、系統(tǒng)調試與結果六、程序清單#include#include#include#define N 20 /虛擬內存尺寸using namespace std;int P; int const blockCount=3 ;/內存中的物

8、理塊數(shù)int count = 0;int blockblockCount;int const PageCount=15;/總的頁面數(shù)int PagePageCount;int stateblockCount;/clock置換算法中，內存中的每個頁面號對應的狀態(tài)int state2blockCount2;/ 二維數(shù)組，第一行第一列為訪問位，第一行的第二列為修改位double lost= 0.0;void generate_list(int *list,int e,int m,int t)int i,j=0,q=P,r;srand(unsigned)time(NULL);while(je)for(

9、i=j;ij+m;i+)if(i=e)break;listi=(q+rand()%e)%N; /保證在虛擬內存的頁號內j=i;r=rand()%100;if(rt)q=rand()%N;else q=(q+1)%N;/隨機生產(chǎn)是否被修改的情況，prop(0100),prop/100的概率為被修改void generate_modify(int *mo,int e,int prop)int i,t;for(i=0;iprop)moi=0;elsemoi=1;/檢測頁號是否在內存中bool inblock(int num)for(int i=0; iblockCount;i+)if(blocki

10、= Pagenum)statei = 1;return true;return false;/判斷頁面是否已經(jīng)被修改bool change()if(rand()%2+1) = 1 )printf(該頁面被修改!n);return true;elsereturn false;/用于改進型clock置換算法，檢測頁號是否在內存中并把訪問位和修改位置1bool inblock2(int num)for(int i=0;iblockCount;i+)if(blocki = Pagenum)if(change()state2i0 = 1;state2i1 = 1;elsestate2i0 = 1;ret

11、urn true;return false;/用于改進型clock置換算法，判斷內存中第幾個需要被置換int whichpage()int j;for(j=0;jblockCount;j+) if(state2j0 = 0&state2j1 = 0)return j;for(j=0;jblockCount;j+ ) if(state2j0 = 0&state2j1 = 1)return j;state2j0 = 0 ;for(j=0;jblockCount;j+ )state2j0 =0 ;return whichpage();/簡單Clock置換算法void CLOCK(int num)in

12、t j;if(inblock(num)printf(命中!n);lost+;for(int i=0;iblockCount;i+) printf(物理塊%d#中內容:%dn,i,block i);elseif(count = blockCount)/lost+;for(j=0;jblockCount; )if(statej = 0)break;elsestatej = 0;j+;j = j%3;blockj = Pagenum;statej = 1;for(int i=0;iblockCount;i+) printf(物理塊%d#中內容:%dn,i,blocki);elseblockcount

13、 = Pagenum;count+;for(int i=0;iblockCount;i+) printf(物理塊%d#中內容:%dn,i,blocki);/改進型clock置換算法void LCLOCK(int num)int j;if(inblock2(num)printf(命中!n); lost+;for(int i=0;iblockCount;i+) printf(物理塊%d#中內容:%dn,i,blocki);elseif(count = blockCount) /lost+;j = whichpage();blockj = Pagenum;state2j0 = 1;for(int i

14、=0;iblockCount;i+) printf(物理塊%d#中內容:%dn,i,blocki);elseblockcount = Pagenum;count+;for(int i=0;iblockCount;i+) printf(物理塊%d#中內容:%dn,i,blocki);int main() int aN;int moN; int A=10; int e,m,prop,t,j;printf(頁面走向為：);generate_list(a, e,m,t);generate_modify(mo,e,prop); for(int i = 0;iPageCount;i+) Pagei =ra

15、nd()%9 + 1;printf(%d ,Pagei);char ch ;printf(n);printf(tt1 Clock置換算法n);printf(tt2 改進型Clock置換算法n);printf(tt3 退出!nn);printf(請輸入算法序號:tn); while(1) scanf(%c,&ch); switch(ch) case 1:lost=0;count=0;for(int m=0;mblockCount;m+)statem = 0;for(int j=0;jblockCount;j+)blockj=0;for(int i=0;iPageCount;i+) printf(

16、讀入Page%dn,i); CLOCK(i); printf(頁面訪問次數(shù): %dn缺頁次數(shù): %0.lfn,PageCount,PageCount-lost); printf(缺頁率為:%0.001fn,(PageCount-lost)/PageCount); printf(n請輸入算法序號:t); break; case 2: lost = 0;count = 0;for(int m = 0; m blockCount; m+) for(int n = 0; n 2;n+)state2mn = 0;for(int j = 0; j blockCount; j+) blockj = 0;fo

17、r(int i = 0; i PageCount; i+) printf(讀入Page%dn,i); LCLOCK(i); printf(頁面訪問次數(shù): %dn缺頁次數(shù): %0.lfn,PageCount,PageCount-lost);printf(缺頁率為:%0.001fn,(PageCount-lost)/PageCount); printf(n請輸入算法序號:t); break;case 3:exit(0); return 0;七、實驗心得 通過這兩周的課程設計,讓我加深了對操作系統(tǒng)的認識,了解了操作系統(tǒng)中各種資源分配算法的實現(xiàn),特別是對虛擬存儲,頁面置換有了深入的了解,并能夠用高級語言進行模擬演示。不僅提高對操作系統(tǒng)的了解，這次的課程設計也使自己的C語言編程能力加強了不少。雖然自己所做的很少也不夠完善，但畢竟是我努力的結果。我也體會到，