Cos'è la cache LRU?

Gli algoritmi di sostituzione della cache sono progettati in modo efficiente per sostituire la cache quando lo spazio è pieno. IL Usato meno di recente (LRU) è uno di quegli algoritmi. Come suggerisce il nome, quando la memoria cache è piena, LRU seleziona i dati utilizzati meno di recente e li rimuove per fare spazio ai nuovi dati. La priorità dei dati nella cache cambia in base alla necessità di tali dati, ovvero se alcuni dati vengono recuperati o aggiornati di recente, la priorità di tali dati verrebbe modificata e assegnata alla priorità più alta, mentre la priorità dei dati diminuisce se rimane inutilizzato operazioni dopo operazioni.

Tabella dei contenuti

• Cos'è la cache LRU?
• Operazioni sulla cache LRU:
• Funzionamento della cache LRU:
• Modi per implementare la cache LRU:
• Implementazione della cache LRU utilizzando Queue e Hashing:
• Implementazione della cache LRU utilizzando Doubly Linked List e Hashing:
• Implementazione della cache LRU utilizzando Deque e Hashmap:
• Implementazione della cache LRU utilizzando Stack e Hashmap:
• Cache LRU che utilizza l'implementazione del contatore:
• Implementazione della cache LRU utilizzando Aggiornamenti Lazy:
• Analisi della complessità della cache LRU:
• Vantaggi della cache LRU:
• Svantaggi della cache LRU:
• Applicazione nel mondo reale della cache LRU:

LRU L'algoritmo è un problema standard e può presentare variazioni in base alle necessità, ad esempio nei sistemi operativi LRU gioca un ruolo cruciale in quanto può essere utilizzato come algoritmo di sostituzione della pagina per ridurre al minimo gli errori di pagina.

Operazioni sulla cache LRU:

• LRUCache (Capacità c): Inizializza la cache LRU con capacità di dimensione positiva C.
• ottenere (chiave) : Restituisce il valore di Chiave ' K' se è presente nella cache altrimenti restituisce -1. Aggiorna anche la priorità dei dati nella cache LRU.
• put (chiave, valore): Aggiorna il valore della chiave se esiste, altrimenti aggiungi la coppia chiave-valore alla cache. Se il numero di chiavi supera la capacità della cache LRU, eliminare la chiave utilizzata meno di recente.

Funzionamento della cache LRU:

Supponiamo di avere una cache LRU di capacità 3 e di voler eseguire le seguenti operazioni:

1. Inserisci (chiave=1, valore=A) nella cache
2. Inserisci (chiave=2, valore=B) nella cache
3. Inserisci (chiave=3, valore=C) nella cache
4. Ottieni (chiave=2) dalla cache
5. Ottieni (chiave=4) dalla cache
6. Inserisci (chiave=4, valore=D) nella cache
7. Inserisci (chiave=3, valore=E) nella cache
8. Ottieni (chiave=4) dalla cache
9. Inserisci (chiave=1, valore=A) nella cache

Le operazioni di cui sopra vengono eseguite una dopo l'altra come mostrato nell'immagine seguente:

Spiegazione dettagliata di ciascuna operazione:

1. Put (chiave 1, valore A) : Poiché la cache LRU ha una capacità vuota=3, non è necessaria alcuna sostituzione e inseriamo {1: A} in alto, ovvero {1: A} ha la massima priorità.
2. Put (chiave 2, valore B) : Poiché la cache LRU ha una capacità vuota=2, anche in questo caso non è necessaria alcuna sostituzione, ma ora {2: B} ha la priorità più alta e la priorità di {1: A} diminuisce.
3. Put (chiave 3, valore C) : C'è ancora 1 spazio vuoto libero nella cache, quindi inserisci {3: C} senza alcuna sostituzione, nota ora che la cache è piena e l'attuale ordine di priorità dal più alto al più basso è {3:C}, {2:B }, {1:A}.
4. Ottieni (tasto 2) : Ora, restituisci il valore di key=2 durante questa operazione, inoltre poiché viene utilizzata key=2, ora il nuovo ordine di priorità è {2:B}, {3:C}, {1:A}
5. Ottieni (tasto 4): Osserva che la chiave 4 non è presente nella cache, restituiamo '-1' per questa operazione.
6. Put (chiave 4, valore D) : Osserva che la cache è PIENA, ora utilizza l'algoritmo LRU per determinare quale chiave è stata utilizzata meno recentemente. Poiché {1:A} ha la priorità minore, rimuovi {1:A} dalla nostra cache e inserisci {4:D} nella cache. Tieni presente che il nuovo ordine di priorità è {4:D}, {2:B}, {3:C}
7. Put (chiave 3, valore E) : Poiché key=3 era già presente nella cache con valore=C, questa operazione non comporterà la rimozione di alcuna chiave, piuttosto aggiornerà il valore di key=3 in ' E' . Ora il nuovo ordine di priorità diventerà {3:E}, {4:D}, {2:B}
8. Ottieni (tasto 4) : Restituisce il valore di chiave=4. Ora la nuova priorità diventerà {4:D}, {3:E}, {2:B}
9. Put (chiave 1, valore A) : Poiché la nostra cache è PIENA, utilizza il nostro algoritmo LRU per determinare quale chiave è stata utilizzata meno recentemente e poiché {2:B} ha la priorità minore, rimuovi {2:B} dalla nostra cache e inserisci {1:A} nella cache. Ora il nuovo ordine di priorità è {1:A}, {4:D}, {3:E}

