Kaj je obročni predpomnilnik?

Obročni buffer je znan tudi kot čakalna vrsta ali ciklični buffer in je pogosta oblika čakalne vrste. To je priljubljen standard, ki se zlahka izvaja, in čeprav je predstavljen kot krog, je v osnovni kodi linearen. Obročna čakalna vrsta obstaja kot polje fiksne dolžine z dvema kazalcema: eden predstavlja začetek čakalne vrste, drugi pa njen rep. Pomanjkljivost te metode je njena fiksna velikost. Za čakalne vrste, v katerih je treba elemente dodajati in odstranjevati na sredini, ne le na začetku in koncu bufferja, je najprimernejši pristop izvedba povezanega seznama.

Teoretične osnove blažilnika

Uporabnik lažje izbere učinkovito strukturo polja, če razume osnovno teorijo. Ciklični buffer je podatkovna struktura, v kateri se polje obdeluje in prikazuje v ciklih, tj. ko je dosežena dolžina polja, se indeksi vrnejo na 0. To storimo z uporabo dveh kazalnikov na polje: "head" in "tail". Ko se v predpomnilnik dodajo podatki, se kazalec glave premakne navzgor. Podobno se ob izbrisu premakne navzgor tudi rep. Opredelitev glave, repa, smeri njunega gibanja, lokacij za pisanje in branje je odvisna od izvajanja sheme.

Krožni predpomnilniki se pretirano uporabljajo za rešitve problemov potrošnik. To pomeni, da je ena nit izvajanja odgovorna za ustvarjanje podatkov, druga nit pa za njihovo porabo. V vgrajenih enotah zelo nizke in srednje ravni je proizvajalec predstavljen v formatu ISR (informacije, prejete od senzorjev), porabnik pa v glavni dogodkovni zanki.

Posebnost cikličnih predpomnilnikov je, da se izvajajo brez potrebe po zaklepanju v enem okolju proizvajalca in porabnika. Zato so idealna informacijska struktura za vgrajene programe. Naslednja razlika je, da ni natančnega načina za razlikovanje med zapolnjenim in praznim sektorjem. V obeh primerih se namreč glava združi z repom. Za to obstaja veliko načinov in obvozov, vendar večina od njih vnaša veliko zmede in otežuje berljivost.

V zvezi s cikličnim blažilnikom se pojavlja še eno vprašanje. ali je treba nove podatke ponastaviti ali pa je treba obstoječe podatke prepisati, ko so polni? Strokovnjaki pravijo, da ni jasnih prednosti ene pred drugo, izvajanje pa je odvisno od konkretnih razmer. Če so slednji za aplikacijo pomembnejši, se uporabi metoda prepisovanja. Po drugi strani pa, če se obdelujejo v načinu "kdor prej pride, prej melje", zavržejo nove, ko je obročni predpomnilnik poln.

Izvedba krožne čakalne vrste

Ob začetku izvajanja določite podatkovne tipe in nato metode: core, push in pop. Postopka "push" in "pop" izračunata "naslednji" točki odmika za lokacijo, kjer bo potekalo trenutno pisanje in branje. Če naslednja lokacija kaže na rep, je predpomnilnik poln in se podatki ne zapišejo več. Podobno, če je "head" enak "tail", je prazen in iz njega ni mogoče prebrati ničesar.

Standardni primer uporabe

Pomožni postopek, ki ga kliče proces aplikacije za pridobivanje podatkov iz obročnega predpomnilnika Java. Vključiti ga je treba v kritične dele, če vsebnik bere več kot ena nit. Pred branjem informacij se rep premakne na naslednji odmik, saj je vsak blok en bajt, podobna količina pa je rezervirana v bufferju, ko je zvezek v celoti naložen. V naprednejših izvedbah krožnega predpomnilnika pa ni nujno, da so posamezni razdelki enako veliki. V takšnih primerih se z dodatnimi preverjanji in omejitvami prihrani tudi zadnji bajt.

