Управление памятью: Взгляд изнутри

Доброго времени суток!
Хочу представить вашему вниманию перевод статьи Джонатана Барлетта (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 байт. Аллокатор это не учтёт.);
• Использует нетривиальный алгоритм, который потенциально ведёт к фрагментации памяти;
• Конечно есть и другие проблемы. Но ведь это только пример!

Другие реализации malloc-а
Существуют множество других реализаций malloc(), которые обладаю как сильными так и слабыми сторонами. Существует ряд критериев, которые следует учесть при проектировании аллокаторов:

• Скорость выделения памяти (allocation speed);
• Скорость освобождения (deallocation speed);
• Поведение в многопоточной среде;
• Поведение при кончающейся памяти;
• Размещение кэша;
• Учёт дополнительных расходов на память;
• Поведение в виртуальной памяти;
• Большие и маленькие объекты;
• Стабильная работа в режиме реального времени.

Например для нашего аллокатора плюсом будет быстрое освобождение памяти, минусом — медленное выделение. Также, из-за примитивного алгоритма работы с вирт. памятью, он работает лучше всего с большими объектами.

Существует много разновидностей аллокаторов. Вот некоторые из них:

• Doug Lea malloc: является целым подмножеством аллокаторов, включающее в себя оригинальные Doug Lea аллокаторы, GNU libc аллокаторы и ptmalloc. Deug Lea аллокаторы имеют похожую структуру что и наш аллокатор, но имеет в своём арсенале индексы для более быстрого поиска и может объединять несколько неиспользуемых блоков в один большой. Также имеется поддержка кэширования, которое ускоряет процесс повторного использования недавно освобождённой памяти. ptmalloc — тот же Deug Lea, который был расширен для поддержки многопоточности. Описание Doug Lea’s malloc доступно в списке литературы в конце статьи.
• BSD malloc: BSD Malloc, реализация, которая распространяется в BSD начиная с версии 4.2 и включена в FreeBSD в качестве аллокатора, который размещает в памяти объекты из пула, с заранее известным размером. Он имеет в своём распоряжении размер классов относящихся к объектам — степень двойки минус константа. Так что если вы запросите память под объект, то он просто выделит память любого из классов, размер которого будет подходящим. Это обеспечивает простую реализацию, но возможны издержки памяти. Описание также доступно в конце статьи.
• Hoard: Hoard был написан с целью быстрой работы в многопоточной среде. Поэтому он заточен под работу с блокировками, которые помогают работать с процессами, ожидающими выделения памяти Это может существенно ускорить многопоточные процессы, которые постоянно работаю с памятью. Описание в списке литературы.

Это наиболее известные из множества аллокаторов. Если ваше приложение нуждается в особом распределении памяти, то вы можете написать самопальный (кастомный — custom) аллокатор, который будет работать исходя из поставленных требований. Как бы то ни было, если вы не знакомы с концепцией работы аллокатора, то самописные реализации создадут больше головной боли, чем принесут профита. Для более глубокого введения в предметную область, советую ознакомиться со следующей книгой: Дональд Кнут: Искусство программирования Том 1: Основные алгоритмы — раздел 2.5: Динамическое выделение памяти. Конечно материал устаревший, там не затронута работа с вирт. памятью окружения, но база у алгоритмов практически не изменилась.

В C++ вы можете реализовать свой аллокатор для класса или шаблона с помощью перегрузки (overload) оператора new(). Андрей Александреску в своей книге Современное программирование на C++ описал небольшой объект аллокатора (Глава 4: Размещение в памяти небольших объектов).

Недостатки распределения с помощью malloc()
Не только наш менеджер памяти имеет недостатки, они также присутствуют и у других реализаций. Управление с помощью malloc() довольно опасная вещь для программ, которые хранят данные долгое время и которые должны быть легко доступны. Имея множество ссылок на динамически выделенную память, часто бывает затруднительно узнать, когда её необходимо освободить. Менеджер, обычно легко справляется со своей работой, если время жизни переменной (или время работы с куском памяти), ограничено рамками какой-либо функции (локальные переменные), но для глобальных переменных, чья память используется на всём протяжении работы программы, задача становится значительно сложнее. Также многие API описаны не совсем чётко и становится не понятно, на ком лежит ответственность за управление памятью — на самой программе или на вызванной функции.
Из-за подобных проблем, многие программы работают с памятью согласно собственным правилам. Иногда может показать, что больше операций (прим. переводчика: по тексту “больше кода”) тратится на выделение и освобождение памяти, чем на вычислительную составляющую. Поэтому рассмотрим альтернативные способы управления памятью.

