Язык С

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


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



Упражнение 8-6

-------------- Функция из стандартной библиотеки CALLOC(N,SIZE) возвра- щает указатель на "N" объектов размера SIZE, причем соответ- ствующая память инициализируется на нуль. напишите программу для CALLOC, используя функцию ALLOC либо в качестве образца, либо как функцию, к которой происходит обращение.

Упражнение 8-7

--------------- Функция ALLOC принимает затребованный размер, не прове- ряя его правдоподобности; функция FREE полагает, что тот блок, который она должна освободить, содержит правильное значение в поле размера. Усовершенствуйте эти процедуры, затратив больше усилий на проверку ошибок.

Упражнение 8-8

--------------- Напишите функцию BFREE(P,N), которая включает произволь- ный блок "P" из "N" символов в список свободных блоков, уп- равляемый функциями ALLOC и FREE. С помощью функции BFREE пользователь может в любое время добавлять в свободный спи- сок статический или внешний массив.




    Содержание раздела