Распределение памяти приятеля - Buddy memory allocation

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

Алгоритм

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

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

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

Пример

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

Шаг	64 К	64 К	64 К	64 К	64 К	64 К	64 К	64 К	64 К	64 К	64 К	64 К	64 К	64 К	64 К	64 К
1	2^4
2.1	2^3								2^3
2.2	2^2				2^2				2^3
2.3	2^1		2^1		2^2				2^3
2.4	2^0	2^0	2^1		2^2				2^3
2.5	А: 2^0	2^0	2^1		2^2				2^3
3	А: 2^0	2^0	БИ 2^1		2^2				2^3
4	А: 2^0	С: 2^0	БИ 2^1		2^2				2^3
5.1	А: 2^0	С: 2^0	БИ 2^1		2^1		2^1		2^3
5.2	А: 2^0	С: 2^0	БИ 2^1		Д: 2^1		2^1		2^3
6	А: 2^0	С: 2^0	2^1		Д: 2^1		2^1		2^3
7.1	А: 2^0	С: 2^0	2^1		2^1		2^1		2^3
7.2	А: 2^0	С: 2^0	2^1		2^2				2^3
8	2^0	С: 2^0	2^1		2^2				2^3
9.1	2^0	2^0	2^1		2^2				2^3
9.2	2^1		2^1		2^2				2^3
9.3	2^2				2^2				2^3
9.4	2^3								2^3
9.5	2^4

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

1. Исходная ситуация.
2. Программа A запрашивает память 34 КБ, порядок 0.
   1. Блоки порядка 0 недоступны, поэтому блок порядка 4 разделяется, создавая два блока порядка 3.
   2. По-прежнему нет доступных блоков порядка 0, поэтому блок первого порядка 3 разделяется, создавая два блока порядка 2.
   3. По-прежнему нет доступных блоков порядка 0, поэтому блок первого порядка 2 разделяется, создавая два блока порядка 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^k блок, который больше или равен запрошенной памяти)
   1. Если он найден, он передается программе
   2. Если нет, то пытается сделать подходящий слот памяти. Система делает это, пробуя следующее:
      1. Разделите свободный слот памяти, превышающий запрошенный размер, пополам
      2. Если достигнут нижний предел, выделите этот объем памяти
      3. Вернитесь к шагу 1 (найдите слот памяти подходящего размера)
      4. Повторяйте этот процесс, пока не найдете подходящий слот памяти.

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

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

Реализация и эффективность

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

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

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

джемаллок^[4] это современный распределитель памяти, в котором, помимо прочего, используется метод приятеля.

Смотрите также

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

Рекомендации

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 Press. ISBN  978-0-470-34343-2.
4. Эванс, Джейсон (16 апреля 2006 г.), Масштабируемый одновременный доступ маллок (3) Реализация для FreeBSD (PDF), стр. 4–5