Clock算法

Clock算法的簡(jiǎn)介

由于LRU算法對(duì)于硬件要求很高，它的近似算法通常是更好的選擇，Clock算法就是用的比較多的一種LRU近似算法。

Clock算法的理解

話不多說，直接進(jìn)入正題！

簡(jiǎn)單Clock置換算法

例題：頁面流 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 在3個(gè)物理塊下的置換過程。
相比起其他算法，Clock算法需要一個(gè)指針，簡(jiǎn)單理解就是指針指向哪里頁面就優(yōu)先插入哪里。
比如在初始狀態(tài)時(shí)指針指向第一個(gè)物理塊，頁面7便插入第一個(gè)物理塊，同時(shí)指針下移，那么什么時(shí)候指針要下移呢？很簡(jiǎn)單，當(dāng)插入成功后指針移到插入位置的下一位。
除了指針還需要給每個(gè)在物理塊中的頁面標(biāo)個(gè)號(hào)（0或1），剛插入的或者已經(jīng)在物理塊中又被訪問的頁面標(biāo)為1。這個(gè)標(biāo)號(hào)有什么用呢，你可以理解為一個(gè)一次性的“免換金牌”，當(dāng)被指針指著要被換出的時(shí)候，如果標(biāo)號(hào)是1，就改為0，然后按順序判斷下一個(gè)位置，直到循環(huán)下去找到一個(gè)0，把標(biāo)號(hào)0的頁面換出去，同時(shí)指針移到換出位置的下一位。
例題的流程便是這樣的（這里我用*表示標(biāo)號(hào)為1，沒有則為0）：

改進(jìn)Clock置換算法

由于在實(shí)際系統(tǒng)使用中頁面不僅會(huì)被訪問還會(huì)被修改，所以改進(jìn)型Clock算法就是把頁面分成四種情況：
1.最近既沒修改也沒訪問
2.最近沒訪問但修改了
3.最近訪問了但沒修改
4.最近即訪問又修改了
按照類似簡(jiǎn)單Clock算法（使用兩個(gè)標(biāo)號(hào)）來依次判斷有沒有情況1的頁面，如果有就換出，如果沒有就判斷有沒有情況2的頁面，注意，當(dāng)判斷完后還是沒有并不是去判斷情況3和4，而是把所有訪問標(biāo)號(hào)都重置為0，再依次判斷1和2，這樣就能找到最適合換出的頁面。

總結(jié)

Clock算法相較于其他頁面置換算法比較復(fù)雜，但是只要掌握原理，用例題練幾遍就能很熟練啦~

總結(jié)

以上是生活随笔為你收集整理的操作系统Clock算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。