Що таке кільцевий буфер?

Що таке кільцевий буфер?

Кільцевий буфер також відомий, як черга або циклічний буфер і є поширеною формою черги. Це популярний, легко реалізований стандарт, і, хоча він представлений у вигляді кола, в базовому коді він є лінійним. Кільцева черга існує як масив фіксованої довжини з двома індексами: один представляє початок черги, а інший - хвіст. Недоліком методу є його фіксований розмір. Для черг, де елементи повинні бути додані і вилучені в середині, а не тільки на початку і кінці буфера, реалізація у вигляді зв 'язаного списку є кращим підходом.

Теоретичні основи буфера

Користувачеві легше зробити вибір ефективної структури масивів після розуміння основоположної теорії. Циклічний буфер - структура даних, де масив обробляється і візуалізується у вигляді циклів, тобто індекси повертаються до 0 після досягнення довжини масиву. Це робиться за допомогою двох покажчиків на масив: «head» и «tail». Коли дані додаються до буфера, курсор заголовка переміщується вгору. Точно так само, коли вони видаляються, то хвіст теж переміщується вгору. Визначення голови, хвоста, напрямки їх руху, місця запису та читання залежать від реалізації схеми.


Кругові буфери надмірно ефективно використовуються для вирішення проблем споживача. Тобто один потік виконання відповідає за виробництво даних, а інший - за споживання. У вбудованих пристроях з дуже низьким і середнім рівнем виробник представлений у форматі ISR (інформація, отримана від датчиків), а споживач - у вигляді основного циклу подій.

Особливістю циклічних буферів є те, що вони реалізуються без необхідності блокувань в середовищі одного виробника і одного споживача. Це робить їх ідеальною інформаційною структурою для вбудованих програм. Наступна відмінність - не існує точного способу диференціювання заповненого сектора від порожнього. Це тому, що в обох випадках голова зливається з хвостом. Є багато способів і обхідних шляхів, щоб впоратися з цим, але більшість з них вносять велику сплутаність і ускладнюють читабельність.

Ще одне питання, яке виникає щодо циклічного буфера. Чи потрібно скидати нові дані або перезаписувати існуючі, коли він заповнений? Фахівці стверджують, що немає явної переваги одного над іншим, а його реалізація залежить від конкретної ситуації. Якщо останні мають більше значимості для програми, використовують метод перезапису. З іншого боку, якщо вони обробляються в режимі "першим прийшов - першим обслужений", то відкидають нові, коли кільцевий буфер заповнений.

Реалізація циклічної черги

Приступаючи до реалізації, визначають типи даних, а потім методи: core, push и pop. У процедурах "push" і "pop" обчислюють "наступні" точки зсуву для розташування, в якому відбуватиметься поточний запис і читання. Якщо наступне місце розташування вказує на хвіст, значить, буфер заповнений і дані більше не записуються. Точно так само, коли "head" дорівнює "tail", він порожній і з нього нічого не читається.

Стандартний параметр використання

Допоміжна процедура викликається процесом програми для вилучення даних з кільцевого буфера Java. Вона повинна бути включена в критичні розділи, якщо зчитують контейнер більше одного потоку. Хвіст переміщується до наступного зміщення до того, як інформація буде прочитана, оскільки кожен блок складає один байт і резервується аналогічну кількість в буфері, коли об 'єм повністю завантажений. Але в більш просунутих реалізаціях циклічного накопичувача поодинокі розділи необов 'язково повинні бути однакового розміру. У таких випадках намагаються зберегти навіть останній байт, додавши більше перевірок і кордонів.

У таких схемах, якщо хвіст пересувається перед читанням, інформація, яка повинна бути прочитана, потенційно може бути перезаписана знову висунутими даними. У загальному випадку рекомендується спочатку читати, а потім переміщати хвостовий покажчик. Спочатку визначають довжину буфера, а потім створюють екземпляр "circ_bbuf_t" і призначають індекс "maxlen". При цьому контейнер повинен бути глобальним або перебувати в стеку. Наприклад, якщо потрібен кільцевий буфер завдовжки 32 байти, виконують у програмі наступне (див. малюнок нижче).


Специфікація функціональних вимог

Тип даних "ring_t" буде типом даних, який містить покажчик на буфер, розмір його, індекс заголовка і хвоста, лічильник даних.

Функція ініціалізації "ring_init ()" ініціалізує буфер на основі отримання індексу на структуру контейнера, створеного зухвалою функцією, що має попередньо визначений розмір.

