Какво е пръстеновиден буфер?

Пръстеновидният буфер е известен също като опашка или буфер с контур и е често срещана форма на опашка. Това е популярен, лесно приложим стандарт и въпреки че е представен като кръг, в основния код той е линеен. Пръстеновидната опашка съществува като масив с фиксирана дължина с два указателя: единият представлява началото на опашката, а другият - нейната опашка. Недостатък на метода е фиксираният му размер. За опашки, в които елементите трябва да се добавят и премахват в средата, а не само в началото и края на буфера, предпочитаният подход е реализацията на свързан списък.

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

За потребителя е по-лесно да избере ефективна структура на масива, след като е разбрал основната теория. Цикличният буфер е структура от данни, при която масивът се обработва и визуализира на цикли, т.е. индексите се връщат на 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 ++

Поради ограничените ресурси на вградените системи в повечето проекти с фиксиран размер се срещат циклични буферни структури за данни, които работят така, сякаш паметта е по своята същност непрекъсната и циклична. Не е необходимо данните да бъдат пренареждани, тъй като паметта се генерира и използва, а указателите "глава/опашка" се коригират. По време на създаването на библиотека с кръгов буфер е необходимо потребителите да работят с приложните програмни интерфейси на библиотеката, а не да модифицират структурата директно. Затова използвайте капсулиране на пръстеновидния буфер при "C". По този начин разработчикът ще запази имплементацията на библиотеката, като я модифицира при необходимост, без да изисква от крайните потребители да я актуализират.

Потребителите не могат да работят с указател "circular_but_t", създаден е тип дескриптор, който може да се използва вместо него. Това би премахнало необходимостта от въвеждане на указател при прилагането на ".typedefcbuf_handle_t". Разработчиците трябва да създадат API за библиотеката. Те взаимодействат с библиотеката за пръстеновиден буфер на "C", като използват непрозрачен тип дескриптор, който се създава по време на инициализацията. Обикновено изберете "uint8_t" като основен тип данни. Но можете да използвате всеки конкретен тип, като се погрижите за правилната обработка на базовия буфер и броя байтове. Потребителите взаимодействат с контейнера, като изпълняват задължителните процедури:

1. Инициализиране на контейнера и неговия размер.
2. Нулиране на кръговия контейнер.
3. Добавяне на данни в пръстеновидния буфер при "C".
4. Извличане на следната стойност от.
5. Запитване за информация относно текущия брой елементи и максималния капацитет.

Както пълните, така и празните кутии изглеждат по един и същи начин: "глава" и "опашка", указатели, равни на. Съществуват два подхода за разграничаване на пълни и празни:

1. Пълно състояние tail + 1 == head.
2. Празна глава == опашка.

Реализиране на библиотечни функции

Създаване на кръгов контейнер и използване на неговата структура за управление на състоянието. За да се запази капсулирането, структурата е дефинирана в библиотека ".c" на файла, а не в заглавието. Инсталацията трябва да се контролира:

1. Буфер за базови данни.
2. Максимален размер.
3. Текуща позиция на главата, увеличава се при добавяне.
4. Увеличаване на текущата опашка при заличаване.
5. Флаг, указващ дали контейнерът е запълнен или не.

След като контейнерът е проектиран, имплементирайте функциите на библиотеката. Всеки от приложните програмни интерфейси изисква инициализиран дескриптор на буфер. Вместо да претрупвате кода с условни оператори, прилагайте оператори за налагане на изисквания за стила на API.

Реализацията няма да бъде ориентирана към нишки, освен ако към основната библиотека за циклично съхранение не са добавени ключалки. За инициализиране на контейнера API има клиенти, които предоставят базов размер на буфера, така че го създайте от страна на библиотеката, например за по-лесно "malloc". Системите, които не могат да използват динамична памет, трябва да променят функцията "init", за да използват друг метод, например заделяне от статичен пул от контейнери.

Друг подход е да се прекъсне капсулирането, като се позволи на потребителите статично да декларират контейнерни структури. В този случай "circular_buf_init" трябва да се актуализира, за да вземе указател или "init", да създаде структура на стека и да я върне. Въпреки това, тъй като капсулирането е нарушено, потребителите ще могат да го модифицират без библиотечни процедури. След като контейнерът е създаден, попълнете стойностите и извикайте "Нулиране на". Преди да се върне от "init", системата гарантира, че контейнерът е създаден в празно състояние.

