Co je to prstencová vyrovnávací paměť?

Prstencová vyrovnávací paměť je také známá jako fronta nebo cyklická vyrovnávací paměť a je běžnou formou fronty. Je to populární, snadno implementovatelný standard, a přestože je prezentován jako kruh, v základním kódu je lineární. Kruhová fronta existuje jako pole pevné délky se dvěma ukazateli: jeden představuje začátek fronty a druhý představuje ocas. Nevýhodou metody je její pevná velikost. U front, kde musí být prvky přidány a odstraněny uprostřed, nejen na začátku a na konci vyrovnávací paměti, je upřednostňovaným přístupem implementace jako propojený seznam.

Teoretické základy vyrovnávací paměti

Po pochopení základní teorie je pro uživatele snazší vybrat efektivní strukturu polí. Cyklická vyrovnávací paměť-datová struktura, kde je pole zpracováno a vykresleno jako smyčky, to znamená, že indexy se po dosažení délky pole vrátí na 0. To se provádí pomocí dvou ukazatelů na pole: "head" a "tail". Když jsou data přidána do vyrovnávací paměti, ukazatel záhlaví se posune nahoru. Podobně, když jsou odstraněny, ocas se také pohybuje nahoru. Určení hlavy, ocasu, směru jejich pohybu, místa zápisu a čtení závisí na implementaci schématu.

Kruhové vyrovnávací paměti jsou nadměrně využívány pro řešení problémů spotřebitele. To znamená, že jedno vlákno provádění je zodpovědné za produkci dat a druhé za spotřebu. Ve vestavěných zařízeních s velmi nízkou až střední úrovní je výrobce prezentován ve formátu ISR (informace získané ze senzorů) a spotřebitel ve formě hlavního cyklu událostí.

Zvláštností cyklických vyrovnávacích pamětí je, že jsou implementovány bez nutnosti zámků v prostředí jednoho výrobce a jednoho spotřebitele. Díky tomu jsou ideální informační strukturou pro vestavěné programy. Následující rozdíl - neexistuje žádný přesný způsob, jak odlišit vyplněný sektor od prázdného. To je, protože v obou případech hlava splývá s ocasem. Existuje mnoho způsobů a řešení, jak to zvládnout, ale většina z nich přináší větší zmatek a ztěžuje čitelnost.

Další otázka, která vyvstává s ohledem na cyklickou vyrovnávací paměť. Musím obnovit nová data nebo přepsat existující data, když je plná? Odborníci tvrdí, že neexistuje jasná výhoda jednoho nad druhým a jeho implementace závisí na konkrétní situaci. Pokud mají tyto aplikace větší význam, použijte metodu přepsání. Na druhou stranu, pokud jsou zpracovány v režimu "first-come-first-served", pak zlikvidovat nové, když je kruhová vyrovnávací paměť naplněna.

Implementace cyklické fronty

Při provádění definujte datové typy a poté metody: core, push a pop. V postupech" push "a" pop "vypočítají" následující " body posunu pro umístění, kde dojde k aktuálnímu zápisu a čtení. Pokud další umístění ukazuje na ocas, vyrovnávací paměť je plná a data již nejsou zapsána. Podobně, když se" head "rovná " tail", je prázdný a nic z toho není čitelné.

Standardní případ použití

Pomocný postup je vyvolán procesem aplikace pro extrakci dat z kruhové vyrovnávací paměti Java. To by mělo být zahrnuto do kritických oddílů, pokud se čte kontejner více než jedno vlákno. Ocas se přesune na další offset před přečtením informací, protože každý blok je jeden bajt a podobné množství je zálohováno ve vyrovnávací paměti, když je objem plně načten. Ale v pokročilejších implementacích cyklické jednotky nemusí být jednotlivé oddíly nutně stejné velikosti. V takových případech se snaží zachránit i poslední bajt přidáním dalších kontrol a hranic.

V takových schématech, pokud se ocas pohybuje před čtením, mohou být informace, které mají být přečteny, potenciálně přepsány nově předloženými daty. Obecně se doporučuje nejprve přečíst a poté přesunout ocasní ukazatel. Nejprve definujte délku vyrovnávací paměti a poté vytvořte instanci "circ_bbuf_t" a přiřaďte ukazatel"maxlen". V tomto případě musí být kontejner globální nebo v zásobníku. Například, pokud potřebujete 32 bajtů kruhovou vyrovnávací paměť, proveďte v aplikaci následující (viz. obrázek níže).

SPECIFIKACE funkčních požadavků

Datový typ "ring_t" by byl datový typ, který obsahuje ukazatel na vyrovnávací paměť, jeho velikost, index záhlaví a ocasu, čítač dat.

