Как известно стандартные функции динамического выделения памяти calloc , malloc не являются детерминированными по времени. При написании программ под микроконтроллер это вряд ли подходит. То есть в условиях с ограниченной памятью наступает момент когда выделение свободного блока памяти резко замедляется, что в большинстве случаев недопустимо в системе реального времени. Это замедление происходит из-за поиска блока памяти нужного размера. Кроме того реализация этих функций может вообще отличаться от компилятора к компилятору. Из за этого возникает идея написать свой менеджер памяти.
Есть разные алгоритмы аллокации , но они приводят к фрагментации. Поэтому , например, операционные системы реального времени содержат свои менеджеры памяти ( memory manager). И это как правило менеджер памяти для выделения блоков фиксированной длинны.
Ниже представлена реализация такого кода.
Сначала объявим структуру memory partion для того можно было работать с несколькими менеджерами памяти.
typedef struct
{
void *pMemFree; // Free block pointer
unsigned char BlkSize; // Size block of the partition
unsigned int BlkNum; // Number blocks in the partition
unsigned int BlkFree; // Number free blocks in the partiotion
}MEM_PART;
Практически нам понадобятся три функции:
1. Инициализации
2. Получить блок памяти
3. Вернуть блок обратно
Функция инициализации строит список из свободных блоков памяти.Далее работа всегда будет идти через голову списка.
void InitMem(MEM_PART * pMem,void *addr,unsigned char size,unsigned int num)
{
unsigned int i;
void** pLink;
unsigned char * pBlk;
pLink = (void**)addr;
pBlk = (unsigned char *)addr+size;
// The first two bytes is pointer to the next block.
// Create free memory block list
for(i=0;i<num-1;i++)
{
*pLink = (void*)pBlk; // same link list : pBlock->next = pBlk;
pLink = (void **)pBlk; // same link list : pBlock = pBlk;
pBlk+=size;
}
*pLink = 0; // last block pointer =0
pMem->pMemFree = addr;
pMem->BlkSize = size;
pMem->BlkNum = num;
pMem->BlkFree = num;
}
Далее функция которая возвращает указатель на блок памяти , если он есть, и ноль, если блоки закончились.
void *GetMemBlock(MEM_PART *pMem)
{
void **pBlk;
if(pMem->BlkFree >0) // Check if thare are free blocks
{
pBlk = (void **)pMem->pMemFree;
pMem->pMemFree = *pBlk;
pMem->BlkFree--;
return pBlk;
}
else
return 0;
}
И ,наконец , функция высвобождения блока памяти. Опять же нужен указатель на структуру MEM_PART и блок памяти который нужно вернуть.
void PutMemBlock(MEM_PART *pMem,void *pBlk)
{
unsigned char **pLink;
if(pMem->BlkFree < pMem->BlkNum)
{
pLink = (unsigned char **)pBlk;
*pLink = pMem->pMemFree;
pMem->pMemFree = pBlk;
pMem->BlkFree++;
}
}
Хочу обратить внимание этот менеджер памяти работает через список свободных блоков, поэтому нет тут дополнительных затрат памяти. То есть указатели списка находятся в начале свободных блоков,а когда блок взят, то они уже ненужны. Именно поэтому вопросы подобного рода любят задавать на собеседованиях при приеме на работу. Конечно вряд ли кто-нибудь обяжет вас написать такой код на бумаге без багов, но такие приемы нужно знать.
Допустим нужно 10 блоков по 10 байт,то вызов инициализации должен быть таким
... MEM_PART MemPart; unsigned char MemPool[100]; ... InitMem(&MemPart,MemPool,10,10); ...
Этот простой аллокатор был использован в проекте написанном на FreeRTOS, так как его собственный не подошел.
Оставить комментарий