Polítiques de substitució de la memòria cau

En informàtica, les polítiques de substitució de memòria cau (també anomenades freqüentment algorismes de substitució de memòria cau o algorismes de memòria cau) són instruccions d'optimització o algorismes que un programa informàtic o una estructura mantinguda per maquinari pot utilitzar per gestionar una memòria cau d'informació emmagatzemada a l'ordinador. L'emmagatzematge en memòria cau millora el rendiment mantenint els elements de dades recents o utilitzats sovint en ubicacions de memòria que són més ràpides o computacionalment més barates d'accedir que els magatzems de memòria normals. Quan la memòria cau està plena, l'algoritme ha de triar quins elements descartar per deixar espai als nous.^[1]

Visió general

El temps mitjà de referència de memòria és

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

on

m = proporció d'errors = 1 - (ràtio d'èxits)

Tm = temps per fer un accés a la memòria principal quan hi ha un error (o, amb la memòria cau multinivell, el temps mitjà de referència de la memòria per a la memòria cau següent inferior)

Th = la latència: el temps per fer referència a la memòria cau (ha de ser el mateix per a encerts i errors)

E = diversos efectes secundaris, com ara efectes de cua en sistemes multiprocessador

Hi ha dues figures principals de mèrit d'una memòria cau: la latència i la proporció d'èxits. També hi ha una sèrie de factors secundaris que afecten el rendiment de la memòria cau.

La "ràtio d'èxits" d'una memòria cau descriu la freqüència amb què es troba realment un element cercat a la memòria cau. Les polítiques de substitució més eficients fan un seguiment de més informació d'ús per tal de millorar la taxa d'èxits (per a una mida de memòria cau determinada).

La "latencia" d'una memòria cau descriu quant de temps després de sol·licitar l'element desitjat, la memòria cau pot retornar-lo (quan hi ha un error). Les estratègies de substitució més ràpides solen fer un seguiment de menys informació d'ús (o, en el cas de la memòria cau de mapes directes, sense informació) per reduir el temps necessari per actualitzar aquesta informació.

Cada estratègia de substitució és un compromís entre la taxa d'èxit i la latència.^[2]

Polítiques més destacades

Algorisme de Bélády

L'algorisme d'emmagatzematge a la memòria cau més eficient seria descartar sempre la informació que no serà necessària durant més temps en el futur. Aquest resultat òptim es coneix com l'algorisme òptim de Bélády /política de substitució simplement òptima o l'algorisme clarivident. Com que generalment és impossible predir fins a quin punt es necessitarà la informació en el futur, això generalment no es pot implementar a la pràctica. El mínim pràctic només es pot calcular després de l'experimentació, i es pot comparar l'efectivitat de l'algorisme de memòria cau escollit realment.

En el moment en què es produeix un error de pàgina, un conjunt de pàgines es troba a la memòria. A l'exemple, la seqüència de '5', '0', '1' s'accedeix al Frame 1, Frame 2, Frame 3 respectivament. Aleshores, quan s'accedeix a "2", substitueix el valor "5", que es troba al fotograma 1, ja que prediu que el valor "5" no s'accedirà en un futur proper. Com que un sistema operatiu de propòsit general de la vida real no pot predir quan s'accedirà a '5', l'algoritme de Bélády no es pot implementar en aquest sistema.

Substitució aleatòria (RR)

Selecciona aleatòriament un element candidat i el descarta per fer espai quan cal. Aquest algorisme no requereix conservar cap informació sobre l'historial d'accés. Per la seva senzillesa, s'ha utilitzat en processadors ARM. Admet simulació estocàstica eficient.

Polítiques simples basades en cues

Primer en entrar, primer en sortir (FIFO)

Utilitzant aquest algorisme, la memòria cau es comporta de la mateixa manera que una cua FIFO. La memòria cau desallotja els blocs en l'ordre en què s'han afegit, sense tenir en compte la freqüència o quantes vegades s'hi accedia abans.