Inicializační funkce " ring_init ()" inicializuje vyrovnávací paměť na základě získání ukazatele na strukturu kontejneru vytvořeného volající funkcí, která má předdefinovanou velikost.

Funkce přidání hovoru " ring_add ()" přidá bajt do další dostupné mezery ve vyrovnávací paměti.

Funkce odstranění prstence "ring_remove ()" odstraní bajt z nejstaršího platného místa v kontejneru.

Ring peek ve funkci "ring_peek ()" přečte počet bajtů "uint8_t ` count` " z kruhové vyrovnávací paměti do nové, poskytnuté jako parametr, aniž by byly odstraněny jakékoli hodnoty načtené z kontejneru. Vrátí počet skutečně přečtených bajtů.

Funkce čištění kroužku "ring_clear () "nastaví" Tail " na "Head" a načte" 0 " na všechny pozice vyrovnávací paměti.

Vytvoření vyrovnávací paměti v C / C ++

Vzhledem k omezeným zdrojům vestavěných systémů lze datové struktury s vyrovnávací pamětí smyčky nalézt ve většině projektů s pevnou velikostí, které fungují, jako by paměť byla ze své podstaty spojitá a cyklická. Data nemusí být přeskupena, protože je generována a používána paměť, ale jsou upraveny ukazatele hlavy / ocasu. Během vytváření knihovny smyčkových vyrovnávacích pamětí je nutné, aby uživatelé pracovali spíše s knihovními API, než aby přímo upravovali strukturu. Proto použijte zapouzdření prstencového pufru na "Si". Tímto způsobem si vývojář ponechá implementaci knihovny a podle potřeby ji upraví, aniž by ji museli aktualizovat i koncoví uživatelé.

Uživatelé nemohou pracovat s ukazatelem" circular_but_t", je vytvořen Typ deskriptoru, který lze místo toho použít. Tím se eliminuje potřeba uvést ukazatel v implementaci funkce ".typedefcbuf_handle_t». Vývojáři potřebují sestavit API pro knihovnu. Interagují s knihovnou kruhové vyrovnávací paměti "C" pomocí neprůhledného typu deskriptoru, který je vytvořen během inicializace. Obvykle zvolit" uint8_t " jako základní datový typ. Je však možné použít jakýkoli konkrétní typ s opatrností při správném zpracování základní vyrovnávací paměti a počtu bajtů. Uživatelé komunikují s kontejnerem a provádějí povinné postupy:

1. Inicializovat kontejner a jeho velikost.
2. Resetujte Kruhový kontejner.
3. Přidat data do kruhové vyrovnávací paměti na "Si".
4. Získejte následující hodnotu z kontejneru.
5. Vyžádejte si informace o aktuálním počtu prvků a maximální kapacitě.

"Plné "i" prázdné " případy vypadají stejně: "head" a "tail", ukazatele jsou stejné. Existují dva přístupy, které rozlišují mezi úplným a prázdným:

1. Kompletní stav tail + 1 = = head.
2. Prázdný stav head = = tail.

Implementace funkcí knihovny

K vytvoření kruhového kontejneru použijte jeho strukturu ke správě stavu. Pro zachování zapouzdření je struktura definována uvnitř knihovny ".C " souboru, nikoli v záhlaví. Při instalaci budete muset sledovat:

1. Základní vyrovnávací paměť dat.
2. Maximální velikost.
3. Aktuální pozice hlavy, která se zvyšuje při přidávání.
4. Aktuální ocas se zvětšuje, když je odstraněn.
5. Příznak označující, zda je kontejner plný nebo ne.

Nyní, když je kontejner navržen, implementují funkce knihovny. Každé z API vyžaduje inicializovaný popisovač vyrovnávací paměti. Namísto ucpání kódu podmíněnými tvrzeními použijte příkazy k zajištění splnění požadavků API ve stylu.

Implementace nebude závitově orientovaná, pokud nebyly do základní knihovny cyklických úložišť přidány žádné zámky. Pro inicializaci kontejneru má API klienty, kteří poskytují základní velikost vyrovnávací paměti, takže ji vytvářejí na straně knihovny, například pro jednoduchost "malloc". Systémy, které nemohou používat dynamickou paměť, musí změnit funkci" init " tak, aby používaly jinou metodu, například alokaci ze statického fondu kontejnerů.

Dalším přístupem je narušení zapouzdření, které umožňuje uživatelům staticky deklarovat struktury kontejnerů. V tomto případě musí být "circular_buf_init" aktualizován, aby vzal ukazatel nebo "init", vytvořil strukturu zásobníku a vrátil ji. Protože je však zapouzdření narušeno, uživatelé jej budou moci změnit bez procedur knihovny. Po vytvoření kontejneru vyplňte hodnoty a vyvolejte "reset". Před návratem z "init" systém zajišťuje, že kontejner je vytvořen v prázdném stavu.

