9 Дополнительный сеанс вопросов и ответов от Аллена Вриггса (Allen Briggs) <briggs@ninthwonder.com>

FreeBSD использует в области подкачки механизм чередования, с индексом по умолчанию, равным четырем. Это означает, что FreeBSD резервирует пространство для четырех областей подкачки, даже если у вас имеется всего лишь одна, две или три области. Так как в области подкачки имеется чередование, то линейное адресное пространство, представляющее ``четыре области подкачки'', будет фрагментироваться, если у вас нет на самом деле четырех областей подкачки. Например, если у вас две области A и B, то представление адресного пространства для этой области подкачки во FreeBSD будет организовано с чередованием блоков из 16 страниц:

A B C D A B C D A B C D A B C D

FreeBSD 3.X использует ``последовательный список свободных областей'' для управления свободными областями в разделе подкачки. Идея состоит в том, что большие последовательные блоки свободного пространства могут быть представлены при помощи узла односвязного списка (kern/subr_rlist.c). Но из-за фрагментации последовательный список сам становится фрагментированным. В примере выше полностью неиспользуемое пространство в A и B будет показано как ``свободное'', а C и D как ``полностью занятое''. Каждой последовательности A-B требуется для учета узел списка, потому что C и D являются дырами, так что узел списка не может быть связан со следующей последовательностью A-B.

Почему мы организуем чередование в области подкачки вместо того, чтобы просто объединить области подкачки в одно целое и придумать что-то более умное? Потому что гораздо легче выделять последовательные полосы адресного пространства и получать в результате автоматическое чередование между несколькими дисками, чем пытаться выдумывать сложности в другом месте.

Фрагментация вызывает другие проблемы. Являясь последовательным списком в 3.X и имея такое огромную фрагментацию, выделение и освобождение в области подкачки становится алгоритмом сложности O(N), а не O(1). Вместе с другими факторами (частое обращение к области подкачки) вы получаете сложность уровней O(N^2) и O(N^3), что плохо. В системе 3.X также может потребоваться выделение KVM во время работы с областью подкачки для создания нового узла списка, что в условии нехватки памяти может привести к блокировке, если система попытается сбросить страницы в область подкачки.

В 4.X мы не используем последовательный список. Вместо этого мы используем базисное дерево и битовые карты блоков области подкачки, а не ограниченный список узлов. Мы принимаем предварительное выделение всех битовых карт, требуемых для всей области подкачки, но при этом тратится меньше памяти, потому что мы используем битовые карты (один бит на блок), а не связанный список узлов. Использование базисного дерева вместо последовательного списка дает нам производительность O(1) вне зависимости от фрагментации дерева.

Да, это запутывает. Связь заключается в ``желаемом'' и ``действительном''. Мы желаем разделить страницы, но реальность такова, что пока у нас нет проблем с памятью, нам это на самом деле не нужно.

Это означает, что FreeBSD не будет очень сильно стараться над отделением грязных страниц (неактивная очередь) от чистых страниц (очередь кэша), когда система не находится под нагрузкой, и не будет деактивировать страницы (активная очередь -> неактивная очередь), когда система не нагружена, даже если они не используются.

Ошибка COW может быть ошибкой при заполнении нулями или данных программы. Механизм в любом случае один и тот же, потому что хранилище данных программы уже в кэше. Я на самом деле не рад ни тому, ни другому. FreeBSD не выполняет предварительное COW данных программы и заполнение нулями, но она выполняет предварительно отображение страниц, которые имеются в ее кэше.

