Què és la memòria cau LRU?

Els algorismes de substitució de la memòria cau estan dissenyats de manera eficient per substituir la memòria cau quan l'espai està ple. El S'ha utilitzat menys recentment (LRU) és un d'aquests algorismes. Com el seu nom indica quan la memòria cau està plena, LRU tria les dades que s'han utilitzat menys recentment i les elimina per fer espai per a les dades noves. La prioritat de les dades a la memòria cau canvia segons la necessitat d'aquestes dades, és a dir, si algunes dades s'obtenen o s'actualitzen recentment, la prioritat d'aquestes dades es canviarà i s'assignaria a la prioritat més alta, i la prioritat de les dades disminueix si resta operacions sense utilitzar després de les operacions.

Taula de contingut

• Què és la memòria cau LRU?
• Operacions a la memòria cau LRU:
• Funcionament de la memòria cau LRU:
• Formes d'implementar la memòria cau LRU:
• Implementació de la memòria cau LRU mitjançant Queue and Hashing:
• Implementació de la memòria cau LRU mitjançant la llista doblement enllaçada i el hashing:
• Implementació de la memòria cau LRU mitjançant Deque & Hashmap:
• Implementació de la memòria cau LRU mitjançant Stack & Hashmap:
• La memòria cau LRU utilitzant la implementació del comptador:
• Implementació de la memòria cau LRU mitjançant Lazy Updates:
• Anàlisi de complexitat de la memòria cau LRU:
• Avantatges de la memòria cau LRU:
• Desavantatges de la memòria cau LRU:
• Aplicació del món real de la memòria cau LRU:

LRU L'algorisme és un problema estàndard i pot tenir variacions segons les necessitats, per exemple, en els sistemes operatius LRU té un paper crucial, ja que es pot utilitzar com a algorisme de substitució de pàgines per tal de minimitzar els errors de la pàgina.

Operacions a la memòria cau LRU:

• LRUCache (capacitat c): Inicialitzeu la memòria cau LRU amb capacitat de mida positiva c.
• obtenir (clau) : retorna el valor de la clau ' k' si està present a la memòria cau en cas contrari retorna -1. També actualitza la prioritat de les dades a la memòria cau LRU.
• posar (clau, valor): Actualitzeu el valor de la clau si aquesta existeix. En cas contrari, afegiu el parell clau-valor a la memòria cau. Si el nombre de claus supera la capacitat de la memòria cau LRU, descarta la clau utilitzada menys recentment.

Funcionament de la memòria cau LRU:

Suposem que tenim una memòria cau LRU de capacitat 3 i que ens agradaria realitzar les operacions següents:

1. Posa (clau=1, valor=A) a la memòria cau
2. Posa (clau=2, valor=B) a la memòria cau
3. Posa (clau=3, valor=C) a la memòria cau
4. Obteniu (clau=2) de la memòria cau
5. Obteniu (clau=4) de la memòria cau
6. Posa (clau=4, valor=D) a la memòria cau
7. Posa (clau=3, valor=E) a la memòria cau
8. Obteniu (clau=4) de la memòria cau
9. Posa (clau=1, valor=A) a la memòria cau

Les operacions anteriors es realitzen una darrere l'altra, tal com es mostra a la imatge següent:

Explicació detallada de cada operació:

