Criteri di sostituzione della cache - Cache replacement policies

In informatica , gli algoritmi della cache (chiamati anche frequentemente algoritmi di sostituzione della cache o politiche di sostituzione della cache ) sono istruzioni di ottimizzazione , o algoritmi , che un programma per computer o una struttura gestita dall'hardware può utilizzare per gestire una cache di informazioni memorizzate sul computer. La memorizzazione nella cache migliora le prestazioni mantenendo gli elementi di dati recenti o utilizzati di frequente in posizioni di memoria a cui è più veloce o computazionalmente più economico accedere rispetto ai normali archivi di memoria. Quando la cache è piena, l'algoritmo deve scegliere quali elementi scartare per fare spazio a quelli nuovi.

Panoramica

Il tempo medio di riferimento della memoria è

T=m\times T_{m}+T_{h}+E

dove

m

= rapporto mancato = 1 - (rapporto risultati)

T_{m}

= tempo per effettuare un accesso alla memoria principale quando si verifica un errore (o, con cache multilivello, tempo medio di riferimento della memoria per la cache successiva inferiore)

T_{h}

= la latenza: il tempo per fare riferimento alla cache (dovrebbe essere lo stesso per hit e miss)

E

= vari effetti secondari, come effetti di coda nei sistemi multiprocessore

Ci sono due figure principali di merito di una cache: la latenza e il tasso di successo. Ci sono anche una serie di fattori secondari che influenzano le prestazioni della cache.

Il "rapporto di successo" di una cache descrive la frequenza con cui un elemento cercato viene effettivamente trovato nella cache. Criteri di sostituzione più efficienti tengono traccia di più informazioni sull'utilizzo al fine di migliorare il tasso di riscontri (per una determinata dimensione della cache).

La "latenza" di una cache descrive quanto tempo dopo aver richiesto un elemento desiderato, la cache può restituire quell'elemento (quando c'è un hit). Strategie di sostituzione più rapide in genere tengono traccia di meno informazioni sull'utilizzo o, nel caso di cache a mappatura diretta, nessuna informazione per ridurre la quantità di tempo necessaria per aggiornare tali informazioni.

Ogni strategia di sostituzione è un compromesso tra hit rate e latenza.

Le misurazioni del tasso di successo vengono in genere eseguite su applicazioni di riferimento . L'effettivo tasso di successo varia notevolmente da un'applicazione all'altra. In particolare, le applicazioni di streaming video e audio hanno spesso un rapporto di successo vicino allo zero, perché ogni bit di dati nel flusso viene letto una volta per la prima volta (mancanza obbligatoria), utilizzato e quindi mai più letto o scritto. Ancora peggio, molti algoritmi di cache (in particolare, LRU) consentono a questi dati in streaming di riempire la cache, spingendo fuori dalla cache le informazioni che verranno presto riutilizzate ( inquinamento della cache ).

Altre cose da considerare:

Articoli con costi diversi: conserva gli articoli che sono costosi da ottenere, ad esempio quelli che richiedono molto tempo per essere reperiti.
Elementi che occupano più cache: se gli elementi hanno dimensioni diverse, la cache potrebbe voler eliminare un elemento di grandi dimensioni per archiviarne diversi più piccoli.
Elementi che scadono con il tempo: alcune cache conservano informazioni che scadono (ad es. una cache delle notizie, una cache DNS o una cache del browser web). Il computer potrebbe eliminare gli elementi perché sono scaduti. A seconda delle dimensioni della cache, potrebbe non essere necessario alcun ulteriore algoritmo di memorizzazione nella cache per eliminare gli elementi.

Esistono anche vari algoritmi per mantenere la coerenza della cache . Ciò si applica solo alla situazione in cui vengono utilizzate più cache indipendenti per gli stessi dati (ad esempio più server di database che aggiornano il singolo file di dati condiviso).

Politiche

Algoritmo di Bélády

