logo

TechCodeview

Повний навчальний посібник із кешу LRU із впровадженнями

Що таке кеш LRU?

Алгоритми заміни кешу ефективно розроблені для заміни кешу, коли місце заповнено. The Найменше використовуваний (LRU) є одним із таких алгоритмів. Як випливає з назви, коли кеш-пам’ять заповнена, LRU вибирає дані, які нещодавно використовувалися, і видаляє їх, щоб звільнити місце для нових даних. Пріоритет даних у кеші змінюється відповідно до потреб цих даних, тобто якщо деякі дані нещодавно отримані або оновлені, пріоритет цих даних буде змінено та призначено для найвищого пріоритету, а пріоритет даних зменшиться, якщо він залишається невикористаним після операцій.

Зміст

LRU Алгоритм є стандартною проблемою, і він може мати варіації відповідно до потреб, наприклад, в операційних системах LRU відіграє вирішальну роль, оскільки його можна використовувати як алгоритм заміни сторінок, щоб мінімізувати помилки сторінки.



Операції з LRU Cache:

  • LRUCache (Ємність c): Ініціалізація кешу LRU із позитивним розміром в.
  • отримати (ключ) : повертає значення ключа к’ якщо він присутній у кеші, інакше він повертає -1. Також оновлює пріоритет даних у кеші LRU.
  • put (ключ, значення): Оновіть значення ключа, якщо він існує. В іншому випадку додайте пару ключ-значення до кешу. Якщо кількість ключів перевищила ємність кешу LRU, відхиліть останній використаний ключ.

Робота LRU Cache:

Припустімо, що у нас є кеш LRU ємністю 3, і ми хочемо виконати наступні операції:

  1. Помістіть (ключ=1, значення=A) в кеш
  2. Помістіть (ключ=2, значення=B) в кеш
  3. Помістіть (ключ=3, значення=C) в кеш
  4. Отримати (key=2) з кешу
  5. Отримати (key=4) з кешу
  6. Помістіть (ключ=4, значення=D) в кеш
  7. Помістіть (ключ=3, значення=E) в кеш
  8. Отримати (key=4) з кешу
  9. Помістіть (ключ=1, значення=A) в кеш

Наведені вище операції виконуються одна за одною, як показано на зображенні нижче:

Working-of-LRU-Cache-(1)



Детальне пояснення кожної операції:

  1. Put (ключ 1, значення A) : Оскільки кеш LRU має порожню ємність = 3, немає потреби в будь-якій заміні, і ми розміщуємо {1 : A} у верхній частині, тобто {1 : A} має найвищий пріоритет.
  2. Покласти (ключ 2, значення B) : Оскільки кеш LRU має порожню ємність=2, знову немає потреби в будь-якій заміні, але тепер {2 : B} має найвищий пріоритет і пріоритет {1 : A} зменшується.
  3. Покласти (ключ 3, значення C) : Все ще є 1 вільне місце в кеші, тому помістіть {3 : C} без будь-яких замін, зверніть увагу, тепер кеш заповнений і поточний порядок пріоритету від найвищого до найнижчого {3: C}, {2: B }, {1:A}.
  4. Отримати (клавіша 2) : Тепер поверніть значення key=2 під час цієї операції, також оскільки використовується key=2, тепер новий порядок пріоритетів {2:B}, {3:C}, {1:A}
  5. Отримати (ключ 4): Зверніть увагу, що ключ 4 відсутній у кеші, ми повертаємо «-1» для цієї операції.
  6. Покласти (ключ 4, значення D) : Зверніть увагу, що кеш ЗАПОВНЕНИЙ, тепер використовуйте алгоритм LRU, щоб визначити, який ключ використовувався останнім часом. Оскільки {1:A} має найменший пріоритет, видаліть {1:A} з нашого кешу та помістіть {4:D} у кеш. Зверніть увагу, що новий порядок пріоритетів: {4:D}, {2:B}, {3:C}
  7. Покласти (ключ 3, значення E) : Оскільки ключ=3 уже був присутній у кеші зі значенням=C, тому ця операція не призведе до видалення будь-якого ключа, натомість вона оновить значення ключу=3 до « І' . Тепер новий порядок пріоритету стане {3:E}, {4:D}, {2:B}
  8. Отримати (клавіша 4) : повертає значення key=4. Тепер новий пріоритет стане {4:D}, {3:E}, {2:B}
  9. Put (ключ 1, значення A) : Оскільки наш кеш ПОВНИЙ, використовуйте наш алгоритм LRU, щоб визначити, який ключ використовувався останнім часом, і оскільки {2:B} мав найменший пріоритет, видаліть {2:B} з нашого кешу та помістіть {1:A} у кеш. Тепер новий порядок пріоритетів: {1:A}, {4:D}, {3:E}

