Представляем UVM - новую систему виртуальной памяти для ядра BSD, которая имеет улучшенную архитектуру, повышающую производительность системы по сравнению со старой системой виртуальной памяти на базе ядра Mach 4.4BSD. В этом документе представлен обзор обеих систем: как системы UVM, так и системы виртуальной памяти BSD. Главной темой обсуждения станут проектные решения, принятые при создании UVM в сравнении с менее эффективными решениями, использованными в системе виртуальной памяти BSD. Обсуждаются темы отображения памяти, управления объектами памяти, анонимная память, механизм копирования при записи, а также архитектура средств подкачки страниц. Мы также представим обзор механизмов перемещения данных средствами виртуальной памяти, введённых системой UVM в ядро BSD. Думаем, что уроки, извлечённые при проектировании и реализации UVM, могут быть применены к другим ядрам и крупным программным системам. Система UVM, реализованная для операционной системы NetBSD, полностью заменит систему виртуальной памяти BSD в NetBSD версии 1.4.
В этом документе представлена UVM1 - новая система виртуальной памяти, которая заменит систему виртуальной памяти 4.4BSD операционных систем на основе BSD. UVM - это третье поколение системы виртуальной памяти BSD, улучшающее производительность и уменьшающее сложность ядра BSD. Улучшения производительности UVM, в частности, полезны для приложений, широко использующих возможности виртуальной памяти, таких как отображение файлов в память и копирование памяти при записи.
Системы BSD до версии 4.4BSD использовали старую систему виртуальной памяти BSD-VAX, которая была тесно связана с архитектурой VAX. Этой системе недоставало отображаемых в память файлов (mmap) и мелкозернистой блокировки структур данных для многопроцессорных систем. Учитывая эти проблемы, старая система виртуальной памяти VAX была заменена на новую систему виртуальной памяти в версии 4.4BSD [12]. Система виртуальной памяти 4.4BSD - это модифицированная версия системы виртуальной памяти, написанной для операционной системы Mach Университета Карнеги Меллона [18]. Преимущества системы виртуальной памяти BSD - это чётко отделённые машинно-зависимые функции, поддержка mmap и мелокзернистой блокировки структур данных, подходящей для многопроцессорных систем.
Система виртуальной памяти BSD имеет четыре главных недостатка, которые повлияли на решение заменить её: сложные структуры данных, низкая производительность, отсутствие механизмов перемещения данных средствами виртуальной памяти и скудная документация.
Используемые BSD cтруктуры данных и функции управления памятью сложные и потому трудны в сопровождении. Это особенно касается структур, используемых для представления отображений объектов памяти, копируемых при записи. При копировании объектов памяти с помощью механизма копирования при записи [2] (например, при ответвлении процесса) они объединяются в списки, называемые цепочками объектов. Если не проводить уборку, использование механизма копирования при записи может привести к значительному росту цепочек объектов. Длинные цепочки объектов являются проблемой по двум причинам. Первая: длинные цепочки объектов замедляют время поиска в памяти, увеличивая количество объектов, которые нужно проверить для нахождения затребованной страницы. Вторая: длинная цепочка объектов скорее всего содержит недоступные избыточные копии одной и той же страницы данных, что приводит к бесполезной трате памяти. Если система виртуальной памяти BSD потратит впустую слишком много страниц, это может привести к заполнению области подкачки избыточными данными и в конечном итоге - к блокировке всей системы. Это состояние известно как блокировка из-за утечки памяти в область подкачки. Для избежания проблем, связанных с длинными цепочками объектов, система виртуальной памяти BSD пытается уменьшить длину цепочек с помощью сложной операции схлопывания. Для успешного схлопывания цепочки объектов система виртуальной памяти должна найти в цепочке неиспользуемый объект, содержащий избыточные данные. Если такой объект найден, он пропускается или отбрасывается. Отметим, что даже при удачном схлопывании в цепочке объектов могут оставаться недоступные избыточные страницы. Операция схлопывания может лишь восстановить область подкачки от уже случившейся утечки памяти, но не может её предотвратить.
Система виртуальной памяти BSD демонстрирует низкую производительность по нескольким причинам. Первая: издержки на управление цепочками объектов приводят к замедлению обычных операций, таких как обработка ошибок доступа к страницам и отображение памяти. Вторая: операции ввода-вывода в системе виртуальной памяти BSD производятся по одной странице за раз, а не более эффективными группами из нескольких страниц, что замедляет время отклика подкачки страниц. Третья: интеграция системы виртуальной памяти BSD в ядро не была оптимизирована. Например, не имеющие ссылок объекты отображаемых в память файлов помещаются в кэш системы ввода-вывода (vnode), а также избыточно размещаются в виртуальной памяти. Наконец, некоторые операции с виртуальной памятью без необходимости повторяются на разных уровнях ядра BSD.
Другой недочёт системы виртуальной памяти BSD заключается в отсутствии механизмов перемещения данных средствами виртуальной памяти. Хотя система виртуальной памяти BSD поддержвает механизм копирования при записи, он не позволяет ей без дорогостоящего копирования данных безопасным образом совместно использовать общую память, управляемую другими подсистемами ядра, такими как системы ввода-вывода и межпроцессного взаимодействия. Она также не позволяет процессам легко обмениваться, копировать или совместно использовать части их виртуального адресного пространства.
Наконец, система виртуальной памяти BSD плохо документирована. Хотя некоторые части ядра BSD, такие как сетевая подсистема и система межпроцессного взаимодействия, документированы хорошо [20], системе виртуальной памяти BSD недостаёт такой подробной документации и в ней мало комментариев. Как следствие, разработчикам проектов свободных операционных систем, таких как NetBSD [17], трудно понимать и поддерживать код системы виртуальной памяти 4.4BSD.
Один из подходов к устранению недостатков системы виртуальной памяти BSD - испытывать и развивать структуры данных и функции BSD, унаследованные из Mach, в более эффективную систему виртуальной памяти. Этот подход был успешно применён в системе виртуальной памяти FreeBSD. Однако улучшенная система виртуальной памяти во FreeBSD продолжает страдать от цепочек объектов, унаследованной от системы виртуальной памяти BSD. Альтернативный подход - реализовать систему виртуальной памяти заново, пользуясь удачными проектными решениями системы виртуальной памяти BSD, заменяя неудовлетворительно работающие части и добавляя новые возможности поверх получившейся системы виртуальной памяти. Этот подход был использован в UVM. В UVM сохранено деление на машинно-зависимый и машинно-независимый уровни, а также структуры отображения из системы виртуальной памяти BSD. Были заменены объект виртуальной памяти, обработчик ошибок доступа к страницам и код подкачки страниц. Также в UVM были введены новые механизмы перемещения данных средствами виртуальной памяти. В сочетании с изменениями в системах ввода-вывода и межпроцессного взаимодействия, разрабатываемыми в настоящее время, эти механизмы могут уменьшить издержки от копирования данных в ядре.
Исходный код UVM свободно доступен под стандартной лицензией BSD. UVM влит в основной репозиторий исходного кода NetBSD в начале 1998 и продемонстрировал свою стабильность на архитектурах, поддерживаемых NetBSD, включая Alpha, I386, M68K, MIPS, Sparc и VAX. UVM станет официальной системой виртуальной памяти NetBSD в выпуске 1.4. Также начат перенос UVM в OpenBSD.
В этом документе представлена архитектура и реализация системы виртуальной памяти UVM, особое внимание уделяется улучшениям относительно архитектуры виртуальной памяти BSD. В разделе 2 представлен обзор систем виртуальной памяти BSD и UVM. В разделах 3, 4, 5, 6 и 7 описана архитектура отображений UVM, объектов, анонимной памяти, средств подкачки страниц и перемещения данных, соответственно. В разделе 8 представлен обзор производительности UVM. Раздел 9 содержит связанные работы, раздел 10 содержит заключительные комментарии и обозначает направление будущих исследований.
И систему виртуальной памяти BSD и UVM можно поделить на два уровня: небольшой машинно-зависимый уровень и крупный машинно-независимый уровень. Машинно-зависимый уровень используется обеими системами и называется уровнем pmap. Уровень pmap отвечает за детали низкоуровневого программирования модуля управления памятью (MMU) процессора. Его задача состоит в добавлении, удалении, изменении и получении информации об отображениях виртуальных адресов или страниц физической памяти. Уровень pmap не знает о высокоуровневых абстракциях операционной системы, таких как файлы. Каждая архитектура, поддерживаемая ядром BSD, должна иметь собственный модуль pmap. Отметим, что система UVM была спроектирована для использования того же машинно-зависимого уровня, который используют системы виртуальной памяти BSD и Mach. Это позволило повторно использовать модули pmap из этих систем в UVM, что снизило затраты на перенос ядра с системой UVM на новые архитектуры.
Машинно-независимый код общий для всех процессоров, поддерживаемых BSD. Он содержит функции для высокоуровневых операций с системой виртуальной памяти. К таким функциям относятся управление отображениями файлов, запрос данных из нижележащего хранилища, выгрузка страниц памяти при их дефиците, управление выделением физической памяти, управление памятью, копируемой при записи. На рисунке 1 изображены пять главных абстракций, с которыми имеет дело машинно-независимый уровень, а таже показаны соответствующие им структуры данных в системах виртуальной памяти BSD и UVM.
Рассмотрим эти абстракции:
пространство виртуальной памяти:
описывает машинно-зависимую и машинно-независимую части виртуального адресного пространства процесса. Структура vmspace содержит указатели на структуры pmap и карты памяти процесса, а также содержит статистику об использовании памяти процессом.
карта памяти:
описывает машинно-независимую часть виртуального адресного пространства процесса или ядра. И системы виртуальной памяти BSD и UVM используют стуктуры map (vm_map) для отображения объектов памяти на области виртуального адресного пространства. Каждая структура map в системе содержит упорядоченный двусвязный список структур-элементов. Каждая структура-элемент содержит информацию об отображении виртуального адресного пространства карты. Эта информация включает в себя начальный и конечный виртуальные адреса и указатель на объект памяти, отображённый в этот диапазон адресов. Элемент также содержит атрибуты отображения: тип защиты, шаблон использования памяти (подсказку) и счётчик связей. Ядро и каждый процесс в системе имеют собственные структуры map для управления их виртуальным адресным пространством.
объект памяти:
описывает файл, заполняемую нулями область памяти или устройство, которое может быть отображено в виртуальное адресное пространство. Объекты памяти содержат список страниц с данными этого объекта. В системе виртуальной памяти BSD объекты памяти состоят из одной или более структур vm_object. В системе UVM объект памяти состоит либо из структуры карты анонимной памяти vm_amap, либо из структуры uvm_object (или из обеих). Особенности управления объектами памяти в системах виртуальной памяти BSD и UVM обсуждаются в разделах 4 и 5.
средство подкачки страниц:
описывает, как получить доступ к нижележащему хранилищу. Каждый объект памяти в системе имеет собственное средство подкачки страниц, которое указывает на список функций, используемых объектом для получения страниц физической памяти из нижележащего хранилищя или для их сохранения в нём. Если происходит ошибка при обращении к страницам памяти (или ожидается возникновение такой ошибки) обработчик ошибки считывает эти страницы из нижележащего хранилища. Страницы записываются в нижележащее хранилище по требованию пользователя (например, через системный вызов msync), при дефиците физической памяти или при освобождении объекта, владеющего этими страницами.
страница:
описывает страницу физической памяти. При загрузке системы для каждой страницы физической памяти, которая может быть использована системой виртуальной памяти2, выделяется структура vm_page.
На рисунке 1 система только что загрузилась в однопользовательском режиме, поэтому есть только два процесса (init и sh). У процесса init есть четыре элемента в карте памяти. Эти элементы соответствуют сегментам процесса text, data, bbs и сегменту стека. Элементы упорядочены по начальному виртуальному адресу. Каждый элемент описывает отображение объекта памяти в адресное пространство процесса init. Отметим, что один и тот же объект памяти может отображаться в разные области адресного пространства. Например, файл /sbin/init отображается в адресное пространство процесса init дважды: первый раз как секция text и второй раз как секция data. Эти отображения должны быть отдельными, поскольку используют разный тип защиты. Каждому объекту памяти сопоставлен список страниц, содержащих его постоянные данные, и указатель на средство подкачки страниц, которое может переносить данные между страницами объекта и нижележащим хранилищем. Отметим, что каждая структура map процесса связана со структурой pmap, содержащей низкоуровневую машинно-зависимую информацию для управления памятью (например, таблицы страниц) виртуального адресного пространства этого процесса.
Когда процесс пытается получить доступ к неотображённой области памяти, происходит ошибка доступа к странице. Обработчик ошибок доступа к страницам виртуальной памяти ищет и отображает недостающую страницу. Чтобы найти страницу, которую нужно отобразить, система виртуальной памяти должна найти в структуре map процесса элемент, соответствующий адресу, при обращении к которому произошла ошибка. Если такого элемента нет, то генерируется сигнал ошибки. Если же имеется объект, отображённый в этот адрес, то система виртуальной памяти должна определить, имеются ли уже требуемые данные на странице. Если есть, то эту страницу можно отобразить. Если нет, тогда обработчик ошибки должен обратиться к средству подкачки страниц, чтобы разместить в памяти данные и обработать ошибку.
В следующих разделах рассматриваются подробности структуры и управления этими пятью абстракциями.
UVM привносит в карты памяти два важных улучшения. Первое: увеличена эффективность и безопасность функций отображения памяти. Второе: значительно уменьшена фрагментация элементов при фиксации памяти.
Функции uvm_map и uvm_unmap - две из большого множества функций для работы с картами. Функция uvm_map используется для создания нового отображения памяти с указанными атрибутами. Функция uvm_map блокирует карту, добавляет отображение и снимает блокировку карты. В системе виртуальной памяти BSD нет функции, эквивалентной uvm_map. Вместо неё в системе виртуальной памяти BSD есть функция для создания отображения с атрибутами по умолчанию и набор функций для изменения атрибутов отображения. Эти функции неэффективны и небезопасны. Неэффективны, потому что требуется дополнительная блокировка карты и изменение значений. Например, по умолчанию система виртуальной памяти BSD разрешает чтение и запись, поэтому создание отображения с защитой от записи происходит в два этапа. Сначала нужно создать отображение с защитой по умолчанию. Потом нужно снова заблокировать карту и найти нужное отображение, чтобы запретить запись. Отметим, что при создании отображения с защитой от записи есть короткий промежуток времени между первым и вторым этапами, во время которого отображение уже создано, но допускает запись. В многопоточном ядре два потока, совместно использующих одно и то же адресное пространство, могут обойти систему безопасности и изменить защищённые данные.
В системах виртуальной памяти BSD и UVM есть функции unmap с одинаковым интерфейсом, однако их внутренняя структура отличается. Функция unmap из системы виртуальной памяти BSD сохраняет указанную карту заблокированной на более длительное время, чем требуется, не позволяя работать с ней другим потокам. При выполнении unmap в системе виртуальной памяти BSD карта блокируется, из неё удаляются указанные элементы, удаляются ссылки на отображённые объекты памяти, после чего карта разблокируется. Однако, блокировка карты, происходящая во время операции unmap в системе виртуальной памяти BSD, на самом деле нужна только для удаления элементов из карты. Для удаления ссылок на объекты памяти блокировка этой карты не требуется (отметим, что удаление последней ссылки на объект памяти может запустить длительные операции ввода-вывода). Функция unmap из UVM выполняется в два этапа. На первом этапе карта блокируется для удаления указанных элементов. После этого карта разблокируется и можно приступить к удалению ссылок на объекты памяти. Второй этап выполняется при разблокированной карте, благодаря чему сокращается длительность её блокировки.
Фрагментация элемента карты происходит при делении соответствующей ей области виртуальной памяти на две или три примыкающих части, для каждой из которых в карте создаётся собственный элемент. Фрагментация элемента карты нежелательна по нескольким причинам. Во-первых, большее количество элементов карты приводит к увеличению длительности операций над ней, например, при поиске подходящго элемента для обработки ошибки обращения к странице. Во-вторых, сама фрагментация элемента карты приводит к дополнительным издержкам. Для фрагментирования элемента карты нужно выделить и инициализировать новые элементы в карте и добавить ссылки на нижележащие объекты. Наконец, если речь заходит о ядре, то у него общее количество элементов карты ограничено. Если у ядра закончатся элементы карты, система не сможет продолжать работу. Так как фрагментация элементов карты во многих случаях неизбежна, очевидно, что ядру выгодно максимально снизить её.
Фрагментация элемента карты происходит только при изменении части области виртуальной памяти, соответствующей этому элементу. Т.к. все страницы виртуальной памяти, соответствующие одному элементу карты, должны иметь одинаковые атрибуты, элемент приходится делить на фрагменты. Например, сегментам text и data процесса init, показанного на рисунке 1, должны соответствовать разные элементы карты, потому что у них разный тип защиты. Пока атрибуты фрагментов элемента карты не станут совместимыми, объединить их не смогут ни система виртуальной памяти BSD, ни UVM.
Чаще всего элементы карты фрагментируются из-за фиксации и снятия фиксации виртуальной памяти. Фиксированная память - это память, которая должна оставаться в физической памяти и не должна выгружаться. В BSD память фиксируется в пяти случаях. В отличие от системы виртуальной памяти BSD, UVM избегает фрагментации элементов карты и вызванных этим издержек в четырёх из пяти случаев. UVM пользуется тем, что зафиксированное состояние страницы часто можно узнать из других областей памяти, а не только из элемента карты, благодаря чему отпадает необходимость беспокоить структуру map. Память фиксируется ядром BSD в следующих случаях:
Кроме перечисленных пяти случаев фиксация памяти используется при выделении аппаратных таблиц страниц в машинно-зависимом коде архитектуры i386. UVM не отмечает зафиксированное состояние памяти в карте пользовательского процесса, т.к. оно отмечается в структуре pmap для архитектуры i386.
Из-за снижения общей фрагментации элементов карты из-за фиксации в UVM значительно уменьшена потребность в элементах карт. Например, рассмотрим статически связанную программу cat и динамически связанную программу od. На платформе i386 системе виртуальной памяти BSD требуется 11 элементов карты для cat и 21 для od, в то время как UVM требуется всего 6 элементов карты для cat и 12 для od. Отличие между системой виртуальной памяти BSD и UVM вызвано лишь изменениями в выделении структуры user, системном вызове sysctl и в процедуре выделения таблицы страниц pmap в i386. Оказалось, что при обычной работе mlock и physio используются редко. В таблице 1 приведено сравнение количества выделенных элементов карты для нескольких обычных операций. Хотя эффект от снижения количества выделенных элементов карты на общую производительность системы минимален, стоит отметить, что общее количество доступных элементов карты памяти ядра фиксировано и при его исчерпании система вынуждена будет совершить аварийную остановку. В системе виртуальной памяти BSD это может быть проблемой, т.к. каждый процесс использует два элемента в карте ядра.
| Операция | Количество элементов карты | |
|---|---|---|
| BSD | UVM | |
| cat (связан статически) | 11 | 6 |
| od (связан динамически) | 21 | 12 |
| загрузка в однопользовательском режиме | 50 | 26 |
| загрузка в многопользовательском режиме (без вошедших пользователей | 400 | 242 |
| запуск X11 (9 процессов) | 275 | 186 |
Управление объектами памяти в UVM значительно отличается от такового в системе виртуальной памяти BSD. В системе виртуальной памяти BSD структура объекта памяти задумана как самостоятельная абстракция под управлением системы виртуальной памяти. Система виртуальной памяти BSD управляет выделением объектов, ссылками на них и их использованием. В то же время в UVM структура объекта памяти задумана как второстепенная структура, спроектированная для встраивания в более крупные структуры, чтобы UVM мог управлять их отображением в памяти. Структура, в которую встраивается объект памяти UVM, обычно является частью структуры, управляемой извне системы виртуальной памяти какой-либо другой подсистемой ядра. Например, структура объекта UVM для данных файла встраивается в структуру системы ввода-вывода vnode. Система vnode выделяет структуру объекта памяти UVM вместе со структурой vnode. Весь доступ к данным объекта памяти и его состоянию проходит через функции средства подкачки. Эти функции выступают в роли моста между UVM и внешней подсистемой ядра, которая предоставляет UVM свои данные (см. раздел 6).
Способ управления объектами памяти UVM предпочтительнее способа системы виртуальной памяти BSD по нескольким причинам. Во-первых, он эффективнее. В UVM объекты памяти выделяются и управляются вместе с их исходными данными (обычно с vnode'ами). В системе виртуальной памяти BSD объекты памяти и их источники должны выделяться и управляться отдельно, вследствие чего система виртуальной памяти BSD повторяет работу, которая уже была произведена подсистемой исходных данных. Система виртуальной памяти BSD по сравнению с UVM должна выделить больше структур и в ней больше кода управления объектами для выполнения тех же действий.
Во-вторых, структура объекта UVM гибче, чем в системе виртуальной памяти BSD. Благодаря возможности встроить объект памяти в структуру данных, любую абстракцию ядра можно с лёгкостью превратить в отображаемую. К тому же маршрутизация запросов объектов в UVM через операции их средств подкачки позволяет внешним подсистемам ядра генерировать данные объектов памяти, более тонко контролируя их использование со стороны UVM.
Наконец, структура управления объектом памяти UVM создаёт меньше конфликтов между системой виртуальной памяти и внешними подсистемами ядра, такими как подсистема vnode. Подсистема vnode BSD сохраняет для повторного использования неиспользуемые vnode в кэше, находящемся в физической памяти. Когда не хватает vnode, то ядро повторно использует последний неиспользуемый vnode. Таким же образом система виртуальной памяти BSD кэширует неиспользуемые объекты памяти. Структура vnode выделяется при открытии файла, чтении, записи или отображении памяти, а соответствующие им объекты памяти выделяются системой виртуальной памяти BSD только при отображении файла в память. Пока неиспользуемый объект памяти хранится в кэше объектов системы виртуальной памяти BSD, он продолжает ссылаться на нижележащий объект vnode, предотвращая его повторное использование. К несчастью, это также значит, что когда выгоднее повторно использовать vnode из кэша объектов системы виртуальной памяти BSD, система vnode выбирает для повторного использования не оптимальный vnode. Другая проблема кэша объектов системы виртуальной памяти BSD состоит в том, что он ограничен одной сотней неиспользуемых объектов, чтобы предотвратить удержание слишком большого количества vnode (из-за чего их нельзя использовать повторно). Если система виртуальной памяти BSD желает добавить неиспользуемый объект в заполненный кэш, то удаляется самый давно использованный объект. Это менее чем оптимально, потому что данные объекта vnode могут всё ещё быть в кэше системы vnode и было бы эффективнее позволить объекту памяти существовать столько, сколько существует vnode.
Вместо двух уровней кэширования неиспользуемых объектов в UVM есть только один. Вместо поддержания собственного кэша неиспользуемых объектов UVM полагается на внешние подсистемы ядра, такие как система vnode. Это снижает избыточность кода и позволяет использовать механизм кэширования редко используемых объектов для справедливого применения к объектам vnode и объектам памяти. Если возникнет необходимость повторно использовать vnode, UVM даёт подсистеме vnode возможность освобождить связанный с ним объект памяти. Это изменение может значительно повлиять на производительность. Например, рассмотрим веб-сервер, такой как Apache, который передаёт файлы в сеть, отображая их в память. Если количество файлов в рабочем множестве сервера меньше ста, тогда и система виртуальной памяти BSD и UVM смогут удержать все данные файлов в памяти. Но если рабочее множество вырастает свыше сотни файлов, то система виртуальной памяти BSD вымывает из кэша объектов самые старые неактивные объекты (даже если памяти достаточно). С системой виртуальной памяти BSD это приводит к замедлению из-за доступа к диску. На рисунке 2 показаны результаты измерений, произведённых на 333-мегагерцовом процессоре Pentium-II. Чтобы нарисовать этот график, мы написали программу, которая обращается к каждому байту растущего множества файлов, так же как Apache, и измеряли время, в течение которого файлы находятся в карте памяти.
Анонимная память освобождается сразу, как только на неё перестают ссылаться. Эта память называется анонимной, потому что не связана с файлом и не может быть названа его именем. При дефиците памяти анонимная память выгружается в пространство подкачки. Анонимная память используется операционными системами типа Unix в самых разнообразных целях, например как заполняемые нулями отображения (например, для сегментов bss и стека), для совместно используемой памяти System V, для выгружаемых областей памяти ядра и для хранения изменённых страниц отображений, копируемых при записи. Значительная часть кода управления анонимной памятью относится к управлению памятью, копируемой при записи. В этом разделе мы начнём с краткого обзора управления анонимной памятью в системах виртуальной памяти BSD и UVM. Затем мы опишем улучшения, введённые в UVM и приведшие к устранению утечек памяти подкачки, рассмотрим более эффективный механизм копирования при записи и упрощения в коде.
Создание анонимного заполняемого нулями отображения в системе виртуальной памяти BSD происходит очень просто. Система виртуальной памяти BSD просто выделяет объект анонимной памяти указанного размера и вставляет в карту элемент, указывающий на объект. Однако с копируемой при записи памятью в системе виртуальной памяти BSD всё обстоит сложнее.
Система виртуальной памяти BSD управляет оботражениями копируемых при записи объектов памяти с использованием затеняющих объектов. Затеняющий объект - это объект анонимной памяти, который содержит изменённые страницы копируемого при записи объекта памяти. Элемент карты, соответствующий копируемой при записи области, указывает на выделенный для этого затеняющий объект. Затеняющие объекты указывают на объект, который они затеняют. При поиске страницы в копируемом при записи отображении первым просматривается затеняющий объект, указанный в элементе карты. Если соответствующей страницы в затеняющем объекте нет, то выполняется поиск в нижележащем объекте. Нижележащий объект может быть объектом-файлом или другим затеняющим объектом. Поиск продолжается пока не будет найдена требуемая страница или больше не останется нижележащих объектов. Список объектов, связанных с копируемым при записи элементом карты, вплоть до самого нижнего объекта, называется цепочкой затеняющих объектов.
В верхней строчке рисунка 3 показано, как образуется цепочка затеняющих объектов в системе виртуальной памяти BSD. На рисунке объект трёхстраничного файла отображён на адресное пространство процесса как копируемый при записи.
В первой колонке рисунка показано, как создаются отображения, копируемые при записи. Для создания копируемого при записи отображения система виртуальной памяти BSD выделяет новый элемент карты, выставляет флаги "требуется копирование" и "копировать при записи", настраивает в элементе карты указатель на нижележащий объект (обычно объект-файл) и вставляет этот элемент в целевую карту. Флаг "требуется копирование" используется для отложенного выделения нового объекта памяти, которое будет выполнено при первой ошибке записи в отображение. При первой такой ошибке создаётся новый объект, который отслеживает все страницы, скопированные и изменённые при обработке ошибок записи. В системе виртуальной памяти BSD флаг "требуется копирование" указывает, что при следующем изменении отображаемой памяти этому отображению потребуется затеняющий объект. При чтении отображения страницы нижележащего объекта отображаются в целевую карту как доступные только для чтения.
Во второй колонке рисунка 3 показано что произойдёт при попытке изменить содержимое страницы в середине объекта. Т.к. страница в середине не отображена или отображена только для чтения, запись в неё приведёт к ошибке доступа к странице. Процедура обработки ошибок доступа к страницам должна перехватить и исправить эту ошибку, чтобы выполнение процесса могло продолжиться. Процедура обработки ошибок находит соответствующий элемент карты и видит, что она принадлежит отображению с флагами "требуется копирование" и "копировать при записи". Сначала она очищает флаг "требуется копирование", выделяя затеняющий объект и вставляя его между элементом карты и нижележащим файлом. Затем она копирует данные из средней страницы нижележащего объекта в новую страницу, которая вставляется в затеняющий объект. Теперь страница затеняющего объекта может быть отображена в адресное пространство процесса, вызвавшего ошибку, как доступная для записи. Отметим, что этот затеняющий объект содержит только среднюю страницу. Другие страницы будут скопированы только при их изменении.
В третьей колонке рисунка 3 показаны структуры данных системы виртуальной памяти BSD после того, как процесс с копируемым при записи отображением породил потомка и выполнил запись в среднюю страницу, а потомок выполнил запись в страницу правее. При разветвлении родителя процесс-потомок принимает копию родительского отображения, копируемого при записи. Это делается при помощи защиты от записи отображения родителя и выставления флага "требуется копирование" у обоих процессов. Если родитель совершит ошибку доступа к средней странице, для него будет выделен второй затеняющий объект (с очищенным флагом "требуется копирование"), который будет вставлен над первым затеняющим объектом. Когда потомок совершит ошибку доступа к странице справа, произойдёт то же самое, что приведёт к созданию третьего затеняющего объекта.
UVM управляет анонимной памятью при помощи расширенных версий абстракций anon и amap, впервые введённых в систему виртуальной памяти SunOS [4,9,13]. anon - это структура данных, описывающая одну страницу анонимной памяти, а amap (также известная как "анонимная карта") - это структура данных, которая содержит указатели на множество структур anon, совместно отображаемых в виртуальную память. Система анонимной памяти UVM, основанная на amap, отличается от системы SunOS в нескольких чертах. Во-первых, в системе анонимной памяти UVM появилось наследование памяти, подобное применявшемуся в Mach, и отложенное создание amap (при помощи флага "требуется копирование"). Во-вторых, подсистема анонимной памяти SunOS находится ниже интерфейса подкачки vnode и скрыта от остального кода виртуальной памяти. В UVM мы вынесли систему анонимной памяти из кода подкачки, что позволило управлять ей централизованно и использовать во всех средствах подкачки, подсистемах межпроцессного взаимодействия и ввода-вывода. В-третьих, структура средств подкачки SunOS требует, чтобы каждая реализация подкачки самостоятельно ошибки доступа к собственным страницам. В UVM имеется обобщённый обработчик ошибок доступа к страницам. Наконец, в UVM интерфейс amap отделён от реализации amap, что позволяет легко менять её.
В системе виртуальной памяти BSD копируемые при записи элементы карты указывают на цепочку затеняющих объектов. Количество затеняющих объектов в одной цепочке не ограничено. В UVM же используется простая двухуровневая схема соответствия, состоящая из верхнего уровня анонимной памяти amap и нижнего уровня подлежащих объектов. В UVM копируемый при записи элемент карты указывает на amap и на нижележащий объект, соответствующий этому элементу. Любой из этих указателей может быть нулевым. Например, совместно используемая память обчно имеет нулевой указатель на amap, а заполняемое нулями отображение имеет нулевой указатель на объект.
Структура anon в UVM содержит счётчик ссылок и текущее положение данных (например, в памяти или в нижележащем хранилище). Структура anon, на которую ссылается только одна структура amap, считается доступной для записи, в противном случае требуется копирование при записи. Для исправления ошибок записи в anon выделяется новая структура anon, в которую копируются имеющиеся данные, после чего ссылка на исходную структуру anon удаляется. В нижней строке рисунка 3 на том же примере, который использовался для системы виртуальной памяти BSD, показано как UVM обрабатывает отображения, копируемые при записи. В UVM копируемое при записи отображение создаётся вставкой в карту элемента с флагами "требуется копирование" и "копировать при записи", который указывает на нижележащий объект в целевой карте. Когда процесс с копируемым при записи отображением пишет в среднюю страницу, процедура обработки ошибок UVM сначала выделяет новую структуру amap, чтобы сбросить флаг "требуется копирование", а затем копирует данные из нижележащего объекта в новую структуру anon. После этого структура anon вставляется в середину отображения amap.
В третьей колонке строки UVM на рисунке 3 показаны структуры данных UVM после ответвления потомка от процесса с отображением, копируемым при записи. Родитель пишет в среднюю страницу, а потомок пишет в страницу справа. При разветвлении родителя потомок получает копию родительского отображения, копируемого при записи. Это делается путём защиты родительского отображения и установки флага "требуется копирование" у родителя и потомка. Когда родитель генерирует ошибку доступа к средней странице, для него создаётся вторая структура amap (которая очищает флаг "требуется копирование" и увеличивает количество ссылок на anon на одну), а затем данные копируются из первой anon (всё ещё принадлежащей исходному amap) в новую структуру anon, которая будет вставлена в новую структуру amap. Когда потомок генерирует ошибку доступа к странице справа, процедура обработки ошибок очищает флаг "требуется копирование" без выделения новой структуры amap, потому что на исходную структуру amap ссылается только потомок. Процедура обработки ошибок исправляет ошибку потомка, выделяя третью структуру anon, которую вставляет в структуру amap потомка.
И в системе виртуальной памяти BSD и в UVM флаг "требуется копирование" откладывает выделение структур анонимной памяти до первой ошибки, требующей выполнить копирование при записи. Таким образом почти пропадает необходимость в копировании amap и создании затеняющих объектов3 при типовых ветвлениях, когда процесс-потомок немедленно запускает другую программу. В обеих системах страницы, защищённые от записи в отображениях родительского процесса, приводят к возникновению издержек, т.к. каждую из них нужно скопировать при записи. Для очистки флага "требуется копирование" в UVM нужно выделить новую структуру amap и инициализировать её указателями на anon (с соответствюущим увеличением счётчика ссылок в структурах anon). Чтобы очистить флаг "требуется копирование", системе виртуальной памяти BSD требуется выделить новый затеняющий объект и вставить его в цепочку объектов. При последующих ошибках записи системе виртуальной памяти BSD нужно найти данные в нижележащих объектах цепочки и предоставить эти данные верхнему затеняющему объекту. Кроме того, система виртуальной памяти BSD при обработке ошибок защиты от записи пытается также выполнить операцию схлопывания объектов.
В системе виртуальной памяти BSD объём памяти, необходимый структурам данных ядра для обработки копирования при записи, зависит от размера затеняющего объекта (который постоянен) и от связанных с ним структур данных подкачки. Количество структур данных подкачки меняется в зависимости от количества виртуальных страниц, соответствующих объекту. Страницы группируются вместе в блоки подкачки, которые могут иметь размер от 32 до 128 килобайт, в зависимосит от размера объекта. Каждая структура блока подкачки содержит информацию о своём положении в нижележащем хранилище. В UVM объём памяти, необходимый структурам данных ядра для обработки копирования при записи, зависит от размера структуры данных amap и связанных с ним структур данных anon. Размер amap зависит от реализации. В настоящее время amap в UVM реализована при помощи массивов, поэтому требования к объёму памяти зависят от количества покрываемых amap виртуальных страниц. Для больших редко выделяемых структур объём amap значителен, но его можно уменьшить, если реализовать гибридные структуры amap на основе хэш-таблиц и массивов. UVM хранит в структурах anon информацию о расположении в области подкачки каждой страницы. UVM нужна информация для каждой страницы, а не для блока подкачки, как в системе виртуальной памяти BSD, потому что UVM может динамически переназначать местоположение каждой страницы в области подкачки для быстрой выгрузки групп страниц (см. описание в разделе 6).
В системе виртуальной памяти BSD существует несколько архитектурных проблем и недостатков анонимной памяти, которые повлияли на наше решение полностью заменить его в UVM на анонимную память на базе amap. Механизм копирования при записи в системе виртуальной памяти BSD может приводить к утечкам памяти, т.к. позволяет более недоступным страницам памяти оставаться внутри цепочек объектов. Например, рассмотрим последнюю диаграмму системы виртуальной памяти BSD на рисунке 3. Если процесс-потомок завершит работу, то третий затеняющий объект будет освобождён. Оставшаяся цепочка затеняющих объектов содержит три копии средней страницы. Из этих трёх копий доступны только две: страница в первом затеняющем объекте больше не доступна и должна быть освобождена. Однако если процесс-потомок запишет среднюю страницу перед выходом, то эта страница в первом затеняющем объекте тоже станет недоступной. Если не устранять такие утечки, система будет использовать пространство подкачки.
Чем длиннее цепочка теневых объектов, тем выше вероятность исчерпания пространства подкачки. Хотя система виртуальной памяти BSD не может предотвратить образование цепочек затеняющих объектов, она пытается уменьшить длину сформировавшейся цепочки её схлопыванием. Система виртуальной памяти BSD пытается схлопнуть цепочку затеняющих объектов при каждой ошибке записи в затеняющий объект, при удалении ссылок на него, при его копировании или при первой выгрузке страниц затеняющего объекта в пространство подкачки. Эти действия выполняются наряду с обычной работой системы виртуальной памяти.
Поиск объектов для схлопывания - сложный процесс, добавляющий дополнительные издержки в систему виртуальной памяти BSD. В UVM схлопывание не требуется, т.к. счётчики ссылок в amap и anon отслеживают, когда нужно освободить страницу. Благодаря этому в UVM можно эффективнее, чем в системе виртуальной памяти BSD, реализовать некоторые новые функции, такие как перемещение данных с использованием механизма копирования при записи.
Другая проблема с механизмом копирования при записи в системе виртуальной памяти BSD заключается в том, что он неэффективен. Например, представим, что процесс-потомок на рисунке 3 выполнит запись в среднюю страницу. При исправлении ошибки доступа к странице в системе виртуальной памяти BSD данные из средней страницы затеняющего объекта 1 будут скопированы в новую страницу затеняющего объекта 3. Но выделять страницу и копировать в неё данные не требуется. Вместо того, чтобы копировать данные из затеняющего объекта 1 в затеняющий объект 3, лучше было бы просто переназначить среднюю страницу из затеняющего объекта 1 в затеняющий объект 3. К несчастью, в системе виртуальной памяти BSD это невозможно, т.к. структура данных не позволяет отметить, нужна ли страница в затеняющем объекте 1 или нет. В UVM процессу-потомку разрешается выполнить запись прямо в среднюю страницу в anon 1 (это допустимо, потому что счётчик ссылок anon 1 равен единице), что позволяет избежать дорогих и ненужных операций выделения страницы и копирования данных.
Наконец, код для управления анонимной памятью в системе виртуальной памяти BSD сложнее кода UVM, основанного на amap. Система виртуальной памяти BSD должна быть готова пройти по многоуровневой цепочке объектов, чтобы найти нужные данные. Каждый объект в цепочке имеет собственный набор операций ввода-вывода, свою блокировку, свой затеняющий объект, собственную область физической памяти и пространства подкачки. Система виртуальной памяти BSD нужно учитывать все особенности каждого объекта в цепочке так, чтобы память осталась в согласованном состоянии. В то же время нужно агрессивно схлопывать и обходить затеняющие объекты для предотвращения утечек памяти и роста длины цепочки объектов, что приводит к замедлению поиска в памяти. UVM может осуществлять те же функции при помощи простого двухуровневого механизма поиска. Вместо просмотра цепочки объектов в поисках данных, UVM нужно проверить лишь amap и уровень объекта. Вместо использования списков объектов UVM использует счётчики ссылок в структурах amap и anon для отслеживания доступа к анонимной памяти. Новая система управления анонимной памяти UVM внесла заметное улучшение в общую производительность системы (см. раздел 8).
Система анонимной памяти UVM на основе amap была создана по аналогии с системой анонимной памяти драйвера сегментов vnode в системе виртуальной памяти SunOS [9,13]. (Драйверы сегментов в SunOS выполняют функции, схожие со средствами подкачки в UVM.) Хотя этой системы достаточно для SunOS, она потребовала значительной доработки для работы в среде BSD и для поддержки новых возможностей по перемещению данных в UVM, описанных в разделе 7. Механизм анонимной памяти SunOS не является абстракцией виртуальной памяти общего назначения. Он реализован как часть драйвера сегментов vnode в SunOS. Это подходит для SunOS, потому что память, копируемая при записи и заполняемая нулями, может быть изолирована от уровня vnode. Но UVM является системой виртуальной памяти общего назначения и поэтому системам обработки ошибок и механизмам перемещения данных требуется доступ к структурам amap. Поэтому в UVM мы изменили роль системы amap, превратив её в машинно-независимую абстракцию виртуальной памяти общего назначения. Это позволяет любому типу отображения обладать анонимным уровнем.
Во-вторых, ядро BSD использует несколько механизмов, отсутствующих в SunOS. Для замены системы виртуальной памяти BSD на UVM без потери функций архитектура системы amap в UVM должна учитывать эти механизмы. Например, BSD поддерживает системный вызов minherit. Этот системный вызов позволяет процессу управлять доступом потомков к своей виртуальной памяти. В традиционных системах типа Unix (включая SunOS) процесс-потомок получает доступ к совместно используемым отображениям процесса-родителя и доступ с копированием при записи к остальным отображениям. Однако в BSD традиционное поведение по умолчанию может быть изменено при помощи системного вызова minherit. Системный вызов minherit позволяет процессу определить свою память как none - недоступную для потомков, shared - общую или copy - копируемую. Может случиться так, что процесс-потомок совместно со своим родителем использует отображение, копируемое при записи, или принимает от родителя копию совместно используемого отображения, копируемого при записи. Кроме minherit в отображениях BSD также используется флаг "требуется копирование" для отложенного выделения структур анонимной памяти до тех пор, пока они не понадобятся. В SunOS нет флага "требуется копирование". Поэтому UVM, в отличие от SunOS, должна быть готова к отложенному выделению структур amap при помощи флага "требуется копирование" до тех пор, пока оно действительно не потребуется. Чтобы поддерживать целостное состояние памяти для всех процессов при наличии системного вызова minherit и флага "требуется копирование", код amap в UVM должен соблюдать аккуратность при создании структур amap и отслеживании структур amap с общим доступом.
В-третьих, адаптация системы анонимной памяти на основе amap в UVM затронула процедуру исправления ошибок доступа к страницам. В SunOS вся работа по обработке ошибки доступа к отсутствующей странице, если она не касается поиска записи в карте, ложится на драйвер сегмента. С другой стороны, в системе виртуальной памяти BSD имеется процедура общего назначения для исправления ошибок доступа к странице, которая учитывает все тонкости выделения памяти, просмотра цепочек объектов и управления ими, за исключением операций ввода-вывода. Большая часть этой процедуры относится к управлению цепочками объектов. Ни один из этих двух способов исправления ошибок не подходит для UVM. Способ исправления ошибок SunOS перекладывает на уровень подкачки слишком много работы, не зависящей от механизма подкачки. А поскольку UVM не использует цепочки объектов, процедура исправления ошибок системы виртуальной памяти BSD тоже не подходит. Поэтому для UVM процедура исправления ошибок была написана с нуля. Процедура исправления ошибок UVM сначала ищет проблемный адрес в карте. Затем она ищет нужные данные отображения на уровне amap. Если данные не найдены, она ищет их на уровне нижележащего объекта. Если данные по-прежнему не найдены, то возвращается код ошибки. Дополнительно при исправлении ошибки доступа к текущей странице процедура UVM также выполняет поиск имеющихся в памяти страниц, которые находятся рядом с проблемным адресом и вносит их в отображение. Количество просматриваемых страниц управляется системой madvise (по умолчанию просматриваются четрые страницы после проблемного адреса и три страницы до него). Это позволяет снизить количество будущих ошибок доступа к страницам. В таблице 2 показаны результаты этих изменений на i386 для нескольких команд. Отметим, что этот механизм работает только для находящихся в памяти страниц и поэтому имеет минимальное влияние на время выполнения для указанных приложений, не совершающих большое количество ошибок доступа к страницам. В рамках последующей работы мы планируем доработать UVM для асинхронной подкачки отсутствующих в памяти страниц, которые могут оказаться полезными.
| Команда | система виртуальной памяти BSD | UVM |
|---|---|---|
| ls / | 59 | 33 |
| finger chuck | 128 | 74 |
| cc | 1086 | 590 |
| man csh | 114 | 64 |
| newaliases | 229 | 127 |
UVM привносит три важных улучшения в средства подкачки. Повышена эффективность выделения структур данных, относящихся к средствам подкачки. API средств подкачки стал более гибким и предоставляет средствам подкачки больше возможностей по управлению своими страницами. Также было введено более агрессивное группирование в системе анонимной памяти.
Есть существенное отличие между способом организации структур данных средств подкачки в системах виртуальной памяти BSD и UVM. В системе виртуальной памяти BSD средство подкачки требует нескольких отдельных структур данных. На рисунке 4 слева показаны эти структуры для средства подкачки vnode. В системе виртуальной памяти BSD объект памяти указывает на структуру vm_pager. Эта структура содержит указатели на набор операций средства подкачки и указатель на структуру его приватных данных (vn_pager), а эта структура указывает на соответствющий vnode. Кроме этих структур в системе виртуальной памяти BSD таже используется хэш-таблица, в которой отслеживается соответствие структуры средства подкачки нижележащему объекту (отметим, что нет указателя из vm_pager на vm_object). На рискунке 4 справа показаны структуры данных средства подкачки UVM, связанные с vnode. Все относящиеся к vnode данные системы виртуальной памяти встроены внутрь самой структуры vnode. Структура данных средства подкачки была упразднена - объект памяти UVM указывает прямо на операции подкачки. Итого, для создания отображения файла система виртуальной памяти BSD должна выделить три структуры данных (vm_object, vm_pager и vn_pager) и отметить средство подкачки в хэш-таблице. UVM же не пользуется хэш-таблицей и не выделяет каких-либо структур данных. Все структуры данных UVM должны быть встроены в структуру vnode.
Другое отличие интерфейса подкачки системы виртуальной памяти BSD от UVM заключается в API, используемом для получения данных из нижележащего хранилища. Для получения страницы данных объекта из нижележащего хранилища система виртуальной памяти BSD должна сначала выделить новую страницу, добавить её в объект, а затем попросить средство подкачки заполнить её данными. В UVM это делает само средство подкачки. Если потребуется новая страница, средство подкачки выделит её самостоятельно. Это изменение API позволяет средству подкачки иметь полный контроль над добавлением страниц к объекту, что может пригодиться если средство подкачки желает выбрать для размещения данных определённую страницу. Например, это может быть средство подкачки для отображения страниц ПЗУ.
Другое отличие между интерфейсами средств подкачки системы виртуальной памяти BSD и UVM заключается в способе подкачки аномнимной памяти. Уникальное свойство анонимной памяти заключается в том, что она находится под полным контролем системы виртуальной памяти и не имеет постоянного положения в нижележащем хранилище. UVM пользуется этим для более агрессивной группировки анонимной памяти, чем это возможно в системе виртуальной памяти BSD. Суть этой агрессивной группировки заключается в том, что pagedaemon из UVM может переназначать место выгрузки страницы анонимной памяти на нижележащем хранилище. Это позволяет pagedaemon из UVM собрать для выгрузки большую группу грязных страниц анонимной памяти. Каждое место в области подкачки назначается (или переназначается) так, чтобы эта группа заняла непрерывный фрагмент области подкачки и могла быть выгружена за одну большую операцию ввода-вывода. Например, если pagedaemon из UVM обнаруживает в объекте анонимной памяти грязные страницы по смещениям три, пять и семь, он всё ещё может сгруппировать эти страницы, в то время как система виртуальной памяти BSD выполнит три отдельные операции ввода-вывода для выгрузки тех же страниц. В результате UVM может выбраться из ситуации нехватки страниц быстрее и эффективнее, чем система виртуальной памяти BSD. На рисунке 5 сравнивается время, требуемое на выделение анонимной памяти в системе виртуальной памяти BSD и в UVM на процессоре Pentium-II с частотой 333 МГц с 32 мегабайтами оперативной памяти. Когда размер уже выделенной памяти становится больше размера физической памяти, для выполнения очередного запроса системе приходится воспользоваться подкачкой. Заметно, что UVM может выполнять подкачку значительно быстрее, чем система виртуальной памяти BSD.
UVM предоставляет три новых метода для перемещения данных средствами виртуальной памяти, более эффективных по сравнению с массовым копированием данных [6] при передаче больших фрагментов данных. Аренда страниц позволяет передавать страницы из адресного пространства процесса взаймы другому процессу. Передача страниц позволяет легко вставлять в адресное пространство процесса страницы из ядра или другого процесса. Передача элементов карты позволяет копировать, использовать совместно или перемещать фрагменты виртуального адресного пространства между процессами. В настоящее время ведутся работы над подсистемами ввода-вывода ядра и межпроцессного взаимодействия над использованием этих средств для уменьшения стоимости перемещения данных.
Аренда страниц позволяет процессу безопасно делиться копией своей памяти, которая будет скопирована при попытке записи, с другими процессами, системой ввода-вывода или системой межпроцессного взаимодействия. Арендованная страница памяти может быть взята из отображаемого в память файла, из анонимной памяти или из их сочетания. Страницы могут быть переданы в аренду как фиксированные страницы подсистемы ввода-вывода ядра или как выгружаемые страницы аномнимной памяти для их передачи другому процессу. Арендованные страницы прозрачно копируются при ошибках записи в страницу, при выгрузке и при очистке памяти. Аренда также позволяет получать доступ к памяти с разбивкой на страницы без фрагментации или повреждения высокоуровневых структур данных отображения системы виртуальной памяти. В качестве примера, когда может быть использована аренда страницы, можно привести передачу данных через сокет. Вместо массового копирования данных из пользовательской памяти в память ядра, пользовательские страницы могут использоваться совместно с уровнем сокетов. Передача страниц позволяет легко вставлять страницы в адресное пространство процесса из подсистемы ввода-вывода, системы межпроцессного взаимодействия и из других процессов. Как только страницы вставлены в процесс, они становятся анонимной памятью. Такая анонимная память неотличима от анонимной памяти, выделенной обычным образом. Переданные страницы, скопированные из адресного пространства другого процесса, можно выгружать. Также, если механизм передачи страниц позволяет выбрать виртуальный адрес, по которому будут вставлены страницы, то обычно их можно вставить без фрамгентации и повреждения высокоуровневых структур данных отображения системы виртуальной памяти. Ядро может перемещать страницы других процессов, устойств ввода-вывода или самого ядра напрямую в адресное пространство принимающего процесса без копирования данных.
Передача элементов карты позволяет процессу и ядру обмениваться большими фрагментами их виртуальных адресных пространств при помощи высокоуровневых структур данных отображения системы виртуальной памяти. Этот механизм может копировать, перемещать или совместно использовать любой диапазон виртуального адресного пространства. Это может быть проблематичным для некоторых систем виртуальной памяти, потому что создаёт возможность совместного использования другими процессами областей памяти, копируемых при записи. Поскольку элемент карты передаётся через высокоуровневые структуры отображения, стоимость передачи элемента карты в пересчёте на страницу ниже, чем при аренде страниц или передаче страниц. Однако при малом количестве страниц повышается вероятность фрагментации элементов карты. Также передача элемента карты не может использоваться для совместного доступа к областями прямого доступа в память, с которыми работают некоторые подсистемы ядра. Передача записей карты может использоваться в качестве альтернативы каналам при передаче объёмных данных.
Предварительные измерения трёх механизмов перемещения данных UVM показывают, что механизмы перемещения данных средствами виртуальной памяти повышают производительность по сравнению с копированием данных при размере передаваемых данных больше страницы. Например, в наших тестах одностраничная аренда в сетевой подсистеме заняла на 26% меньше времени, чем копирование данных. Тесты с арендой многих страниц показали, что аренда может уменьшить время обработки ещё сильнее, например аренда 256 страниц заняла на 78% меньше времени, чем копирование данных. В настоящее время ведётся работа над определением эффективности этих механизмов в повседневных задачах.
Замена старой системы виртуальной памяти BSD на UVM улучшила и общую эффективность и производительность ядра BSD. Например, на рисунке 6 показано общее время, потраченное на выделение указанной анонимной памяти в системах виртуальной памяти BSD и UVM при ответвлении процесса-потомка и ожидании его завершения. На графике показаны результаты измерений для задач, требовательных к виртуальной памяти, таких как: создание нового адресного пространства, копирование отображений процесса-родителя в процесс-потомок, обработка копирования при записи и размещение адресного пространства процесса-потомка. На двух верхних графиках процесс-потомок осуществляет одну операцию записи в динамически выделенную память и завершает работу (инициируя таким образом исправление ошибки записи в область, требующую копирования). На нижних графиках процесс-потомок завершает работу без обращения к данным. В обоих случаях UVM заметно превосходит систему виртуальной памяти BSD.
Другой пример увеличения производительности UVM показан в таблице 3. В таблице показано среднее время миллиона циклов, требуемое на отображение страницы памяти, исправление ошибки доступа к странице и последующую отмену отображения страницы. UVM превосходит систему виртуальной памяти BSD во всех случаях. Отметим, что ошибка чтения в приватном отображении в системе виртуальной памяти BSD обходится дороже, чем ошибка чтения в совместно используемом отображении, потому что система виртуальной памяти BSD выделяет для отображения затеняющий объект (даже если это не нужно).
| Ошибки/отображение | BSD VM (мкс) | UVM (мкс) |
|---|---|---|
| Чтение/общий файл | 24 | 21 |
| Чтение/приватный файл | 48 | 22 |
| Запись/общий файл | 113 | 100 |
| Запись/приватный файл | 80 | 67 |
| Чтение/заполнено нулями | 60 | 49 |
| Запись/заполнено нулями | 60 | 48 |
Пользователи NetBSD также сообщили о положительном влиянии улучшений UVM на их приложения. Влияние заметнее всего при недостатке физической памяти, когда система виртуальной памяти выгружает данные, чтобы освободить память. В системе виртуальной памяти BSD выгрузка сопровождалась низкой отзывчивостью системы, в то время как с UVM система замедляется, но остаётся отзывчивой. Подобная ситуация может возникать при запуске приложений, интенсивно использующих много виртуальной памяти, таких как интерпретатор lisp, или при компиляции крупного проекта при работающем X-сервере на системе с малым количеством физической памяти. Кроме того пользователи старых архитектур, поддерживаемых NetBSD, отметили ускорение работы приложений. Например, на архитектуре VAX время запуска /etc/rc уменьшилось на 10% (10 секунд).
В UVM мы сосредоточили усилия на изучении ключевых структур данных и механизмов, используемых при управлении памятью. В последнее время велись небольшие работы в этой области, но больше работ было связано с расширяемой структурой операционной системы. UVM тесно интегрирована и содержит глобальные оптимизации, производящие положительное влияние на производительность системы. Расширяемые операционные системы предназначены для разделения и расширения функций операционной системы для нужд пользователей. Для этого есть много способов, включая создание аппаратуро-подобного интерфейса для приложений (экзоядра [11]), позволяющего встраивать в ядро код на типобезопасных языках (SPIN [1]) и позволяющего программным модулям соединяться в вертикальные слои (Scout [14,19]). Структуры данных и механизмы UVM не влияют на структуру операционной системы, влияние тесно связанных глобальных оптимизаций UVM на расширяемость не очевидно. Можно приспособить к этим системам наработки UVM. Например, в недавней работе над микроядром L4 [10] показано, как перенести Linux на L4 с минимальными издержками производительности. Однако, взаимодействие с другими расширениями может привести к негативным последствиям.
Наиболее близкими родственниками UVM являются система виртуальной памяти Mach [18] и система виртуальной памяти SunOS [4,9,13]. Поскольку система виртуальной памяти BSD основана на системе виртуальной памяти Mach, большая часть рассмотренных в этом документе особенностей системы виртуальной памяти BSD применима к обеим системам виртуальной памяти (и в меньшей степени к системе виртуальной памяти FreeBSD). Как было сказано в разделе 5, UVM вобрала и расширила части механизма управления анонимной памятью из исистемы виртуальной памяти SunOS. Дайсон и Гриман выбрали другой подход к улучшению структур данных виртуальной памяти BSD во FreeBSD, сохранив ту же базовую структуру, но избавившись от ненужных частей системы виртуальной памяти Mach, унаследованных BSD [16]. Система виртуальной памяти Linux [21] не предоставляет полнофункционального API, подобного pmap в Mach, вместо него для управления памятью используется обобщённый интерфейс на основе трёхуровневых таблиц страниц нижележащего оборудования. Все функции анонимной памяти управляются с помощью таблицы страниц. Это ограничивает возможность создания высокоуровневой абстракции для анонимных страниц памяти и не позволяет повторно использовать таблицы страниц при недостатке физической памяти. Недавняя работа над поддержкой в системе виртуальной памяти страниц разных размеров [8] позволет лучше группировать операции ввода-вывода, как при агрессивном группировании анонимной памяти при выгрузке страниц в UVM. Однако, при большом размере страниц выгружаемые данные необходимо предварительно скопировать в физически непрерывный блок памяти. UVM может динамически переназначать местонахождение анонимных областей подкачки с использованием страниц обычного размера без копирования данных.
В другой недавней работе внимание обращено на механизмы перемещения данных без копирования. IO-Lite [15] - это унифицированная система буферизации, основанная на Fbufs [7]. IO-Lite избегает копирования, делая все буферы неизменяемыми после инициализации и принуждая все операции ввода-вывода оперировать агрегатами буферов. IO-Lite не взаимодействует должным образом с отображаемыми в память файлами и не интегрирована с системой виртуальной памяти. Механизм избежания копирования TCP в Solaris [5] использует новый низкоуровневый API и поддержку со стороны оборудования ATM, не прибегая к высокоуровневому коду виртуальной памяти. Микроядро L4 [10] предоставляет потокам примитивы смены разрешений (remap), создания и отмены отображений, позволяющие быстро перемещать данные средствами виртуальной памяти, но копирование при записи и другие задачи обрабатываются программным обеспечением вышележащего уровня, таким как сервер Linux. Наконец, подсистема ввода-вывода Genie [3] позвляет операционной системе эмулировать API копирования средствами виртуальной памяти. Механизмы Genie могут быть применимы в UVM, если возникнет такая необходимость.
В этом документе мы представили UVM - новую систему виртуальной памяти для ядра BSD. Ключевые особенности архитектуры UVM:
В будущем в UVM планируется объединить кэш системы виртуальной памяти с буферным кэшем BSD, добавить поддержку большей асинхронности ввода-вывода (как для загрузки, так и выгрузки страниц), а также доработать ядро BSD для улучшения производительности приложений, воспользовавшись преимуществами новых механизмов перемещения данных UVM.
Мы хотим поблагодарить Оррана Кригера (Orran Krieger), Лорри Фэйт Краннор (Lorrie Faith Cranor) и анонимных рецензентов за их полезные комментарии черновиков этого документа.
B. Bershad et al.
Extensibility, safety and performance in the SPIN operating system.
In Proceedings of the Fifteenth Symposium on Operating System Principles, 1996.
D. Bobrow et al.
TENEX, a paged time sharing system for the PDP-10.
Communications of the ACM, 15(3), March 1972.
J. Brustoloni and P. Steenkiste.
Copy emulation in checksummed, multiple-packet communication.
In Proceedings of IEEE INFOCOM 1997, pages 1124-1132, April 1997.
H. Chartock and P. Snyder.
Virtual swap space in SunOS.
In Proceedings of the Autumn 1991 European UNIX Users Group Conference, September 1991.
H. Chu.
Zero-copy TCP in Solaris.
In Proceedings of the USENIX Conference, pages 253-264. USENIX, 1996.
C. Cranor.
Design and Implementation of the UVM Virtual Memory System.
Doctoral dissertation, Washington University, August 1998.
P. Druschel and L. Peterson.
Fbufs: A high-bandwidth cross-domain transfer facility.
In Proceedings of the Fourteenth ACM Symposium on Operating Systems Principles, December 1993.
N. Ganapathy and C. Schimmel.
General purpose operating system support for multiple page sizes.
In Proceedings of the USENIX Conference. USENIX, 1998.
R. Gingell, J. Moran, and W. Shannon.
Virtual memory architecture in SunOS.
In Proceedings of USENIX Summer Conference, pages 81-94. USENIX, June 1987.
H. Härtig, M. Hohmuth, J. Liedtke, S. Schönberg, and J. Wolter.
The performance of μ-kernel-based systems.
In Proceedings of the ACM Symposium on Operating Systems Principles, 1997.
M. Kaashoek et al.
Application performance and flexibility on Exokernel systems.
In Proceedings of the Sixteenth Symposium on Operating System Principles, October 1997.
M. McKusick, K. Bostic, M. Karels, and J. Quarterman.
The Design and Implementation of the 4.4BSD Operating SystemПП1
.Addison Wesley, 1996.
J. Moran.
SunOS virtual memory implementation.
In Proceedings of the Spring 1988 European UNIX Users Group Conference, April 1988.
D. Mosberger and L. Peterson.
Making paths explicit in the Scout operating system.
In Operating Systems Design and Implementation (OSDI), pages 153-168, 1996.
V. Pai, P. Druschel, and W. Zwaenepoel.
IO-Lite: a unified I/O buffering and caching system.
In Operating Systems Design and Implementation (OSDI), pages 15-28. USENIX, 1999.
Проект FreeBSD.
Операционная система FreeBSD.
Более подробную информацию см. по ссылке https://www.freebsd.org.
Проект NetBSD.
Операционная система NetBSD.
Более подробную информацию см. по ссылке https://www.netbsd.org.
R. Rashid et al.
Machine-independent virtual memory management for paged uniprocessor and multiprocessor architectures.
IEEE Transactions on Computing, 37(8), August 1988.
O. Spatscheck and L. Peterson.
Defending against denial of service attacks in Scout.
In Operating Systems Design and Implementation (OSDI), pages 59-72. USENIX, 1999.
R. Stevens.
TCP/IP Illustrated, Volume 2: The Implementation.
Addison-Wesley, 1995.
Л. Торвальдс и другие.
Операционная система Linux.
Более подробную информацию см. по ссылке https://www.linux.org.
Автор перевода на русский язык: Владимир Ступин