L' algoritmo di memorizzazione nella cache più efficiente sarebbe quello di scartare sempre le informazioni che non saranno necessarie per molto tempo in futuro. Questo risultato ottimale è indicato come algoritmo ottimale di Bélády /politica di sostituzione semplicemente ottimale o algoritmo chiaroveggente . Poiché è generalmente impossibile prevedere fino a che punto in futuro saranno necessarie le informazioni, ciò non è generalmente attuabile nella pratica. Il minimo pratico può essere calcolato solo dopo la sperimentazione e si può confrontare l'efficacia dell'algoritmo di cache effettivamente scelto.

Nel momento in cui si verifica un errore di pagina , in memoria è presente una serie di pagine. Nell'esempio, alla sequenza di '5', '0', '1' si accede rispettivamente da Frame 1, Frame 2, Frame 3. Quindi, quando si accede a "2", sostituisce il valore "5", che è nel frame 1 poiché prevede che il valore "5" non sarà accessibile nel prossimo futuro. Poiché un sistema operativo generico della vita reale non può effettivamente prevedere quando si accederà a "5", l'algoritmo di Bélády non può essere implementato su un tale sistema.

Primo ad uscire primo (FIFO)

Utilizzando questo algoritmo la cache si comporta allo stesso modo di una coda FIFO . La cache elimina i blocchi nell'ordine in cui sono stati aggiunti, indipendentemente dalla frequenza o dal numero di accessi a cui è stato effettuato prima.

Last in first out (LIFO) o First in last out (FILO)

Utilizzando questo algoritmo la cache si comporta allo stesso modo di uno stack e al contrario di una coda FIFO. La cache elimina per primo il blocco aggiunto più di recente senza alcun riguardo alla frequenza o al numero di accessi a cui è stato effettuato prima.

Utilizzato meno di recente (LRU)

Elimina per primi gli elementi utilizzati meno di recente. Questo algoritmo richiede di tenere traccia di ciò che è stato utilizzato e quando, il che è costoso se si vuole assicurarsi che l'algoritmo scarti sempre l'elemento utilizzato meno di recente. Le implementazioni generali di questa tecnica richiedono di mantenere i "bit di età" per le linee di cache e di tenere traccia della linea di cache "Usata meno di recente" in base ai bit di età. In tale implementazione, ogni volta che viene utilizzata una linea di cache, l'età di tutte le altre linee di cache cambia. LRU è in realtà una famiglia di algoritmi di memorizzazione nella cache con membri tra cui 2Q di Theodore Johnson e Dennis Shasha e LRU/K di Pat O'Neil, Betty O'Neil e Gerhard Weikum.

La sequenza di accesso per l'esempio seguente è ABCDED F.

Nell'esempio sopra una volta che ABCD viene installato nei blocchi con numeri di sequenza (Incremento 1 per ogni nuovo accesso) e quando si accede a E, è un errore e deve essere installato in uno dei blocchi. Secondo l'algoritmo LRU, poiché A ha il grado più basso (A (0)), E sostituirà A.

Nel penultimo passo si accede a D e quindi il numero di sequenza viene aggiornato.

LRU, come molte altre politiche di sostituzione, può essere caratterizzata utilizzando un campo di transizione di stato in uno spazio vettoriale, che decide i cambiamenti di stato della cache dinamica in modo simile a come un campo elettromagnetico determina il movimento di una particella carica posta al suo interno.

Tempo consapevole utilizzato meno di recente (TLRU)

Il Time consapevole Least Recent Used (TLRU) è una variante di LRU progettata per la situazione in cui i contenuti memorizzati nella cache hanno una durata valida. L'algoritmo è adatto nelle applicazioni di cache di rete, come le reti incentrate sulle informazioni (ICN), le reti di distribuzione dei contenuti (CDN) e le reti distribuite in generale. TLRU introduce un nuovo termine: TTU (Time to Use). TTU è un timestamp di un contenuto/pagina che stabilisce il tempo di fruibilità del contenuto in base alla località del contenuto e all'annuncio dell'editore del contenuto. A causa di questo timestamp basato sulla località, TTU fornisce un maggiore controllo all'amministratore locale per regolare l'archiviazione di rete. Nell'algoritmo TLRU, quando arriva un contenuto, un nodo della cache calcola il valore TTU locale in base al valore TTU assegnato dall'editore del contenuto. Il valore TTU locale viene calcolato utilizzando una funzione definita localmente. Una volta calcolato il valore TTU locale, la sostituzione del contenuto viene eseguita su un sottoinsieme del contenuto totale archiviato nel nodo della cache. Il TLRU garantisce che i contenuti meno popolari e di piccole dimensioni debbano essere sostituiti con i contenuti in arrivo.

