2

クロック キャッシュの置き換えポリシーの原則を理解したい。

機能し始めるとどうなりますか？たとえば、キャッシュ サイズ = 5 です。したがって、最初に 5 つのランダム オブジェクトをキャッシュに追加します。これらすべてのオブジェクトが最初は clockbit = 0 になると思うのは本当ですか? 次に、6 番目のオブジェクトが来たら、その場所を見つけなければなりません。時計の針を使わずに (ifInCache(comingObject) だけで) キャッシュ内の同じオブジェクトを見つけようとする必要がありますか? そのようなオブジェクトがキャッシュにない場合はどうなりますか? 時計の針のスタート位置は？

たくさんの記事を読み、Clock に関する主な質問を理解したいだけです。

4

2 に答える 2

4

これらすべてのオブジェクトが最初は clockbit = 0 になると思うのは本当ですか?

それらが参照されていない場合は、はい。

時計の針を使わずに (ifInCache(comingObject) だけで) キャッシュ内の同じオブジェクトを見つけようとする必要がありますか?

はい、オブジェクトが既にキャッシュにあるかどうかを確認する必要があります。その場合、参照ビット (clockbit) は 1 に設定されます。

そのようなオブジェクトがキャッシュにない場合はどうなりますか? 時計の針のスタート位置は？

オブジェクトがまだキャッシュにない場合は、時計の針でオブジェクトを確認します。ハンドの位置は、まだいっぱいになっていない場合はキャッシュ内の最後の位置になり、それ以外の場合は 2 つのキャッシュ ルックアップ間で同じままになります (ルックアップ自体によってインクリメントされます)。

例 (キャッシュ サイズ = 5):

  • 追加A-> 前に 0、後に 1 でハンド
  • 追加B-> 前の 1 と後の 2 で手
  • 追加C-> 前に 2、後に 3 で手
  • 追加D-> 前の 3 と後の 4 で手
  • 追加E-> 前に 4、後に 0 でハンド
  • 追加F-> 0 のAハンド。

すべてのオブジェクトの参照ビットが 1 に設定されている場合、オブジェクトをチェックした後にその参照ビットが 0 に設定され、オブジェクトが 2 回目にチェックされたときにビットが 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;
}
于 2012-04-12T11:22:10.617 に答える
3

あなたは自分自身のために物事を複雑にしていると思います。人々がこのアプローチを使用する理由は、それが非常に単純だからです。

これにより、最近使用されたエントリの置き換えが回避されます。

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;
}
于 2012-04-12T11:12:35.663 に答える