Ce este un buffer inelar?

Un buffer inelar este cunoscut și sub numele de coadă sau buffer circular și este o formă comună de coadă. Este un standard popular, ușor de implementat și, deși este reprezentat ca un cerc, este liniar în codul de bază. O coadă inelară există sub forma unei matrice de lungime fixă cu doi pointeri: unul reprezentând începutul cozii și unul reprezentând coada. Dezavantajul acestei metode este dimensiunea sa fixă. Pentru cozile de așteptare în care elementele trebuie adăugate și eliminate la mijloc, nu doar la începutul și la sfârșitul tamponului, o implementare de tip listă legată este abordarea preferată.

Bazele teoretice ale unui tampon

Este mai ușor pentru utilizator să aleagă o structură eficientă de matrice odată ce teoria de bază este înțeleasă. Un buffer ciclic este o structură de date în care o matrice este procesată și redată în cicluri, adică indicii sunt readuși la 0 după ce se atinge lungimea matricei. Acest lucru se face folosind doi pointeri la matrice: "head" și "tail". Atunci când se adaugă date în memoria tampon, pointerul de antet este mutat în sus. În mod similar, atunci când sunt șterse, coada se deplasează și ea în sus. Definirea capului, a cozii, a direcției de deplasare a acestora, a locațiilor de scriere și de citire depinde de implementarea schemei.

Tampoanele circulare sunt suprautilizate pentru rezolvarea problemelor consumator. Adică, un fir de execuție este responsabil pentru producerea de date, iar celălalt pentru consum. În cazul dispozitivelor embedded de nivel foarte scăzut și mediu, producătorul este reprezentat de ISR (informații primite de la senzori), iar consumatorul de bucla principală de evenimente.

O caracteristică specială a tampoanelor ciclice este aceea că sunt implementate fără a fi nevoie de interblocare într-un mediu cu un singur furnizor și consumator. Acest lucru le face să fie structura informațională ideală pentru programele integrate. Următoarea diferență este că nu există o modalitate exactă de a diferenția un sector plin de unul gol. Asta pentru că, în ambele cazuri, capul se unește cu coada. Există mai multe modalități și soluții pentru a rezolva acest lucru, dar cele mai multe dintre ele introduc multă confuzie și îngreunează lectura.

O altă problemă care apare în legătură cu bufferul ciclic. Dacă se resetează datele noi sau se suprascriu datele existente atunci când acestea sunt pline? Specialiștii spun că nu există un avantaj clar al unuia față de celălalt, iar implementarea sa depinde de situația specifică. În cazul în care acestea din urmă sunt mai relevante pentru aplicație, se utilizează o metodă de suprascriere. Pe de altă parte, dacă acestea sunt procesate în modul primul venit-primul servit, ele le resping pe cele noi atunci când bufferul inelului este plin.

Implementarea unei cozi circulare

Când începeți implementarea, definiți tipurile de date și apoi metodele: core, push și pop. Procedurile "push" și "pop" calculează punctele de decalaj "următoare" pentru locația în care va avea loc scrierea și citirea curentă. Dacă următoarea locație indică coada, atunci bufferul este plin și nu se mai scriu date. În mod similar, atunci când "head" este egal cu "tail", este gol și nu se poate citi nimic din el.

Caz de utilizare standard

O procedură auxiliară este apelată de către procesul aplicației pentru a prelua date din memoria tampon Java ring buffer. Trebuie inclusă în secțiunile critice dacă mai multe fire de execuție citesc containerul. Coada este mutată la următorul decalaj înainte de citirea informației, deoarece fiecare bloc este de un octet și o cantitate similară este rezervată în buffer atunci când volumul este complet încărcat. Dar în implementările mai avansate de stocare ciclică, partițiile individuale nu trebuie să aibă neapărat aceeași dimensiune. În astfel de cazuri, se încearcă să se salveze chiar și ultimul octet prin adăugarea mai multor verificări și limite.

În astfel de sisteme, dacă coada este mutată înainte de citire, informațiile care urmează să fie citite ar putea fi suprascrise de noile date extinse. În general, se recomandă să citiți mai întâi și apoi să mutați pointerul de coadă. Definiți mai întâi lungimea bufferului, apoi creați o instanță de "circ_bbuf_t" și atribuiți-i pointerul "maxlen". Containerul trebuie să fie global sau pe stivă. Astfel, de exemplu, dacă este nevoie de un buffer inelar cu o lungime de 32 de octeți, în aplicație se execută următorul lucru (a se vedea. figura de mai jos).

Specificarea cerințelor funcționale

Tipul de date "ring_t" va fi un tip de date care conține un pointer la buffer, dimensiunea acestuia, indexul antetului și al cozii și un contor de date.

