Доброго времени суток!
Хочу представить вашему вниманию перевод статьи Джонатана Барлетта (Jonathan Bartlett), который является техническим директором в компании New Medio. Статья была опубликована 16 ноября 2004 года на сайте ibm.com и посвящена методам управления памятью. Хотя возраст статьи достаточно высок (по меркам IT), информация в ней является фундаментальной и описывает подходы к распределению памяти, их сильные и слабые стороны. Всё это сопровождается «самопальными» реализациями, для лучшего усвоения материала.
Аннотация от автора
Решения, компромисы и реализации динамического распределения памяти
Получите представление о методах управления памятью, которые доступны Linux разработчикам. Данные методы не ограничиваются языком C, они также применяются и в других языках программирования. Эта статья даёт подробное описание как происходит управление памятью, на примерах ручного подхода (manually), полуавтоматического (semi-manually) с использованием подсчёта ссылок (referencing count) или пула (pooling) и автоматического при помощи сборщика мусора (garbage collection).
Почему возникает необходимость в управлении памятью
Управление памятью одна из наиболее фундаментальных областей в программировании. Во множестве скриптовых языков, вы можете не беспокоится об управлении памятью, но это не делает сей механизм менее значимым. Знания о возможностях вашего менеджера памяти (memory manager) и тонкостях его работы, являются залогом эффективного программирования. В большинстве системных языков, например таких как C/C++, разработчику необходимо самому следить за используемой памятью. Статья повествует о ручных, полуавтоматических и автоматических методах управления памятью.
Было время, когда управления памятью не было большой проблемой. В качестве примера можно вспомнить времена разработки на ассемблере под Apple II. В основном программы запускались не отдельно от ОС, а вместе с ней. Любой участок памяти мог использоваться как системой, так и разработчиком. Не было необходимости в расчёте общего объёма памяти, т.к. она была одинакова для всех компьютеров. Так что требования к памяти были достаточно статичны — достаточно было просто выбрать участок памяти и использовать его.
Тем не менее, даже в таком простом компьютере можно было хапнуть проблем, особенно если вы не знали сколько памяти может потребоваться отдельно взятому участку программы.
Если имеются ограничения, связанные с памятью, то необходим подход, который будет заниматься решением таких задач как:
- Определить, имеется-ли достаточный объём памяти;
- Получить секцию из доступной памяти;
- Вернуть секцию обратно в пул, чтобы её можно было использовать в других частях программы или другими программами.
(прим. переводчика: Обозначим данный список как Memory-Requirements, чтобы ссылаться на него в дальнейшем)
Библиотеки, которые занимаются поиском/выделением/освобождением памяти называются allocator-ми. С ростом сложности программы, повышается сложность управления памятью и тем самым повышается роль allocator-а в такой программе. Давайте взглянем на различные метод управления памятью, рассмотрим их преимущества и недостатки, а также ситуации, где они наиболее эффективны.
Аллокаторы (C-Style)
Язык C поддерживает две функции, которые занимаются решением задач из Memory-Requirements:
- malloc: Выделяет заданное число байт и возвращает указатель на них. Если памяти недостаточно, возвращает указатель на NULL (null pointer);
- free: Принимает на вход указатель на область в памяти, выделенной с помощью malloc и возвращает её для дальнейшего использования в программе или операционной системе (на самом деле, некоторые malloc возвращают память для последующего использования только программе, но не ОС).
Физическая и виртуальная память
Для понимая, как происходит выделение в пределах программы, необходимо иметь представление как ОС выделяет память под программу. (прим. переводчика: т.к. программа запускается под конкретной ОС, то именно она решает, сколько памяти выделить под ту или иную программу) Каждый запущенный процесс считает что имеет доступ ко всей физической памяти компьютера. (прим. переводчика: физическая — жёсткий диск, виртуальная — оперативная память) Очевиден тот факт, что одновременно работает множество процессов и каждый из них не может иметь доступ ко всей памяти. Но что будет если процессам использовать виртуальную память (virtual memory).
В качестве примера, допустим программа обращается к 629-у участку в памяти. Система виртуальной памяти (virtual memory system), не гарантирует что данные хранятся в RAM по адресу 629. Фактически, это может быть даже не RAM — данные могли быть перенесены на диск, если RAM оказалась вся занята. Т.е. в вирт. памяти могут могут храниться адреса, соответствующие физическому устройству. ОС хранит таблицу соответствий вирт. адресов к физическим (virtual address-to-physical address), чтобы компьютер мог правильно реагировать на запрос по адресу (address requests). Если RAM хранит физические адреса, то ОС будет вынуждена временно приостановить процесс, выгрузить часть данных НА ДИСК (из RAM), подгрузить необходимые данные для работы процесса С ДИСКА и перезапустить процесс. Таким образом, каждый процесс получает своё адресное пространство с которым может оперировать и может получить ещё больше памяти, чем ему было выделила ОС.
В 32-х битных приложениях (архитектура x86), каждый процесс может работать с 4 гигабайтами памяти. На данный момент большинство пользователей не владеют таким объёмом. Даже если используется подкачка (swap), всё равно должно получиться меньше 4 Гб на процесс. Таким образом, когда процесс выгружается в память, ему выделяется определённое пространство. Конец этого участка памяти именуется как system break. За этой границей находится неразмеченная память, т.е. без проекции на диск или RAM. Поэтому когда у процесса заканчивается память (из той, что ему была выделена при загрузке) он должен запросить у ОС больший кусок памяти. (Mapping (от англ. mapping — отражение, проекция ) — это математический термин, означающий соответствие один к одному — т.е. когда по виртуальному адресу хранится другой адрес (адрес на диске), по которому уже хранятся реальные данные)
ОС на базе UNIX имеют в своём арсенале два системных вызова для дополнительной разметки памяти:
- brk:brk() — это очень простой системный вызов. System break — это крайняя граница размеченной для процесса памяти. brk() просто перемещает эту границу вперёд/назад, чтобы увеличить или уменьшить объём выделенной памяти. (прим. переводчика: представьте шкалу масштаба в том же MS Word. System break — это макс. значение, которое может принять бегунок, а сам бегунок — Current break);
- mmap:mmap() (или “memory map”) аналогичен brk(), но является более гибким инструментом. Во-первых, он может разметить память в любом месте адресного пространства, а не только в конце процесса. Во-вторых, он может не просто разметить память (виртуальную) как проекцию к физической или свопу (swap), он может привязать память к конкретным файлам так, что чтение и запись будут оперировать непосредственно с файлом. Антиподом mmap() является munmap().
Как вы можете видеть, простые вызовы brk() или mmap() могут быть использованы для расширения памяти процесса. Дальше по тексту будут использоваться brk() т.к. он является наиболее простым и распространённым инструментом.
Реализация простого allocator-а
Если вы писали программы на языке C, то наверняка использовали такие функции как malloc() и free(). Наверняка вы даже не задумывались о их реализации. Этот раздел продемонстрирует упрощённую реализацию этих функций и проиллюстрирует как они участвуют в распределении памяти.
Для примера нам понадобится вот этот листинг. Скопируйте и вставьть его в файл под названием malloc.c. Его мы разберём чуть позже.
Распределите памяти в большинстве операционных систем повязана на двух простых функциях:
- void* malloc(long numbytes): Выделяет в памяти numbytes байт и возвращает указатель на первый из них;
- void free(void* firstbyte): firstbyte — указатель полученный с помощью malloc() и память по которому необходимо освободить.
Объявим функцию malloc_init, которая будет инициализировать наш allocator. Это подразумевает три вещи: Помечать allocator как проинициалированный, находить в памяти последний валидный адрес (т.е который можно было бы использовать для выделения) и установка указателя на начало этой памяти. Для этого объявим три глобальные переменные:
Листинг 1: Глобальные переменные для нашего аллокатора
int has_initialized = 0; void *managed_memory_start; void *last_valid_address; Как упоминалось выше, «край» размеченной памяти (последний действительный адрес) имеет несколько названий — System break или Current break. В большиснтве Unix-like систем, для поиска current system break, используется функция sbrk(0). sbrk отодвигает current break на n байт (передаётся в аргументе), после чего current break примет новое значение. Вызов sbrk(0) просто вернёт current system. Напишем код для нашего malloc, который будет искать current break и инициализировать переменные:
Листинг 2: Инициализации Allocator-а
/* Include the sbrk function */ #include <unistd.h> void malloc_init() { /* захватить (запросить у системы) последний валидный адрес */ last_valid_address = sbrk(0); /* пока у нас нет памяти, которой можно было бы управлять * установим начальный указатель на last_valid_address */ managed_memory_start = last_valid_address; /* Инициализация прошла, теперь можно пользоваться */ has_initialized = 1; } Для правильного управления, необходимо следить за выделяемой и освобождаемой памятью. Необходимо помечать память как “неиспользуемую”, после вызова free() для какого либо участка памяти. Это необходимо для поиска свободной памяти, когда вызывается malloc(). Таким образом, начало каждого участка памяти, которое возвращает malloc() будет будет иметь следующую структуру:
Листинг 3: Структура Memory Control Block
struct mem_control_block { int is_available; int size; }; Можно догадаться, что данная структура будет мешать, если вернуть на неё указатель (вызов функции malloc). (прим. переводчика: имеется в виду, что если указатель установить на начало этой структуры, то при записи в эту память, мы потеряем информацию о том, сколько памяти было выделено) Решается всё достаточно просто — её необходимо скрыть, а именно вернуть указатель на память, которая располагается сразу за этой структурой. Т.е. по факту вернуть указатель на ту область, которая не хранит в себе никакой информации и куда можно “писать” свои данные. Когда происходит вызов free(), в котором передаётся указатель, мы просто отматываем назад некоторое количество байт (а конкретно sizeof(mem_control_block) ), чтобы использовать данные в этой структуре для поиска в дальнейшем.
Для начала поговорим об освобождении памяти, т.к. этот процесс проще чем выделение. Всё что необходимо сделать для освобождения памяти, это взять указатель, переданный в качестве параметра функции free(), переместить его на sizeof(struct mem_control_block) байт назад, и пометить память как свободную. Вот код:
Листинг 4: Освобождение памяти
void free(void *firstbyte) { struct mem_control_block *mcb; /* Отматываем текущий указатель и работаем с ним как с * mem_control_block */ mcb = firstbyte - sizeof(struct mem_control_block); /* Помечаем блок как доступный */ mcb->is_available = 1; /* Всё готово! */ return; } Как вы можете заметить, в данном примере освобождение происходит за константное время, т.к. имеет очень простую реализацию. С выделением уже немного сложнее. Рассмотрим алгоритм в общих чертах:
Листинг 5: Псевдокод алгоритма работы аллокатора
1. Если наш алокатор не был инициализирован, то инициализируем его. 2. Прибавить sizeof(struct mem_control_block) к размеру запрашиваемой памяти; 3. Начнём с managed_memory_start. 4. Является ли он указателем на last_valid address? 5. Если да: A. Значит не найдено ни одного подходящего участка памяти сообщите ОС что вам необходимо больше памяти и возвращайтесь сюда. 6. Если нет: A. Текущий блок не занят?( mem_control_block->is_available == 1)? B. Если да: I) Является-ли он достаточно большим (mem_control_block->is_available >= запрашиваемой памяти)? II) Если да: a. Помечаем память как недоступную (mem_control_block->is_available = 0) b. Перемещаем указатель за mem_control_block и возвращаем его III) В противном случае: a. Перемещаемся на "size" байт вперёд b. Возвращаемся к шагу 4 C. Если нет: I) Двигаемся на "size" байт вперёд II) Возврат на шаг 4 Вся суть заключается в своего рода “прогулке” по памяти с целью нахождения свободных участков. Взглянем на код:
Листинг 6: Реализация алгоритма работы
void *malloc(long numbytes) { /* Место откуда начинается поиск */ void *current_location; /* Представим что мы работаем с * memory_control_block */ struct mem_control_block *current_location_mcb; /* В этот указатель мы вернём найденную память. На время поиска он должен быть 0 */ void *memory_location; /* Инициализируем, если мы этого не сделали */ if(! has_initialized) { malloc_init(); } /* Память содержит в себе memory * control block, но пользователям функции mallocне нужно * об этом знать. Просто смещаем указатель на размер структуры */ numbytes = numbytes + sizeof(struct mem_control_block); /* Присваиваем memory_location 0 пока не найдем подходящий участок */ memory_location = 0; /* Начинаем поиск с начала доступной (управляемой) памяти */ current_location = managed_memory_start; /* Ищем по всему доступному пространству */ while(current_location != last_valid_address) { /* По факту current_location и current_location_mcb * одинаковые адреса. Но current_location_mcb * мы используем как структуру , а * current_location как указатель для перемещенияt */ current_location_mcb = (struct mem_control_block *)current_location; if(current_location_mcb->is_available) { if(current_location_mcb->size >= numbytes) { /* Воооу! Мы нашли подходящий блок... */ /* Кто первым встал, того и тапки - отмечаем участок как занятый */ current_location_mcb->is_available = 0; /* Мы оккупировали эту территорию */ memory_location = current_location; /* Прекращаем цикл */ break; } } /* Если мы оказались здесь, это потому что текущиё блок памяти нам не подошёл, сяпаем дальше */ current_location = current_location + current_location_mcb->size; } /* Если мы всё ещё не имеем подходящего адреса, то следует запросить память у ОС */ if(! memory_location) { /* Move the program break numbytes further */ sbrk(numbytes); /* После выделения, last_valid_address должен обновится */ memory_location = last_valid_address; /* Перемещаемся от last valid address на * numbytes вперёд */ last_valid_address = last_valid_address + numbytes; /* И инициализируем mem_control_block */ current_location_mcb = memory_location; current_location_mcb->is_available = 0; current_location_mcb->size = numbytes; } /* Теперь мы получили память (если не получили ошибок). * И в memory_location также есть место под * mem_control_block */ /* Перемещаем указатель в конец mem_control_block */ memory_location = memory_location + sizeof(struct mem_control_block); /* Возвращаем указатель */ return memory_location; } Это наш Memory Manager. Теперь его необходимо собрать, для использования в своих программах.
Чтобы построить наш malloc-подобный allocator, нужно набрать следующую команду (мы не затронули такие функции как realloc(), но malloc() и free() являются наиболее значимыми):
Листинг 7: Компиляция
gcc -shared -fpic malloc.c -o malloc.so На выходе получим файл malloc.so, который является библиотекой и содержит наш код.
На Unix системах, вы можете использовать свой allocator, вместо системного. Делается это так:
Листинг 8: Заменяем стандартный malloc
LD_PRELOAD=/path/to/malloc.so export LD_PRELOAD LD_PRELOAD это переменная среды окружения (environment variable). Она используется динамическим линковщиком (dynamic linker) для определения символов, которые содержаться в библиотеке, перед тем как эта библиотека будет подгружена каким-либо приложением. Это подчёркивает важность символов в динамичких библиотеках. Таким образом, приложения, которые будут создаваться в рамках текущей сессии, будут использовать malloc(), которой мы только что написали. Некоторые приложения не используют malloc(), но это скорее исключение, чем правило. Другие же, которые использую аллокаторы на подобии realloc(), или которые не имеют представления о внутреннем поведении malloc(), скорее всего упадут. Ash shell (ash — это командная оболочка UNIX подобных систем) отлично работает с нашим malloc аллокатором.
Если вы хотите убедиться в том, что используется именно ваш malloc(), можете добавить вызов write() в начало ваших функций.
В плане функционала, наш менеджер памяти (Memory manager) оставляет желать лучшего, но он отлично подходит в качестве примера для демонстрации работы. Из его недостатков следует отметить:
Т.к. он работает с System break (глобальная переменная), он не может сосуществовать с другими аллокаторами или с mmap.
При распределении, аллокатору, в худшем случае придётся пройти через всю память процесса, которая между прочим также может включать в себя адреса данных, которые хранятся на диске. Это приведёт к тому, что ОС будет тратить время на перемещение данных с диска в вирт. память и обратно.
Он обладает не самой лучше обработкой ошибок, связанных с недостатком памяти (out-of-memory).
Не имеет реализации множества других функций, таких как realloc().
Т.к. sbrk() может выделить больше памяти, чем мы запросили, это повлечёт утечку памяти в конце кучи.
is_available использует 4 байт, хотя по факту, необходим всего один бит.
Аллокатор не обладает потоковой безопасностью (thread-safety).
Не может сливаться в более крупные блоки. (прим. переводчика: допустим мы запрашиваем 32 байти. В памяти есть следующие друг за другом два свободных блока по 16 байт. Аллокатор это не учтёт.)
Использует не тривиальный алгоритм, который потенциально ведёт к фрагментации памяти.
Конечно есть и другие проблемы. Но ведь это только пример!
ссылка на оригинал статьи http://habrahabr.ru/post/270007/
Добавить комментарий