Últim en entrar primer sortit (LIFO) o Primer en entrar últim sortit (FILO)

Utilitzant aquest algorisme, la memòria cau es comporta de la mateixa manera que una pila i de manera oposada com una cua FIFO. La memòria cau desallotja el bloc afegit més recentment primer sense tenir en compte la freqüència o quantes vegades s'ha accedit abans.

Polítiques simples basades en l'actualitat

L'ús més recent (LRU)

Descarta primer els elements utilitzats menys recentment. Aquest algorisme requereix fer un seguiment del que s'ha utilitzat quan, cosa que és car si es vol assegurar-se que l'algorisme sempre descarta l'element que s'ha utilitzat menys recentment . Les implementacions generals d'aquesta tècnica requereixen mantenir "bits d'edat" per a les línies de memòria cau i fer un seguiment de la línia de memòria cau "Ús menys recentment" basat en bits d'edat. En aquesta implementació, cada vegada que s'utilitza una línia de memòria cau, l'edat de totes les altres línies de memòria cau canvia. LRU és en realitat una família d'algoritmes de memòria cau amb membres que inclouen 2Q de Theodore Johnson i Dennis Shasha,^[3] i LRU/K de Pat O'Neil, Betty O'Neil i Gerhard Weikum.^[4]

La seqüència d'accés per a l'exemple següent és ABCDED F.

A l'exemple, una vegada que ABCD s'instal·la als blocs amb números de seqüència (increment 1 per cada nou accés) i quan s'accedeix a E, és un error i cal instal·lar-lo en un dels blocs. Segons l'algoritme LRU, com que A té el rang més baix (A(0)), E substituirà A.

En el penúltim pas, s'accedeix a D i, per tant, s'actualitza el número de seqüència.

Finalment, s'accedeix a F ocupant el lloc de B que tenia el rang (B(1)) més baix en aquest moment.

El temps que s'utilitza menys recentment (TLRU)

El Time Aware Least Recently Used (TLRU) ^[5] és una variant de LRU dissenyada per a la situació en què els continguts emmagatzemats a la memòria cau tenen una vida útil vàlida. L'algorisme és adequat en aplicacions de memòria cau de xarxa, com ara xarxes centrades en la informació (ICN), xarxes de lliurament de contingut (CDN) i xarxes distribuïdes en general. TLRU introdueix un nou terme: TTU (Time to Use). TTU és un segell de temps d'un contingut/pàgina que estipula el temps d'usabilitat del contingut en funció de la localitat del contingut i de l'anunci de l'editor de contingut. A causa d'aquesta marca de temps basada en la localitat, TTU proporciona més control a l'administrador local per regular l'emmagatzematge de la xarxa. A l'algorisme TLRU, quan arriba una part de contingut, un node de memòria cau calcula el valor TTU local en funció del valor TTU assignat per l'editor de contingut. El valor TTU local es calcula mitjançant una funció definida localment. Un cop calculat el valor TTU local, la substitució del contingut es realitza en un subconjunt del contingut total emmagatzemat al node de memòria cau. El TLRU garanteix que el contingut de vida menys popular i petit s'ha de substituir pel contingut entrant.

S'utilitza més recentment (MRU)

A diferència de l'ús menys recent (LRU), MRU descarta primer els elements utilitzats més recentment . En les conclusions presentades a la 11a conferència de VLDB, Chou i DeWitt van assenyalar que "Quan un fitxer s'escaneja repetidament en un patró de referència [Looping Sequential], MRU és el millor algorisme de substitució". Posteriorment, altres investigadors que es van presentar a la 22a conferència VLDB van assenyalar que per als patrons d'accés aleatori i exploracions repetides sobre grans conjunts de dades (de vegades coneguts com a patrons d'accés cíclic) els algorismes de memòria cau MRU tenen més èxits que LRU a causa de la seva tendència a retenir dades més antigues. Els algorismes MRU són més útils en situacions en què com més antic és un element, més probabilitats hi ha d'accedir-hi.

