Рубрики

Реализация LRU Cache

Как реализовать схему кэширования LRU? Какие структуры данных следует использовать?
Нам дается общее количество возможных номеров страниц, на которые можно сослаться. Нам также дается размер кеша (или памяти) (количество фреймов страницы, которые может хранить кеш за раз). Схема кэширования LRU состоит в том, чтобы удалять наименее использованный кадр, когда кэш заполнен и на него ссылается новая страница, которой нет в кэше. Пожалуйста, смотрите книгу Гальвина для более подробной информации (см. Слайд замены страницы LRU здесь ).

Мы используем две структуры данных для реализации LRU-кэша.

  1. Очередь, которая реализована с использованием двусвязного списка. Максимальный размер очереди будет равен общему количеству доступных кадров (размер кэша). Последние использованные страницы будут рядом с передней частью, а наименьшее количество последних страниц будет рядом с задней частью.
  2. Хеш с номером страницы в качестве ключа и адресом соответствующего узла очереди в качестве значения.

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

Пример — рассмотрим следующую ссылочную строку:

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

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

Примечание: изначально в памяти нет страницы.

C ++ с использованием STL

// Мы можем использовать список контейнеров stl как double
// закончил очередь для хранения ключей кеша, с
// нисходящее время обращения с фронта
// назад и установить контейнер для проверки наличия
// ключа. Но чтобы получить адрес ключа
// в списке с использованием find (), это занимает O (N) время.
// Это можно оптимизировать, сохранив ссылку
// (итератор) для каждого ключа в хэш-карте.
#include <bits/stdc++.h>

using namespace std;

  

class LRUCache {

    // храним ключи кеша

    list<int> dq;

  

    // храним ссылки на ключ в кеше

    unordered_map<int, list<int>::iterator> ma;

    int csize; // максимальная емкость кеша

  

public:

    LRUCache(int);

    void refer(int);

    void display();

};

  
// Объявляем размер

LRUCache::LRUCache(int n)

{

    csize = n;

}

  
// Отсылает ключ x в кеш LRU

void LRUCache::refer(int x)

{

    // отсутствует в кеше

    if (ma.find(x) == ma.end()) {

        // кеш заполнен

        if (dq.size() == csize) {

            // удаляем наименее недавно использованный элемент

            int last = dq.back();

  

            // выскакивает последний elmeent

            dq.pop_back();

  

            // Стереть последний

            ma.erase(last);

        }

    }

  

    // присутствует в кеше

    else

        dq.erase(ma[x]);

  

    // обновить ссылку

    dq.push_front(x);

    ma[x] = dq.begin();

}

  
// Функция для отображения содержимого кеша

void LRUCache::display()

{

  

    // Итерация в деке и печать

    // все элементы в нем

    for (auto it = dq.begin(); it != dq.end();

         it++)

        cout << (*it) << " ";

  

    cout << endl;

}

  
// Код драйвера

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;

}
// Этот код предоставлен Satish Srinivas

С

// AC программа для показа реализации LRU-кэша
#include <stdio.h>
#include <stdlib.h>

  
// Узел очереди (очередь реализована с использованием двусвязного списка)

typedef struct QNode {

    struct QNode *prev, *next;

    unsigned pageNumber; // номер страницы, сохраненный в этом QNode

} QNode;

  
// Очередь (коллекция FIFO узлов очереди)

typedef struct Queue {

    unsigned count; // Количество заполненных кадров

    unsigned numberOfFrames; // общее количество кадров

    QNode *front, *rear;

} Queue;

  
// Хеш (коллекция указателей на узлы очереди)

typedef struct Hash {

    int capacity; // сколько страниц может быть

    QNode** array; // массив узлов очереди

} Hash;

  
// Служебная функция для создания нового узла очереди. Узел очереди
// будет хранить указанный «pageNumber»
QNode* newQNode(unsigned pageNumber)
{

    // Распределяем память и присваиваем 'pageNumber'

    QNode* temp = (QNode*)malloc(sizeof(QNode));

    temp->pageNumber = pageNumber;

  

    // Инициализируем prev и next как NULL

    temp->prev = temp->next = NULL;

  

    return temp;

}

  
// Утилита для создания пустой очереди.
// В очереди может быть не более 'numberOfFrames' узлов

Queue* createQueue(int numberOfFrames)

{

    Queue* queue = (Queue*)malloc(sizeof(Queue));

  

    // очередь пуста

    queue->count = 0;

    queue->front = queue->rear = NULL;

  

    // Количество кадров, которые можно сохранить в памяти

    queue->numberOfFrames = numberOfFrames;

  

    return queue;

}

  
// Утилита для создания пустого хэша заданной емкости

Hash* createHash(int capacity)

{

    // Выделим память для хэша

    Hash* hash = (Hash*)malloc(sizeof(Hash));

    hash->capacity = capacity;

  

    // Создать массив указателей для реферирования узлов очереди

    hash->array = (QNode**)malloc(hash->capacity * sizeof(QNode*));

  

    // Инициализируем все записи хеша как пустые

    int i;

    for (i = 0; i < hash->capacity; ++i)

        hash->array[i] = NULL;

  

    return hash;

}

  
// Функция для проверки наличия свободного места в памяти

int AreAllFramesFull(Queue* queue)