Utilizzato più di recente (MRU)

A differenza di Meno di recente utilizzo (LRU), MRU elimina per primi gli elementi utilizzati più di recente . Nei risultati presentati all'undicesima conferenza VLDB , Chou e DeWitt hanno notato che "Quando un file viene scansionato ripetutamente in un modello di riferimento [Looping Sequential], MRU è il miglior algoritmo di sostituzione ". Successivamente, altri ricercatori che si sono presentati alla 22a conferenza VLDB hanno notato che per i modelli di accesso casuale e le scansioni ripetute su set di dati di grandi dimensioni (a volte noti come modelli di accesso ciclico) gli algoritmi di cache MRU hanno più risultati di LRU a causa della loro tendenza a conservare i dati più vecchi. Gli algoritmi MRU sono più utili in situazioni in cui più un elemento è vecchio, più è probabile che sia accessibile.

La sequenza di accesso per l'esempio seguente è ABCDECD B.

Qui, ABCD vengono inseriti nella cache poiché c'è ancora spazio disponibile. Al quinto accesso E, vediamo che il blocco che conteneva D è ora sostituito con E poiché questo blocco è stato utilizzato più di recente. Un altro accesso a C e al successivo accesso a D, C viene sostituito in quanto era il blocco a cui si accedeva appena prima di D e così via.

Pseudo-LRU (PLRU)

Per le cache della CPU con una grande associatività (generalmente >4 modi), il costo di implementazione di LRU diventa proibitivo. In molte cache della CPU è sufficiente uno schema che scarta quasi sempre uno degli elementi utilizzati meno di recente, quindi molti progettisti di CPU scelgono un algoritmo PLRU che richiede solo un bit per elemento della cache per funzionare. PLRU ha in genere un rapporto di missaggio leggermente peggiore, ha una latenza leggermente migliore, utilizza una potenza leggermente inferiore rispetto a LRU e costi generali inferiori rispetto a LRU.

L'esempio seguente mostra come i bit funzionano come un albero binario di puntatori a 1 bit che puntano al sottoalbero utilizzato meno di recente. Seguendo la catena del puntatore al nodo foglia si identifica il candidato di sostituzione. Al momento dell'accesso, tutti i puntatori della catena dal nodo foglia della via a cui si accede al nodo radice vengono impostati per puntare a un sottoalbero che non contiene la via a cui si accede.

La sequenza di accesso è ABCD E.

Il principio qui è semplice da capire se osserviamo solo i puntatori a freccia. Quando c'è un accesso a un valore, diciamo 'A', e non possiamo trovarlo nella cache, allora lo carichiamo dalla memoria e lo posizioniamo nel blocco dove stanno puntando le frecce , andando dall'alto verso il basso. Dopo aver posizionato quel blocco, capovolgiamo le stesse frecce in modo che puntino nella direzione opposta . Nell'esempio sopra vediamo come è stata posizionata 'A', seguita da 'B', 'C e 'D'. Quindi, quando la cache si è riempita, "E" ha sostituito "A" perché era lì che le frecce puntavano in quel momento e le frecce che portavano ad "A" sono state capovolte per puntare nella direzione opposta. Le frecce poi hanno portato a 'B', che sarà il blocco sostituito al successivo errore di cache.

Sostituzione casuale (RR)

Seleziona casualmente un elemento candidato e lo scarta per fare spazio quando necessario. Questo algoritmo non richiede di conservare alcuna informazione sulla cronologia degli accessi. Per la sua semplicità, è stato utilizzato nei processori ARM . Ammette una simulazione stocastica efficiente.

