|
Применение кольцевого буфера (ring buffer) - обычный прием, когда нужно организовать поток данных между асинхронными по отношению друг к другу процессами - например, между получением данных по каналу связи и обработкой этих данных в программе. Кольцевой буфер является упрощенным аналогом очереди (queue), которая применяется в многозадачных операционных системах (Windows, Linux, FreeRTOS и многих других) для организации безопасного (thread-safe) обмена данных между потоками (синхронизации).
Кольцевой буфер может использоваться не только на прием, но и на передачу - например, если нужно быстро подготовленные где-то данные постепенно передавать с течением времени. Кольцевой буфер удобен прежде всего тем, что очень просто производить заполнение буфера, проверку наличия данных в буфере и выборку данных из буфера, при этом не нужно особенно беспокоиться о выходе данных за границу буфера, переполнении памяти и т. п. Кольцевой буфер позволяет корректно обмениваться данными между обработчиком прерывания и основной программой.
Кольцевой буфер является разновидностью буфера FIFO, First Input First Output (первый зашел - первый вышел). Принцип кольцевого буфера довольно прост - в памяти выделяется непрерывный блок размером обычно равным степени двойки (назовем его buffer), и два индекса (idxIN и idxOUT) - один индекс указывает на место для записи в буфер (idxIN), другой - на место чтения из буфера. Размер буфера, равный степени двойки, выбирается для того, чтобы удобно было манипулировать индексами, указывающими на данные буфера, с помощью инкремента/декремента и наложения маски (это будет понятно далее). Индекс - это обычное число, равное адресу ячейки буфера. Например, на ячейку buffer[0] указывает индекс, равный нулю. Количество бит индекса как раз равно степени двойки размера буфера. Максимально удобны буфера размером 256 байт - в этом случае в качестве индекса можно применить 1 байт, и маску при операциях с указателями уже накладывать не надо. Код получается в этом случае максимально быстрый и компактный. На рисунке показан принцип работы кольцевого буфера на примере буфера в 16 байт (желтым показаны еще не обработанные данные буфера):
Вот так, например, выделяется буфер:
#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);
}
Еще одну реализацию кольцевого буфера см. в библиотеке LUFA, файл Lib\LightweightRingBuff.h или LUFA\Drivers\Misc\RingBuffer.h.
UPD100920: процедуру получения количества данных в буфере idxDiff можно упростить следующим образом:
u8 idxDiff (u8 idxIN, u8 idxOUT)
{
return (idxIN - idxOUT)&BUF_MASK;
}
Кольцевой буфер не очень удобен для случаев, когда имеется несколько отправителей и один получатель, тогда при выборке информации из буфера необходимо правильно её сортировать. Для обратного случая - один отправитель и несколько получателей - кольцевой буфер подходит отлично, но нужно иметь для каждого получателя отдельный индекс idxOUT. Если же только один получатель и только один отправитель, то кольцевой буфер по быстродействию и простоте реализации практически идеальный вариант.
[Другие популярные разновидности буферов]
Флажковый буфер. Работает он как набор одинаковых ячеек в памяти. Каждая ячейка может иметь как простую структуру, так и сложную (в виде структуры или объекта). Каждая ячейка снабжена флажком, показывающим - занята эта ячейка или свободна. Флажковый буфер удобен в двух случаях. Во-первых, когда у передаваемой информации есть один отправитель и несколько получателей (и наоборот - когда получатель один, а отправителей несколько). Во-вторых, когда в нескольких ячейках может содержаться части какого-то большого сообщения, и эти части могут прийти в разное время, и не по порядку. Флаги занятости ячеек обычно для удобства держат в отдельном регистре. Если регистр 8-битный, то он может поддерживать максимум 8 ячеек, если 16-битный, то 16 ячеек, и так далее.
Алгоритм заполнения флажкового буфера и выборки из него следующий. Когда отправителю нужно поместить в буфер сообщение, то он ищет в регистре флагов первый попавшийся нулевой бит. Когда нулевой бит найден, то передатчик устанавливает его в единицу (помечая тем самым занятой соответствующую ячейку), вычисляет по номеру бита индекс ячейки, и затем помещает в ячейку информацию. Получатель действует так - просматривает флаги в поиске ненулевых бит. Все ячейки, которым соответствуют ненулевые биты, опрашиваются, и если там находится подлежащая выборке информация, то эта информация копируется из ячейки буфера, и соответствующий флажок сбрасывается, сигнализируя об освобождении ячейки.
Кэширование. Этот буфер работает как набор пронумерованных ячеек, составляющих образ какой-то другой (обычно более медленной) памяти, условно назовем эту память внешнее хранилище. В каждой ячейке хранятся как полезные данные, так и адрес, который соответствует месту размещения информации во внешнем хранилище. Обычный способ применения такого кэширования - доступ к данным на диске (карта SD, жесткий диск, флешка и т. п.), в этом случае каждая ячейка часто имеет размер 512 байт (сектор), и номер сектора является её адресом.
Стек. Если кольцевой буфер является буфером типа FIFO, то стек в этом отношении является его полной противоположностью, так как стек имеет тип FILO (First Input Last Output, т. е. первым пришел и последним вышел). Стек обычно реализован на уровне системы (аппаратно в микроконтроллере или процессоре), и поддерживается как со стороны инструкций процессора, так и со стороны системы программирования. Этот стек программист часто может использовать только неявно - определяя локальные переменные в функциях, передавая параметры и возвращая значения.
Программист сам может реализовать подпрограммы для доступа к своему собственному буферу со стековой структурой - если это требуется для обеспечения функционала программы. Однако искусственный стековый буфер применяется достаточно редко.
|
