Добавлен: 29.10.2018
Просмотров: 48082
Скачиваний: 190
10.4. Управление памятью в Linux
831
64-разрядных машинах семейства x86 для адресации используется не более 48 бит,
следовательно, для адресуемой памяти существует теоретический лимит размером
256 Тбайт. Linux разделяет эту память между ядром и пространством пользователя, что
дает каждому процессу максимальное виртуальное пространство объемом 128 Тбайт.
Адресное пространство создается при инициализации процесса и переписывается с по-
мощью системного вызова exec.
Чтобы несколько процессов могли совместно использовать физическую память, Linux
отслеживает использование физической памяти, выделяет при необходимости допол-
нительную память пользовательским процессам и компонентам ядра, динамически
отображает области физической памяти на адресное пространство разных процессов,
а также динамически доставляет в память и убирает из нее исполняемые программы,
файлы и прочую информацию состояния (по мере необходимости) — чтобы эффектив-
но использовать ресурсы платформы и обеспечить продвижение процесса выполнения.
Остальная часть данной главы описывает реализацию различных механизмов ядра
Linux, которые отвечают за эти операции.
Управление физической памятью
Вследствие различных аппаратных ограничений, имеющихся на многих системах, не
вся их физическая память одинакова, особенно в отношении ввода-вывода и виртуаль-
ной памяти. Linux различает три зоны памяти:
1. ZONE_DMA — это страницы, которые можно использовать для операций DMA.
2. ZONE_NORMAL — это нормальные отображаемые страницы.
3. ZONE_HIGHMEM — это страницы с адресами в верхней области памяти, которые
не имеют постоянного отображения.
Точные границы и компоновка этих зон памяти зависят от архитектуры. На плат-
формах х86 некоторые устройства могут выполнять операции DMA только в первых
16 Мбайт адресного пространства, следовательно, ZONE_DMA находится в диапазоне
от 0 до 16 Мбайт. На 64-разрядных машинах имеется дополнительная поддержка для
таких устройств, которая может выполнять 32-разрядные операции DMA, и эта об-
ласть имеет метку ZONE_DMA32. Кроме того, если оборудование наподобие ранних
выпусков i386 не может непосредственно отображать адреса памяти выше 896 Мбайт,
то все, что выше этой отметки, соответствует ZONE_HIGHMEM. А к ZONE_NORMAL
относится все, что между ними. Поэтому на 32-разрядных платформах х86 пер-
вые 896 Мбайт адресного пространства Linux отображаются напрямую, а остальные
128 Мбайт адресного пространства ядра используются для доступа к верхним областям
памяти. На x86 64 ZONE_HIGHMEM не определена. Ядро поддерживает структуру
zone для каждой из этих трех зон и может выполнять выделение памяти для каждой
из них по отдельности.
Основная память в Linux состоит из трех частей. Первые две части — ядро и карта
памяти — прикреплены в памяти (то есть никогда не вытесняются). Остальная память
разделена на страничные блоки, каждый из которых может содержать страницу текста,
данных или стека, страницу с таблицей страниц или находиться в списке свободных.
Ядро поддерживает карту памяти, которая содержит всю информацию об использо-
вании физической памяти системы (такую, как зоны, свободные страничные блоки
и т. д.). Эта информация (рис. 10.8) организована следующим образом. Прежде всего,
832
Глава 10. Изучение конкретных примеров: Unix, Linux и Android
Linux поддерживает массив дескрипторов страниц (page descriptors) типа page для
каждого физического страничного блока системы (он называется mem_map). Каждый
дескриптор страницы содержит: указатель на адресное пространство, к которому при-
надлежит страница (если она не свободна); пару указателей, которые позволяют ему
сформировать дважды связанный список с другими дескрипторами (например, чтобы
собрать вместе все свободные страничные блоки), а также несколько прочих полей. На
рис. 10.8 дескриптор страницы 150 содержит отображение на то адресное пространство,
к которому принадлежит данная страница. Страницы 70, 80 и 200 свободны и связаны
вместе. Размер дескриптора страницы равен 32 байтам, поэтому вся mem_map может
занимать менее 1 % физической памяти (при размере страничного блока 4 Кбайт).
Рис. 10.8. Представление памяти в Linux
Поскольку физическая память разделена на зоны, для каждой зоны Linux поддержи-
вает дескриптор зоны (zone descriptor). Этот дескриптор содержит информацию об
использовании памяти в зоне, такую как количество активных и неактивных страниц,
нижний и верхний пределы для алгоритма замещения страниц (который будет описан
далее в этой главе), а также много других полей.
Кроме того, дескриптор зоны содержит массив свободных областей. i-й элемент этого
массива указывает первый дескриптор страницы первого блока из 2
i
свободных стра-
ниц. Поскольку может существовать много блоков из 2
i
свободных страниц, то Linux
использует в каждом элементе page пару указателей на дескрипторы страниц (чтобы
10.4. Управление памятью в Linux
833
связать их вместе). Эта информация используется в операциях выделения памяти.
На рис. 10.8 область free_area[0] (которая идентифицирует все свободные области
памяти, состоящие только из одного страничного блока (поскольку 2
0
= 1)) указывает
на страницу 70 — первую из трех свободных областей. Остальные свободные блоки
размера 1 можно найти по ссылкам в каждом дескрипторе страниц.
И наконец, поскольку Linux является переносимой на архитектуру NUMA (где разные
физические адреса имеют очень сильно различающееся время доступа), для различения
физической памяти различных узлов (и во избежание выделения структур данных
в чужих узлах) используется дескриптор узла (node descriptor). Каждый дескриптор
узла содержит информацию об использовании памяти и зонах данного конкретного
узла. На платформах UMA система Linux описывает всю память при помощи одного
дескриптора узла. Первые несколько битов каждого дескриптора страниц используют-
ся для идентификации узла и зоны, к которой принадлежит данный страничный блок.
Чтобы механизм подкачки был эффективен на архитектурах х32 и х64, система Linux
использует четырехуровневую страничную организацию. Трехуровневая схема была
реализована в системе для процессора Alpha, она была расширена после версии
Linux 2.6.10, и начиная с версии 2.6.11 используется четырехуровневая схема. Каждый
виртуальный адрес разбивается на пять полей, как показано на рис. 10.9. Поля катало-
гов используются как индекс в соответствующем каталоге страниц (каждый процесс
имеет свой приватный каталог). Обнаруженное значение является указателем на один
из каталогов следующего уровня, которые тоже проиндексированы полем из виртуаль-
ного адреса. Выбранный элемент среднего каталога страниц указывает на окончатель-
ную таблицу страниц, проиндексированную полем страницы из виртуального адреса.
Найденный здесь элемент содержит указатель на нужную страницу. На компьютерах
с процессором Pentium используется только двухуровневая организация страниц.
В этом случае каждый из верхних и средних каталогов страниц содержит только одну
запись. Таким образом, элемент глобального каталога фактически указывает на табли-
цу страниц. При необходимости может использоваться и трехуровневая страничная
организация, для этого размер поля верхнего каталога страниц устанавливается в нуль.
Физическая память используется для различных целей. Само ядро жестко фиксиро-
вано — ни одна из его частей никогда не выгружается на диск. Остальная часть памяти
доступна для страниц пользователей, страничного кэша и других задач. Страничный
кэш содержит страницы с блоками файлов, которые недавно считаны или были считаны
заранее (в надежде на то, что они скоро могут понадобиться), либо страницы с блоками
файлов, которые надо записать на диск (например, созданные процессами пользователь-
ского режима, которые были выгружены на диск). Его размер динамически меняется,
причем он состязается за один и тот же пул страниц с пользовательскими процессами.
Страничный кэш в действительности не является настоящим отдельным кэшем, а пред-
ставляет собой набор страниц пользователя, которые более не нужны и ожидают выгруз-
ки на диск. Если страница, находящаяся в страничном кэше, потребуется снова (прежде,
чем она будет удалена из памяти), то ее можно быстро получить обратно.
Кроме того, операционная система Linux поддерживает динамически загружаемые
модули, в основном драйверы устройств. Они могут быть произвольного размера,
и каждому из них должен быть выделен непрерывный участок в памяти ядра. Для вы-
полнения этих требований система Linux управляет физической памятью таким обра-
зом, что она может получить по желанию участок памяти произвольного размера. Для
этого используется так называемый дружественный (или «приятельский») алгоритм
(buddy algorithm) . Он описан далее.
834
Глава 10. Изучение конкретных примеров: Unix, Linux и Android
Рис. 10.9. В Linux используются четырехуровневые таблицы страниц
Алгоритм выделения памяти
Linux поддерживает несколько механизмов выделения памяти. Главным механизмом
для выделения новых страничных блоков физической памяти является распреде-
литель
страниц (page allocator), который работает при помощи широко известного
«приятельского» алгоритма.
Основная идея управления блоками памяти заключается в следующем. Изначально
память состоит из единого непрерывного участка. В нашем примере на рис. 10.10, а
размер этого участка равен 64 страницам. Когда поступает запрос на выделение па-
мяти, он сначала округляется до степени числа 2, например до 8 страниц. Затем весь
блок памяти делится пополам (рис. 10.10, б). Так как получившиеся в результате этого
деления участки памяти все еще слишком велики, нижняя половина делится пополам
еще (рис. 10.10, в) и еще (рис. 10.10, г). Теперь мы получили участок памяти нужного
размера, поэтому он предоставляется вызвавшему процессу (затенен на рис. 10.10, г).
Рис. 10.10. Работа «приятельского» алгоритма
10.4. Управление памятью в Linux
835
Теперь предположим, что приходит второй запрос на 8 страниц. Он может быть удов-
летворен немедленно (рис. 10.10, д). Следом поступает запрос на 4 страницы. Наи-
меньший из имеющихся участков делится надвое (рис. 10.10, е), и выделяется половина
(рис. 10.10, ж). Затем освобождается второй 8-страничный участок (рис. 10.10, з).
Наконец, освобождается другой 8-страничный участок. Поскольку эти два смежных
только что освободившихся участка были «приятелями» (то есть они вышли из одного
16-страничного блока), то они снова объединяются в 16-страничный блок (рис. 10.10, и).
Операционная система Linux управляет памятью при помощи «приятельского» алго-
ритма. В дополнение к нему имеется массив, в котором первый элемент представляет
собой начало списка блоков размером в 1 единицу, второй элемент является началом
списка блоков размером в 2 единицы, третий элемент — началом списка блоков раз-
мером в 4 единицы и т. д. Таким образом, можно быстро найти любой блок, размер
которого кратен степени 2.
Этот алгоритм приводит к существенной внутренней фрагментации, так как если вам
нужен 65-страничный участок, то вы должны будете запросить и получите 128-стра-
ничный блок.
Чтобы решить эту проблему, в системе Linux есть второй механизм выделения памя-
ти — распределитель фрагментов (slab allocator), выбирающий блоки памяти при по-
мощи «приятельского» алгоритма, а затем нарезающий из этих блоков более мелкие
куски и управляющий ими по отдельности.
Поскольку ядро часто создает и уничтожает объекты определенных типов (например,
task_struct), то оно зависит от так называемых кэшей объектов (object caches). Эти
кэши состоят из указателей на один или несколько кусков, в которых может храниться
несколько объектов одного типа. Каждый из этих кусков может быть полным, частично
заполненным или пустым.
Например, когда ядру нужно выделить новый дескриптор процесса (то есть новую
task_struct), оно ищет в кэше объектов структуры задач и сначала пытается найти
частично заполненный кусок и выделить новую task_struct в нем. Если такого куска
нет, то оно просматривает список пустых кусков. Наконец (при необходимости) оно
выделит новый кусок, поместит в него новую структуру задач и свяжет этот кусок
с кэшем объектов структур задач. Служба ядра kmalloc, которая выделяет физически
смежные области памяти в адресном пространстве ядра, фактически построена поверх
интерфейса кусков и кэша объектов (описанного здесь).
Есть и третий механизм выделения памяти — vmalloc, который используется в тех
случаях, когда запрошенная память должна быть смежной только в виртуальном про-
странстве, а не в физической памяти. На практике это справедливо для большей части
запрашиваемой памяти. Одним из исключений являются устройства, которые живут
на другой стороне от шины памяти и блока управления памятью (и поэтому не пони-
мают виртуальных адресов). Однако использование vmalloc приводит к некоторому
падению производительности, поэтому он применяется в основном для выделения
больших количеств непрерывного виртуального адресного пространства (например,
для динамической вставки модулей ядра). Все эти механизмы выделения памяти ведут
свое происхождение от System V.
Представление виртуального адресного пространства
Виртуальное адресное пространство делится на однородные, непрерывные и выровнен-
ные по границам страниц области. То есть каждая область состоит из участка смежных