La sequenza di accesso per l'esempio seguente è ABCDEBD F.

LRU segmentato (SLRU)

La cache SLRU è divisa in due segmenti, un segmento di prova e un segmento protetto. Le righe in ogni segmento sono ordinate dalla più recente alla meno visitata. I dati dei mancati vengono aggiunti alla cache all'estremità più recente del segmento in prova. Gli hit vengono rimossi dalla posizione in cui risiedono attualmente e aggiunti all'estremità più recente del segmento protetto. Le linee del segmento protetto sono state così utilizzate almeno due volte. Il segmento protetto è finito, quindi la migrazione di una linea dal segmento in prova al segmento protetto può forzare la migrazione della linea LRU nel segmento protetto all'estremità utilizzata più di recente (MRU) del segmento in prova, dando a questa linea un'altra possibilità a cui accedere prima di essere sostituiti. Il limite di dimensione sul segmento protetto è un parametro SLRU che varia in base ai modelli del carico di lavoro di I/O. Ogni volta che i dati devono essere eliminati dalla cache, le linee vengono ottenute dall'estremità LRU del segmento di prova.

Utilizzo meno frequente (LFU)

Conta la frequenza con cui è necessario un articolo. Quelli che vengono utilizzati meno spesso vengono scartati per primi. Funziona in modo molto simile a LRU, tranne per il fatto che invece di memorizzare il valore di quanto recentemente è stato effettuato l'accesso a un blocco, memorizziamo il valore di quante volte è stato effettuato l'accesso. Quindi, ovviamente, durante l'esecuzione di una sequenza di accesso, sostituiremo un blocco che è stato utilizzato meno volte dalla nostra cache. Ad esempio, se A è stato utilizzato (acceso) 5 volte e B è stato utilizzato 3 volte e gli altri C e D sono stati utilizzati 10 volte ciascuno, sostituiremo B.

Utilizzo meno frequente di recente (LFRU)

Lo schema di sostituzione della cache meno frequente (LFRU) combina i vantaggi degli schemi LFU e LRU. LFRU è adatto per applicazioni cache "in rete", come reti incentrate sulle informazioni (ICN), reti di distribuzione di contenuti (CDN) e reti distribuite in generale. In LFRU, la cache è divisa in due partizioni chiamate partizioni privilegiate e non privilegiate. La partizione privilegiata può essere definita come partizione protetta. Se il contenuto è molto popolare, viene inserito nella partizione privilegiata. La sostituzione della partizione privilegiata viene eseguita come segue: LFRU rimuove il contenuto dalla partizione non privilegiata, invia il contenuto dalla partizione privilegiata alla partizione non privilegiata e infine inserisce il nuovo contenuto nella partizione privilegiata. Nella procedura di cui sopra viene utilizzata la LRU per la partizione privilegiata e uno schema LFU approssimato (ALFU) per la partizione non privilegiata, da cui l'abbreviazione LFRU.

L'idea di base è filtrare i contenuti popolari localmente con lo schema ALFU e spingere i contenuti popolari in una delle partizioni privilegiate.

LFU con invecchiamento dinamico (LFUDA)

Una variante chiamata LFU with Dynamic Aging (LFUDA) che utilizza l'invecchiamento dinamico per adattarsi ai cambiamenti nell'insieme di oggetti popolari. Aggiunge un fattore di età della cache al conteggio dei riferimenti quando un nuovo oggetto viene aggiunto alla cache o quando viene fatto nuovamente riferimento a un oggetto esistente. LFUDA incrementa la durata della cache durante l'eliminazione dei blocchi impostandola sul valore della chiave dell'oggetto eliminato. Pertanto, l'età della cache è sempre inferiore o uguale al valore minimo della chiave nella cache. Supponiamo che quando un oggetto è stato utilizzato frequentemente in passato e ora diventa impopolare, rimarrà nella cache per molto tempo, impedendo così agli oggetti nuovi o meno popolari di sostituirlo. Quindi questo invecchiamento dinamico viene introdotto per ridurre il conteggio di tali oggetti, rendendoli così idonei per la sostituzione. Il vantaggio di LFUDA è che riduce l' inquinamento della cache causato da LFU quando le dimensioni della cache sono molto piccole. Quando le dimensioni della cache sono grandi, poche decisioni di sostituzione sono sufficienti e l' inquinamento della cache non sarà un problema.

