Работа с кольцевым буфером
Написал microsin   
12.02.2010

Применение кольцевого буфера (ring buffer) - обычный прием, когда нужно организовать поток данных между асинхронными по отношению друг к другу процессами - например, между получением данных по каналу связи и обработкой этих данных в программе. Кольцевой буфер является упрощенным аналогом очереди (queue), которая применяется в многозадачных операционных системах (Windows, Linux, FreeRTOS и многих других) для организации безопасного (thread-safe) обмена данных между потоками (синхронизации).

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

Кольцевой буфер является разновидностью буфера FIFO, First Input First Output (первый зашел - первый вышел). Принцип кольцевого буфера довольно прост - в памяти выделяется непрерывный блок размером обычно равным степени двойки (назовем его buffer), и два индекса (idxIN и idxOUT) - один индекс указывает на место для записи в буфер (idxIN), другой - на место чтения из буфера. Размер буфера, равный степени двойки, выбирается для того, чтобы удобно было манипулировать индексами, указывающими на данные буфера, с помощью инкремента/декремента и наложения маски (это будет понятно далее). Индекс - это обычное число, равное адресу ячейки буфера. Например, на ячейку buffer[0] указывает индекс, равный нулю. Количество бит индекса как раз равно степени двойки размера буфера. Максимально удобны буфера размером 256 байт - в этом случае в качестве индекса можно применить 1 байт, и маску при операциях с указателями уже накладывать не надо. Код получается в этом случае максимально быстрый и компактный. На рисунке показан принцип работы кольцевого буфера на примере буфера в 16 байт (желтым показаны еще не обработанные данные буфера):

ringbuf.jpg

Вот так, например, выделяется буфер:
#define BUF_SIZE    16  //размер буфера обязательно равен степени двойки!
#define BUF_MASK    (BUF_SIZE-1)

u8 idxIN, idxOUT;
char buffer [BUF_SIZE];

При помещения значения value в буфер используется индекс idxIN. Это делается так:
buffer[idxIN++] = value;
idxIN &= BUF_MASK;

Значение константы BUF_MASK равно размеру буфера минус 1 (при условии, что размер буфера равен степени двойки). При таком принципе работы с индексом происходит автоматический переход на начало буфера, как только мы достигли его конца.

Операция выборки из буфера происходит похожим образом, только используется индекс idxOUT:
value = buffer[idxOUT++];
idxOUT &= BUF_MASK;

Теперь становится понятным, почему при размере буфера 256 байт и байтовом индексе не нужна операция наложения маски - переход в ноль индекса при достижении конца буфера происходит автоматически.

Проверка на наличие данных в буфере происходит очень просто - если idxIN не равен idxOUT, то в буфере есть данные, в противном случае данных в буфере нет. Индекс idxOUT как-бы постоянно догоняет индекс idxIN при работе с данными буфера. Если догнал - значит, считывать из буфера больше нечего.
if (idxIN != idxOUT)
{
   //данные есть, обрабатываем их
   ...
}

Сбросить данные буфера (т. е. удалить их оттуда) тоже очень просто - для этого в idxOUT записывают значение idxIN:
idxOUT = idxIN;

Иногда бывает необходимо знать, что не только данные в буфере есть, а еще нужно знать сколько именно байт данных в буфере. Для этого используется довольно простая процедура:
u8 idxDiff (u8 idxIN, u8 idxOUT)
{
    if (idxIN >= idxOUT)
        return (idxIN - idxOUT);
    else
        return ((BUF_SIZE - idxOUT) + idxIN);
}

Последнее обновление ( 18.10.2011 )