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

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 увеличение размера кэша изменяет порядок удаления элементов.Что в некоторых случаях может увеличить частоту отказов.

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

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

Answer 2

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

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

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

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

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

Answer 3

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

Answer 4

Вкратце об аномалии Беледи мы можем сказать: «Добавление большего количества кадров может привести к большему количеству ошибок на странице».

Answer 5

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