{

    return queue->count == queue->numberOfFrames;

}

  
// Утилита для проверки, пуста ли очередь

int isQueueEmpty(Queue* queue)

{

    return queue->rear == NULL;

}

  
// Утилита для удаления кадра из очереди

void deQueue(Queue* queue)

{

    if (isQueueEmpty(queue))

        return;

  

    // Если это единственный узел в списке, то измените фронт

    if (queue->front == queue->rear)

        queue->front = NULL;

  

    // Изменить задний и удалить предыдущий задний

    QNode* temp = queue->rear;

    queue->rear = queue->rear->prev;

  

    if (queue->rear)

        queue->rear->next = NULL;

  

    free(temp);

  

    // уменьшить количество полных кадров на 1

    queue->count--;

}

  
// Функция для добавления страницы с указанным «pageNumber» в обе очереди
// и хеш

void Enqueue(Queue* queue, Hash* hash, unsigned pageNumber)

{

    // Если все кадры заполнены, удалите страницу сзади

    if (AreAllFramesFull(queue)) {

        // удаляем страницу из хеша

        hash->array[queue->rear->pageNumber] = NULL;

        deQueue(queue);

    }

  

    // Создать новый узел с заданным номером страницы,

    // И добавляем новый узел в начало очереди

    QNode* temp = newQNode(pageNumber);

    temp->next = queue->front;

  

    // Если очередь пуста, меняем передний и задний указатели

    if (isQueueEmpty(queue))

        queue->rear = queue->front = temp;

    else // Остальное меняем фронт

    {

        queue->front->prev = temp;

        queue->front = temp;

    }

  

    // Добавить запись страницы в хеш

    hash->array[pageNumber] = temp;

  

    // увеличиваем количество полных кадров

    queue->count++;

}

  
// Эта функция вызывается при обращении к странице с указанным «pageNumber»
// из кеша (или памяти). Есть два случая:
// 1. Кадра нет в памяти, мы заносим его в память и добавляем вперед
// очереди
// 2. Кадр находится в памяти, мы перемещаем кадр в начало очереди

void ReferencePage(Queue* queue, Hash* hash, unsigned pageNumber)

{

    QNode* reqPage = hash->array[pageNumber];

  

    // страница не в кеше, вывести ее

    if (reqPage == NULL)

        Enqueue(queue, hash, pageNumber);

  

    // страница есть, а не впереди, меняем указатель

    else if (reqPage != queue->front) {

        // Отключить запрашиваемую страницу от ее текущего местоположения

        // в очереди.

        reqPage->prev->next = reqPage->next;

        if (reqPage->next)

            reqPage->next->prev = reqPage->prev;

  

        // Если запрашиваемая страница задняя, то изменить заднюю

        // как этот узел будет перемещен вперед

        if (reqPage == queue->rear) {

            queue->rear = reqPage->prev;

            queue->rear->next = NULL;

        }

  

        // Поместить запрошенную страницу перед текущим фронтом

        reqPage->next = queue->front;

        reqPage->prev = NULL;

  

        // Изменение предыстории текущего фронта

        reqPage->next->prev = reqPage;

  

        // Изменить фронт на запрашиваемую страницу

        queue->front = reqPage;

    }

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    // Пусть кеш может содержать 4 страницы

    Queue* q = createQueue(4);

  

    // Пусть может быть запрошено 10 разных страниц

    // ссылки нумеруются от 0 до 9

    Hash* hash = createHash(10);

  

    // Давайте сошлемся на страницы 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);

  

    // Давайте распечатаем кадры кеша после упомянутых выше страниц

    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 Deque как двойной

   закончена очередь для хранения ключей кеша, с

   время опускания с фронта

   назад и установить контейнер, чтобы проверить наличие

   ключа. Но удалите ключ из Deque, используя

   удалить (), это занимает O (N) время. Это может быть

   оптимизирован путем сохранения ссылки (итератор) на

   каждый ключ в хэш-карте. * /

import java.util.Deque;

import java.util.HashSet;

import java.util.LinkedList;

import java.util.Iterator;

public class LRUCache {

    // храним ключи кеша

    static Deque<Integer> dq;

    // храним ссылки на ключ в кеше

    static HashSet<Integer> map;

    // максимальная емкость кеша

    static int csize;

  

    LRUCache(int n)

    {

        dq = new LinkedList<>();

        map = new HashSet<>();

        csize = n;

    }

  

    / * Относится к ключу x в кеше LRU * /

    public void refer(int x)

    {

        if (!map.contains(x)) {

            if (dq.size() == csize) {

                int last = dq.removeLast();

                map.remove(last);

            }

        }

        else {

            / * Найденная страница не всегда может быть последним элементом, даже если она

               промежуточный элемент, который необходимо удалить и добавить в начало

               очереди * /

            int index = 0, i = 0;

            Iterator<Integer> itr = dq.iterator();

            while (itr.hasNext()) {

                if (itr.next() == x) {

                    index = i;

                    break;

                }

                i++;

            }

            dq.remove(index);

        }

        dq.push(x);

        map.add(x);

    }

  

    // отображаем содержимое кеша

    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();

    }

}
// Этот код предоставлен Гауравом Тивари


Выход:

5 4 1 3

Эта статья составлена Aashish Barnwal и рецензирована командой GeeksforGeeks. Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Реализация LRU Cache

0.00 (0%) 0 votes