Clock-Pro緩存替換

我已經閱讀了很多關於ClockPro緩存替換算法文章 - 改進的時鐘緩存替換的版本。爲了方便起見，我實現了Clock。現在我想用2隻手實現Java Clock-Pro（實際算法中冷熱手而不是3手）。我發現了一些說明：

The ClockPro Algorithm 

On Start(): 
    cold_block = first block 
    hot_block = first block 

On Memory Lookup(): 
    curr_block = NULL 
    If block is in cache: 
     Set clock bit 
     Return block to CPU 
    Else: 
     While curr_block == NULL: 
      If cold_block.clockbit == 0: 
       curr_block = cold_block 
      Else if cold_block.test == 1 : 
       Turn cold hand block hot 
       Unset the clockbit 
       Run Hot Hand Algorithm 
      Else: 
       cold_block.clockbit = 0 
      cold_block = cold_block.next 

    If curr_block is dirty : write 
    Find accessed block in memory 
    Return fetched block to the CPU 
    Replace curr_block with fetched one 

Hot Hand Algorithm() : 
    curr_block = NULL 
    While curr_block == NULL: 
     If hot_block is cold : 
      hot_block.text = 0 
     Else if hot_block.clockbit == 0 : 
      Turn the block cold 
     Else : 
      hot_block.clockbit = 0 
     hot_block = hot_block.next

如果沒有人嘗試過，請回答一些問題：

什麼測試周期是什麼？它何時開始，我們可以使用什麼類型的。它只是一點點，可以告訴我們，如果對象是在測試期間或不是，或者它是一個計數器？在某些時刻，雙手是否可以指向一個街區？

如果有人能，請幫我算法的這種行爲在一個簡單的例子由於模型..。

來源

2012-04-19 golgofa

該代碼非常不完整。至少有兩個重要的部分是丟失： 1）測試手（試手） 2）熱/冷頁reatio適應性

我不得不說，在這個問題上的原始論文確實缺乏許多重要的細節。

我目前正在寫Python實現，但我還沒有發佈的來源，因爲質量不夠高呢。

項目網址：https://bitbucket.org/samilehtinen/pyclockpro

即使代碼被釋放時，我十分肯定有微小但重要的細節，這可能需要微調。

贊： 1）初始化時內存熱/冷頁面分配比率，我已經配置爲100％的內存分配給冷頁面。 2）如果熱分配調得如此之低以致熱手應該冷手，該怎麼辦？我假設在這種情況下，熱分配被簡單地忽略了，因爲熱手經過冷手會破壞一切。在這種情況下，熱手也會清除所有非常駐測試頁面。

根據測試數據，我的實現似乎得到調整得很好。

問題的答案：測試周期時，密鑰保存，但價值被丟棄。在鐘面上，你會看到冷和測試之間的這些條目。我用int來表示頁面類型，0非常駐的冷頁面（測試頁面），1表示冷頁面，2表示熱頁面。如果您使用指向數據的指針，如果指針爲Null，則頁面爲非常駐頁面，因爲您只有沒有數據（值）的鍵。

是，兩者都可以動手，有時指向一個街區。主要問題是，手可以通過對方。我發現如果發生事情就會被打破。所以基本上熱手可以推測試手，並且可以推冷手。取決於你如何實現的東西。或者如果你像在報紙上那樣做，手熱可以越過測試手，但是在那種情況下，它會用手拖動測試手。而且據我所知，手熱不能越過冷手，或者如果你這樣實施，那麼冷手的作用仍然是用手冷手。

很難做出簡單的例子，因爲這並不簡單。還有一些邊緣案例需要處理，至少在這裏提到的情況。自適應還會增加邊緣情況，因爲在迭代處理期間內存分配可能會發生變化。在這些情況下保持100％的分配需要一些額外的檢查。如果你允許在緩存大小上有+/-塊，那麼實現就更簡單了。

更新，Python源代碼和文檔現在發佈。所以有完整的工作示例可以在Python中查看。

來源

2012-11-20 16:34:31

Clock-Pro緩存替換

回答

相關問題