До сих пор мы относились к нашей простой бесплатный список как концептуальные сущности; это
просто список с описанием свободных блоков памяти в куче. Но как
нам создать такой список в свободном пространстве себя?
В более типичном списке при выделении нового узла можно просто вызвать
функция malloc
когда вам нужно место для узла. К сожалению, в
памяти-выделение библиотека, вы не можете сделать это! Вместо этого вам нужно построить
список в свободном пространстве себя. Не волнуйтесь, если это звучит немного странно;
это, однако, не так странно, что вы не можете сделать это!
Предположим, у нас есть 4096 байт блока памяти (т. е.
кучи 4КБ). Для управления в этом списке, мы должны сначала инициализировать сказал
список; изначально в этом списке должна быть одна запись, размером 4096 (за вычетом заголовка
размер). Вот описание узла списка
typedef struct _ _ node_t
int
размер;
структуру __узел_Т *следующая
} node_t
Теперь давайте посмотрим на код, который инициализирует кучу и ставит первый
элемент списка внутри этого пространства. Мы исходим из того, что куча
причине в свободное пространство, приобретенные через Вызов системного вызова вызов mmap();
это не единственный способ создания такой куче, но подают нам в этом
пример. Вот код
// вызов mmap() возвращает указатель на кусок свободного пространства
node_t *глава = вызов mmap(значение null, 4096, PROT_READ|флаг prot_write
MAP_ANON/ MAP_PRIVATE, -1, 0
размер головы
= 4096-sizeof (node_t
head- > next
= НЕДЕЙСТВИТЕЛЬНЫЙ
После выполнения этого кода, статус списка является то, что она имеет один ввод,
размера 4088. Да, это крошечная куча, но она служит для нас прекрасным примером
o
PERATING
С
YSTEMS
[В.
ERSION
1.00]
ВСЕМИРНАЯ ПАУТИНА
.
ОСТЕП
.
Орг
Ф
РЗЭ
-С
ШАГ
М
ANAGEMENT
размер
Далее
...
глава
[виртуальный адрес: 16КБ]
заголовок: размер поля
Заголовок: следующее поле (NULL-0
остальная часть 4kb кусок
Рис. 17.3: Куча С Одним Свободным Кусок
размер
магия: 1234567
...
размер
Далее
...
запись ptr
[виртуальный адрес: 16KB
глава
Теперь выделено 100 байт
Свободный 3980 байт
Рисунок 17.4: Кучи: После Одного Выделения
здесь. Головной указатель содержит начальный адрес Этот диапазон, давайте
предположим, это 16 КБ (хотя любой виртуальный адрес будет в порядке). Визуально,
кучи, таким образом, выглядит так, как показано на рис. 17.3.
Теперь, давайте представим, что кусок памяти, скажем, размером
100 байт. Для обслуживания этого запроса, библиотека будет сначала найти кусок, который
достаточно большой, чтобы удовлетворить просьбу; потому что есть только один свободный
кусок (размер: 4088), этот кусок будет выбран. Тогда кусок будет
сплит
на два: один кусок достаточно большой, чтобы обслужить запрос (и заголовок,
как описано выше), а оставшееся свободное чанка. При условии 8-байтовый
заголовок (целочисленный тип, размер и число магическое число), пространство в
куче теперь выглядит так, как показано на рис. 17.4.
Таким образом, по запросу на 100 байт, библиотеки выделено 108 байт
из существующих один свободный кусок, возвращает указатель (ПТР отмечены на
рисунке выше), чтобы он, прячет информацию заголовка непосредственно перед
c 2008-18, A
RPACI
-Д
USSEAU
T
ХРИ
Ми
ASY
p
IECES
Ф
РЗЭ
-С
ШАГ
М
ANAGEMENT
размер
магия: 1234567
...
размер
магия: 1234567
...
размер
магия: 1234567
...
размер
Далее
...
sptr
[виртуальный адрес: 16KB
глава
100 байт все еще выделены
100 байт все еще выделены
(но вот-вот освободится
Еще 100 байт
Свободный 3764-байтовый кусок
Рис. 17.5: Свободное Пространство С Трех Блоков, Выделенных
выделенные места для последующего использования на свободных(), и уменьшается на один свободный узел
в списке 3980 байт (4088 минус 108).
Теперь давайте посмотрим на кучу, если есть три выделены регионы, каждый
из 100 байт (или 108 включая заголовок). Визуализация этой кучи
показано на рис. 17.5.
Как вы можете видеть в нем, первым 324 байта кучи сейчас
выделяется, и, таким образом, мы видим три заголовки в этом пространстве, а также три
100byte регионов используется вызывающей программы. Список свободных остается
неинтересным: только один узел (указанный в голову), но теперь только 3764
байта после трех сплитов. Но что происходит, когда звонишь
программа возвращает память через бесплатно()?
o
PERATING
С
YSTEMS
[В.
ERSION
1.00]
ВСЕМИРНАЯ ПАУТИНА
.
ОСТЕП
.
Орг
Ф
РЗЭ
-С
ШАГ
М
ANAGEMENT
размер
магия: 1234567
...
размер
Далее
...
размер
магия: 1234567
...
размер
Далее
...
[виртуальный адрес: 16KB
глава
sptr
100 байт все еще выделены
(теперь свободный кусок памяти
Еще 100 байт
Свободный 3764-байтовый кусок
Рис. 17.6: Свободное Пространство С Двух Блоков, Выделенных
В этом примере приложение возвращает в середине кусок выделенной
памяти, с помощью вызова Free(16500) (стоимость 16500 прибыл на
добавление в начало области памяти, 16384, на 108 предыдущего
блока и 8 байт заголовка для этой части). Это значение показано
в предыдущей схеме указатель СПТР.
В библиотеке сразу же выясняет размер свободной области, а
затем добавляет бесплатный кусок обратно на свободный список. Предположим, что мы вставляем в
голову списка свободных, пространство теперь выглядит следующим образом (Рис. 17.6).
И теперь у нас есть список, который начинается с небольшой свободный кусок (100 байт,
который указывает на голову списка) и большой свободный кусок (3764 байта).
c 2008-18, A
RPACI
-Д
USSEAU
T
ХРИ
Ми
ASY
p
IECES
Ф
РЗЭ
-С
ШАГ
М
ANAGEMENT
размер
Далее
...
размер
Далее
...
размер
Далее
...
размер
Далее
...
[виртуальный адрес: 16KB
глава
(теперь бесплатно
(теперь бесплатно
(теперь бесплатно
Свободный 3764-байтовый кусок
Рис. 17.7: Не Слипались Бесплатно Список
Наш список, наконец, имеет более чем один элемент на нем! И да, свободное пространство
фрагментировано, неприятным, но распространенным явлением.
Последний пример: предположим теперь, что две последние в использовании куски
освобождены. Без объединения, вы могли бы закончить с бесплатного списка, который сильно
фрагментирован (см. рис. 17.7).
Как вы можете видеть из рисунка, у нас теперь большой беспорядок! Почему? Просто,
мы забыли сливаются списке. Хотя вся память свободна, она
порублена на куски, что приводит к фрагментации памяти несмотря на то
, что я не одна. Решение простое: пойти по списку и слияния
соседних блоков; после завершения кучи будет все снова.
o
PERATING
С
YSTEMS
[В.
ERSION
1.00]
ВСЕМИРНАЯ ПАУТИНА
.
ОСТЕП
.
Орг
Ф
РЗЭ
-С
ШАГ
М
ANAGEMENT
Выращивание Кучи
Мы должны обсудить один последний механизм встречается во многих выделения
библиотеки. В частности, что делать, если куча заканчивается?
Самый простой подход-просто не получится. В некоторых случаях это единственный вариант,
и, таким образом, возвращая null честный подход. Не чувствуйте себя плохо! Вы
пробовали, хоть и проиграла, хорошо боролся.
Большинство традиционных распределителей начать с небольшого размера кучи, а затем
запросить больше памяти от операционной системы, когда они закончатся. Как правило, это означает, что
они делают какой-то системный вызов (например, сбрк в большинстве у
ШУХЕР
системы), чтобы
расти кучи, а затем выделять новые куски оттуда. На службу
в сбрк запрос, ОС находит свободной физической страницы, карты им в
адресном пространстве запрашивающего процесса, а затем возвращает значение
конец нового куче; в этот момент, больше памяти, и
запрос может быть успешно подняться.
17.3 Основные Стратегии
Теперь у нас есть несколько машин под нашим поясом, давайте рассмотрим некоторые
основные стратегии для управления свободным пространством. Эти подходы, в основном,
основана на довольно простых стратегий, которые вы могли бы придумать сами; попробуйте
, прежде чем читать и посмотреть, если вы столкнетесь со всеми из альтернатив (или
, возможно, некоторые новые!).
Идеальный распределитель быстро и минимизирует фрагментацию.
К сожалению, потому что поток распределения и бесплатных запросов может быть произвольной
(в конце концов, они определяются программистом), какой-либо конкретной
стратегии может сделать довольно плохо дали неправильный набор входных данных. Таким образом, мы не будем
описывать “лучший” подход, а говорить о некоторых основах и обсудить
их плюсы и минусы.
Наиболее подходящий
То лучше подойдет стратегия довольно проста: во-первых, поиск через список свободных и
найти куски свободной памяти, которые, как большой или больше, чем требуемый
размер. Затем, вернуться в тот, который самый маленький в этой группе кандидатов;
это так называемый Бест-Нуса (его можно назвать маленьким подойдет тоже). Один
проход через бесплатного списка достаточно, чтобы найти правильное блок для возврата.
Интуиция позади наилучшего прост: вернуться в блок, который близко
к тому, что пользователь просит, лучше подойдет старается уменьшить потери пространства. Однако, есть
стоимость; наивных реализациях платить высокую производительность при
выполнении исчерпывающий поиск для правильного свободный блок.
Худшая Посадка
В худшем, пригодный подход является противоположностью наилучшего вписывания; найти самый большой кусок
и вернуть запрашиваемую сумму; оставшиеся (большой) кусок на
свободный список. Худшая подгонка пытается таким образом оставить большие куски свободными, а не много
c 2008-18, A
RPACI
-Д
USSEAU
T
ХРИ
Ми
ASY
p
IECES
Ф
РЗЭ
-С
ШАГ
М
ANAGEMENT
небольшие куски, которые могут возникнуть из наиболее подходящего подхода. В очередной раз,
однако, полный поиск свободного пространства требуется, и таким образом этот подход может быть
дорогостоящим. Хуже того, большинство исследований показывают, что он выполняет плохо, что приводит к лишней
фрагментации в то же время имеющие высокие накладные расходы.
Первая Посадка
На первый пригодный метод просто находит первый блок, который является достаточно большим и
возвращает запрашиваемую сумму для пользователя. Как и прежде, оставшееся свободное
пространство хранится бесплатно в течение последующих запросов.
Первая посадка имеет преимущество в скорости перебора всех
свободных пространствах необходимы, но иногда загрязняет начало
свободного списка с мелкими предметами. Таким образом, как распределитель управляет свободной списка
того, становится проблемой. Одним из подходов является использование адресной основе заказ;
сохранение списка заказанных адрес свободного пространства, Объединение
становится легче, и фрагментации, как правило, должны быть сокращены.
Следующая Посадка
Вместо того, чтобы всегда начиная с первого-фит поиска в начале списка,
то следующий подходящий алгоритм сохраняет дополнительный указатель на место в
списке где был в прошлом. Идея в том, чтобы распространить ищет
свободное место во всем списке более равномерно, что позволяет избежать сколов
в начале списка. Результативность такого подхода вполне
похож на первый подходят, как перебор в очередной раз избежать.
Образцы
Вот несколько примеров вышеперечисленных стратегий. Представляем бесплатный список с
тремя элементами на нем, размеров 10, 30, и 20 (мы будем игнорировать заголовки и другие
подробности здесь, вместо того, чтобы просто сосредоточиться на том, как стратегии работы
глава
НЕДЕЙСТВИТЕЛЬНЫЙ
Предположим, что запрос на выделение имеет размер 15. Наилучшее подход мог бы
поиск по всему списку и обнаружим, что 20 лучше всего подходят, так как это наименьшее
свободное пространство, которое может удовлетворить эту просьбу. Итоговый свободный список
глава
НЕДЕЙСТВИТЕЛЬНЫЙ
Как происходит в этом примере, и часто случается с передовой
подход, небольшой кусок остался за. В худшем-пригодный подход аналогичен
, но вместо этого находит большой кусок, в данном примере 30. Полученный список
глава
НЕДЕЙСТВИТЕЛЬНЫЙ
o
PERATING
С
YSTEMS
[В.
ERSION
1.00]
ВСЕМИРНАЯ ПАУТИНА
.
ОСТЕП
.
Орг
Ф
РЗЭ
-С
ШАГ
М
ANAGEMENT
Первый-подойдет стратегия, в данном примере, делает то же самое, худшее-фит
также нахождении первого свободного блока, что может удовлетворить запрос. Разница
есть в поиске цена; как наилучшее и худшее-фит просматриваю весь список;
первая-годные только изучает кусочки, пока не найдет то, что соответствует, таким образом уменьшающ
цену ищите.
Эти примеры просто царапают поверхность политик распределения. Более
детальный анализ с реальными нагрузками и более сложные распределитель
поведения (например, объединение) необходимы для более глубокого понимания. Возможно,
что-то на домашнюю работу секции, вы говорите?
17.4 Другие Подходы
Помимо основных подходов, описанных выше, есть множество
предложенных методов и алгоритмов для повышения выделения памяти в
некотором роде. Мы перечислим лишь некоторые из них здесь для вашего рассмотрения (т. е., чтобы
подумать немного больше, чем просто наилучшее распределение).
Сегрегированные Списки
Один интересный подход, который был вокруг в течение некоторого времени является использование
в сегрегированных списки. Основная идея проста: если определенное приложение
имеет одну (или несколько) популярного размера запрос, который это делает, держать отдельный
список только для управления объектами такого размера, а все остальные запросы перенаправляются к
более общим выделения памяти.
Преимущества такого подхода очевидны. Имея кусок
памяти, выделенный для одного конкретного размера просит, фрагментация-это
гораздо меньшая проблема; кроме того, распределение и бесплатные запросы могут быть
обслужили достаточно быстро, когда они нужного размера, а не сложный
поиск список является обязательным.
Как и любая хорошая идея, такой подход вводит новые осложнения
в системе, а также. Например, сколько памяти нужно
выделить для пула памяти, который служит в специализированных запросов определенного
размера, в отличие от общего пула? Одного конкретного распределителя, в плите
распределителя
uber-инженер Джефф Bonwick (который был конструирован для пользы внутри
ядро Solaris), обрабатывает эту проблему довольно хорошим способом [B94].
В частности, когда ядро загружается, он выделяет ряд объектов
Тайники
для объектов ядра, которые могут быть запрошены часто (например,
замки, файловой системы дескрипторов и т. д.); объект схрона таким образом каждый сегрегированный
списков свободной памяти заданного размера и служат выделения памяти и бесплатные запросы
быстро. Когда кэша не хватает свободного пространства, он просит
какой - плиты из памяти из-за выделения памяти (на
общую сумму просил быть кратен размеру страницы и объекта в
вопрос). И наоборот, когда подсчет ссылок на объекты в пределах
данной плиты все уйдет в ноль, общий аллокатор может освободить их от
специализированный аллокатор, который часто делал, когда ВМ система требует
больше памяти.
c 2008-18, A
RPACI
-Д
USSEAU
T
ХРИ
Ми
ASY
p
IECES
Ф
РЗЭ
-С
ШАГ
М
ANAGEMENT
есть
СТОРОНА
: Г
РЕАТ
Ми
NGINEERS
есть
РЕ
Р
EALLY
Г
РЕАТ
Инженеры бы Jeff Bonwick (кто только не писал плиты распределителя
упомянутые в настоящем документе, а также был ведущим удивительной файловой системы, файловая система ZFS) находятся в
самом сердце Силиконовой долины. За почти любой большой продукт или
технология человека (или небольшой группы людей), которые намного выше среднего,
в свои таланты, способности и преданность. Как Марк Цукерберг (из
Facebook) говорит: “тот, кто является исключительным в их роль, не просто немного
лучше, чем тот, кто довольно хорошо. Они в 100 раз лучше.” Это
почему еще сегодня, один или два человека могут начать компанию, что изменения
лицо мира навсегда (подумайте Google, Apple, или Facebook). Работать
трудно, и вы можете стать одним из таких “100х” человека. В противном случае
работать с таким человеком; вы узнаете больше в день, чем большинство учатся в
месяц. Если этого не будет, то будет грустно.
Плиты распределителя также выходит за рамки самых сегрегированных список подходов
, сохраняя свободные объекты в списках в инициализированном состоянии. Bonwick
показывает, что инициализация и разрушение структур данных является дорогостоящим [B94];
сохраняя освободил объекты в определенный список в инициализированном состоянии, на
плиты распределителя таким образом избегает частых инициализация и разрушение циклов
на объект и таким образом снижает накладные расходы заметно.
Распределение Друзей
Потому что объединение имеет решающее значение для выделения некоторых подходов были
разработаны вокруг срастанию просто. Один хороший пример можно найти
в бинарных дружище распределитель [К65].
В такой системе свободная память впервые концептуально рассматривается как единое целое
большой космос размера
Северный
. Когда запрос на обращение к памяти производится поиск
свободного пространства рекурсивно делит свободное пространство от двух до блока, что является большим
достаточно для того чтобы приспособить запрос найден (и далее разделяется на два
приведет в место, которое является слишком маленьким). На данный момент, запрашиваемый
блок возвращается пользователю. Вот пример 64КБ свободного пространства
раскалывался в поисках 7КБ блок
64 КБ
32 КБ
32 КБ
16 КБ
16 КБ
8 КБ 8 КБ
o
PERATING
С
YSTEMS
[В.
ERSION
1.00]
ВСЕМИРНАЯ ПАУТИНА
.
ОСТЕП
.
Орг
Ф
РЗЭ
-С
ШАГ
М
ANAGEMENT
В Примере левого 8кб блок выделяется (как указано в
темный оттенок серого) и возвращается пользователю, отметим, что эта схема может
страдать от внутренней фрагментации, так как вы только разрешено выдавать
мощность в два по размеру блоков.
Красота дружище распределения в том, что случается, когда
блок освобождается. При возврате 8кб блок в список свободных, распределитель
проверяет, является ли “дружище” 8кб бесплатный; если это так, то сращивается два блока
в 16КБ блока. Распределитель затем проверяет, если друг 16КБ
блока остается свободным; если это так, то сращивается этих двух блоков. Этот рекурсивный
процесс объединения продолжается до дерева, восстановив все свободное пространство
или мешает, когда приятель находится в использовании.
Причиной дружище распределения работает так хорошо, заключается в том, что это просто, чтобы
определить дружище конкретного блока. Как, спросите Вы? Подумайте о
адреса блоков в свободном пространстве выше. Если вы считаете, внимательно,
достаточно, вы увидите, что адрес каждого приятеля пара отличается только
один бит; бит, который определяется уровнем в Бадди дерево. И
таким образом у вас есть базовое представление о том, как бинарные дружище распределения схем работы.
Более подробно, как всегда, увидеть опрос Уилсон [Вт+95].
Другие соображения
Одна из основных проблем многих из подходов, описанных выше, является их
отсутствие масштабирования. В частности, поиск списков может быть довольно медленным. Таким образом,
дополнительные распределители использовать более сложные структуры данных для решения этих
затрат, торговле простотой исполнения. Примеры включают в себя сбалансированные
бинарные деревья, косые деревья, или частично-упорядоченные деревья [Вт+95].
Учитывая, что современные системы часто имеют несколько процессоров и запуска
многопоточных рабочих нагрузок (то, что вы узнаете об этом в мельчайших подробностях
в разделе книги параллелизма), неудивительно, что много
усилий было потрачено делая распределителей хорошо работать на
multiprocessorbased систем. Два замечательных примера можно найти в Berger et al. [Б+00]
и Эванс [E06]; проверить их на детали.
Это всего лишь два из Тысячи идей, которые люди имели с течением времени
память о распределителей; читать самостоятельно, если вам интересно. Не
то, прочитал о том, как в glibc распределитель работ [С15], чтобы дать вам ощущение
того, что в реальном мире.
17.5 резюме
В этой главе мы говорили о самых элементарных форм
памяти счетчиков. Такие распределители существуют везде, в каждой связан с
программой вы пишете, так же как и в базовой ОС, которая отвечает за управление
памятью для своих собственных структур данных. Как и во многих системах, существует множество
компромиссных решений, которые будут сделаны в создание такой системы, и чем больше вы знаете
о точной нагрузки представлен распределителем, тем больше вы можете сделать
, чтобы настроить его, чтобы работать лучше для этой нагрузки. Сделав быстрое и экономичное,
масштабируемое распределителя, который хорошо работает в широком диапазоне нагрузок остается
непрерывный вызов в современных компьютерных системах.
c 2008-18, A
RPACI
-Д
USSEAU
T
ХРИ
Ми
ASY
p
IECES
Ф
РЗЭ
-С
ШАГ
М
ANAGEMENT
Ссылки на литературу
[Б+00] “клад: масштабируемая выделения памяти для многопоточных приложений” по Эмери Д.
Бергер, Кэтрин С. Маккинли, Роберт Д. Blumofe, Пауль Р. Уилсон. АСПЛОС-IX, Ноябрь 2000 года.
Бергер и отличную компанию распределитель для многопроцессорных систем. Помимо просто удовольствия бумагу, а также
использовать на практике!
[B94] “плиты распределителя: объект-кэширование ядра распределитель памяти” исполнителя Jeff Bonwick.
По USENIX ’94. Прохладный бумаги о том, как построить распределитель для ядра операционной системы, и отличный
пример того, как специализироваться на конкретном общие размеры объектов.
[E06] “Масштабируемая параллельная реализация malloc(3) Для FreeBSD” от Jason Evans. Апрель,
2006. https://people.freebsd.org/jasone/jemalloc/bsdcan2006/jemalloc.pdf. Подробно рассмотрим
, как построить настоящий современный распределитель для использования в многопроцессорных системах. В “jemalloc” распределитель широко
используется сегодня, во FreeBSD, NetBSD, так и в Mozilla Firefox, и в Facebook.
[К65] “быстро хранение распределитель” Кеннет С. Ноултон. Коммуникаций АКМ,
том 8:10, октябрь 1965 года. Общая ссылка для распределения друзей. Случайный странный факт: Кнут
это заслуга не Ноултона, а Гарри Марковица, лауреата Нобелевской премии по экономике.
Еще один странный факт: кнут общается все его письма через секретаря; он не отправит письмо
сам, а он говорит своему секретарю по эл. почте отправить, а затем секретарь выполняет работу по электронной почте.
Последние кнута факт: он создал Текс, инструмент, используемый для версталась эта книга. Это удивительная часть программного обеспечения
.
[С15] “понимание функции malloc в glibc” по Sploitfun. Февраль 2015. sploitfun.wordpress.com/
2015/02/10/понимание-с glibc-функции malloc/. Глубокое погружение в как в glibc malloc и работает. Удивительно
подробная и очень здорово читать.
[Вт+95] “динамического выделения памяти: обзор и критический обзор” Пауль Р. Уилсон, Марк
С. Джонстон, Майкл Нили, Дэвид Боулз. Международный семинар по управления памятью,
Шотландия, Великобритания, сентябрь 1995 года. Отличный и далеко идущие исследования многих аспектов памяти
распределения. Слишком много деталей в этой крошечной главе!
На самом деле мы используем LaTeX, который основан на дополнениях Lamport к TeX, но достаточно близко.
o
PERATING
С
YSTEMS
[В.
ERSION
1.00]
ВСЕМИРНАЯ ПАУТИНА
.
ОСТЕП
.
Орг
Ф
РЗЭ
-С
ШАГ
М
ANAGEMENT