Элементы архитектуры системы виртуальной памяти во FreeBSD

1. Введение

Перед тем, как перейти непосредственно к существующей архитектуре, потратим немного времени на рассмотрение вопроса о необходимости поддержки и модернизации любого длительно живущего кода. В мире программирования алгоритмы становятся более важными, чем код, и именно из-за академических корней BSD изначально большое внимание уделялось проработке алгоритмов. Внимание, уделенное архитектуре, в общем отражается на ясности и гибкости кода, который может быть достаточно легко изменен, расширен или с течением времени заменен. Хотя некоторые считают BSD ''старой'' операционной системой, те их нас, кто работает над ней, видят ее скорее системой со ''зрелым'' кодом с различными компонентами, которые были заменены, расширены или изменены современным кодом. Он развивается, и FreeBSD остается передовой системой, вне зависимости от того, насколько старой может быть часть кода. Это важное отличие, которое, к сожалению, не всеми понимается. Самой большой ошибкой, которую может допустить программист, является игнорирование истории, и это именно та ошибка, которую сделали многие другие современные операционные системы. Самым ярки примером здесь является Windows NT®, и последствия ужасны. Linux также в некоторой степени совершил эту ошибку—достаточно, чтобы мы, люди BSD, по крайней мере по разу отпустили по этому поводу шутку. Проблема Linux заключается просто в отсутствии опыта и истории для сравнения идей, проблема, которая легко и быстро решается сообществом Linux точно так же, как она решается в сообществе BSD—постоянной работой над кодом. Разработчики Windows NT, с другой стороны, постоянно совершают те же самые ошибки, что были решены в UNIX® десятки лет назад, а затем тратят годы на их устранение. Снова и снова. Есть несколько случаев ''проработка архитектуры отсутствует'' и ''мы всегда правы, потому что так говорит наш отдел продаж''. Я плохо переношу тех, кого не учит история.

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

1. Самым важным аспектом при проектировании производительности является то, что называется “оптимизацией критического маршрута”. Часто случается, что оптимизация производительности дает прирост объема кода ради того, чтобы критический маршрут работал быстрее.

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

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

---

2. Объекты VM

Лучше всего начать описание VM-системы FreeBSD с попытки взглянуть на нее с точки зрения пользовательского процесса. Каждый пользовательский процесс имеет единое, принадлежащее только ему и неразрывное адресное пространство VM, содержащее несколько типов объектов памяти. Эти объекты имеют различные характеристики. Код программы и ее данные являются единым файлом, отображаемым в память (это выполняющийся двоичный файл), однако код программы доступен только для чтения, когда как данные программы размещаются в режиме копирования-при-записи. BSS программы представляет собой всего лишь выделенную область памяти, заполненную, если это требовалось, нулями, что называется обнулением страниц памяти по требованию. Отдельные файлы могут также отображаться в адресное пространство, именно так работают динамические библиотеки. Такие отображения требуют изменений, чтобы оставаться принадлежащими процессу, который их выполнил. Системный вызов fork добавляет переводит проблему управления VM полностью в новую плоскость, вдобавок к уже имеющимся сложностям.

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

Вы тут же заметите, что то, что сначала было простым отображением файла в память, становится гораздо более сложным предметом. Данные могут модифицироваться постранично, когда как отображение файла выполняется для многих страниц за раз. Сложность еще более увеличивается, когда процесс выполняет вызов fork. При этом порождаются два процесса—каждый со с собственным адресным пространством, включающим все изменения, выполненные исходным процессом до вызова функции fork(). Было бы глупо для VM-системы делать полную копию данных во время вызова fork(), так как весьма вероятно, что один из двух процессов будет нужен только для чтения из той страницы, что позволяет использование исходной страницы. То, что было страницей, принадлежащей только процессу, сделается снова страницей, копируемой при записи, так как каждый из процессов (и родитель, и потомок) полагают, что их собственные изменения после разветвления будут принадлежать только им, и не затронут родственный процесс.

