Главная arrow Программирование arrow AVR arrow Работа с кольцевым буфером Sunday, July 23 2017  
ГлавнаяКонтактыАдминистрированиеПрограммированиеСсылки
UK-flag-ico.png English Version
GERMAN-flag-ico.png Die deutsche Version
map.gif карта сайта
нашли опечатку?

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

Поделиться:

Работа с кольцевым буфером Версия для печати
Написал 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 )
 

Комментарии  

  1. #6 dccharacter
    2012-09-2015:26:45 u8 idxDiff (u8 idxIN, u8 idxOUT)
    {
    if (idxIN >= idxOUT)
    return (idxIN - idxOUT);
    else
    return ((BUF_SIZE - idxOUT) + idxIN);
    }

    можно упростить до

    u8 idxDiff (u8 idxIN, u8 idxOUT)
    {
    return (idxIN - idxOUT)&BUF_MASK;
    }

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

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

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

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

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

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

    u8 idxIN, idxOUT;
    char buffer [256];

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

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

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

:D:lol::-);-)8):-|:-*:oops::sad::cry::o:-?:-x:eek::zzz:P:roll::sigh:

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

< Пред.   След. >

Top of Page
 
microsin © 2017