改進(jìn)型Clock算法實驗報告

1、福州大學(xué)工程技術(shù)學(xué)院實 驗 報 告課程名稱： 操作系統(tǒng) _學(xué) 號： xx _姓 名： xx _專 業(yè)： 計算機(jī)科學(xué)與技術(shù) _年 級： 10級 學(xué) 期： 2010年第1學(xué)期 _ 2010年12月20日實驗一 頁面置換算法及其實現(xiàn)分析一、實驗?zāi)康谋緦嶒炛饕獙Σ僮飨到y(tǒng)中應(yīng)用的一些關(guān)鍵算法進(jìn)行模擬。學(xué)生通過設(shè)計與實現(xiàn)相關(guān)算法，能夠加強(qiáng)對相應(yīng)理論的理解，并對了解操作系統(tǒng)內(nèi)部的基本處理原理與過程也有很多益處。2、 實驗要求 描述Clock算法的基本原理、必要的數(shù)據(jù)結(jié)構(gòu)、算法執(zhí)行流程圖、編碼實現(xiàn)。三、實驗內(nèi)容 1、頁面置換原理描述在采用請求分頁機(jī)制的操作系統(tǒng)中，當(dāng)運行一個程序的時候，若要訪問的頁面不在內(nèi)存中

2、而需要把它們調(diào)入內(nèi)存，但此時內(nèi)存已無空閑空間，為了保證該進(jìn)程能正常運行，需選擇內(nèi)存中暫時不用的頁面調(diào)出到磁盤交換區(qū)。選擇調(diào)出哪個頁面，由頁面算法決定。頁面置換算法的好壞，直接影響系統(tǒng)的性能，所以一個好的頁面置換算法，應(yīng)盡可能選擇調(diào)出較長時間內(nèi)不會再訪問的頁面，以保證較低的缺頁率。改進(jìn)型的Clock算法的思想：在將一個頁面換出時，如果該頁已被修改過，便須將它重新寫到磁盤上；但如果該頁未被修改過，則不必將它拷回磁盤。同時滿足這兩條件的頁面作為首先淘汰的頁。由訪問位A和修改位M可以組合成下面四種類型的頁面：1 類（A=0，M=0）：表示該頁最近既未被訪問、又未被修改，是最佳淘汰頁。2 類（A=0，M

3、=1）：表示該頁最近未被訪問，但已被修改，并不是很好的淘汰頁。3 類（A=1，M=0）：最近已被訪問，但未被修改，該頁有可能再被訪問。4 類（A=1，M=1）：最近已被訪問且被修改，該頁有可能再被訪問。在內(nèi)存中的每個頁必定是這四類頁面之一，在進(jìn)行頁面置換時，可采用與簡單Clock算法相類似的算法，其差別在于須同時檢查訪問位和修改位，以確定該頁是四類頁面中的哪一種。此算法稱為改進(jìn)型Clock算法。其執(zhí)行過程可分成以下三步：（1）從指針?biāo)甘镜漠?dāng)前位置開始，掃描循環(huán)隊列，尋找A=0且M=0的第一類頁面，將所遇到的第一個頁面作為所選中的淘汰頁。在第一次掃描期間不改變訪問位A。（2）如果第一步失敗，即

4、查找一周后未遇到第一類頁面，則開始第二輪掃描，尋找A=0且M=1的第二類頁面，將所遇到的第一個這類頁面作為淘汰頁。在第二輪掃描期間，將所有經(jīng)過的頁面的訪問位置0。（3）如果第二步也失敗，即未找到第二類頁面，則將指針返回到開始的位置，并將所有的訪問位復(fù)0。然后，重復(fù)第一步，如果仍失敗，必要時再重復(fù)第二步，此時就一定能夠找到被淘汰的頁。3、改進(jìn)型的 Clock算法的流程圖如下：3、頁面置換實現(xiàn)過程（1） 定義頁面表的數(shù)據(jù)結(jié)構(gòu)，它包括頁號（info）,訪問位（A），修改標(biāo)志（M）和指針4個屬性。代碼如下： template<typename T>class Node/結(jié)點類模板，不同數(shù)據(jù)

