Керниган и Ритчи - Язык программирования Си (793773), страница 44
Текст из файла (страница 44)
Такой алгоритм называется "поиском первого подходящего" в отличие оталгоритма "поиска наилучшего подходящего", который ищет наименьший блок из числа удовлетворяющихзапросу. Если размер блока в точности соответствует требованиям, то такой блок исключается из списка иотдается в пользование. Если размер блока больше, чем требуется, от него отрезается нужная часть — онаотдается пользователю, а ненужная оставляется в списке свободных блоков. Если блока достаточногоразмера не оказалось, то у операционной системы запрашивается еще один большой кусок памяти, которыйприсоединяется к списку свободных блоков.Процедура освобождения сопряжена с прохождением по списку свободных блоков, поскольку нужно найтиподходящее место для освобождаемого блока. Если подлежащий освобождению блок примыкает с какой-тостороны к одному из свободных блоков, то он объединяется с ним в один блок большего размера, чтобы повозможности уменьшить раздробленность (фрагментацию) памяти.
Выполнение проверки, примыкают либлоки друг к другу, не составляет труда, поскольку список свободных блоков всегда упорядочен повозрастанию адресов.Существует проблема, о которой мы уже упоминали в главе 5, состоящая в том, что память, выдаваемаяфункцией malloc, должна быть соответствующим образом выровнена с учетом объектов, которые будут вней храниться. Хотя машины и отличаются друг от друга, но для каждой из них существует тип,предъявляющий самые большие требования на выравнивание, и, если по некоему адресу допускаетсяразмещение объекта этого типа, то по нему можно разместить и объекты всех других типов. На некоторыхмашинах таким самым "требовательным" типом является double, на других это может быть int или long.Свободный блок содержит указатель на следующий блок в списке, свой размер и собственно свободноепространство.
Указатель и размер представляют собой управляющую информацию и образуют такназываемый "заголовок". Чтобы упростить выравнивание, все блоки создаются кратными размеру заголовка,а заголовок соответствующим образом выравнивается. Этого можно достичь, сконструировав объединение,которое будет содержать соответствующую заголовку структуру и самый требовательный в отношениивыравнивания тип. Для конкретности мы выбрали тип long.typedef long Align; /* для выравнивания по границе long */union header { /* заголовок блока: */struct {union header *ptr; /* след. блок в списке свободных */unsigned size; /* размер этого блока */} s;Align x; /* принудительное выравнивание блока */};typedef union header Header;Поле Align нигде не используется; оно необходимо только для того, чтобы каждый заголовок был выровненпо самому "худшему" варианту границы.Затребованное число символов округляется в malloc до целого числа единиц памяти размером в заголовок(именно это число и записывается в поле size (размер) в заголовке); кроме того, в блок входит еще однаединица памяти — сам заголовок.
Указатель, возвращаемый функцией malloc, указывает на свободноепространство, а не на заголовок. Со свободным пространством пользователь может делать что угодно, но,если он будет писать что-либо за его пределами, то, вероятно, список разрушится.Поскольку память, управляемая функцией malloc, не обладает связностью, размеры блоков нельзявычислить по указателям, и поэтому без поля, хранящего размер, нам не обойтись.Для организации начала работы используется переменная base. Если freep есть NULL (как это бывает припервом обращении к malloc), создается "вырожденный" список свободного пространства; он содержитодин блок нулевого размера с указателем на самого себя. Поиск свободного блока подходящего размераначинается с этого указателя (freep), т. е.
с последнего найденного блока; такая стратегия помогаетподдерживать список однородным. Если найденный блок окажется слишком большим, пользователю будетотдана его хвостовая часть; при этом потребуется только уточнить его размер в заголовке найденногосвободного блока. В любом случае возвращаемый пользователю указатель является адресом свободногопространства, размещающегося в блоке непосредственно за заголовком.static Header base; /* пустой список для нач. запуска */static Header *freep = NULL; /* начало в списке своб. блоков *//* malloc: универсальный распределитель памяти */void *malloc(unsigned nbytes){Header *p, *prevp;Header *morecore(unsigned);unsigned nunits;nunits = (nbytes + sizeof (Header) - 1) / sizeof (Header) + 1;if ((prevp = freep) == NULL) { /* списка своб.
памяти еще нет */base.s.ptr = freep = prevp = &base;base.s.size = 0;}for (p = prevp->s.ptr; ; prevp = p, p = p->s.ptr) {if (p->s.size >= nunits) { /* достаточно большой */if (p->s.size == nunits) /* точно нужного размера */prevp->s.ptr = p->s.ptr;else { /* отрезаем хвостовую часть */p->s.size -= nunits;p += p->s.size;p->s.size = nunits;}freep = prevp;return (void *)(p+1);}if (p == freep) /* прошли полный цикл по списку */if ((p = morecore(nunits)) == NULL)return NULL; /* больше памяти нет */}}Функция morecore получает память от операционной системы. Детали того, как это делается, могут несовпадать в различных системах. Так как запрос памяти у системы — сравнительно дорогая операция, мы быне хотели для этого каждый раз обращаться к malloc. Поэтому используется функция morecore, котораязапрашивает не менее NALLOC единиц памяти; этот больший кусок памяти будет "нарезаться" потом по меренадобности.
После установки в поле размера соответствующего значения функция morecore вызываетфункцию free и тем самым включает полученный кусок в список свободных областей памяти.#define NALLOC 1024 /* миним. число единиц памяти для запроса *//* morecore: запрашивает у системы дополнительную память */static Header * morecore( unsigned nu){char *cp, *sbrk(int);Header *up;if (nu < NALLOC)nu = NALLOC;ср = sbrk(nu * sizeof(Header));if (cp == (char *) -1) /* больше памяти нет */return NULL;up = (Header *) cp;up->s.size = nu;free((void *)(up+1));return freep;}Системный вызов sbrk(n) в UNIXe возвращает указатель на n байт памяти или -1, если требуемогопространства не оказалось, хотя было бы лучше, если бы в последнем случае он возвращал NULL.
Константу 1 необходимо привести к типу char *, чтобы ее можно было сравнить с возвращаемым значением. Это ещеодин пример того, как операция приведения типа делает функцию относительно независимой от конкретногопредставления указателей на различных машинах. Есть, однако, одна "некорректность", состоящая в том, чтосравниваются указатели на различные блоки, выдаваемые функцией sbrk. Такое сравнение негарантировано стандартом, который позволяет сравнивать указатели лишь в пределах одного и того жемассива. Таким образом, эта версия malloc верна только на тех машинах, в которых допускается сравнениелюбых указателей.В заключение рассмотрим функцию free.
Она просматривает список свободной памяти, начиная с freep,чтобы подыскать место для вставляемого блока. Искомое место может оказаться или между блоками, или вначале списка, или в его конце. В любом случае, если подлежащий освобождению блок примыкает ксоседнему блоку, он объединяется с ним в один блок. О чем еще осталось позаботиться, — так это о том,чтобы указатели указывали в нужные места и размеры блоков были правильными./* free: включает блок в список свободной памяти */void free(void *ap){Header *bp, *p;bp = (Header *)ap -1; /* указатель на заголовок блока */for (p=freep; !(bp > p && bp < p->s.ptr); p = p->s.ptr)if (p >= p->s.ptr && (bp > p || bp < p->s.ptr))break; /* освобождаем блок в начале или в конце */if (bp + bp->s.size == p->s.ptr) { /* слить с верхним */bp->s.size += p->s.ptr->s.size; /* соседом */bp->s.ptr = p->s.ptr->s.ptr;} elsebp->s.ptr = p->s.ptr;if (p + p->s.size == bp) { /* слить с нижним соседом */p->s.size += bp->s.size;p->s.ptr = bp->s.ptr;} elsep->s.ptr = bp;freep = p;}Хотя выделение памяти по своей сути — машинно-зависимая проблема, с ней можно справиться, что ииллюстрирует приведенная программа, в которой машинная зависимость упрятана в очень маленькой еечасти.
Что касается проблемы выравнивания, то мы разрешили ее с помощью typedef и union(предполагается, что sbrk дает подходящий в смысле выравнивания указатель). Операции приведения типовпозволяют нам сделать явными преобразования типов и даже справиться с плохо спроектированныминтерфейсом системы. Несмотря на то, что наши рассуждения касались распределения памяти, этот общийподход применим и в других ситуациях.Упражнение 8.6. Стандартная функция calloc(n, size) возвращает указатель на n элементов памятиразмера size, заполненных нулями. Напишите свой вариант callос, пользуясь функцией malloc илимодифицируя последнюю.Упражнение 8.7.
Функция malloc допускает любой размер, никак не проверяя его на правдоподобие; freeпредполагает, что размер освобождаемого блока — правильный. Усовершенствуйте эти программы такимобразом, чтобы они более тщательно контролировали ошибки.Упражнение 8.8. Напишите программу bfree(p, n), освобождающую произвольный блок р, состоящий изn символов, путем включения его в список свободной памяти, поддерживаемый функциями malloc и free.С помощью bfree пользователь должен иметь возможность в любое время добавить в список свободнойпамяти статический или внешний массив.А. Справочное руководствоА 1.
ВведениеДанное руководство описывает язык программирования Си, определенный 31 октября 1989 г. в соответствиис проектом, утвержденным в ANSI в качестве Американского национального стандарта для информационныхсистем: Язык программирования Си, Х3.159-1989 ("American National Standard for Information Systems —Programming Language C, X3.159-1989"). Это описание — лишь один из вариантов предлагаемого стандарта, ане сам стандарт, однако мы специально заботились о том, чтобы сделать его надежным руководством поязыку.Настоящий документ в основном следует общей схеме описания, принятой в стандарте (публикация которогов свою очередь основывалась на первом издании этой книги), однако в организационном плане естьразличия.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
