Перейти к содержанию

Кольцевой буфер

Прерывание UART принимает байты тогда, когда они приходят, а основной цикл разбирает их тогда, когда освободится. Между ними нужна очередь фиксированного размера, которая не требует динамической памяти и не теряет порядок байтов. Чаще всего это кольцевой буфер.

Обновлено Редакция GAW

Содержание

Кольцевой буфер (ring buffer, circular buffer) — массив фиксированного размера, который используется как очередь: элементы пишутся по индексу головы (head) и читаются по индексу хвоста (tail), а дойдя до конца массива, оба индекса возвращаются в начало. Данные «бегут по кругу», и буфер может пропускать через себя сколько угодно байтов, не требуя ни сдвигов, ни динамической памяти.

Как устроен

Документация ядра Linux формулирует правила кратко: производитель вставляет элементы по голове, потребитель забирает по хвосту, хвост никогда не обгоняет голову, а при достижении конца массива индексы переходят на ноль.

СостояниеУсловие
Пустхвост = голова
Полонголова + 1 = хвост (по модулю размера)
Занято(голова − хвост) по модулю размера

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

Зачем он в микроконтроллере

У USART ATmega328P аппаратный приёмный буфер вмещает всего два символа (DS40002061B, разд. 20.2). Если программа не успела их прочитать, следующий байт теряется и выставляется флаг переполнения. Прерывание приёма перекладывает каждый байт в кольцевой буфер в ОЗУ, а основной цикл забирает их, когда освободится. Аппаратный буфер такого же назначения у периферии называют FIFO; программный кольцевой буфер — его аналог в памяти. Полный разбор с кодом для AVR и STM32 — в статье о кольцевых буферах для UART.

Один писатель и один читатель

Кольцевой буфер хорош тем, что при одном производителе и одном потребителе обходится без блокировок: голову меняет только писатель, хвост — только читатель. Тот же принцип использует SEGGER RTT: у канала «вверх» указатель записи пишет только программа, указатель чтения — только отладчик, и SEGGER прямо отмечает, что так гонка не возникает.

Условия, без которых это не работает:

  • индексы объявлены volatile, иначе компилятор держит их копию в регистре;
  • чтение и запись индекса — одна неделимая операция; на 8-битном AVR это значит индекс не шире байта или атомарный доступ;
  • данные записываются в ячейку раньше, чем сдвигается голова, и компилятор не должен переставить эти записи: на одном ядре с прерыванием для этого достаточно volatile для буфера и индексов или барьера компилятора (например, asm volatile с clobber «memory» в GCC). Аппаратный барьер памяти (DMB на Cortex-M) нужен, когда второй стороной выступает DMA или другое ядро.

Если писателей два (например, два прерывания), без критической секции возникает состояние гонки.

Размер

Размер степенью двойки (16, 32, 64, 128) позволяет переносить индекс маской: head = (head + 1) & (SIZE - 1). Ядро Linux даёт для таких буферов готовые макросы, потому что обычный остаток от деления медленнее. Объём выбирают по худшему случаю: сколько байтов успеет прийти за самый длинный промежуток, когда цикл не читает буфер. Для потока с разбивкой на сообщения поверх буфера работает кадрирование.

Частые вопросы

Как отличить пустой кольцевой буфер от полного?

Классический способ из документации ядра Linux: пустой, когда хвост равен голове, полный — когда следующая позиция головы совпала бы с хвостом, то есть голова стоит на одну ячейку позади хвоста по кругу. Одна ячейка при этом всегда остаётся незанятой. Второй способ — хранить отдельный счётчик элементов, но тогда его меняют и запись, и чтение, и доступ к нему нужно защищать.

Зачем размер кольцевого буфера берут степенью двойки?

Чтобы перенос индекса через конец массива делался побитовым И с маской (размер − 1), а не делением с остатком. На 8-битном AVR деления в системе команд нет, и операция % заметно дороже одной команды AND.

Нужно ли запрещать прерывания при работе с кольцевым буфером?

Если писатель один (например, прерывание приёма) и читатель один (основной цикл), и каждый меняет только свой индекс, запрет не нужен: голову пишет только прерывание, хвост — только цикл. Но индексы должны читаться за одну операцию — на AVR индекс шире 8 бит читается двумя командами и требует атомарного доступа — и быть объявлены volatile.

Источники

  1. D. Howells, P. E. McKenney. Circular Buffers. The Linux Kernel documentation (core-api/circular-buffers) — кольцевой буфер — буфер фиксированного размера с двумя индексами: голова (head), куда производитель вставляет элементы, и хвост (tail), откуда потребитель их берёт; хвост равен голове — буфер пуст, голова на единицу меньше хвоста — полон; оба индекса при достижении конца переходят на 0; при размере, равном степени двойки, остаток от деления заменяют побитовым И; без блокировки — один производитель и один потребитель
  2. SEGGER Knowledge Base: RTT (kb.segger.com/RTT), страница по состоянию на октябрь 2026 — кольцевые буферы каналов в ОЗУ: у буфера «вверх» указатель записи пишет только целевая программа, указатель чтения — только отладчик, поэтому гонки не возникает; указатели равны — буфер пуст
  3. Microchip. ATmega48A/PA/88A/PA/168A/PA/328/P Data Sheet, DS40002061B, 2020 — разд. 20.2 и 20.11.1: у приёмника USART двухуровневый приёмный буфер (FIFO на два символа) и сдвиговый регистр, при переполнении выставляется флаг DOR — программный буфер в ОЗУ снимает эту границу
  4. GCC 16.2 Manual: Extended Asm (clobber «memory») — asm volatile с clobber «memory» не даёт компилятору переносить обращения к памяти через это место — барьер только для компилятора
  5. Arm. Application Note 321: ARM Cortex-M Programming Guide to Memory Barrier Instructions, DAI 0321A, 2012 — в однопроцессорной системе сохраняется порядок программы; барьер нужен, в частности, между обращением процессора к памяти и операцией DMA

Нашли ошибку?

Смотрите также