java - 时钟缓存算法

Question

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

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

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

Answer 1

当我认为所有这些对象一开始都具有clockbit = 0时，我是真的吗？

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

我们是否应该尝试在没有时钟指针的情况下在缓存中找到相同的对象（仅 ifInCache(comingObject)）？

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

如果缓存中没有这样的对象会发生什么？时钟指针的起始位置在哪里？

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

示例（缓存大小 = 5）：

• 添加A-> 手在 0 之前和 1 之后
• 添加B-> 手在 1 之前和 2 之后
• add C-> hand at 2 before and at 3 after
• add D-> hand at 3 before and at 4 after
• 添加E-> 手在 4 之前和 0 之后
• add 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;
}

Answer 2

我认为你自己让事情变得复杂。人们使用这种方法的原因是它非常简单。

这避免了替换最近使用的条目。

private final Object[] objects = new Object[5];
private final boolean[] referenced = new boolean[objects.length];
private int clock = 0;

public Object getOrCache(Object obj) {
    for (int i = 0, objectsLength = objects.length; i < objectsLength; i++) {
        Object o = objects[i];
        if (obj.equals(o)) {
            referenced[i] = true;
            return obj;
        }
    }
    while(referenced[clock]) {
        referenced[clock] = false;
        incrClock();
    }
    objects[clock] = obj;
    incrClock();
    return obj;
}

private void incrClock() {
    if (++clock >= objects.length)
        clock = 0;
}

---

这不麻烦。

private final Object[] objects= new Object[5];
private int clock = 0;

public Object getOrCache(Object obj) {
   for(Object o: objects) 
       if (obj.equals(o))
           return obj;
   objects[clock++ % objects.length] = obj;
   return obj;
}