Алгоритм подкачки наименее недавно использованных (LRU) всегда более эффективен, чем FIFO?

Я делаю проект, имитирующий замену страницы для моего курса по операционным системам. У меня есть симулятор, который запускает все три алгоритма на 1200 ссылках. Однако я получаю показатели ошибок страниц, когда алгоритм LRU получает равную или меньшую оценку, чем FIFO, только большую часть времени. Время от времени ввод будет работать, что LRU будет иметь немного более высокую частоту ошибок страниц, чем FIFO. Это неправильно?

Я использую счетчики для каждого номера страницы, которые увеличиваются каждый раунд для реализации LRU. Счетчик используемой страницы сбрасывается на 0. Когда я заменяю кадр, я использую свой кадр с максимальным значением счетчика. Я чувствую, что моя реализация должна быть правильной.


operating-system algorithm paging fifo lru
person Cory Gross    schedule 28.11.2012    source источник

Ответы (1)


arrow_upward
3
arrow_downward

Конечно, может случиться так, что LRU не оптимален, а FIFO может даже работать лучше.

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

Я думаю, что оптимальной стратегией будет сохранение в массиве ранних страниц, которые будут использоваться при каждом сканировании, а не недавно использованных страниц, которые могут не понадобиться снова в течение некоторого времени. Эта стратегия больше похожа на FIFO, чем на LRU.

person rici    schedule 29.11.2012