b'\n_START_ARTICLE_\nAlgoritmo de cach\xc3\xa9\n_START_SECTION_\nAlgoritmo de B\xc3\xa9l\xc3\xa1dy\n_START_PARAGRAPH_\nEl algoritmo te\xc3\xb3rico m\xc3\xa1s eficiente debe consistir en descartar la informaci\xc3\xb3n que se tardar\xc3\xa1 m\xc3\xa1s en solicitar. A este resultado \xc3\xb3ptimo se le denomina el de L\xc3\xa1szl\xc3\xb3 B\xc3\xa9l\xc3\xa1dy, o el algoritmo clarividente. Dado que es imposible predecir cu\xc3\xa1ndo en el futuro va a ser solicitada una informaci\xc3\xb3n tambi\xc3\xa9n es imposible predecir cu\xc3\xa1n tarde va a ser solicitada, por lo que este algoritno no es implementable en la pr\xc3\xa1ctica. Los tiempos s\xc3\xb3lo pueden ser calculados te\xc3\xb3ricamente y sirven como patr\xc3\xb3n para cuantificar la eficiencia de los algoritmos reales.\n_START_SECTION_\nMenos usado recientemente (LRU)\n_START_PARAGRAPH_\nEl algoritmo Least Recently Used (LRU) descarta primero los elementos menos usados recientemente. El algoritmo lleva el seguimiento de lo que se va usando, lo que resulta caro si se quiere hacer con precisi\xc3\xb3n. La implementaci\xc3\xb3n de esta t\xc3\xa9cnica requiere llevar la cuenta de la edad de cada elemento de cache y buscar el menos usado sobre la base de ella. En una implementaci\xc3\xb3n como esa, cada vez que se usa un elemento, la edad de todos las dem\xc3\xa1s elementos cambia. LRU pertenece a una familia de algoritmos de caching ente cuyos miembros se incluye 2Q por Theodore Johnson y Dennis Shasha and LRU/K por Pat O\'Neil, Betty O\'Neil y Gerhard Weikum.\n_START_SECTION_\nUsado m\xc3\xa1s recientemente\n_START_PARAGRAPH_\nMost Recently Used (MRU) descarta primero -al contrario de LRU- los elementos m\xc3\xa1s usados recientemente. Chou y Dewitt mostraron sus hallazgos en la 11 conferencia VLDB, haciendo notar que "Cuando un fichero se escanea repetidamente en un patr\xc3\xb3n en bucle secuencial, el mejor algoritmo de reemplazo resulta ser MRU".\xe2\x80\x8b A partir de ah\xc3\xad otros investigadores presentaron en el 22 congreso VLDB que para patrones de acceso aleatorio sobre grandes conjuntos de datos (conocidos como patrones de acceso c\xc3\xadclico) el algoritmo de cache MRU dan mayor tasa de acierto por su tendencia a retener los datos m\xc3\xa1s antiguos.\xe2\x80\x8b Los algoritmos MRU son los m\xc3\xa1s \xc3\xbatiles en situaciones en las que cuanto m\xc3\xa1s antiguo es un elemento, m\xc3\xa1s probable es que se acceda a \xc3\xa9l.\n_START_SECTION_\nPseudo-LRU\n_START_PARAGRAPH_\nPseudo-LRU (PLRU): para caches de CPU con gran asociatividad (generalmente >4 v\xc3\xadas), el coste de implementaci\xc3\xb3n de LRU resulta prohibitivo. En muchos caches de CPUs, una pol\xc3\xadtica que casi siempre desplace uno de los registros menos usados recientemente resulta suficiente. Muchos dise\xc3\xb1os de CPUs imlpementan un algoritmo PLRU que s\xc3\xb3lo necesita un bit por cada \xc3\xadtem en el cache para funcionar._NEWLINE_T\xc3\xadpicamente PLRU tiene una tasa de fallos ligeramente mayor, una latencia ligeramente mejor y usa menos energ\xc3\xada que LRU.\n_START_SECTION_\nReemplazo aleatorio\n_START_PARAGRAPH_\nRandom Replacement (RR): cuando se necesita espacio se selecciona aleatoriamente un candidato a descartar. Este algoritmo no requiere guardar informaci\xc3\xb3n sobre la historia de accesos. Dada su simplicidad, ha sido usado en procesadores ARM.\xe2\x80\x8b Admite simulaci\xc3\xb3n estoc\xc3\xa1stica eficiente.\xe2\x80\x8b\n_START_SECTION_\nLRU segmentado\n_START_PARAGRAPH_\nSegmented LRU (SLRU) divide el cache en dos segmentos, un segmento de supervisi\xc3\xb3n y un segmento protegido. En ambos segmentos se ordenan los elementos del m\xc3\xa1s al menos accedido recientemente. La informaci\xc3\xb3n sobre omisiones se a\xc3\xb1ade al cache en el extremo de los m\xc3\xa1s recientemente accedidos, en el segmento de supervisi\xc3\xb3n. Los aciertos se eliminan de all\xc3\xad donde residen y se a\xc3\xb1aden en el extremo de los m\xc3\xa1s recientemente accedidos dentro del segmento protegido. Los elementos del segmento protegido ha sido entonces accedidos al menos dos veces. El segmento protegido es finito, por lo que la migraci\xc3\xb3n de un elemento del segmento de supervisi\xc3\xb3n al protegido puede forzar la migraci\xc3\xb3n del elemento LRU en el segmento protegido al extremo MRU del segemnto de supervisi\xc3\xb3n, dando a este elemento otra oportunidad para ser accedido antes de ser reemplazado. El l\xc3\xadmite del tama\xc3\xb1o del segmento protegido es un par\xc3\xa1metro de SLRU que var\xc3\xada seg\xc3\xban los patrones de carga E/S. Cuando los datos han de ser descartados del cache se obtienen elementos de extremos LRU del segmento de supervisi\xc3\xb3n.\xe2\x80\x8b"\n_START_SECTION_\nAsociaci\xc3\xb3n de ida y vuelta\n_START_PARAGRAPH_\n2-way set associative: se utiliza para cache de alta velocidad de CPUs, donde incluso un PLRU resulta demasiado lento. En \xc3\xa9l, la direcci\xc3\xb3n de un nuevo elemento se usa para calcular una de las dos posibles posiciones del cache a las que se puede enviar. Este algoritmo requiere s\xc3\xb3lo un bit por cada par de elementos de cache, para indicar cu\xc3\xa1l de los dos se ha sido menos usado recientemente. Esto resulta m\xc3\xa1s eficiente que hacer LRU con las dos.\n_START_SECTION_\nMapeo directo de cache\n_START_PARAGRAPH_\nDirect-mapped cache: se utiliza en las CPU de m\xc3\xa1s alta velocidad donde incluso el cache de ida y vuelta resultan muy lentos. La direcci\xc3\xb3n de los nuevos elementos se utiliza para calcular d\xc3\xb3nde ubicar lo que llega. Lo que hubiera ah\xc3\xad se descarta.\n_START_SECTION_\nMenos frecuentemente usados\n_START_PARAGRAPH_\nLeast Frequently Used (LFU) cuenta la frecuencia con la que un elemento se solicita. Aqu\xc3\xa9llos que se solicitan menos se descartan primero.\n_START_SECTION_\ncache de reemplazo adaptativo\n_START_PARAGRAPH_\nAdaptive Replacement Cache (ARC)\xe2\x80\x8b hace un balanceo constante entre LRU y LFU, mejorando el resultado con su combinaci\xc3\xb3n._NEWLINE_ARC mejora SLRU usando informaci\xc3\xb3n acerca de elementos desalojados recientemente para ajustar din\xc3\xa1micamente el tama\xc3\xb1o de el segmento protegido y del supervisi\xc3\xb3n para hacer mejor uso del espacio disponible.\n_START_SECTION_\nCLOCK con reemplazo adaptativo\n_START_PARAGRAPH_\nCLOCK with Adaptive Replacement (CAR) combina Adaptive Replacement Cache (ARC) con el algoritmo de reemplazo de p\xc3\xa1ginas CLOCK. CAR tiene unas prestaciones comparables a las de ARC, y mejora sustancialmente tanto LRU como CLOCK. Del mismo modo que ARC, CAR se autoajusta y no requiere de par\xc3\xa1metros del usuario.\n_START_SECTION_\nAlgoritmo de cache multi-cola\n_START_PARAGRAPH_\nMulti Queue (MQ) caching algorithm:\xe2\x80\x8b (por Zhou, Philbin, and Li).'