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

Question

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

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

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

 ____
O____O  size 4

 ________
O________O  size 8

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

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

Answer 1

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

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

Недостатки страниц отмечены "F".

1:

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

2:

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 увеличение размера кэша меняет порядок, в котором элементы удаляются. Который в немного Случаи могут увеличить скорость неисправности.

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

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

Answer 2

Это утверждение неверно, потому что оно чрезмерный:

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

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

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

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

Answer 3

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

Answer 4

Короче говоря, об аномалии Белди мы можем сказать «добавление большего количества кадров может вызвать больше недостатков страниц».

Answer 5

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