java - 时钟缓存算法

Question

我想了解时钟缓存替换策略的原理。

当它开始工作时会发生什么？例如，我们有缓存大小 = 5。因此，首先我们将 5 个随机对象添加到缓存中。当我认为所有这些对象最初都将 habe clockbit = 0 时，我是真的吗？那么当第六个对象来的时候，我们必须给它找个地方。我们是否应该尝试在没有时钟指针的情况下在缓存中找到相同的对象(只是 ifInCache(comingObject))？如果缓存中没有这样的对象会怎样？时钟指针的起始位置在哪里？

我阅读了很多文章，只是想了解有关 Clock 的主要问题。

Answer 1

Am I true when I think that all these objects at first will habe clockbit = 0?

如果它们没有被引用，那么是。

Should we try to find same object in cache without Clock hand (just ifInCache(comingObject))?

是的，您必须检查对象是否已经在缓存中。如果是这样，引用位 (clockbit) 将被设置为 1。

What happens if there is no such object in cache? Where is a start position for Clock hand?

如果对象不在缓存中，则在时钟指针处检查对象。如果手的位置尚未满，则它的位置将是缓存中的最后一个位置，否则在两次缓存查找之间保持相同(它将由查找本身递增)。

示例(缓存大小 = 5):

• 添加 A -> 手在 0 之前和 1 之后
• 添加 B -> 手在 1 之前和 2 之后
• 添加 C -> 手在 2 之前和 3 之后
• 添加 D -> 前 3 和后 4 的手
• 添加 E -> 手在 4 之前和 0 之后
• 添加F -> hand at 0，检查A的引用位，如果是0则替换并递增hand，否则仅递增hand -> 之后hand在1

请注意，如果所有对象的引用位都设置为 1，则手头的对象将被替换，因为在检查一个对象后，其引用位设置为 0，因此第二次检查该对象时，该位将为 0。

编辑:

这是@PeterLawrey 代码的扩展/调整版本:

private final Object[] objects= new Object[5]; 
private final boolean[] referenced = new boolean[5]; //boolean for simplicity
private int clock = 0;

public Object getOrCache(Object obj) {
   for(int i = 0; i < objects.length; ++i) {
     if (obj.equals(objects[i])) {
       referenced[i] = true; //object has been referenced, note that this is for simplicity and could be optimized
       return obj;
     }
   }

   //loop over the entries until there is a non-referenced one
   //reference flags are removed in the process
   while( referenced[clock] ) {
     referenced[clock] = false;
     clock = (clock + 1) % objects.length; //for clarity
   }

   //replace the object at the current clock position and increment clock
   objects[clock] = obj;
   referenced[clock] = true;
   clock = (clock + 1) % objects.length; //for clarity

   return obj;
}