Полу-автоматические (semi-automatic) подходы к управлению памятью

---

Подсчёт ссылок (reference-counting)
Подсчёт ссылок (reference-counting) — это полу-автоматический метод работы с памятью, требующий дополнительного кода и при котором можно не следить за тем, когда память перестаёт использоваться. Reference-counting делает это за вас.

Механизм работы следующий — для каждой динамически выделенной памяти существует поле, которое хранит число ссылающихся на неё ссылок. Если в программе появляется переменная, ссылающаяся на этот кусок памяти, счётчик увеличивается. И наоборот — при уменьшении переменных, ссылающихся на эту память, счётчик уменьшается. При декременте счётчика, происходит проверка — если количество ссылок 0, то память освобождается.

Каждая ссылка ссылающаяся на эту память, просто увеличивает или уменьшает счётчик. Это предотвращает ситуации очистки памяти, когда она используется. В любом случае, вы не должны забывать использовать функции отвечающие за подсчёт ссылок, если работаете с таким типом (“подсчитываемых”) структур. Также встроенные функции и сторонние библиотеки могут не уметь работать с reference-counting или иметь свой механизм работы.

Для реализации этого механизма, вам достаточно двух функций. Первая будет увеличивать счётчик ссылок, вторая уменьшать и освобождать память, если он достиг нуля.
Например функция подсчёта ссылок может выглядеть примерно так:
Листинг 9. Принцип работы reference-counting

/* Описание/определение структур */

/* Основная структура для подсчёта ссылок - Reference counter */
struct refcountedstruct
{
	int refcount;
}

/* Все структуры (которые необходимо отслеживать), должны
 * в качестве первой переменной иметь ссылку refcountedstruct
 */

/* Функции подсчёта ссылок */

/* Инкремент ссылок */
void REF(void *data)
{
	struct refcountedstruct *rstruct;
	rstruct = (struct refcountedstruct *) data;
	rstruct->refcount++;
}

/* Декремент ссылок */
void UNREF(void *data)
{
	struct refcountedstruct *rstruct;
	rstruct = (struct refcountedstruct *) data;
	rstruct->refcount--;

	/* Освобождение памяти, если она осталась бесхозной */
	if(rstruct->refcount == 0)
	{
		free(rstruct);
	}
}

REF и UNREF могут быть более сложными — всё зависит от того, какие цели вы преследуете. К примеру, вы захотите добавить блокировку для многопоточных приложений. Тогда вам нужно будет добавить в refcountedstruct, указатель на функцию для освобождения памяти (подобно деструктору в объектно-ориентированных языках — это необходимо, если ваша структура содержит указатели)
При использовании REF и UNREF, необходимо придерживаться следующих правил при присваивании указателей:

• UNREF — вызывается перед присваиванием
• REF — вызывается после присваивания

Для функций, которые принимают recounted структуры, используются следующие правила:

• REF — вызывается начале функции
• UNREF — вызывается в конце функции

Вот ещё один небольшой пример:

/* EXAMPLES OF USAGE */

/* Структура с поддержкой refcounted */

struct mydata
{
	int refcount; /*  перекочевало из refcountedstruct */
	int datafield1; /* специфичное поле этой структуры */
	int datafield2;

	/* другие определения, если они требуются */

};

/* Используем функции в коде */
void dosomething(struct mydata *data)
{
	REF(data);
	/* Обработка данных */
	
/* когда всё готово */
	UNREF(data);
}

struct mydata *globalvar1;

/* Обратите внимание на одну вещь, мы не уменьшаем
 * refcount т.к. храним ссылку в глоб. переменной
 */

void storesomething(struct mydata *data)
{
	REF(data); /* передаём как параметр */
	globalvar1 = data;
	REF(data); /* ref потому что было присваивание */
	UNREF(data); /* Завершающая функция */
}

