© Copyright 2006, 2007 Грибов Игорь, e-mail: gribov@depni.sinp.msu.ru
Изменения в версиях. Организация сигнало-безопасной памяти. Программное решение. Вариант с не атомарными семафорами и многопоточностью.
Полная версия раздела задается в виде: версия.подверсия.выпуск.
Номер версии увеличивается при появлении глав, затрагивающих не рассмотренные ранее вопросы. Названия этих глав выносятся в оглавление раздела. Подверсия увеличивается, когда в существующие главы добавляются новые абзацы, рисунки, либо значительно перерабатывается имеющийся материал, существенно изменяя содержание главы. А при внесении лишь незначительных правок в существующие главы увеличивается номер выпуска.
Версия 1.1.0. Приведена новая версия функций sig_malloc(bytes) и sig_free(ptr) в главе «программное решение».
Версия 2.0.0. Добавлена глава «вариант с не атомарными семафорами и многопоточностью».
Не столь редко возникает вполне законное желание использовать динамически выделяемую память во встроенных приложениях. Одним их важнейших требований к такой памяти становится безусловная сигналобезопасность, которая позволяет осуществлять асинхронные, в том числе повторно-входимые запросы выделения и освобождения памяти. В отличие от программ, выполняемых под управлением операционных систем общего назначения, во встроенных приложениях как правило известен размер максимально необходимого сегмента динамической памяти. Это заметно облегчает задачу ее организации, позволяя использовать в качестве буфера массивы статической памяти .
Доступ к каждому буферу защищен отдельным семафором. Размер и число буферов выбираются исходя из потребностей приложения. При запросе памяти осуществляется поиск и выделение первого свободного буфера достаточного размера.
#define MEMSIZE_1 8 #define MEMSIZE_2 32 #define MEMSIZE_3 64 #define MEMSIZE_4 256 #define MEMSIZE_MAX 1234 #define NUMOF_1 1 #define NUMOF_2 2 #define NUMOF_3 2 #define NUMOF_4 1 #define NUMOF_MAX 1
Константы MEMSIZE_* определяют размер сегментов (буферов) динамической памяти в возрастающей последовательности. Константы NUMOF_* задают отличное от нуля число сегментов каждого буфера. Эти параметры определяются соответственно потребностям приложения.
#define NUMOF_MEMBUFS (NUMOF_1 + NUMOF_2 + NUMOF_3 + NUMOF_4 + NUMOF_MAX)
#define NULL ((void *)0)
typedef char int8;
typedef unsigned char unsigned8;
typedef short int16;
typedef unsigned short unsigned16;
typedef int int32;
typedef unsigned int unsigned32;
typedef int align; // Тип данных для выравнивания памяти
struct bufdes {
int16 busy; // Семафор доступа к буферу памяти
void *ptr; // Указатель на начало буфера
} bd[NUMOF_MEMBUFS]; // Описывает состояние всех буферов
union mem1 {
align al;
unsigned8 mb[MEMSIZE_1];
} m1[NUMOF_1]; // Буферы динамической памяти размера MEMSIZE_1
union mem2 {
align al;
unsigned8 mb[MEMSIZE_2];
} m2[NUMOF_2]; // Буферы динамической памяти размера MEMSIZE_2
union mem3 {
align al;
unsigned8 mb[MEMSIZE_3];
} m3[NUMOF_3]; // Буферы динамической памяти размера MEMSIZE_3
union mem4 {
align al;
unsigned8 mb[MEMSIZE_4];
} m4[NUMOF_4]; // Буферы динамической памяти размера MEMSIZE_4
union mmax {
align al;
unsigned8 mb[MEMSIZE_MAX];
} mm[NUMOF_MAX]; // Буферы динамической памяти размера MEMSIZE_MAX
void *sig_malloc(unsigned32 bytes) // sm_0
{
unsigned16 nbuf;
if (bytes == 0 || bytes > MEMSIZE_MAX) return NULL; // sm_4
nbuf = 0;
if (bytes > MEMSIZE_1) nbuf += NUMOF_1; // sm_6
if (bytes > MEMSIZE_2) nbuf += NUMOF_2; // sm_7
if (bytes > MEMSIZE_3) nbuf += NUMOF_3; // sm_8
if (bytes > MEMSIZE_4) nbuf += NUMOF_4; // sm_9
while (nbuf < NUMOF_MEMBUFS) { // sm_10
bd[nbuf].busy++; // sm_11
if (bd[nbuf].busy == 0) return bd[nbuf].ptr; // sm_12
bd[nbuf].busy--; // sm_13
if (bd[nbuf].busy < -1) bd[nbuf].busy = -1; // sm_14
else nbuf++; // sm_15
}
return NULL; // sm_17
}Прототип функции запроса динамической памяти [sm_0] определен подобно прикладному интерфейсу библиотечной функции C malloc(...). В качестве входного параметра sig_malloc(bytes) принимает размер запрашиваемой памяти в байтах. А возвращает указатель на начало выделенного сегмента памяти в случае успеха, либо NULL если выделить память не удалось.
Оператор [sm_4] осуществляет проверку запрашиваемого размера памяти относительно возможностей буфера и если они не соответствуют друг другу возвращается NULL. Такое же значение будет возвращено, если все подходящие буферы оказались заняты [sm_17]. В строках [sm_6 - sm_9] определяется номер первого подходящего по размеру буфера. Цикл [sm_10] пытается с помощью инкрементной операции закрытия семафора [sm_11] захватить свободный буфер. В случае успеха возвращается указатель на начало этого буфера [sm_12] и таким образом завершается выделение памяти приложению. Если же буфер оказался занятым, его семафор декрементируется [sm_13]. Назначение следующего оператора [sm_14] заключается в исправлении ситуации постоянного блокирования ресурса, то есть утечки памяти. Она может возникнуть вследствие асинхронного вызова функции освобождения памяти sig_free(ptr) или неоднократного обращения к ней с одним и тем же значением указателя из-за ошибок в приложении. После исправления значения семафора освободившийся буфер сразу отправляется в работу – переход к очередному буферу [sm_15] не производится.
void sig_free(void *ptr) // sf_0
{
unsigned16 cnt;
for (cnt = 0; cnt < NUMOF_MEMBUFS; cnt++) { // sf_4
if (ptr == bd[cnt].ptr) bd[cnt].busy = -1; // sf_5
}
}Прототип функции освобождения памяти [sf_0] также аналогичен прикладному интерфейсу библиотечной функции C free(...). В качестве параметра sig_free(ptr) принимает указатель, возвращаемый запросом выделения памяти sig_malloc(bytes). Для освобождения буфера последовательно просматриваются все указатели [sf_4] и при обнаружении заданного его семафор явно открывается [sf_5]. Если требуемый указатель не обнаружен, никаких действий не предпринимается.
Если управление семафором осуществляется в пределах одной программной структуры, захват и освобождение ресурса оформляются в виде инкрементных и декрементных операций. Здесь легко контролировать симметричность этих команд, а значит исключить возможность постоянного блокирования ресурса. В случае разнесения операций захвата и освобождения для выполнения последней можно использовать как декрементную операцию, так и явное присваивание значения семафора. Однако, вызов функции освобождения памяти может произойти после выполнения семафорной операции [sm_11] для того же самого буфера (попытки его захвата). Тогда декремент [sm_13], следующий за явным открытием семафора, приведет к его значению менее минус 1. Декрементное открытие семафора лишено этого недостатка, но лишь при условии полной симметричности разнесенных семафорных операций, то есть отсутствия ошибок, способных привести к неоднократному вызову функции освобождения ресурса. Таким образом, если освобождение ресурса выполняется не зависимо от его захвата, следует обязательно предусмотреть корректирующий оператор [sm_14], чтобы избежать постоянного блокирования буфера памяти. Тогда возможно безопасное использование любого алгоритма. Поскольку явное открытие разнесенного семафора делает программный код более прозрачным, будем использовать именно такой метод освобождения ресурса.
void sig_init_malloc(void) // si_0
{
unsigned16 cnt, mbc;
mbc = 0;
for (cnt = 0; cnt < NUMOF_1; cnt++) {
bd[mbc].ptr = m1[cnt].mb; // si_6
mbc++;
}
for (cnt = 0; cnt < NUMOF_2; cnt++) {
bd[mbc].ptr = m2[cnt].mb; // si_10
mbc++;
}
for (cnt = 0; cnt < NUMOF_3; cnt++) {
bd[mbc].ptr = m3[cnt].mb; // si_14
mbc++;
}
for (cnt = 0; cnt < NUMOF_4; cnt++) {
bd[mbc].ptr = m4[cnt].mb; // si_18
mbc++;
}
for (cnt = 0; cnt < NUMOF_MAX; cnt++) {
bd[mbc].ptr = mm[cnt].mb; // si_22
mbc++;
}
for (cnt = 0; cnt < NUMOF_MEMBUFS; cnt++) bd[cnt].busy = -1; // si_25
}Функция sig_init_malloc() осуществляет инициализацию состояния динамической памяти. При этом в структуре bufdes сохраняются адреса начала буферов [si_6, si_10, si_14, si_18, si_22], а их семафоры устанавливаются в открытое состояние [si_25].
Приведенный ниже вариант программы сигнало-безопасной памяти допускает использование не атомарных семафорных операций в однопоточных приложениях. Здесь также выделены критические секции семафоров, дающие возможность применять код и в многопоточной среде. Для этого используются макросы CRITICAL_BEGIN и CRITICAL_END. В контекстно последовательных программах, к которым относится большинство микроконтроллерных приложений, эти макросы могут оставаться не заполненными.
#define MEMSIZE_1 8 #define MEMSIZE_2 32 #define MEMSIZE_3 64 #define MEMSIZE_4 256 #define MEMSIZE_MAX 1234 #define NUMOF_1 1 #define NUMOF_2 2 #define NUMOF_3 2 #define NUMOF_4 1 #define NUMOF_MAX 1 #define NUMOF_MEMBUFS (NUMOF_1 + NUMOF_2 + NUMOF_3 + NUMOF_4 + NUMOF_MAX) #define NULL ((void *)0) #define CRITICAL_BEGIN #define CRITICAL_END
Макросы для выделения критических секций семафоров позволяют использовать код в многопоточной среде. Некоторые операционные системы содержат библиотеки атомарных семафоров и предоставляют соответствующий API. Их применение может оказаться более эффективным по сравнению со “скобками” критических секций, но потребует некоторой модификации программного кода.
typedef char int8;
typedef unsigned char unsigned8;
typedef short int16;
typedef unsigned short unsigned16;
typedef int int32;
typedef unsigned int unsigned32;
typedef int align;
static int16 sem_free; // Семафор освобождения буферов памяти. Может не быть атомарным.
struct bufdes {
int16 busy; // Семафор доступа к буферу памяти (возможно, не атомарный)
unsigned8 capture; // Флаг занятости буфера памяти
void *ptr; // Указатель на начало буфера
} bd[NUMOF_MEMBUFS]; // Описывает состояние всех буферов
static union mem1 {
align al;
unsigned8 mb[MEMSIZE_1];
} m1[NUMOF_1];
static union mem2 {
align al;
unsigned8 mb[MEMSIZE_2];
} m2[NUMOF_2];
static union mem3 {
align al;
unsigned8 mb[MEMSIZE_3];
} m3[NUMOF_3];
static union mem4 {
align al;
unsigned8 mb[MEMSIZE_4];
} m4[NUMOF_4];
static union mmax {
align al;
unsigned8 mb[MEMSIZE_MAX];
} mm[NUMOF_MAX];
static void free_actually(void) // free_0
{
unsigned16 cnt;
CRITICAL_BEGIN
sem_free++; // free_5
if (sem_free == 0) { // free_6
CRITICAL_END
for (cnt = 0; cnt < NUMOF_MEMBUFS; cnt++) { // free_8
if (bd[cnt].capture == 255) { // free_9
bd[cnt].capture = 0; // free_10
bd[cnt].busy = -1; // free_11
}
}
CRITICAL_BEGIN
}
sem_free--; // free_16
CRITICAL_END
}Функция free_actually()осуществляет фактическое освобождение памяти путем сброса флага занятости [free_10] и открытия семафора буфера [free_11], который отмеченного в качестве свободного специальным значением флага занятости [free_9]. Использование этой функции обусловлено требованием взаимно исключающего выполнения операций занятия и освобождения динамической памяти (см. раздел критические разделяемые ресурсы). В то же время, необходимо обеспечить постоянную доступность приложению как функции запроса памяти, так и ее освобождения. Семафор sem_free [free_5], [free_6], [free_16] как раз и осуществляет взаимное исключение этих операций. В однопоточном приложении атомарность манипуляций с sem_free не обязательна, поскольку все операции освобождения памяти производятся в едином последовательно исполняемом цикле [free_8]. Для многопоточных приложений семафорные операции заключаются в “скобки” макросов критических секций CRITICAL_BEGIN и CRITICAL_END.
void *sig_malloc_non_atomic(unsigned32 bytes) // smna_0
{
unsigned16 nbuf;
if (bytes == 0 || bytes > MEMSIZE_MAX) return NULL;
nbuf = 0;
if (bytes > MEMSIZE_1) nbuf += NUMOF_1;
if (bytes > MEMSIZE_2) nbuf += NUMOF_2;
if (bytes > MEMSIZE_3) nbuf += NUMOF_3;
if (bytes > MEMSIZE_4) nbuf += NUMOF_4;
free_actually(); // smna_10
CRITICAL_BEGIN
sem_free++; // smna_12
CRITICAL_END
while (nbuf < NUMOF_MEMBUFS) { // smna_14
CRITICAL_BEGIN
bd[nbuf].busy++; // smna_16
if (bd[nbuf].busy == 0) {
CRITICAL_END
if (bd[nbuf].capture == 0) {
bd[nbuf].capture = 1; // smna_20
CRITICAL_BEGIN
sem_free--;
CRITICAL_END
return bd[nbuf].ptr;
}
} else {
bd[nbuf].busy--; // smna_27
CRITICAL_END
}
nbuf++;
}
CRITICAL_BEGIN
sem_free--;
CRITICAL_END
return NULL;
}Функция запроса памяти sig_malloc_non_atomic(bytes) теперь отвечает и за ее фактическое освобождение. Вызов функции освобождения памяти [smna_10] производится до начала каких-либо операций по захвату подходящего свободного буфера. После этого семафор sem_free закрывается [smna_12], что обеспечивает взаимное исключение операций занятия и освобождения памяти. Таким образом, повторно-входимые запросы не приведут к вызову функции фактического освобождения памяти во время выполнения цикла поиска и захвата свободного буфера [smna_14]. Алгоритм его занятия [smna_16 - smna_20] соответствует описанному в разделе критические разделяемые ресурсы. Если текущий буфер оказался занятым, его семафор декрементируется [smna_27]. Здесь, в отличие от примера предыдущей главы, не используется корректирующий оператора типа [sm_14], поскольку семафорные операции захвата [smna_16] и фактического освобождения памяти в функции free_actually()не накладываются друг на друга, а выполняются в режиме взаимного исключения. Для многопоточных приложений семафорные операции заключаются в макросы критических секций CRITICAL_BEGIN и CRITICAL_END, которые обеспечивают как атомарность полных семафорных операций, так и согласованность итоговых значений семафорных переменных.
void sig_free_non_atomic(void *ptr) // sfna_0
{
unsigned16 cnt;
for (cnt = 0; cnt < NUMOF_MEMBUFS; cnt++) {
if (ptr == bd[cnt].ptr) bd[cnt].capture = 255; // sfna_5
}
}Функция освобождения памяти sig_free_non_atomic(ptr) устанавливает специальное значение флага занятости соответствующего буфера [sfna_5]. Его фактическое освобождение произойдет лишь при очередном обращении к функции запроса памяти sig_malloc_non_atomic(bytes). Таким образом обеспечивается взаимно исключающее выполнение операций занятия и освобождения динамической памяти.
void sig_init_malloc_non_atomic(void)
{
unsigned16 cnt, mbc;
mbc = 0;
for (cnt = 0; cnt < NUMOF_1; cnt++) {
bd[mbc].ptr = m1[cnt].mb;
mbc++;
}
for (cnt = 0; cnt < NUMOF_2; cnt++) {
bd[mbc].ptr = m2[cnt].mb;
mbc++;
}
for (cnt = 0; cnt < NUMOF_3; cnt++) {
bd[mbc].ptr = m3[cnt].mb;
mbc++;
}
for (cnt = 0; cnt < NUMOF_4; cnt++) {
bd[mbc].ptr = m4[cnt].mb;
mbc++;
}
for (cnt = 0; cnt < NUMOF_MAX; cnt++) {
bd[mbc].ptr = mm[cnt].mb;
mbc++;
}
for (cnt = 0; cnt < NUMOF_MEMBUFS; cnt++) {
bd[cnt].capture = 0;
bd[cnt].busy = -1;
}
sem_free = -1;
}