stringtranslate.com

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

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

Алгоритм

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

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

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

Пример

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

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

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

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

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

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

Одна из версий алгоритма распределения памяти Buddy была подробно описана Дональдом Кнутом в первом томе книги The Art of Computer Programming . [2] Ядро Linux также использует систему Buddy с дальнейшими модификациями для минимизации внешней фрагментации, а также различные другие распределители для управления памятью внутри блоков. [3]

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

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

Ссылки

  1. ^ Кеннет К. Ноултон. Быстрый распределитель памяти. Communications of the ACM 8(10):623–625, октябрь 1965 г. также Кеннет К. Ноултон. Программистское описание L6. Communications of the ACM , 9(8):616–625, август 1966 г. [см. также: Google books [1] стр. 85]
  2. ^ Кнут, Дональд (1997). Фундаментальные алгоритмы . Искусство программирования . Том 1 (Второе изд.). Рединг, Массачусетс: Addison-Wesley. С. 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