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