FreeRTOS. Взгляд изнутри

Все статьи цикла

Как FreeRTOS использует память микроконтроллера?

FreeRTOS позволяет создавать и уничтожать объекты, такие как задачи, очереди, семафоры и мьютексы, на этапе выполнения программы — как до, так и после запуска планировщика. Необходимо динамически выделять и освобождать память для размещения этих объектов в ходе выполнения программы. Соответственно во FreeRTOS реализован собственный механизм динамического выделения памяти — менеджер памяти.

Менеджер памяти выделяет память для размещения того или иного объекта из «системной «кучи»» (heap). «Системная куча» во FreeRTOS представляет собой непрерывный массив памяти микроконтроллера, участки которого используются для размещения той или иной структуры данных. Следует помнить, что в большинстве компиляторов Си есть возможность организовать «кучу» для динамического размещения в памяти прикладных данных: она входит в состав стандартной библиотеки языка Си, и для операций с ней предназначены стандартные функции Си, например malloc(), calloc(), free(). Далее будем называть эту «кучу» стандартной.

Размер «системной кучи» FreeRTOS задается в конфигурационном файле FreeRTOSConfig.h макроопределением configTOTAL_HEAP_SIZE.

FreeRTOS расходует память «системной кучи» в следующих ситуациях:

1. Создание задачи. При создании задачи в памяти должны быть размещены блок управления задачей (TCB) и стек задачи.
2. Создание сопрограммы. При создании сопрограммы в памяти размещается блок управления сопрограммой (CCB). Память под стек для каждой сопрограммы не выделяется, так как все сопрограммы в программе используют общий стек — стек той задачи, из которой вызывается API-функция vCoRoutineSchedule().
3. Создание очереди (семафора или мьютекса). В памяти размещается блок управления очередью (QCB) и собственно сами элементы, хранящиеся в очереди. Причем память под все элементы выделяется в полном объеме один раз: если очередь пуста, то все равно память для хранения максимально возможного числа элементов выделена.

Если в программе происходит динамическое создание и удаление задачи, то правильно организовать программу так, чтобы данные, с которыми работает эта задача, также размещались в динамической памяти, которую можно освободить перед удалением задачи. Программисту предоставлена возможность разместить данные прикладной задачи в «системной куче» FreeRTOS. Эта возможность реализуется с помощью программного интерфейса менеджера памяти, который описан в этой статье.

Кроме динамически размещаемых объектов, ядро FreeRTOS для своего функционирования использует множество системных глобальных переменных, которые размещаются в памяти статически — на этапе компиляции проекта.

Например, системная переменная «счетчик системных квантов» xTickCount определена в глобальной области видимости файла tasks.c следующим образом:

PRIVILEGED_DATA static volatile portTickType xTickCount = ( portTickType ) 0U;

Квалификатор доступа static задает для переменной xTickCount область видимости, ограниченной файлом, в котором данная переменная определена: tasks.c. Таким образом, данные ядра FreeRTOS защищены на этапе написания кода прикладных задач: программист, который пишет код прикладной задачи, не имеет доступа к переменным, имеющим квалификатор static и объявленным в других файлах.Макроопределение PRIVILEGED_DATA определено при использовании модуля защиты памяти (MPU) в микроконтроллерах ARM Cortex-M и означает, что данная переменная будет размещена в защищенном регионе памяти (регионе 2), доступ к которому возможен только из привилегированного режима, то есть когда выполняется код FreeRTOS. Таким образом, для микроконтроллеров ARM Cortex-M данные ядра FreeRTOS могут быть «физически» защищены от случайного воздействия прикладных задач. Подробнее об использовании модуля MPU рассказано в [1, № 4’2012]. Для всех портов, кроме FreeRTOS-MPU, значение PRIVILEGED_DATA задано пустым и никак не влияет на переменную xTickCount.

Остальные системные глобальные переменные определены схожим образом в файлах, содержащих исходный код FreeRTOS: tasks.c, list.c, queue.c, croutine.c, timers. c. Это означает, что на этапе написания кода прикладных задач программист не имеет к ним доступа, однако при компоновке проекта физически они будут размещены вперемешку с прикладными глобальными и статическими переменными (если не используется порт FreeRTOS-MPU).

Важно, что сама «системная куча» также размещается в памяти статически — на этапе компиляции проекта, а динамически из нее выделяются блоки памяти.

Итак, на этапе компиляции проекта FreeRTOS размещает в памяти:

1. «Системную кучу» в полном объеме.
2. Системные глобальные и статические переменные.

Объем, занимаемый системными переменными, зависит от конкретного порта и настроек FreeRTOS. Например, для порта AVR и настроек из демонстрационного проекта объем памяти, занимаемый системными переменными, составил 164 байт.

Представление прикладных данных в памяти

Любая задача работает с какими-либо прикладными данными, которые могут быть размещены в памяти следующим образом:

• Глобальные переменные в исходном файле с задачей (задачами).
• Локальные переменные в теле задачи.
• Статические переменные в теле задачи.
• Динамически в стандартной «куче» Си.
• Динамически в «куче» FreeRTOS.

Рассмотрим пример реализации тела задачи с различными способами выделения памяти под прикладные переменные:

/* 1. Глобальные переменные */
long Counter = 5;
char Flag;

portTASK_FUNCTION( vTask1, pvParameters ) {

   /* 2. Локальная переменная задачи */
   int i;
   /* 3. Статические переменные задачи */
   static int num = 155;
   static char ch;
   /* 4. Блок памяти 100 байт в стандартной куче. */
   char *pStand = malloc(100);
   /* 5. Блок памяти 100 байт в куче FreeRTOS. */
   char *pFR = pvPortMalloc(100);
   
   /* Бесконечный цикл */
   for (;;) {
   }
}

В большинстве компиляторов языка Си для микроконтроллеров глобальные и статические переменные размещаются в специальной секции памяти. Для компилятора GCC [5] это будет секция data: компилятор разместит в ней инициализированные переменные (Counter и num из приведенного примера). Неинициализированные переменные компилятор разместит в секции bss: для примера, приведенного выше, это переменные Flag и ch.

Судя по данным таблицы 1, основное отличие между глобальной и статической переменной — это область видимости. Для статической переменной она будет ограничена функцией, в которой эта переменная объявлена. Поэтому рекомендуется по возможности использовать статические переменные вместо глобальных, чтобы избежать потенциальной проблемы, когда в разных исходных файлах объявляются глобальные переменные с одинаковым именем. Хотя в целях повышения эффективности кода рекомендуется использовать локальные переменные вместо статических (операции с локальными переменными выполняются быстрее [5]). Однако при программировании под FreeRTOS следует ограничивать количество локальных переменных, так как если регистров процессора становится недостаточно для хранения всех локальных переменных, то они сохраняются в стеке, тем самым увеличивается вероятность его переполнения.

Программный интерфейс менеджера памяти FreeRTOS

Интерфейс менеджера памяти FreeRTOS очень похож на интерфейс менеджера динамической памяти, входящий в состав стандартной библиотеки языка Си. Интерфейс менеджера памяти представлен тремя операциями и соответственно тремя функциями:

• Выделение памяти — API-функция pvPortMalloc().
• Освобождение памяти — API-функция vPortFree().
• Получение объема свободной памяти «кучи» — API-функция xPortGetFreeHeapSize().

Кроме того, предоставлена возможность обработать ситуацию, когда выделить блок заданного размера невозможно, — с помощью функции обратного вызова vApplicationMallocFailedHook(), вызов которой осуществляется автоматически, если вызов API-функции pvPortMalloc() закончился неудачей.

