Программирование AVR Работа с кольцевым буфером Thu, June 22 2017  

Поделиться

нашли опечатку?

Пожалуйста, сообщите об этом - просто выделите ошибочное слово или фразу и нажмите Shift Enter.


Работа с кольцевым буфером Печать
Добавил(а) microsin   

Применение кольцевого буфера (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);
}

Еще одну реализацию кольцевого буфера см. в библиотеке 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, т. е. первым пришел и последним вышел). Стек обычно реализован на уровне системы (аппаратно в микроконтроллере или процессоре), и поддерживается как со стороны инструкций процессора, так и со стороны системы программирования. Этот стек программист часто может использовать только неявно - определяя локальные переменные в функциях, передавая параметры и возвращая значения.

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

 

Комментарии  

 
0 #8 ivanr 17.05.2015 20:31
Ситуация, когда буфер кольцевой буфер заполнен полностью никак не отличается от ситуации, когда он пуст, следовательно не будет работать, если читать медленнее, чем писать, собственно об этом Вы уже написали. Вопрос в том, как сделать, чтобы ситуации различались? Придется вводить флаги и при каждой записи и чтении сперва проверять флаги, потом выставлять?

microsin: достоинство кольцевого буфера именно в его простоте и скорости. Единственное условие, которое нужно выполнить, чтобы такой буфер работал - не допускать его переполнения, т. е. делать выборку значений быстрее, чем значения записываются в буфер. Если нужно что-то кроме этого функционала, то это уже не будет кольцевой буфер, а что-то другое (FIFO, стек, очередь и т. д.), что не имеет смысла здесь обсуждать.
Цитировать
 
 
0 #7 Игорь 31.05.2014 19:56
А если 256 ячеек мало, и нужно индексы использовать 2-х байтовые, то тогда как будет выглядеть организация такого буфера?

microsin: абсолютно так же, на принцип работы кольцевого буфера это никак не повлияет. Помните только, что выгоднее всего использовать для размера буфера число в степени N двойки (размер буфера = 2^N). Для организации закольцовывания индекса при инкременте достаточно накладывать на индекс маску, равную (2^N)-1.
Цитировать
 
 
-2 #6 a791 21.03.2012 17:04
Цитирую 10199:
microsin: вся прелесть кольцевого буфера в том, что про синхронизацию можно вообще забыть

Совсем забыть? И для индексов volatile не нужно?
Цитировать
 
 
0 #5 kek 02.09.2011 15:58
Не совсем верно. Кольцевой буфер используется в классической задаче "производителя"-"потребителя" (см. например здесь: http://www.cs.mtu.edu/~shene/NSF-3/e-Book/MONITOR/ProducerConsumer-1/MON-example-buffer-1.html). При переполнении буфера производитель должен быть заблокирован, разблокироватьс я он может по сигналу от потребителя, когда последний извлечет данные из буфера.
Недостоверными данные буфера при переполнении и последующем прекращении заполнения станут только в одном случае: если буфер обязан содержать чисто реалтаймовые данные: скажем, измерения за BUF_SIZE моментов времени вплоть до текущего момента. Но тогда задача еще проще: можно иметь один индекс для записи и считывать весь буфер целиком при необходимости обработки. Индекс записи в таком случае покажет границу между самыми новыми и самыми старыми данными.

microsin: при обмене с квитированием, т. е. с блокировкой/разблокировкой передатчика данных (с управлением потоком данных от потребителя) кольцевой буфер может быть не нужен, так как всегда гарантируется, что приемник готов принять данные в нужное время. Повторяю еще раз, на всякий случай - в этой статье подобная ситуация с блокировкой/разблокировкой передатчика данных - НЕ РАССМАТРИВАЕТСЯ .
Цитировать
 
 
0 #4 kek 02.09.2011 15:10
Если буфер заполнится до конца, то индексы idxIN и idxOUT сравняются. И тогда функция idxDiff() вернет не BUF_SIZE, а 0. Не говоря уже о том, что u8 idxDiff (u8 idxIN, u8 idxOUT) в принципе не может вернуть BUF_SIZE, равный 256...
То же самое относится и к фразе "Если догнал - значит, считывать из буфера больше нечего". На самом деле, или нечего, или буфер заполнен до конца.
Если принять за постулат, что буфер опустошается всегда быстрее, чем заполняется, то это не важно. Но что если что-то пойдет не так, как мы предполагаем? Скажем, потеряна связь с потребителем данных, символы не извлекаются из кольца, а производитель продолжает писать данные: средств для идентификации переполнения ведь нет в принципе! За границу мы, конечно, не выйдем, но вот последовательно сть чтения накопленных данных будет искажена.

microsin: Вы во всем правы, и об этом в статье явно не пишется только потому, что буфер КОЛЬЦЕВОЙ, и если запись в буфер будет идти быстрее чтения, то буфер переполнится, и данные в нем будут недостоверны. В этом случае не только нельзя применить кольцевой буфер, но и невозможно синхронизироват ь процессы по передаваемым данным, если не отбрасывать пакеты. Описание такого поведения программы выходит за рамки статьи, статья только про принцип работы с КОЛЬЦЕВЫМ БУФЕРОМ. Повторяю снова - говорить о кольцевом буфере, когда скорость входящего потока данных превышает скорость исходящего - совершенно бессмысленно.
Цитировать
 
 
-2 #3 10199 22.02.2011 16:50
Ранее придумал нечто похожее на Ваш пример, только у меня было 2 строки char и два указателя. Один указывал на строку приема, второй - на строку, которую надо обработать. После некоторой возни с синхронизацией этих потоков все работало достаточно шустро :)

microsin: вся прелесть кольцевого буфера в том, что про синхронизацию можно вообще забыть, как про страшный сон. При работе с кольцевым буфером нужно только соблюсти два условия - средняя скорость записи в буфер должна быть меньше средней скорости чтения из него, и размер буфера должен быть достаточно большим для того, чтобы не терялись записываемые за один раз (до операции чтения) данные.
Цитировать
 
 
0 #2 AlexQt 03.11.2010 16:27
Как лучше контролировать корректность записываемых данных, то есть случай, когда записывается больше данных, чем осталось места в буфере.

microsin: никак, потому что кольцевой буфер не предназначен для такого случая. Использование кольцевого буфера автоматически подразумевает условие, что СРЕДНЯЯ скорость записи в кольцевой буфер ВСЕГДА МЕНЬШЕ СРЕДНЕЙ скорости чтения из кольцевого буфера.
Цитировать
 
 
0 #1 Andrey 23.10.2010 02:29
Можно пример кольцевого буфера размером 256 байт без применения маски (индекс в один байт)?

microsin: нет ничего проще, просто отсутствует наложение маски:

u8 idxIN, idxOUT;
char buffer [256];

//запись в буфер
buffer[idxIN++] = value;

//чтение из буфера
value = buffer[idxOUT++ ];
Цитировать
 

Добавить комментарий


Защитный код
Обновить

Top of Page