Способи впровадження кешу LRU:

Кеш LRU може бути реалізований різними способами, і кожен програміст може вибрати інший підхід. Однак нижче наведено підходи, які зазвичай використовуються:

  1. LRU з використанням черги та хешування
  2. використання LRU Двозв'язаний список + хешування
  3. LRU за допомогою Deque
  4. LRU за допомогою стека
  5. використання LRU Контрреалізація
  6. LRU з використанням відкладених оновлень

Реалізація кешу LRU за допомогою черги та хешування:

Ми використовуємо дві структури даних для реалізації LRU Cache.



  1. Черга реалізується за допомогою двозв’язаного списку. Максимальний розмір черги дорівнюватиме загальній кількості доступних кадрів (розмір кешу). Сторінки, які використовувалися останнім часом, будуть розміщені біля переднього кінця, а сторінки, які використовувалися найменше, – біля заднього кінця.
  2. Хеш з номером сторінки як ключем і адресою відповідного вузла черги як значенням.

Коли є посилання на сторінку, потрібна сторінка може бути в пам'яті. Якщо він є в пам'яті, нам потрібно від'єднати вузол списку та перенести його на початок черги.
Якщо потрібної сторінки немає в пам'яті, ми заносимо її в пам'ять. Простими словами, ми додаємо новий вузол у початок черги та оновлюємо відповідну адресу вузла в хеші. Якщо черга заповнена, тобто всі кадри заповнені, ми видаляємо вузол із задньої частини черги та додаємо новий вузол до початку черги.

Ілюстрація:

Давайте розглянемо операції, Посилається ключ x з у кеші LRU: { 1, 2, 3, 4, 1, 2, 5, 1, 2, 3 }
Примітка: Спочатку в пам'яті немає сторінки.

На зображеннях нижче показано покрокове виконання вищевказаних операцій над кеш-пам’яттю LRU.

LRU-queue-Implementation-min-(1)

Алгоритм:

  • Створіть клас LRUCache з оголошенням списку типу int, невпорядкованої карти типу і змінна для зберігання максимального розміру кешу
  • У функції посилання LRUCache
    • Якщо цього значення немає в черзі, тоді вставте це значення перед чергою та видаліть останнє значення, якщо черга заповнена
    • Якщо значення вже є, видаліть його з черги та помістіть на початок черги
  • У функції відображення друку LRUCache використовує чергу, починаючи з передньої частини

Нижче наведено реалізацію вищезазначеного підходу:

C++




// 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.> #include> using> namespace> std;> > class> LRUCache {> >// store keys of cache> >list<>int>>dq;> > >// store references of key in cache> >unordered_map<>int>, list<>int>>::ітератор> ma;> >int> csize;>// maximum capacity of cache> > public>:> >LRUCache(>int>);> >void> refer(>int>);> >void> display();> };> > // Declare the size> LRUCache::LRUCache(>int> n) { csize = n; }> > // Refers key x with in the LRU cache> void> LRUCache::refer(>int> x)> {> >// not present in cache> >if> (ma.find(x) == ma.end()) {> >// cache is full> >if> (dq.size() == csize) {> >// delete least recently used element> >int> last = dq.back();> > >// Pops the last element> >dq.pop_back();> > >// Erase the last> >ma.erase(last);> >}> >}> > >// present in cache> >else> >dq.erase(ma[x]);> > >// update reference> >dq.push_front(x);> >ma[x] = dq.begin();> }> > // Function to display contents of cache> void> LRUCache::display()> {> > >// Iterate in the deque and print> >// all the elements in it> >for> (>auto> it = dq.begin(); it != dq.end(); it++)> >cout << (*it) <<>' '>;> > >cout << endl;> }> > // Driver Code> int> main()> {> >LRUCache ca(4);> > >ca.refer(1);> >ca.refer(2);> >ca.refer(3);> >ca.refer(1);> >ca.refer(4);> >ca.refer(5);> >ca.display();> > >return> 0;> }> // This code is contributed by Satish Srinivas> 

>