Če se v takšnih vezjih rep pred branjem premakne, lahko podatki, ki jih je treba prebrati, prepišejo novo podaljšani podatki. Na splošno je priporočljivo, da najprej preberete in nato premaknete končni kazalec. Najprej se določi dolžina predpomnilnika, nato se ustvari primerek "circ_bbuf_t" in dodeli kazalec "maxlen". Posoda mora biti globalna ali se mora nahajati v skladišču. Če je na primer potreben obročni predpomnilnik dolžine 32 bajtov, je v dodatku izvedeno naslednje (glejte "Dodatek"). spodnja slika).

Specifikacija funkcionalnih zahtev

Podatkovni tip "ring_t" bo podatkovni tip, ki vsebuje kazalec na buffer, velikost bufferja, indeks glave in repa, števec podatkov.

Funkcija inicializacije "ring_init ()" inicializira buffer na podlagi pridobitve kazalca na strukturo vsebnika, ki jo je ustvarila kličoča funkcija in ima vnaprej določeno velikost.

Funkcija "ring_add ()" za dodajanje obroča doda bajt na naslednje razpoložljivo mesto v medpomnilniku.

Funkcija "ring_remove ()" odstrani bajt z najstarejšega veljavnega mesta v vsebniku.

Funkcija "ring_peek ()" bo prebrala število bajtov "uint8_t `count`" iz obročnega bufferja v novega, ki je podan kot parameter, ne da bi odstranila vse vrednosti, prebrane iz vsebnika. Vrne število dejansko prebranih bajtov.

Funkcija "ring_clear ()" bo nastavila "Tail" na "Head" in naložila "0" v vse pozicije bufferja.

Ustvarjanje bufferja v jeziku C/C ++

Zaradi omejenih virov vgrajenih sistemov lahko v večini projektov s fiksno velikostjo najdemo podatkovne strukture s cikličnim bufferjem, ki delujejo, kot da je pomnilnik po naravi neprekinjen in cikličen. Podatkov ni treba preurediti, ker se ustvarja in uporablja pomnilnik, kazalci na glavo/konec pa se prilagodijo. Med ustvarjanjem knjižnice krožnega bufferja morajo uporabniki delati s knjižničnimi API-ji in ne smejo neposredno spreminjati strukture. Zato uporabite enkapsulacijo obročnega predpomnilnika na "C". Tako bo razvijalec ohranil implementacijo knjižnice in jo po potrebi spreminjal, ne da bi od končnih uporabnikov zahteval, da jo prav tako posodobijo.

Uporabniki ne morejo delati s kazalnikom "circular_but_t", namesto tega je ustvarjen tip deskriptorja, ki se lahko uporablja. Tako ne bo treba vnesti kazalca pri izvajanju funkcije ".typedefcbuf_handle_t". Razvijalci morajo zgraditi API za knjižnico. S knjižnico obročnega bufferja "C" komunicirajo s pomočjo nepreglednega tipa deskriptorja, ki se ustvari med inicializacijo. Običajno kot osnovno podatkovno vrsto izberete "uint8_t". Lahko pa uporabite katero koli posebno vrsto, pri čemer pazite na pravilno ravnanje z osnovnim bufferjem in številom bajtov. Uporabniki v stiku z vsebnikom izvajajo obvezne postopke:

1. Inicializacija vsebnika in njegove velikosti.
2. Ponastavitev krožne posode.
3. Dodajanje podatkov v krožni predpomnilnik "C".
4. Pridobi naslednjo vrednost iz vsebnika.
5. Zahtevajte informacije o trenutnem številu elementov in največji zmogljivosti.

Tako polni kot prazni primeri so videti enako: "glava" и "rep", kazalci so enaki. Obstajata dva pristopa, ki razlikujeta med polnim in praznim:

1. Polno stanje rep + 1 == glava.
2. prazna glava == rep.

Izvajanje knjižničnih funkcij

