Почему LRU не страдает аномалией Белады?

Question

У меня есть вопрос об алгоритмах замены страниц. FIFO страдает от Аномалии Белади , но LRU нет. Кто-нибудь знает, почему LRU не страдает? Я искал причину в интернете, но не повезло.

Answer 1

Поскольку LRU является алгоритмом стекирования, и использование k кадров всегда будет подмножеством k + n кадров для LRU.Таким образом, любые сбои страниц, которые могут возникнуть для k + n кадров, также будут иметь место для k кадров, что, в свою очередь, означает, что LRU не страдает аномалией Белади.

Answer 2

Поскольку FIFO предполагает, что сам факт того, что страница долгое время занимала память, заменить ее безопаснее, хотя в действительности это не так.Скорее, в случае сбоя FIFO статистически, если страница вызывается часто, она будет вызываться чаще, чем другая, недавно вызванная страница.Другими словами, частота гораздо лучше определяет загрузку страницы, чем возраст.

Answer 3

Аналогично ответу Каспара, однако я нашел объяснение из своего учебника (слегка отредактированное) более ясным.

[ LRU принадлежит ] к классуалгоритмы замены страниц, называемые алгоритмами стека, [, которые ] никогда не могут проявлять аномалию Белади.

Алгоритм стека - это алгоритм, для которого можно показать, что набор страниц в памяти дляN кадров всегда является подмножеством набора страниц, которые будут в памяти с N + 1 кадрами.[ Поэтому дополнительный фрейм никогда не вызовет дополнительную ошибку страницы. ]

Для замены LRU набор страниц в памяти будет N последними ссылочными страницами.Если количество кадров будет увеличено, эти N страниц будут по-прежнему ссылаться последними и, следовательно, будут в памяти.

Silberschatz, A., Galvin, PB, & Gagne, G. (2014).Концепции операционной системы (9-е изд.).Сингапур: Вайли.