0

每个人。

我已经阅读了很多关于 ClockPro 缓存替换算法的文章 - 时钟缓存替换的改进版本。起初为了简单起见，我实现了时钟。现在我想用 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

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

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

如果有人可以，请帮助我在一个简单的示例中对算法的这种行为进行建模。谢谢。

4

1 回答 1

1

该代码非常不完整。至少缺少两个重要部分：1）测试手（test hand） 2）热/冷页面reatio适应性

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

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

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

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

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

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

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

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

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

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

于 2012-11-20T16:34:31.843 回答