Т.к. reference counting достаточно тривиальный механизм, то многие разработчики реализовывают его самостоятельно, избегая сторонних библиотек. Однако их реализации всё равно базируются на аллокаторах подобных malloc и free, которые и занимаются выделением и освобождением памяти. Reference counting находит применение и в языках высокого уровня, например Perl. Данные обязанности возлагаются на сам язык, так что вам не нужно ни о чём беспокоится, если вы конечно не захотите заняться его расширением. Безусловно, подсчёт ссылок незначительно понижает скорость работы, но зато добавляет немного безопасности и простоты в разработку. Рассмотрим основные преимущества:

• Простая реализация;
• Просто использовать;
• Ссылка на объект является частью структуры что обеспечивает хорошую локальность кэша (cache locality).

Так же есть и недостатки:

• Необходимо помнить о вызове функции подсчёта ссылок;
• Нельзя освобождать память если объект есть часть кольцевой структуры;
• Понижение скорости при присваивании указателя;
• Необходима особая осторожность в процессе обработки исключений (try или setjmp()/longjmp() );
• Требуется дополнительная память при работе с ссылками;
• Reference counter находится на первом месте в структуре, что даёт быстрый доступ на большинстве машин;
• Медленное выполнение и дополнительные сложности при работе в многопоточной среде.

C++ может снизить вероятность ошибки посредством «умных» указателей (smart pointers), которые работают с указателями также кропотливо как и reference counting. Если вы является обладателем legacy кода, который работает не под управлением smart pointers (например, linkage в библиотеке C) то дальнейшее использование этого кода приведёт к страшному беспорядку, а код станет сложным и запутанным по сравнению с кодом, который управляется умными указателями. Поэтому их обычно используют только в C++ проектах. Если вы хотите использовать умные указатели, то вам просто необходимо прочитать главу “Умные указатели” книги Современное программирование на C++ (автор Андрей Александрексу).

Memory pools
Memory pools ещё один способ полу-автоматического управления памятью. Он автоматизирует процесс для программ, которые проходят через определенные стадии/фрагменты (stages) выполнения, на каждой стадии которой известно сколько места потребуется программе. В качестве примера можно привести серверные процессы, где выделено много памяти под соединения — у неё максимальное время жизни (lifespan) совпадает с временем жизни соединения. Тот же Apache — каждое соединение это отдельный stage, который имеет свой memory pool. После выполнения фрагмента, память моментально освобождается.

В “пуловой” модели управления, каждое выделение памяти относится к конкретному пулу, из которого память и будет выделена. (прим. переводчика: представьте функцию, в которой 5 локальных переменных типа char. Т.е. заранее известно что при выполнении этой функции, необходимо будет 5 байт памяти. Т.е. тело этой функции это как stage через который проходит программа в процессе выполнения, и можно сразу под него выделить кусок памяти фиксированного размера в 5 байт. Это сэкономит время на поиск и “резку” памяти по мере появления переменных в функции и даст гарантию того, что памяти всегда хватит.) Каждый pool имеет своё время жизни. В apache, pool может иметь время жизни равное времени работы сервера, длительности соединения, времени обработки запроса и т.д… Поэтому, если имеется набор функций, которые требуют память не превышающую размер соединения, то её можно просто выделить из пула соединений и по завершению работы, она будет освобождена автоматически. Кроме того, некоторые реализации дают возможность регистрировать функции очистки (cleanup functions), которые вызываются чтобы выполнить некоторые действия перед тем как пул будет очищен (что-то вроде деструкторов в ООП).

Чтобы использовать пул в своих программах, вы можете просто воспользоваться реализацией obstack (GNU — libc) или Apache Protable Runtime (Apache). Преимущество obstack это то, что он по умолчанию идёт со всеми Linux дистрибутивами. А Apache Portable Runtime это возможность использования на множестве платформ. Чтобы узнать больше об их реализациях, в конце статьи лежат ссылки.

Следующий “надуманный” пример демонстрирует применение obstack:
Листинг 11. Пример с использованием obstack

#include <obstack.h>

#include <stdlib.h>

/* Попробуем использовать obstack функционал */

/* Используем obstack макрос (xmalloc 
 * это тот же malloc, только который сворачивает лавочку, если не удалось получить память (т.е. получен нулевой указатель)
 */

#define obstack_chunk_alloc xmalloc

#define obstack_chunk_free free

/* Pools */

/* Only permanent allocations should go in this pool */
struct obstack *global_pool;

