В компьютерной памяти , аномалия Bélády в этом явлении , при котором увеличении числа страниц кадров приводят к увеличению числа ошибок страниц для определенных шаблонов доступа к памяти. Это явление обычно наблюдается при использовании алгоритма замены страниц по принципу « первым пришел - первым обслужен» ( FIFO ) . В FIFO ошибка страницы может увеличиваться или не увеличиваться по мере увеличения кадров страницы, но в оптимальных алгоритмах и алгоритмах на основе стека, таких как LRU, по мере увеличения кадров страницы ошибка страницы уменьшается. Ласло Белади продемонстрировал это в 1969 году [1].
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Пример аномалии Белади. При использовании трех страничных фреймов происходит девять страничных ошибок. Увеличение до четырех страничных фреймов приводит к возникновению десяти страничных ошибок. Ошибки страницы отображаются красным цветом . Это можно рассматривать как результат поведения «Пенни Мудрый, Глупый фунт». |
При обычном управлении памятью компьютера информация загружается частями определенного размера. Каждый фрагмент называется страницей . Основная память может одновременно хранить только ограниченное количество страниц. Для каждой загружаемой страницы требуется фрейм . Ошибка страницы возникает, когда страница не найдена, и может потребоваться загрузка с диска в память.
Когда возникает ошибка страницы и все фреймы используются, необходимо очистить один, чтобы освободить место для новой страницы. Простой алгоритм - это FIFO: какая бы страница ни находилась в кадрах дольше всех, она очищается. До тех пор, пока аномалия Белади не была продемонстрирована, считалось, что увеличение количества страничных фреймов всегда будет приводить к тому же количеству или меньшему количеству ошибок страницы.
Аномалия Белади безгранична
Белади, Нельсон и Шедлер построили ссылочные строки, для которых алгоритм замены страниц FIFO вызывал почти в два раза больше ошибок страниц в большей памяти, чем в меньшей, и они сформулировали гипотезу, что 2 является общей границей.
В 2010 году Форнаи и Иваньи показали, что аномалия на самом деле неограниченна и что можно построить ссылочную строку для любого произвольного коэффициента ошибок страницы.
Рекомендации
- ^ Кристофер Kruegel (3 декабря 2012). «Операционные системы (курс CS170-08)» (PDF) . cs.UCSB.edu . Архивировано из оригинального (PDF) 10 августа 2016 года . Проверено 13 июня +2016 .
Внешние ссылки
- Статья Белади 1969 года: аномалия в пространственно-временных характеристиках некоторых программ, выполняемых в пейджинговой машине.
- Аномалия FIFO не ограничена. arXiv : 1003.1336
- Решения конкурса по решению проблем в Интернете - Задача L - Библиотекарь