Če želite ustvariti krožni vsebnik, uporabite njegovo strukturo za upravljanje stanja. Da bi ohranili zaprtost, je struktura opredeljena znotraj knjižnice ".c" datoteke in ne v glavi. namestitev bo treba spremljati:

1. Osnovni podatkovni buffer.
2. Največja velikost.
3. trenutni položaj glave, ki se z dodajanjem povečuje.
4. Trenutni rep se z izbrisom povečuje.
5. Zastava, ki označuje, ali je posoda polna ali ne.

Zdaj, ko je vsebnik zasnovan, implementirajte funkcije knjižnice. Vsak od vmesnikov API zahteva inicializiran opisnik predpomnilnika. Namesto da bi preobremenili kodo s pogojnimi stavki, uporabite stavke za uveljavljanje zahtev sloga API.

Izvedba ne bo niti usmerjena, razen če so bile osnovni knjižnici cikličnega shranjevanja dodane ključavnice. API ima odjemalce, ki zagotavljajo osnovno velikost medpomnilnika za inicializacijo vsebnika, zato jo ustvarite na strani knjižnice, npr. zaradi lažjega "malloc". Sistemi, ki ne morejo uporabljati dinamičnega pomnilnika, morajo spremeniti funkcijo "init" in uporabiti drugo metodo, na primer dodelitev iz statičnega bazena vsebnikov.

Drug pristop je prekinitev enkapsulacije, ki uporabnikom omogoča statično deklariranje kontejnerskih struktur. V tem primeru je treba "circular_buf_init" posodobiti, da prevzame kazalec ali "init", ustvari strukturo sklada in jo vrne. Ker pa je enkapsulacija prekinjena, jo bodo uporabniki lahko spreminjali brez potrebe po knjižničnih postopkih. Ko je vsebnik ustvarjen, vnesite vrednosti in pokličite "ponastavitev". Pred vrnitvijo iz funkcije "init" sistem poskrbi, da je vsebnik ustvarjen v praznem stanju.

Dodajanje in brisanje podatkov

Za dodajanje in odstranjevanje podatkov iz medpomnilnika je treba ravnati s kazalcema "head" in "tail". Pri dodajanju v vsebnik se nova vrednost vstavi v trenutni "glava"-mesto in ga promovirati. Ob izbrisu se prikliče trenutna vrednost "rep"-kazalec in spodbujanje "rep". Če jo je treba promovirati "rep"-in "head", je treba preveriti, ali vstavitev vrednosti povzroči "celotna". Ko je predpomnilnik že poln, premaknite "rep" za en korak pred "glavo".

Ko je kazalec povišan, napolnite "celotna"-in preveri enakost "head == rep". Modularna uporaba operatorja bo povzročila, da se vrednosti "head" in "tail" ponastavijo na "0", Ko je dosežena največja velikost. To zagotavlja, da sta "head" in "tail" vedno veljavna indeksa osnovne podatkovne posode: "statični void advance_pointer (cbuf_handle_t cbuf)". Ustvarite lahko podobno pomožno funkcijo, ki se pokliče, ko se vrednost izbriše iz predpomnilnika.

Vmesnik razreda predloge

Da bi implementacija C++ podpirala vse podatkovne vrste, se uporabi vzorec:

1. Ponastavite buffer, da se počisti.
2. Dodajanje in odstranjevanje podatkov.
3. Preverite stanje polnosti/praznosti.
4. Preverite trenutno število elementov.
5. Preverjanje skupne prostornine posode.
6. Če želite, da po uničenju predpomnilnika ne ostanejo podatki, uporabite inteligentne kazalnike C ++, ki uporabnikom zagotavljajo, da lahko manipulirajo s podatki.

