CLOCK時(shí)鐘置換算法

1、青島理工大學(xué)操作系統(tǒng)課程設(shè)計(jì)報(bào)告院（系）：計(jì)算機(jī)工程學(xué)院專業(yè)：軟件工程學(xué)生姓名:班級(jí)：學(xué)號(hào):題目：釆用CLOCK置換算法仿真請(qǐng)求分頁系統(tǒng)起迄日期：2012.7.62012.7.13_設(shè)計(jì)地點(diǎn):實(shí)驗(yàn)樓指導(dǎo)教師：20112012年度第2學(xué)期完成日期：2012年7月12日一、課程設(shè)計(jì)目的操作系統(tǒng)課程設(shè)計(jì)是為了對(duì)學(xué)習(xí)的操作系統(tǒng)課程更深刻的理解和鞏固，對(duì)操作系統(tǒng)的整體進(jìn)行一個(gè)模擬。通過實(shí)踐加深對(duì)各個(gè)部分的管理功能的認(rèn)識(shí)，還能進(jìn)一步分析各個(gè)部分之間的聯(lián)系，最后達(dá)到對(duì)完整系統(tǒng)的理解。同時(shí)，可以提高運(yùn)用操作系統(tǒng)知識(shí)解決實(shí)際問題的能力；鍛煉實(shí)際的編程能力、創(chuàng)新能力及團(tuán)隊(duì)組織、協(xié)作開發(fā)軟件的能力；還能提高調(diào)查研究

2、、查閱技術(shù)文獻(xiàn)、資料以及編寫軟件設(shè)計(jì)文檔的能力。課程設(shè)計(jì)是自己獨(dú)立完成一項(xiàng)任務(wù)的過程，編程過程中要充分調(diào)動(dòng)個(gè)人的枳極性，提高自身解決實(shí)際問題的能力，發(fā)現(xiàn)自身的編程錯(cuò)誤習(xí)慣，提高編寫程序的質(zhì)量。同時(shí)，也為以后深入層次的學(xué)習(xí)及研究打基礎(chǔ)。編程中少不了難題，遇到難題時(shí)需要的是用程序員的思維方式去考慮問題解決問題，還需要很大的精力和耐心，對(duì)于我們來說都是磨練和提高。二、課程設(shè)計(jì)內(nèi)容與要求1、設(shè)計(jì)內(nèi)容：用高級(jí)語言編寫和調(diào)試一個(gè)內(nèi)存分配程序，加深對(duì)內(nèi)存分配算法的理解。2、設(shè)計(jì)要求：1）實(shí)現(xiàn)請(qǐng)求分頁存儲(chǔ)管理方式的頁面置換算法：CLOCK算法2）內(nèi)存物理塊數(shù)固定為15個(gè)，對(duì)多個(gè)作業(yè)采用可變分配全局置換的策略分

3、配物理塊3）作業(yè)數(shù)量與作業(yè)大?。?0-20頁）可在界面進(jìn)行設(shè)置4）所有作業(yè)按RR算法進(jìn)行調(diào)度，時(shí)間片長(zhǎng)度為1秒5）可為每個(gè)作業(yè)隨機(jī)產(chǎn)生引用的頁面串，也可以人工輸入引用的頁面串，頁面串長(zhǎng)度50-100,要求必須包拾作業(yè)所有的頁面，可作為樣例數(shù)據(jù)保存6）可讀取樣例數(shù)據(jù)（要求存放在外部文件中）進(jìn)行作業(yè)數(shù)量、作業(yè)大小、頁面串長(zhǎng)度的初始化7）要求采用可視化界面，模擬內(nèi)存分配和使用情況圖，可在運(yùn)行過程中隨時(shí)暫停，查看當(dāng)前內(nèi)存物理塊使用情況。8）每次全部作業(yè)運(yùn)行結(jié)束后，要求打印出訪問命中率三、系統(tǒng)分析與設(shè)計(jì)1、系統(tǒng)分析CLOCK頁面置換算法是根據(jù)進(jìn)程的實(shí)際需要，動(dòng)態(tài)地為之分配內(nèi)存空間。在實(shí)現(xiàn)可變分區(qū)分配時(shí)，