Set di recency interreferenziale basso (LIRS)

LIRS è un algoritmo di sostituzione della pagina con prestazioni migliorate rispetto a LRU e molti altri algoritmi di sostituzione più recenti. Ciò si ottiene utilizzando la distanza di riutilizzo come metrica per classificare dinamicamente le pagine a cui si accede per prendere una decisione di sostituzione. I LIRS affrontano efficacemente i limiti di LRU utilizzando la recency per valutare l'Inter-Reference Recency (IRR) per prendere una decisione di sostituzione.

Nella figura sopra, "x" rappresenta che si accede a un blocco al tempo t. Supponiamo che se si accede al blocco A1 al tempo 1, Recency diventerà 0 poiché questo è il primo blocco a cui si accede e IRR sarà 1 poiché prevede che si accederà di nuovo ad A1 nel tempo 3. Nel tempo 2 poiché si accede ad A4, il recency diventerà 0 per A4 e 1 per A1 perché A4 è l'oggetto a cui si è avuto accesso più di recente e IRR diventerà 4 e andrà avanti. Al tempo 10, l'algoritmo LIRS avrà due insiemi LIR set = {A1, A2} e HIR set = {A3, A4, A5}. Ora, al tempo 10, se c'è accesso ad A4, si verifica un errore. L'algoritmo LIRS ora eliminerà A5 invece di A2 a causa della sua più grande attualità.

CLOCK-Pro

L'algoritmo LRU non può essere implementato direttamente nel percorso critico dei sistemi informatici, come i sistemi operativi , a causa del suo elevato sovraccarico. Per l'implementazione viene comunemente utilizzata un'approssimazione di LRU, chiamata CLOCK . Allo stesso modo, CLOCK-Pro è un'approssimazione di LIRS per un'implementazione a basso costo nei sistemi. CLOCK-Pro è sotto il framework CLOCK di base , ma ha tre principali meriti distinti. Innanzitutto, CLOCK-Pro ha tre "lancette dell'orologio" in contrasto con una semplice struttura di CLOCK in cui viene utilizzata solo una "lancetta". Con le tre lancette, CLOCK-Pro è in grado di misurare in modo approssimativo la distanza di riutilizzo degli accessi ai dati. In secondo luogo, vengono mantenuti tutti i meriti di LIRS, come la rapida rimozione di elementi di dati con accesso una tantum e/o di bassa località. In terzo luogo, la complessità di CLOCK-Pro è la stessa di CLOCK, quindi è facile da implementare a basso costo. L'implementazione della sostituzione della cache del buffer nella versione corrente di Linux è una combinazione di LRU e CLOCK-Pro.

Cache sostitutiva adattiva (ARC)

Equilibrio costante tra LRU e LFU, per migliorare il risultato combinato. ARC migliora SLRU utilizzando le informazioni sugli elementi della cache eliminati di recente per regolare dinamicamente le dimensioni del segmento protetto e del segmento in prova per utilizzare al meglio lo spazio disponibile nella cache. L'algoritmo di sostituzione adattiva è spiegato con l'esempio.

AdaptiveClimb (AC)

Utilizza il recente hit/miss per regolare il salto in cui in salita qualsiasi hit sposta la posizione di uno slot in alto, e in LRU hit cambia la posizione del hit in alto. Quindi, beneficiando dell'ottimalità della salita quando il programma è in un ambito fisso, e del rapido adattamento a un nuovo ambito, come fa LRU. Supporta anche la condivisione della cache tra i core rilasciando extra quando i riferimenti sono nella parte superiore della cache.

Orologio con sostituzione adattiva (CAR)

