Введение
Явление в компьютерной памяти
>[{}\atop\text{Время}] Запросы страниц 3 2 1 0 3 2 4 3 2 1 0 4 Самая новая страница 3 2 1 0 3 2 4 4 4 1 0 0 3 2 1 0 3 2 2 2 4 1 1 Самая старая страница 3 2 1 0 3 3 3 2 4 4 >[{}\atop\text{Время}] Запросы страниц 3 2 1 0 3 2 4 3 2 1 0 4 Самая новая страница 3 2 1 0 0 0 4 3 2 1 0 4 3 2 1 1 1 0 4 3 2 1 0 3 2 2 2 1 0 4 3 2 1 Самая старая страница 3 3 3 2 1 0 4 3 2 Пример аномалии Белади. При использовании трех фреймов страниц возникает девять промахов страниц. Увеличение до четырех фреймов страниц приводит к возникновению десяти промахов страниц. Промахи страниц выделены красным цветом. Это можно рассматривать как результат поведения "скупой платит дважды". В компьютерной памяти аномалия Белади – это явление, при котором увеличение количества фреймов страниц приводит к увеличению количества промахов страниц при определенных шаблонах доступа к памяти. Это явление часто встречается при использовании алгоритма замены страниц FIFO (первым пришел – первым ушел). В FIFO количество промахов страниц может как увеличиваться, так и не увеличиваться при увеличении количества фреймов страниц, но в оптимальных и основанных на стеке алгоритмах, таких как LRU, с увеличением количества фреймов страниц количество промахов страниц уменьшается. Ласло Белади продемонстрировал это в 1969 году.
>[{}\atop\text{Time}] Page requests 3 2 1 0 3 2 4 3 2 1 0 4 Newest page 3 2 1 0 3 2 4 4 4 1 0 0 3 2 1 0 3 2 2 2 4 1 1 Oldest page 3 2 1 0 3 3 3 2 4 4 >[{}\atop\text{Time}] Page requests 3 2 1 0 3 2 4 3 2 1 0 4 Newest page 3 2 1 0 0 0 4 3 2 1 0 4 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 An example of Bélády's anomaly. Using three page frames, nine page faults occur. Increasing to four page frames causes ten page faults to occur. Page faults are in red. This can be thought of as a result of a "Penny Wise, Pound Foolish" behavior. In computer storage, Bélády's anomaly is the phenomenon in which increasing the number of page frames results in an increase in the number of page faults for certain memory access patterns. This phenomenon is commonly experienced when using the first in first out (FIFO) page replacement algorithm. In FIFO, the page fault may or may not increase as the page frames increase, but in optimal and stack based algorithms like LRU, as the page frames increase, the page fault decreases. László Bélády demonstrated this in 1969.
Предыстория
В стандартной организации памяти компьютера информация загружается блоками фиксированного размера. Каждый блок называется страницей. Оперативная память может содержать лишь ограниченное количество страниц одновременно. Для каждой страницы, которую можно загрузить, требуется фрейм (ячейка памяти). Происходит ошибка страницы (page fault), когда страница не найдена и, возможно, потребуется загрузка с диска в память. Если возникает ошибка страницы и все фреймы заняты, один из них необходимо освободить, чтобы освободить место для новой страницы. Простой алгоритм – FIFO (First-In, First-Out): удаляется страница, которая находилась во фреймах дольше всего. До демонстрации аномалии Белади считалось, что увеличение количества фреймов всегда приводит к тому же числу или меньшему количеству ошибок страниц.
Аномалия Белади безгранична.
Белади, Нельсон и Шедлер построили эталонные строки, для которых алгоритм FIFO замены страниц приводил почти к двукратному увеличению числа промахов страниц в большей памяти по сравнению с меньшей, и они выдвинули предположение, что 2 является общей верхней границей. В 2010 году Форнай и Ивани показали, что эта аномалия на самом деле не ограничена, и можно построить эталонную строку для любого произвольного соотношения промахов страниц.