1. Posa (clau 1, valor A) : Com que la memòria cau LRU té capacitat buida = 3, no cal cap substitució i posem {1 : A} a la part superior, és a dir, {1 : A} té la prioritat més alta.
2. Posa (clau 2, valor B) : Com que la memòria cau LRU té capacitat buida=2, de nou no cal cap substitució, però ara {2 : B} té la prioritat més alta i la prioritat de {1 : A} disminueix.
3. Posa (clau 3, valor C) : Encara hi ha 1 espai buit a la memòria cau, per tant, poseu {3 : C} sense cap substitució, observeu que ara la memòria cau està plena i l'ordre actual de prioritat de més alt a més baix és {3:C}, {2:B }, {1:A}.
4. Obtenir (clau 2) : Ara, retorneu el valor de clau=2 durant aquesta operació, també com que s'utilitza clau=2, ara el nou ordre de prioritat és {2:B}, {3:C}, {1:A}
5. Obteniu (clau 4): Observeu que la clau 4 no està present a la memòria cau, retornem '-1' per a aquesta operació.
6. Posa (clau 4, valor D) : Observeu que la memòria cau és COMPLETA, ara feu servir l'algorisme LRU per determinar quina clau s'ha utilitzat menys recentment. Com que {1:A} tenia la menor prioritat, elimineu {1:A} de la nostra memòria cau i poseu-hi {4:D}. Tingueu en compte que el nou ordre de prioritat és {4:D}, {2:B}, {3:C}
7. Posa (clau 3, valor E) : Com que key=3 ja estava present a la memòria cau amb valor=C, per tant, aquesta operació no donarà lloc a l'eliminació de cap clau, sinó que actualitzarà el valor de key=3 a ' I' . Ara, el nou ordre de prioritat es convertirà en {3:E}, {4:D}, {2:B}
8. Obtenir (clau 4) : retorna el valor de key=4. Ara, la nova prioritat es convertirà en {4:D}, {3:E}, {2:B}
9. Posa (clau 1, valor A) : Com que la nostra memòria cau és COMPLETA, utilitzeu el nostre algorisme LRU per determinar quina clau s'ha utilitzat menys recentment, i com que {2:B} tenia la menor prioritat, elimineu {2:B} de la nostra memòria cau i introduïu {1:A} a la memòria cau. Ara, el nou ordre de prioritat és {1:A}, {4:D}, {3:E}

Formes d'implementar la memòria cau LRU:

La memòria cau LRU es pot implementar de diverses maneres i cada programador pot triar un enfocament diferent. Tanmateix, a continuació es mostren els enfocaments d'ús habitual:

1. LRU utilitzant cua i hashing
2. LRU utilitzant Llista doblement enllaçada + hashing
3. LRU utilitzant Deque
4. LRU utilitzant Stack
5. LRU utilitzant Implementació del comptador
6. LRU utilitzant Lazy Updates

Implementació de la memòria cau LRU mitjançant Queue and Hashing:

Utilitzem dues estructures de dades per implementar una memòria cau LRU.

1. Cua s'implementa mitjançant una llista doblement enllaçada. La mida màxima de la cua serà igual al nombre total de fotogrames disponibles (mida de la memòria cau). Les pàgines utilitzades més recentment estaran prop de la part frontal i les pàgines menys utilitzades estaran prop de la part posterior.
2. Un Hash amb el número de pàgina com a clau i l'adreça del node de cua corresponent com a valor.

Quan es fa referència a una pàgina, és possible que la pàgina requerida estigui a la memòria. Si està a la memòria, hem de desconnectar el node de la llista i portar-lo al capdavant de la cua.
Si la pàgina requerida no està a la memòria, la portem a la memòria. En paraules senzilles, afegim un nou node al capdavant de la cua i actualitzem l'adreça del node corresponent al hash. Si la cua està plena, és a dir, tots els fotogrames estan plens, eliminem un node de la part posterior de la cua i afegim el nou node al davant de la cua.

Il·lustració:

Considerem les operacions, Es refereix clau x amb a la memòria cau de LRU: { 1, 2, 3, 4, 1, 2, 5, 1, 2, 3 }
Nota: Inicialment no hi ha cap pàgina a la memòria.

Les imatges següents mostren l'execució pas a pas de les operacions anteriors a la memòria cau LRU.

Algorisme:

• Creeu una classe LRUCache amb declarar una llista de tipus int, un mapa de tipus no ordenat , i una variable per emmagatzemar la mida màxima de la memòria cau
• A la funció de referència de LRUCache
  • Si aquest valor no està present a la cua, premeu aquest valor davant de la cua i elimineu l'últim valor si la cua està plena
  • Si el valor ja està present, elimineu-lo de la cua i premeu-lo al davant de la cua
• A la funció de visualització d'impressió, el LRUCache utilitza la cua començant per la part frontal

A continuació es mostra la implementació de l'enfocament anterior:

C++

C

// A C program to show implementation of LRU cache> #include> #include> > // A Queue Node (Queue is implemented using Doubly Linked> // List)> typedef> struct> QNode {> > struct> QNode *prev, *next;> > unsigned> > pageNumber;> // the page number stored in this QNode> } QNode;> > // A Queue (A FIFO collection of Queue Nodes)> typedef> struct> Queue {> > unsigned count;> // Number of filled frames> > unsigned numberOfFrames;> // total number of frames> > QNode *front, *rear;> } Queue;> > // A hash (Collection of pointers to Queue Nodes)> typedef> struct> Hash {> > int> capacity;> // how many pages can be there> > QNode** array;> // an array of queue nodes> } Hash;> > // A utility function to create a new Queue Node. The queue> // Node will store the given 'pageNumber'> QNode* newQNode(unsigned pageNumber)> {> > // Allocate memory and assign 'pageNumber'> > QNode* temp = (QNode*)> malloc> (> sizeof> (QNode));> > temp->pageNumber = pageNumber;>>> > return> temp;> }> > // A utility function to create an empty Queue.> // The queue can have at most 'numberOfFrames' nodes> Queue* createQueue(> int> numberOfFrames)> {> > Queue* queue = (Queue*)> malloc> (> sizeof> (Queue));> > > // The queue is empty> > queue->recompte = 0;>>> > // Number of frames that can be stored in memory> > queue->numberOfFrames = nombreOfFrames;>>> > // Create an array of pointers for referring queue nodes> > hash->matriu>>> (QNode*));> > > // Initialize all hash entries as empty> > int> i;> > for> (i = 0; i capacity; ++i)> > hash->matriu[i] = NULL;>>> > // A utility function to check if queue is empty> int> isQueueEmpty(Queue* queue)> {> > return> queue->posterior == NULL;>>> queue->davant = NULL;>>> queue->posterior = cua->darrera->anterior;>>> queue->darrere->següent = NULL;>>> > // A function to add a page with given 'pageNumber' to both> // queue and hash> void> Enqueue(Queue* queue, Hash* hash, unsigned pageNumber)> {> > // If all frames are full, remove the page at the rear> > if> (AreAllFramesFull(queue)) {> > // remove page from hash> > hash->array[queue->rear->pageNumber] = NULL;>>> > // If queue is empty, change both front and rear> > // pointers> > if> (isQueueEmpty(queue))> > queue->posterior = cua->front = temp;>>> queue->davant = temp;>>> > // increment number of full frames> > queue->comptar++;>>> // are two cases:> // 1. Frame is not there in memory, we bring it in memory> // and add to the front of queue> // 2. Frame is there in memory, we move the frame to front> // of queue> void> ReferencePage(Queue* queue, Hash* hash,> > unsigned pageNumber)> {> > QNode* reqPage = hash->matriu[número de pàgina];>>> // Unlink rquested page from its current location> > // in queue.> > reqPage->prev->next = reqPage->next;>>> reqPage->següent->anterior = reqPage->anterior;>>> queue->darrere->següent = NULL;>>> reqPage->anterior = NULL;>>> > // Change front to the requested page> > queue->front = reqPage;>>> , q->portada->número de pàgina);>>> , q->front->next->pageNumber);>>> , q->front->next->next->pageNumber);>>> , q->front->next->next->next->pageNumber);>>> Java /* We can use Java inbuilt Deque as a double> > ended queue to store the cache keys, with> > the descending time of reference from front> > to back and a set container to check presence> > of a key. But remove a key from the Deque using> > remove(), it takes O(N) time. This can be> > optimized by storing a reference (iterator) to> > each key in a hash map. */> import> java.util.Deque;> import> java.util.HashSet;> import> java.util.Iterator;> import> java.util.LinkedList;> > public> class> LRUCache {> > > // store keys of cache> > private> Deque doublyQueue;> > > // store references of key in cache> > private> HashSet hashSet;> > > // maximum capacity of cache> > private> final> int> CACHE_SIZE;> > > LRUCache(> int> capacity)> > {> > doublyQueue => new> LinkedList();> > hashSet => new> HashSet();> > CACHE_SIZE = capacity;> > }> > > /* Refer the page within the LRU cache */> > public> void> refer(> int> page)> > {> > if> (!hashSet.contains(page)) {> > if> (doublyQueue.size() == CACHE_SIZE) {> > int> last = doublyQueue.removeLast();> > hashSet.remove(last);> > }> > }> > else> {> /* The found page may not be always the last> > element, even if it's an intermediate> > element that needs to be removed and added> > to the start of the Queue */> > doublyQueue.remove(page);> > }> > doublyQueue.push(page);> > hashSet.add(page);> > }> > > // display contents of cache> > public> void> display()> > {> > Iterator itr = doublyQueue.iterator();> > while> (itr.hasNext()) {> > System.out.print(itr.next() +> ' '> );> > }> > }> > > // Driver code> > public> static> void> main(String[] args)> > {> > LRUCache cache => new> LRUCache(> 4> );> > cache.refer(> 1> );> > cache.refer(> 2> );> > cache.refer(> 3> );> > cache.refer(> 1> );> > cache.refer(> 4> );> > cache.refer(> 5> );> > cache.display();> > }> }> // This code is contributed by Niraj Kumar> Python 3 # We can use stl container list as a double> # ended queue to store the cache keys, with> # the descending time of reference from front> # to back and a set container to check presence> # of a key. But to fetch the address of the key> # in the list using find(), it takes O(N) time.> # This can be optimized by storing a reference> # (iterator) to each key in a hash map.> class> LRUCache:> > # store keys of cache> > def> __init__(> self> , n):> > self> .csize> => n> > self> .dq> => []> > self> .ma> => {}> > > > # Refers key x with in the LRU cache> > def> refer(> self> , x):> > > # not present in cache> > if> x> not> in> self> .ma.keys():> > # cache is full> > if> len> (> self> .dq)> => => self> .csize:> > # delete least recently used element> > last> => self> .dq[> -> 1> ]> > > # Pops the last element> > ele> => self> .dq.pop();> > > # Erase the last> > del> self> .ma[last]> > > # present in cache> > else> :> > del> self> .dq[> self> .ma[x]]> > > # update reference> > self> .dq.insert(> 0> , x)> > self> .ma[x]> => 0> ;> > > # Function to display contents of cache> > def> display(> self> ):> > > # Iterate in the deque and print> > # all the elements in it> > print> (> self> .dq)> > # Driver Code> ca> => LRUCache(> 4> )> > ca.refer(> 1> )> ca.refer(> 2> )> ca.refer(> 3> )> ca.refer(> 1> )> ca.refer(> 4> )> ca.refer(> 5> )> ca.display()> # This code is contributed by Satish Srinivas> C# // C# program to implement the approach> > using> System;> using> System.Collections.Generic;> > class> LRUCache {> > // store keys of cache> > private> List <> int> >doublelyQueue;>>> > // maximum capacity of cache> > private> int> CACHE_SIZE;> > > public> LRUCache(> int> capacity)> > {> > doublyQueue => new> List <> int> >();> > hashSet => new> HashSet <> int> >();> > CACHE_SIZE = capacity;> > }> > > /* Refer the page within the LRU cache */> > public> void> Refer(> int> page)> > {> > if> (!hashSet.Contains(page)) {> > if> (doublyQueue.Count == CACHE_SIZE) {> > int> last> > = doublyQueue[doublyQueue.Count - 1];> > doublyQueue.RemoveAt(doublyQueue.Count - 1);> > hashSet.Remove(last);> > }> > }> > else> {> > /* The found page may not be always the last> > element, even if it's an intermediate> > element that needs to be removed and added> > to the start of the Queue */> > doublyQueue.Remove(page);> > }> > doublyQueue.Insert(0, page);> > hashSet.Add(page);> > }> > > // display contents of cache> > public> void> Display()> > {> > foreach> (> int> page> in> doublyQueue)> > {> > Console.Write(page +> ' '> );> > }> > }> > > // Driver code> > static> void> Main(> string> [] args)> > {> > LRUCache cache => new> LRUCache(4);> > cache.Refer(1);> > cache.Refer(2);> > cache.Refer(3);> > cache.Refer(1);> > cache.Refer(4);> > cache.Refer(5);> > cache.Display();> > }> }> > // This code is contributed by phasing17> Javascript // JS code to implement the approach> class LRUCache {> > constructor(n) {> > this> .csize = n;> > this> .dq = [];> > this> .ma => new> Map();> > }> > > refer(x) {> > if> (!> this> .ma.has(x)) {> > if> (> this> .dq.length ===> this> .csize) {> > const last => this> .dq[> this> .dq.length - 1];> > this> .dq.pop();> > this> .ma.> delete> (last);> > }> > }> else> {> > this> .dq.splice(> this> .dq.indexOf(x), 1);> > }> > > this> .dq.unshift(x);> > this> .ma.set(x, 0);> > }> > > display() {> > console.log(> this> .dq);> > }> }> > const cache => new> LRUCache(4);> > cache.refer(1);> cache.refer(2);> cache.refer(3);> cache.refer(1);> cache.refer(4);> cache.refer(5);> cache.display();> > // This code is contributed by phasing17> Implementació de la memòria cau LRU mitjançant la llista doblement enllaçada i el hashing : La idea és molt bàsica, és a dir, seguir inserint els elements al capdavant. si l'element no està present a la llista, afegiu-lo a la capçalera de la llista si l'element està present a la llista, moveu l'element al capçal i desplaceu l'element restant de la llista Tingueu en compte que la prioritat del node dependrà de la distància d'aquest node al cap, com més a prop estigui el node al cap, més alta serà la prioritat que tingui. Així, quan la mida de la memòria cau és plena i hem d'eliminar algun element, eliminem l'element adjacent a la cua de la llista doblement enllaçada. Implementació de la memòria cau LRU mitjançant Deque & Hashmap: L'estructura de dades de Deque permet la inserció i la supressió tant des del davant com del final, aquesta propietat permet la implementació de LRU possible, ja que l'element frontal pot representar un element d'alta prioritat mentre que l'element final pot ser l'element de baixa prioritat, és a dir, menys utilitzat recentment. Treball: Obtenir l'operació : Comprova si la clau existeix al mapa hash de la memòria cau i segueix els casos següents al deque: Si es troba la clau: L'element es considera com a utilitzat recentment, per la qual cosa es trasllada a la part davantera del deque. El valor associat a la clau es retorna com a resultat de l' get> funcionament. Si no es troba la clau: torna -1 per indicar que no hi ha cap clau. Operació de posada: Primer comproveu si la clau ja existeix al mapa hash de la memòria cau i seguiu els casos següents al deque Si existeix la clau: S'actualitza el valor associat a la clau. L'element es mou a la part davantera del deque, ja que ara és el que s'utilitza més recentment. Si la clau no existeix: Si la memòria cau està plena, vol dir que s'ha d'inserir un element nou i s'ha de desallotjar l'element utilitzat menys recentment. Això es fa eliminant l'element del final del deque i l'entrada corresponent del mapa hash. A continuació, la nova parella clau-valor s'insereix tant al mapa hash com a la part davantera del deque per indicar que és l'element utilitzat més recentment Implementació de la memòria cau LRU mitjançant Stack & Hashmap: La implementació d'una memòria cau LRU (Least Recently Used) utilitzant una estructura de dades de pila i hash pot ser una mica complicat perquè una pila senzilla no proporciona un accés eficient a l'element menys utilitzat. Tanmateix, podeu combinar una pila amb un mapa hash per aconseguir-ho de manera eficient. Aquí teniu un enfocament d'alt nivell per implementar-lo: Utilitzeu un mapa hash : El mapa hash emmagatzemarà els parells clau-valor de la memòria cau. Les claus s'assignaran als nodes corresponents de la pila. Utilitzeu una pila : La pila mantindrà l'ordre de les claus en funció del seu ús. L'element utilitzat menys recentment estarà a la part inferior de la pila i l'element utilitzat més recentment estarà a la part superior Aquest enfocament no és tan eficient i, per tant, no s'utilitza sovint. La memòria cau LRU utilitzant la implementació del comptador: Cada bloc de la memòria cau tindrà el seu propi comptador LRU al qual pertany el valor del comptador {0 a n-1} , aquí ' n ' representa la mida de la memòria cau. El bloc que es canvia durant la substitució del bloc es converteix en el bloc MRU i, com a resultat, el seu valor del comptador es canvia a n – 1. Els valors del comptador superiors al valor del comptador del bloc accedit es disminueixen en un. La resta de blocs no es modifiquen. Valor de Conter Prioritat Estat usat 0 baix Utilitzat menys recentment n-1 Alt Usat més recentment Implementació de la memòria cau LRU mitjançant Lazy Updates: La implementació d'una memòria cau LRU (Least Recently Used) utilitzant actualitzacions mandroses és una tècnica habitual per millorar l'eficiència de les operacions de la memòria cau. Les actualitzacions lazy impliquen el seguiment de l'ordre en què s'accedeix als elements sense actualitzar immediatament tota l'estructura de dades. Quan es produeix un error de memòria cau, podeu decidir si voleu o no realitzar una actualització completa segons alguns criteris. Anàlisi de complexitat de la memòria cau LRU: Complexitat temporal: Operació Put(): O(1), és a dir, el temps necessari per inserir o actualitzar el nou parell clau-valor és constant Operació Get(): O(1), és a dir, el temps necessari per obtenir el valor d'una clau és constant Espai auxiliar: O(N) on N és la capacitat de la memòria cau. Avantatges de la memòria cau LRU: Accés ràpid : triga O(1) temps a accedir a les dades de la memòria cau de LRU. Actualització ràpida : Es necessita temps O(1) per actualitzar un parell clau-valor a la memòria cau LRU. Eliminació ràpida de les dades utilitzades menys recentment : Cal que O(1) suprimi allò que no s'ha utilitzat recentment. Sense golejades: LRU és menys susceptible a la derrota en comparació amb FIFO perquè té en compte l'historial d'ús de les pàgines. Pot detectar quines pàgines s'utilitzen amb freqüència i prioritzar-les per a l'assignació de memòria, reduint el nombre d'errors de pàgina i les operacions d'E/S del disc. Desavantatges de la memòria cau LRU: Requereix una gran mida de memòria cau per augmentar l'eficiència. Requereix una estructura de dades addicional per implementar-se. L'assistència de maquinari és alta. En LRU, la detecció d'errors és difícil en comparació amb altres algorismes. Té una acceptabilitat limitada. Aplicació del món real de la memòria cau LRU: A sistemes de bases de dades per obtenir resultats ràpids de consultes. En sistemes operatius per minimitzar errors de pàgina. Editors de text i IDE per emmagatzemar fitxers o fragments de codi d'ús freqüent Els encaminadors i commutadors de xarxa utilitzen LRU per augmentar l'eficiència de la xarxa d'ordinadors En optimitzacions del compilador Eines de predicció de text i d'autocompleció Comparteix Twitter Facebook LinkedIn Potser T'Agradarà Full de trucs de la màscara de subxarxa Nombres naturals | Definició, exemples i propietats Articles Més Populars Realment hauríeu d'estudiar a l'estranger a l'escola secundària? Interpolació de cadenes de Python He d'estudiar una d'aquestes titulacions universitàries més ben pagades? Com solucionar l'error del mòdul no trobat? 7 millors llocs per a allotjament web gratuït Què és Internet? Tutorial de Salesforce Spring Boot: personalitza la pàgina d'error de l'etiqueta blanca Stack Permutations Comandament de línia Categoria Bloc Conversió De Java Matemàtiques Col·leccions Java Diferències Cadena De Java Articles D'Interès Cercles Radi del cercle Diferències Diferència entre hotels i restaurants Tutorial D'arrencada De Primavera Baixeu i instal·leu STS IDE Bloc Avantatges i desavantatges dels parlants Tutorial Css Com subratllar el text en CSS? Xarxa D'ordinadors OSI vs TCP/IP