Modi per implementare la cache LRU:

La cache LRU può essere implementata in vari modi e ogni programmatore può scegliere un approccio diverso. Tuttavia, di seguito sono riportati gli approcci comunemente utilizzati:

1. LRU utilizzando coda e hashing
2. LRU utilizzando Elenco doppiamente collegato + Hashing
3. LRU utilizzando Deque
4. LRU utilizzando Stack
5. LRU utilizzando Controimplementazione
6. LRU utilizzando Aggiornamenti lenti

Implementazione della cache LRU utilizzando Queue e Hashing:

Utilizziamo due strutture dati per implementare una cache LRU.

1. Coda viene implementato utilizzando un elenco doppiamente collegato. La dimensione massima della coda sarà pari al numero totale di frame disponibili (dimensione della cache). Le pagine utilizzate più di recente si troveranno nella parte anteriore e le pagine utilizzate meno di recente si troveranno nella parte posteriore.
2. Un hash con il numero di pagina come chiave e l'indirizzo del nodo della coda corrispondente come valore.

Quando si fa riferimento a una pagina, la pagina richiesta potrebbe essere in memoria. Se è in memoria, dobbiamo staccare il nodo della lista e portarlo in testa alla coda.
Se la pagina richiesta non è in memoria, la riportiamo in memoria. In parole semplici, aggiungiamo un nuovo nodo all'inizio della coda e aggiorniamo l'indirizzo del nodo corrispondente nell'hash. Se la coda è piena, cioè tutti i frame sono pieni, rimuoviamo un nodo dalla parte posteriore della coda e aggiungiamo il nuovo nodo all'inizio della coda.

Illustrazione:

Consideriamo le operazioni, Si riferisce chiave X con nella cache LRU: { 1, 2, 3, 4, 1, 2, 5, 1, 2, 3 }
Nota: Inizialmente non è presente alcuna pagina in memoria.

Le immagini sottostanti mostrano l'esecuzione passo passo delle operazioni di cui sopra sulla cache LRU.

Algoritmo:

• Crea una classe LRUCache con la dichiarazione di un elenco di tipo int, una mappa di tipo non ordinata e una variabile per memorizzare la dimensione massima della cache
• Nella funzione di riferimento di LRUCache
  • Se questo valore non è presente nella coda, inserisci questo valore davanti alla coda e rimuovi l'ultimo valore se la coda è piena
  • Se il valore è già presente, rimuovilo dalla coda e inseriscilo in primo piano
• Nella funzione di visualizzazione stampa, LRUCache utilizza la coda a partire dalla parte anteriore

Di seguito è riportata l’implementazione dell’approccio di cui sopra:

C++

>

>

C

>

>

Giava

>

>

Python3

>

>

C#

>

>

Javascript

>

>

Implementazione della cache LRU utilizzando Doubly Linked List e Hashing :

L'idea è molto semplice, ovvero continuare a inserire gli elementi in testa.

• se l'elemento non è presente nella lista allora aggiungetelo in testa alla lista
• se l'elemento è presente nell'elenco, sposta l'elemento in testa e sposta l'elemento rimanente dell'elenco

Si noti che la priorità del nodo dipenderà dalla distanza di quel nodo dalla testa, più il nodo è vicino alla testa, maggiore è la priorità che ha. Quindi, quando la dimensione della cache è piena e dobbiamo rimuovere qualche elemento, rimuoviamo l'elemento adiacente alla coda della lista doppiamente collegata.

Implementazione della cache LRU utilizzando Deque e Hashmap:

La struttura dei dati di deque consente l'inserimento e l'eliminazione sia dal front che dall'end, questa proprietà consente l'implementazione di LRU possibile poiché l'elemento Front può rappresentare un elemento ad alta priorità mentre l'elemento end può essere l'elemento a bassa priorità, ovvero quello utilizzato meno di recente.

Lavorando:

1. Ottieni l'operazione : controlla se la chiave esiste nella mappa hash della cache e segue i casi seguenti sulla deque:
   • Se la chiave viene trovata:
     • L'articolo è considerato utilizzato di recente, quindi viene spostato in primo piano nella deque.
     • Il valore associato alla chiave viene restituito come risultato dell'operazioneget>operazione.
   • Se la chiave non viene trovata:
     • restituisce -1 per indicare che tale chiave non è presente.
