1、 操作系統(tǒng)課程設(shè)計(jì)報(bào)告學(xué) 院： 學(xué)生姓名: 學(xué) 號(hào): 題 目： Clock 及改進(jìn) Clock置換算法實(shí)現(xiàn)指 導(dǎo) 教 師: 一、 課程設(shè)計(jì)目的操作系統(tǒng)課程設(shè)計(jì)是計(jì)算機(jī)專業(yè)重要的教學(xué)環(huán)節(jié)，它為學(xué)生提供了一個(gè)既動(dòng)手又動(dòng)腦，將課本上的理論知識(shí)和實(shí)際有機(jī)的結(jié)合起來(lái)，獨(dú)立分析和解決實(shí)際問(wèn)題的機(jī)會(huì)。 l 進(jìn)一步鞏固和復(fù)習(xí)操作系統(tǒng)的基礎(chǔ)知識(shí)。 l 培養(yǎng)學(xué)生結(jié)構(gòu)化程序、模塊化程序設(shè)計(jì)的方法和能力。 l 提高學(xué)生調(diào)試程序的技巧和軟件設(shè)計(jì)的能力。l 提高學(xué)生分析問(wèn)題、解決問(wèn)題以及綜合利用 C 語(yǔ)言進(jìn)行程序設(shè)計(jì)的能力。二、 課程設(shè)計(jì)內(nèi)容與要求：模擬實(shí)現(xiàn)Clock及改進(jìn)Clock置換算法，程序應(yīng)按照Clock置換算法

2、及改進(jìn)Clock置換算法模擬實(shí)現(xiàn)頁(yè)面的置換。1不同的功能使用不同的函數(shù)實(shí)現(xiàn)（模塊化），對(duì)每個(gè)函數(shù)的功能和調(diào)用接口要注釋清楚。對(duì)程序其它部分也進(jìn)行必要的注釋。 2對(duì)系統(tǒng)進(jìn)行功能模塊分析、畫(huà)出總流程圖和各模塊流程圖。 3用戶界面要求使用方便、簡(jiǎn)潔明了、美觀大方、格式統(tǒng)一。所有功能可以反復(fù)使用，最好使用菜單。 4通過(guò)命令行相應(yīng)選項(xiàng)能直接進(jìn)入某個(gè)相應(yīng)菜單選項(xiàng)的功能模塊。 5所有程序需調(diào)試通過(guò)三、 算法及關(guān)鍵數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)(1)Clock置換算法：當(dāng)采用簡(jiǎn)單Clock算法是只需為每頁(yè)設(shè)置一位訪問(wèn)位，再將內(nèi)存中的所用頁(yè)面都通過(guò)鏈接指針鏈接成一個(gè)循環(huán)隊(duì)列。當(dāng)某頁(yè)被訪問(wèn)時(shí)，其訪問(wèn)位被置1。置換算法在選擇一頁(yè)淘汰

3、時(shí)，只需檢查頁(yè)的訪問(wèn)位。如果是0，就選擇該頁(yè)換出；若為1，則重新將他置0,暫不換出，而給該頁(yè)第二次駐留內(nèi)存的機(jī)會(huì),在按照FIFO算法檢查下一個(gè)頁(yè)面。當(dāng)檢查到隊(duì)列中的最后一個(gè)頁(yè)面是，若其訪問(wèn)位仍為1，則再返回到隊(duì)首去檢查第一個(gè)頁(yè)面。（2）算法流程圖（3）改進(jìn)型Clock置換算法在將一個(gè)頁(yè)面換出時(shí)，如果該頁(yè)已被修改過(guò)，便須將該頁(yè)重新寫回到磁盤上；但如果該頁(yè)未被修改過(guò)，則不必將它拷回磁盤。在改進(jìn)型Clock算法中，除須考慮頁(yè)面的使用情況外，還須在增加一個(gè)因素，即置換代價(jià)，這樣 頁(yè)面換出時(shí)，既要是未使用過(guò)的頁(yè)面，又要是未被修改過(guò)的頁(yè)面。把同時(shí)滿足這兩個(gè)條件的頁(yè)面作為首選淘汰的頁(yè)面。由訪問(wèn)位A和修改位M

