Алгоритмы для встроенных систем с ограниченными ресурсами: эффективная работа с памятью, оптимизация по скорости/размеру

Введение

Встроенные (embedded) системы работают в жёстких условиях:

• ограниченный объём ОЗУ и ПЗУ;
• низкая тактовая частота процессора;
• жёсткие требования реального времени;
• энергопотребление;
• отсутствие операционной системы или ОС с минимальными возможностями.

В таких условиях оптимизация кода становится не «хорошим тоном», а жизненной необходимостью. Цель — выполнить задачу:

• за отведённое время;
• в выделенном объёме памяти;
• с предсказуемой задержкой (jitter);
• без сбоев из‑за переполнения стека или кучи.

В статье разберём:

• модели памяти во встроенных системах;
• приёмы экономии ОЗУ и ПЗУ;
• оптимизацию скорости выполнения;
• паттерны безопасного управления памятью;
• примеры кода и метрики.

---

1. Модели памяти во встроенных системах

1.1. Сегменты памяти

Типичное распределение (на примере Cortex‑M):

1. Flash (ПЗУ):
   • код программы (text);
   • константы (rodata).
2. ОЗУ (RAM):
   • глобальные/статические переменные (data, bss);
   • стек (вызовы функций, локальные переменные);
   • куча (динамическое выделение, если есть ОС/менеджер памяти).

1.2. Ограничения

• Flash: 8 КБ – 2 МБ (зависит от МК).
• RAM: 2 КБ – 512 КБ.
• Стек: часто 1–8 КБ (переполнение — крах системы).
• Куча: может отсутствовать (без ОС).

1.3. Что измеряем

• Размер кода (Flash) — байты.
• Статическое ОЗУ — глобальные + статические переменные.
• Динамическое ОЗУ — куча (если используется).
• Глубина стека — максимальный расход стека при вызовах.

---

2. Экономия памяти: приёмы для ОЗУ и ПЗУ

2.1. Оптимизация ПЗУ (Flash)

Цель: уместить код в отведённый объём.

Приёмы:

1. Встраивание функций (inline):
   • устраняет накладные расходы на вызов;
   • увеличивает размер кода (компромисс).
2. Макросы вместо функций (осторожно!):
   • нет пролога/эпилога вызова;
   • риск раздувания кода при частом использовании.
3. Таблицы переходов (jump tables) для состояний:
   • заменяют длинные if‑else на индексный доступ.
4. Сжатие данных:
   • RLE, Huffman для константных массивов (изображения, шрифты);
   • загрузка в RAM при старте.
5. Условная компиляция (#ifdef):
   • выключаем отладку, неиспользуемые модули.
6. Оптимизации компилятора:
   • -Os (оптимизация по размеру);
   • -fdata-sections -ffunction-sections + линкер с --gc-sections (удаление неиспользуемого кода).

Пример: таблица состояний вместо switch

typedef void (*state_handler_t)(void);
state_handler_t state_table[4] = {state_idle, state_run, state_error, state_sleep};
state_table[current_state]();  // вызов по индексу

2.2. Экономия ОЗУ

Цель: снизить статическое и динамическое потребление.

Приёмы:

1. const для констант → в Flash, не в RAM.
2. static для локальных переменных (если допустимо):
   • память выделяется один раз, не на стеке.
3. Битовые поля (bit‑fields):struct flags { unsigned int ready : 1; unsigned int error : 1; unsigned int timeout : 1; } status;
4. Объединения (union) для перекрывающихся данных:
   • одно и то же место под разные типы.
5. Переиспользование буферов:
   • один буфер для разных этапов обработки.
6. Статические буферы вместо динамических:
   • фиксированный массив вместо malloc.
7. Сжатие структур (__attribute__((packed))):
   • убирает выравнивание, экономит байты (риск снижения скорости).

Пример: упакованная структура

struct __attribute__((packed)) packet {
    uint8_t header;
    uint16_t id;
    uint8_t data[8];
};  // Размер: 11 байт (без packed — 12–16 байт)

---

3. Оптимизация скорости выполнения

3.1. Источники замедления

• вызовы функций (пролог/эпилог);
• деление/умножение (особенно плавающая точка);
• доступ к периферии без буферизации;
• частые прерывания;
• алгоритмы с высокой сложностью (O(n2) и хуже).

3.2. Приёмы ускорения

1. Размотка циклов (loop unrolling):
   • уменьшает число проверок условия.
   // Было for (int i = 0; i < 4; i++) sum += arr[i]; // Стало sum = arr[0] + arr[1] + arr[2] + arr[3];
2. Битовые операции вместо деления/умножения:
   • x << 1 ≡ x * 2;
   • x >> 1 ≡ x / 2 (для степеней двойки).
3. Кэширование часто используемых значений:
   • локальная переменная вместо повторного чтения регистра.
4. Использование аппаратных ускорителей:
   • DMA (прямой доступ к памяти);
   • FPU (блок плавающей точки);
   • CRC‑модуль.
5. Минимизация прерываний:
   • обработка пакетов данных за один вход в ISR.
6. Алгоритмы с низкой сложностью:
   • бинарный поиск (O(logn)) вместо линейного (O(n));
   • хеш‑таблицы для быстрого доступа.
7. Профилирование:
   • замер времени выполнения критических секций (таймер, логи).

Пример: битовая проверка вместо %

if ((status & 0x01) != 0) { /* бит 0 установлен */ }  // Быстро
if (status % 2 == 1) { /* нечётное */ }           // Медленно

---

4. Безопасное управление памятью

4.1. Проблемы динамического выделения

• Фрагментация кучи → невозможность выделить блок.
• Утечки памяти (malloc без free).
• Переполнение стека → непредсказуемое поведение.

4.2. Альтернативы malloc/free`

1. Статические пулы памяти:
   • массив фиксированного размера;
   • менеджер выделяет блоки из пула.
2. Буферы фиксированного размера:
   • один буфер на тип данных (например, пакет UART).
3. Объектные пулы:
   • заранее созданные экземпляры структур;
   • флаг «свободен/занят».
4. Stack‑only allocation:
   • все данные на стеке (если глубина предсказуема).

Пример: пул буферов

#define POOL_SIZE 4
#define BUFFER_LEN 64

static uint8_t buffer_pool[POOL_SIZE][BUFFER_LEN];
static bool buffer_free[POOL_SIZE] = {true, true, true, true};

uint8_t* allocate_buffer(void) {
    for (int i = 0; i < POOL_SIZE; i++) {
        if (buffer_free[i]) {
            buffer_free[i] = false;
            return buffer_pool[i];
        }
    }
    return NULL;  // Пул исчерпан
}

void free_buffer(uint8_t *buf) {
    for (int i = 0; i < POOL_SIZE; i++) {
        if (buf == buffer_pool[i]) {
            buffer_free[i] = true;
            return;
        }
    }
}

4.3. Контроль стека

• Статический анализ: инструменты линкера (--print-memory-usage).
• Замеры во время выполнения:
  • заполнение стека «маркерами» при старте;
  • проверка оставшегося пространства.