Рассмотрим эти API-функции подробнее.

Выделение памяти

Прототип API-функции выделения памяти pvPortMalloc():

void *pvPortMalloc( size_t xSize ) PRIVILEGED_FUNCTION;

В качестве аргумента pvPortMalloc() получает размер запрашиваемого блока памяти. Возвращаемое значение — указатель на выделенный блок памяти в случае успешного выделения и NULL, если размер запрашиваемого блока превышает объем свободной памяти «кучи». Кроме того, можно сконфигурировать FreeRTOS так, чтобы при неудачной попытке выделить память API-функцией pvPortMalloc() происходила активация функции обратного вызова vApplicationMallocFailedHook(). Подробнее об этом мы расскажем далее.

Освобождение памяти

Указатель, который вернула API-функция pvPortMalloc(), следует хранить в программе до тех пор, пока блок памяти, на который ссылается этот указатель, не будет освобожден API-функцией vPortFree().

Прототип vPortFree():

void vPortFree( void *pv ) PRIVILEGED_FUNCTION;

В качестве аргумента vPortFree() получает указатель на блок памяти, который необходимо освободить, и ничего не возвращает. В результате вызова vPortFree() память, на которую ссылался указатель pv, станет считаться свободной и будет доступна для размещения в ней других переменных.

Объем свободной памяти

API-функция xPortGetFreeHeapSize() позволяет выяснить, сколько свободной (невыделенной) памяти осталось в «системной куче». Ее прототип:

size_t xPortGetFreeHeapSize( void ) PRIVILEGED_FUNCTION;

Обработка ситуации «отказ» при выделении памятиФункция xPortGetFreeHeapSize() не имеет аргументов и возвращает объем свободной памяти в байтах. xPortGetFreeHeapSize() не учитывает эффект фрагментации памяти. Может сложиться ситуация, когда невозможно выделить блок заданного размера, хотя xPortGetFreeHeapSize() возвращает объем свободной памяти больший, чем размер запрашиваемого блока. Например, если xPortGetFreeHeapSize() вернула значение 1000, то это не означает, что попытка выделить блок памяти размером 500 байт будет успешной, так как в «куче» может не оказаться непрерывного участка свободной памяти больше или равного 500 байт. Подробнее об эффекте фрагментации памяти «кучи» рассказано ниже.

При запросе на выделение блока памяти возможны два варианта:

1. Блок памяти выделен успешно и получен указатель на этот блок.
2. Отказ — в «куче» недостаточно свободной памяти для выделения блока памяти заданного размера (возможны и другие причины).

Если была попытка выделить память непосредственно вызовом API-функции vPortMalloc(), например, для динамического размещения в памяти данных прикладной задачи, то отследить отказ в выделении памяти просто — необходимо проверить возвращаемое API-функцией vPortMalloc() значение на равенство макроопределению NULL. Если оно равно NULL, то менеджер ответил отказом, и память не была выделена.

Кроме явного вызова vPortMalloc() в программе, вызов vPortMalloc() происходит внутри других API-функций при создании объектов FreeRTOS. В этом случае нет возможности напрямую проверить возвращаемое API-функцией vPortMalloc() значение.

В этом случае, чтобы обработать ситуацию отказа, можно использовать функцию обратного вызова vApplicationMallocFailedHook(). Для этого необходимо установить значение макроопределения configUSE_MALLOC_FAILED_HOOK в файле FreeRTOSConfig.h в значение 1, тогда при отказе в выделении памяти автоматически будет вызвана функция vApplicationMallocFailedHook(). Поэтому код прикладной программы должен содержать реализацию vApplicationMallocFailedHook().

Отдельно стоит сказать о макроопределении PRIVILEGED_FUNCTION в прототипах рассмотренных API-функций. Как и в случае с PRIVILEGED_DATA, оно используется только для порта FreeRTOS-MPU и указывает на то, что компоновщик поместит код функций с макроопределением PRIVILEGED_FUNCTION в защищенный регион памяти. Во всех остальных случаях PRIVILEGED_FUNCTION определено с пустым значением.

Отметим, что помимо API-функций менеджера памяти, рассмотренных выше, код FreeRTOS содержит также API-функцию vPortInitialiseBlocks():

void vPortInitialiseBlocks( void ) PRIVILEGED_FUNCTION;

Функция vPortInitialiseBlocks() служит для освобождения всех блоков памяти в «системной куче» (для возвращения ее в первоначальное состояние). Однако, учитывая тот факт, что API-функция vPortInitialiseBlocks() реализована лишь для схемы выделения памяти Heap_1 и практически не встречается в демонстрационных проектах, далее мы рассматривать ее не будем.

Реализация менеджера памяти

FreeRTOS может выполняться на микроконтроллерах разнообразных архитектур. Реализовать менеджер памяти, который смог бы одинаково эффективно работать как на слабых 8-битных микроконтроллерах с небольшим объемом ОЗУ, так и на мощных 32-битных с большим объемом ОЗУ, не представляется возможным. Поэтому дистрибутив FreeRTOS содержит четыре различные реализации менеджера памяти — четыре схемы выделения памяти: heap_1, heap_2, heap_3, heap_4 (heap_4 появилась в составе дистрибутива недавно — начиная с версии FreeRTOS 7.2.0).

Для каждой архитектуры микроконтроллеров существует рекомендованная схема выделения памяти, именно она используется в демонстрационном проекте для данной архитектуры. Тем не менее для конкретного микроконтроллера разработчик может самостоятельно выбрать одну из четырех схем выделения памяти из поставки FreeRTOS.

Каждая схема выделения памяти реализована в виде исходного файла с именем, соответствующим названию схемы: heap_1.c, heap_2.c, heap_3.c или heap_4.c. Эти исходные файлы находятся в директории SourceportableMemMang, что свидетельствует о том, что реализация менеджера памяти вынесена в платформенно-зависимый код FreeRTOS (об этом также говорит префикс Port в именах API-функций выделения памяти).

Каждый исходный файл, соответствующий одной из схем выделения памяти, содержит тела API-функций выделения памяти. Объявления этих функций содержатся в файле portable.h и поэтому доступны из файлов с исходным кодом прикладных задач. Это позволяет использовать менеджер памяти FreeRTOS для динамического размещения в «системной куче» данных прикладных задач.

Выбор одной из схем выделения памяти осуществляется включением в проект одного (и только одного!) из файлов heap_1.c, heap_2.c, heap_3.c или heap_4.c. Рассмотрим преимущества и недостатки, а также реализацию каждой из схем выделения памяти.

Схема выделения памяти heap_1

Характеристика

Зачастую программа под FreeRTOS строится так, что все необходимые задачи, очереди, семафоры и мьютексы создаются перед запуском планировщика и в ходе выполнения программы не уничтожаются. В этом случае отпадает необходимость в реализации операции освобождения памяти: она выделяется перед началом выполнения задач и никогда не освобождается. Реализация менеджера памяти в этом случае оказывается очень простой. Такой подход позволяет исключить такие потенциальные проблемы при динамическом выделении памяти, как фрагментация «кучи» и отсутствие детерминизма, что важно для обеспечения заданного времени реакции системы на внешнее событие.

Именно такой подход реализован в схеме выделения памяти heap_1. Память «системной кучи» единожды распределяется между всеми объектами FreeRTOS, и в таком состоянии «системная куча» пребывает до выключения питания микроконтроллера.

«Системная куча»

Рассмотрим реализацию схемы выделения памяти heap_1. «Системная куча» определена в файле heap_1.c в виде объединения:

