Пример - распределитель памяти

В главе 5 мы написали бесхитростный вариант функции

ALLOC. Вариант, который мы напишем теперь, не содержит огра-

ничений: обращения к функциям ALLOC и FREE могут перемежать-

ся в любом порядке; когда это необходимо, функция ALLOC об-

ращается к операционной системе за дополнительной памятью.

Кроме того, что эти процедуры полезны сами по себе, они так-

же иллюстрируют некоторые соображения, связанные с написани-

ем машинно-зависимых программ относительно машинно-независи-

мым образом, и показывают практическое применение структур,

объединений и конструкций TYPEDEF.

Вместо того, чтобы выделять память из скомпилированного

внутри массива фиксированного размера, функция ALLOC будет

по мере необходимости обращаться за памятью к операционной

системе. Поскольку различные события в программе могут тре-

бовать асинхронного выделения памяти, то память, управляемая

ALLOC, не может быть непрерывной. В силу этого свободная па-

мять хранится в виде цепочки свободных блоков. Каждый блок

включает размер, указатель следующего блока и саму свободную

память. Блоки упорядочиваются в порядке возрастания адресов

памяти, причем последний блок (с наибольшим адресом) указы-

вает на первый, так что цепочка фактически оказывается коль-

цом.

При поступлении запроса список свободных блоков просмат-

ривается до тех пор, пока не будет найден достаточно большой

блок. Если этот блок имеет в точности требуемый размер, то

он отцепляется от списка и передается пользователю. Если же

этот блок слишком велик, то он разделяется, нужное количест-

во передается пользователю, а остаток возвращается в свобод-

ный список. Если достаточно большого блока найти не удается,

то операционной системой выделяется новый блок, который

включается в список свободных блоков; затем поиск возобнов-

ляется.

Освобождение памяти также влечет за собой просмотр сво-

бодного списка в поиске подходящего места для введения осво-

божденного блока. Если этот освободившийся блок с какой-либо

стороны примыкает к блоку из списка свободных блоков, то они

объединяются в один блок большего размера, так что память не

становится слишком раздробленной. Обнаружить смежные блоки

просто, потому что свободный список содержится в порядке

возрастания адресов.

Одна из проблем, о которой мы упоминали в главе 5, зак-

лючается в обеспечении того, чтобы возвращаемая функцией

ALLOC память была выровнена подходящим образом для тех

объектов, которые будут в ней храниться. Хотя машины и раз-

личаются, для каждой машины существует тип, требующий наи-

больших ограничений по размещению памяти, если данные самого

ограничительного типа можно поместить в некоторый определен-

ный адрес, то это же возможно и для всех остальных типов.

Например, на IBM 360/370,HONEYWELL 6000 и многих других ма-

шинах любой объект может храниться в границах, соответствую-

щим переменным типа DOUBLE; на PDP-11 будут достаточны пере-

менные типа INT.

Свободный блок содержит указатель следующего блока в це-

почке, запись о размере блока и само свободное пространство;

управляющая информация в начале называется заголовком. Для

упрощения выравнивания все блоки кратны размеру заголовка, а

сам заголовок выровнен надлежащим образом. Это достигается с

помощью объединения, которое содержит желаемую структуру за-

головка и образец наиболее ограничительного по выравниванию

типа:

TYPEDEF INT ALIGN; /*FORCES ALIGNMENT ON PDP-11*/

UNION HEADER \(/*FREE BLOCK HEADER*/

STRUCT \(

UNION HEADER *PTR; /*NEXT FREE BLOCK*/

UNSIGNED SIZE; /*SIZE OF THIS FREE BLOCK*/

\) S;

ALIGN X; /*FORCE ALIGNMENT OF BLOCKS*/

\);

TYPEDEF UNION HEADER HEADER;

Функция ALLOC округляет требуемый размер в символах до

нужного числа единиц размера заголовка; фактический блок,

который будет выделен, содержит на одну единицу больше,

предназначаемую для самого заголовка, и это и есть значение,

которое записывается в поле SIZE заголовка. Указатель, возв-

ращаемый функцией ALLOC, указывает на свободное пространст-

во, а не на сам заголовок.

STATIC HEADER BASE; /*EMPTY LIST TO GET STARTED*/

STATIC HEADER *ALLOCP=NULL; /*LAST ALLOCATED BLOCK*/

CHAR *ALLOC(NBYTES)/*GENERAL-PURPOSE STORAGE ALLOCATOR*/

UNSIGNED NBYTES;

\(

HEADER *MORECORE();

REGISTER HEADER *P, *G;

REGISTER INT NUNITS;

NUNITS=1+(NBYTES+SIZEOF(HEADER)-1)/SIZEOF(HEADER);

IF ((G=ALLOCP)==NULL) \(/*NO FREE LIST YET*/

BASE.S PTR=ALLOCP=G=&BASE;

BASE.S.SIZE=0;

\)

FOR (P=G>S.PTR;; G=P, P=P->S.PTR) \(

IF (P->S.SIZE>=NUNITS) \(/*BIG ENOUGH*/

IF (P->S.SIZE==NUNITS) /*EXACTLY*/

G->S.PTR=P->S.PTR;

ELSE \(/*ALLOCATE TAIL END*/

P->S.SIZE-=NUNITS;

P+=P->S.SIZE;

P->S.SIZE=NUNITS;

\)

ALLOCP=G;

RETURN((CHAR *)(P+1));

\)

IF(P==ALLOCP) /*WRAPPED AROUND FREE LIST*/

IF((P=MORECORE(NUNITS))==NULL)

RETURN(NULL); /*NONE LEFT*/

\)

\)

Переменная 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 обеспечивает подходящий указатель). Переводы типов

организуют выполнение явного преобразования типов и даже

справляются с неудачно разработанным системным интерфейсом.

И хотя рассмотренные здесь подробности связаны с распределе-

нием памяти, общий подход равным образом применим и к другим

ситуациям.