Funcția de inițializare "ring_init ()" inițializează buffer-ul pe baza obținerii unui pointer la structura container creată de funcția apelantă, care are o dimensiune predefinită.

Funcția de apelare "ring_add ()" va adăuga un octet la următorul spațiu disponibil din buffer.

Funcția "ring_remove ()" va elimina un octet din cea mai veche locație validă din container.

Ring peek din funcția "ring_peek ()" va citi numărul de octeți "uint8_t `count`" din bufferul ring în noul buffer furnizat ca parametru, fără a elimina valorile citite din container. Se va returna numărul de octeți citiți efectiv.

Funcția "ring_clear ()" va seta "Tail" la "Head" și va încărca "0" în toate pozițiile din buffer.

Crearea de tampoane în C/C ++

Din cauza resurselor limitate ale sistemelor integrate, structurile de date cu buffer ciclic pot fi găsite în majoritatea proiectelor de dimensiuni fixe, care funcționează ca și cum memoria este în mod inerent continuă și ciclică. Datele nu trebuie rearanjate, deoarece memoria este generată și utilizată, iar indicatorii cap/coadă sunt ajustați. În timpul creării unei biblioteci de tampoane circulare, este necesar ca utilizatorii să lucreze cu API-urile bibliotecii, mai degrabă decât să modifice direct structura. Acesta este motivul pentru care se utilizează încapsularea bufferului circular la "C". În acest fel, dezvoltatorul va păstra implementarea bibliotecii, modificând-o după cum este necesar, fără a cere utilizatorilor finali să o actualizeze și ei.

Utilizatorii nu pot lucra cu un pointer "circular_but_t", se creează un tip de descriptor care poate fi folosit în schimb. Acest lucru elimină necesitatea unui pointer în implementarea funcției ".typedefcbuf_handle_t". Dezvoltatorii trebuie să construiască un API pentru bibliotecă. Acestea interacționează cu biblioteca de buffer inelar "C" folosind un tip de descriptor opac care este creat în timpul inițializării. De obicei, alegeți "uint8_t" ca tip de date de bază. Dar puteți folosi orice tip specific, având grijă să gestionați corect bufferul de bază și numărul de octeți. Utilizatorii interacționează cu containerul prin executarea unor proceduri obligatorii:

1. Se inițializează containerul și dimensiunea.
2. Resetarea containerului circular.
3. Adăugați date în bufferul circular pe "C".
4. Preluarea următoarei valori din container.
5. Obținerea de informații despre numărul curent de elemente și capacitatea maximă.

Atât cazurile "pline", cât și cele "goale" arată la fel: "cap" и "coadă", sunt egale cu. Există două abordări, făcând distincția între plin și gol:

1. Stare completă coadă + 1 == cap.
2. Cap gol == coadă.

Implementarea funcțiilor de bibliotecă

Pentru a crea un container circular, utilizați structura acestuia pentru a controla starea. Pentru a păstra încapsularea, structura este definită în interiorul unei biblioteci ".c" din fișier, nu în antet. În timpul instalării, va fi necesar să se țină cont de:

1. Buffer de date de bază.
2. Dimensiunea maximă.
3. Poziția curentă a capului, incrementată atunci când se adaugă.
4. Coada curentă, care crește pe măsură ce este ștearsă.
5. Semnalizator care indică dacă rezervorul este plin sau nu.

Acum că containerul este proiectat, implementați funcțiile de bibliotecă. Fiecare dintre API-uri necesită un descriptor de tampon inițializat. În loc să aglomerați codul cu instrucțiuni condiționale, aplicați instrucțiuni pentru a impune cerințele de stil API.

Implementarea nu va fi orientată pe fire de execuție decât dacă au fost adăugate încuietori la biblioteca de stocare ciclică subiacentă. Pentru inițializarea containerelor, API-ul are clienți care oferă o dimensiune de bază a bufferului, deci creați-o pe partea bibliotecii, de exemplu, pentru a facilita "malloc". Sistemele care nu pot utiliza memoria dinamică trebuie să modifice funcția "init" pentru a utiliza o altă metodă, cum ar fi alocarea dintr-un grup de containere statice.

O altă abordare este de a rupe încapsularea, permițând utilizatorilor să declare static structuri container. În acest caz, "circular_buf_init" trebuie actualizat pentru a lua un pointer sau "init", a crea o structură de stivă și a o returna. Cu toate acestea, din moment ce încapsularea este ruptă, utilizatorii vor putea să o modifice fără proceduri de bibliotecă. Odată ce containerul este creat, completați valorile și apelați "resetare". Înainte de a reveni de la "init", sistemul se asigură că recipientul este creat într-o stare goală.

Adăugarea și ștergerea datelor

