Не могу понять аномалию Беди

Итак, Belady Anomaly заявляет, что при использовании политики замены страницы FIFO при добавлении большего пространства страницы мы будем иметь больше ошибок страницы.

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

Если мы думаем о очереди FIFO как о трубе, добавление большего пространства страницы походит на то, чтобы сделать канал больше:

 ____
O____O  size 4

 ________
O________O  size 8

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

Что не так с моими рассуждениями?

Ответ 1

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

Рассмотрим третий раз, когда в примере wikipedia запрашивается "3": http://en.wikipedia.org/wiki/Belady%27s_anomaly

Ошибки страниц отмечены знаком "f".

Page Requests   3    2    1    0    3    2    4    3    2    1    0    4
Newest Page     3f   2f   1f   0f   3f   2f   4f   4    4    1f   0f   0
                     3    2    1    0    3    2    2    2    4    1    1
Oldest Page               3    2    1    0    3    3    3    2    4    4

Page Requests   3    2    1    0    3    2    4    3    2    1    0    4
Newest Page     3f   2f   1f   0f   0    0    4f   3f   2f   1f   0f   4f
                     3    2    1    1    1    0    4    3    2    1    0
                          3    2    2    2    1    0    4    3    2    1
Oldest Page                    3    3    3    2    1    0    4    3    2

В первом примере (с меньшим количеством страниц) существует 9 ошибок страницы.

Во втором примере (с большим количеством страниц) есть 10 ошибок страницы.

При использовании FIFO увеличение размера кеша изменяет порядок удаления элементов. Который в некоторых случаях может увеличить частоту отказов.

Belady Anomaly ничего не говорит о общей тенденции к сбоям в отношении размера кеша. Таким образом, ваши рассуждения (о просмотре кеша как канала) в общем случае не ошибаются.

Вкратце: Belady Anomaly отмечает, что можно использовать тот факт, что больший размер кеша может привести к тому, что элементы в кеше будут подняты в очереди FIFO позже меньших размеров кеша, чтобы увеличить размер кэша большего размера в соответствии с конкретный (и, возможно, редкий) шаблон доступа.

Ответ 2

Это утверждение неверно, потому что оно слишком обобщено:

Belady Anomaly заявляет, что при использовании политики замены страницы FIFO при добавлении большего пространства страницы мы будем иметь больше ошибок страницы

Это исправленная версия:

"Belady Anomaly заявляет, что при использовании политики замены страницы FIFO при добавлении большего пространства на страницу некоторые шаблоны доступа к памяти фактически приводят к большему количеству ошибок страницы."

Другими словами... наблюдается ли аномалия, зависит от фактического шаблона доступа к памяти.

Ответ 3

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

Ответ 4

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