Функція додавання дзвінка "ring_add ()" додасть байт до наступного доступного пробілу в буфері.

Функція видалення кільця "ring_remove ()" видалить байт із найстарішого місця в контейнері.

Ring peek у функції "ring_peek ()" буде зчитувати число байтів "uint8_t 'count" з кільцевого буфера в новий, наданий як параметр, без видалення будь-яких значень, зчитаних з контейнера. Він поверне кількість фактично прочитаних байтів.

Функція очищення кільця "ring_clear ()" встановить "Tail" рівним "Head" і завантажить "0" у всі позиції буфера.

Створення буфера для C/C + +

Через обмеженість ресурсів вбудованих систем структури даних з циклічним буфером можна знайти в більшості проектів фіксованого розміру, які працюють так, як якщо б пам 'ять за своєю природою була безперервною і циклічною. Дані не потрібно переставляти, оскільки пам 'ять генерується і використовується, а коригуються покажчики голови/хвоста. Під час створення циклічної буферної бібліотеки потрібно, щоб користувачі працювали з бібліотечними API, а не змінювали структуру безпосередньо. Тому використовують інкапсуляцію кільцевого буфера на "Сі" ". Таким чином розробник збереже бібліотечну реалізацію, змінюючи її в міру необхідності, не вимагаючи, щоб кінцеві користувачі також оновлювали її.


Користувачі не можуть працювати з "circular_but_t" покажчиком, створюється тип дескриптора, який можна використовувати замість нього. Це позбавить від необхідності приводити покажчик у реалізації функції ".typedefcbuf_handle_t". Розробникам потрібно зібрати API для бібліотеки. Вони взаємодіють з бібліотекою кільцевого буфера C, використовуючи непрозорий тип дескриптора, який створюється під час ініціалізації. Зазвичай вибирають "uint8_t" як базовий тип даних. Але можна використовувати будь-який конкретний тип, виявляючи обережність, щоб правильно обробляти базовий буфер і кількість байтів. Користувачі взаємодіють з контейнером, виконуючи обов 'язкові процедури:

  1. Ініціалізувати контейнер і його розмір.
  2. Скинути круговий контейнер.
  3. Додавати дані в кільцевий буфер на "Сі".
  4. Отримувати наступне значення з контейнера.
  5. Затребувати інформацію про поточну кількість елементів і максимальну ємність.

І "повний", і "порожній" випадки виглядають однаково: "head" і "" tail "", покажчики рівні. Існує два підходи, що розрізняють повний і порожній:

  1. Повний стан tail + 1 = = head.
  2. Порожній стан head = = tail.

Реалізація бібліотечних функцій

Для створення кругового контейнера використовується його структура для керування станом. Щоб зберегти інкапсуляцію, структура визначається всередині бібліотечного ".c" файлу, а не в заголовку. При установці потрібно буде відстежувати:

  1. Базовий буфер даних.
  2. Максимальний розмір.
  3. Поточну позицію голови, що збільшується при додаванні.
  4. Поточний хвіст, що збільшується під час вилучення.
  5. Прапор, що вказує, заповнений контейнер чи ні.

Тепер, коли контейнер спроектовано, реалізують бібліотечні функції. Кожен з API вимагає ініціалізованого дескриптора буфера. Замість того щоб засмічувати код умовними твердженнями, застосовують твердження для забезпечення виконання вимог API в стилі.

Реалізація не буде поточно орієнтованою, якщо до базової бібліотеки циклічних сховищ не було додано блокування. Для ініціалізації контейнера у API є клієнти, які надають базовий розмір буфера, тому створюють його на стороні бібліотеки, наприклад, для простоти "malloc". Системи, які не можуть використовувати динамічну пам 'ять, повинні змінити "init" функцію, щоб використовувати інший метод, наприклад, такий як виділення зі статичного пулу контейнерів.


Інший підхід полягає в порушенні інкапсуляції, що дозволяє користувачам статично оголошувати структури контейнерів. У цьому випадку "circular_buf_init" необхідно оновити, щоб взяти покажчик або "init", створити структуру стека і повернути її. Однак, оскільки інкапсуляція порушена, користувачі зможуть змінювати її без бібліотечних процедур. Після того як створено контейнер, заповнюють значення і викликають "reset" ". Перш ніж повернутися з "init", система гарантує, що контейнер створений в порожньому стані.