FreeBSD управляет всем этим при помощи многоуровневой модели VM-объектов. Исходный файл с двоичной программой переносится на самый нижний уровень объектов VM. Уровень страниц, копируемых при записи, находится выше него, и хранит те страницы, которые были скопированы из исходного файла. Если программа модифицирует страницы данных, относящиеся к исходному файлу, то система VM обнаруживает это и переносит копию этой страницы на более высокий уровень. Когда процесс разветвляется, добавляются новые уровни VM-объектов. Это можно показать на простом примере. Функция fork() является общей операцией для всех систем *BSD, так что в этом примере будет рассматриваться программа, которая запускается, а затем разветвляется. Когда процесс запускается, VM-система создает некоторый уровень объектов, обозначим его A:

A соответствует файлу—по необходимости страницы памяти могут высвобождаться и подгружаться с носителя файла. Подгрузка с диска может потребоваться программе, однако на самом деле мы не хотим, чтобы она записывалась обратно в файл. Поэтому VM-система создает второй уровень, B, который физически поддерживается дисковым пространством подкачки:

При первой записи в страницу после выполнения этой операции, в B создается новая страница, содержимое которой берется из A. Все страницы в B могут сбрасываться и считываться из устройства подкачки. Когда программа ветвится, VM-система создает два новых уровня объектов—C1 для порождающего процесса и C2 для порожденного—они располагаются поверх B:

В этом случае, допустим, что страница в B была изменена начальным родительским процессом. В процессе возникнет ситуация копирования при записи и страница скопируется в C1, при этом исходная страница останется в B нетронутой. Теперь допустим, что та же самая страница в B изменяется порожденным процессом. В процессе возникнет ситуация копирования при записи и страница скопируется в C2. Исходная страница в B теперь полностью скрыта, так как и C1, и C2 имеют копии, а B теоретически может быть уничтожена, если она не представляет собой ''реального'' файла). Однако такую оптимизацию не так уж просто осуществить, потому что она делается на уровне мелких единиц. Во FreeBSD такая оптимизация не выполняется. Теперь положим (а это часто случается), что порожденный процесс выполняет вызов exec(). Его текущее адресное пространство обычно заменяется новым адресным пространством, представляющим новый файл. В этом случае уровень C2 уничтожается:

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

Такая модель создает некоторое количество потенциальных проблем. Первая, с которой вы можете столкнуться, заключается в сравнительно большой последовательности уровней объектов VM, на сканирование которых тратится время и память. Большое количество уровней может возникнуть, когда процессы разветвляются, а затем разветвляются еще раз (как порожденные, так и порождающие). Вторая проблема заключается в том, что вы можете столкнуться с мертвыми, недоступными страницами глубоко в иерархии объектов VM. В нашем последнем примере если как родитель, так и потомок изменяют одну и ту же страницу, они оба получают собственные копии страницы, а исходная страница в B становится никому не доступной. такая страница в B может быть высвобождена.

FreeBSD решает проблему с глубиной вложенности с помощью приема оптимизации, который называется “All Shadowed Case”. Этот случай возникает, если в C1 либо C2 возникает столько случаев копирования страниц при записи, что они полностью закрывают все страницы в B. Допустим, что такое произошло в C1. C1 может теперь полностью заменить B, так что вместо цепочек C1->B->A и C2->B->A мы теперь имеем цепочки C1->A и C2->B->A. Но посмотрите, что получается—теперь B имеет только одну ссылку (C2), так что мы можем объединить B и C2. В конечном итоге B будет полностью удален и мы имеем цепочки C1->A и C2->A. Часто B будет содержать большое количество страниц, и ни C1, ни C2 не смогут полностью их заменить. Если мы снова породим процесс и создадим набор уровней D, при этом, однако, более вероятно, что один из уровней D постепенно сможет полностью заместить гораздо меньший набор данных, представленный C1 и C2. Та же самая оптимизация будет работать в любой точке графа и главным результатом этого является то, что даже на сильно загруженной машине с множеством порождаемых процессов стеки объектов VM не часто бывают глубже четырех уровней. Это так как для порождающего, так и для порожденного процессов, и остается в силе как в случае, когда ветвление делает родитель, так и в случае, когда ветвление выполняет потомок.

