Не существует единого алгоритма кэширования, который всегда будет работать хорошо, потому что для этого требуются совершенные знания о будущем. (И если вы знаете, где это взять ...) Доминирование LRU в дизайне кеша ВМ является результатом долгой истории измерения поведения системы. Учитывая реальную рабочую нагрузку, LRU работает довольно хорошо большую часть времени. Однако не так сложно создать справочную строку, для которой FIFO будет иметь более высокую производительность по сравнению с LRU.
Рассмотрим линейную развертку через большое адресное пространство, намного превышающее доступную реальную память с возможностью постраничного вывода. LRU основан на предположении, что «то, к чему вы недавно прикасались, вы, скорее всего, коснетесь снова», но линейная развертка полностью нарушает это предположение. Вот почему некоторые операционные системы позволяют программам сообщать ядру об их эталонном поведении - одним из примеров является сборка мусора «разметка и очистка», типичная для классических интерпретаторов LISP. (И основной драйвер для работы на более современных GC, таких как «поколения».)
Другим примером является таблица символов в определенном античном макропроцессоре (STAGE2). Двоичное дерево ищется в корне для каждого символа, а оценка строки выполняется в стеке. Оказалось, что уменьшение доступных фреймов страницы путем «разводки» корневой страницы дерева символов и нижней страницы стека значительно улучшило частоту отказов страниц. Кэш был крошечным и сильно взбалтывался, всегда выталкивая две наиболее часто упоминаемые страницы, потому что кэш был меньше, чем расстояние между ссылками до этих страниц. Таким образом, маленький кэш работал лучше, но ТОЛЬКО потому, что эти два фрейма страницы, украденные из кеша, использовались с умом.
Суть всего этого в том, что LRU является стандартным ответом, потому что он обычно довольно хорош для реальных рабочих нагрузок в системах, которые не перегружены ужасно (ВМ много раз превышает реальную доступную память), и это подтверждается годами тщательных измерений. , Тем не мение,
Вы, конечно, можете найти случаи, когда альтернативное поведение будет превосходным. Вот почему измерение реальных систем важно.