Додавання і вилучення даних

Додавання та вилучення даних з буфера вимагає маніпуляцій з "head" - і "tail" -вказниками. При додаванні до контейнера вставляють нове значення в поточному "head" - місці і просувають його. Коли вилучають, отримують значення поточного "" tail "" -вказника і просувають "tail". Якщо потрібно просунути "" tail "" -вказник, а також "head", необхідно перевірити, чи викликає вставка значення "" full "". Коли буфер вже заповнений, просувають "tail" на крок попереду "head".

Після того як покажчик був просунутий, заповнюють "" full "" -флаг, перевіряючи рівність "" head = = tail "". Модульне використання оператора призведе до того, що "head" і "tail" скинуть значення в "" 0 "", коли буде досягнутий максимальний розмір. Це гарантує, що "head" і "tail" завжди будуть дійсними індексами базового контейнера даних: ""static void advance_pointer (cbuf_handle_t cbuf)"". Можна створити подібну допоміжну функцію, яка викликається при видаленні значення з буфера.

Інтерфейс шаблонного класу

Для того, щоб реалізація C++ підтримувала будь-які типи даних, виконують шаблон:

  1. Скидання буфера для очищення.
  2. Додавання і вилучення даних.
  3. Перевірка повного/порожнього стану.
  4. Перевірка поточної кількості елементів.
  5. Перевірка загальної ємності контейнера.
  6. Щоб не залишити жодних даних після знищення буфера, використовують інтелектуальні індекси C++, щоб гарантувати, що користувачі можуть керувати даними.

У цьому прикладі буфер C++ імітує більшу частину логіки реалізації C, але в результаті виходить набагато більш чистий і багаторазово використовуваний дизайн. Крім того, контейнер C++ використовує "" std::mutex "" для забезпечення поточно-орієнтованої реалізації. При створенні класу виділяють дані для основного буфера і встановлюють його розмір. Це усуває накладні витрати, необхідні з реалізацією C. На відміну від неї, конструктор C++ не викликає "reset", оскільки вказують початкові значення для змінних-членів, круговий контейнер запускається в правильному стані. Поведінка скидання повертає буфер у порожній стан. У реалізації циклічного контейнера C++ "size" і "capacity" повідомляє кількість елементів у черзі, а не розмір у байтах.


Драйвер UART STM32

Після запуску буфера, він повинен бути інтегрований в драйвер UART. Спочатку як глобальний елемент у файлі, тому необхідно оголосити:

  • "descriptor _ rbd" "і буферну пам 'ять" "_ rbmem: static rbd_t _rbd"";
  • ""static char _rbmem [8]"".

Оскільки це драйвер UART, де кожен символ повинен бути 8-розрядним, створення масиву символів допустимо. Якщо використовується 9- або 10-бітовий режим, кожен елемент повинен бути "" uint16 _ t "". Контейнер розраховується таким чином, щоб уникнути втрати даних.

Часто додатки черг містять статистичну інформацію, що дозволяє відстежувати максимальне використання. У функції ініціалізації "uart_init" буфер повинен бути ініціалізований шляхом виклику "ring_buffer_init" і передачі структури атрибутів з кожним членом, якому призначені обговорювані значення. Якщо він успішно ініціалізується, модуль UART виводиться зі скидання, переривання прийому дозволено в IFG2.

Друга функція, яка повинна бути змінена, - це "" uart _ getchar "". Видирання отриманого символу з периферійного пристрою UART замінюється читанням з черги. Якщо черга порожня, функція повинна повернути -1. Далі потрібно впровадити UART для отримання ISR. Відкривають файл заголовка "msp430g2553.h", прокручують вниз до секції векторів переривань, де знаходять вектор з іменем USCIAB0RX. Імена мають на увазі, що це воно використовується модулями USCI A0 і B0. Статус переривання прийому USCI A0 можна прочитати з IFG2. Якщо він встановлений, прапор повинен бути очищений, а дані в приймальному відсіку поміщені в буфер за допомогою "ring_buffer_put".

Сховище даних UART