Проблема с мертвой страницей все еще имеет место, когда C1 или C2 не полностью перекрывают B. Из-за других применяемых нами методов оптимизации этот случай не представляет большой проблемы и мы просто позволяем таким страницам существовать. Если система испытывает нехватку оперативной памяти, она выполняет их выгрузку в область подкачки, что занимает некоторое пространство в области подкачки, но это все.

Преимущество модели VM-объектов заключается в очень быстром выполнении функции fork(), так как при этом не выполняется реального копирования данных. Минусом этого подхода является то, что вы можете построить сравнительно сложную иерархию объектов VM, которая несколько замедляет обработку ситуаций отсутствия страниц памяти, и к тому же тратится память на управление структурами объектов VM. Приемы оптимизации, применяемые во FreeBSD, позволяют снизить значимость этих проблем до степени, когда их можно без особых потерь игнорировать.

---

3. Уровни области подкачки

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

• Во FreeBSD 3.X в структуре управления областью подкачки предварительно выделяется массив, который представляет целый объект, требующий хранения в области подкачки—даже если только несколько страниц этого объекта хранятся в области подкачки. Это создает проблему фрагментации памяти ядра в случае, когда в память отображаются большие объекты или когда ветвятся процессы, занимающие большой объем памяти при работе (RSS).

• Также для отслеживания памяти подкачки в памяти ядра поддерживается ''список дыр'', и он также несколько фрагментирован. Так как ''список дыр'' является последовательным списком, то производительность при распределении и высвобождении памяти в области подкачки неоптимально и ее сложность зависит от количества страниц как O(n).

• Также в процессе высвобождения памяти в области подкачки требуется выделение памяти в ядре, и это приводит к проблемам блокировки при недостатке памяти.

• Проблема еще более обостряется из-за дыр, создаваемых по чередующемуся алгоритму.

• Кроме того, список распределения блоков в области подкачки легко оказывается фрагментированным, что приводит к распределению непоследовательных областей.

• Память ядра также должна распределяться по ходу работы для дополнительных структур по управлению областью подкачки при выгрузке страниц памяти в эту область.

Очевидно, что мест для усовершенствований предостаточно. Во FreeBSD 4.X подсистема управления областью подкачки была полностью переписана мною:

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

• Вместо того, чтобы использовать однонаправленный связный список для отслеживания выделения пространства в области подкачки, теперь используется побитовая карта блоков области подкачки, выполненная в основном в виде древовидной структуры с информацией о свободном пространстве, находящейся в узлах структур. Это приводит к тому, что выделение и высвобождение памяти в области подкачки становится операцией сложности O(1).

• Все дерево также распределяется заранее для того, чтобы избежать распределения памяти ядра во время операций с областью подкачки при критически малом объеме свободной памяти. В конце концов, система обращается к области подкачки при нехватке памяти, так что мы должны избежать распределения памяти ядра в такие моменты для избежания потенциальных блокировок.

• Для уменьшения фрагментации дерево может распределять большой последовательный кусок за раз, пропуская меньшие фрагментированные области.

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

---

4. Когда освобождать страницу

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

Какую дополнительную нагрузку мы может выделить в критическом пути для избежания высвобождения не той страницы? Каждый неправильный выбор будет стоить нам сотни тысяч тактов работы центрального процессора и заметное замедление работы затронутых процессов, так что мы должны смириться со значительными издержками для того, чтобы была заведомо выбрана правильная страница. Вот почему FreeBSD превосходит другие системы в производительности при нехватке ресурсов памяти.

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

В любом случае, бит использования страницы очищается, и в некоторый более поздний момент VM-система обращается к странице снова и обнаруживает, что этот бит установлен. Это указывает на то, что страница активно используется. Периодически проверяя этот бит, накапливается история использования (в виде счетчика) физической страницы. Когда позже VM-системе требуется высвободить некоторые страницы, проверка истории выступает указателем при определении наиболее вероятной кандидатуры для повторного использования.

