LRU (Least Recently Used)

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 17:35, 21 января 2019.

LRU (Least Recently Used) — это алгоритм, при котором вытесняются значения, которые дольше всего не запрашивались. Соответственно, необходимо хранить время последнего запроса к значению. И как только число закэшированных значений превосходит N необходимо вытеснить из кеша значение, которое дольше всего не запрашивалось.[Источник 1].

Алгоритм

Сначала отбрасывает наименее использованные предметы. Этот алгоритм требует отслеживания того, что и когда использовалось, что дорого, если нужно убедиться, что алгоритм всегда отбрасывает наименее использованный элемент. Общие реализации этого метода требуют хранения «битов возраста» для строк кэша и отслеживания строки кэша «Наименее недавно использованные» на основе битов возраста. В такой реализации каждый раз, когда используется строка кэша, возраст всех других строк кэша изменяется. Последовательность доступа для приведенного ниже примера: A B C D E D F. Алгоритм кеширования представлен на рисунке 1.

Рисунок 1 - Алгоритм кеширования LRU

Здесь A B C D помещаются в кэш, так как еще есть свободное место. При пятом доступе E мы видим, что блок, который содержал D, теперь заменен на E, так как этот блок использовался совсем недавно. Другой доступ к C и при следующем доступе к D заменяется C, так как это был блок, к которому обращались непосредственно перед D, и так далее.

Реализация

Схема кэширования LRU состоит в том, чтобы удалить наименее использованный кадр, когда кэш заполнен, и имеется ссылка на новую страницу, которой нет в кэше. [Источник 2].

Структура данных

  • очередь, которая реализована с использованием двусвязного списка. Максимальный размер очереди будет равен общему количеству доступных кадров (размеру кэша). Самые последние использованные страницы будут находиться ближе к переднему краю, а наименее недавние страницы будут ближе к заднему;
  • хеш с номером страницы в качестве ключа и адресом соответствующего узла очереди в качестве значения.

Пример

Рассмотреть следующую ссылочную строку:

 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

Найти количество сбоев страниц, используя алгоритм замены страниц с наименьшим количеством использовавшихся (LRU) страниц с 3-мя фреймами. Решение примера представлено на рисунках 2 и 3.

Рисунок 2 – Решение примера
Рисунок 3 – Решение примера

Вывод:

 5 4 1 3

Представление LRU на языке программирования

Язык С++ с использованием STL

  #include <bits/stdc++.h> 
using namespace std; 
  
class LRUCache 
{ 
    // store keys of cache 
    list<int> dq; 
  
    // store references of key in cache 
    unordered_map<int, list<int>::iterator> ma; 
    int csize; //maximum capacity of cache 
  
public: 
    LRUCache(int); 
    void refer(int); 
    void display(); 
}; 
  
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(); 
            dq.pop_back(); 
            ma.erase(last); 
        } 
    } 
  
    // present in cache 
    else
        dq.erase(ma[x]); 
  
    // update reference 
    dq.push_front(x); 
    ma[x] = dq.begin(); 
} 
  
// display contents of cache 
void LRUCache::display() 
{ 
    for (auto it = dq.begin(); it != dq.end(); 
                                        it++) 
        cout << (*it) << " "; 
  
    cout << endl; 
} 
  
// Driver program to test above functions 
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; 
}

Язык С

// A C program to show implementation of LRU cache 
#include <stdio.h> 
#include <stdlib.h> 
  
// 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; 
  
    // Initialize prev and next as NULL 
    temp->prev = 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->count = 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->capacity = capacity; 
  
    // Create an array of pointers for refering queue nodes 
    hash->array = (QNode **) malloc( hash->capacity * sizeof( QNode* ) ); 
  
    // Initialize all hash entries as empty 
    int i; 
    for( i = 0; i < hash->capacity; ++i ) 
        hash->array[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->rear == 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->front = NULL; 
  
    // Change rear and remove the previous rear 
    QNode* temp = queue->rear; 
    queue->rear = queue->rear->prev; 
  
    if (queue->rear) 
        queue->rear->next = NULL; 
  
    free( temp ); 
  
    // decrement the number of full frames by 1 
    queue->count--; 
} 
  
// 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->next = queue->front; 
  
    // 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->front = temp; 
    } 
  
    // Add page entry to hash also 
    hash->array[ pageNumber ] = temp; 
  
    // increment number of full frames 
    queue->count++; 
} 
  
// 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->array[ pageNumber ]; 
  
    // 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->front) 
    { 
        // Unlink rquested page from its current location 
        // in queue. 
        reqPage->prev->next = reqPage->next; 
        if (reqPage->next) 
           reqPage->next->prev = reqPage->prev; 
  
        // If the requested page is rear, then change rear 
        // as this node will be moved to front 
        if (reqPage == queue->rear) 
        { 
           queue->rear = reqPage->prev; 
           queue->rear->next = NULL; 
        } 
  
        // Put the requested page before current front 
        reqPage->next = queue->front; 
        reqPage->prev = NULL; 
  
        // Change prev of current front 
        reqPage->next->prev = reqPage; 
  
        // Change front to the requested page 
        queue->front = reqPage; 
    } 
} 
  
// Driver program to test above functions 
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

import java.util.Deque; 
import java.util.HashSet; 
import java.util.LinkedList; 
import java.util.Iterator; 
public class LRUCache { 
    // store keys of cache 
    static Deque<Integer> dq;   
    // store references of key in cache  
    static HashSet<Integer> map; 
    //maximum capacity of cache  
    static int csize; 
      
    LRUCache(int n) 
    { 
        dq=new LinkedList<>(); 
        map=new HashSet<>(); 
        csize=n; 
    } 
      
    /* Refers key x with in the LRU cache */
    public void refer(int x) 
    { 
        if(!map.contains(x)) 
        { 
            if(dq.size()==csize) 
            { 
                int last=dq.removeLast(); 
                map.remove(last); 
            } 
        } 
        else
        { 
            dq.remove(x); 
        } 
        dq.push(x); 
        map.add(x); 
    } 
      
    // display contents of cache  
    public void display() 
    { 
        Iterator<Integer> itr = dq.iterator(); 
        while(itr.hasNext()) 
        { 
            System.out.print(itr.next()+" "); 
        } 
    } 
      
      
    public static void main(String[] args) { 
        LRUCache ca=new LRUCache(4); 
        ca.refer(1);  
        ca.refer(2);  
        ca.refer(3);  
        ca.refer(1);  
        ca.refer(4);  
        ca.refer(5);  
        ca.display();      
    } 
}

Источники

  1. LRU, метод вытеснения из кэша // Habrahabr [2006 - 2019]. Дата обновления: 22.01.12. URL: https://habr.com/ru/post/136758/ (дата обращения: 21.01.2019)
  2. Page Replacement Algorithm // Блог [2019-2019]. Дата обновления: 08.02.02. URL: http://www.informit.com/articles/article.aspx?p=25260&seqNum=7l (дата обращения: 21.01.2019)