3 LRU k-Algorithmus

Ideee

Die letzte K-Zugriff auf eine Seite im Puffer wird berücksichtigt, um die Seitenersetzungstrategien zu verbessern.

• Der Algorithmus wählt die Seite mit der größten K-Rückwärtsdistanz $k$-$B$ ($k$-Rückwärtsdistanz, $B$ Backward distance)
• $k$-$B$ ist der Distanz zwischen aktueller Zeit und $k$-letzter Referenz der Seite
• Um $k$-$B$ zu berechnen, muss der Algorithmus die Referenzzeitpunkte der Seiten speichern
• Notation
  • $LU=(t_k,t_{k-1},\dots ,t_2,t_1)$
  • t_i: i-te letzte Zugriff
  • $(\dots )$ ist HINT

Beispiele und Probleme

Algorithmus

1. Fallbeispiel: Seite im Puffer mit unkorreliertem Referenz

• C_R_P = 5
• Anfrage Seite C zum Zeitpunkt 18

Seite	LU
F	(0,0,16|16)
G	(0,0,17|17)
C	(3,5,8|9)
E	(6,11,15|15)
B	(10,13,14|14)

procedureLRU(p,t,K) {
    if inBuffer(p) { // C Seite ist im Puffer -> true
        if t-LAST(p) > C_R_P { // 18 - 9 = 9 -> 9 > 5 -> true
            C_P_P = LAST(p)-HIST(p,1) // 1 = 9 - 8
            for(i=2toK) {
                HIST(p,i) = HIST(p,i-1) + C_P_P // verschiebe HIST zu und erhöhe es um 1 (6,9,8|9)
            }                                   
            HIST(p,1)=t // HIST = (6,9,18|9)
            LAST(p)=t   // HIST = (6,9,18|18)
        }
        else {
            LAST(p)=t
        }
    }
    else {
        ...
    }
}

2. Fallbeispiel: Seite im Puffer mit korreliertem Referenz

• C_R_P = 5
• Anfrage Seite E zum Zeitpunkt 18

Seite	LU
F	(0,0,16|16)
G	(0,0,17|17)
C	(3,5,8|9)
E	(6,11,15|15)
B	(10,13,14|14)

procedureLRU(p,t,K) {
    if inBuffer(p) {  // Seite ist im Puffer   -> true
        if t-LAST(p) > C_R_P {  // 18 - 15 = 3 -> 3 < 5  -> false
            C_P_P = LAST(p)-HIST(p,1)
            for(i=2toK) {
                HIST(p,i) = HIST(p,i-1) + C_P_P
            }
            HIST(p,1)=t
            LAST(p)=t
        }
        else {
            LAST(p)=t  // -> HIST = (6,11,15|18)
        }
    }
    else {
        ...
    }
}

3. Fallbeispiel: Seite nicht im Puffer, neue Seite ohne Historie

• C_R_P = 5
• Anfrage Seite H zum Zeitpunkt 18

Seite	LU
F	(0,0,16|16)
G	(2,3,7|7)
C	(3,5,8|9)
E	(6,11,15|15)
B	(10,13,14|14)

procedureLRU(p,t,K) {
    if inBuffer(p) {         // Seite ist im Puffer -> false
        ...
    }
    else {
        min = t
        for all q in buffer{  // Bestimme Victim -> C
            if((t-LAST(q)>C_R_P) && (HIST(q,K)<min)) {
                victim = q
                min = HIST(q,K)
            }
        }
        if isDirty(victim) {
            write victim to disc
        }
        fetch(p,victim)
        if notexists(HIST(p)) { // HIST(H) existiert nicht
            allocate HIST(p) 
            for(i=2 to K){
                HIST(p,i)=0
            }// -> HIST(H) = (0,0,_|_)
        }            
        else {
            for(i=2toK){
            HIST(p,i)=HIST(p,i-1)
            }
        }
        HIST(p,1)=t  // HIST(H) -> (0,0,18|_)
        LAST(p)=t    // HIST(H) -> (0,0,18|18)
    }
}

4. Fallbeispiel, Seite nicht im Puffer, neue Seite mit Historie

• C_R_P = 5
• Anfrage Seite C zum Zeitpunkt 19
• C Historie (3,5,8|9)

Seite	LU
F	(0,0,16|16)
G	(2,3,7|7)
H	(0,0,18|18)
E	(6,11,15|15)
B	(10,13,14|14)

procedureLRU(p,t,K) {
    if inBuffer(p) {// Seite ist im Puffer -> false
        ...
    }
    else {
        min = t // -> 19
        for all q in buffer{  // Bestimme Victim -> G
            if((t - LAST(q) > C_R_P) && (HIST(q,K) < min)) { // Durchläufe:
                victim = q        // 1. F -> 19 - 16 = 3 > 5 -> False
                min = HIST(q,K)   // 2. G -> 19 - 7 = 12 > 5 -> True && True <- True = HIST(0,0,18\|18) 18 < min)
            }
        }
        if isDirty(victim) {
            write victim to disc //  G auf Platte sichern
        }
        fetch(p,victim)
        if notexists(HIST(p)) {  // HIST(C) existiert -> false
            allocate HIST(p)
            for(i=2toK){HIST(p,i)=0}
        }
        else {
            for(i=2 to K){
            HIST(p,i)=HIST(p,i-1)} // HIST(C) = (5,8,8|9)
        }      
        HIST(p,1)=t // HIST(C) = (5,8,19|9)
        LAST(p)=t   // HIST(C) = (5,8,19|19)
    }
}

Performenceanalyse

• LRU-2 bester Algorithmus
• Je kleiner Puffer, desto überlegener ist LRU-2 gegenüber LRU
• LFU auch gut, aber nicht genommmen weil
  • Wenn früher eine Seite oft referenziert wurde, bleibt sie lange im Puffer, obwolh sie “veraltet” ist
  • LFU braucht lange, um sich an Änderungen anzupassen. D.h. wenn neue Daten inn den Vordergrund treten, dauert es länger, bis sich LFU daran anpasst

Fazit

Die Performanceanalyse zeigt, dass der LRU-k-Algorithmus, insbesondere mit k = 2, eine deutliche Verbesserung gegenüber dem klassischen LRU-Algorithmus darstellt. Die Wahl des optimalen k hängt von der spezifischen Workload ab.

procedureLRU(p,t,K) {
    if inBuffer(p) {
        if t-LAST(p) > C_R_P {  
            C_P_P = LAST(p)-HIST(p,1)
            for(i=2toK) {
                HIST(p,i) = HIST(p,i-1) + C_P_P
            }
            HIST(p,1)=t
            LAST(p)=t
        }
        else {
            LAST(p)=t 
        }
    }
    else {
        min = t 
        for all q in buffer{  
            if((t - LAST(q) > C_R_P) && (HIST(q,K) < min)) { 
                victim = q       
                min = HIST(q,K)  
            }
        }
        if isDirty(victim) {
            write victim to disc 
        }
        fetch(p,victim)
        if notexists(HIST(p)) {  
            allocate HIST(p)
            for(i=2toK){HIST(p,i)=0}
        }
        else {
            for(i=2 to K){
            HIST(p,i)=HIST(p,i-1)} 
        }      
        HIST(p,1)=t 
        LAST(p)=t  
    }
}