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

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

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

Користувачеві легше зробити вибір ефективної структури масивів після розуміння основної теорії. Циклічний буфер-структура даних, де масив обробляється і візуалізується у вигляді циклів, тобто індекси повертаються до 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.