Открыть сервис
Главная → Блог → Кольцевой буфер

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

Кольцевой буфер (также циклический буфер, кольцевая очередь, англ. ring buffer, circular buffer) — это структура данных фиксированного размера, работающая по принципу FIFO (first in, first out — «первым пришёл — первым ушёл»), в которой последний элемент логически соединяется с первым, образуя кольцо. Основное свойство кольцевого буфера — возможность непрерывной записи и чтения данных без физического перемещения элементов в памяти, что достигается за счёт переиспользования освободившихся ячеек. При заполнении буфера новые данные могут либо перезаписывать самые старые, либо вызывать блокировку записи до освобождения места.

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

Кольцевой буфер реализуется на основе линейного массива фиксированной длины (обычно степени двойки для оптимизации вычислений) и двух указателей (индексов): указателя записи (write pointer, head) и указателя чтения (read pointer, tail). Указатели перемещаются по массиву циклически: после достижения последнего индекса они переходят на нулевой.

Базовые операции

  1. Запись (push): данные помещаются в ячейку, на которую указывает head, после чего head увеличивается на 1 (с учётом цикличности). Если head догоняет tail, буфер считается полным. В зависимости от реализации возможны два поведения:
  1. Чтение (pop): данные извлекаются из ячейки, на которую указывает tail, после чего tail увеличивается на 1. Если tail равен head, буфер пуст.

Определение состояния

Для различения пустого и полного состояний часто применяют один из трёх методов:

История

Концепция кольцевого буфера восходит к ранним дням вычислительной техники, когда потребовалось организовать обмен данными между устройствами с разной скоростью работы (например, между процессором и периферией). Одним из первых известных применений стала реализация кольцевого буфера в операционной системе Multics (1960-е годы) для управления вводом-выводом. В 1970-х годах кольцевые буферы активно использовались в телетайпах и модемах для временного хранения символов. С развитием микропроцессоров и встраиваемых систем кольцевые буферы стали стандартным элементом драйверов устройств, обработчиков прерываний и буферов звуковых карт.

Реализации

Программные реализации

В языках программирования кольцевой буфер может быть реализован вручную или с использованием стандартных библиотек:

Аппаратные реализации

В цифровой электронике кольцевые буферы реализуются на регистрах сдвига или FIFO-памяти (First-In-First-Out memory). Например, в микроконтроллерах (STM32, AVR) кольцевые буферы используются в аппаратных UART-модулях для приёма и передачи данных без участия процессора. В ПЛИС (FPGA) кольцевые буферы строятся на блочной памяти (BRAM) с отдельными портами записи и чтения.

Применение

Обработка потоковых данных

Кольцевые буферы незаменимы при работе с непрерывными потоками данных, где требуется временное хранение фиксированного объёма последних элементов:

Взаимодействие процессов и потоков

Кольцевые буферы служат основой для реализации очередей сообщений в многопоточных и многопроцессных приложениях:

Встраиваемые системы

В микроконтроллерах кольцевые буферы применяются для:

Графические интерфейсы и игры

В игровых движках (Unity, Unreal Engine) кольцевые буферы используются для хранения последних кадров анимации, ввода с клавиатуры или мыши, а также для реализации эффекта «зацикленного» видео.

Преимущества и недостатки

Преимущества

Недостатки

Альтернативы

Пример реализации на C

Ниже приведён упрощённый пример кольцевого буфера на языке C с фиксированным размером и перезаписью старых данных:

```c

include <stdint.h>

include <stdbool.h>

define BUFFER_SIZE 16

typedef struct { uint8_t data[BUFFER_SIZE]; uint8_t head; // указатель записи uint8_t tail; // указатель чтения bool full; } ring_buffer_t;

void rb_init(ring_buffer_t *rb) { rb->head = 0; rb->tail = 0; rb->full = false; }

bool rb_is_empty(ring_buffer_t *rb) { return (!rb->full && (rb->head == rb->tail)); }

bool rb_is_full(ring_buffer_t *rb) { return rb->full; }

void rb_push(ring_buffer_t *rb, uint8_t data) { rb->data[rb->head] = data; rb->head = (rb->head + 1) % BUFFER_SIZE; if (rb->full) { rb->tail = (rb->tail + 1) % BUFFER_SIZE; // перезапись старых данных } rb->full = (rb->head == rb->tail); }

uint8_t rb_pop(ring_buffer_t *rb) { uint8_t data = rb->data[rb->tail]; rb->tail = (rb->tail + 1) % BUFFER_SIZE; rb->full = false; return data; } ```

Интересные факты

Источники

BFOmetr — база данных и аналитика по компаниям России.

На главную BFOmetr →

Похожие материалы