Действие SET при обнаружении промаха в реализации Java-кэша LRU

Question

Я реализую кеш LRU в Java, используя мою собственную реализацию DoublyLinkedList с узлом, имеющим целочисленный ключ и значения, где ключ обозначает идентификатор страницы, а значение обозначает его местоположение на диске. Кроме того, я использую Hashmap для доступа O(1). Я знаю следующие основы реализации:

Если запрашиваемый ключ является попаданием в кэш, верните его значение (то есть его местоположение) и переместите этот узел в начало DoublyLinkedList.

У меня есть сомнения в другом важном аспекте, когда это мисс. Согласно различным ресурсам, когда это происходит, тогда номер страницы, который является ключевым в моем случае, устанавливается в качестве заголовка LinkedList, и при этом, если мы сталкиваемся с возможностью заполнения, мы удаляем элемент в конце, а затем введите его на фронт. Теперь для целей реализации, каким должно быть "значение" такого номера страницы (т.е. ключа), когда я помещаю его в кэш? Должен ли я установить его на мусор? В моей представленной ниже реализации метода get я возвращаю -1 в настоящее время в случае промаха.

Кроме того, в практическом рабочем коде кеша LRU, кеш содержит номера страниц или фактические значения, хранящиеся на этих номерах страниц? T

Пожалуйста, помогите мне прояснить этот аспект. Благодарю.

import java.util.HashMap;


public class LRU {

private static class Node {

    Node previous;
    Node next;
    int key;
    int value;

    public Node(int key, int value) {
        this.key = key;
        this.value = value;
    }
}

Node head = null;
Node tail = null;

HashMap<Integer, Node> hmap = new HashMap<>();

public int get(int key) {
    if (hmap.containsKey(key)) {
        Node n = hmap.get(key);
        remove(n);
        moveToFront(n);
        return n.value;
    }
    return -1;
}

public void remove(Node n) {
    // if n is head
    if (n.previous == null) {
        head = head.next;
    } else {
        n.previous.next = n.next;
    }

    //if n is tail
    if (n.next == null) {
        tail = n.previous;
    } else {
        n.next.previous = n.previous;

    }
}

public void moveToFront(Node n) {
    if(n==head)
        return;
    if(n.next==null)
    {
        n.previous.next=n.next;
        tail = n.previous;                    
        n.previous = null;
        n.next = head;
        head = n;
    }
    else {
        n.previous.next=n.next;
        n.next.previous=n.previous;
    }
}

public void set(int key, int value) {

   }
}

Answer 1

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

LRU (наименее недавно использовавшийся) - это одна из возможных политик для выбора пары, которая будет выселена, а не единственная. Кэш данных процессора является примером кеша, реализованного аппаратно, где ключ получается из адреса (обычно учитывающего только определенное количество старших значащих бит), а значение представляет собой часть памяти, содержащую такой адрес. В этом случае строка кэша содержит копию данных, находящихся в памяти. Другим примером является то, что в ОС, поддерживающей виртуальную память, подкачка ОС реализована как комбинация HW (MMU) и программного обеспечения в ядре ОС. В этом примере, ближе к тому, что вы описываете, значением пары является физический адрес страницы памяти, на которой размещена виртуальная страница.

Поэтому, когда вы спрашиваете "Кроме того, в практическом рабочем коде кеша LRU, кеш содержит номера страниц или фактические значения, хранящиеся под этими номерами страниц? T", ответ может зависеть от того, о каком кеше мы говорим. В вашем случае неясно, чем поддерживается кеш. Я предполагаю, что это смещение в каком-то файле. В этом случае я ожидаю, что ваше значение будет байтовым массивом или строкой, представляющей часть файла. Доступ к смещению x в файле будет сопоставлен с ключом = offset/PAGE_SIZE; если ключ отсутствует в таблице, и если таблица заполнена, то последний узел может быть "переработан" с настройкой замены существующего ключа и чтением содержимого файла со смещением (ключ, ключ + PAGE_SIZE-1) в байтовом буфере и, наконец, перемещая страницу как первую.