Телекоммуникационный портал GateWay

Раскраска страниц является оптимизацией производительности, предназначенной для обеспечения того, что доступ к смежным страницам в виртуальной памяти наилучшим образом использует кеш с физической адресацией. В архитектуре Intel используется кеш с физической адресацией, который обозначают кешем L1. Производительность системы тесно связана с процентным соотношением ссылок памяти, которые могут быть обслужены кешем L1, поскольку кеш L1 работает на частоте процессора. Промах в кеше L1 требует нескольких циклов задержки процессора в ожидании данных из кеша L2 или десятков циклов ожидания динамической RAM, в которой хранятся данные основной памяти.

Процесс в FreeBSD работает с пространством виртуальной памяти, не с пространством физической памяти. Физические страницы, лежащие в основе виртуального адресного пространства, редко бывают смежными. В худшем случае две последовательные виртуальные страницы могли бы быть сохранены в двух физических страницах, относящихся к одной и той же ячейке в кеше L1. Рассмотрим процесс, работающий на процессоре с 1 Мбайт физического кеша. Если процесс отобразил свою первую виртуальную страницу на физическую страницу 1 Мбайт, а свою вторую виртуальную страницу отобразил на физическую страницу 2 Мбайт, несмотря на сохранение локальности ссылки между двумя его смежными виртуальными страницами, процесс ненамеренно вызывает промахи в кеше L1. Эффект несколько смягчается многоканальными наборно-ассоциативными кешами, но проблема по-прежнему сохраняется.

Роль алгоритма раскраски страниц в том, чтобы гарантировать, что смежные страницы в виртуальной памяти будут смежными с точки зрения кеша. Вместо назначения виртуальным адресам случайных физических страниц, раскраска страниц назначает виртуальным адресам смежные в кеше физические страницы. Две физические страницы являются смежными в кеше, если они попадают в последовательные страницы в кеше. Эти страницы в физической памяти могут быть далеко друг от друга. На рис. ниже показан образец назначения страниц процессу. На рис. ниже кеш содержит 4 страницы, и страница 10 физической памяти назначена странице 0 виртуальной памяти процесса. Страница физической памяти 10 имеет цвет 2 кеша (остаток деления 10 на 4 равен 2). Код раскраски страниц назначил страницу 15 физической страницы странице 1 виртуальной памяти процесса, поскольку он имеет цвет 3. Код раскраски страницы пытается избежать назначения страниц 6 или 14, поскольку они отображаются на ту же самую область памяти кеша, что и страница 10, и привели бы к неоптимальному квитированию, тогда как любая из страниц 7, 11 или 15 является оптимальной, поскольку каждая из нихследуют за памятью кеша, использованной для страницы 10.

Раскраска страниц реализуется созданием стольких свободных списков, сколько страниц в кеше. Каждой странице в кеше назначается цвет. Машина с 1 Мбайт кеша и 4-килобайтными страницами имела бы 256 страниц кеша - следовательно, 256 цветов. При запуске системы каждая vm_page записывает свой цвет в кеше L1. Когда страница освобождается, она помещается в свободный список, соответствующий ее цвету. При создании объекта ему назначается начальный цвет. Чтобы гарантировать, что запрос цветов достаточно сбалансирован, начальный цвет, который будет использован для следующего объекта, корректируется наименьшим из размера объекта и трети размера кеша L1. Когда в объекте возникает отказ страницы, его предпочтительный цвет для новой страницы вычисляется путем добавления логического номера страницы объекта, вызвавшей отказ, к начальному цвету объекта по модулю числа цветов. Страница берется из свободного списка этого цвета, если он доступен. В противном случае проверяются цвета, отстоящие дальше всего от запрошенного цвета, до тех пор, пока не будет найдена доступная страница. Самая далеко отстоящая страница используется, потому что алгоритм хочет минимизировать возможность коллизий кеша с соседней страницей в виртуальном адресном пространстве. Например, если бы использовалась страница со следующим цветом, она скорее всего конфликтовала бы со страницей, которую алгоритм выбрал для следующего большего виртуального адреса.

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