8.7. приклад. Розподільник пам’яті
У розділі 5 був описаний простий розподільник пам'яті, що базується на принципі стека. Версія, яку ми напишемо тут, не має обмежень: виклики malloc та free можуть виконуватись у будь-якому порядку; malloc робить запит до операційної системи на виділення пам'яті тоді, коли вона потрібна. Ці програми ілюструють прийоми, що дозволяють отримувати машинно-залежний код порівняно машиннонезалежним способом, і, крім того, вони можуть служити прикладом застосування таких засобів мови, як структури, об'єднання та типи.
Ніякого раніше скомпілюваного масиву фіксованого розміру, з якого виділяються шматки пам'яті, не буде. Функція malloc просить пам'ять у операційної системи при необхідності. Оскільки і
При виникненні запиту на згадку проглядається список вільних блоків, доки не виявиться досить великий блок. Такий алгоритм називається "пошуком першого відповідного" на відміну від алгоритму "пошуку найкращого відповідного", який шукає найменший блок із числа, що задовольняють запиту. Якщо розмір блоку точно відповідає вимогам, то такий блок виключається зі списку і віддається в користування. Якщо розмір блоку більший, ніж потрібно, від нього відрізається потрібна частина - вона віддається користувачеві, а непотрібна залишається у списку вільних блоків. Якщо блоку достатнього розміру не виявилося, то операційна система потребує ще одного великого шматка пам'яті, який приєднується до списку вільних блоків.
Вільний блок містить покажчик на наступний блок у списку, свій розмір та власне вільний простір. Покажчик і розмір є керуючою інформацією і утворюють так званий "заголовок". Щоб спростити вирівнювання, всі блоки створюються кратними розміру заголовка, а заголовоквідповідним чином вирівнюється. Цього можна досягти, сконструюючи об'єднання, яке міститиме відповідну заголовку структуру і найвибагливіший щодо вирівнювання тип. Для конкретності ми вибрали тип long.
typedef long Align; /* для вирівнювання по межі long */ union header < /* заголовок блоку: */
union header *ptr; / * Слід. блок у списку вільних */
unsigned size; /* Розмір цього блоку */
Align x; /* примусове вирівнювання блоку */
typedef union header Header;
Поле Align ніде не використовується; воно необхідно тільки для того, щоб кожен заголовок був вирівняний за "найгіршим" варіантом кордону.
Потрібне число символів округляється в malloc до цілого числа одиниць пам'яті розміром в заголовок (саме це число і записується в поле size (розмір) в заголовку); крім того, до блоку входить ще одна одиниця пам'яті - сам заголовок. Покажчик, який повертається функцією malloc, вказує на вільний простір, а не на заголовок. З вільним простором користувач може робити що завгодно, але якщо він буде писати що-небудь за його межами, то, ймовірно, список зруйнується.
Оскільки пам'ять, керована функцією malloc, не має зв'язності, розміри блоків не можна обчислити за вказівниками, і тому без поля, що зберігає розмір, нам не обійтися.
static Header base; /* Порожній список для поч. запуску * / static Header * freep = NULL; /* початок у списку вільн. блоків */
/* malloc: універсальний розподільник пам'яті */ void *malloc(unsigned nbytes)
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) /* точно потрібного розміру */ prevp->s.ptr = p->s.ptr;
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 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)
bp = (Header *) ap -1; /* покажчик на заголовок блоку */ for (p=freep; !(bp > p & bp s.ptr); p = p->s.ptr) if (p >= p-> s.ptr &(bp >p bp 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;
p->s.ptr = bp->s.ptr; > else
p->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 користувач повинен мати можливість у будь-який час додати до списку вільної пам'яті статичний чи зовнішній масив.