Мне нужна последовательность чисел, когда FIFO побеждает LRU. Скажем, меньше 15 номеров и количество страниц 3. Я хочу, чтобы FIFO получал меньше ошибок страниц, чем LRU. Является ли это возможным?
Когда FIFO выигрывает у алгоритма замены LRU?
comment
что ты пробовал?
- person Christophe Roussy schedule 04.02.2021
comment
LRU похож на FIFO, за исключением случаев, когда на что-то в очереди ссылаются, он перемещается в конец очереди. Итак, вам нужно найти последовательность, в которой, переместив один элемент (A) в конец очереди, LRU выбрал выселение (B), тогда как FIFO выселил (C), затем (B) появился в последовательности до (A), поэтому LRU пришлось повторно получить (B), а FIFO - нет.
- person mevets schedule 04.02.2021
Ответы (2)
Для трехстраничного кеша достаточно использовать последовательность 1, 2, 3, 1, 4, 2. Эволюция тайников:
FIFO LRU
1 1
12 12
123 123 [three misses for both as the cache fills]
123 231 [LRU moves 1 to the back]
234 314
234 142 [LRU but not FIFO misses on 2]
person
David Eisenstat
schedule
04.02.2021
FIFO - это простая реализация кеширования, которая не обеспечивает оптимальных ошибок страниц, хотя ее легко реализовать.
Мы можем получить лучшую производительность при использовании структуры данных на основе CLOCK (вариант FIFO), которая дает меньше ошибок страниц по сравнению с LRU. Есть несколько вариантов ЧАСОВ.
На практике LRU является оптимальной реализацией кеширования, и различные ОС, базы данных используют вариант LRU, такой как ARC, LIRS ...
Для получения дополнительной информации см. Вики для различных стратегий кеширования.
https://en.wikipedia.org/wiki/Cache_replacement_policies https://en.wikipedia.org/wiki/Page_replacement_algorithm
person
srao
schedule
04.02.2021
