Аномалия Беладиса - Википедия - Béládys anomaly

Запросы страниц321032432104
Самая новая страница321032444100
  32103222411
Самая старая страница  3210333244
Запросы страниц321032432104
Самая новая страница321000432104
  32111043210
   3222104321
Самая старая страница   333210432
Пример аномалии Белади. При использовании трех страничных фреймов происходит девять страничных ошибок. Увеличение до четырех страничных фреймов приводит к возникновению десяти страничных ошибок. Ошибки страницы в красный. Это можно рассматривать как результат поведения «Пенни Мудрый, Фунт глупо».

В компьютерное хранилище, Аномалия Белади это явление, при котором увеличение количества страничных фреймов приводит к увеличению количества ошибки страницы для определенных шаблонов доступа к памяти. Это явление обычно наблюдается при использовании системы «первым пришел - первым обслужен» (ФИФО ) алгоритм замены страницы. В FIFO ошибка страницы может увеличиваться, а может и не увеличиваться по мере увеличения кадров страницы, но в оптимальных алгоритмах и алгоритмах на основе стека, таких как LRU, по мере увеличения кадров страницы ошибка страницы уменьшается.Ласло Белади продемонстрировал это в 1969 году.[1]

В общем компьютере управление памятью, информация загружается частями определенного размера. Каждый фрагмент называется страница. Основная память может одновременно хранить только ограниченное количество страниц. Это требует Рамка для каждой страницы, которую он может загрузить. А ошибка страницы возникает, когда страница не найдена и может потребоваться загрузить с диска в память.

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

Аномалия Белади безгранична

Белади, Нельсон и Шедлер построили ссылочные строки, для которых алгоритм замены страниц FIFO вызывал почти в два раза больше ошибок страниц в большей памяти, чем в меньшей, и они сформулировали гипотезу, что 2 является общей границей.

В 2010 году Форнаи и Иваньи показали, что аномалия на самом деле неограниченна и что можно построить ссылочную строку для любого произвольного коэффициента ошибок страницы.

Рекомендации

  1. ^ Кристофер Крюгель (3 декабря 2012 г.). «Операционные системы (курс CS170-08)» (PDF). cs.UCSB.edu. Архивировано из оригинал (PDF) 10 августа 2016 г.. Получено 13 июн 2016.

внешняя ссылка