Adăugarea și eliminarea datelor din buffer necesită manipularea indicatorilor "head" și "tail". Când se adaugă la un container, se inserează o nouă valoare la valoarea curentă "cap"-locul și avansați-l. Atunci când este ștearsă, se păstrează valoarea din valoarea curentă "coadă"-și avansează "coada". În cazul în care este necesar să se promoveze "coadă"-precum și "head", trebuie verificat dacă inserarea lui "complet". Atunci când memoria tampon este deja plină, avansați "coada" cu un pas înaintea "capului".

După ce pointerul a fost promovat, se va trece la "complet"-prin verificarea egalității "cap == coadă". Utilizarea modulară a operatorului va face ca "head" și "tail" să reseteze valorile la "0", atunci când este atinsă dimensiunea maximă. Acest lucru garantează că "head" și "tail" sunt întotdeauna indici validați ai containerului de date de bază: "static void advance_pointer (cbuf_handle_t cbuf)". Se poate crea o funcție auxiliară similară care este apelată atunci când o valoare este eliminată din buffer.

Interfața clasei șablon

Pentru ca implementarea C ++ să suporte orice tip de date, se realizează un șablon:

1. Resetarea tamponului pentru a curăța.
2. Adăugarea și ștergerea datelor.
3. Verificarea stării pline/vide.
4. Verificați numărul curent de articole.
5. Verificați capacitatea totală a containerului.
6. Pentru a se asigura că nu rămân date în urmă atunci când bufferul este distrus, se folosesc pointeri inteligenți C+ pentru a se asigura că utilizatorii pot manipula datele.

În acest exemplu, bufferul C ++ imită o mare parte din logica unei implementări C, dar rezultatul este un design mult mai curat și reutilizabil. În plus, containerul C ++ utilizează "std::mutex" pentru a furniza o implementare orientată pe fire de execuție a. Când se creează o clasă, alocați date pentru memoria tampon principală și stabiliți dimensiunea acesteia. Acest lucru elimină costurile suplimentare necesare cu o implementare C. Prin contrast, constructorul C ++ nu apelează "resetare", deoarece acestea specifică valorile inițiale pentru variabilele membre, containerul circular este pornit în starea corectă. Comportamentul de resetare readuce memoria tampon la o stare goală. În implementarea în C ++ a containerului ciclic, "size" și "capacity" raportează numărul de elemente din coadă, nu dimensiunea în bytes.

Driver UART STM32

Odată ce bufferul este în funcțiune, trebuie integrat în driverul UART. În primul rând ca element global în fișier, deci trebuie declarat:

• "descriptor_rbd" și memoria tampon "_rbmem: static rbd_t _rbd";
• "static char _rbmem [8]".

Deoarece acesta este un driver UART în care fiecare caracter trebuie să fie pe 8 biți, este acceptabilă crearea unei matrice de caractere. În cazul în care se utilizează modul pe 9 sau 10 biți, fiecare element trebuie să fie "uint16_t". Containerul este calculat în așa fel încât să se evite pierderea de date.

Adesea, modulele de coadă conțin informații statistice pentru a ține evidența utilizării maxime. În funcția de inițializare "uart_init", tamponul trebuie inițializat prin apelarea "ring_buffer_init" și trecerea unei structuri de atribute cu fiecare membru atribuit la valorile discutate. Dacă se inițializează cu succes, modulul UART este resetat și este permisă o recepție întreruptă în IFG2.

A doua funcție care trebuie modificată este "uart_getchar". Caracterul primit de la perifericul UART este înlocuit de o citire din coada de așteptare. În cazul în care coada este goală, funcția trebuie să returneze -1. În continuare trebuie să implementăm UART pentru a obține ISR-ul. Deschideți fișierul antet "msp430g2553.h", derulați în jos până la secțiunea vectorului de întrerupere, unde se găsește un vector numit USCIAB0RX. Denumirea implică faptul că acesta este cel utilizat de modulele USCI A0 și B0. Starea de întrerupere a USCI A0 poate fi citită din IFG2. Dacă este activat, stegulețul trebuie să fie eliminat, iar datele din compartimentul de recepție trebuie introduse în memoria tampon cu ajutorul "ring_buffer_put".

Depozit de date UART

Acest repertoriu oferă informații despre cum se citesc date prin UART folosind DMA atunci când numărul de octeți de primit nu este cunoscut în avans. În familia de microcontrolere STM32, bufferul inelar poate funcționa în diferite moduri:

