Как мы выделяем и освобождаем память со структурами данных? Хотя операционная система сделает за нас свою работу, чтобы выяснить, как управлять памятью, иногда лучше разработать специальную систему управления памятью для чего-то, а не полагаться на системный менеджер памяти.
Память содержит две вещи: стек и кучу. При вызове процедур аргументы и локальные переменные помещаются в стек, а когда процедура возвращает значение, эти переменные извлекаются. Куча не является структурой данных кучи. Когда вы делаете что-то вроде malloc, new Object() и т. д., элементы или объекты будут храниться в другом разделе памяти, то есть в куче. Когда элементы выделяются и освобождаются, хранилище кучи фрагментируется на части. Итак, как мы поддерживаем кучу? Другими словами, как выяснить, какое пространство памяти доступно, а какое нет, и как управлять пространством памяти.
В языках программирования, таких как C/C++, память выделяется с помощью malloc или new и явно освобождается с помощью free или delete. Если у вас есть два указателя, указывающих на один и тот же блок памяти, и вы освобождаете память, используя один из указателей, это вызовет проблемы, потому что даже если вы освободите память, другой указатель все равно будет ссылаться на освобожденную память. Возможно, программист сделал неглубокую копию, которая приводит к копированию указателя, а не копированию фактических данных, например. Java, Go и т. д. имеют процесс сборки мусора, чтобы определить, какие объекты больше не доступны, а затем освободить хранилище. Этот вид управления памятью осуществляется неявно.
Я собираюсь написать об явном управлении памятью.
Когда все выделяемые объекты имеют одинаковый размер, освободить их очень легко. Скажем, для кучи используется большая непрерывная часть памяти, и мы разделяем ее на блоки размером b, где b — размер каждого объекта. Для каждого нераспределенного блока мы используем одно слово блока в качестве следующего указателя и просто связываем эти блоки вместе в связанном списке, называемом списком доступного пространства. для каждого запроса на выделение мы извлекаем блок из списка доступного пространства, а для каждого запроса на выделение мы возвращаем блок в список.
Если нам нужны разные размеры, все становится намного сложнее. Мы разделим память на блоки разного размера. Каждый блок содержит информацию, указывающую, насколько он велик. Доступные блоки связаны вместе, чтобы сформировать список доступного пространства.
Теперь есть два вопроса: как лучше всего выделить блоки для каждого запроса на выделение и как быстрее всего освободить блоки для каждого запроса на освобождение.
Самая большая проблема в системах заключается в том, что после серии запросов на выделение и освобождение пространство памяти имеет тенденцию фрагментироваться на небольшие блоки памяти. Это называется внешней фрагментацией и присуще всем распределителям динамической памяти. Фрагментация увеличивает время работы системы распределения памяти за счет увеличения размера списка доступного пространства, и когда приходит запрос на большой блок, может быть невозможно удовлетворить этот запрос, даже если в этих маленьких блоках достаточно общей памяти. . Это как-то неловко, эээ…
Хороший диспетчер памяти хорошо справляется с управлением внешней фрагментацией.
При выделении блока нам обязательно нужно пройтись по списку доступных блоков памяти в поисках того, который достаточно велик, чтобы удовлетворить запрос. Какой блок лучше выбрать? Мы просим.
Две общие стратегии:
Первое соответствие: поиск доступных блоков последовательно до тех пор, пока не будет найден первый блок, достаточно большой для удовлетворения запроса.
Наилучшее соответствие: поиск всех доступных блоков и выбор наименьшего блока, который достаточно велик для выполнения запроса.
Наилучшее соответствие часто на практике работает хуже, чем первое соответствие. Причина в том, что First-fit выполняется быстрее, поскольку поиск может остановиться на первом блоке достаточно большого размера, а не искать во всем доступном списке. Наилучшее соответствие имеет тенденцию вызывать значительную фрагментацию за счет выбора блоков, которые едва превышают запрошенный размер, и в будущем может не быть запросов, которые были бы достаточно малы, чтобы можно было использовать этот небольшой блок.
Способ уменьшить фрагментацию — когда запрос едва заполняется доступным блоком, который немного больше, чем запрос, мы выделяем весь блок (больше, чем запрос), чтобы избежать создания осколка. Это избавляет список доступных блоков от большого количества крошечных фрагментов, которые увеличивают время поиска. Дополнительная трата пространства, возникающая из-за того, что мы выделяем больший блок памяти, чем запрошенный пользователем, называется внутренней фрагментацией (поскольку трата находится внутри выделенного блока).
При освобождении блока важно, чтобы при наличии доступного хранилища мы объединили недавно освобожденный блок с любыми соседними доступными блоками, чтобы создать большие блоки свободного пространства. Это называется слиянием.
Слияние? Хм, так мы хотим знать, доступен ли предыдущий блок. Мы могли бы пройтись по списку доступного пространства и посмотреть, найдем ли мы его, но это будет медленно. Как насчет того, чтобы добавить дополнительную информацию, например, сохранить какой-то битовый шаблон, чтобы показать конец и начало каждого блока, чтобы мы знали, доступен ли блок памяти или нет. Что, если блок выделен и содержимое данных случайно совпадает с этим битовым шаблоном?
Давайте посмотрим.
Как мы храним доступные блоки, чтобы мы могли их быстро искать (пропуская используемые блоки), и как мы определяем, можем ли мы объединиться с соседними блоками или нет? Нам нужны эффективные операции, но без чрезмерного использования пространства точек.
Обычно мы выделяем память в байтах, но принято выравнивать все выделенные блоки по слову (32 бита) или двойному слову (64 бита). Таким образом, нам не нужно знать, для чего используется тип данных (bytes, int, float, double, …).
Для упрощения предположим, что запросы на выделение памяти заданы в виде количества слов, а возвращаемый нами блок памяти будет выровнен по границе слова.
Объяснять:
Выделенные блоки: для каждого блока используемой памяти мы записываем
- size: размер блока памяти
- inUse: один бит, установленный в 1, чтобы указать, что этот блок используется
- prevInUse: один бит, который устанавливается в 1, если предыдущий блок используется.
Доступные блоки: для доступного блока мы храним больше информации, и это нормально, поскольку пользователь все равно не использует блок. Доступные блоки хранятся в двусвязном круговом списке. Порядок блоков может зависеть от размера блоков. Мы включаем
- size: размер блока памяти
- inUse: один бит, установленный в 1, чтобы указать, что он используется
- prevInUse: один бит, который устанавливается в 1, если предыдущий блок используется.
- prev: указатель на предыдущий блок в списке доступного пространства
- next: указатель на следующий блок в списке доступного пространства
- size2: содержит то же значение, что и size в начале блока. он хранится в последнем слове блока. Для блока p к нему можно получить доступ как *(p + p.size — 1).
Должны ли мы доверять программе пользователя, не перезаписывающей ни одно из полей заголовка блока или указатели на предыдущий/следующий? Нет. Если программа случайно перезапишет область памяти за пределами выделенного блока, она может разрушить целостность системы памяти, и тогда все выйдет из строя. Чтобы этого не допустить, мы можем выкинуть что-то вроде «Ошибка сегментации». Допустим, мы этого не делаем, тогда может произойти запись с переполнением буфера.
Чтобы выделить блок, мы просматриваем связанный список доступных блоков, пока не найдем блок достаточного размера. Если запрос примерно того же размера, что и блок, мы удаляем блок из списка доступных блоков и возвращаем на него указатель. Нам также необходимо обновить бит prevInUse следующего блока, так как этот блок больше недоступен. В противном случае разделите блок на два меньших блока, верните один пользователю, а другой оставьте в списке доступного пространства.
//let p be a pointer to memory.
//*p will be the contents of the word of memory at xxx address
(void*) alloc(int b) //allocate block with b words
{
b += 1; //extra space
p = search available space list for block of size at least b;
if (p == null) {error}
if (p.size - b < TOO_SMALL) //remaingin fragment too small?
{
avail.unlink(p); //remove the entire block from avail list
q = p; //the block to return
}
else //split the block
{
p.size -= b; //decrease size by b
*(p + p.size - 1) = p.size; //set new block's size2 field
q = p + p.size; //offset of start of new block
q.size = b; //size of new block
q.prevInUse = 0; //previous block is unused
}
q.inUse = 1; //new block is used
(q + q.size).prevInUse = 1; //adjust prevInUser for following block
return q + 1; //offset the link (to avoid header)
}
Чтобы освободить блок, проверьте, доступен ли следующий блок или предыдущие блоки. Для следующего блока мы можем найти его первое слово и проверить его поле inUse. Для предыдущего блока мы используем собственное поле prevInUse. Если предыдущий блок не используется, мы используем значение размера, хранящееся в последнем слове, чтобы найти заголовок блока. Если какой-либо из этих блоков доступен, мы объединяем два блока и обновляем значения заголовков. Если и предыдущий, и следующий блоки доступны, то это приводит к удалению одного из этих блоков из списка доступного пространства. Если и предыдущий, и следующий блоки используются, мы можем связать этот блок со списком доступных блоков.
void dealloc(void* p)
{
p--; //back up to the header;
q = p + p.size; //the following block
if (!q.inUse) //is the following block available?
{
p.size += q.size; //merge q into p
avail.move(q, p); //move q to p in avail space list
}
else avail.insert(p); //insert p into avail space list
p.inUse = 0; //p is now available
*(p + p.size - 1) = p.size; //set out size2 value
if (!p.prevInUse) //is previous available?
{
q = p - *(p - 1); //get previous block using size2
q.size += p.size; //merge p into q
*(q + q.size - 1) = q.size; //store new size2 value
avail.unlink(p); //unlink p from avail space list
(q + q.size).prevInUse = 0; //notify next that we are avail
}
}
Система друзей:
Система напарников — это альтернативная система распределения, которая ограничивает возможные размеры блоков и их позиции для создания более структурированного распределения. Поскольку это ограничивает размеры блоков, внутренняя фрагментация становится проблемой. Система напарников работает, начиная с блока памяти, размер которого равен степени 2, а затем иерархически подразделяет каждый блок на блоки одинакового размера.
Размеры всех блоков (как выделенных, так и доступных) являются степенью числа 2. Когда приходит запрос на выделение, запрос (включая служебное пространство, необходимое для хранения информации о размере блока) искусственно округляется до следующей большей степени 2. Выделенный размер никогда не превышает размер запроса более чем в два раза.
Блоки размером 2^k начинаются с адресов памяти, кратных 2^k.
Для каждого блока существует ровно один другой блок, с которым этот блок может быть объединен. Это называется его приятель. В общем, если блок b имеет размер 2 ^ k и расположен по адресу x, то его партнером является блок размера 2 ^ k, расположенный по адресу:
|-> x + 2^k if 2^(k+1) divides x
buddy_k(x) = |
|
|-> x - 2^k otherwise
Адрес друга формируется путем дополнения бита k в двоичном представлении x, где бит младшего разряда равен биту 0. Итак, мы можем сделать что-то вроде этого
buddy(k, x) = (1<<k)^x
Преимущество системы напарников заключается в том, что мы можем использовать обычные размеры блоков для эффективного поиска доступных блоков. Мы можем создать массив связанных списков, по одному для списка доступных блоков для каждой группы размеров. Итак, avail[k] — это указатель заголовка на двусвязный список доступных блоков размером 2^k.
Предположим, что каждый блок имеет ту же структуру, что и раньше (доступный блок и выделенный блок). Бит prevInUse и поле размера в конце каждого доступного блока не нужны, учитывая дополнительную структуру, предусмотренную в системе друзей. Каждый блок хранит свой размер и бит, указывающий, выделен он или нет. Кроме того, каждый доступный блок имеет ссылки на предыдущую и следующую записи в списке доступного пространства. Существует не одно доступное место, а несколько списков, по одному для каждого уровня иерархии, например списки пропуска (нажмите здесь). Это позволяет быстро искать блок заданного размера.
Распределение? Чтобы выделить блок размера b, пусть k = ⌈lg(b + 1)⌉ (помните дополнительное слово для размера блока). Мы выделяем блок размером 2^k. Однако блока такого размера может не быть, поэтому найдите наименьшее значение j ≥ k, чтобы был доступный блок размера 2^j. Если j › k, многократно разбивать этот блок, пока не будет создан блок размером 2^k. В процессе мы создадим один или несколько новых блоков, которые будут добавлены в списки доступного пространства.
Освобождение? Сначала отметьте блок, который мы хотим удалить, как доступный. Затем проверьте, доступен ли его приятель. Это будет O(1). Если это так, мы удаляем приятеля из списка доступного пространства и объединяем их вместе в один свободный блок вдвое большего размера. Повторяем это, пока не обнаружим, что приятель выделен.
Я думаю, что я закончу здесь. В управлении памятью определенно есть что-то еще.
— Конец моих учебных заметок —
