Может ли стратегия замены страниц FIFO превзойти LRU?

В качестве домашнего задания по операционным системам меня попросили сравнить количество ошибочных страниц, вызванных стратегиями замены страниц по принципу «первым поступил — первым обслужен» и «наименее недавно использованные» для заданной последовательности обращений к страницам. Вызывает недоумение тот факт, что FIFO вызвал меньше ошибок страниц, чем LRU. Возможно ли это, или я ошибся?


operating-system algorithm page-replacement
person Evan Kroske    schedule 05.03.2012    source источник
comment
Конечно, это возможно. Не существует единого алгоритма, который был бы лучшим в замене страниц. LRU превосходит FIFO в реальных условиях использования, но, безусловно, можно построить случай, в котором верно обратное.   -  person user703016    schedule 05.03.2012
comment
Предлагаемое расширение для собственного назидания: учитывая любые две стратегии замены страниц X и Y, докажите, что существует последовательность обращений, при которой X имеет меньше ошибок страниц, чем Y.   -  person Nemo    schedule 05.03.2012

Ответы (2)


arrow_upward
5
arrow_downward

Да, FIFO может победить LRU. Самый маленький пример, который я могу придумать,

Размер кэша: 2 страницы.

Схема доступа: A, B, A, C

После этого кэш LRU содержит «A, C», тогда как кэш FIFO содержит «B, C». На данный момент каждый из них промахнулся по 3 раза. Таким образом, если доступ к следующей странице — «B», то FIFO побеждает LRU. Если это «A», LRU превосходит FIFO. Если это что-то еще, они остаются связанными.

person Steve Jessop    schedule 05.03.2012
comment
Это должен быть наименьший возможный пример: конечно, пример cachesize=1 невозможен, так как LRU=FIFO, когда cachesize=1. И пример cachesize=2, totalnumaccesses=4 невозможен, так как такой пример должен включать вытеснение при 3-м доступе, но LRU и FIFO всегда вытесняют один и тот же элемент (если есть) при 3-м доступе, поэтому здесь не происходит различия. - person Don Hatch; 06.04.2016

arrow_upward
3
arrow_downward

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

person High Performance Mark    schedule 05.03.2012
comment
Теоретически это, очевидно, будет зависеть от заданной последовательности. И +1 за искривленное темное место, если подумать, очень хорошее предложение :D - person Gargi Srinivas; 05.03.2012