5、類型，編譯時生成不同的類 public:T info; /定義三個變量int A; /訪問頁變量，引用位的值int M; /修改頁變量，引用位的值Node<T> *link;/定義類的基地址 ;（2）通過界面接收的頁面數(shù)（K），在主程序中先對K個頁面通過調(diào)用方法Insertrear(T data)進(jìn)行初始化，代碼如下：while(1)if(n<k)cout<<"請輸入要訪問的頁面號："<<endl; cin>>num; cout<<endl; www->Insertrear(num); n+;初始化顯示

6、如下圖：（3） 初始化頁面之后會提示是否對內(nèi)存中存在的頁面進(jìn)行修改，選擇Y，就會調(diào)用方法change(),并對你選擇的頁面的修改標(biāo)志（M）進(jìn)行修改，把它改為1（說明該頁面已被修改過了）。選擇N，就會提示你“請輸入訪問的頁面號”，當(dāng)你輸入一個頁面號： a、通過調(diào)用方法find0(T data)判斷你輸入的頁面號是否跟內(nèi)存中存在的頁面號是否相同，如果相同，通過調(diào)用方法tihuan(Node<T>*p,T data)來進(jìn)行置換頁面。代碼如下：find0(T data)Node<T> *tempb;tempb=head->link;while(tempb!=head)if

7、(tempb->info=data)return tempb;tempb=tempb->link;return NULL; b、如果不是相同的兩個頁面，通過調(diào)用find1(T data)來尋找內(nèi)存中是否存在訪問位為0，修改標(biāo)志為0的頁號，如果找到了，通過調(diào)用方法tihuan(Node<T>*p,T data)來進(jìn)行置換頁面。如果沒有找到就調(diào)用find2(T data)來進(jìn)行第二次掃描，并把掃描過的頁面的訪問為改為1。如果在內(nèi)存中找到訪問為為0，修改標(biāo)志為1的頁號，通過調(diào)用方法tihuan(Node<T>*p,T data)來進(jìn)行置換頁面，否則，繼續(xù)循環(huán)fin

8、d1(T data)的查找直到置換為止。代碼如下：第一次掃描：find1(T data) Node<T> *tempb;tempb=head->link;while(tempb!=head)if(tempb->A=0&&tempb->M=0)return tempb;tempb=tempb->link;return NULL; 第二次掃描：find2(T data) Node<T> *tempb;tempb=head->link;while(tempb!=head)if(tempb->A=0&&temp

9、b->M=1)return tempb;tempb->A=0;tempb=tempb->link;return NULL;找到內(nèi)存中存在訪問位為0，修改標(biāo)志為0的頁號，如下圖：找到內(nèi)存中存在訪問為0，修改標(biāo)志為1的頁號，如下圖：四、實驗總結(jié) 通過這幾周的課程設(shè)計,加深了對操作系統(tǒng)的認(rèn)識,了解了操作系統(tǒng)中各種資源分配算法的實現(xiàn),特別是對虛擬存儲,頁面置換有了深入的了解,并能夠用高級語言進(jìn)行模擬演示。在這短短的幾周時間里，通過瀏覽、閱讀有關(guān)的資料，學(xué)到了很多東西，同時也發(fā)現(xiàn)僅僅書本的知識是遠(yuǎn)遠(yuǎn)不夠的，需要把知識運用到實踐中去，能力才能得到提高。 不僅提高對操作系統(tǒng)的了解，這次的課程設(shè)計也使自己的C+編程能力加強(qiáng)了不少。一分耕耘，一分收獲，這次的課程設(shè)計讓我受益匪淺。雖然自己所做的很少也不夠完善，但畢竟也是努力的結(jié)果。另外，使我體會最深的是：任何一門知識的掌握，僅靠學(xué)習(xí)理論知識是遠(yuǎn)遠(yuǎn)不夠的，要與實際動手操作相結(jié)合才能達(dá)到功效。參考文獻(xiàn)1 朱振