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

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

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

Користувачеві легше зробити вибір ефективної структури масивів після розуміння фундаментальної теорії. Циклічний буфер - структура даних, де масив обробляється і візуалізується у вигляді циклів, тобто індекси повертаються до 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» в якості базового типу даних. Але можна використовувати будь-який конкретний тип, виявляючи обережність, щоб правильно обробляти базовий буфер і кількість байтів. Користувачі взаємодіють з контейнером, виконуючи обов'язкові процедури: Ініціалізувати контейнер і його розмір. Скинути кругової контейнер. Додавати дані в кільцевий буфер на "Сі". Отримувати наступне значення з контейнера. Зажадати інформацію про поточному кількості елементів і максимальної ємності. І «повний», і «порожній» випадки виглядають однаково: "head" і "tail", покажчики рівні. Існує два підходи, различающие повний і порожній: Повне стан tail + 1 == head. Пусте стан head == tail.

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

Для створення кругового контейнера використовують його структуру для управління станом. Щоб зберегти інкапсуляцію, структура визначається в межах бібліотечного «.c файлу, а не в заголовку. При установці потрібно буде відстежувати:
Базовий буфер даних. Максимальний розмір. Поточну позицію голови, збільшується при додаванні. Поточний хвіст, збільшується при видаленні. Прапор, який вказує, заповнений контейнер чи ні. Тепер, коли контейнер спроектований, реалізують бібліотечні функції. Кожен з 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 ++ підтримувала будь-які типи даних, виконують шаблон: Скидання буфера для очищення. Додавання та видалення даних. Перевірка повного/порожнього стану. Перевірка поточного кількості елементів. Перевірка загальної ємності контейнера. Щоб не залишити ніяких даних після знищення буфера, використовують інтелектуальні покажчики 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 може працювати в різних режимах: Режим опитування (без DMA, без IRQ)- додаток повинен опитувати біти стану, щоб перевірити, чи був прийнятий новий символ, і прочитати його досить швидко, щоб отримати всі байти. Дуже проста реалізація, але ніхто не використовує її в реальному житті. Мінуси - легко пропустити одержані символи в пакетах даних, працює тільки для низьких швидкостей передачі. Режим переривання (без DMA) - кільцевої буфер UART запускає переривання, і ЦПУ переходить до службової програмі для обробки прийому даних. Найбільш поширений підхід у всіх додатках сьогодні, добре працює в діапазоні середніх швидкостей. Мінуси - процедура обробки переривання виконується для кожного отриманого символу, може зупиняти інші завдання у високопродуктивних мікроконтролерах з великою кількістю переривань і одночасно операційну систему при отриманні пакету даних. Режим 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.