Clock-Cache-Algorithmus

Question

Ich möchte Prinzipien der Clock-Cache-Ersetzungsrichtlinie verstehen.

Was passiert whrn es anfangen zu arbeiten? Wir haben zum Beispiel Cache-Größe = 5. Also, zunächst fügen wir 5 zufällige Objekte in den Cache. Bin ich wahr, wenn ich denke, dass alle diese Objekte zuerst ClockBit = 0 haben werden? Dann, wenn das sechste Objekt kommt, müssen wir einen Platz dafür finden. Sollten wir versuchen, dasselbe Objekt im Cache ohne Uhrzeiger zu finden (nur ifInCache (comingObject))? Was passiert, wenn sich kein solches Objekt im Cache befindet? Wo ist eine Startposition für die Uhrzeiger?

las ich eine Menge Artikel und wollen einfach nur Hauptfragen über Clock zu verstehen.

Answer 1

Ich denke, dass man die Dinge machen für sich selbst kompliziert. Der Grund, warum Menschen diesen Ansatz verwenden, ist, dass es SEHR einfach ist.

dies zu vermeiden eine entriy zu ersetzen, die vor kurzem verwendet wurde.

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; 
} 

---

Das stört nicht.

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; 
} 

Answer 2

Bin ich richtig, wenn ich denke, dass alle diese Objekte zunächst Willen habe clockbit = 0?

Wenn sie nicht referenziert sind, dann ja.

Sollten wir versuchen, gleiches Objekt im Cache ohne Uhrzeiger zu finden (nur ifInCache (comingObject))?

Ja, Sie müssen überprüfen, ob das Objekt bereits im Cache ist. Wenn ja, würde die Referenzbitleitung (clockbit)

auf 1 gesetzt sein Was ist kein solches Objekt im Cache, wenn es passiert? Wo ist eine Startposition für die Uhrzeiger?

Wenn das Objekt nicht bereits im Cache ist, überprüfen Sie das Objekt auf der Uhrzeiger. Die Position der Hand wäre die letzte Position im Cache, wenn sie noch nicht voll ist und ansonsten zwischen zwei Cache-Lookups gleich bleibt (sie würde durch die Suchvorgänge selbst inkrementiert werden).

Beispiel (cache size = 5):

• A hinzufügen -> Hand bei 0 vor und zu 1 nach
• B hinzufügen -> Hand in 1 vor und zu 2 nach
• hinzufügen C -> Hand bei 2 vor und bei 3 nach
• hinzufügen D -> Hand bei 3 vor und bei 4 nach
• hinzufügen E -> Hand bei 4 vor und bei 0 nach
• hinzufügen F -> Hand bei 0, überprüfen referenzierten bisschen A, wenn es 0 ersetzen und Erhöhung der Hand, sonst Zuwachs Hand nur -> danach Hand ist bei 1

Beachten Sie, dass, wenn alle Objekte Wenn ihr Referenzbit auf 1 gesetzt ist, wird das Objekt an der Hand ersetzt, da das Referenzbit nach Überprüfung eines Objekts auf 0 gesetzt ist und somit das zweite Mal das Objekt 0 ist.

Hier ist eine erweiterte/angepasste Version von @ PeterLawrey's Code:

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; 
}