>

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 = номер сторінки;> > >// Initialize prev and next as NULL> >temp->попередній = temp->next = NULL;> > >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->кількість = 0;> >queue->front = queue->rear = NULL;> > >// Number of frames that can be stored in memory> >queue->numberOfFrames = numberOfFrames;> > >return> queue;> }> > // A utility function to create an empty Hash of given> // capacity> Hash* createHash(>int> capacity)> {> >// Allocate memory for hash> >Hash* hash = (Hash*)>malloc>(>sizeof>(Hash));> >hash->емкость = місткість;> > >// Create an array of pointers for referring queue nodes> >hash->масив>> >= (QNode**)>malloc>(hash->місткість *>sizeof>(QNode*));> > >// Initialize all hash entries as empty> >int> i;> >for> (i = 0; i capacity; ++i)> >hash->масив[i] = NULL;> > >return> hash;> }> > // A function to check if there is slot available in memory> int> AreAllFramesFull(Queue* queue)> {> >return> queue->count == queue->numberOfFrames;> }> > // A utility function to check if queue is empty> int> isQueueEmpty(Queue* queue)> {> >return> queue->задній == NULL;> }> > // A utility function to delete a frame from queue> void> deQueue(Queue* queue)> {> >if> (isQueueEmpty(queue))> >return>;> > >// If this is the only node in list, then change front> >if> (queue->front == queue->rear)> >queue->фронт = NULL;> > >// Change rear and remove the previous rear> >QNode* temp = queue->задній;> >queue->задній = черга->задній->попередній;> > >if> (queue->ззаду)> >queue->задній->наступний = NULL;> > >free>(temp);> > >// decrement the number of full frames by 1> >queue->рахувати--;> }> > // 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;> >deQueue(queue);> >}> > >// Create a new node with given page number,> >// And add the new node to the front of queue> >QNode* temp = newQNode(pageNumber);> >temp->наступний = черга->передній;> > >// If queue is empty, change both front and rear> >// pointers> >if> (isQueueEmpty(queue))> >queue->rear = queue->front = temp;> >else> // Else change the front> >{> >queue->front->prev = temp;> >queue->фронт = темп;> >}> > >// Add page entry to hash also> >hash->масив[Номерсторінки] = temp;> > >// increment number of full frames> >queue->рахувати++;> }> > // This function is called when a page with given> // 'pageNumber' is referenced from cache (or memory). There> // 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->масив[Номерсторінки];> > >// the page is not in cache, bring it> >if> (reqPage == NULL)> >Enqueue(queue, hash, pageNumber);> > >// page is there and not at front, change pointer> >else> if> (reqPage != queue->спереду) {>> >// Unlink rquested page from its current location> >// in queue.> >reqPage->попередня->наступна = reqPage->наступна;> >if> (reqPage->далі)> >reqPage->наступна->попередня = reqPage->попередня;> > >// If the requested page is rear, then change rear> >// as this node will be moved to front> >if> (reqPage == queue->ззаду) {> >queue->rear = reqPage->prev;> >queue->задній->наступний = NULL;> >}> > >// Put the requested page before current front> >reqPage->наступний = черга->передній;> >reqPage->попередній = NULL;> > >// Change prev of current front> >reqPage->наступна->попередня = reqPage;> > >// Change front to the requested page> >queue->front = reqPage;> >}> }> > // Driver code> int> main()> {> >// Let cache can hold 4 pages> >Queue* q = createQueue(4);> > >// Let 10 different pages can be requested (pages to be> >// referenced are numbered from 0 to 9> >Hash* hash = createHash(10);> > >// Let us refer pages 1, 2, 3, 1, 4, 5> >ReferencePage(q, hash, 1);> >ReferencePage(q, hash, 2);> >ReferencePage(q, hash, 3);> >ReferencePage(q, hash, 1);> >ReferencePage(q, hash, 4);> >ReferencePage(q, hash, 5);> > >// Let us print cache frames after the above referenced> >// pages> >printf>(>'%d '>, q->front->pageNumber);> >printf>(>'%d '>, q->front->next->pageNumber);> >printf>(>'%d '>, q->front->next->next->pageNumber);> >printf>(>'%d '>, q->front->next->next->next->pageNumber);> > >return> 0;> }> 

>

>

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> 

>

>

Python3




# 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>>doubleQueue;> > >// store references of key in cache> >private> HashSet<>int>>hashSet;> > >// 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> 

>

>

Реалізація кешу LRU за допомогою подвійного зв’язаного списку та хешування :

Ідея дуже проста, тобто продовжуйте вставляти елементи в голову.

  • якщо елемент відсутній у списку, додайте його до початку списку
  • якщо елемент присутній у списку, тоді перемістіть елемент у заголовок і перемістіть решту елемента списку

Зауважте, що пріоритет вузла залежатиме від відстані цього вузла від голови, чим ближче вузол до голови, тим вищий пріоритет він має. Отже, коли розмір кешу заповнений і нам потрібно видалити якийсь елемент, ми видаляємо елемент, який примикає до хвоста двозв’язаного списку.

Реалізація кешу LRU за допомогою Deque & Hashmap:

Структура даних Deque дозволяє вставляти та видаляти як з початку, так і з кінця, ця властивість дозволяє реалізувати LRU, оскільки елемент Front може представляти елемент з високим пріоритетом, тоді як кінцевий елемент може бути елементом з низьким пріоритетом, тобто найменш використовуваним.