Что, если аппаратура не имеет бита использования страницы? Для тех платформ, что не имеют этой возможности, система эмулирует этот бит. Она снимает отображение или защищает страницу, что приводит к ошибке доступа к странице, если к странице выполняется повторное обращение. При возникновении этой ошибки система просто помечает страницу как используемую и снимает защиту со страницы, так что она может использоваться. Хотя использование такого приема только для определения использования страницы весьма накладно, это выгоднее, чем повторно использовать страницу для других целей и обнаружить, что она снова нужна процессу и подгружать ее с диска.

FreeBSD использует несколько очередей страниц для обновления выбора страниц для повторного использования, а также для определения того, когда же грязные страницы должны быть сброшены в хранилище. Так как таблицы страниц во FreeBSD являются динамическими объектами, практически ничего не стоит вырезать страницу из адресного пространства любого использующего ее процесса. После того, как подходящая страница, на основе счетчика использования, выбрана, именно это и выполняется. Система должна отличать между чистыми страницами, которые теоретически могут быть высвобождены в любое время, и грязными страницами, которые сначала должны быть переписаны в хранилище перед тем, как их можно будет использовать повторно. После нахождения подходящей страницы она перемещается в неактивную очередь, если она является грязной, или в очередь кэша, если она чистая. Отдельный алгоритм, основывающийся на отношении количества грязных страниц к чистым, определяет, когда грязные страницы в неактивной очереди должны быть сброшены на диск. Когда это выполнится, сброшенные страницы перемещаются из неактивной очереди в очередь кэша. В этот момент страницы в очереди кэша могут быть повторно активизированы VM со сравнительно малыми накладными расходами. Однако страницы в очереди кэша предполагается ''высвобождать немедленно'' и повторно использовать в LRU-порядке (меньше всего используемый), когда системе потребуется выделение дополнительной памяти.

Стоит отметить, что во FreeBSD VM-система пытается разделить чистые и грязные страницы во избежание срочной необходимости в ненужных сбросах грязных страниц (что отражается на пропускной способности ввода/вывода) и не перемещает беспричинно страницы между разными очередями, когда подсистема управления памятью не испытывает нехватку ресурсов. Вот почему вы можете видеть, что при выполнении команды systat -vm в некоторых системах значение счетчика очереди кэша мало, а счетчик активной очереди большой. При повышении нагрузки на VM-систему она прилагает большие усилия на поддержку различных очередей страниц в соотношениях, которые являются наиболее эффективными.

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

---

5. Оптимизация ошибок доступа к страницам и их обнуления

Полагая, что ошибка доступа к странице памяти в VM не является операцией с большими накладными расходами, если страница уже находится в основной памяти и может быть просто отображена в адресное пространство процесса, может оказаться, что это станет весьма накладно, если их будет оказываться регулярно много. Хорошим примером этой ситуации является запуск таких программ, как ls(1) или ps(1), снова и снова. Если бинарный файл программы отображен в память, но не отображен в таблицу страниц, то все страницы, к которым обращалась программа, окажутся недоступными при каждом запуске программы. Это не так уж необходимо, если эти страницы уже присутствуют в кэше VM, так что FreeBSD будет пытаться восстанавливать таблицы страниц процесса из тех страниц, что уже располагаются в VM-кэше. Однако во FreeBSD пока не выполняется предварительное копирование при записи определенных страниц при выполнении вызова exec. Например, если вы запускаете программу ls(1) одновременно с работающей vmstat 1, то заметите, что она всегда выдает некоторое количество ошибок доступа к страницам, даже когда вы запускаете ее снова и снова. Это ошибки заполнения нулями, а не ошибки кода программы (которые уже были обработаны). Предварительное копирование страниц при выполнении вызовов exec или fork находятся в области, требующей более тщательного изучения.