Добавяне и премахване на данни

Добавянето и премахването на данни от буфера изисква манипулиране на указателите "head" и "tail". При добавяне към контейнера новата стойност се вмъква в текущия "глава"-място и да го популяризира. При изтриване стойността на текущия "опашка"-показалец и насърчаване на "опашката". Ако искате да напреднете "опашка"-както и на "главата", трябва да се провери дали вмъкването на стойността причинява "пълен". Когато буферът вече е пълен, преместете "опашката" с една стъпка напред пред "главата".

След като показалецът е бил преместен, "пълен"-флаг, като се проверява равенството на "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 ++ не извиква "Нулиране на", тъй като те посочват началните стойности на членните променливи, кръговият контейнер се стартира в правилното състояние. Поведението за нулиране връща буфера в празно състояние. В реализацията на цикличния контейнер на C ++ "size" и "capacity" отчитат броя на елементите в опашката, а не размера в байтове.

STM32 UART драйвер

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

• "дескриптор_rbd" и буферна памет "_rbmem: статичен 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 ring buffer се отнася както за дизайна на платката, така и за използваната среда за програмиране да работи. Сърцевината на Arduino е микроконтролер от серията AVR на Atmel. AVR е този, който върши по-голямата част от работата, и в много отношения платката Arduino, разположена около AVR, представя функционалност - лесни за свързване щифтове, USB сериен интерфейс за програмиране и комуникация.

Много от разпространените днес платки Arduino използват пръстеновиден буфер с ATmega 328, а по-старите платки използваха ATmega168 и ATmega8. Табла като Mega избират по-сложни варианти, като 1280 и подобни. Колкото по-бързи са Due и Zero, толкова по-добре е да използвате ARM. Съществуват около дузина различни платки Arduino с имена. Те могат да имат различно количество флаш памет, RAM и I/O портове с пръстеновиден буфер на AVR.

Използва се променливата "roundBufferIndex" да съхранявате на текущата позиция, а при добавяне в буфера ограничението на масива ще бъде.

Това са резултатите от изпълнението на кода. Числата се съхраняват в буфер и когато той се запълни, се презаписват. По този начин можете да получите последните N числа.

В предишния пример се използва индекс за достъп до текущата позиция на буфера, тъй като той е достатъчен, за да обясни операцията. Но по принцип е нормално да се използва указател. Това е модифициран код за използване на указател вместо индекс. Операцията по същество е същата като предишната и резултатите са подобни.

Високопроизводителни операции CAS

Disruptor е високопроизводителна библиотека за обмен на съобщения между нишки, разработена и открита преди няколко години от LMAX Exchange. Те създадоха този софтуер, за да се справят с огромния трафик (над 6 милиона TPS) в тяхната платформа за търговия на дребно. През 2010 г. те изненадаха всички с бързината на своята система, като изпълниха цялата бизнес логика в една нишка. Въпреки че една нишка е важна концепция в тяхното решение, Disruptor работи в многонишкова среда и се основава на кръгов буфер - нишка, в която остарелите данни вече не са необходими, защото постъпват по-свежи и по-актуални данни.

В този случай ще се върне невярна логическа стойност или ще се задейства блокиране. Ако нито едно от тези решения не удовлетворява потребителите, можете да приложите буфер с променлив размер, но само когато той е пълен, а не само когато производителят достигне края на масива. Промяната на размера ще изисква преместване на всички елементи в новоразпределен по-голям масив, ако се използва като основна структура на данните, което, разбира се, е скъпа операция. Има много други неща, които правят Disruptor бърз, като например консумиране на съобщения в пакетен режим.

Пръстеновиден буфер "qtserialport" (сериен порт) се наследява от QIODevice, може да се използва за получаване на различна серийна информация и включва всички налични серийни устройства. Серийният порт е винаги отворен с монополен достъп, което означава, че други процеси или нишки нямат достъп до отворения сериен порт.

Пръстеновидните буфери са много полезни при програмиране на "C", например, възможно е да се оцени потокът от байтове, постъпващ чрез UART.