java - Clock-Pro缓存替换

Question

每个人。

看了很多关于ClockPro缓存替换算法的文章——改进版Clock缓存替换。为了简单起见，我首先实现了 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

如果有人试过，请回答一些问题:

什么是测试期？它什么时候开始，我们可以使用什么类型。只是一点点，可以告诉我们对象是否处于测试期，或者它是一个计数器？双手能否在某个时间点指向一个方 block ？

如果有人有能力，请帮我用一个简单的例子来模拟这种算法行为。谢谢。

Answer 1

该代码非常不完整。至少缺少两个重要部分:1)测试手(test hand)2) 热/冷页响应自适应

我不得不说，关于这个主题的原始论文确实缺少很多重要的细节。

我目前正在编写 Python 实现，但我还没有发布源代码，因为质量还不够高。

项目网址:https://bitbucket.org/samilehtinen/pyclockpro

即使发布了代码，我也很确定有一些次要但很重要的细节可能需要微调。

喜欢:1)初始化时内存热/冷页分配比率，我已经配置为冷页分配100%的内存。2) 如果热分配被调得太低以至于热手应该通过冷手怎么办。我假设在这种情况下，热分配被简单地忽略了，因为热手越过冷手会破坏一切。在这种情况下，hand hot 还清除了所有非驻留测试页。

根据测试数据，我的实现似乎得到了很好的调整。

您问题的答案:测试期是保留 key 但丢弃值的时间。在钟面上，您会看到冷和测试之间的这些条目。页面类型我用了int，0是非常驻冷页(测试页)，1是冷页，2是热页。如果您使用指向数据的指针，如果指针为 Null，则页面为非常驻页面，因为您只有键而没有数据(值)。

是的，有时双手和所有手都可以指向一个方 block 。主要问题是，手可以互相过去吗？我认为如果发生这种情况，事情就会坏掉。所以基本上热手可以推测试手，也可以推冷手。取决于你如何实现。或者如果你像在论文中那样做，热手可以通过测试手，但在那种情况下它会拖着测试手。据我所知，热手不能越过冷手，或者如果你这样做，那么它会完成冷手的工作，但仍然会用热手拖拽冷手。

很难做出简单的例子，因为这并不简单。还有一些边缘情况需要处理，至少是这里提到的情况。自适应性还增加了边缘情况，因为在迭代处理期间内存分配可能会发生变化。在这些情况下保持 100% 分配需要一些额外的检查。如果您允许缓存大小中有 +/- 几个 block ，那么实现会更简单。

更新，Python 源代码和文档现已发布。因此，有完整的工作示例可以在 Python 中查看。