4、將涉及到分區(qū)分配中所用的數(shù)據(jù)結(jié)構(gòu)、分區(qū)分配算法和分區(qū)的分配和回收操作這樣三個(gè)問題。為了實(shí)現(xiàn)分區(qū)分配，系統(tǒng)中必須配置相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，用來描述空閑區(qū)和已分配區(qū)的情況，為分配提供依據(jù)。常用的數(shù)據(jù)結(jié)構(gòu)有兩種形式：空閑分區(qū)表和空閑分區(qū)鏈。為把一個(gè)新作業(yè)裝入內(nèi)存，須按照一定的算法，從空閑分區(qū)表或空閑分區(qū)鏈中選出一個(gè)分區(qū)分配給該作業(yè)。在動(dòng)態(tài)分區(qū)存儲(chǔ)管理方式中，主要操作是分配內(nèi)存和回收內(nèi)存。（1）信息。本系統(tǒng)完成的是對(duì)作業(yè)數(shù)量不固定，作業(yè)人小、進(jìn)入內(nèi)存時(shí)間、運(yùn)行時(shí)間需要通過界面進(jìn)行輸入，或者從文件讀取的作業(yè)基本信息，內(nèi)存（15一20）的處理信息是處理對(duì)于各種作業(yè)完成動(dòng)態(tài)的內(nèi)存分配，回收和緊湊。（2）行為。完全

5、描述系統(tǒng)狀態(tài)變化所需處理或功能；本系統(tǒng)處理了RR時(shí)間片輪轉(zhuǎn)算法對(duì)內(nèi)存的動(dòng)態(tài)分配，每一個(gè)作業(yè)都是按照先進(jìn)先出的原則進(jìn)入內(nèi)存當(dāng)?shù)匾粋€(gè)作業(yè)進(jìn)入內(nèi)存后，會(huì)長(zhǎng)生一個(gè)時(shí)鐘信號(hào)，依次遞增，當(dāng)一個(gè)作業(yè)從進(jìn)入時(shí)間開始到運(yùn)行時(shí)間結(jié)束，會(huì)動(dòng)態(tài)的釋放所占人小的內(nèi)存區(qū)間，直到時(shí)鐘信號(hào)等于最后一個(gè)作業(yè)釋放他所占的內(nèi)存區(qū)間，此時(shí)所有的作業(yè)運(yùn)行完，內(nèi)存也回收完。表示。詳細(xì)描述系統(tǒng)的對(duì)外接口與界面。本系統(tǒng)采用的VC編寫的，在DOS界面下運(yùn)行2、系統(tǒng)設(shè)計(jì)：系統(tǒng)利用RR時(shí)間片輪轉(zhuǎn)算法掉調(diào)度作業(yè)，并從內(nèi)存區(qū)動(dòng)態(tài)分配內(nèi)存。設(shè)內(nèi)存區(qū)的人小為number,表中每個(gè)空閑分區(qū)的人小可表示為nunber個(gè)。虛擬存儲(chǔ)區(qū)采用page類型二維數(shù)組實(shí)現(xiàn)