Працює:

  1. Отримати операцію : Перевіряє, чи існує ключ у хеш-карті кешу, і дотримується наведених нижче випадків на deque:
    • Якщо ключ знайдено:
      • Предмет вважається нещодавно використаним, тому його переміщують на передню частину дека.
      • Значення, пов’язане з ключем, повертається як результатget>операція.
    • Якщо ключ не знайдено:
      • повертає -1, щоб вказати, що такого ключа немає.
  2. Операція Put: Спочатку перевірте, чи ключ уже існує в хеш-карті кешу, і дотримуйтесь наведених нижче випадків у deque
    • Якщо ключ існує:
      • Значення, пов’язане з ключем, оновлюється.
      • Елемент переміщується на передню частину дека, оскільки тепер він використаний останнім.
    • Якщо ключ не існує:
      • Якщо кеш-пам’ять заповнена, це означає, що потрібно вставити новий елемент, а елемент, який використовувався найменше, потрібно вилучити. Це робиться шляхом видалення елемента з кінця довжини та відповідного запису з хеш-карти.
      • Потім нова пара ключ-значення вставляється як у хеш-карту, так і в передню частину двоканального ряду, щоб означити, що це останній використаний елемент

Реалізація кешу LRU за допомогою Stack & Hashmap:

Реалізація кешу LRU (найменш використовуваного) за допомогою структури даних стека та хешування може бути дещо складною, оскільки простий стек не забезпечує ефективного доступу до елемента, який використовувався найменше. Однак ви можете поєднати стек із хеш-картою, щоб досягти цього ефективного результату. Ось підхід високого рівня для його реалізації:

  1. Використовуйте хеш-карту : Хеш-карта зберігатиме пари ключ-значення кешу. Ключі будуть зіставлені з відповідними вузлами в стеку.
  2. Використовуйте стек : стек підтримуватиме порядок ключів на основі їх використання. Найменше використовуваний предмет буде внизу стека, а останній використаний – угорі

Такий підхід не дуже ефективний, тому використовується не часто.

Кеш LRU з використанням реалізації лічильника:

Кожен блок у кеші матиме власний лічильник LRU, до якого належить значення лічильника від 0 до n-1} , тут ' п ' представляє розмір кешу. Блок, який змінюється під час заміни блоку, стає блоком MRU, і в результаті його значення лічильника змінюється на n – 1. Значення лічильника, які перевищують значення лічильника блоку, до якого здійснюється доступ, зменшуються на одиницю. Решта блоків без змін.

Значення Conter

Пріоритет

Статус використаний

0

Низький

Найменше нещодавно використовуваний

центральна кнопка в css

n-1

Високий

Останні використані

Реалізація кешу LRU за допомогою відкладених оновлень:

Реалізація кешу LRU (найменше використовуваного) з використанням відкладених оновлень є поширеною технікою підвищення ефективності операцій кешу. Відкладені оновлення включають відстеження порядку доступу до елементів без негайного оновлення всієї структури даних. У разі пропуску кешу ви можете вирішити, виконувати чи ні повне оновлення на основі певних критеріїв.

Аналіз складності кешу LRU:

  • Часова складність:
    • Операція Put(): O(1), тобто час, необхідний для вставки або оновлення нової пари ключ-значення, є постійним
    • Операція Get(): O(1), тобто час, необхідний для отримання значення ключа, є постійним
  • Допоміжний простір: O(N), де N - ємність кешу.

Переваги кешу LRU:

  • Швидкий доступ : Для доступу до даних із кешу LRU потрібно O(1).
  • Швидке оновлення : Для оновлення пари ключ-значення в кеші LRU потрібно O(1) часу.
  • Швидке видалення останніх використаних даних : потрібно O(1) видалити те, що нещодавно не використовувалося.
  • Жодного обмолоту: LRU менш сприйнятливий до трішу порівняно з FIFO, оскільки він враховує історію використання сторінок. Він може визначати, які сторінки часто використовуються, і розставляти їм пріоритети для розподілу пам’яті, зменшуючи кількість помилок сторінки та операцій введення-виведення диска.

Недоліки кешу LRU:

  • Для підвищення ефективності потрібен великий розмір кешу.
  • Для цього потрібна додаткова структура даних.
  • Апаратна підтримка висока.
  • У LRU виявлення помилок складніше порівняно з іншими алгоритмами.
  • Він має обмежену прийнятність.

Реальне застосування кешу LRU:

  • У системах баз даних для швидких результатів запиту.
  • В операційних системах для мінімізації помилок сторінок.
  • Текстові редактори та IDE для зберігання часто використовуваних файлів або фрагментів коду
  • Мережеві маршрутизатори та комутатори використовують LRU для підвищення ефективності комп’ютерної мережі
  • В оптимізації компілятора
  • Інструменти передбачення тексту та автозаповнення