Язык программирования C



         

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


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




Содержание  Назад  Вперед