Přidávání a mazání dat

Přidání a odebrání dat z vyrovnávací paměti vyžaduje manipulaci s ukazateli" head "- a"tail". Při přidávání do kontejneru vložte novou hodnotu do aktuálního "head"-a propagují ho. Když je odstraněn, získá se hodnota aktuálního "tail"-ukazatel a propagovat "tail". Pokud potřebujete postoupit "tail"-ukazatel, stejně jako "head", je třeba zkontrolovat, zda vložení volá hodnoty "full". Když je vyrovnávací paměť již plná, posuňte "tail" o krok napřed před "head".

Jakmile je ukazatel pokročilý, vyplňte "full"-vlajka, kontrola rovnosti "head == tail". Modulární použití příkazu způsobí, že" head "a" tail " resetují hodnoty na "0", až bude dosaženo maximální velikosti. To zajišťuje, že" head "a" tail " budou vždy platné indexy podkladového datového kontejneru: "static void advance_pointer (cbuf_handle_t cbuf)". Je možné vytvořit podobnou pomocnou funkci, která se volá, když je hodnota odstraněna z vyrovnávací paměti.

Rozhraní třídy šablon

Aby implementace c ++ podporovala všechny typy dat, proveďte šablonu:

1. Resetování vyrovnávací paměti pro čištění.
2. Přidávání a mazání dat.
3. Kontrola úplného / prázdného stavu.
4. Kontrola aktuálního počtu položek.
5. Kontrola celkové kapacity kontejneru.
6. Chcete-li po zničení vyrovnávací paměti nezanechat Žádná Data, použijte inteligentní ukazatele C++, abyste zajistili, že uživatelé mohou data spravovat.

V tomto příkladu vyrovnávací paměť c ++ napodobuje většinu implementační logiky C, ale výsledkem je mnohem čistší a opakovaně použitelný design. Také kontejner C ++ používá "std::mutex" pro zajištění implementace zaměřené na vlákno. Při vytváření třídy přidělte data hlavní vyrovnávací paměti a nastavte její velikost. To eliminuje režii požadovanou implementací C. Na rozdíl od ní Konstruktor c ++ nevyvolává "reset", protože označují počáteční hodnoty pro členské proměnné, je kruhový kontejner spuštěn ve správném stavu. Resetovací chování vrátí vyrovnávací paměť do prázdného stavu. Při implementaci cyklického kontejneru C ++ "size" a "capacity" hlásí počet prvků ve frontě, nikoli velikost v bajtech.

Ovladač UART STM32

Po spuštění vyrovnávací paměti, musí být integrován do ovladače UART. Nejprve jako globální prvek v souboru, takže musíte deklarovat:

• "descriptor_rbd" a vyrovnávací paměť "_rbmem: static rbd_t _rbd";
• "static char _rbmem [8]".

Protože se jedná o ovladač UART, kde musí být každý znak 8bitový, je vytvoření pole znaků platné. Pokud se použije 9 nebo 10bitový režim, musí být každá položka "uint16_t". Kontejner se vypočítá tak, aby nedošlo ke ztrátě dat.

Moduly front často obsahují statistické informace, které umožňují sledovat maximální využití. Ve funkci inicializace "uart_init" musí být vyrovnávací paměť inicializována voláním "ring_buffer_init" a předáním struktury atributů každému členu, kterému jsou přiřazeny diskutované hodnoty. Pokud je úspěšně inicializován, modul UART je vyřazen z resetu, přerušení příjmu je povoleno v IFG2.

Druhou funkcí, kterou je třeba změnit, je "uart_getchar". Čtení přijatého znaku z periferie UART je nahrazeno čtením z fronty. Pokud je fronta prázdná, měla by funkce vrátit -1. Dále musíte implementovat UART, abyste získali ISR. Otevřete soubor záhlaví "msp430g2553.h", přejděte dolů do sekce přerušovacích vektorů, kde najdete vektor s názvem USCIAB0RX. Pojmenování znamená, že jej používají moduly USCI A0 a B0. Stav přerušení příjmu USCI A0 lze přečíst z IFG2. Pokud je nastaven, měl by být příznak vymazán a data v přijímacím prostoru umístěna do vyrovnávací paměti pomocí "ring_buffer_put".

Úložiště dat UART

Toto úložiště poskytuje informace o čtení dat přes UART pomocí DMA, když počet bajtů pro příjem není předem znám. V rodině mikrokontrolérů může kruhová vyrovnávací paměť STM32 pracovat v různých režimech:

1. Režim dotazování (bez DMA, bez IRQ) - aplikace musí dotazovat stavové bity, aby zkontrolovala, zda byl nový znak přijat, a přečíst jej dostatečně rychle, aby získal všechny bajty. Velmi jednoduchá implementace, ale nikdo ji v reálném životě nepoužívá. Nevýhody - snadno přeskočit přijaté znaky v datových paketech, funguje pouze pro nízké přenosové rychlosti.
2. Režim přerušení ( bez DMA) - kruhová vyrovnávací paměť UART spustí přerušení a procesor přejde do obslužného programu pro zpracování příjmu dat. Nejběžnější přístup ve všech aplikacích dnes funguje dobře v rozsahu střední rychlosti. Nevýhody - postup zpracování přerušení se provádí pro každý přijatý znak, může zastavit další úkoly ve vysoce výkonných mikrokontrolérech s velkým počtem přerušení a současně operační systém při přijímání datového paketu.
3. Režim DMA se používá k přenosu dat z registru USART RX do uživatelské paměti na hardwarové úrovni. V tomto okamžiku není nutná žádná interakce s aplikací, s výjimkou potřeby zpracovat data přijatá aplikací. Může velmi snadno pracovat s operační systém. Optimalizováno pro vysoké přenosové rychlosti > 1Mbps a aplikace s nízkým výkonem, v případě velkých datových paketů může zvýšení velikosti vyrovnávací paměti zlepšit funkčnost.

Implementace v Arduinu

Prstencová vyrovnávací paměť Arduino odkazuje jak na návrh desek, tak na programovací prostředí, které se používá pro provoz. Jádrem Arduina je mikrokontrolér řady Atmel AVR. Je to AVR, který dělá většinu práce, a v mnoha ohledech deska Arduino kolem AVR představuje funkčnost - snadno připojitelné kolíky, USB sériové rozhraní pro programování a komunikaci.

Mnoho běžných desek Arduino v současné době používá kruhovou vyrovnávací paměť C ATmega 328, starší desky používaly ATmega168 a ATmega8. Desky jako Mega se rozhodnou pro složitější možnosti, jako je 1280 a podobné. Čím rychlejší jsou Due a Zero, tím lepší je použití ARM. Existuje asi tucet různých desek Arduino se jmény. Mohou mít různá množství flash paměti, RAM a I / O porty s vyrovnávací pamětí AVR Ring.

Proměnná" roundBufferIndex " se používá pro skladování aktuální pozice a při přidání do vyrovnávací paměti dojde k omezení pole.

Toto jsou výsledky spuštění kódu. Čísla jsou uložena ve vyrovnávací paměti a jakmile jsou plná, začnou se přepisovat. Tímto způsobem můžete získat poslední n čísel.

Předchozí příklad používá index pro přístup k aktuální pozici vyrovnávací paměti, protože je dostatečný k vysvětlení operace. Ale obecně je normální použít ukazatel. Toto je upravený kód pro použití ukazatele místo indexu. Operace je v zásadě stejná jako předchozí a získané výsledky jsou podobné.

Vysoce výkonné operace CAS

Disruptor je vysoce výkonná Knihovna pro přenos zpráv mezi vlákny vyvinutá a otevřená před několika lety společností Lmax Exchange. Vytvořili tento software pro zpracování obrovského provozu (více než 6 milionů TPS) ve své maloobchodní finanční obchodní platformě. V roce 2010 překvapili každého, jak rychlý může být jejich systém, a to provedením veškeré obchodní logiky v jednom vlákně. Ačkoli jedno vlákno bylo důležitým konceptem v jejich řešení, Disruptor běží ve vícevláknovém prostředí a je založen na kruhové vyrovnávací paměti-podproces, ve kterém již nejsou potřeba žádná zastaralá data, protože přicházejí novější a relevantnější.

V tomto případě bude fungovat buď návrat falešné booleovské hodnoty, nebo zámek. Pokud žádné z těchto řešení neuspokojuje uživatele, je možné implementovat vyrovnávací paměť s proměnlivou velikostí, ale pouze když je naplněna, nejen když výrobce dosáhne konce pole. Změna velikosti bude vyžadovat přesun všech prvků do nově přiděleného většího pole, pokud se použije jako základní datová struktura, což je samozřejmě nákladná operace. Existuje mnoho další věci, díky nimž je Disruptor rychlý, například spotřeba zpráv v dávkovém režimu.

Prstencová vyrovnávací paměť "qtserialport" (sériový port) dědí z QIODevice, může být použit k získání různých sériových informací a zahrnuje všechna dostupná sériová zařízení. Sériový port je vždy otevřen v monopolním přístupu, což znamená, že jiné procesy nebo vlákna nemohou přistupovat k otevřenému sériovému portu.

Kruhové vyrovnávací paměti jsou velmi užitečné při programování na "Si", je například možné odhadnout tok bajtů přicházejících přes UART.