static union xRTOS_HEAP
{
   #if portBYTE_ALIGNMENT == 8
      volatile portDOUBLE dDummy;
   #else
      volatile unsigned long ulDummy;
   #endif
   unsigned char ucHeap[ configTOTAL_HEAP_SIZE ];
} xHeap;

Непосредственно «системная куча» задана массивом байт ucHeap, размер массива (то есть размер «кучи» в байтах) задан макроопределением configTOTAL_HEAP_SIZE, которое должно быть определено в конфигурационном файле FreeRTOSConfig.h. Объединение используется для того, чтобы добиться выравнивания массива ucHeap в памяти по границе 8 или 4 байт с применением стандартного синтаксиса языка Си (без использования расширений языка). Значение выравнивания задается размером неиспользуемой переменной — члена объединения dDummy или ulDummy, которая в зависимости от значения макроопределения portBYTE_ALIGNMENT в файле portmacro.h может иметь тип либо portDOUBLE (8 байт), либо unsigned long (4 байт).

Таким образом, «системная куча» задается в виде глобального массива с областью видимости, ограниченной файлом heap_1.c. Массив выровнен по границе 4 или 8 байт.

Выделение блока памяти

Реализация API-функции pvPortMalloc() для схемы выделения памяти heap_1 имеет вид:

void *pvPortMalloc( size_t xWantedSize )
{
void *pvReturn = NULL;
   #if portBYTE_ALIGNMENT != 1
      if( xWantedSize & portBYTE_ALIGNMENT_MASK )
   {
          xWantedSize += ( portBYTE_ALIGNMENT - ( xWantedSize & portBYTE_ALIGNMENT_MASK ) );
   }
   #endif

   vTaskSuspendAll();
   {
      if( ( ( xNextFreeByte + xWantedSize ) < configTOTAL_HEAP_SIZE ) && ( ( xNextFreeByte + xWantedSize ) > xNextFreeByte )
      {
        pvReturn = &( xHeap.ucHeap[ xNextFreeByte ] );
        xNextFreeByte += xWantedSize;
      }
   }
   xTaskResumeAll();

   #if( configUSE_MALLOC_FAILED_HOOK == 1 )
   {
      if( pvReturn == NULL )
      {
         extern void vApplicationMallocFailedHook( void );
         vApplicationMallocFailedHook();
      }
   }
   #endif

   return pvReturn;
}

Прежде всего, API-функция pvPortMalloc() проверяет размер запрашиваемого блока памяти на условие того, чтобы этот размер был кратен макроопределению portBYTE_ALIGNMENT, которое зависит от разрядности конкретного микроконтроллера и определяется для каждого порта FreeRTOS в файле portmacro.h. Для 8-битных архитектур это значение равно 1, для 16-битных — 2, для 32-битных — 4 или 8 байт. Для проверки кратности используется макроопределение portBYTE_ALIGNMENT_MASK — битовая маска, которая позволяет путем побитовой операции И выяснить, является ли число кратным заданному значению. Например, для проверки кратности числу 4 битовая маска должна содержать единицы в разрядах, где должны быть нули в любом числе, которое кратно 4, то есть в младших двух разрядах: 0x0003. Значение битовой маски portBYTE_ALIGNMENT_MASK задано в файле portable.h в зависимости от значения выравнивания portBYTE_ALIGNMENT.

Если размер запрашиваемого блока памяти в байтах не кратен одному машинному слову, то требуемый размер блока памяти увеличивается до ближайшего большего значения, которое кратно одному машинному слову. Таким образом, API-функция pvPortMalloc() выделяет блок памяти с размером, равным или большим запрашиваемого, но кратным разрядности машинного слова конкретной архитектуры.

Системная глобальная переменная xNextFreeByte используется для хранения индекса первого невыделенного байта памяти в массиве ucHeap. Изначально xNextFreeByte устанавливается на первый элемент (то есть байт) в массиве:

static size_t xNextFreeByte = ( size_t ) 0;

При выделении блока памяти индекс xNextFreeByte переустанавливается на байт памяти, следующий за последним байтом только что выделенного блока (рис. 1). Перед этим выполняется проверка, не превысит ли индекс xNextFreeByte размер массива ucHeap.

Рис. 1. Установка индекса xNextFreeByte на следующий свободный байт при выделении блока памяти

Так как индекс xNextFreeByte является разделяемым ресурсом для всех задач в программе, то операции с индексом производятся внутри критической секции, в виде приостановки работы планировщика (вызов API-функций vTaskSuspendAll() — вход в критическую секцию и xTaskResumeAll() — выход из нее).

Если запрашиваемый размер блока памяти не превышает размер оставшейся памяти в массиве ucHeap, то результатом выполнения API-функции pvPortMalloc() становится адрес байта по индексу xNextFreeByte — начало блока памяти. Сам же индекс xNextFreeByte увеличивается на размер этого блока, после чего он указывает на следующий нераспределенный байт памяти.

Если оставшегося свободного места в «куче» недостаточно, то результатом вызова pvPortMalloc() будет значение NULL, индекс xNextFreeByte при этом никуда не переместится. При этом если макроопределение configUSE_MALLOC_FAILED_HOOK в файле FreeRTOSConfig.h задано равным «1», то до выхода из API-функции pvPortMalloc() вызывается функция обратного вызова vApplicationMallocFailedHook().

Освобождение памяти

Как было сказано выше, схема выделения памяти heap_1 не подразумевает операцию освобождения памяти, поэтому исходный файл heap_1.c содержит API-функцию vPortFree() с пустым телом.

Получение объема свободной памяти «кучи»

API-функция xPortGetFreeHeapSize() позволяет получить оставшийся нераспределенный объем памяти «кучи». Для схемы выделения памяти heap_1 он равен размеру всей «кучи» configTOTAL_HEAP_SIZE минус текущее значение индекса xNextFreeByte.

Схема выделения памяти heap_2

Характеристика

Главное отличие схемы выделения памяти heap_2 от heap_1 — это то, что heap_2 позволяет освобождать ранее выделенную память, а следовательно — уничтожать объекты FreeRTOS на этапе выполнения программы. Соответственно, схема heap_2 содержит реализацию API-функции vPortFree().

Так как блоки памяти могут освобождаться в порядке, отличном от того, в котором они были выделены, то «куча» может состоять из нескольких блоков свободной памяти вперемешку с выделенными блоками памяти. Этот эффект носит название фрагментации и характерен также для файловых систем на современных носителях информации. Подробнее эффект фрагментации описан ниже, также далее по тексту приводятся результаты тестирования схемы heap_2 на предмет влияния фрагментации на результат запроса выделения памяти.

Для нахождения подходящего участка свободной памяти, в котором будет размещен запрашиваемый блок памяти, в схеме heap_2 используется алгоритм поиска наилучшего подходящего фрагмента (the best fit algorithm).

Работа алгоритма наилучшего подходящего фрагмента заключается в следующем. Когда pvPortMalloc() запрашивает блок памяти заданного размера, происходит поиск свободного участка с размером как можно ближе к размеру запрашиваемого блока и, естественно, больше или равным ему. Например, если есть свободные участки размером 100, 150, 200 байт и необходимо выделить блок памяти размером 140 байт, то для его размещения будет выбран участок размером 150 байт.

Реализация алгоритма наилучших подходящих фрагментов во FreeRTOS не предусматривает слияния двух примыкающих друг к другу свободных участков в один большой свободный участок. Поэтому при использовании схемы heap_2 характерна сильная фрагментация «кучи». Однако фрагментации можно не опасаться, если размер выделяемых и освобождаемых впоследствии блоков памяти не изменяется в течение выполнения программы.

То есть при создании и уничтожении задач необходимо задавать один и тот же размер стека для каждой задачи. Это же правило касается и очередей: максимальное число элементов в очереди при ее создании/уничтожении нужно оставлять неизменным. Для размещения прикладных данных также следует выделять и освобождать блоки памяти фиксированного размера.

Время выполнения функций pvPortMalloc() и vPortFree() для схемы heap_2 не является детерминированной величиной, однако их реализация значительно эффективнее стандартных функций выделения и освобождения памяти malloc() и free().

«Системная куча»

Определение «системной кучи» для схемы выделения памяти heap_2 ничем не отличается от рассмотренного выше для схемы heap_1:

static union xRTOS_HEAP
{
   #if portBYTE_ALIGNMENT == 8
      volatile portDOUBLE dDummy;
   #else
      volatile unsigned long ulDummy;
   #endif
   unsigned char ucHeap[ configTOTAL_HEAP_SIZE ];
} xHeap;

Физически «системная куча» также представляет собой массив байт, выровненный по границе или 4 или 8 байт.

Однако для схемы выделения памяти heap_2 количество свободных блоков в «куче» — величина заранее неизвестная и меняющаяся в ходе выполнения программы, поэтому для представления блоков свободной памяти используется динамическая структура данных — односвязный список [2]. В начале любого — и свободного, и занятого — блока памяти размещается служебная структура данных xBlockLink:

typedef struct A_BLOCK_LINK
{
   struct A_BLOCK_LINK *pxNextFreeBlock;
   size_t xBlockSize;
} xBlockLink;

Структура xBlockLink содержит размер блока памяти, к которому она относится, — xBlockSize и указатель на следующий свободный блок памяти pxNextFreeBlock. Именно указатель pxNextFreeBlock позволяет связать несколько структур xBlockLink (а следовательно, и блоков памяти) в односвязный список (рис. 2).

Рис. 2. Структура данных в односвязном списке

Односвязный список позволяет двигаться по элементам списка, используя указатель на структуру xBlockLink с помощью простой операции:

xBlockLink *pxLink;
/* ѕ */
pxLink = pxLink->pxNextFreeBlock;

Кроме того, необходимо хранить в памяти или указатель на первый и последний элемент списка, или непосредственно сам первый и последний элемент. Во FreeRTOS используется второй вариант: файл heap_2.c содержит две системные глобальные переменные — структуры xBlockLink, которые соответствуют первому и последнему блоку свободной памяти:

static xBlockLink xStart, xEnd;

Следует отметить, что только свободные блоки памяти объединяются в список, указатели pxNextFreeBlock структур xBlockLink распределенных блоков памяти устанавливаются на конец списка свободных блоков — структуру xEnd.

Новый блок свободной памяти создается в двух случаях:

1. При освобождении памяти — блок, который был распределен (занят), становится свободным.
2. При выделении памяти — когда запрашивается блок размером меньше, чем блок свободной памяти. В этом случае блок свободной памяти делится на две части: одна уходит под выделяемый блок, а другая часть преобразуется в новый блок свободной памяти уже меньшего размера.

При появлении нового блока свободной памяти он помещается в список так, чтобы блоки свободной памяти в списке были отсортированы по возрастанию размера блока. Это возможно благодаря тому, что список позволяет легко добавлять элементы в середину списка. Таким образом, список свободных блоков всегда отсортирован в порядке возрастания размера блока, причем отдельная операция сортировки не проводится: сортированное состояние списка достигается благодаря вставке элементов в «нужное» место.

На рис. 3 приведен пример состояния «кучи», когда в ней находятся три свободных блока памяти и три распределенных.

Рис. 3. Пример состояния «кучи» при использовании схемы выделения памяти heap_2

Указатель pxNextFreeBlock структуры xStart ссылается на самый маленький блок памяти, он в свою очередь (точнее, указатель pxNextFreeBlock его структуры xBlockLink) — на следующий по величине блок памяти и т. д. Указатель pxNextFreeBlock самого большого блока памяти ссылается на структуру xEnd. На нее также ссылаются указатели распределенных блоков памяти: таким образом они помечены как занятые.

Исходный файл heap_2.c содержит определение размера структуры xBlockLink с учетом выравнивания по границе машинного слова:

static const unsigned short heapSTRUCT_SIZE = ( sizeof( xBlockLink ) + portBYTE_ALIGNMENT - ( sizeof( xBlockLink ) % portBYTE_ALIGNMENT ) );

Для подсчета объема нераспределенной памяти «кучи» используется глобальная системная переменная xFreeBytesRemaining, при инициализации она устанавливается равной всему объему «кучи»:

static size_t xFreeBytesRemaining = configTOTAL_HEAP_SIZE;

Выделение блока памяти

Рассмотрим реализацию API-функции выделения памяти pvPortMalloc():

void *pvPortMalloc( size_t xWantedSize )
{
xBlockLink *pxBlock, *pxPreviousBlock, *pxNewBlockLink;
static portBASE_TYPE xHeapHasBeenInitialised = pdFALSE;
void *pvReturn = NULL;

   /* Вход в критическую секцию. */
   vTaskSuspendAll();
   {
   if( xHeapHasBeenInitialised == pdFALSE )
   {
      /* Инициализация «кучи», если это первый вызов pvPortMalloc(). */
      prvHeapInit();
      xHeapHasBeenInitialised = pdTRUE;
   }
   if( xWantedSize > 0 )
   {
      /* Увеличить запрашиваемый размер блока памяти на размер структуры xBlockLink. */
      xWantedSize += heapSTRUCT_SIZE;
      /* Выровнять по границе машинного слова. */
      if( xWantedSize & portBYTE_ALIGNMENT_MASK )
      {
      xWantedSize += ( portBYTE_ALIGNMENT - ( xWantedSize & portBYTE_ALIGNMENT_MASK ) );
      }
   }

   if( ( xWantedSize > 0 ) && ( xWantedSize < configTOTAL_HEAP_SIZE ) )
   {
      /* Список отсортирован в порядке увеличения размера блока. */
      /* Перебор элементов списка до тех пор, пока */
      /* - не будет найден подходящий по размеру, */
      /* - список не пройден до конца. */
      /* Рис. 5а пункт 1. */
      pxPreviousBlock = &xStart;
      /* Рис. 5а пункт 2. */
      pxBlock = xStart.pxNextFreeBlock;
      while( ( pxBlock->xBlockSize < xWantedSize ) && ( pxBlock->pxNextFreeBlock ) )
      {
      pxPreviousBlock = pxBlock;
      pxBlock = pxBlock->pxNextFreeBlock;
      }
      /* Если список не пройден до конца, т. е. найден подходящий свободный блок. */
      if( pxBlock != &xEnd )
      {
      /* Вернуть указатель на "чистый" блок памяти. */
      /* "Перепрыгнуть" структуру xBlockLink в начале блока памяти. */
      /* Рис. 5б пункт 3. */
      pvReturn = ( void * ) ( ( ( unsigned char * ) pxPreviousBlock->pxNextFreeBlock ) + heapSTRUCT_SIZE );
      /* "Выкинуть" из списка свободных блоков только что выделенный блок. */
      /* Рис. 5б пункт 4. */
      pxPreviousBlock->pxNextFreeBlock = pxBlock->pxNextFreeBlock;
      /* Если оставшегося объема в свободном блоке достаточно для размещения
      /* еще одного блока памяти. */
      if( ( pxBlock->xBlockSize - xWantedSize ) > heapMINIMUM_BLOCK_SIZE )
      {
         /* Разделить блок на две части. */
         /* Сформировать новый свободный блок памяти. */
         pxNewBlockLink = ( void * ) ( ( ( unsigned char * ) pxBlock ) + xWantedSize );
         /* Размер нового свободного блока. */
         pxNewBlockLink->xBlockSize = pxBlock->xBlockSize - xWantedSize;
         /* Размер выделенного блока. */
         pxBlock->xBlockSize = xWantedSize;
         /* Поместить новый свободный блок в список, */
         /* не нарушая порядок следования от наименьшего к наибольшему. */
         prvInsertBlockIntoFreeList( ( pxNewBlockLink ) );
      }
      /* Уменьшить счетчик свободной памяти на размер только что выделенного блока. */
      xFreeBytesRemaining -= pxBlock->xBlockSize;
      }
      }
      }
      /* Выход из критической секции. */
      xTaskResumeAll();

      #if( configUSE_MALLOC_FAILED_HOOK == 1 )
      {
      if( pvReturn == NULL )
      {
         extern void vApplicationMallocFailedHook( void );
         vApplicationMallocFailedHook();
      }
      }
      #endif

      return pvReturn;
}

Так как «системная куча» — это разделяемый ресурс для всех задач в программе, то доступ к ней организован с использованием механизма взаимного исключения — критической секции. Все операции осуществляются внутри критической секции, организованной с помощью остановки планировщика API-функцией vTaskSuspendAll() и возобновления работы — xTaskResumeAll().

Далее происходит проверка, первый ли это вызов pvPortMalloc(), для этого используется статическая переменная-флаг xHeapHasBeenInitialised, которая определяет, была ли произведена инициализация «кучи». Если инициализация не прошла, то вызывается системный макрос prvHeapInit():

#define prvHeapInit()
{
   xBlockLink *pxFirstFreeBlock;
   xStart.pxNextFreeBlock = ( void * ) xHeap.ucHeap;
   xStart.xBlockSize = ( size_t ) 0;
   xEnd.xBlockSize = configTOTAL_HEAP_SIZE;
   xEnd.pxNextFreeBlock = NULL;
   pxFirstFreeBlock = ( void * ) xHeap.ucHeap;
   pxFirstFreeBlock->xBlockSize = configTOTAL_HEAP_SIZE;
   pxFirstFreeBlock->pxNextFreeBlock = &xEnd;
}

В результате вызова макроса prvHeapInit() в «куче» размещается один свободный блок памяти с размером, равным общему объему «кучи» configTOTAL_HEAP_SIZE. Первый элемент списка свободных блоков — структура xStart — указывает на свободный блок. Структура xBlockLink, входящая в этот свободный блок, указывает на последний элемент списка — структуру xEnd (рис. 4).

Рис. 4. Состояние «кучи» после инициализации (схема heap_2)

Далее рассмотрим поэтапно процесс выделения нового блока памяти для случая, когда «куча» только что проинициализирована и не содержит ни одного распределенного блока (рис. 5).

Рис. 5. Выделение нового блока памяти для схемы heap_2

Происходит перебор свободных блоков памяти в поиске первого подходящего по размеру. Для перебора используются два указателя:

• pxBlock — ссылается на текущий блок;
• pxPreviousBlock — ссылается на предыдущий по списку.

Прежде всего указатель pxPreviousBlock устанавливается на структуру xStart (пункт 1 на рис. 5а), а pxBlock — соответственно, на первый свободный блок, точнее сказать, на структуру xBlockLink первого свободного блока (пункт 2 на рис. 5а).

Далее внутри цикла while() происходит проход по всем свободным блокам памяти до тех пор, пока не найден блок равного или большего размера, чем запрашиваемый, или пока в процессе перебора не будет достигнут последний элемент списка — структура xEnd, которая содержит NULL в поле pxNextFreeBlock.

В нашем случае ни одной итерации цикла while() не произойдет, так как первый свободный блок подходит по размеру, указатели pxBlock и pxPreviousBlock не изменятся.

Далее производится проверка — не дошел ли указатель pxBlock до последнего элемента в списке — структуры xEnd. В нашем случае нет, следовательно, подходящий свободный блок найден, можно получить указатель на его начало — указатель pvReturn. Его значение возвращается при выходе из функции pvPortMalloc, и он изначально установлен в значение NULL. pvReturn устанавливается на начало блока выделяемой памяти (рис. 5б, пункт 3). Значение pvReturn получается как значение указателя pxPreviousBlock→ pxNextFreeBlock, увеличенное на размер структуры xBlockLink.

Далее необходимо «выкинуть» только что распределенный блок из списка свободных. На данном этапе список свободных блоков состоит из одного блока, поэтому после его удаления из списка свободных получится ситуация, когда начало списка xStart указывает на его конец xEnd (рис. 5б, пункт 4).

Далее необходимо выяснить, достаточен ли размер блока для разделения его на две части — только что выделенный блок и новый свободный блок памяти. Для этого используется указатель pxBlock, который все еще ссылается на выделенный блок памяти.

Минимально возможный размер блока памяти задается макроопределением heapMINIMUM_BLOCK_SIZE, равным удвоенному размеру структуры xBlockLink:

#define heapMINIMUM_BLOCK_SIZE ( ( size_t ) ( heapSTRUCT_SIZE * 2 ) )

В данном случае оставшийся объем превышает минимальный размер блока heapMINIMUM_BLOCK_SIZE, поэтому будет создан новый свободный блок памяти.

Для этого используется переменная pxNewBlockLink — указатель на структуру xBlockLink. Указатель pxNewBlockLink устанавливается на следующий адрес сразу за выделенным блоком (рис. 5в, пункт 5). Затем устанавливаются размеры блоков памяти — только что выделенного и нового свободного — путем записи соответствующих значений в поля xBlockSize принадлежащих им структур xBlockLink.

Рис. 5. Выделение нового блока памяти для схемы heap_2

После этого необходимо поместить новый свободный блок памяти в список свободных блоков. Это выполняет системный макрос prvInsertBlockIntoFreeList(). Его тело:

#define prvInsertBlockIntoFreeList( pxBlockToInsert )
{
   xBlockLink *pxIterator;
   size_t xBlockSize;
\
   xBlockSize = pxBlockToInsert->xBlockSize;
   /* Проход по элементам списка до тех пор, */
   /* пока следующий блок за pxIterator */
   /* окажется больше или равен размеру вставляемого блока. */
   for (pxIterator = &xStart; /* Рис. 5г, пункт 6 */
      pxIterator->pxNextFreeBlock->xBlockSize < xBlockSize;
      pxIterator = pxIterator->pxNextFreeBlock )
   {\
      /* Тело цикла - пустое. Только перебор элементов списка. */
   }\
   /* Вставить блок pxBlockToInsert на место найденного pxIterator */
   /* Рис. 5г, пункт 7 */
   pxBlockToInsert->pxNextFreeBlock = pxIterator->pxNextFreeBlock;
   /* Рис. 5г, пункт 8 */
   pxIterator->pxNextFreeBlock = pxBlockToInsert;
}

В макросе prvInsertBlockIntoFreeList() применен указатель pxIterator, который «пробегает» все свободные блоки в списке до тех пор, пока не найден тот блок, на место которого будет вставлен новый свободный блок. Таким образом, отсортированный порядок следования блоков в списке не нарушается.

Изначально указатель pxIterator устанавливается на начало списка — структуру xStart (рис. 5г, пункт 6). Ее поле pxNextFreeBlock еще пока указывает на конец списка — структуру xEnd, поле xBlockSize которой задано равным configTOTAL_HEAP_SIZE. Поэтому ни одной итерации цикла for() не произойдет, pxIterator останется на начале списка xStart.

В результате вставки поле pxNextFreeBlock нового свободного блока станет указывать на конец списка xEnd (рис. 5г, пункт 7), а поле pxNextFreeBlock начала списка xStart — на новый свободный блок (рис. 5г, пункт 8). Таким образом, список свободных блоков будет содержать один элемент.

Глобальная системная переменная xFreeBytesRemaining — счетчик свободной памяти — уменьшается на размер только что выделенного блока памяти.

Освобождение памяти

Освобождение блока для схемы выделения памяти heap_2 сводится к включению освобождаемого блока в список свободных, далее он может быть заново распределен. Однако физически после освобождения память блока не изменяется, блок просто признается свободным без изменения его содержимого.

Файл heap_2.c содержит реализацию API-функции vPortFree():

void vPortFree( void *pv )
{
unsigned char *puc = ( unsigned char * ) pv;
xBlockLink *pxLink;
   if( pv )
   {
      /* Переместить указатель puc так, чтобы он указывал на структуру xBlockLink, */
      /* относящуюся к освобождаемому блоку памяти. */
      puc -= heapSTRUCT_SIZE;

      pxLink = ( void * ) puc;

      /* Куча - разделяемый ресурс. Используется критическая секция. */
      vTaskSuspendAll();
      {
         /* Добавить блок в список свободных. */
         prvInsertBlockIntoFreeList( ( ( xBlockLink * ) pxLink ) );
         /* Подсчет кол-ва свободных байт в куче. */
         xFreeBytesRemaining += pxLink->xBlockSize;
      }
   xTaskResumeAll();
   }
}

Рассмотрим поэтапно процесс освобождения блока памяти API-функцией vPortFree(). Состояние «кучи» будет соответствовать двум распределенным блокам и одному свободному блоку, занимающему весь оставшийся объем «кучи» (рис. 6).

Рис. 6. Освобождение блока памяти

В качестве аргумента vPortFree() получает указатель на «чистый» блок памяти (рис. 6а, пункт 1). Чтобы переместить указатель на структуру xBlockLink, из указателя puc вычитается размер этой структуры (адресная арифметика). Далее его значение записывается в переменную pxLink.

Теперь указатель pxLink ссылается на структуру xBlockLink блока памяти, который необходимо освободить (рис. 6б, пункт 2). Далее происходит вызов макроса prvInsertBlockIntoFreeList() с аргументом pxLink. В результате чего блок памяти, на который ссылается pxLink, будет добавлен в список свободных. Рассмотрим подробно, как это происходит.

Как и в случае выделения блока памяти (который был рассмотрен выше), макрос prvInsertBlockIntoFreeList() устанавливает указатель pxIterator на начало списка — структуру xStart (рис. 6в, пункт 3). Далее внутри пустого цикла for() происходит перебор свободных блоков до тех пор, пока не найден тот, чей размер больше или равен размеру блока pxLink. Этим блоком оказывается единственный свободный блок, указатель pxIterator при этом никуда не перемещается. Затем происходит вставка нового блока перед найденным (рис. 6в, пункты 4 и 5).

Получение объема свободной памяти «кучи»

API-функция xPortGetFreeHeapSize() возвращает количество свободных байт в «системной куче». Она реализована как возврат значения переменной xFreeBytesRemaining:

size_t xPortGetFreeHeapSize( void )
{
return xFreeBytesRemaining;
}

Следует иметь в виду, что API-функция xPortGetFreeHeapSize() не учитывает эффект фрагментации памяти «кучи», рассмотренный ниже. То есть может сложиться ситуация, когда выделить блок памяти заданного размера невозможно, хотя API-функция xPortGetFreeHeapSize() возвращает значение, которое больше, чем запрашиваемый размер блока.

Схема выделения памяти heap_3

Для схемы heap_3 характерно отсутствие «кучи» FreeRTOS в виде отдельного массива. Теперь для выделения памяти под нужды FreeRTOS используется «куча» из стандартной библиотеки языка Си.

При использовании схемы heap_3 работа менеджера памяти FreeRTOS целиком и полностью определяется качеством реализации менеджера памяти из стандартной библиотеки Си. Недостатки использования схемы heap_3 сводятся к недостаткам менеджера памяти из стандартной библиотеки Си:

1. Менеджер памяти входит в состав не всех компиляторов Си.
2. Его использование в проекте приводит к дополнительному расходу памяти программ.
3. Отсутствие детерминизма: время выполнения функций malloc() и free() может сильно изменяться от вызова к вызову.

Вызовы API-функций pvPortMalloc() и vPortFree() в схеме heap_3 сводятся к вызовам функций выделения/освобождения памяти malloc() и free() из стандартной библиотеки языка Си. Их вызов заключен в критические секции, с помощью которых достигается реентерабельность (thread safe) API-функций pvPortMalloc() и vPortFree(), то есть предотвращается одновременное выполнение этих функций из разных задач. Кроме того, в API-функцию pvPortMalloc() добавлен вызов функции обратного вызова vApplicationMallocFailedHook(), если выделить блок заданного размера невозможно.

При использовании схемы heap_3 необходимо в настройках компоновщика и компилятора указать, что будет использована стандартная «куча», и задать ее размер. Макроопределение configTOTAL_HEAP_SIZE при использовании схемы heap_3 не влияет на размер «кучи». Кроме того, необходимо подключить к проекту стандартную библиотеку Си stdlib.h.

Схема выделения памяти heap_4

Характеристика

Схема выделения памяти heap_4 появилась во FreeRTOS начиная с версии 7.2.0; для этой схемы в меньшей степени характерна фрагментация памяти (хотя и здесь она полностью не исключена). Схема heap_4 представляет собой усовершенствованную схему heap_2 со следующими отличиями:

1. Теперь прилегающие друг к другу блоки свободной памяти объединяются в один большой блок.
2. При поиске блока свободной памяти используется алгоритм поиска первого подходящего фрагмента First fit algorithm (вместо алгоритма поиска наилучшего подходящего фрагмента в схеме heap_2).

Схема heap_4 допускает освобождение памяти с помощью API-функции vPortFree(), поэтому она предназначена для программ, которые допускают динамическое создание и уничтожение задач и очередей, а также динамическое выделение и освобождение прикладной памяти.

Время выполнения функций pvPortMalloc() и vPortFree() для схемы heap_4 не является детерминированной величиной, однако их реализация значительно эффективнее стандартных функций выделения и освобождения памяти malloc() и free().

В отличие от схемы heap_2 допускается задавать различный размер выделяемых блоков на протяжении выполнения программы. Теперь можно выделять/освобождать блоки памяти случайного размера без опасения, что число свободных блоков неограниченно возрастет и, как следствие, произойдет отказ в выделении памяти.

Следует помнить, что, даже когда схема выделения памяти предусматривает слияние соседних блоков в один блок большего размера, отказ в выделении блока памяти, обусловленный фрагментацией «кучи», полностью не исключен. На рис. 7 приведен пример, когда два малых выделенных блока разделяют весь объем «кучи» так, что в ней не остается достаточно большого непрерывного блока для размещения запрашиваемого блока.

Рис. 7. Отказ в выделении блока памяти, вызванный фрагментацией (схема heap_4)

Реализация выделения/освобождения памяти

Реализация схемы выделения памяти heap_4 очень близка схеме heap_2, рассмотренной выше. Поэтому сосредоточимся только на отличиях схемы heap_4.

В схеме heap_4 «куча» определена точно так же, как и в схемах heap_1 и heap_2, — в виде массива ucHeap.

Для представления множества свободных блоков, как и в схеме heap_2, здесь также используется односвязный список, организованный добавлением в начало блока памяти такой же служебной структуры xBlockLink. Однако теперь список свободных блоков отсортирован не по размеру блока, а по адресу начала блока в памяти. Это сделано для того, чтобы ускорить процесс слияния соседних блоков.

Реализация API-функций выделения/освобождения памяти pvPortMalloc() и vPortFree(), а также получения свободного объема памяти xPortGetFreeHeapSize() перешла из схемы heap_2 практически без изменений.

Изменения затронули реализацию системного макроса prvInsertBlockIntoFreeList(), который выполняет добавление нового блока свободной памяти в список свободных блоков. Теперь макрос реализован в виде функции:

static void prvInsertBlockIntoFreeList( xBlockLink *pxBlockToInsert )
{
xBlockLink *pxIterator;
unsigned char *puc;

   /* Перебор блоков в списке до тех пор, пока не будет найден
   * наиболее близко расположенный свободный блок. */
   for( pxIterator = &xStart; pxIterator->pxNextFreeBlock < pxBlockToInsert; pxIterator = pxIterator->pxNextFreeBlock )
   {
   }

   /* Объединение с блоком, расположенным слева от освобождаемого. */
   puc = ( unsigned char * ) pxIterator;
   if( ( puc + pxIterator->xBlockSize ) == ( unsigned char * ) pxBlockToInsert )
   {
      pxIterator->xBlockSize += pxBlockToInsert->xBlockSize;
      pxBlockToInsert = pxIterator;
   }

   /* Объединение с блоком, расположенным справа от освобождаемого. */
   puc = ( unsigned char * ) pxBlockToInsert;
   if( ( puc + pxBlockToInsert->xBlockSize ) == ( unsigned char * ) pxIterator->pxNextFreeBlock )
   {
      if( pxIterator->pxNextFreeBlock != pxEnd )
      {
         pxBlockToInsert->xBlockSize += pxIterator->pxNextFreeBlock->xBlockSize;
         pxBlockToInsert->pxNextFreeBlock = pxIterator->pxNextFreeBlock->pxNextFreeBlock;
      }
      else
      {
         pxBlockToInsert->pxNextFreeBlock = pxEnd;
      }
   }
   else
   {
      pxBlockToInsert->pxNextFreeBlock = pxIterator->pxNextFreeBlock;
   }

   if( pxIterator != pxBlockToInsert )
   {
      pxIterator->pxNextFreeBlock = pxBlockToInsert;
   }
}

Рассмотрим процесс объединения блоков памяти системной функцией prvInsertBlockIntoFreeList() для случая, когда блок, который необходимо освободить, с двух сторон окружен свободными блоками (рис. 8а).

Рис. 8. Слияние блоков памяти при использовании схемы heap_4

В качестве аргумента prvInsertBlockInto-FreeList() получает pxBlockToInsert — указатель на блок, который необходимо освободить (рис. 8б, пункт 1). Далее в пустом цикле for происходит перебор всех свободных блоков до тех пор, пока указатель pxIterator не укажет на ближайший свободный блок с адресом меньшим, чем у блока, который необходимо освободить (рис. 8б, пункт 2).

Затем проводится проверка, прилегает ли вплотную блок, который нужно освободить, к найденному перебором блоку. В нашем случае это так, и блоки можно объединить. Объединение производится увеличением размера найденного свободного блока на размер освобождаемого (рис. 8в, пункт 3).

Получаем ситуацию, когда освобождаемый блок фактически освобожден: он был присоединен к свободному блоку, который прилегал к нему со стороны меньших адресов (слева на рис. 8в).

Однако сейчас два свободных блока соседствуют друг с другом, поэтому их необходимо объединить. Для этого указатель pxBlockToInsert устанавливается на блок, найденный перебором, — pxIterator (рис. 8в, пункт 4). Проверяем, прилегает ли со стороны старших адресов следующий свободный блок к блоку, на который указывает pxBlockToInsert. В нашем случае это так, поэтому блоки объединяются путем увеличения размера блока pxBlockToInsert на размер свободного блока справа (рис. 8г, пункт 5).

Последним действием указатель на следующий блок pxBlockToInsert переустанавливается на блок, на который указывал только что присоединенный (рис. 8г, пункт 6).

Таким образом, в процессе освобождения блока памяти, которого с обеих сторон окружали свободные блоки, освобождаемый блок присоединяется сначала к левому блоку, а полученный объединением блок в свою очередь присоединяется к правому свободному блоку.

Помимо случая, когда освобождаемый блок с обеих сторон окружен свободными блоками, возможно два варианта:

1. Свободный блок прилегает только с одной стороны. При этом, соответственно, только он и объединяется с освобождаемым блоком.
2. Освобождаемый блок окружен с обеих сторон занятыми блоками. В этом случае он ни с одним блоком не объединяется.

Фрагментация памяти и способы ее уменьшения

Вернемся к рассмотрению схемы выделения памяти heap_2. Как можно было заметить, блоки памяти в этой схеме создаются, но никогда не уничтожаются и не объединяются. Поэтому «системная куча» подвержена дроблению на маленькие фрагменты — эффекту фрагментации. Фрагментация в данном случае означает рост количества блоков памяти и, соответственно, уменьшение среднего размера блока. Сразу следует оговориться, что это будет происходить только при выделении/освобождении блоков случайного размера и в случайном порядке. Из этого вытекают три следствия:

1. Может оказаться, что вся свободная память уже разбита на множество свободных блоков небольшого размера. Суммарный объем этих блоков (то есть свободной памяти) достаточен для размещения блока памяти запрашиваемого размера, но самый большой по размеру блок все же меньше запрашиваемого, поэтому возникает ситуация, когда выделить блок памяти невозможно, хотя свободной памяти в «куче» достаточно, — фрагментация. Пример: размер «кучи» 2000 байт. Выделяем 20 блоков по 100 байт. Затем 10 блоков освобождаем. Объем свободной памяти становится равен 1000 байт. Однако попытка выделить один блок размером, например, 250 байт закончится неудачей, так как теперь «куча» фрагментирована, наибольший свободный блок имеет размер всего 100 байт, и выделить блок больше этого размера невозможно (рис. 9).
2. С увеличением степени фрагментации уменьшается эффективность использования памяти «кучи», так как чем меньше блок памяти, тем хуже соотношение полезного объема блока к объему, занимаемому служебной структурой xBlockLink.
3. С увеличением количества свободных блоков памяти увеличивается время, которое необходимо затратить на выделение/освобождение блока, так как блок заданного размера необходимо искать в более длинном списке свободных блоков.

Тестирование схем выделения памяти FreeRTOS

Автор не смог удержаться от того, чтобы не протестировать предлагаемые в дистрибутиве схемы выделения памяти heap_2 и heap_4. Объектом изучения стала работоспособность менеджера памяти при различной интенсивности выделения/освобождения блоков памяти.

Рис. 9. Отказ в выделении блока памяти, вызванный фрагментацией (схема heap_2)

Тест призван показать, при каких условиях та или иная схема дает отказ в выделении очередного блока памяти. Причем отказ не может быть вызван нехваткой свободного места в куче: эта причина отказа тривиальна и может быть легко отслежена в программе. Интерес представляет отказ, вызванный эффектом фрагментации памяти «кучи».

Для этой цели был создан синтетический тест, имитирующий работу сложной программы со множеством задач. Тест имитирует ситуацию, когда задачи динамически создаются и уничтожаются, причем размер стека у каждой задачи свой. Кроме того, каждая задача запрашивает блок памяти заранее неизвестного размера под прикладные данные.

Нужно сказать, что такого режима работы в реальных программах следует избегать, так как менеджер памяти работает в этом случае в наихудших условиях — выделение блоков памяти случайного размера.

Принцип работы теста

Тестирование проводилось на настольном компьютере, для этого исходные файлы, содержащие схемы выделения памяти heap_2.c и heap_4.c, были извлечены из состава FreeRTOS и скомпилированы отдельно на ПК под управлением Windows в среде Microsoft Visual Studio 2005. Для работы менеджера памяти отдельно от FreeRTOS потребовалось включить в проект заголовочный файл с необходимыми для работы менеджера памяти макроопределениями и прототипами функций:

#define PRIVILEGED_FUNCTION

#define pdFALSE           (0)
#define pdTRUE            (!pdFALSE)

/* Type definitions. */
#define portCHAR           char
#define portFLOAT          float
#define portDOUBLE         double
#define portLONG           long
#define portSHORT          short
#define portSTACK_TYPE     unsigned portLONG
#define portBASE_TYPE      long

#define portBYTE_ALIGNMENT 8
#if portBYTE_ALIGNMENT == 8
#define portBYTE_ALIGNMENT_MASK ( 0x0007 )
#endif

#define configTOTAL_HEAP_SIZE (100000L)

void *pvPortMalloc( size_t xSize ) PRIVILEGED_FUNCTION;
void vPortFree( void *pv ) PRIVILEGED_FUNCTION;
void vPortInitialiseBlocks( void ) PRIVILEGED_FUNCTION;
size_t xPortGetFreeHeapSize( void ) PRIVILEGED_FUNCTION;

Размер «кучи» для этого теста был выбран равным 100 000 байт. Для того чтобы исключить отказ выделения памяти, вызванный нехваткой свободного места, тест в процессе выделения/освобождения блоков памяти контролирует объем свободной памяти «кучи», полученный API-функцией xPortGetFreeHeapSize(). Заданы максимальный и минимальный объемы свободной памяти в процентах от размера «кучи», например 40 и 30% соответственно. Тест поддерживает объем свободной памяти в указанных пределах путем выполнения следующего алгоритма:

1. Если на данный момент объем свободной памяти больше максимального уровня (или объем равен максимальному уровню), то выделить блок памяти случайного размера.
2. Выделять блоки памяти случайного размера до тех пор, пока не будет достигнут минимальный уровень свободной памяти.
3. Когда достигнут минимальный уровень, в случайном порядке освобождать блоки памяти, выделенные ранее, до тех пор, пока объем свободной памяти не достигнет максимального уровня.
4. Когда достигнут максимальный уровень, перейти к пункту 1.

Таким образом, суммарный объем свободной памяти постоянно «плавает» от максимального уровня к минимальному и обратно за счет выделения блоков памяти случайного размера и освобождения ранее выделенных блоков в случайном порядке.

Размер блока памяти выбирается случайным образом из диапазона максимальный и минимальный размер блока, которые также заданы в процентах от размера «кучи». Например, минимальный размер блока 1% от размера «кучи», максимальный — 2%.

Пункты 1–4, приведенные выше, повторяются заданное число итераций, в данном случае 100 000 раз. Если заданное число итераций выполнено и ни одного отказа при выделении блока памяти не зафиксировано, то тест для заданных параметров считается пройденным.

Итак, тест выполняется со следующими параметрами:

1. Размер «кучи»: 100 000 байт.
2. Минимальный и максимальный уровень объема свободной памяти в «куче»: от 10 до 90% размера «кучи».
3. Максимальный и минимальный размер блока памяти: от 0,1 до 20% размера «кучи».
4. Число итераций: 100 000.

Результаты тестирования схемы heap_4

Было принято решение начать именно со схемы heap_4, так как заявлено, что она более стойкая к эффекту фрагментации. Минимальный объем блока выбран равным 0,1%, максимальный менялся от 1 до 20% от размера «кучи». Для каждого диапазона размера блока последовательно выбирались различные уровни свободной памяти «кучи» с шагом в 10%, например 80–90%, 70–80% и т. д. Каждый тест был повторен три раза; если все три раза не было отказа в выделении памяти, то он считался пройденным. Результаты тестирования сведены в таблицу 2.

Примечание. Знак «–» обозначает проваленный тест, знак «+» — пройденный.

Результаты теста вполне предсказуемы: увеличение размера блока и уменьшение объема оставшейся свободной памяти приводит к более вероятному отказу в выделении памяти. По таблице 2 видно, что для схемы heap_4 безопасной можно считать долю свободного места в «куче» на уровне около 50% при размере блока 0,1–10%.

Результаты тестирования схемы heap_2

Проверка схемы heap_2 с помощью приведенного выше теста показала полную непригодность этой схемы для выделения памяти блоками случайного размера. Так, для всех условий из таблицы 2 схема heap_2 не прошла тест ни для одного условия. Схема heap_2 оказалась работоспособной лишь для размера блока в пределах 0,1–0,5% и для остатка свободной памяти «кучи» не меньше 60–70%.

Такой плохой результат есть следствие того, что соседние блоки памяти в схеме heap_2 не могут объединяться в один большой блок. Поэтому их число неуклонно растет с каждым новым запросом/освобождением блока памяти случайного размера.

Сравнение схем heap_2 и heap_4

Оценить влияние эффекта фрагментации памяти в процессе выделения/освобождения блоков позволяют такие параметры, как число блоков свободной памяти в «куче» и средний размер блока. Средний размер блока равен объему всей свободной памяти, деленному на количество свободных блоков.

На рис. 10 показано изменение числа свободных блоков для схем heap_2 и heap_4 с момента запуска теста до момента, когда тест для схемы heap_2 вызвал отказ в выделении памяти. Графики приведены для следующих условий: размер блока памяти — 0,1–5%, уровень свободной памяти — 50–70% от размера «кучи».

Рис. 10. Динамика изменения количества блоков свободной памяти

На рис. 10 видно, что для схемы heap_2 число блоков постоянно растет с каждой новой итерацией, в то время как для схемы heap_4 число блоков выходит на уровень около 10 и остается практически неизменным.

Если взглянуть на изменение среднего размера блока (рис. 11), то также видно, что для схемы heap_4 средний размер блока стабилизируется около какого-то среднего значения, в то время как для схемы heap_2 он очень быстро уменьшается, что напрямую свидетельствует о сильной фрагментации памяти «кучи».

Рис. 11. Динамика изменения среднего размера блока

Таким образом, испытания показали, что схема heap_2 не пригодна для программ, где предполагается динамическое выделение/освобождение блоков памяти, имеющих заранее неизвестный размер. Напротив, испытания схемы heap_4 показали ее работоспособность в таких программах, однако выявили, что для того, чтобы гарантировать безотказную работу в таких условиях, рекомендуется выполнять следующие условия:

• Объем свободной памяти «кучи» не должен опускаться ниже 50%.
• Объем запрашиваемых блоков памяти не должен быть слишком велик (не более 10% от размера «кучи»).

Выводы

Подводя итог, можно дать следующие рекомендации по использованию той или иной схемы выделения памяти:

• Если нет необходимости в динамическом освобождении памяти (задачи не удаляются), то однозначно рекомендуется использовать схему heap_1.
• Если необходимо динамически создавать задачи с неизменным размером стека, то лучше применить схему heap_2.
• Если размер запрашиваемых блоков памяти носит случайный характер, то необходимо выбирать между heap_3 и heap_4. Окончательный выбор будет зависеть от качества реализации стандартного менеджера динамической памяти Си, используемого в heap_3.