/* Этот pool для соединений (per-connection) */
struct obstack *connection_pool;

/* А этот для запросов (per-request) */
struct obstack *request_pool;

void allocation_failed()
{
	exit(1);
}

int main()
{
	/* Иним пулы */
	global_pool = (struct obstack *)

		xmalloc (sizeof (struct obstack));

	obstack_init(global_pool);

	connection_pool = (struct obstack *)

		xmalloc (sizeof (struct obstack));

	obstack_init(connection_pool);

	request_pool = (struct obstack *)

		xmalloc (sizeof (struct obstack));

	obstack_init(request_pool);

	/* Устанавливаем обработчики ошибок */
	obstack_alloc_failed_handler = &allocation_failed;

	/* Серверный цикл */
	while(1)
	{
		wait_for_connection();

		/* Поступил запрос на соединение */
		while(more_requests_available())
		{
			/* Обрабатываем запрос */
			handle_request();

			/* Чистим использованную память в пуле запросов (request pool) */

			obstack_free(request_pool, NULL);
		}

		/* Время соединения истекло - пора почистить пул */
		obstack_free(connection_pool, NULL);
	}
}

int handle_request()
{
	/* Будьте уверены, что вся память выделяется из пула запросов (request pool) */
	int bytes_i_need = 400;

	void *data1 = obstack_alloc(request_pool, bytes_i_need);

	/* Действия по обработке запроса */

	/* Обработка закончена */
	return 0;
}

Как правило, после выполнения каждого stage-а, происходит освобождение памяти для obstack. Но стоит заметить, если в процессе выполнения потребуется больше памяти, чем выделено для stage, то это может привести к увеличению времени жизни obstack, которое будет сравнимо с временем жизни соединения или глобальной переменной. Если obstack_free() вызвать с параметром NULL, то будет освобожден весь obstack. Вызов с другими параметрами встречается редко.
Преимущества использования пулов:

• Простое управление памятью в приложениях;
• Выделение и освобождение памяти происходит быстро, т.к. всё происходит в рамках пула. Выделение происходит за O(1) и освобождение примерно за то же время (в действительности это O(n), но деление пула имеет огромное значение и приводит к O(1) в большинстве случаев);
• Для пула можно задать обработчик ошибок, что поможет программе не упасть, если память исчерпана;
• Существуют стандартные реализации, которые достаточно просто использовать.

Из недостатков можно отметить следующее:

• Используется в программах, выполнение которых можно разделить на отдельные стадии (stage);
• Часто не работают со сторонними библиотеками;
• Если изменится структура программы, то пул памяти также может изменится, что повлечёт реконструкции системы управления памятью (memory management system);
• Вы должны помнить, из какого пула следует выделять память. Если вы всё же ошибётесь, то это будет достаточно трудно обнаружить.

Сборщик мусора (Garbage collection)
Garbage collection — это полностью автоматическое определение и удаление неиспользуемых объектов из памяти. Он заступает на смену, когда память опускается ниже определённого порога. Как правило, первым делом он проходит по “базовым” данным, с которыми оперирует программа — это стэк (stack), глобальные переменные (global variables) и регистры (registers). Сборщик пытается отследить, использование этих данных в программе. Если были найдены ссылки на эти данные, то он их не трогает, в противном случае память чистится и может быть использована повторно. Для более эффективного управления памятью, множество сборщиков имеет в своём распоряжении своего рода “базу” указателей на структуры и поэтому должны входить в состав языка, чтобы корректно работать.
Типа сборщиков