La seqüència d'accés per a l'exemple següent és ABCDECD B.

Aquí, ABCD es col·loquen a la memòria cau, ja que encara hi ha espai disponible. Al 5è accés E, veiem que el bloc que contenia D ara es substitueix per E, ja que aquest bloc es va utilitzar més recentment. Un altre accés a C i al següent accés a D, se substitueix C ja que era el bloc al qual s'accedia just abans de D i així successivament.

LRU segmentat (SLRU)

Aproximacions de LRU

CLOCK-Pro

Polítiques senzilles basades en la freqüència

Ús menys freqüent (LFU)

Utilitzat recentment amb menys freqüència (LFRU)

LFU amb envelliment dinàmic (LFUDA)

Polítiques d'estil RRIP

Predicció d'intervals de re-referència (RRIP)

Polítiques de substitució de la memòria cau aproximant l'algorisme de Bélády

Ull de falcó

Mockingjay

Polítiques de substitució de la memòria cau mitjançant l'aprenentatge automàtic

Altres polítiques de substitució de la memòria cau

Memòria cau de substitució adaptativa (ARC)

AdaptiveClimb (AC)

Rellotge amb substitució adaptativa (CAR)

Cua múltiple (MQ)

S3FIFO: algorisme de desallotjament basat en FIFO millorat

Pannier: algorisme de memòria cau basat en contenidors per a objectes compostos

Referències

↑ «Cache Replacement Policies» (en anglès). https://par.nsf.go.+[Consulta: 3 setembre 2023].
↑ «Cache Replacement Policies» (en anglès). https://ece752.ece.wisc.edu.+[Consulta: 3 setembre 2023].
↑ Johnson, Theodore; Shasha, Dennis Proceedings of the 20th International Conference on Very Large Data Bases [San Francisco, CA], 12-09-1994, pàg. 439–450.
↑ O'Neil, Elizabeth J. «The LRU-K page replacement algorithm for database disk buffering». A: Proceedings of the 1993 ACM SIGMOD international conference on Management of data - SIGMOD '93 (en anglès). New York, NY, USA: ACM, 1993, p. 297–306 (SIGMOD '93). DOI 10.1145/170035.170081. ISBN 978-0-89791-592-2.
↑ Bilal, Muhammad. «Time Aware Least Recent Used (TLRU) cache management policy in ICN». A: 16th International Conference on Advanced Communication Technology (en anglès), 2014, p. 528–532. DOI 10.1109/ICACT.2014.6779016. ISBN 978-89-968650-3-2.

[1] «Cache Replacement Policies» (en anglès). https://par.nsf.go.+[Consulta: 3 setembre 2023].

[2] «Cache Replacement Policies» (en anglès). https://ece752.ece.wisc.edu.+[Consulta: 3 setembre 2023].

[3] Johnson, Theodore; Shasha, Dennis Proceedings of the 20th International Conference on Very Large Data Bases [San Francisco, CA], 12-09-1994, pàg. 439–450.

[4] O'Neil, Elizabeth J. «The LRU-K page replacement algorithm for database disk buffering». A: Proceedings of the 1993 ACM SIGMOD international conference on Management of data - SIGMOD '93 (en anglès). New York, NY, USA: ACM, 1993, p. 297–306 (SIGMOD '93). DOI 10.1145/170035.170081. ISBN 978-0-89791-592-2.

[5] Bilal, Muhammad. «Time Aware Least Recent Used (TLRU) cache management policy in ICN». A: 16th International Conference on Advanced Communication Technology (en anglès), 2014, p. 528–532. DOI 10.1109/ICACT.2014.6779016. ISBN 978-89-968650-3-2.

[1]

[2]

[3]

[4]

[5]