V tem primeru je v bufferju C ++ posneman velik del logike implementacije C, vendar je rezultat veliko čistejši in ponovno uporaben. Poleg tega vsebnik C ++ uporablja "std::mutex" za zagotavljanje izvajanja, usmerjenega v niti. Pri ustvarjanju razreda se dodelijo podatki za glavni predpomnilnik in določi njegova velikost. S tem se odpravijo režijski stroški, ki so potrebni pri uporabi C. V nasprotju s tem konstruktor C ++ ne kliče "ponastavitev", ker so določene začetne vrednosti spremenljivk, se krožni vsebnik začne v pravilnem stanju. Ponastavitev vrne predpomnilnik v prazno stanje. C ++ implementacija krožnega zabojnika "velikost" in "zmogljivost" sporočata število elementov v vrsti in ne velikosti v bajtih.

Gonilnik STM32 UART

Ko bo buffer deloval, ga je treba vključiti v gonilnik UART. Najprej kot globalni element v datoteki, zato mora biti deklariran:

• "deskriptor_rbd" in pomnilnik "_rbmem: statični rbd_t _rbd";
• "statični znak _rbmem [8]".

Ker gre za gonilnik UART, pri katerem mora biti vsak znak 8-bitni, je dovoljeno ustvariti polje znakov. Če se uporablja 9- ali 10-bitni način, mora biti vsak element "uint16_t". vsebnik se izračuna tako, da se prepreči izguba podatkov.

Moduli čakalne vrste pogosto vsebujejo statistične informacije, ki omogočajo spremljanje največje izkoriščenosti. V inicializacijski funkciji "uart_init" je treba buffer inicializirati s klicem "ring_buffer_init" in posredovanjem atributne strukture z vsakim članom, ki mu je dodeljena obravnavana vrednost. Če je uspešno inicializiran, se modul UART ponastavi in v IFG2 je dovoljeno prekinjeno sprejemanje.

Druga funkcija, ki jo je treba spremeniti, je "uart_getchar". Branje prejetega simbola iz periferije UART se nadomesti z branjem iz čakalne vrste. Če je čakalna vrsta prazna, mora funkcija vrniti -1. Nato moramo implementirati UART, da dobimo ISR. Odprite datoteko glave "msp430g2553.h", pomaknite se navzdol do razdelka z vektorji prekinitev, kjer se nahaja vektor z imenom USCIAB0RX. Iz poimenovanja je razvidno, da ga uporabljata modula USCI A0 in B0. Status prekinitve prejema USCI A0 lahko preberete iz IFG2. Če je nastavljena, je treba zastavico izbrisati in podatke v sprejemnem polju spraviti v buffer z uporabo "ring_buffer_put".

Repozitorij podatkov UART

Ta zbirka vsebuje informacije o tem, kako brati podatke prek UART z uporabo DMA, kadar število bajtov za sprejem ni vnaprej znano. V družini mikrokrmilnikov STM32 lahko obročni predpomnilnik STM32 deluje v različnih načinih:

1. Način spraševanja (brez DMA, brez IRQ) - aplikacija mora spraševati bitov stanja, da preveri, ali je bil sprejet nov znak, in ga prebrati dovolj hitro, da lahko pobere vse bajte. Zelo preprosta izvedba, ki pa je nihče ne uporablja v resničnem življenju. minus - zlahka spregledate prejete znake v podatkovnih paketih, deluje le pri nizkih prenosnih hitrostih.
2. način prekinitve (brez DMA) - obročni predpomnilnik UART sproži prekinitev in CPU izvede servisno rutino za obdelavo sprejema podatkov. Najpogostejše Pristop v vseh današnjih aplikacijah, dobro deluje v območju srednjih hitrosti. Slabosti - prekinitvene rutine se izvajajo za vsak prejeti znak, kar lahko ustavi druga opravila v zmogljivih mikrokrmilnikih z veliko prekinitvami in hkrati ustavi operacijski sistem ob prejemu podatkovnega paketa.
3. Način DMA se uporablja za prenos podatkov iz registra USART RX v uporabniški pomnilnik na ravni strojne opreme. Na tej stopnji ni potrebna interakcija z aplikacijo, razen obdelave podatkov, ki jih prejme aplikacija. Zelo enostavno delo z operacijski sistemi. Optimizirano za visoke hitrosti prenosa podatkov > 1 Mb/s in aplikacijah z nizko porabo energije, v primeru velikih podatkovnih paketov pa bi lahko povečana velikost predpomnilnika izboljšala funkcionalnost.