4、可以組合成下面四種類型的頁(yè)面:1類（A=0，M=0）：表示該頁(yè)最近既未被訪問(wèn)，又未被修改，是最佳淘汰頁(yè)。2類（A=0，M=0）：表示該頁(yè)最近未被訪問(wèn)，但已被修改，并不是很好的淘汰頁(yè)。3類（A=1，M=0）：表示該頁(yè)最近已被訪問(wèn)，但未被修改，該頁(yè)有可能在被訪問(wèn)。4類（A=1，M=1）：表示該頁(yè)最近已被訪問(wèn)且被修改，該頁(yè)可能再被訪問(wèn)。，執(zhí)行過(guò)程： 從查尋指針當(dāng)前位置起掃描內(nèi)存分頁(yè)循環(huán)隊(duì)列，選擇A=0且M=0的第一個(gè)頁(yè)面淘汰；若未找到，轉(zhuǎn) 開(kāi)始第二輪掃描，選擇A=0且M=1的第一個(gè)頁(yè)面淘汰，同時(shí)將經(jīng)過(guò)的所有頁(yè)面訪問(wèn)位置0；若不能找到，轉(zhuǎn)四、 程序代碼分析（1） Clock置換算法代碼實(shí)現(xiàn)void C

5、LOCK(int num)int j;if(isInside(num)cout<<"命中"<<endl;for(int i=0 ; i <A; i+) cout<<"物理塊"<<i<<"#中內(nèi)容:"<<Inside i<<endl;elseif(count = A)lost+;for(j=0; j < A; )if(statej = 0)break;elsestatej = 0;j+;j = j %3;Insidej = Pagenum;s

6、tatej = 1;for(int i=0 ; i <A; i+) cout<<"物理塊"<<i<<"#中內(nèi)容:"<<Inside i<<endl;elseInsidecount = Pagenum;count+;for(int i=0 ; i <A; i+) cout<<"物理塊"<<i<<"#中內(nèi)容:"<<Inside i<<endl;（2） 改進(jìn)Clock置換算法實(shí)現(xiàn)void L

7、CLOCK(int num)int j;if(isInside2(num)cout<<"命中"<<endl;for(int i=0 ; i <A; i+)cout<<"物理塊"<<i<<"#中內(nèi)容:"<<Inside i<<endl;elseif(count = A)lost+;j =whichpage();Insidej = Pagenum;state2j0 = 1;for(int i=0 ; i <A; i+) cout<<

8、"物理塊"<<i<<"#中內(nèi)容:"<<Inside i<<endl;elseInsidecount = Pagenum;count+;for(int i=0 ; i <A; i+)cout<<"物理塊"<<i<<"#中內(nèi)容:"<<Inside i<<endl;五程序截圖運(yùn)行截圖：六程序代碼#include<iostream>#include<stdlib.h>using name

9、space std;#define M 2int const A = 4;/內(nèi)存中存放的頁(yè)面數(shù)int count = 0;int InsideA;int const PageCount =10;/總的頁(yè)面數(shù)int PagePageCount;int insert = 0;/先到先出置換算法fcfo中表示 當(dāng)內(nèi)存滿的時(shí)候，新進(jìn)入的頁(yè)號(hào)放的位置int suiji = 0; /隨機(jī)置換算法randchange 當(dāng)內(nèi)存滿的時(shí)候，新進(jìn)入的頁(yè)號(hào)放的位置int stateA;/clock置換算法中，內(nèi)存中的每個(gè)頁(yè)面號(hào)對(duì)應(yīng)的狀態(tài)int state2AM;/ 二維數(shù)組，第一行第一列為訪問(wèn)位，第一行的第二列為修改

10、位double lost = 0.0;/檢測(cè)頁(yè)號(hào)是否在內(nèi)存中bool isInside(int num)for(int i = 0; i < A; i+)if(Insidei = Pagenum)statei = 1;return true;return false;/判斷頁(yè)面是否已經(jīng)被修改bool change()if(rand()%2+1) = 1 )cout<<"該頁(yè)面被修改"<<endl;return true;elsereturn false;/用于改進(jìn)型clock置換算法，檢測(cè)頁(yè)號(hào)是否在內(nèi)存中并把訪問(wèn)位和修改位置1bool isIn

11、side2(int num)for(int i = 0; i < A; i+)if(Insidei = Pagenum)if(change()state2i0 = 1;state2i1 = 1;elsestate2i0 = 1;return true;return false;/用于改進(jìn)型clock置換算法，判斷內(nèi)存中第幾個(gè)需要被置換int whichpage()int j;for(j=0; j < A;j+) if(state2j0 = 0&&state2j1 = 0)return j;for(j=0; j < A;j+ ) if(state2j0 = 0&

12、amp;&state2j1 = 1)return j;state2j0 = 0 ;for(j=0; j < A;j+ )state2j0 = 0 ;return whichpage();/簡(jiǎn)單Clock置換算法void CLOCK(int num)int j;if(isInside(num)cout<<"命中"<<endl;for(int i=0 ; i <A; i+) cout<<"物理塊"<<i<<"#中內(nèi)容:"<<Inside i<

13、<endl;elseif(count = A)lost+;for(j=0; j < A; )if(statej = 0)break;elsestatej = 0;j+;j = j %3;Insidej = Pagenum;statej = 1;for(int i=0 ; i <A; i+) cout<<"物理塊"<<i<<"#中內(nèi)容:"<<Inside i<<endl;elseInsidecount = Pagenum;count+;for(int i=0 ; i <A;

14、 i+) cout<<"物理塊"<<i<<"#中內(nèi)容:"<<Inside i<<endl;/改進(jìn)型clock置換算法void LCLOCK(int num)int j;if(isInside2(num)cout<<"命中"<<endl;for(int i=0 ; i <A; i+) cout<<"物理塊"<<i<<"#中內(nèi)容:"<<Inside i<&l

15、t;endl;elseif(count = A)lost+;j =whichpage();Insidej = Pagenum;state2j0 = 1;for(int i=0 ; i <A; i+) cout<<"物理塊"<<i<<"#中內(nèi)容:"<<Inside i<<endl;elseInsidecount = Pagenum;count+;for(int i=0 ; i <A; i+)cout<<"物理塊"<<i<<&quo

16、t;#中內(nèi)容:"<<Inside i<<endl;int main() char ch ; cout<<"默認(rèn)的頁(yè)號(hào)為"<<endl; for(int i = 0; i < PageCount; i+) Pagei =rand()%9 + 1;cout<<Pagei<<" " cout<<endl; while(1)cout<<"-1.Clock置換算法（CLOCK）-"<<endl;cout<<&q

17、uot;-2.改進(jìn)型Clock置換算法-"<<endl;cout<<"-0.退出-"<<endl;cout<<"-輸入進(jìn)行選擇-"<<endl;cin>>ch;switch(ch) case '1': lost = 0;count = 0;for(int m = 0; m < A; m+)statem = 0;for(int j = 0; j < A; j+)Insidej = 0;for(int i = 0; i < PageCount;

18、 i+) cout<<"讀入Page"<<i<<"="<<Pagei<<endl; CLOCK(i); cout<<"n頁(yè)面訪問(wèn)次數(shù)"<<PageCount<<"n缺頁(yè)中斷次數(shù)"<<lost<<"n缺頁(yè)率"<<lost/(PageCount)<<"n"<<endl; break; case '2': lost = 0;count = 0;for(int m = 0; m < A; m+) for(int n = 0; n < 2;n+)state2mn = 0;for(int j = 0; j < A; j+) Insidej = 0;for(int i = 0; i < PageCount; i+) cout<<"讀入Page