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

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

Алгоритм

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

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

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

Пример

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

Шаг	64 К	64 К	64 К	64 К	64 К	64 К
1	2 ⁴
2.1	2 ³					2 ³
2.2	2 ²			2 ²		2 ³
2.3	2 ¹		2 ¹	2 ²		2 ³
2.4	2 ⁰	2 ⁰	2 ¹	2 ²		2 ³
2.5	А: 2 ⁰	2 ⁰	2 ¹	2 ²		2 ³
3	А: 2 ⁰	2 ⁰	Б: 2 ¹	2 ²		2 ³
4	А: 2 ⁰	С: 2 ⁰	Б: 2 ¹	2 ²		2 ³
5.1	А: 2 ⁰	С: 2 ⁰	Б: 2 ¹	2 ¹	2 ¹	2 ³
5.2	А: 2 ⁰	С: 2 ⁰	Б: 2 ¹	Д: 2 ¹	2 ¹	2 ³
6	А: 2 ⁰	С: 2 ⁰	2 ¹	Д: 2 ¹	2 ¹	2 ³
7.1	А: 2 ⁰	С: 2 ⁰	2 ¹	2 ¹	2 ¹	2 ³
7.2	А: 2 ⁰	С: 2 ⁰	2 ¹	2 ²		2 ³
8	2 ⁰	С: 2 ⁰	2 ¹	2 ²		2 ³
9.1	2 ⁰	2 ⁰	2 ¹	2 ²		2 ³
9.2	2 ¹		2 ¹	2 ²		2 ³
9.3	2 ²			2 ²		2 ³
9.4	2 ³					2 ³
9.5	2 ⁴

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

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

Как видите, при запросе памяти происходит следующее:

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

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

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

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

Внедрение и эффективность

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

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

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

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

См. также

Ссылки

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

[1] Кеннет К. Ноултон. Быстрый распределитель памяти. Сообщения ACM 8(10):623–625, октябрь 1965 г., а также Кеннет К. Ноултон. Описание программиста L6. Communications of ACM , 9(8):616–625, август 1966 г. [см. также: книги Google [1], стр. 85]

[2] Кнут, Дональд (1997). Фундаментальные алгоритмы . Искусство компьютерного программирования . Том. 1 (Второе изд.). Ридинг, Массачусетс: Аддисон-Уэсли. стр. 435–455. ISBN 0-201-89683-4 .

[3] Мауэрер, Вольфганг (октябрь 2008 г.). Профессиональная архитектура ядра Linux . Врокс Пресс . ISBN 978-0-470-34343-2 .

[4] Эванс, Джейсон (16 апреля 2006 г.), Масштабируемый параллелизм malloc(3) Реализация для FreeBSD (PDF) , стр. 4–5.

[1]

[2]

[3]

[4]