algorithmEdit di Bélády
L’algoritmo di caching più efficiente sarebbe quello di scartare sempre le informazioni che non saranno necessarie per il tempo più lungo in futuro. Questo risultato ottimale è indicato come algoritmo ottimale di Bélády/simply optimal replacement policy o algoritmo chiaroveggente. Poiché è generalmente impossibile prevedere fino a che punto in futuro saranno necessarie informazioni, questo non è generalmente implementabile 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, un insieme di pagine è in memoria. Nell’esempio, la sequenza di ‘5’, ‘0’, ‘1’ si accede da Frame 1, Frame 2, Frame 3 rispettivamente. Quindi, quando si accede a ‘2’, sostituisce il valore’ 5′, che si trova nel frame 1 poiché prevede che il valore’ 5 ‘ non sarà accessibile nel prossimo futuro. Poiché un sistema operativo general purpose reale non può effettivamente prevedere quando si accederà a ‘5’, l’algoritmo di Bélády non può essere implementato su tale sistema.
First in first out (FIFO)Edit
Usando questo algoritmo la cache si comporta allo stesso modo di una coda FIFO. La cache sfratta i blocchi nell’ordine in cui sono stati aggiunti, senza alcun riguardo a quanto spesso o quante volte sono stati raggiunti prima.
Last in first out (LIFO) o First in last out (FILO)Edit
Usando questo algoritmo la cache si comporta allo stesso modo di uno stack e esattamente il modo opposto di una coda FIFO. La cache sfratta il blocco aggiunto più di recente prima senza alcun riguardo a quanto spesso o quante volte è stato raggiunto prima.
Least Recently used (LRU)Edit
Scarta prima gli elementi usati meno di recente. Questo algoritmo richiede di tenere traccia di ciò che è stato utilizzato quando, il che è costoso se si vuole assicurarsi che l’algoritmo scarta sempre l’elemento utilizzato meno di recente. Le implementazioni generali di questa tecnica richiedono di mantenere ” bit di età “per le linee di cache e tenere traccia della linea di cache” meno utilizzata 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 caching 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 è A B C D E D F.
Nell’esempio precedente una volta A B C D viene installato nei blocchi con numeri di sequenza (Incremento 1 per ogni nuovo accesso) e quando si accede a E, è una miss e deve essere installato in uno dei blocchi. Secondo l’algoritmo LRU, poiché A ha il rango più basso(A (0)), E sostituirà A.
Nel penultimo passaggio si accede a D e quindi il numero di sequenza viene aggiornato.
LRU, come molte altre politiche di sostituzione, può essere caratterizzato utilizzando un campo di transizione di stato in uno spazio vettoriale, che decide lo stato dinamico della cache cambia simile a come un campo elettromagnetico determina il movimento di una particella carica posto in esso.
Time aware least recently used (TLRU)Modifica
Il Time aware Least Recently Used (TLRU) è una variante di LRU progettata per la situazione in cui i contenuti memorizzati nella cache hanno un tempo di vita valido. L’algoritmo è adatto in applicazioni di cache di rete, come Information-centric networking (ICN), Content Delivery Networks (CDN) e 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 usabilità per il contenuto in base alla località del contenuto e all’annuncio dell’editore del contenuto. Grazie a questo timestamp basato località, TTU fornisce un maggiore controllo per l’amministratore locale per regolare in storage di rete.Nell’algoritmo TLRU, quando arriva una parte di contenuto, un nodo 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 memorizzato nel nodo cache. Il TLRU assicura che il contenuto di vita meno popolare e piccolo dovrebbe essere sostituito con il contenuto in entrata.
Most Recently used (MRU)Edit
Scarta, a differenza di LRU, gli elementi utilizzati più di recente prima. Nei risultati presentati alla conferenza VLDB 11th, Chou e DeWitt hanno osservato che ” Quando un file viene ripetutamente scansionato in un modello di riferimento, MRU è il miglior algoritmo di sostituzione.”Successivamente, altri ricercatori che hanno presentato alla 22a conferenza VLDB hanno notato che per i modelli di accesso casuale e le scansioni ripetute su grandi set di dati (a volte noti come modelli di accesso ciclico) Gli algoritmi di cache MRU hanno più hit rispetto a 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 è A B C D E C D B.
Qui, A B C D sono collocati nella cache in quanto vi è ancora spazio disponibile. Al 5 ° 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 come era il blocco a cui si accedeva poco prima di D e così via.
Pseudo-LRU (PLRU)Modifica
Per le cache della CPU con grande associatività (generalmente> 4 modi), il costo di implementazione di LRU diventa proibitivo. In molte cache della CPU, uno schema che scarta quasi sempre uno degli elementi utilizzati meno di recente è sufficiente, quindi molti progettisti di CPU scelgono un algoritmo PLRU che richiede solo un bit per elemento della cache per funzionare.PLRU in genere ha un rapporto di miss leggermente peggiore, ha una latenza leggermente migliore, utilizza un po ‘ meno potenza di LRU e spese generali inferiori rispetto a LRU.
Il seguente esempio mostra come i Bit funzionano come un albero binario di puntatori a 1 bit che puntano al sottoalbero usato meno di recente. Seguendo la catena del puntatore al nodo foglia identifica il candidato di sostituzione. Al momento di un accesso tutti i puntatori nella catena dal nodo foglia del modo di accesso al nodo radice sono impostati per puntare alla sottostruttura che non contiene il modo di accesso.
La sequenza di accesso è A B C D E.
Il principio qui è semplice da capire se guardiamo solo i puntatori della freccia. Quando c’è un accesso a un valore, diciamo ‘A’, e non possiamo trovarlo nella cache, quindi lo carichiamo dalla memoria e lo posizioniamo nel blocco in cui le frecce stanno attualmente puntando, andando dall’alto verso il basso. Dopo aver posizionato quel blocco, lanciamo quelle stesse frecce in modo che puntino in senso opposto. Nell’esempio sopra vediamo come è stato posizionato ‘A’, seguito da ‘B’, ‘C e ‘D’. Poi, mentre la cache diventava piena, ” E “sostituiva” A “perché era lì che le frecce puntavano in quel momento, e le frecce che portavano a” A ” venivano capovolte per puntare nella direzione opposta. Le frecce hanno poi portato a ‘B’, che sarà il blocco sostituito sulla prossima cache miss.
Sostituzione casuale (RR)Modifica
Seleziona casualmente un elemento candidato e lo scarta per creare spazio quando necessario. Questo algoritmo non richiede la conservazione di 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 è A B C D E B D F
LRU segmentato (SLRU)Edit
La cache SLRU è divisa in due segmenti, un segmento di prova e un segmento protetto. Le linee in ogni segmento sono ordinate dal più al meno recente accesso. I dati da miss vengono aggiunti alla cache alla fine più recente del segmento di prova. Gli hit vengono rimossi dal luogo in cui risiedono attualmente e aggiunti all’estremità del segmento protetto più recente. Le linee nel segmento protetto sono state quindi raggiunte almeno due volte. Il segmento protetto è finito, quindi la migrazione di una linea dal segmento di prova al segmento protetto può forzare la migrazione della linea LRU nel segmento protetto all’estremità più utilizzata (MRU) del segmento di prova, dando a questa linea un’altra possibilità di accesso prima di essere sostituita. Il limite di dimensione del segmento protetto è un parametro SLRU che varia in base ai modelli di carico di lavoro I/O. Ogni volta che i dati devono essere scartati dalla cache, le righe vengono ottenute dalla fine LRU del segmento di prova.
Least-frequently used (LFU)Modifica
Conta la frequenza con cui un elemento è necessario. Quelli che vengono utilizzati meno spesso vengono scartati per primi. Funziona in modo molto simile a LRU, tranne 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, naturalmente, durante l’esecuzione di una sequenza di accesso, sostituiremo un blocco che è stato utilizzato il minor numero di volte dalla nostra cache. Ad esempio, se A è stato usato (accesso) 5 volte e B è stato usato 3 volte e altri C e D sono stati usati 10 volte ciascuno, sostituiremo B.
LFRU (Least frequent recently used)Modifica
Lo schema di sostituzione della cache LFRU (Least Frequently Recently Used) combina i vantaggi degli schemi LFU e LRU. LFRU è adatto per applicazioni di cache “in rete”, come ICN (Information-Centric Networking), CDN (Content Delivery Networks) 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 una partizione protetta. Se il contenuto è molto popolare, viene inserito nella partizione privilegiata. La sostituzione della partizione privilegiata avviene come segue: LFRU elimina il contenuto dalla partizione non privilegiata, spinge il contenuto dalla partizione privilegiata alla partizione non privilegiata e infine inserisce nuovo contenuto nella partizione privilegiata. Nella procedura precedente la LRU viene utilizzata per la partizione privilegiata e uno schema LFU approssimato (ALFU) viene utilizzato per la partizione non privilegiata, da cui l’abbreviazione LFRU.
L’idea di base è di filtrare i contenuti localmente popolari con lo schema ALFU e spingere i contenuti popolari in una delle partizioni privilegiate.
LFU con invecchiamento dinamico (LFUDA)Modifica
Una variante chiamata LFU con invecchiamento dinamico (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 un oggetto esistente viene ri-referenziato. LFUDA incrementa l’età della cache quando si sfrattano i blocchi impostandola sul valore chiave dell’oggetto sfrattato. Pertanto, l’età della cache è sempre inferiore o uguale al valore minimo della chiave nella cache. Supponiamo che quando in passato si accedeva frequentemente a un oggetto e ora diventa impopolare, rimarrà nella cache per un lungo periodo impedendo così agli oggetti nuovi o meno popolari di sostituirlo. Quindi questo invecchiamento dinamico viene introdotto per ridurre il conteggio di tali oggetti rendendoli idonei alla 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.
Low inter-reference recency set (LIRS)Edit
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. Le LIR affrontano efficacemente i limiti delle LRU utilizzando recency per valutare la Recency inter-Reference (IRR) per prendere una decisione sostitutiva.
Nella figura precedente, “x” rappresenta l’accesso a un blocco al momento t. Supponiamo che se si accede al blocco A1 al tempo 1, la Recency diventerà 0 poiché questo è il primo blocco a cui si accede e IRR sarà 1 poiché prevede che A1 sarà nuovamente accessibile nel tempo 3. Nel tempo 2 dall’accesso A4, la recency diventerà 0 per A4 e 1 per A1 perché A4 è l’oggetto a cui si accede più di recente e IRR diventerà 4 e andrà avanti. Al tempo 10, l’algoritmo LIRS avrà due set LIR set = {A1, A2} e HIR set = {A3, A4, A5}. Ora al momento 10 se c’è accesso a A4, si verifica la mancanza. L’algoritmo LIRS ora sfratterà A5 invece di A2 a causa della sua più grande recente.
CLOCK-ProEdit
L’algoritmo LRU non può essere implementato direttamente nel percorso critico dei sistemi informatici, come i sistemi operativi, a causa del suo alto sovraccarico. Un’approssimazione di LRU, chiamato OROLOGIO è comunemente usato per l’implementazione. Allo stesso modo, CLOCK-Pro è un’approssimazione di LIRS per un’implementazione a basso costo nei sistemi. CLOCK-Pro è sotto il quadro di CLOCK di base, ma ha tre principali meriti distinti. Innanzitutto, CLOCK-Pro ha tre ” lancette dell’orologio “in contrasto con una semplice struttura dell’OROLOGIO in cui viene utilizzata una sola” mano”. Con le tre lancette, CLOCK-Pro è in grado di misurare la distanza di riutilizzo degli accessi ai dati in modo approssimativo. In secondo luogo, vengono mantenuti tutti i meriti di LIRS, come lo sfratto rapido di elementi di dati di accesso una tantum e/o di bassa località. In terzo luogo, la complessità del CLOCK-Pro è la stessa di quella di CLOCK, quindi è facile da implementare a basso costo. L’implementazione di buffer cache replacement nella versione corrente di Linux è una combinazione di LRU e CLOCK-Pro.
Adaptive replacement cache (ARC)Modifica
Bilancia costantemente tra LRU e LFU, per migliorare il risultato combinato. ARC migliora la SLRU utilizzando le informazioni sugli elementi della cache eliminati di recente per regolare dinamicamente le dimensioni del segmento protetto e del segmento di prova per utilizzare al meglio lo spazio cache disponibile. L’algoritmo di sostituzione adattivo è spiegato con l’esempio.
AdaptiveClimb (AC)Edit
Utilizza hit / miss recenti per regolare il salto in cui in climb qualsiasi hit commuta la posizione di uno slot verso l’alto, e in LRU hit commuta la posizione del hit verso l’alto. Pertanto, 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 core rilasciando extra quando i riferimenti sono nella parte superiore della cache.
Orologio con adaptive replacement (CAR)Modifica
Combina i vantaggi di Adaptive Replacement Cache (ARC) e CLOCK. AUTO ha prestazioni paragonabili a ARC, e sostanzialmente sovraperforma sia LRU e OROLOGIO. Come ARC, CAR è auto-tuning 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 “utility a breve termine” mentre T2 memorizza le pagine con “frequency”o” long term utility”. T1 e T2 contengono quelle pagine che sono nella cache, mentre B1 e B2 contengono pagine che sono state recentemente sfrattate rispettivamente da T1 e T2. L’algoritmo cerca di mantenere la dimensione di questi elenchi B1≈T2 e B2≈T1. Nuove pagine vengono inserite in T1 o T2. Se c’è un colpo in B1 la dimensione di T1 è aumentata e allo stesso modo se c’è un colpo in B2 la dimensione di T1 è diminuita. La regola di adattamento utilizzata ha lo stesso principio di quella di ARC, investire di più in elenchi che daranno più risultati quando vengono aggiunte più pagine.
Multi queue (MQ)Edit
L’algoritmo multi queue o MQ è stato sviluppato per migliorare le prestazioni della cache buffer di secondo livello per esempio una cache buffer del server. Viene introdotto in un documento da Zhou, Philbin e Li. La cache MQ contiene un numero m di code LRU: Q0, Q1,…, Qm-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 Qj avranno una durata maggiore rispetto a quelli in Qi. Oltre a questi c’è un altro buffer di cronologia Qout, una coda che mantiene un elenco di tutti gli identificatori di blocco insieme alle loro frequenze di accesso. Quando Qout è pieno l’identificatore più vecchio viene sfrattato. I blocchi rimangono nelle code LRU per una data durata, che è definita dinamicamente dall’algoritmo MQ come la distanza temporale massima tra due accessi allo stesso file o il numero di blocchi di cache, a seconda di quale sia maggiore. Se un blocco non è stato referenziato durante la sua vita, viene retrocesso da Qi a Qi−1 o sfrattato dalla cache se è in Q0. Ogni coda ha anche un numero massimo di accessi; se si accede a un blocco in queue Qi più di 2i volte, questo blocco viene promosso a Qi + 1 fino a quando non si accede più di 2i+1 volte o la sua durata scade. All’interno di una determinata coda, i blocchi sono classificati in base alla recency of access, secondo LRU.
Possiamo vedere da Fig. come vengono posizionate le code m LRU nella cache. Vedi anche da Fig. come il Qout memorizza gli identificatori di blocco e le loro frequenze di accesso corrispondenti. a è stato inserito in Q0 in quanto è stato raggiunto solo una volta di recente e possiamo controllare in Qout come b e c sono stati collocati in Q1 e Q2 rispettivamente come le loro frequenze di accesso sono 2 e 4. La coda in cui è posizionato un blocco dipende dalla frequenza di accesso(f) come log2(f). Quando la cache è piena, il primo blocco da sfrattare sarà il capo di Q0 in questo caso a. Se si accede a a un’altra volta, si sposterà su Q1 sotto b.
Pannier: algoritmo di caching basato su container per oggetti compositimodifica
Pannier è un meccanismo di caching flash basato su container che identifica contenitori divergenti (eterogenei) in cui i blocchi in esso contenuti hanno Pannier utilizza una struttura di coda di sopravvivenza basata su coda di priorità per classificare i contenitori in base al loro tempo di sopravvivenza, che è proporzionale ai dati in tempo reale nel contenitore. Pannier è costruito sulla base di LRU segmentato (S2LRU), che segrega i dati caldi e freddi. Pannier utilizza anche un controller di feedback multi-step per strozzare le scritture flash per garantire la durata del flash.