Combina i vantaggi di Adaptive Replacement Cache (ARC) e CLOCK . CAR ha prestazioni paragonabili a ARC e supera sostanzialmente sia LRU che CLOCK. Come ARC, CAR è autoregolante e non richiede parametri magici specificati dall'utente. Utilizza 4 liste doppiamente collegate: due orologi T1 e T2 e due semplici liste LRU B1 e B2. L'orologio T1 memorizza le pagine in base a "recency" o "utilità a breve termine", mentre T2 memorizza le pagine con "frequenza" o "utilità a lungo termine". T1 e T2 contengono quelle pagine che sono nella cache, mentre B1 e B2 contengono pagine che sono state recentemente eliminate rispettivamente da T1 e T2. L'algoritmo cerca di mantenere la dimensione di queste liste B1≈T2 e B2≈T1. Le nuove pagine vengono inserite in T1 o T2. Se c'è un hit in B1 la dimensione di T1 è aumentata e allo stesso modo se c'è un hit in B2 la dimensione di T1 è diminuita. La regola di adattamento utilizzata ha lo stesso principio di quella in ARC, investi di più in elenchi che daranno più risultati quando vengono aggiunte più pagine.

Multicoda (MQ)

L'algoritmo multi-coda o MQ è stato sviluppato per migliorare le prestazioni della cache del buffer di secondo livello per, ad esempio, una cache del buffer del server. È introdotto in un articolo di Zhou, Philbin e Li. La cache MQ contiene un numero m di code LRU: Q ₀ , Q ₁ , ..., Q _{m -1} . Qui, il valore di m rappresenta una gerarchia basata sulla durata di tutti i blocchi in quella particolare coda. Ad esempio, se j > i , i blocchi in Q _j avranno una durata maggiore di quelli in Q _i . Oltre a questi c'è un altro buffer storico Q _out , una coda che mantiene un elenco di tutti i Block Identifier insieme alle loro frequenze di accesso. Quando Q _out è pieno, l'identificatore più vecchio viene eliminato. I blocchi rimangono nelle code LRU per una determinata durata, definita dinamicamente dall'algoritmo MQ come la distanza temporale massima tra due accessi allo stesso file o il numero di blocchi della cache, a seconda di quale sia maggiore. Se un blocco non è stato referenziato durante la sua vita, viene retrocesso da Q _i a Q _{i −1} o eliminato dalla cache se si trova in Q ₀ . Ogni coda ha anche un numero massimo di accessi; se si accede a un blocco nella coda Q _i più di 2 ⁱ volte, questo blocco viene promosso a Q _{i +1} finché non viene eseguito l'accesso più di 2 ^{i +1} volte o la sua durata scade. All'interno di una data coda, i blocchi sono classificati in base alla recency di accesso, secondo LRU .

Possiamo vedere dalla Fig. come le code m LRU sono poste nella cache. Si veda anche dalla Fig. come il Q _out memorizzi gli identificatori di blocco e le loro corrispondenti frequenze di accesso. una è stata posta in Q ₀ come era accessibile solo una volta di recente e può controllare in Q _out come b e c sono stati collocati in Q ₁ e Q ₂ rispettivamente loro frequenze di accesso sono 2 e 4. La coda in cui è posto un blocco dipende dalla frequenza di accesso (f) come log ₂ (f). Quando la cache è piena, il primo blocco da eliminare sarà l'head di Q ₀ in questo caso a . Se una si accede ancora una volta si sposterà a Q ₁ sotto b .

Pannier: algoritmo di memorizzazione nella cache basato su container per oggetti composti

Pannier è un meccanismo di memorizzazione nella cache flash basato su contenitori che identifica contenitori divergenti (eterogenei) in cui i blocchi contenuti al loro interno hanno modelli di accesso molto variabili. Pannier utilizza una struttura di coda di sopravvivenza basata su code di priorità per classificare i container in base al loro tempo di sopravvivenza, che è proporzionale ai dati in tempo reale nel container. Pannier è costruito sulla base di Segmented LRU (S2LRU), che separa i dati caldi e freddi. Pannier utilizza anche un controller di feedback multi-step per limitare le scritture flash per garantire la durata del flash.

Languages

In other projects