2. Operazione Put: Per prima cosa controlla se la chiave esiste già nella mappa hash della cache e segui i casi seguenti sulla deque
   • Se la chiave esiste:
     • Il valore associato alla chiave viene aggiornato.
     • L'elemento viene spostato in primo piano nella deque poiché ora è l'ultimo utilizzato.
   • Se la chiave non esiste:
     • Se la cache è piena, significa che è necessario inserire un nuovo elemento e eliminare l'elemento utilizzato meno di recente. Questo viene fatto rimuovendo l'elemento dalla fine della deque e la voce corrispondente dalla mappa hash.
     • La nuova coppia chiave-valore viene quindi inserita sia nella mappa hash che nella parte anteriore della deque per indicare che si tratta dell'elemento utilizzato più di recente

Implementazione della cache LRU utilizzando Stack e Hashmap:

L'implementazione di una cache LRU (Least Recently Used) utilizzando una struttura dati stack e l'hashing può essere un po' complicata perché uno stack semplice non fornisce un accesso efficiente all'elemento utilizzato meno di recente. Tuttavia, puoi combinare uno stack con una mappa hash per raggiungere questo obiettivo in modo efficiente. Ecco un approccio di alto livello per implementarlo:

1. Utilizza una mappa hash : La mappa hash memorizzerà le coppie chiave-valore della cache. Le chiavi verranno mappate ai nodi corrispondenti nello stack.
2. Usa una pila : Lo stack manterrà l'ordine delle chiavi in ​​base al loro utilizzo. L'elemento utilizzato meno di recente si troverà in fondo alla pila, mentre l'elemento utilizzato più di recente sarà in cima

Questo approccio non è così efficiente e quindi non viene utilizzato spesso.

Cache LRU che utilizza l'implementazione del contatore:

Ogni blocco nella cache avrà il proprio contatore LRU a cui appartiene il valore del contatore da {0 a n-1} , Qui ' N ‘ rappresenta la dimensione della cache. Il blocco modificato durante la sostituzione del blocco diventa il blocco MRU e, di conseguenza, il suo valore del contatore viene modificato in n – 1. I valori del contatore maggiori del valore del contatore del blocco a cui si accede vengono diminuiti di uno. I restanti blocchi rimangono inalterati.

Implementazione della cache LRU utilizzando Aggiornamenti Lazy:

L'implementazione di una cache LRU (Least Recently Used) utilizzando aggiornamenti lazy è una tecnica comune per migliorare l'efficienza delle operazioni della cache. Gli aggiornamenti lenti implicano il monitoraggio dell'ordine in cui si accede agli elementi senza aggiornare immediatamente l'intera struttura dei dati. Quando si verifica un errore nella cache, puoi decidere se eseguire o meno un aggiornamento completo in base ad alcuni criteri.

Analisi della complessità della cache LRU:

• Complessità temporale:
  • Operazione Put(): O(1), ovvero il tempo richiesto per inserire o aggiornare una nuova coppia chiave-valore è costante
  • Operazione Get(): O(1), ovvero il tempo necessario per ottenere il valore di una chiave è costante
• Spazio ausiliario: O(N) dove N è la capacità della Cache.

Vantaggi della cache LRU:

• Accesso veloce : È necessario un tempo O(1) per accedere ai dati dalla cache LRU.
• Aggiornamento veloce : è necessario un tempo O(1) per aggiornare una coppia chiave-valore nella cache LRU.
• Rimozione rapida dei dati utilizzati meno di recente : Occorre O(1) eliminare ciò che non è stato utilizzato di recente.
• Nessuna frustata: LRU è meno suscettibile al thrashing rispetto a FIFO perché considera la cronologia di utilizzo delle pagine. È in grado di rilevare quali pagine vengono utilizzate frequentemente e dare loro la priorità per l'allocazione della memoria, riducendo il numero di errori di pagina e di operazioni di I/O del disco.

Svantaggi della cache LRU:

• Richiede una cache di grandi dimensioni per aumentare l'efficienza.
• Richiede l'implementazione di una struttura dati aggiuntiva.
• L'assistenza hardware è elevata.
• In LRU il rilevamento degli errori è difficile rispetto ad altri algoritmi.
• Ha un'accettabilità limitata.

Applicazione nel mondo reale della cache LRU:

• Nei sistemi di database per risultati rapidi delle query.
• Nei sistemi operativi per ridurre al minimo gli errori di pagina.
• Editor di testo e IDE per archiviare file o frammenti di codice utilizzati di frequente
• I router e gli switch di rete utilizzano LRU per aumentare l'efficienza della rete di computer
• Nelle ottimizzazioni del compilatore
• Strumenti di previsione del testo e di completamento automatico