1. Modul de interogare (fără DMA, fără IRQ) - aplicația trebuie să interogheze biții de stare pentru a verifica dacă a fost primit un nou caracter și să citească suficient de repede pentru a primi toți octeții. Implementare foarte simplă, dar nimeni nu o folosește în viața reală. Dezavantaje - este ușor de ratat caracterele primite în pachetele de date, funcționează numai pentru viteze de transmisie mici.
2. Modul de întrerupere (fără DMA) - Un buffer de inel UART declanșează o întrerupere și CPU intră într-un program de serviciu pentru a procesa recepția de date. Cele mai frecvente abordare în toate aplicațiile actuale și funcționează bine în gama de viteze medii. Minusuri - procedura de tratare a întreruperilor este executată pentru fiecare caracter primit, poate opri alte sarcini în microcontrolerele de înaltă performanță cu multe întreruperi și simultan sistemul de operare atunci când se primește un pachet de date.
3. Modul DMA este utilizat pentru a transfera date din registrul USART RX în memoria utilizatorului la nivel hardware. În această etapă nu este necesară nicio interacțiune cu aplicația, cu excepția necesității de a procesa datele primite de către aplicație. Poate lucra foarte ușor cu sisteme de operare. optimizat pentru viteze mari de date > 1Mbps și aplicații cu consum redus de energie, în cazul pachetelor de date mari, creșterea dimensiunii buffer-ului poate îmbunătăți funcționalitatea.

Implementarea în ARDUINO

Tamponul inelar Arduino se referă atât la designul plăcii, cât și la mediul de programare care este utilizat pentru performanță. Nucleul lui Arduino este un microcontroler Atmel AVR din seria AVR. AVR-ul este cel care face cea mai mare parte a muncii și, în multe feluri, placa Arduino din jurul AVR-ului prezintă funcționalitatea - pini ușor de conectat, interfață serială USB pentru programare și comunicare.

Multe dintre plăcile comune Arduino folosesc acum un buffer inelar c ATmega 328, plăcile mai vechi au folosit ATmega168 și ATmega8. Plăcile precum Mega optează pentru opțiunile mai complexe, cum ar fi 1280 și altele similare. Cu cât sunt mai rapide Due și Zero, cu atât mai bine să folosiți ARM. Există aproximativ o duzină de plăci Arduino diferite cu nume. Acestea pot avea diferite cantități de memorie flash, RAM și porturi I/O cu un buffer de inel AVR.

Se utilizează variabila "roundBufferIndex" pentru a stoca poziția curentă, iar atunci când sunt adăugate în memoria tampon, constrângerea de matrice.

Acestea sunt rezultatele execuției codului. Numerele sunt stocate în memoria tampon, iar când sunt pline, încep să fie suprascrise. În acest fel puteți obține ultimele N numere.

Exemplul anterior a folosit un index pentru a accesa poziția curentă a bufferului, deoarece este suficient pentru a explica operația. Dar, în general, este normal ca un pointer să fie utilizat. Acesta este codul modificat pentru a utiliza un pointer în loc de un index. Operațiunea este, în esență, aceeași cu cea anterioară, iar rezultatele obținute sunt similare.

Operațiuni CAS de înaltă performanță

Disruptor este o bibliotecă de mesagerie inter-flux de înaltă performanță dezvoltată și descoperită acum câțiva ani de LMAX Exchange. Ei au creat acest software pentru a gestiona traficul uriaș (peste 6 milioane de TPS) în platforma lor de tranzacționare financiară cu amănuntul. În 2010 au surprins pe toată lumea cu cât de rapid putea fi sistemul lor prin executarea întregii logici de afaceri într-un singur fir de execuție. Deși un singur fir a fost un concept important în soluția lor, Disruptor funcționează într-un mediu cu mai multe fire și se bazează pe un buffer circular - un fir în care datele învechite nu mai sunt necesare deoarece sosesc date mai proaspete și mai actuale.

În acest caz, se va declanșa fie o revenire logică falsă, fie un blocaj. Dacă niciuna dintre aceste soluții nu satisface utilizatorii, se poate implementa un buffer de dimensiune variabilă, dar numai atunci când bufferul este plin, nu numai atunci când producătorul ajunge la capătul matricei. Redimensionarea ar necesita mutarea tuturor elementelor într-o matrice mai mare nou alocată, dacă este folosită ca structură de date de bază, ceea ce, desigur, este o operațiune costisitoare. Există multe Alte lucruri care îl fac pe Disruptor rapid, cum ar fi consumul de mesaje în modul batch.

Tampon inelar "qtserialport" (port serial) este moștenit de la QIODevice, poate fi utilizat pentru a primi diverse informații seriale și include toate dispozitivele seriale disponibile. Portul serial este întotdeauna deschis cu acces monopolist, ceea ce înseamnă că alte procese sau fire de execuție nu pot accesa portul serial deschis.

Tampoanele inelare sunt foarte utile în programarea pe "C", De exemplu, puteți estima fluxul de octeți care intră prin intermediul unei UART.