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

Почему кольцевой буфер на N ячеек вмещает только N − 1 байт?

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

Содержание

В кольцевом буфере два индекса: head — куда производитель пишет следующий байт, tail — откуда потребитель читает. Документация ядра Linux описывает классическое правило: буфер пуст, когда указатели равны, и полон, когда голова на единицу «отстаёт» от хвоста. Значит, одна ячейка всегда остаётся пустой.

Почему нельзя заполнить все N

Возьмём буфер на 8 ячеек с индексами, которые заворачиваются по модулю 8:

Записано байтheadtailhead == tailСостояние
000дапусто
330нет3 байта
770нетполон по правилу N − 1
800данеотличимо от «пусто»

Если разрешить восьмой байт, head догонит tail, и потребитель решит, что данных нет, — потеряны все восемь байт. Поэтому запись разрешают, только пока (head+1) mod N≠tail(head + 1) \bmod N \ne tail.

Как вместить все N

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

заполнено=(head−tail) mod 2k,ячейка=индекс&(N−1)\text{заполнено} = (head - tail) \bmod 2^k, \qquad \text{ячейка} = \text{индекс} \mathbin{\&} (N - 1)

Это требует, чтобы N было степенью двойки и не больше половины диапазона индекса. Такой вариант и код для UART разобраны в статье «Кольцевой буфер для UART»; общий принцип очереди — в статье о FIFO.

Когда буфер всё же переполнился

Это значит, что данные приходят быстрее, чем их забирают. Варианты из документации SEGGER RTT: ждать места (нельзя в обработчике прерывания), отбросить новое сообщение целиком или записать столько, сколько влезет. Если же переполняется не программный буфер, а регистр приёмника, теряется байт ещё в железе — это ошибка переполнения. Почему схема с двумя индексами безопасна без запрета прерываний, объясняет статья «Прерывания и общие данные».

Похожие вопросы

Нельзя ли просто завести счётчик элементов?

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

Что лучше при переполнении: терять новые байты или старые?

Зависит от данных. Для команд и пакетов обычно отбрасывают новое и ставят флаг ошибки — разборщик потом ресинхронизируется. Для журнала полезнее свежие записи. SEGGER RTT предлагает три режима: ждать места, отбросить сообщение целиком или записать сколько влезет.

Почему индекс uint8_t ограничивает буфер 128 байтами?

Со свободными индексами заполненность — разность head − tail по модулю 256. Если буфер на 256 ячеек заполнить целиком, разность станет 256, а в uint8_t это 0 — снова «пусто». Поэтому размер должен быть не больше половины диапазона индекса: до 128 для uint8_t, до 32 768 для uint16_t (наш вывод).

Источники

  1. The Linux Kernel documentation. Circular Buffers (Documentation/core-api/circular-buffers.rst) — буфер пуст, когда указатель головы равен указателю хвоста, и полон, когда голова на единицу меньше хвоста; в буфере всегда остаётся пустым один элемент; размер — степень двойки, индекс заворачивается маской size − 1; один производитель и один потребитель
  2. SEGGER Knowledge Base. RTT (Real Time Transfer) — указатель записи меняет только одна сторона, указатель чтения — только другая, поэтому гонок нет; при равенстве указателей буфер пуст; режимы при заполненном буфере: блокирующий (ждать места), skip (отбросить всё новое сообщение), trim (записать сколько влезет, остальное отбросить)

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

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