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

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

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

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

 ____
O____O  size 4

 ________
O________O  size 8

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

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


operating-system virtual-memory page-fault
person devoured elysium    schedule 26.01.2011    source источник
comment
Не уверен, что именно вы здесь ищете — на странице WP есть фактический пример: en. wikipedia.org/wiki/Belady's_anomaly   -  person Ken    schedule 26.01.2011
comment
Вы читали статью в Википедии? Это называется аномалией, потому что противоречит интуиции большинства людей. :)   -  person Fred Nurk    schedule 26.01.2011
comment
В этом конкретном случае наличие большего количества фреймов страниц заставило алгоритм дольше хранить страницы, которые в конечном итоге используются реже позже, и они не удаляются из FIFO достаточно быстро, чтобы освободить место для страниц, которые на самом деле в конечном итоге нужны. . Но я не знаю, можно ли из этого извлечь какую-то общую интуицию. Вот только что может случиться.   -  person Ken    schedule 26.01.2011
comment
В этом конкретном случае наличие большего количества фреймов страниц заставляло алгоритм дольше удерживать страницы, которые в конечном итоге использовались реже позже. Я не понимаю, как это может иметь какое-либо значение. Почему лучше вообще не иметь их в памяти (что происходит, когда у вас труба меньшего размера)   -  person devoured elysium    schedule 26.01.2011
comment
devoured: В этом случае, конечно, было бы лучше, но FIFO не может предсказать будущее. Вы работали с примером в википедии?   -  person Ken    schedule 27.01.2011

Ответы (6)


arrow_upward
35
arrow_downward

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

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

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

person Olhovsky    schedule 26.01.2011
comment
но когда к 3 обращались во второй раз, то во втором случае он был в кеше, а в первом - нет - person Utkarsh Srivastav; 20.04.2012
comment
не могли бы вы объяснить пример? эти цифры в примере не имеют для меня никакого смысла. Не в состоянии увидеть закономерности, понять их смысл :( - person Mahesha999; 30.01.2016
comment
хорошо понял... благодаря этой лекции...youtube FTW :) - person Mahesha999; 30.01.2016
comment
Может ли это происходить в алгоритмах, отличных от FIFO? - person User; 25.04.2016
comment
@Olhovsky, внизу; Разве они не должны быть вынесены наверх при доступе? - person Pacerier; 23.10.2019

arrow_upward
8
arrow_downward

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

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

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

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

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

person Tim Lovell-Smith    schedule 25.03.2015
comment
Это происходит только в алгоритме FIFO? - person User; 25.04.2016
comment
А как насчет алгоритма случайной замены страницы? Страдает ли он аномалией Белади? - person sameerkn; 16.02.2017
comment
@sameerkn Я бы сказал, что нет. При случайной замене страниц поведение является случайным каждый раз, когда независимо от шаблона доступа к памяти. И то, как часто он дает сбои, также является случайной величиной. Добавление дополнительного места ожидается, что в среднем не приведет к большему количеству сбоев страниц... - person Tim Lovell-Smith; 18.02.2017
comment
Но по крайней мере один раз, если алгоритм RPR имитирует аномалию Белади, тогда говорят, что алгоритм страдает от аномалии. FIFO не всегда страдает от аномалий. Подумайте, что, если алгоритм RPR имитирует алгоритм FIFO? - person sameerkn; 20.02.2017

arrow_upward
2
arrow_downward

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

person Surajit    schedule 06.04.2017

arrow_upward
1
arrow_downward

Я не мог понять аномалию belady даже после прочтения статьи в Википедии и принятия ответа. После написания трассировки я вроде понял. Здесь я хотел бы поделиться своим пониманием.

Ключи к пониманию аномалии белади.

  • В отличие от LRU, FIFO просто вытесняет самые старые элементы независимо от частоты. Таким образом, пребывание в FIFO дольше означает стать жертвой выселения.

Отсюда я называю очередь FIFO с 3 и 4 страницами FIFO3 и FIFO4.

Чтобы понять пример из Википедии, я разделил его на 2 части. Когда FIFO3 догоняет FIFO4 и когда FIFO3 догоняет FIFO4.

Как FIFO3 догоняет FIFO4 на 9-м месте

введите здесь описание изображения

Посмотрите на 3 в обоих FIFO. В FIFO3 3 вытесняется 4-м и возвращается 5-м. Значит, он все еще был там на 8-м, и произошло попадание в кеш. В FIFO4 3 является HIT на 5-м, но это попадание в кеш заставило 3 оставаться дольше и вытеснено на 7-м, прямо перед следующими 3 на 8-м.

2 совпадает с 3. Второй 2 (6-й) — ПРОМАХ в FIFO3 и ПОПАДАНИЕ в FIFO4, а третий 2 (9-й) — ПОПАДАНИЕ в FIFO3 и ПРОМАХ в FIFO4. Это может помочь думать так. В FIFO3 номер 3 был обновлен 5-го числа, поэтому оставался дольше до 8-го числа. В FIFO4 3 был старым и был выселен 7-го числа, как раз перед тем, как появятся следующие 3.

Как FIFO3 превосходит FIFO4

введите здесь описание изображения

Поскольку есть 2 промаха кеша на 8, 9-й для FIFO4, 4 помещается вниз и вытесняется 11-м в FIFO4. FIFO3 по-прежнему сохраняет 4 на 12-м, потому что есть кэш-попадание на 8, 9-м, поэтому 4 не было перемещено вниз. Я думаю, именно поэтому в статье Википедии говорится: Пенни Мудрая, Фунт Глупая.

Заключение

FIFO — это простой и наивный алгоритм, не учитывающий частоту. Вы можете лучше понять это, применив LRU (наименее недавно использовавшиеся) к примеру из Википедии. В LRU 4 лучше, чем 3.

person ohkts11    schedule 02.11.2020

arrow_upward
-2
arrow_downward

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

person Rubel    schedule 30.08.2018

arrow_upward
-3
arrow_downward

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

person Pranov    schedule 20.05.2013
comment
Это происходит только в FIFO? - person User; 25.04.2016