Цей репозиторій дає інформацію про те, як зчитувати дані по UART з використанням DMA, коли кількість байтів для прийому заздалегідь невідома. У сімействі мікроконтролерів кільцевий буфер STM32 може працювати в різних режимах:


  1. Режим опитування (без DMA, без IRQ) - програма повинна опитувати біти стану, щоб перевірити, чи був прийнятий новий символ, і прочитати його досить швидко, щоб отримати всі байти. Дуже проста реалізація, але ніхто не використовує її в реальному житті. Мінуси - легко пропустити отримані символи в пакетах даних, працює тільки для низьких швидкостей передачі.
  2. Режим переривання (без DMA) - кільцевий буфер UART запускає переривання, і ЦПУ переходить до службової програми для обробки прийому даних. Найбільш поширений підхід у всіх додатках сьогодні, добре працює в діапазоні середніх швидкостей. Мінуси - процедура обробки переривання виконується для кожного отриманого символу, може зупиняти інші завдання у високопродуктивних мікроконтролерах з великою кількістю переривань і одночасно операційну систему при отриманні пакета даних.
  3. Режим DMA використовується для передачі даних з регістру USART RX у власну пам 'ять на апаратному рівні. На цьому етапі взаємодія з програмою не потрібна, за винятком необхідності обробки отриманих додатком даних. Може дуже легко працювати з операційними системами. Оптимізовано для високих швидкостей передачі даних > 1Mbps і малопотужних програм, у разі великих пакетів даних збільшення розміру буфера може поліпшити функціональність.

Реалізація в ARDUINO

Кільцевий буфер Arduino відноситься як до проектування плат, так і до середовища програмування, яке використовується для роботи. Ядром Arduino є мікроконтролер серії Atmel AVR. Саме AVR виконує більшу частину роботи, і в багатьох відношеннях плата Arduino навколо AVR представляє функціональність - легко підключаються контакти, USB-послідовний інтерфейс для програмування і зв 'язку.

Багато зі звичайних плат Arduino в даний час використовують кільцевий буфер c ATmega 328, більш старі плати використовували ATmega168 і ATmega8. Плати на кшталт Mega вибирають більш складні варіанти, такі як 1280 і аналогічні. Чим швидше Due і Zero, тим краще використовуйте ARM. Існує близько десятка різних плат Arduino з іменами. Вони можуть мати різну кількість флеш-пам 'яті, ОЗП і порти введення-виведення з кільцевим буфером AVR.

Змінну "roundBufferIndex" використовують для зберігання поточної позиції, а при додаванні до буфера відбудеться обмеження масиву.

Це результати виконання коду. Числа зберігаються в буфері, і, коли вони заповнені, вони починають перезаписуватися. Таким чином можна отримати останні N чисел.

У попередньому прикладі використано індекс для доступу до поточної позиції буфера, тому що він достатній для пояснення операції. Але загалом, нормальним є те, що використовується покажчик. Це модифікований код для використання індексу замість індексу. По суті, операція така ж, як і попередня, а отримані результати аналогічні.

Високопродуктивні операції CAS

Disruptor - це високопродуктивна бібліотека для передачі повідомлень між потоками, розроблена і відкрита кілька років тому компанією LMAX Exchange. Вони створили це програмне забезпечення для обробки величезного трафіку (понад 6 мільйонів TPS) у своїй роздрібній фінансовій торговій платформі. У 2010 році вони здивували всіх тим, наскільки швидкою може бути їхня система, виконавши всю бізнес-логіку в одному потоці. Хоча один потік був важливою концепцією в їх вирішенні, Disruptor працює в багатопоточному середовищі і заснований на кільцевому буфері - потік, в якому застарілі дані більше не потрібні, тому що надходять більш свіжі і більш актуальні.

У цьому випадку спрацює або повернення помилкового логічного значення, або блокування. Якщо жодне з цих рішень не задовольняє користувачів, можна реалізувати буфер зі змінюваним розміром, але тільки тоді, коли він заповнюється, а не тільки тоді, коли виробник досягає кінця масиву. Зміна розміру вимагає переміщення всіх елементів у знову виділений більший масив, якщо він використовується як базова структура даних, що, звичайно, є дорогою операцією. Є багато інших речей, які роблять Disruptor швидким, наприклад споживання повідомлень в пакетному режимі.

Кольцевий буфер "qtserialport" (послідовний порт) успадковується від QIODevice, може бути використаний для отримання різних послідовної інформації і включає в себе всі з доступних послідовних пристроїв. Послідовний порт завжди відкритий в монопольному доступі, це означає, що інші процеси або потоки не можуть отримати доступ до відкритого послідовного порту.

Кільцеві буфери дуже корисні в програмуванні на "" Сі "", наприклад, можна оцінити потік байтів, що надходять через UART.