Аномалия Беладиса - Википедия - Béládys anomaly
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Пример аномалии Белади. При использовании трех страничных фреймов происходит девять страничных ошибок. Увеличение до четырех страничных фреймов приводит к возникновению десяти страничных ошибок. Ошибки страницы в красный. Это можно рассматривать как результат поведения «Пенни Мудрый, Фунт глупо». |
В компьютерное хранилище, Аномалия Белади это явление, при котором увеличение количества страничных фреймов приводит к увеличению количества ошибки страницы для определенных шаблонов доступа к памяти. Это явление обычно наблюдается при использовании системы «первым пришел - первым обслужен» (ФИФО ) алгоритм замены страницы. В 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 - Библиотекарь