Аномалия Белади
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Пример аномалии Белади. При использовании трех фреймов страниц происходит девять ошибок страниц. Увеличение до четырех фреймов страниц приводит к десяти ошибкам страниц. Ошибки страниц выделены красным цветом . Это можно рассматривать как результат поведения «Penny Wise, Pound Foolish». | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
![{\displaystyle {\ce {->[{} \atop {\text{Время}}]}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5bbe595e28fc03e4a78bd8a926bc0e17cb542c5f)
В компьютерном хранилище аномалия Белади — это явление, при котором увеличение числа фреймов страниц приводит к увеличению числа ошибок страниц для определенных шаблонов доступа к памяти. Это явление обычно наблюдается при использовании алгоритма замены страниц «первым пришел — первым вышел» ( FIFO ) . В FIFO ошибка страницы может увеличиваться или не увеличиваться по мере увеличения фреймов страниц, но в оптимальных и стековых алгоритмах, таких как LRU , по мере увеличения фреймов страниц ошибка страницы уменьшается. Ласло Белади продемонстрировал это в 1969 году. [1]
Фон
В обычном управлении памятью компьютера информация загружается порциями определенного размера. Каждая порция называется страницей . Основная память может одновременно хранить только ограниченное количество страниц. Для каждой страницы, которую она может загрузить, требуется фрейм . Ошибка страницы возникает, когда страница не найдена и может потребоваться ее загрузка с диска в память.
Когда происходит ошибка страницы, а все кадры используются, один из них должен быть очищен, чтобы освободить место для новой страницы. Простой алгоритм — FIFO: та страница, которая дольше всего находилась в кадрах, очищается. Пока не была продемонстрирована аномалия Белади, считалось, что увеличение числа кадров страниц всегда будет приводить к тому же количеству или меньшему количеству ошибок страниц.
Аномалия Белади не имеет границ
Белади, Нельсон и Шедлер построили справочные строки, для которых алгоритм замены страниц FIFO приводил почти в два раза больше ошибок страниц в большей памяти, чем в меньшей, и сформулировали гипотезу, что 2 является общей границей. [ необходима ссылка ]
В 2010 году Форнаи и Ивани показали, что аномалия на самом деле неограниченна и что можно построить ссылочную строку для любого произвольного коэффициента ошибок страниц. [ необходима цитата ]
Ссылки
- ^ Кристофер Крюгель (3 декабря 2012 г.). "Операционные системы (курс CS170-08)" (PDF) . cs.UCSB.edu . Архивировано из оригинала (PDF) 10 августа 2016 г. . Получено 13 июня 2016 г. .
Внешние ссылки
- Статья Белади 1969 года: Аномалия в пространственно-временных характеристиках некоторых программ, работающих в пейджинговой машине
- Аномалия FIFO не ограничена. arXiv :1003.1336
- Решения интернет-конкурса по решению проблем – Задача L – Библиотекарь
