操作系統(tǒng)實(shí)驗(yàn)報(bào)告(clock算法)

實(shí)驗(yàn)四頁(yè)面置換算法一、 實(shí)驗(yàn)?zāi)康谋緦?shí)驗(yàn)主要對(duì)操作系統(tǒng)中請(qǐng)求分頁(yè)式內(nèi)存管理及其應(yīng)用的一些關(guān)鍵算法進(jìn)行模擬。學(xué)生通過設(shè)計(jì)與實(shí)現(xiàn)Clock算法，能夠加強(qiáng)對(duì)相應(yīng)理論的理解，并對(duì)了解操作系統(tǒng)內(nèi)部的基本處理原理與過程也有很多益處。二、 實(shí)驗(yàn)要求基本要求：描述Clock算法的基本原理、必要的數(shù)據(jù)結(jié)構(gòu)、算法執(zhí)行流程圖、編碼實(shí)現(xiàn)。1） 初始化：輸入作業(yè)可占用的總頁(yè)框數(shù)，初始化置空。2） 輸入請(qǐng)求序列：輸入一個(gè)作業(yè)頁(yè)號(hào)訪問請(qǐng)求序列，依次占用相應(yīng)頁(yè)框，直至全部占用；3） Clock算法：當(dāng)頁(yè)框全部占用后，對(duì)于后續(xù)新的頁(yè)號(hào)訪問請(qǐng)求，執(zhí)行Clock算法，淘汰1個(gè)頁(yè)面后裝入新的頁(yè)號(hào)。4） 顯示當(dāng)前分配淘汰序列：顯示淘汰的頁(yè)號(hào)序列。描述Clock算法的基本原理、必要的數(shù)據(jù)結(jié)構(gòu)、算法執(zhí)行流程圖、編碼實(shí)現(xiàn)。三、實(shí)驗(yàn)內(nèi)容1）基本原理時(shí)鐘頁(yè)面置換算法是把所有的頁(yè)面都保存在一個(gè)類似鐘面的環(huán)形鏈表中，一個(gè)表針指向最老的頁(yè)面，日日回I回 /回當(dāng)發(fā)生缺頁(yè)中斷時(shí)，檢查君針指向的頁(yè)根據(jù)R位采取動(dòng)作t￡=伐淘汰頁(yè)面R=It當(dāng)發(fā)生缺頁(yè)中斷時(shí)，檢查君針指向的頁(yè)根據(jù)R位采取動(dòng)作t￡=伐淘汰頁(yè)面R=It清除威位井向前翔動(dòng)成針□國(guó)回回曰如圖所示。當(dāng)發(fā)生缺頁(yè)中斷時(shí)，算法首先檢查表針指向的頁(yè)面，如果它的R位是0就淘汰該頁(yè)面，并把新的頁(yè)面插入這個(gè)位置，然后把表針前移一個(gè)位置；如果R位是1就清除R位并把表針前移一個(gè)位置，重復(fù)這個(gè)過程直到找到了一個(gè)R位為0的頁(yè)面為止。2）算法流程設(shè)計(jì)主函數(shù)流程：STEP1:輸入分配的頁(yè)框數(shù)，頁(yè)面訪問次數(shù)和要訪問的頁(yè)面號(hào)序列STEP2:內(nèi)存頁(yè)面初始化。內(nèi)存中頁(yè)面的數(shù)據(jù)結(jié)構(gòu)為單循環(huán)鏈表，含有頁(yè)號(hào)值yehao和訪問位值a。開始時(shí)頁(yè)號(hào)均為-1,訪問位為0.STEP3：測(cè)試數(shù)據(jù)。具體算法是依要訪問的頁(yè)面號(hào)，調(diào)用find()函數(shù)查找是否已經(jīng)存在于內(nèi)存中。若存在，則修改其訪問位為1.若不存在，觸發(fā)缺頁(yè)中斷，調(diào)用tihuan()函數(shù)。最后，打印當(dāng)前內(nèi)存狀態(tài)。如此循環(huán)直至測(cè)試串都訪問完畢。主要函數(shù)實(shí)現(xiàn)Makenode(double)函數(shù)：用于初始化一個(gè)節(jié)點(diǎn)。Find(double)函數(shù)：依據(jù)輸入的頁(yè)號(hào)，查詢內(nèi)存中是否已存在此頁(yè)面。若存在返回值1，不存在返回值0.Tihuan(double)函數(shù)：在發(fā)生缺頁(yè)中斷時(shí)，時(shí)鐘指針查找訪問位為0的頁(yè)面進(jìn)行替換，指針掃過的頁(yè)面訪問位置0，新加入的頁(yè)面訪問位置1。替換后指針下移。Print_state()函數(shù)：打印當(dāng)前內(nèi)存中存在的頁(yè)面的狀態(tài)以及當(dāng)前時(shí)鐘指針?biāo)赶虻捻?yè)面位置。測(cè)試數(shù)據(jù)輸入：輸入分配的頁(yè)框數(shù)3輸入頁(yè)面訪問次數(shù)15輸入要訪問的頁(yè)面號(hào)序列342643743634846輸出(僅最后一項(xiàng))：頁(yè)面可訪問位TOC\o"1-5"\h\z4 1頁(yè)荷號(hào)訪問位6 1頁(yè)面號(hào)訪問位8 1clock^g針?biāo)谖恢庙?yè)面號(hào)為4結(jié)果分析以下是clock算法對(duì)應(yīng)輸入頁(yè)面號(hào)序列342643743634846的分析表四、實(shí)驗(yàn)總結(jié)加深對(duì)clock算法的理解。通過與其他算法的比較，我也了解了他們的異同之處。Clock算法其實(shí)是一種改進(jìn)的第二次機(jī)會(huì)算法，它通過設(shè)置訪問位，找到最早最不常訪問的頁(yè)面，即標(biāo)號(hào)為0的頁(yè)面。之所以叫clock算法，依我理解是將內(nèi)存中的排列順序附上時(shí)間的概念，clock指針掃過的頁(yè)面要將他們1置0就是基于這個(gè)思想，因?yàn)樗麄兌际菦]被訪問的，且在時(shí)鐘上的排列按照訪問時(shí)間順序。這樣就保證了每次替換的都是最早進(jìn)來的且不最常訪問的頁(yè)面。在時(shí)鐘內(nèi)存結(jié)構(gòu)的代碼實(shí)現(xiàn)上，我使用了自建的單循環(huán)鏈表，對(duì)其進(jìn)行順序地遍歷即可實(shí)現(xiàn)時(shí)鐘指針的移動(dòng)。另外通過全局變量node*r（時(shí)鐘）node*start（開始頁(yè)面項(xiàng)）node*r_prev（時(shí)鐘指針的前驅(qū)）的設(shè)置，方便了有關(guān)算法的實(shí)現(xiàn)。此算法較為簡(jiǎn)單，還有一種改進(jìn)版的clock算法，增加了一個(gè)修改位，表示頁(yè)框是否被修改過。這樣的設(shè)計(jì)更加符合現(xiàn)在操作系統(tǒng)的調(diào)度原則。參考文獻(xiàn)（美）StanleyB.Lippman等著李師賢等譯.C++Primer中文版（第4版）.人民郵電出版社，2006-03-01蔣愛軍，李師賢，梅曉勇著.C++Primer習(xí)題解答（第4版）.人民郵電出版社，2007-02-01塔嫩鮑姆（Tanenbaum.A.S），陳向群，馬洪兵著.現(xiàn)代操作系統(tǒng)（原書第