Интерфейс системы UNIX
Переменная base используется для начала работы. Если allocp имеет значение null, как в случае первого обращения к alloc, то создается вырожденный свободный список: он состоит из свободного блока размера нуль и указателя на самого себя. В любом случае затем исследуется свободный список. Поиск свободного блока подходящего размера начинается с того места (allocp ), где был найден последний блок; такая стратегия помогает сохранить однородность диска. Если найден слишком большой блок, то пользователю предлагается его хвостовая часть; это приводит к тому, что в заголовке исходного блока нужно изменить только его размер. Во всех случаях возвращаемый пользователю указатель указывает на действительно свободную область, лежащую на единицу дальше заголовка. Обратите внимание на то, что функция alloc перед возвращением "p" преобразует его в указатель на символы.
Функция morecore получает память от операционной системы. Детали того, как это осуществляется, меняются, конечно, от системы к системе. На системе UNIX точка входа sbrk(n) возвращает указатель на "n" дополнительных байтов памяти.(указатель удовлетворяет всем ограничениям на выравнивание). Так как запрос к системе на выделение памяти является сравнительно дорогой операцией, мы не хотим делать это при каждом обращении к функции alloc. Поэтому функция morecore округляет затребованное число единиц до большего значения; этот больший блок будет затем разделен так, как необходимо. Масштабирующая величина является параметром, который может быть подобран в соответствии с необходимостью.
#define nalloc 128 /*#units to allocate at once*/ static header *morecore(nu) /*ask system for memory*/ unsigned nu; { char *sbrk(); register char *cp; register header *up; register int rnu; rnu=nalloc*((nu+nalloc-1)/nalloc); cp=sbrk(rnu*sizeof(header)); if ((int)cp==-1) /*no space at all*/ return(null); up=(header *)cp; up->s.size=rnu; free((char *)(up+1)); return(allocp); }
Если больше не осталось свободного пространства, то функция sbrk возвращает "-1", хотя null был бы лучшим выбором. Для надежности сравнения "-1" должна быть преобразована к типу int. Снова приходится многократно использовать явные преобразования (перевод) типов, чтобы обеспечить определенную независимость функций от деталей представления указателей на различных машинах.
И последнее - сама функция free. Начиная с allocp, она просто просматривает свободный список в поиске места для введения свободного блока. Это место находится либо между двумя существующими блоками, либо в одном из концов списка. В любом случае, если освободившийся блок примыкает к одному из соседних, смежные блоки объединяются. Следить нужно только затем, чтобы указатели указывали на то, что нужно, и чтобы размеры были установлены правильно.
free(ap) /* put blocke ap in free list*/ char *ap; { register header *p, *g; p=(header*)ap-1; /*point to header*/ for (g=allocp; !(p>g && p>g->s.ptr);g=g->s.ptr) if (g>=g->s.ptr && (p>g || p<g->s.ptr)) break; /*at one end or other*/ if (p+p->s.size==g->s.ptr) { /*join to upper nbr*/ p->s.size += g->s.ptr->s.size; p->s.ptr = g->s.ptr->s.ptr; } else p->s.ptr = g->s.ptr; if (g+g->s.size==p) { /*join to lower nbr*/ g->s.size+=p->s.size; g->s.ptr=p->s.ptr; } else g->s.ptr=p; allocp = g; }
Хотя распределение памяти по своей сути зависит от используемой машины, приведенная выше программа показывает, как эту зависимость можно регулировать и ограничить весьма небольшой частью программы. Использование typedef и union позволяет справиться с выравниванием (при условии, что функция sbrk обеспечивает подходящий указатель). Переводы типов организуют выполнение явного преобразования типов и даже справляются с неудачно разработанным системным интерфейсом. И хотя рассмотренные здесь подробности связаны с распределением памяти, общий подход равным образом применим и к другим ситуациям.
Упражнение 8-6
функция из стандартной библиотеки calloc(n,size) возвращает указатель на "n" объектов размера size, причем соответствующая память инициализируется на нуль. Напишите программу для calloc, используя функцию alloc либо в качестве образца, либо как функцию, к которой происходит обращение.
Упражнение 8-7
функция alloc принимает затребованный размер, не проверяя его правдоподобности; функция free полагает, что тот блок, который она должна освободить, содержит правильное значение в поле размера. Усовершенствуйте эти процедуры, затратив больше усилий на проверку ошибок.
Упражнение 8-8
Напишите функцию bfree(p,n), которая включает произвольный блок "p" из "n" символов в список свободных блоков, управляемый функциями alloc и free. С помощью функции bfree пользователь может в любое время добавлять в свободный список статический или внешний массив.