Izvajanje v sistemu ARDUINO

Arduino ring buffer velja tako za zasnovo plošče kot za programsko okolje, ki se uporablja za delovanje. Jedro Arduina je mikrokrmilnik serije Atmel AVR. Večino dela opravi AVR in v mnogih pogledih plošča Arduino okoli AVR predstavlja funkcionalnost - enostavno povezovanje nožic, serijski vmesnik USB za programiranje in komunikacijo.

Veliko običajnih plošč Arduino zdaj uporablja obročni predpomnilnik ATmega 328, starejše plošče pa so uporabljale ATmega168 in ATmega8. Plošče, kot je Mega, se odločijo za bolj zapletene različice, kot so 1280 in podobne. Hitrejši kot sta Due in Zero, boljša je uporaba ARM. Obstaja približno ducat različnih plošč Arduino z imeni. Imajo lahko različne količine pomnilnika flash, RAM in vhodno-izhodnih priključkov z obročnim predpomnilnikom AVR.

Uporablja se spremenljivka "roundBufferIndex" za shranjevanje trenutnega položaja, pri dodajanju v medpomnilnik pa se pojavi omejitev polja.

To so rezultati izvajanja kode. Številke so shranjene v medpomnilniku, in ko je ta poln, se začnejo prepisovati. Na ta način lahko dobite zadnjih N številk.

V prejšnjem primeru je bil za dostop do trenutnega položaja v predpomnilniku uporabljen indeks, saj zadostuje za razlago operacije. Na splošno pa je običajno, da uporabljate kazalec. To je spremenjena koda za uporabo kazalca namesto indeksa. Postopek je v bistvu enak prejšnjemu, dobljeni rezultati pa so podobni.

Visoko zmogljive operacije CAS

Disruptor je visoko zmogljiva knjižnica za posredovanje sporočil med nitmi, ki jo je pred nekaj leti razvilo in odkrilo podjetje LMAX Exchange. To programsko opremo so ustvarili za obdelavo velikega prometa (več kot 6 milijonov TPS) v svoji platformi za maloprodajno finančno trgovanje. Leta 2010 so vse presenetili s hitrostjo svojega sistema, saj so vso poslovno logiko izvajali v eni sami niti. Medtem ko je bila ena nit pomemben koncept njihove rešitve, Disruptor deluje v večnitnem okolju in temelji na krožnem bufferju - niti, v kateri zastareli podatki niso več potrebni, ker prihajajo bolj sveži in aktualni podatki.

V tem primeru vrne napačno logično vrednost ali zaklene. Če nobena od teh rešitev ne zadovolji uporabnikov, je mogoče uporabiti buffer spremenljive velikosti, vendar le, ko je poln, in ne le, ko proizvajalec doseže konec polja. Za spremembo velikosti bo treba vse elemente premakniti v novo dodeljeno večje polje, če se uporablja kot osnovna podatkovna struktura, kar je seveda draga operacija. Obstaja veliko Druge stvari, zaradi katerih je Disruptor hiter, na primer poraba sporočil v paketnem načinu.

Obročni buffer "qtserialport" (serijska vrata) je podedovana od QIODevice, uporablja se lahko za sprejemanje različnih serijskih informacij in vključuje vse razpoložljive serijske naprave. Serijska vrata so vedno odprta z monopolnim dostopom, kar pomeni, da drugi procesi ali niti ne morejo dostopati do odprtih serijskih vrat.

Obročni predpomnilniki so zelo uporabni pri programiranju na "C", Tako lahko na primer ocenimo tok bajtov, ki prihaja prek UART.