Cirkulär buffert
Inom datavetenskap är en cirkulär buffert , cirkulär kö , cyklisk buffert eller ringbuffert en datastruktur som använder en enda buffert med fast storlek som om den var ansluten ände till ände. Denna struktur lämpar sig lätt för att buffra dataströmmar . Det fanns tidiga cirkulära buffertimplementeringar i hårdvara.
Översikt
En cirkulär buffert börjar först tom och har en inställd längd. I diagrammet nedan är en 7-elements buffert:
Antag att 1 skrivs i mitten av en cirkulär buffert (den exakta startplatsen är inte viktig i en cirkulär buffert):
Antag sedan att ytterligare två element läggs till i den cirkulära bufferten — 2 & 3 — som sätts efter 1:
Om två element tas bort kommer de två äldsta värdena inuti den cirkulära bufferten att tas bort. Cirkulära buffertar använder FIFO ( först in, först ut ) logik. I exemplet var 1 & 2 de första som gick in i den cirkulära bufferten, de är de första som tas bort, vilket lämnar 3 inuti bufferten.
Om bufferten har 7 element är den helt full:
En egenskap hos den cirkulära bufferten är att när den är full och en efterföljande skrivning utförs, så börjar den skriva över den äldsta datan. I det aktuella exemplet läggs ytterligare två element - A & B - till och de skriver över 3 och 4:
Alternativt kan rutinerna som hanterar bufferten förhindra att data skrivs över och returnera ett fel eller skapa ett undantag . Huruvida data skrivs över eller inte är upp till semantiken för buffertrutinerna eller applikationen som använder den cirkulära bufferten.
Slutligen, om två element nu tas bort så är det som skulle returneras inte 3 & 4 utan A & B eftersom A & B skrev över 3 & 4:an som ger bufferten med:
Används
Den användbara egenskapen hos en cirkulär buffert är att den inte behöver blandas runt när en är förbrukad. (Om en icke-cirkulär buffert användes skulle det vara nödvändigt att flytta alla element när ett är förbrukat.) Med andra ord är den cirkulära bufferten väl lämpad som en FIFO (först in, först ut) buffert medan en standard, icke-cirkulär buffert är väl lämpad som en LIFO ( sist in, först ut ) buffert.
Cirkulär buffring är en bra implementeringsstrategi för en kö som har fast maxstorlek. Skulle en maximal storlek antas för en kö, då är en cirkulär buffert en helt idealisk implementering; alla köoperationer är konstant tid. För att utöka en cirkulär buffert krävs dock att minnet flyttas, vilket är jämförelsevis kostsamt. För godtyckligt expanderande köer kan en länkad listmetod vara att föredra istället.
I vissa situationer kan överskrivande cirkulär buffert användas, t.ex. i multimedia. Om bufferten används som den avgränsade bufferten i producent-konsumentproblemet är det förmodligen önskvärt att producenten (t.ex. en ljudgenerator) skriver över gammal data om konsumenten (t.ex. ljudkortet) inte kan hänga med för en stund. . Dessutom LZ77 -familjen av förlustfria datakomprimeringsalgoritmer på antagandet att strängar som ses på senare tid i en dataström är mer sannolikt att förekomma snart i strömmen. Implementeringar lagrar de senaste uppgifterna i en cirkulär buffert.
Cirkulär buffertmekanik
En cirkulär buffert kan implementeras med hjälp av en pekare och tre heltal:
- buffertstart i minnet
- buffertkapacitet (längd)
- skriv till buffertindex (slut)
- läsa från buffertindex (start)
Den här bilden visar en delvis full buffert med Length = 7:
Den här bilden visar en full buffert med fyra element (nummer 1 till 4) som har skrivits över:
I början är indexen slut och start satta till 0. Den cirkulära buffertskrivoperationen skriver ett element till slutindexpositionen och slutindexet inkrementeras till nästa buffertposition. Den cirkulära buffertläsoperationen läser ett element från startindexpositionen och startindexet inkrementeras till nästa buffertposition.
Start- och slutindexen räcker inte för att säga att bufferten är full eller tom samtidigt som alla buffertplatser används, men kan om bufferten endast har en maximal användningsstorlek på Length - 1. I detta fall är bufferten tom om start- och slutindex är lika och fulla när storleken under användning är Length - 1. En annan lösning är att ha ytterligare ett heltalsantal som inkrementeras vid en skrivoperation och minskas vid en läsoperation. Att kontrollera för tomhet betyder att testantalet är lika med 0 och att kontrollera om det är fyllt betyder att testantalet är lika med Length.
Följande källkod är en C-implementation. Funktion put() lägger ett objekt i bufferten, funktion get() får ett objekt från bufferten:
0
0
#define BUFLEN 3 int buf [ BUFLEN ]; /* array som ska behandlas som cirkulär buffert av BUFLEN-heltal */ int end = ; /* skriv index */ int start = ; /* läs index */ void put ( int item ) { buf [ end ++ ] = item ; slut %= BUFLEN ; } int get () { int item = buf [ start ++ ]; start %= BUFLEN ; returnera vara ; }
Optimering
En cirkulär buffertimplementering kan optimeras genom att mappa den underliggande bufferten till två sammanhängande regioner av virtuellt minne . [ ifrågasatt ] (Naturligtvis måste den underliggande buffertens längd då motsvara någon multipel av systemets sidstorlek .) Läsning från och skrivning till den cirkulära bufferten kan då utföras med större effektivitet med hjälp av direkt minnesåtkomst; de åtkomster som faller bortom slutet av den första virtuella minnesregionen kommer automatiskt att gå runt till början av den underliggande bufferten. När läsförskjutningen flyttas till den andra virtuella minnesregionen, minskas båda förskjutningarna – läs och skriv – med längden på den underliggande bufferten.
Cirkulär buffert med fast längd och angränsande block
Den kanske vanligaste versionen av den cirkulära bufferten använder 8-bitars byte som element.
Vissa implementeringar av den cirkulära bufferten använder element med fast längd som är större än 8-bitars byte—16-bitars heltal för ljudbuffertar, 53-byte ATM-celler för telekombuffertar, etc. Varje objekt är sammanhängande och har korrekt datajustering , så programvara som läser och skriver dessa värden kan vara snabbare än programvara som hanterar icke-sammanhängande och icke-justerade värden.
Ping-pong-buffring kan betraktas som en mycket specialiserad cirkulär buffert med exakt två stora element med fast längd.
Bip -bufferten (bipartit buffert) är mycket lik en cirkulär buffert, förutom att den alltid returnerar angränsande block som kan ha variabel längd. Detta erbjuder nästan alla effektivitetsfördelarna med en cirkulär buffert samtidigt som det behåller möjligheten för bufferten att användas i API:er som endast accepterar angränsande block.
Komprimerade cirkulära buffertar med fast storlek använder en alternativ indexeringsstrategi baserad på elementär talteori för att upprätthålla en komprimerad representation med fast storlek av hela datasekvensen.
externa länkar
- CircularBuffer vid Portland Pattern Repository
- Boost:
- CB i Linux-kärnan
- CB i DSP
- Cirkulär kö i C Arkiverad 2018-10-29 på Wayback Machine