Большой процент ошибок доступа к страницам, относится к ошибкам при заполнении нулями. Вы можете обычно видеть это, просматривая вывод команды vmstat -s. Это происходит, когда процесс обращается к страницам в своей области BSS. Область BSS предполагается изначально заполненной нулями, но VM-система не заботится о выделении памяти до тех пор, пока процесс реально к ней не обратится. При возникновении ошибки VM-система должна не только выделить новую страницу, но и заполнить ее нулями. Для оптимизации операции по заполнению нулями в системе VM имеется возможность предварительно обнулять страницы и помечать их, и запрашивать уже обнуленные страницы при возникновении ошибок заполнения нулями. Предварительное заполнение нулями происходит, когда CPU простаивает, однако количество страниц, которые система заранее заполняет нулями, ограничено, для того, чтобы не переполнить кэши памяти. Это прекрасный пример добавления сложности в VM-систему ради оптимизации критического пути.

---

6. Оптимизация таблицы страниц

Оптимизация таблицы страниц составляет самую содержательную часть архитектуры VM во FreeBSD и она проявляется при появлении нагрузки при значительном использовании mmap(). Я думаю, что это на самом деле особенность работы большинства BSD-систем, хотя я не уверен, когда это проявилось впервые. Есть два основных подхода к оптимизации. Первый заключается в том, что аппаратные таблицы страниц не содержат постоянного состояния, а вместо этого могут быть сброшены в любой момент с малыми накладными расходами. Второй подход состоит в том, что каждая активная таблица страниц в системе имеет управляющую структуру pv_entry, которая связана в структуру vm_page. FreeBSD может просто просматривать эти отображения, которые существуют, когда как в Linux должны проверяться все таблицы страниц, которые могут содержать нужное отображение, что в некоторых ситуация дает увеличение сложности O(n^2). Из-за того, что FreeBSD стремится выбрать наиболее подходящую к повторному использованию или сбросу в область подкачки страницу, когда ощущается нехватка памяти, система дает лучшую производительность при нагрузке. Однако во FreeBSD требуется тонкая настройка ядра для соответствия ситуациям с большим совместно используемым адресным пространством, которые могут случиться в системе, обслуживающей сервер телеконференций, потому что структуры pv_entry могут оказаться исчерпанными.

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

---

7. Подгонка страниц

Мы закончим рассмотрением метода оптимизации подгонкой страниц. Подгонка является методом оптимизации, разработанным для того, чтобы доступ в последовательные страницы виртуальной памяти максимально использовал кэш процессора. В далеком прошлом (то есть больше 10 лет назад) процессорные кэши предпочитали отображать виртуальную память, а не физическую. Это приводило к огромному количеству проблем, включая необходимость очистки кэша в некоторых случаях при каждом переключении контекста и проблемы с замещением данных в кэше. В современных процессорах кэши отображают физическую память именно для решения этих проблем. Это означает, что две соседние страницы в адресном пространстве процессов могут не соответствовать двух соседним страницам в кэше. Фактически, если вы об этом не позаботились, то соседние страницы в виртуальной памяти могут использовать ту же самую страницу в кэше процессора—это приводит к сбросу кэшируемых данных и снижению производительности CPU. Это так даже с множественными ассоциативными кэшами (хотя здесь эффект несколько сглажен).

Код выделения памяти во FreeBSD выполняет оптимизацию с применением подгонки страниц, означающую то, что код выделения памяти будет пытаться найти свободные страницы, которые являются последовательными с точки зрения кэша. Например, если страница 16 физической памяти назначается странице 0 виртуальной памяти процесса, а в кэш помещается 4 страницы, то код подгонки страниц не будет назначать страницу 20 физической памяти странице 1 виртуальной памяти процесса. Вместо этого будет назначена страница 21 физической памяти. Код подгонки страниц попытается избежать назначение страницы 20, потому что такое отображение перекрывается в той же самой памяти кэша как страница 16, и приведет к неоптимальному кэшированию. Как вы можете предположить, такой код значительно добавляет сложности в подсистему выделения памяти VM, но результат стоит того. Подгонка страниц делает память VM предсказуемой, как и обычная физическая память, относительно производительности кэша.

---

8. Заключение

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

---

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