6、，然后將虛擬存儲(chǔ)區(qū)的首址返回給調(diào)用者。當(dāng)進(jìn)程運(yùn)行完畢釋放內(nèi)存時(shí)，系統(tǒng)根據(jù)回收區(qū)的首址，從內(nèi)存區(qū)表中按CLOCK算法找到相應(yīng)的插入點(diǎn)。2.1、模塊設(shè)計(jì)：RR算法(nextfit)(詳見程序流程圖)先將所有的進(jìn)程排成一隊(duì)，按先來先服務(wù)原則排列，先調(diào)度首進(jìn)程按時(shí)間片輪轉(zhuǎn)執(zhí)行。當(dāng)執(zhí)行到隊(duì)尾時(shí)再從頭執(zhí)行，詳細(xì)參看課本95頁333節(jié)時(shí)間片輪轉(zhuǎn)法改進(jìn)型CLOCK算法(bestfit/worstfit)根據(jù)頁面的訪問位A和修改位M確定調(diào)出頁面執(zhí)行四步循壞找出要置換頁面，詳細(xì)介紹參看課本153頁483節(jié)CLOCK置換算法虎擬存儲(chǔ)區(qū)采用的page二維數(shù)組模擬內(nèi)存區(qū)定義如卜voidMeinPageInut(mtnu

7、mber)/內(nèi)存鏈headptr=newpage;tailpti-=headpti*;fbr(mti=1;inext=newpage;tailpti*=tailptr-iiext;if(i=(number-1)tailptr-next=NULL;MemPageIinit(intnumber)虛擬存儲(chǔ)區(qū)2ProcessPagelnitO*MemPageIinit(intnumber)虛擬存儲(chǔ)區(qū)2ProcessPagelnitO*函數(shù)關(guān)系圖2.2、數(shù)據(jù)結(jié)構(gòu)說明：Strnctpage數(shù)據(jù)對(duì)象job:page的作業(yè)號(hào),int型。數(shù)據(jù)對(duì)象*next:page的后繼指針。數(shù)據(jù)對(duì)象pagelD:page的頁

8、號(hào),int型。數(shù)據(jù)對(duì)象A:訪問碼，int型。數(shù)據(jù)對(duì)象M:修改碼int型。數(shù)據(jù)關(guān)系R：數(shù)據(jù)元素同屬一個(gè)集合?；静僮鱌：MemPageIinit(intnumber)初始條件：指向newpageheadpti-指針操作結(jié)果：構(gòu)造一個(gè)number大小的指針鏈。ProcessPageliiitO初始條件：i=PPAGENUMBERl,尸PPAGENUMBER2人小page類型的二維數(shù)組。操作結(jié)果：數(shù)組各項(xiàng)賦初值。rr()初始條件：操作結(jié)果：各個(gè)作業(yè)按時(shí)間片輪轉(zhuǎn)算法調(diào)度sleep(clock_twait)初始條件：clock_t=1000操作結(jié)果：程序補(bǔ)壞一秒ClockReplace(page*pag

9、et)初始條件：指向要調(diào)入頁指針paget操作結(jié)果：按CLOCK算法調(diào)換頁面ShowPagel()初始條件：操作結(jié)果：顯示內(nèi)存調(diào)用情況。ReplacePage(page*prepti;page*ptrpage*paget)初始條件：指向要被替換掉頁面指針的前序指針preptr,指向要被替換掉頁面指針ptr,指向要調(diào)入頁指針pagetpaget操作結(jié)果：調(diào)換paget和ptr；程序中主要用到指針鏈表模擬內(nèi)存區(qū),2.3、算法流程圖：函數(shù)關(guān)系圖RR算法燈()及其調(diào)用函數(shù)sleepQitVx作業(yè)數(shù)?j=pagesi;Sleep：500)sleep(lOO)pagesi=i1=9J結(jié)束goalclock

10、()?wait)j=?頁尾sleep(clockti=0&j=Op=NULLj+;ShowPagel()ClockReplace(paget);ShowPagelQp-pageID=processpageijpageID;p=p-iiext尸？頁尾CLOCK頁面置換算法prepti*=headpti;cuipti*=headptifReplacePage(prepti;ciuptr,paget)fReplacePage(prepti;ciuptr,paget)cuiptr-A=0preptr=curptr;ciuptr=cuq)fr-next;、聲四、系統(tǒng)測(cè)試與調(diào)試分析1、系統(tǒng)測(cè)試2、調(diào)試分析

11、：進(jìn)入程序輸入1顯示隨機(jī)產(chǎn)生的多個(gè)作業(yè)的頁面信息f冃才刖丿、口卩V：wser1：6j：3eneryPageenPgelD：1:1:0133101000011313100110211：6j：3eneryPageenPgelD：1:1:013310100001131310011021111978621111i：6j：4MeneryPageMenPgelD：1A:1M:01314110001101301000113100011101199786211011111i：6j：5MeneryPageMenPgelD：1K：1:0131411000110151100011310001110119978621

12、1011111XXXXXXXXX口口卄口口口XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXHXXXXXXXXXXXXXXPageID：7382?116191474106911111115358838117141531!101314910l2:81017141371191512107154101173111151119L5312141.9211315192!1L53389n:00000000000000000000000000000000000030000000000000000000000000000000000000003000M:000000000000000000

13、0000000000000000003000000000000000000000000000000000000000300031012134I912137114136S10101215101271232141074410155Ei1495111461461411158212312416128134894159151134961L5131514414939229000000000000000000000000000000000000000000000000000000000000000000000000000000:0000000000000000000000000000000000000000

14、00000000000000000000000000000000000000輸入2開始執(zhí)行CLOCK頁面置換算法i：6J：6MenPgelD：47124151313113-I111312114A:1111111000001111:000000000001011i：llj：76MeneryPage1enPgeID：4?12415131351313111312114A:1111111100001111:000000000001011i：llj：77MeneryPageMenPgelD：471241513135631111312114A:1111111110001111:00000000000101

