Распределение памяти партнера

Метод распределения памяти партнера - это алгоритм выделения памяти, который разделяет память на разделы, чтобы попытаться удовлетворить запрос памяти как можно более подходящим образом. Эта система использует разделение памяти на половинки, чтобы попытаться подобрать наилучшее соответствие. Согласно Дональду Кнуту, система друзей была изобретена в 1963 году Гарри Марковицем и впервые была описана Кеннетом К. Ноултоном (опубликовано в 1965 году). Распределение памяти Buddy относительно легко реализовать. Он поддерживает ограниченное, но эффективное разделение и объединение блоков памяти.

• 1 Алгоритм
  • 1.1 Пример
• 2 Реализация и эффективность
• 3 См. Также
• 4 Ссылки

Существуют различные формы приятельской системы; те, в которых каждый блок разделен на два меньших блока, являются самой простой и наиболее распространенной разновидностью. Каждый блок памяти в этой системе имеет порядок, где порядок является целым числом от 0 до определенного верхнего предела. Размер блока порядка n пропорционален 2, так что размер блоков ровно в два раза превышает размер блоков, которые на один порядок меньше. Размеры блоков, равные степени двойки, упрощают вычисление адресов, поскольку все партнеры выровнены по границам адресов памяти, которые являются степенью двойки. Когда большой блок разделяется, он делится на два меньших блока, и каждый меньший блок становится уникальным другом для другого. Разделенный блок можно объединить только с его уникальным партнерским блоком, который затем преобразует более крупный блок, из которого они были отделены.

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

Затем программист должен решить или написать код для получения максимально возможного порядка, который может поместиться в оставшемся доступном пространстве памяти. Поскольку общая доступная память в данной компьютерной системе может не быть кратной минимальному размеру блока в степени двойки, наибольший размер блока может не охватывать всю память системы. Например, если в системе было 2000 КБ физической памяти и размер блока нулевого порядка был 4 КБ, верхний предел порядка был бы 8, поскольку блок порядка 8 (256 блоков нулевого порядка, 1024 КБ) равен самый большой блок, который уместится в памяти. Следовательно, невозможно выделить всю физическую память в одном фрагменте; оставшиеся 976 КБ памяти должны быть выделены меньшими блоками.

Пример

Ниже приводится пример того, что происходит, когда программа запрашивает память. Допустим, в этой системе наименьший возможный блок имеет размер 64 килобайта, а верхний предел для порядка равен 4, что приводит к максимально возможному размещаемому блоку, 2 раза по 64 КБ = 1024 КБ. Ниже показано возможное состояние системы после различных запросов к памяти.

Это распределение могло произойти следующим образом:

1. Исходная ситуация.
2. Программа A запрашивает память 34 КБ, порядок 0.
   1. Блоки порядка 0 недоступны, поэтому блок порядка 4 разделяется, создавая два блока порядка 3.
   2. По-прежнему нет доступных блоков порядка 0, поэтому блок первого порядка 3 разделяется, создавая два блока порядка 2.
   3. По-прежнему нет доступных блоков порядка 0, поэтому первый блок порядка 2 - s plit, создавая два блока порядка 1.
   4. По-прежнему нет доступных блоков порядка 0, поэтому первый блок порядка 1 разделяется, создавая два блока порядка 0.
   5. Теперь доступен блок порядка 0, поэтому он выделяется A.
3. Программа B запрашивает память 66 КБ, порядок 1. Доступен блок порядка 1, поэтому он выделяется B.
4. Программа C запрашивает память 35 КБ, порядок 0. Доступен блок порядка 0, поэтому он выделяется C.
5. Программа D запрашивает память 67 КБ, порядок 1.
   1. Блоки порядка 1 недоступны, поэтому блок порядка 2 разделяется., создавая два блока порядка 1.
   2. Теперь доступен блок порядка 1, поэтому он выделен для D.
6. Программа B освобождает свою память, освобождая один блок порядка 1.
7. Программа D освобождает свою память.
   1. Освобождается один блок порядка 1.
   2. Так как блок-партнер только что освобожденного блока также свободен, они объединяются в один блок порядка 2.