vm_page представляет собой пару (object,index#). pv_entry является записью из аппаратной таблицы страниц (pte). Если у вас имеется пять процессов, совместно использующих одну и ту же физическую страницу, и в трех таблицах страниц этих процессов на самом деле отображается страница, то страница будет представляться одной структурой vm_page и тремя структурами pv_entry.

Структуры pv_entry представляют страницы, отображаемые MMU (одна структура pv_entry соответствует одной pte). Это означает, что, когда нам нужно убрать все аппаратные ссылки на vm_page (для того, чтобы повторно использовать страницу для чего-то еще, выгрузить ее, очистить, пометить как грязную и так далее), мы можем просто просмотреть связный список структур pv_entry, связанных с этой vm_page, для того, чтобы удалить или изменить pte из их таблиц страниц.

В Linux нет такого связного списка. Для того, чтобы удалить все отображения аппаратной таблицы страниц для vm_page, linux должен пройти по индексу каждого объекта VM, который может отображать страницу. К примеру, если у вас имеется 50 процессов, которые все отображают ту же самую динамическую библиотеку и хотите избавиться от страницы X в этой библиотеке, то вам нужно пройтись по индексу всей таблицы страниц для каждого из этих 50 процессов, даже если только 10 из них на самом деле отображают страницу. Так что Linux использует простоту подхода за счет производительности. Многие алгоритмы VM, которые имеют сложность O(1) или (N малое) во FreeBSD, в Linux приобретают сложность O(N), O(N^2) или хуже. Так как pte, представляющий конкретную страницу в объекте, скорее всего, будет с тем же смещением во всех таблицах страниц, в которых они отображаются, то уменьшение количества обращений в таблицы страниц по тому же самому смещению часто позволяет избежать разрастания кэша L1 для этого смещения, что приводит к улучшению производительности.

Во FreeBSD введены дополнительные сложности (схема с pv_entry) для увеличения производительности (уменьшая количество обращений только к тем pte, которые нужно модифицировать).

Но во FreeBSD имеется проблема масштабирования, которой нет в Linux, потому что имеется ограниченное число структур pv_entry, и это приводит к возникновению проблем при большом объеме совместно используемых данных. В этом случае у вас может возникнуть нехватка структур pv_entry, даже если свободной памяти хватает. Это может быть достаточно легко исправлено увеличением количества структур pv_entry при настройке, но на самом деле нам нужно найти лучший способ делать это.

Что касается использования памяти под таблицу страниц против схемы с pv_entry: Linux использует ``постоянные'' таблицы страниц, которые не сбрасываются, но ему не нужны pv_entry для каждого потенциально отображаемого pte. FreeBSD использует ``сбрасываемые'' таблицы страниц, но для каждого реально отображаемого pte добавляется структура pv_entry. Я думаю, что использование памяти будет примерно одинакова, тем более что у FreeBSD есть алгоритмическое преимущество, заключающееся в способности сбрасывать таблицы страниц с очень малыми накладными расходами.

Знаете ли вы, как работает аппаратный кэш памяти L1? Объясняю: Представьте машину с 16МБ основной памяти и только со 128К памяти кэша L1. В общем, этот кэш работает так, что каждый блок по 128К основной памяти использует те же самые 128К кэша. Если вы обращаетесь к основной памяти по смещению 0, а затем к основной памяти по смещению 128К, вы перезаписываете данные кэша, прочтенные по смещению 0!

Я очень сильно все упрощаю. То, что я только что описал, называется ``напрямую отображаемым'' аппаратным кэшем памяти. Большинство современных кэшей являются так называемыми 2-сторонними множественными ассоциативными или 4-сторонними множественными ассоциативными кэшами. Множественная ассоциативность позволяет вам обращаться к вплоть до N различным областям памяти, которые используют одну и ту же память кэша без уничтожения ранее помещенных в кэш данных. Но только N.

Так что если у меня имеется 4-сторонний ассоциативный кэш, я могу обратиться к памяти по смещению 0, смещению 128К, 256К и смещению 384K, затем снова обратиться к памяти по смещению 0 и получу ее из кэша L1. Однако, если после этого я обращусь к памяти по смещению 512К, один из ранее помещенных в кэш объектов данных будет из кэша удален.

Это чрезвычайно важно... для большинства обращений к памяти процессора чрезвычайно важно, чтобы данные находились в кэше L1, так как кэш L1 работает на тактовой частоте работы процессора. В случае, если данных в кэше L1 не обнаруживается, и они ищутся в кэше L2 или в основной памяти, процессор будет простаивать, или, скорее, сидеть, сложив ручки, в ожидании окончания чтения из основной памяти, хотя за это время можно было выполнить сотни операций. Основная память (динамическое ОЗУ, которое установлено в компьютере) работает по сравнению со скоростью работы ядра современных процессоров медленно.

Хорошо, а теперь рассмотрим подгонку страниц: Все современные кэши памяти являются так называемыми физическими кэшами. Они кэшируют адреса физической памяти, а не виртуальной. Это позволяет кэшу не принимать во внимание переключение контекстов процессов, что очень важно.

Но в мире UNIX® вы работаете с виртуальными адресными пространствами, а не с физическими. Любая программа, вами написанная, имеет дело с виртуальным адресным пространством, ей предоставленным. Реальные физические страницы, соответствующие виртуальному адресному пространству, не обязательно расположены физически последовательно! На самом деле у вас могут оказаться две страницы, которые в адресном пространстве процессов являются граничащими, но располагающимися по смещению 0 и по смещению 128К в физической памяти.

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

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

Заметьте, что я сказал ``примерно'' подходящие, а не просто ``последовательные''. С точки зрения напрямую отображаемого кэша в 128К, физический адрес 0 одинаков с физическим адресом 128К. Так что две граничащие страницы в вашем виртуальном адресном пространстве могут располагаться по смещению 128К и 132К физической памяти, но могут легко находиться по смещению 128К и по смещению 4К физической памяти, и иметь те же самые характеристики работы кэша. Так что при подгонке не нужно назначать в действительности последовательные страницы физической памяти последовательным страницам виртуальной памяти, достаточно просто добиться расположения страниц по соседству друг с другом с точки зрения работы кэша.