15、1i：llj：78MeneryPage1enPgeID：47124151313563111312114A:1111111110001111:000000000001011i：llj：79785命中率為1.8000000us五、用戶手冊(cè)1、使用平臺(tái)是什么？下載網(wǎng)址？使用的VC卄平臺(tái)2、是否需要安裝？如需要安裝，如何安裝？不需要安裝3、說明如何使用你編寫的程序，詳細(xì)列出每一步的具體操作步驟。這里可以有適當(dāng)?shù)倪\(yùn)行結(jié)果抓圖。程序運(yùn)行效果圖neneFyPageMenPgelD：12671041210105143113412A:110110001011111M:111001110111110i：10j：7

16、7MeneryPageMenPgelD：12(i、1041210105J143113412A:001110001011111N:111001110111110i：llj：77IMeneryPageMenPgelD：4691041210105143i113412b=101110001011111h=111001110111110IMeneryPageMenPgelD：4691041210105143i113412A:011110001011111M:111001110111110i：llj：79-M-105,781,11.000000US、六、程序清單voidProcessPagelnitO頁面

17、初始化引用串srand(unsigiied)time(NULL);mta;fbr(mt1=0;iPPAGENUMBER1;1+)/PPAGENUMBER為引用串?dāng)?shù)for(mtj=0;jPPAGENUMBER2;j+)a=rand()%15;a=a+l;/printf(na:%da);processpageij.pageLD=a;processpage1j.A=0;processpage1j.M=0;processpage1jnext=NULL;processpageij.job=i;/pnntf(nnn);/printf(,dsfds%o,processpage00.next);/ShowPa

18、geO；voidMemPageIuut(mtnumber)/內(nèi)存鏈headpti*=newpage;tailptr=headpti;fbr(int1=1;iiiext=newpage;tailptr=tailpti-next;if(i=(number-1)tailpti-next=NULL;voidnclockO)/piiiitf(nonce%d%dir,ij);if(i=0&j=0)page*p;p=headptr;mta;srand(unsigiied)time(NULL);for(；1；J卄)a=randO%2;p-A=processpagei|j.A;p-M=a;p-pageID=pr

19、ocesspageij.pagelD;p=p-next;/ShowPagel();if(p=NULL)break;J+;ShowPagel();else/pnntfCj%dWj);paget=&processpageij;ClockReplace(paget);ShowPagel();1f(1=ppAGENUMBERl-1&j=PPAGENUMBER21)break;elseif(j=pPAGENUMBER2-1)/pnntf(,19nM);break;/?J+；coutnext-iiext!=NULL)preptr=preptr-next;cui-ptr=headpti*;/prepti*=

20、tailptr;while(l)if(paget-pageID=cuipti-pageID&paget-job=cuipti-job)/modifyacesscuipti-A=1;k+；break;elseif(curptr-A=falg_A)&(ciuptr-M=falg_M)ReplacePage(prepticuiptipaget);1+;break;if(falg_M=1)/(2)curptr-A=0;preptr=cuipti*;ciuptr=cuipti-next;f(curptr=NULL)if(falg_M=0)falg_M=1;/(2)elsefalg_M=0;preptr=

21、headptr;curptr=headptr;voidReplacePage(page*prepti;page*pti;page*paget)/coutnheren;page*temppti-;tempptr=ptr;coutprocesspageiit.Acoutprocesspageiit.AHM;inta;srand(unsigiied)time(NULL);a=randO%2;if(ptr=headptr)pagetnext=headpti-next;pti*=prepti-headptr=paget;elseif(pti*-next=NULL)ptr=paget;preptr-iie

22、xt=paget;elsepagetnext=ptr-next;preptr-iiext=paget;processpagei|j.A=1;processpagefi|j.M=a;/if(tempptr=NULL)priiitf(HNULDun);/free(temppti);voidShowPage()coutM*Hendl;coutnPageID:n;for(mt1=0;iPPAGENUMBERl;i+)for(mt尸0;jPPAGENUMBER2;j+)coutprocesspagei|j.pageIDn”；coutendl;coutHA:n;fbr(intit=0;itPPAGENUM

23、BER2;it+)coutendl;coutMM:n;fbr(iiitic=O;icpageIDHn;ptr=pti-next;ptr=headptr;coutendl;coutHA:H;while(pti*!=NULL)coutpti-AHn;ptr=pti-next;ptr=headptr;coutendl;coutMM:while(pti*!=NULL)coutpti-MMn;ptr=pti-next;ptr=headptr;coutendl;intmam()coutprocesspageiit.Acoutprocesspageiit.AHM;ProcessPageInit();頁面初始化MeinPageI