<<
>>

Алгоритм выделения памяти

Linux поддерживает несколько механизмов выделения памяти. Главным механизмом для выделения новых страничных блоков физической памяти является распределитель страниц (page allocator), который работает при помощи широко известного «приятельского» алгоритма.

Основная идея управления блоками памяти заключается в следующем. Изначально память состоит из единого непрерывного участка. В нашем примере на рис. 10.10, а размер этого участка равен 64 страницам. Когда поступает запрос на выделение памяти, он сначала округляется до степени числа 2, например до 8 страниц. Затем весь блок памяти делится пополам (рис. 10.10, б). Так как получившиеся в результате этого деления участки памяти все еще слишком велики, нижняя половина делится пополам еще (рис. 10.10, в) и еще (рис. 10.10, г). Теперь мы получили участок памяти нужного размера, поэтому он предоставляется вызвавшему процессу (затенен на рис. 10.10, г).

Теперь предположим, что приходит второй запрос на 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.

<< | >>
Источник: Э. ТАНЕНБАУМ Х. БОС. СОВРЕМЕННЫЕ ОПЕРАЦИОННЫЕ СИСТЕМ Ы 4-е ИЗДАНИЕ. 2015

Еще по теме Алгоритм выделения памяти:

  1. Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
  2. Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
  3. АЛГОРИТМ
  4. АЛГОРИТМ УДАЧИ
  5. Статья 109. Выделение
  6. Алгоритм исцеления:
  7. Правило выделения
  8. Алгоритм избавления от боли
  9. ПРЕДСТАВЛЕНИЕ ПАМЯТИ
  10. § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
  11. Алгоритм обработки результатов.
  12. 2. Специфика и алгоритмы работы с источниками.
  13. Правило выделения
  14. Гигиена памяти.
  15. выделение единиц анализа
  16. Порядок выделения подкреплений.
  17. укрепление памяти
  18. СИСТЕМНАЯ ДИАГНОСТИКА АЛГОРИТМ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ПРИЧИН ПОВРЕЖДЕНИЙ ВСЕХ СЕМИ ТЕЛ ЧЕЛОВЕКА.