• Копирующий (Coping): Они делят память на две части и позволяют размещаться объектам только в одной из них. Периодически они начинают копировать данные с одного “отрезка” в другой, начиная с “базовых” элементов. Те секции, куда недавно были перемещены данные становится “активной”, а всё остальное считается мусором. После перемещения данных в новые секции, обновляются все ссылки на эти элементы. Именно по этой причине garbage collector должен быть интегрирован в язык.
• Маркирующий (Mark and sweep): Некоторые данные помечаются специальным тегом. Изначально тег для данных равен нулю, Во время “прогулки” сборщика по “базовым” элементам, он присваивает тег 1 тем данным, которые не используются, тем самым позволяя использовать эту память в дальнейшем.
• Инкрементальный (Incremental): Этому типу сборщиков не требуется обходить все данные за один раз. Проход через всю память порождает проблемы, например предоставление доступа ко всем текущим данным (находящимся в пределах страницы). Инкрементальный сборщик осуществляет несколько коротких проходов и избавляет от долгих задержек в работе программы.
• Консервативный (Conservative): Консервативные сборщики ничего не знают о структуре ваших данных. Они просто ищут байты, которые теоретически могут быть указателями. Если последовательность байт может быть указателем на кусок памяти, то они помечаются как ссылка. Это иногда приводит к проблемам, например когда удаляются данные, а ссылка на них остаётся. (прим. переводчика: например в памяти есть объект типа int и ссылка на него. Данные сборщик может удалить само число, а ссылку на эту память оставить.) Но это случается достаточно редко и только в случаях с небольшими данными. Отличительная особенность данного типа, это их интеграция с любым языком.

Консервативны сбощик Ханса Бема (Hans Boehm) является одним из самых популярных на сборщиков, т.к. является бесплатным и является как консервативным так и инкрементальным. Вы вполне можете использовать как замену вашему системному аллокатору (использование malloc/free вместо собственной API) если построите приложение с флагом -enable-redirect-malloc. Фактически это тоже самое что трикс (с англ. trick — уловка, хитрость) с LD_PRELOAD, который мы использовали в нашем аллокаторе, только в данном случае он поможет привязать сборщик практически к любой программе. Если вы подозреваете что программа страдает от утечки памяти, вы можете использовать данный сборщик, чтобы снизить объём потребляемой памяти. Многие люди использовали эту технику в эпоху первого появления Mozila — тогда она тяжело болела утечкой памяти. Сборщик работает как под Windows так и под Linux.
Преимущества сборщиков:

• Вам не придётся заботиться о двойном освобождении или времени жизни объекта;
• API некоторых сборщиков совпадает с тем, что обычно используется в аллокаторах.

Недостатки:

• Большинство сборщиков вас не оповестит о том, что память была освобождена;
• Почти всегда сборщики работают медленнее, чем другие техники по управлению памятью;
• Проблемы, вызванные неправильной работой сборщика, трудно отлаживать;
• Вы неизбежно получите утечку, если забудете присвоить указателю NULL.

Итоги
Это мир компромиссов: производительность, простота в использовании, простота в реализации, совместимость с многопоточностью. Существует множество шаблонов управления памятью — какой-нибудь обязательно удовлетворит требованиям вашего проекта. Каждый шаблон имеет как свои преимущества так и недостатки. Стандартные методы подходят для большинства программ, но знания об альтернативных методах пригодятся, когда у вашего проекта появятся свои особые требования. В заключении представляю вам сравнительную таблицу по методам управления памятью, рассмотренные в данной статье.
Таблица 1: Сравнение подходов к распределению памяти

Подход	Скорость выделения	Скорость освобождения	Локальность кэша	Простота в использовании	Применимость	Практичность использования в real time	Поддержка SMP и многопоточности
Custom allocator	Зависит от реализации	Зависит от реализации	Зависит от реализации	Высокая сложность	Не применяется	Зависит от реализации	Зависит от реализации
Simple allocator	Быстрая для небольших объёмов	Очень быстрая	Низкая	Простая	Хорошая	Нет	Нет
GNU malloc	Удовлетворительная	Быстрая	Удовлетворительная	Простая	Хорошая	Нет	Удовлетворительная
Hoard	Удовлетворительная	Удовлетворительная	Удовлетворительная	Простая	Хорошая	Нет	Да
Reference counting	-	-	Отличная	Удовлетворительная	Удовлетворительная	Да (зависит от реализации malloc)	Зависит от реализации
Pooling	Удовлетворительная	Очень быстрая	Отличная	Удовлетворительная	Удовлетворительная	Да (зависит от реализации malloc)	Зависит от реализации
Garbage collection	Удовлетворительная (медленная при сборке мусора)	Удовлетворительная	Низкая	Удовлетворительная	Удовлетворительная	Нет	Встречается редко
Incremental garbage collection	Удовлетворительная	Удовлетворительная	Удовлетворительная	Удовлетворительная	Удовлетворительная	Нет	Встречается редко
Incremental conservative garbage collection	Удовлетворительная	Удовлетворительная	Удовлетворительная	Простая	Хорошая	Нет	Встречается редко