В этой главе мы сделаем небольшой поворот в сторону от нашего обсуждения виртуализации памяти, чтобы обсудить фундаментальный аспект любой системы управления памятью, будь то библиотека malloc (управление страницами кучи процесса) или сама ОС (управление частями адресного пространства процесса). В частности, мы обсудим вопросы, связанные с управлением свободным пространством (free-space management).
Давайте сделаем проблему более конкретной. Управление свободным пространством, безусловно, может быть простым, это мы увидим, когда обсудим концепцию подкачки (paging). Менеджмент становится проще, когда управляемое пространство разделено на единицы фиксированного размера; в таком случае вы просто ведете список этих единиц; когда клиент запрашивает одну из них первую запись.
Более сложный (и интересный) случай возникает, когда свободное пространство, которым вы управляете, состоит из единиц переменного размера; это происходит в библиотеке распределения памяти на уровне пользователя (как в malloc() и free()) и в ОС, управляющей физической памятью при использовании сегментации для реализации виртуальной памяти. В любом случае проблема, которая существует, известна как внешняя фрагментация: свободное пространство разрезается на маленькие кусочки разных размеров и, таким образом, фрагментируется; последующие запросы могут завершиться неудачей, поскольку нет ни одного смежного пространства, которое могло бы удовлетворить запрос, даже если общий объем свободного пространства превышает размер запроса.
На рисунке показан пример этой проблемы. В этом случае общее доступное свободное пространство составляет 20 байт; к сожалению, оно фрагментировано на два куска размером 10 каждый. В результате запрос на 15 байт завершится неудачей, даже если есть свободные 20 байт. Таким образом, мы подходим к проблеме, рассматриваемой в этой главе.
Проблема: КАК УПРАВЛЯТЬ СВОБОДНЫМ ПРОСТРАНСТВОМ
Как следует управлять свободным пространством при удовлетворении запросов переменного размера? Какие стратегии можно использовать для минимизации фрагментации? Каковы временные и пространственные накладные расходы альтернативных подходов?
Предположения
Most of this discussion will focus on the great history of allocators found in user level memory-allocation libraries. We draw on Wilson’s excellent survey [W+95] but encourage interested readers to go to the source document itself for more details1.
Большая часть этого обсуждения будет сосредоточена на большой истории аллокаторов (allocators), найденных в библиотеках распределения памяти на уровне пользователя. Мы опираемся на отличное исследование Уилсона*, но призываем заинтересованных читателей обратиться к самому исходному документу для получения более подробной информации.
* “Dynamic Storage Allocation: A Survey and Critical Review” by Paul R. Wilson, Mark S. Johnstone, Michael Neely, David Boles. International Workshop on Memory Management, Scotland, UK, September 1995. An excellent and far-reaching survey of many facets of memory allocation. Far too much detail to go into in this tiny chapter!
Мы предполагаем базовый интерфейс, такой как тот, который предоставляется malloc() и free(). В частности, void *malloc(size t size) принимает один параметр size, который представляет собой количество байтов, запрашиваемых приложением; он возвращает указатель (не определенного типа или указатель void на языке Си) в область такого размера (или больше). Дополнительная процедура void free(void *ptr) берет указатель и освобождает соответствующий фрагмент. Обратите внимание на подтекст интерфейса: пользователь, освобождая пространство, не сообщает библиотеке его размер; таким образом, библиотека должна быть в состоянии вычислить, насколько велик кусок памяти, когда ей вручают только указатель на него. О том, как это сделать, мы поговорим чуть позже.
Пространство, которым управляет эта библиотека, исторически известно как куча, а общая структура данных, используемая для управления свободным пространством в куче, является своего рода свободным списком. Эта структура содержит ссылки на все свободные куски пространства в управляемой области памяти. Конечно, эта структура данных не должна быть списком как таковым, а просто какой-то структурой данных для отслеживания свободного пространства.
Далее мы предполагаем, что в первую очередь мы имеем дело с внешней фрагментацией, как описано выше. Распределители (allocators), конечно, могут также иметь проблему внутренней фрагментации; если распределитель раздает куски памяти больше, чем запрошено, любое непрошенное (и, следовательно, неиспользуемое) пространство в таком куске считается внутренней фрагментацией (потому что фрагментация происходит внутри выделенного блока) и является еще одним примером потери пространства. Однако для простоты и потому, что это наиболее интересный из двух типов фрагментации, мы в основном сосредоточимся на внешней фрагментации.
Мы также предположим, что, как только память передается клиенту, она не может быть перемещена в другое место в памяти. Например, если программа вызывает malloc() и получает указатель на некоторое пространство в куче, эта область памяти по существу “принадлежит” программе (и не может быть перемещена библиотекой) до тех пор, пока программа не вернет ее через соответствующий вызов free(). Таким образом, никакое уплотнение свободного пространства невозможно, что было бы полезно для борьбы с фрагментацией. Однако сжатие может быть использовано в ОС для борьбы с фрагментацией при реализации сегментации (как обсуждалось в упомянутой главе о сегментации).
Наконец, предположим, что распределитель управляет смежной областью байтов. В некоторых случаях распределитель может запросить увеличение этой области; например, библиотека распределения памяти на уровне пользователя может вызвать ядро для увеличения кучи (через системный вызов, такой как sbrk), когда у нее заканчивается место. Однако для простоты мы просто предположим, что область имеет один фиксированный размер на протяжении всей своей жизни.
Механизмы низкого уровня
Прежде чем углубляться в некоторые детали политики, мы сначала рассмотрим некоторые общие механизмы, используемые в большинстве распределителей (allocators). Во-первых, мы обсудим основы расщепления и коалесцирования, общие методы в большинстве распределителей. Во-вторых, мы покажем, как можно быстро и относительно легко отслеживать размер выделенных областей. Наконец, мы обсудим, как построить простой список внутри свободного пространства, чтобы отслеживать, что свободно, а что нет.
Расщепление и коалесцирование (Splitting and Coalescing)
Свободный список содержит набор элементов, описывающих свободное пространство, все еще остающееся в куче. Таким образом, предположим следующую 30-байтовую кучу:
Свободный список для этой кучи будет иметь два элемента. Одна запись описывает первый 10-байтовый свободный сегмент (байты 0-9), а другая запись описывает другой свободный сегмент (байты 20-29):
Как описано выше, запрос на что-либо большее, чем 10 байт, завершится неудачей (возвращая NULL); просто нет ни одного смежного куска памяти такого размера. Запрос именно такого размера (10 байт) может быть легко удовлетворен любым из свободных кусков. Но что произойдет, если запрос будет на что-то меньшее, чем 10 байт?
Предположим, что у нас есть запрос только на один байт памяти. В этом случае распределитель выполнит действие, известное как разделение: он найдет свободный кусок памяти, который может удовлетворить запрос, и разделит его на два. Первый фрагмент он вернет вызывающему абоненту; второй фрагмент останется в списке. Таким образом, в нашем примере выше, если был сделан запрос на 1 байт, и распределитель решил использовать второй из двух элементов списка для удовлетворения запроса, вызов malloc() вернет 20 (адрес выделенной области 1 байт), и список будет выглядеть следующим образом:
На картинке вы можете видеть, что список в основном остается нетронутым; единственное изменение заключается в том, что свободная область теперь начинается с 21 вместо 20, а длина этой свободной области теперь составляет всего 9. Таким образом, разделение сегмента обычно используется в алокаторах, когда запросы на выделение памяти меньше размера любого конкретного свободного участка памяти.
Полученный механизм, обнаруженный во многих алокаторах, известен как коалесцирование (coalescing) свободного пространства. Возьмем еще раз наш пример описанный выше (свободные 10 байт, использованные 10 байт и еще одни свободные 10 байт).
Учитывая эту (крошечную) кучу, что происходит, когда приложение вызывает free(10), возвращая таким образом пространство в середине кучи? Если мы просто добавим это свободное пространство обратно в наш список, не слишком задумываясь, мы можем получить список, который выглядит следующим образом:
Обратите внимание на проблему: хотя вся куча теперь свободна, она, по-видимому, разделена на три участка по 10 байт каждый. Таким образом, если пользователь запросит 20 байт, простой обход списка не найдет такого свободного куска и вернет сбой.
Чтобы избежать этой проблемы, алокаторы объединяют свободное пространство при освобождении куска памяти. Идея проста: возвращая свободный фрагмент в память, внимательно посмотрите на адреса возвращаемого фрагмента, а также на близлежащие фрагменты свободного пространства; если новообретенное пространство находится рядом с одним (или двумя, как в этом примере) существующими свободными фрагментами, объедините их в один больший свободный фрагмент. Таким образом, при слиянии наш окончательный список должен выглядеть так:
Действительно, именно так выглядел список кучи сначала, до того, как были сделаны какие-либо распределения. С помощью коалесцирования распределитель может лучше гарантировать, что для приложения доступны большие свободные экстенты.
Отслеживание размера выделенных участков памяти
Возможно, вы заметили, что интерфейс free(void *ptr) не принимает параметр size; таким образом, предполагается, что при наличии указателя библиотека malloc может быстро определить размер освобождаемой области памяти и таким образом включить пространство обратно в список free.
Для выполнения этой задачи большинство распределителей хранят немного дополнительной информации в блоке заголовка, который хранится в памяти, как правило, непосредственно перед раздачей куска памяти. Давайте еще раз рассмотрим пример (рис. 17.1). В этом примере мы рассматриваем выделенный блок размером 20 байт, на который указывает ptr; представьте себе, что пользователь вызвал malloc() и сохранил результаты в ptr, например, ptr = malloc(20);.
Заголовок, как минимум, содержит размер выделенной области (в данном случае 20); он также может содержать дополнительные указатели для ускорения освобождения, магическое число для обеспечения дополнительной проверки целостности и другую информацию. Предположим, что простой заголовок содержит размер области и магическое число, например:
Приведенный выше пример будет выглядеть так, как показано на рис. 17.2. Когда пользователь вызывает free(ptr), библиотека затем использует простую арифметику указателей, чтобы выяснить, где начинается заголовок:
Получив такой указатель на заголовок, библиотека может легко определить, соответствует ли магическое число ожидаемому значению (assert(hptr->magic == 1234567)) и вычислить общий размер вновь освобожденной области с помощью простой математики (т. е. Обратите внимание на небольшую, но важную деталь в последнем предложении: размер свободной области-это размер заголовка плюс размер пространства, выделенного пользователю. Таким образом, когда пользователь запрашивает N байт памяти, библиотека не ищет свободный кусок размером N; скорее, она ищет свободный кусок размером N плюс размер заголовка.
Внедрение списка свободной памяти
До сих пор мы рассматривали наш простой свободный список как концептуальную сущность; это просто список, описывающий свободные куски памяти в куче. Но как построить такой список внутри самого свободного пространства?
В более типичном списке при выделении нового узла вы просто вызываете malloc(), когда вам нужно место для узла. К сожалению, в библиотеке распределения памяти вы не можете этого сделать! Вместо этого вам нужно построить список внутри самого свободного пространства. Не волнуйтесь, если это звучит немного странно; это так, но не настолько странно, чтобы вы не могли этого сделать!
Предположим, что у нас есть 4096-байтовый кусок памяти для управления (т. е. куча составляет 4 КБ). Чтобы управлять этим как свободным списком, мы сначала должны инициализировать указанный список; первоначально список должен иметь одну запись размером 4096 (минус размер заголовка). Вот описание узла списка:
Теперь давайте посмотрим на некоторый код, который инициализирует кучу и помещает первый элемент свободного списка в это пространство. Мы предполагаем, что куча построена в некотором свободном пространстве, полученном с помощью вызова системного вызова mmap(); это не единственный способ построить такую кучу, но хорошо служит нам в данном примере. Вот код:
После запуска этого кода статус списка таков, что он имеет одну запись размером 4088. Да, это крошечная кучка, но она служит прекрасным примером для нас здесь. Головной указатель содержит начальный адрес этого диапазона; предположим, что он равен 16 КБ (хотя любой виртуальный адрес был бы хорош). Визуально куча выглядит так, как показано на рис. 17.3.
Теперь давайте представим, что запрашивается кусок памяти, скажем, размером 100 байт. Для обслуживания этого запроса библиотека сначала найдет фрагмент, достаточно большой для размещения запроса; поскольку есть только один свободный фрагмент (размер: 4088), этот фрагмент будет выбран. Затем фрагмент будет разделен на два: один фрагмент достаточно большой, чтобы обслуживать запрос (и заголовок, как описано выше), и оставшийся свободный фрагмент. Предполагая 8-байтовый заголовок (целочисленный размер и целочисленное магическое число), пространство в куче теперь выглядит так, как вы видите на рис.17.4.
Таким образом, по запросу на 100 байт библиотека выделяет 108 байт из существующего одного свободного фрагмента, возвращает ему указатель (обозначенный ptr на рисунке выше), прячет информацию заголовка непосредственно перед выделенным пространством для последующего использования при free() и сжимает один свободный узел в списке до 3980 байт (4088 минус 108).
Теперь давайте посмотрим на кучу, когда есть три выделенные области, каждая из которых имеет 100 байт (или 108, включая заголовок). Визуализация этой кучи показана на рис. 17.5.
Как можно увидеть, первые 324 байта кучи теперь выделены, и таким образом мы видим три заголовка в этом пространстве, а также три 100 - байтовые области, используемые вызывающей программой. Свободный список остается неинтересным: только один узел (на который указывает голова), но теперь только 3764 байта в размере после трех разбиений. Но что происходит, когда вызывающая программа возвращает некоторую память через free()?
В этом примере приложение возвращает средний фрагмент выделенной памяти, вызывая free(16500) (значение 16500 получается путем добавления начала области памяти, 16384, к 108 предыдущему фрагменту и 8 байтам заголовка для этого фрагмента). Это значение показано на предыдущей диаграмме указателем sptr.
Библиотека немедленно вычисляет размер свободной области, а затем добавляет свободный кусок обратно в список свободных. Предположим, что мы вставляем в начало свободного списка, пространство теперь выглядит так (рис. 17.6).
Теперь у нас есть список, который начинается с небольшого свободного куска (100 байт, на который указывает глава списка) и большого свободного куска (3764 байта). В нашем списке наконец-то есть больше одного элемента! И да, свободное пространство фрагментировано, прискорбное, но обычное явление.
Последний пример: предположим теперь, что последние два используемых фрагмента освобождены. Не сливаясь, вы получаете фрагментацию (рис. 17.7).
Как видно из рисунка, у нас сейчас большой бардак! Почему? Просто мы забыли объединить список. Несмотря на то, что вся память свободна, она разбита на части, таким образом, появляется как фрагментированная память, несмотря на то, что она не является единым целым. Решение простое: пройдитесь по списку и объедините соседние куски; когда закончите, куча снова станет целой.
Рост кучи
Мы должны обсудить последний механизм, найденный во многих библиотеках распределения. В частности, что вы должны делать, если в куче не хватает места? Самый простой подход-просто потерпеть неудачу. В некоторых случаях это единственный вариант, и поэтому возвращение NULL является почетным подходом. Не расстраивайся! Ты пытался, и хотя у тебя ничего не вышло, ты сражался достойно.
Большинство традиционных алокаторов начинают с небольшой кучи, а затем запрашивают больше памяти у ОС, когда они заканчиваются. Как правило, это означает, что они делают какой-то системный вызов (например, sbrk в большинстве систем UNIX), чтобы увеличить кучу, а затем выделяют оттуда новые куски. Для обслуживания запроса sbrk ОС находит свободные физические страницы, сопоставляет их в адресное пространство запрашивающего процесса, а затем возвращает значение конца новой кучи; в этот момент доступна большая куча, и запрос может быть успешно обслужен.
Основные Стратегии
Теперь, когда у нас есть понимание механизмов работы с памятью, давайте рассмотрим некоторые основные стратегии управления свободным пространством. Эти подходы в основном основаны на довольно простых политиках, которые вы могли бы придумать сами; попробуйте сделать это перед чтением и посмотрите, получилось ли у вас придумать все рассмотренные в главе варианты (или, может быть, вы придумали некоторые новые и неописанные здесь!).
Идеальный алокатор является одновременно быстрым и минимизирует фрагментацию. К сожалению, поскольку поток распределений и свободных запросов может быть произвольным (в конце концов, они определяются программистом), любая конкретная стратегия может работать довольно плохо при неправильном наборе входных данных. Таким образом, мы не будем описывать “лучший” подход, а скорее поговорим о некоторых основах и обсудим их плюсы и минусы.
Best Fit
Cтратегия Best Fit довольно проста: во-первых, выполните поиск в свободном списке и найдите куски свободной памяти такого же размера или больше, чем запрошенный размер. Затем верните тот, который является самым маленьким в этой группе кандидатов; это так называемый наилучший кусок (его тоже можно назвать наименьшим). Одного прохода через свободный список достаточно, чтобы найти правильный блок для возврата.
Интуиция, лежащая в основе best fit, проста: возвращая блок, близкий к тому, что запрашивает пользователь, best fit пытается уменьшить потерянное пространство. Тем не менее, есть цена; наивные реализации платят большой штраф за производительность при выполнении исчерпывающего поиска правильного свободного блока.
Worst Fit
Худший подход-это противоположность наилучшему подходу; найдите самый большой кусок и верните требуемую сумму; сохраните оставшийся (большой) кусок в свободном списке. Worst Fit пытается таким образом оставить большие куски свободными вместо множества маленьких кусков, которые могут возникнуть в результате работы Best Fit. Опять же, однако, требуется полный поиск свободного пространства, и поэтому такой подход может быть дорогостоящим. Хуже того, большинство исследований показывают, что он работает плохо, что приводит к избыточной фрагментации, но при этом имеет высокие накладные расходы.
First Fit
Метод First Fit просто находит первый блок, который достаточно велик, и возвращает запрошенную сумму на пользователя. Как и прежде, оставшееся свободное пространство остается свободным для последующих запросов.
First fit имеет преимущество в скорости — не требуется исчерпывающего поиска всех свободных пространств, — но иногда загрязняет начало свободного списка небольшими объектами. Таким образом, вопрос о том, как распределитель управляет порядком свободного списка, становится проблемой. Один из подходов заключается в использовании адресного упорядочения; сохраняя список упорядоченным по адресу свободного пространства, коалесцирование становится проще, а фрагментация, как правило, уменьшается.
Next Fit
Вместо того, чтобы всегда начинать поиск First Fit в начале списка, алгоритм Next Fit сохраняет дополнительный указатель на то место в списке, где он искал в последний раз. Идея состоит в том, чтобы распределить поиск свободного места по всему списку более равномерно, таким образом избегая расщепления начала списка. Эффективность такого подхода очень похожа на first fit, так как исчерпывающий поиск в очередной раз избегается.
Примеры
Вот несколько примеров приведенных выше стратегий. Представьте себе свободный список с тремя элементами размером 10, 30 и 20 (здесь мы проигнорируем заголовки и другие детали, вместо этого просто сосредоточимся на том, как работают стратегии):
Предположим, что запрос на выделение имеет размер 15. Наиболее подходящий подход будет искать весь список и находить, что 20 было наилучшим вариантом, поскольку это наименьшее свободное пространство, которое может вместить запрос. Результирующий свободный список:
Как это происходит в этом примере, и часто происходит с Best Fit, теперь остается небольшой свободный кусок. Worst Fit аналогичен, но вместо этого находит самый большой кусок, в данном примере 30. Результирующий список:
Стратегия first-fit в этом примере делает то же самое, что и стратегия worst-fit, также находя первый свободный блок, который может удовлетворить запрос. Разница заключается в стоимости поиска; как наиболее подходящий, так и наихудший вариант просматривают весь список; первый вариант рассматривает только свободные куски, пока не найдет тот, который подходит, тем самым снижая стоимость поиска.
Эти примеры просто царапают поверхность политик распределения. Для более глубокого понимания требуется более детальный анализ с реальными рабочими нагрузками и более сложным поведением распределителей (например, коалесцирование). Может быть, что-нибудь для домашнего задания, говорите?
Другие Подходы
Помимо основных подходов, описанных выше, было предложено множество методов и алгоритмов для улучшения распределения памяти. Мы перечислим некоторые из них здесь для вашего рассмотрения (то есть для того, чтобы вы подумали о чем-то большем, чем просто наилучшее распределение).
Сегрегированные списки
Один интересный подход, который существует уже некоторое время, - это использование сегрегированных списков. Основная идея проста: если у конкретного приложения есть один (или несколько) запрос популярного размера, который он делает, держите отдельный список только для управления объектами такого размера; все остальные запросы направляются в более общий распределитель памяти.
Преимущества такого подхода очевидны. Имея кусок памяти, выделенный для одного конкретного размера запросов, фрагментация гораздо меньше беспокоит; кроме того, выделение и свободные запросы могут быть обслужены довольно быстро, когда они имеют правильный размер, так как не требуется сложный поиск списка.
Как и любая хорошая идея, этот подход также вносит новые сложности в систему. Например, сколько памяти следует выделить пулу памяти, который обслуживает специализированные запросы заданного размера, в отличие от общего пула? Один конкретный алокатор, slab allocator uber-инженера Джеффа Бонвика (который был разработан для использования в ядре Solaris), справляется с этой проблемой довольно хорошо.
В частности, когда ядро загружается, оно выделяет ряд объектных кэшей для объектов ядра, которые, вероятно, будут часто запрашиваться (например, блокировки, индексные коды файловой системы и т. Д.); Таким образом, объектные кэши представляют собой отдельные свободные списки заданного размера и быстро обслуживают выделение памяти и свободные запросы. Когда у данного кэша заканчивается свободное пространство, он запрашивает некоторые блоки памяти у более общего распределителя памяти (общий объем запрашиваемой памяти кратен размеру страницы и рассматриваемому объекту). И наоборот, когда отсчеты ссылок на объекты в пределах данной плиты все идут к нулю, общий распределитель может вернуть их из специализированного распределителя, что часто делается, когда системе виртуальной машины требуется больше памяти.
Slab allocator также выходит за рамки большинства подходов к сегрегированным спискам, сохраняя свободные объекты в списках в предварительно инициализированном состоянии. Бонвик показывает, что инициализация и разрушение структур данных обходятся дорого; сохраняя освобожденные объекты в определенном списке в их инициализированном состоянии, Slab allocator таким образом избегает частых циклов инициализации и разрушения для каждого объекта и, таким образом, заметно снижает накладные расходы.
Buddy Allocation
Поскольку коалесцирование имеет решающее значение для алокатора, некоторые подходы были разработаны вокруг упрощения коалесцирования. Один хороший пример можно найти в двоичном распределителе buddy allocator.
В такой системе, свободная память рассматривается как одно большое пространство объемом 2N. Когда делается запрос на память, поиск свободного пространства рекурсивно делит свободное пространство на два, пока не будет найден блок, достаточно большой, чтобы вместить запрос (и дальнейшее разделение на два приведет к слишком маленькому пространству). В этот момент запрошенный блок возвращается пользователю. Вот пример разделения свободного пространства размером 64 КБ при поиске блока размером 7 КБ (рис. 17.8, стр. 15).
В этом примере выделяется самый левый блок размером 8 КБ (на что указывает более темный оттенок серого) и возвращается пользователю; обратите внимание, что эта схема может страдать от внутренней фрагментации, так как вам разрешено выдавать только блоки мощности двух размеров.
Красота budy алокатора заключается в том, что происходит, когда этот блок освобождается. Возвращая блок 8 КБ в список свободных, алокатор проверяет, свободен ли “buddy” 8 КБ; если да, то он объединяет два блока в блок 16 КБ. Затем алокатор проверяет, свободен ли buddy блока 16 КБ; если да, то он объединяет эти два блока. Этот рекурсивный процесс слияния продолжается вверх по дереву, либо восстанавливая все свободное пространство, либо останавливаясь, когда обнаруживается, что buddy используется.
Причина, по которой buddy алокация работает так хорошо, заключается в том, что определить buddy конкретного блока очень просто. Как, спросите вы? Подумайте об адресах блоков в свободном пространстве выше. Если вы хорошенько подумаете, то увидите, что адрес каждой пары приятелей отличается только на один бит; какой бит определяется уровнем в дереве приятелей. Таким образом, у вас есть базовое представление о том, как работают бинарные схемы buddy алокации. Более подробно, как всегда, смотрите исследование Уилсона.
Другие идеи
Одной из основных проблем многих описанных выше подходов является их недостаточное масштабирование. В частности, поиск списков может быть довольно медленным. Таким образом, продвинутые распределители используют более сложные структуры данных для решения этих проблем, обменивая простоту на производительность. Примеры включают сбалансированные бинарные деревья, расщепленные деревья или частично упорядоченные деревья.
Учитывая, что современные системы часто имеют несколько процессоров и выполняют многопоточные рабочие нагрузки (о чем вы подробно узнаете в разделе книги о параллелизме), неудивительно, что много усилий было потрачено на то, чтобы распределители хорошо работали в многопроцессорных системах. Два замечательных примера можно найти у Бергера и др. и Эванс; проверьте их для получения более подробной информации.
Это всего лишь две из тысяч идей, которые люди имели в течение долгого времени о распределителях памяти; читайте сами, если вам интересно. В противном случае прочтите о том, как работает распределитель glibc, чтобы иметь представление о том, каков реальный мир.
Резюме
В этой главе мы рассмотрели самые примитивные формы распределителей памяти. Такие распределители существуют повсюду, связанные с каждой написанной вами программой на языке Си, а также в базовой ОС, которая управляет памятью для своих собственных структур данных. Как и во многих других системах, при построении такой системы приходится идти на множество компромиссов, и чем больше вы знаете о точной рабочей нагрузке, представленной распределителю, тем больше вы можете сделать, чтобы настроить ее так, чтобы она лучше работала для этой рабочей нагрузки. Создание быстрого, компактного, масштабируемого распределителя, который хорошо работает для широкого диапазона рабочих нагрузок, остается постоянной проблемой в современных компьютерных системах.
[B+00] “Hoard: A Scalable Memory Allocator for Multithreaded Applications” by Emery D. Berger, Kathryn S. McKinley, Robert D. Blumofe, Paul R. Wilson. ASPLOS-IX, November 2000. Berger and company’s excellent allocator for multiprocessor systems. Beyond just being a fun paper, also used in practice!
[B94] “The Slab Allocator: An Object-Caching Kernel Memory Allocator” by Jeff Bonwick. USENIX ’94. A cool paper about how to build an allocator for an operating system kernel, and a great example of how to specialize for particular common object sizes.
[E06] “A Scalable Concurrent malloc(3) Implementation for FreeBSD” by Jason Evans. April, 2006. http://people.freebsd.org/˜jasone/jemalloc/bsdcan2006/jemalloc.pdf. A detailed look at how to build a real modern allocator for use in multiprocessors. The “jemalloc” allocator is in widespread use today, within FreeBSD, NetBSD, Mozilla Firefox, and within Facebook.
[K65] “A Fast Storage Allocator” by Kenneth C. Knowlton. Communications of the ACM, Volume 8:10, October 1965. The common reference for buddy allocation. Random strange fact: Knuth gives credit for the idea not to Knowlton but to Harry Markowitz, a Nobel-prize winning economist. Another strange fact: Knuth communicates all of his emails via a secretary; he doesn’t send email himself, rather he tells his secretary what email to send and then the secretary does the work of emailing. Last Knuth fact: he created TeX, the tool used to typeset this book. It is an amazing piece of software4 .
[S15] “Understanding glibc malloc” by Sploitfun. February, 2015. sploitfun.wordpress.com/ 2015/02/10/understanding-glibc-malloc/. A deep dive into how glibc malloc works. Amazingly detailed and a very cool read.
[W+95] “Dynamic Storage Allocation: A Survey and Critical Review” by Paul R. Wilson, Mark S. Johnstone, Michael Neely, David Boles. International Workshop on Memory Management, Scotland, UK, September 1995. An excellent and far-reaching survey of many facets of memory allocation. Far too much detail to go into in this tiny chapter!