Algoritmo cache
Un algoritmo Cache è un algoritmo utilizzato per gestire una cache o un gruppo di dati. Quando la cache è piena, decide quale elemento deve essere cancellato dalla cache. La parola "hit rate" descrive la frequenza con cui una richiesta può essere servita dalla cache. Il termine latenza descrive per quanto tempo si può ottenere un elemento della cache. Gli aloritmi della cache sono un compromesso tra hit rate e latenza.
- L'algoritmo di caching più efficiente sarebbe quello di scartare sempre le informazioni che non saranno più necessarie in futuro. Questo risultato ottimale è indicato come l'algoritmo ottimale di Belady o l'algoritmo del 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 con il minimo ottimale.
- Least Recently Used (LRU): elimina prima gli articoli meno usati di recente. Questo algoritmo richiede di tenere traccia di ciò che è stato usato quando. Questo è costoso se si vuole essere sicuri che l'algoritmo elimini sempre l'elemento meno usato 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 "Least Recently Used" basata sui bit di età. In tale implementazione, ogni volta che viene usata una linea di cache, l'età di tutte le altre linee di cache cambia. LRU è in realtà una famiglia di algoritmi di cache con membri che includono: 2Q di Theodore Johnson e Dennis Shasha e LRU/K di Pat O'Neil, Betty O'Neil e Gerhard Weikum.
- Ultimamente usato (MRU): Questo algoritmo cancella prima gli elementi usati più di recente. Questo meccanismo di caching è comunemente usato per le cache di memoria di database.
- Pseudo-LRU (PLRU): Ci sono alcuni casi in cui la LRU è molto difficile da implementare. In questi casi può essere sufficiente sapere che nella maggior parte dei casi, uno degli elementi meno utilizzati di recente viene cancellato. L'algoritmo PLRU può essere usato lì, perché ha bisogno di un solo bit per ogni elemento della cache per funzionare.
- 2-way set associativo: per cache di CPU ad alta velocità dove anche PLRU è troppo lento. L'indirizzo di un nuovo elemento viene utilizzato per calcolare una delle due possibili posizioni nella cache dove è permesso andare. Il LRU dei due viene scartato. Questo richiede un bit per ogni coppia di linee di cache, per indicare quale delle due è stata usata meno di recente.
- Cache con mappatura diretta: per le cache delle CPU a più alta velocità, dove anche le cache associative a 2 vie sono troppo lente. L'indirizzo del nuovo elemento viene utilizzato per calcolare l'unica posizione nella cache in cui è permesso andare. Qualsiasi cosa ci fosse prima viene scartata.
- Utilizzato meno frequentemente (LFU): LFU conta la frequenza con cui un articolo è necessario. Quelli che vengono usati meno spesso vengono scartati per primi.
- Adaptive Replacement Cache (ARC): bilancia costantemente tra LRU e LFU, per migliorare il risultato combinato.
- Algoritmo di caching multi-coda (MQ): (di Y. Zhou J.F. Philbin e Kai Li).
Altre cose da considerare:
- Articoli con costi diversi: conservare gli articoli che sono costosi da ottenere, ad esempio quelli che richiedono molto tempo per essere acquistati.
- Gli elementi che occupano più cache: Se gli articoli hanno dimensioni diverse, la cache potrebbe voler scartare un articolo grande per memorizzarne diversi più piccoli.
- Articoli che scadono con il tempo: Alcune cache conservano informazioni che scadono con il tempo (ad es. una cache delle notizie, una cache DNS o una cache del browser web). Il computer può scartare gli elementi perché sono scaduti. A seconda delle dimensioni della cache non è necessario un ulteriore algoritmo di caching per eliminare gli elementi.
Esistono anche vari algoritmi per mantenere la coerenza della cache. Ciò vale solo in situazioni 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).
Quali posizioni di memoria possono essere memorizzate in cache da quali posizioni di cache
Domande e risposte
D: Che cos'è un algoritmo di cache?
R: Un algoritmo di cache è un algoritmo utilizzato per gestire una cache o un gruppo di dati. Decide quale elemento deve essere eliminato dalla cache quando è piena.
D: Che cos'è il tasso di successo?
R: Il tasso di risposta descrive la frequenza con cui una richiesta può essere servita dalla cache.
D: Cosa descrive la latenza?
R: La latenza descrive per quanto tempo un elemento nella cache può essere ottenuto.
D: Che cos'è l'algoritmo ottimale di Belady?
R: L'algoritmo ottimale di Belady, noto anche come algoritmo chiaroveggente, è un algoritmo di caching efficiente che scarta sempre le informazioni che non saranno necessarie per un periodo di tempo più lungo nel futuro. Questo risultato non può essere generalmente implementato nella pratica, perché richiede la previsione di ciò che sarà necessario nel futuro.
D: Come funziona il sistema Least Recently Used (LRU)?
R: LRU elimina per primi gli elementi utilizzati meno di recente e richiede di tenere traccia di ciò che è stato utilizzato quando, utilizzando i "bit di età" per ogni linea di cache e tracciando quale è stata utilizzata meno di recente in base ai bit di età. Ogni volta che una linea di cache viene utilizzata, l'età di tutte le altre linee di cache viene modificata di conseguenza.
D: Come funziona la funzione Most Recently Used (MRU)?
R: MRU elimina per primi gli elementi utilizzati più di recente e questo meccanismo di cache è comunemente utilizzato per le cache di memoria dei database.
D: Quali altri algoritmi esistono per mantenere la coerenza della cache?
R; Esistono vari algoritmi per mantenere la coerenza della cache quando vengono utilizzate più cache indipendenti per i dati condivisi, come ad esempio l'aggiornamento da parte di più server di database di un unico file di dati condiviso.