8. Программа A освобождает свою память, освобождая один блок порядка 0.
9. Программа C освобождает свою память.
   1. Освобождается один блок порядка 0.
   2. Поскольку блок-партнер вновь освобожденного блока также является свободным, они объединяются в один блок порядка 1.
   3. Поскольку Партнерский блок вновь сформированного блока порядка 1 также является свободным, два объединяются в один блок порядка 2.
   4. Поскольку партнерский блок вновь сформированного блока порядка 2 также свободен, два объединяются в один блок порядка 3.
   5. Поскольку вспомогательный блок вновь сформированного блока порядка 3 также свободен, они объединяются в один блок порядка 4.

Как вы можете видеть, что происходит, когда запрос памяти делается следующим образом:

• Если память должна быть выделена

1. Найдите слот памяти подходящего размера (минимальные 2 блока, которые больше или равны блокам запрошенной памяти)
   1. Если он найден, он выделяется программе
   2. Если нет, он пытается освободить подходящий слот памяти. Система делает это, пытаясь сделать следующее:
      1. Разделить свободный слот памяти, превышающий запрошенный размер памяти, на половину
      2. Если достигнут нижний предел, выделите этот объем памяти
      3. Вернитесь к шагу 1 (найдите слот памяти подходящего размера)
      4. Повторяйте этот процесс, пока не будет найден подходящий слот памяти

• Если память должна быть освобождена

1. Освободите блок памяти
2. Посмотрите на соседний блок - он тоже свободен?
3. Если да, объедините их, вернитесь к шагу 2 и повторяйте этот процесс, пока не будет достигнут верхний предел (вся память освобождена) или до тех пор, пока не будет обнаружен несвободный соседний блок

По сравнению с другими более простыми методами, такими как динамическое выделение, система партнерской памяти имеет небольшую внешнюю фрагментацию и допускает сжатие памяти с небольшими накладными расходами. Партнерский метод освобождения памяти является быстрым, при этом максимальное количество требуемых уплотнений равно log 2 (высший порядок). Обычно система распределения вспомогательной памяти реализуется с использованием двоичного дерева для представления используемых или неиспользуемых разделенных блоков памяти. «Друг» каждого блока может быть найден с помощью исключающего ИЛИ адреса блока и его размера.

Однако по-прежнему существует проблема внутренней фрагментации - память тратится впустую, потому что запрошенная память немного больше, чем маленький блок, но намного меньше, чем большой блок. Из-за того, как работает метод распределения памяти напарника, программе, запрашивающей 66 КБ памяти, будет выделено 128 КБ, что приведет к потере 62 КБ памяти. Эта проблема может быть решена с помощью выделения блоков, которое может быть наложено поверх более грубого вспомогательного распределителя, чтобы обеспечить более детальное распределение.

Одна версия алгоритма распределения партнеров была подробно описана Дональдом Кнутом в томе 1 книги Искусство компьютерного программирования. Ядро Linux также использует систему приятелей с дальнейшими модификациями для минимизации внешней фрагментации, а также различные другие распределители для управления памятью внутри блоков.

jemalloc- это современный распределитель памяти, который использует, среди прочего, приятельская техника.

• Пул памяти
• Распределение памяти на основе стека

1. ^Кеннет К. Ноултон. Распределитель быстрого хранилища. Сообщения ACM 8 (10): 623–625, октябрь 1965 г. также Кеннет К. Ноултон. Описание L6 программистом. Сообщения ACM, 9 (8): 616–625, август 1966 г. [см. Также: Google books [1] стр. 85]
2. ^Кнут, Дональд (1997). Фундаментальные алгоритмы. Искусство программирования. 1(Второе изд.). Ридинг, Массачусетс: Эддисон-Уэсли. С. 435–455. ISBN 0-201-89683-4.
3. ^Мауэрер, Вольфганг (октябрь 2008 г.). Профессиональная архитектура ядра Linux. Wrox Нажмите. ISBN 978-0-470-34343-2.
4. ^Эванс, Джейсон (16 апреля 2006 г.), Масштабируемая параллельная реализация malloc (3)Реализация для FreeBSD (PDF), стр. 4–5