Алгоритмы динамического управления памятью
Описатели блоков хранятся не вместе с самими блоками, а в отдельном динамическом массиве _heapihfo. Описатель заводится не на непрерывную последовательность свободных байтов, а на каждые 4096 байт памяти (в примере 4.3 именно это значение принимает константа BLOCKSIZE). Благодаря этому мы можем вычислить индекс описателя в _heapinfo, просто разделив на 4096 смещение освобождаемого блока от начала пула.
Для нефрагментированных блоков описатель хранит состояние (занят-свободен) и размер непрерывного участка, к которому принадлежит блок. Благодаря этому, как и в алгоритме парных меток, мы легко можем найти соседей освобождаемого участка памяти и объединить их в большой непрерывный участок.
Для фрагментированных блоков описатель хранит размер фрагмента, счетчик занятых фрагментов и список свободных. Кроме того, все свободные Фрагменты одного размера объединены в общий список – заголовки этих списков собраны в массив _f raghead.
Используемая структура данных занимает больше места, чем применяемая в Классическом алгоритме парных меток, но сокращает объем списка свободных блоков и поэтому имеет более высокую производительность. Средний обьем блока, выделяемого современными программами для ОС общего назначения, измеряется многими килобайтами, поэтому в большинстве случаев повышение накладных расходов памяти оказывается терпимо.
Пример 4.3. Реализация malloc/fгее в GNU LibC. Функция __default_morecore приведена в примере 4.1:
malloc.с
/* Распределитель памяти 'malloc'.
Copyright 1990, 1991, 1992 Free Software Foundation Написана в мае 1989 Mike Haertel.
GNU С Library является свободным программным обеспечением;
вы можете передавать другим лицам и/или модифицировать ее в соответствии
с положениями GNU General Public License версии 2 или (по вашему выбору) любой более поздней версии.
библиотека GNU С распространяется в надежде, что она будет полезна,
но БЕЗ КАКИХ-ЛИБО ГАРАНТИЙ; даже без неявно предполагаемых гарантий
КОММЕРЧЕСКОЙ ЦЕННОСТИ или ПРИГОДНОСТИ ДЛЯ КОНКРЕТНОЙ ЦЕЛИ.
Подробнее см. GNU General Public License.
ВЫ должны были получить копию GNU General Public License вместе с
GNU С Library; см. файл COPYING.
Если вы ее не получили, напишите по адресу:
Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
С автором можно связаться по электронной почте
по адресу mike@ai.rait.edu, или Mike Haertel с/о Free Software Foundation. */
# ifndef _MALLOC_INTERNAL
#define _MALLOC_INTERNAL tinclude <malloc.h>
#endif
#ifdef __ELF_
ipragma weak malloc = __libc_malloc
#endif
/* Как действительно получить дополнительную память. */
__ptr_t (*__morecore) __Р ((ptrdiff_t __size))
= __default_morecore_init;
/* Предоставляемая пользователем отладочная функция (hook) для xmalloc' */
void (*__malloc_initialize_hook) __P ((void));
__ptr_t (*_malloc_hook) __P ((size_t __size));
/* Указатель на основание первого блока. */ char *_heapbase;
* Таблица информационных записей о блоках. Размещается
через align/__free (не malloc/free). */
malloc_info *_heapinfo;
/* Количество информационных записей. */ static size_t heapsize;
/* Индекс поиска в информационной таблице. */ size_t _heapindex;
/* Ограничитель допустимых индексов в информационной таблице */ size_t _heaplimit;
#if 1 /* Adapted from Mike */
/* Счетчик больших блоков, размещенных для каждого из размеров
фрагментов. */
int _fragblocks[BLOCKLOG];
#endif
/* Списки свободных фрагментов по размерам.
*/ struct list _fraghead[BLOCKLOG];
/* Инструментальные переменные.
*/ size_t __chunks_used; size_t _bytes_used; size_t _chunks_free; size_t _bytes_free;
/* Имеем ли мы опыт? */
/* Are you experienced? */
int malloc initialized;
/* Выровненное размещение. */
static __ptr_t align __P ((size_t));
static __ptr_t
align (size)
size_t size; {
__ptr_t result;
unsigned long int adj;
[result = (*__morecore) (size);
adj = (unsigned long int) ((unsigned long int) ((char *) result –
(char *) NULL)) % BLOCKSIZE; lit (adj!= 0)
{
adj = BLOCKSIZE – adj; (void) (*_morecore) (adj); result = (char *) result + adj;
}
return result;