Cirkulär buffert - Circular buffer
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 vore ansluten från ände till ände. Denna struktur lämpar sig lätt för buffring av dataströmmar .
Översikt
En cirkulär buffert börjar först tom och har en inställd längd. I diagrammet nedan finns en 7-elements buffert:
Antag att 1 är skrivet 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 läggs efter 1:
Om två element tas bort skulle de två äldsta värdena inuti den cirkulära bufferten tas bort. Cirkulära buffertar använder FIFO ( först in, först ut ) logik. I exemplet var 1 & 2 först med att komma in i den cirkulära bufferten, de är de första som togs bort och lämnade 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, börjar den skriva över de äldsta data. I det aktuella exemplet läggs ytterligare två element - A & B - till och de skriver över 3 & 4:
Alternativt kan de rutiner som hanterar bufferten förhindra överskrivning av data 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 är det som skulle returneras inte 3 & 4 utan 5 & 6 eftersom A & B skrev över 3 & 4 som gav bufferten med:
Användningsområden
Den användbara egenskapen hos en cirkulär buffert är att den inte behöver ha sina element blandade runt när en konsumeras. (Om en icke-cirkulär buffert användes skulle det vara nödvändigt att flytta alla element när en förbrukas.) 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ö, är en cirkulär buffert en helt idealisk implementering; alla köoperationer är konstant tid. Att expandera en cirkulär buffert kräver dock att minnet skiftas, vilket är relativt dyrt. För godtyckligt expanderande köer kan en länkad listmetod i stället föredras.
I vissa situationer kan överskrivande cirkulär buffert användas, t.ex. i multimedia. Om bufferten används som den begränsade bufferten i producent-konsumentproblemet är det förmodligen önskvärt för producenten (t.ex. en ljudgenerator) att skriva över gamla data om konsumenten (t.ex. ljudkortet ) inte kan hänga med tillfälligt . Även LZ77 familjen förlustfri datakomprimering algoritmer arbetar på antagandet att strängar ses mer nyligen i en dataström är mer sannolikt att inträffa kort tid i strömmen. Implementeringar lagrar de senaste uppgifterna i en cirkulär buffert.
Cirkulär buffertmekanik
En cirkulär buffert kan implementeras med fyra pekare eller två pekare och två heltal:
- buffertstart i minnet
- buffertänd i minne eller buffertkapacitet
- start av giltig data (index eller pekare)
- slutet av giltiga data (index eller pekare), eller datamängd för närvarande i bufferten (heltal)
Den här bilden visar en delvis full buffert:
Denna bild visar en fullständig buffert med fyra element (nummer 1 till 4) som har skrivits över:
När ett element skrivs över ökas startpekaren till nästa element.
Genom att utnyttja full buffertkapacitet med pekarbaserad implementeringsstrategi kunde buffertens fulla eller tomma tillstånd inte lösas direkt genom att kontrollera start- och slutindexens positioner. Därför måste en ytterligare mekanism implementeras för att kontrollera detta. Ett vanligt sätt att hantera detta, när du använder 2 pekare, är att bara låta bufferten hålla (storlek - 1) objekt. När båda pekarna är lika är bufferten tom och när slutpekaren är en mindre än startpekaren är bufferten full.
När bufferten istället är utformad för att spåra antalet insatta element n betyder kontroll för tomhet att kontrollera n = 0 och att kontrollera om fullhet innebär att kontrollera om n är lika med kapaciteten.
Ökning och minskning av de cirkulära buffertadresspekarna åstadkoms i programvara med följande modulformler:
increment_address_one = (address + 1) % Length
decrement_address_one = (address + Length - 1) % Length
På språk vars modulo -operatör tillämpar trunkerad division , krävs det extra längdtillägget för minskningen med en operation för att förhindra negativa resultat och för att säkerställa att slutadressen för den cirkulära bufferten är korrekt.
Optimering
En cirkulärbuffertimplementering kan optimeras genom att mappa den underliggande bufferten till två sammanhängande områden i virtuellt minne . (Naturligtvis måste den underliggande buffertlängden då motsvara en multipel av systemets sidstorlek .) Läsning från och skrivning till den cirkulära bufferten kan sedan utföras med större effektivitet med hjälp av direkt minnesåtkomst; de accesser som faller bortom slutet av det första virtuella minnesområdet kommer automatiskt att linda runt till början av den underliggande bufferten. När läsförskjutningen avanceras till det andra virtuella minnesområdet, minskas båda förskjutningarna-läs och skriv-med längden på den underliggande bufferten.
Fixerad längd-element och sammanhängande block cirkulär buffert
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 rätt datajustering , så att läsa och skriva av dessa värden kan vara snabbare än programvara som hanterar icke-sammanhängande och icke-anpassade värden.
Pingisbuffert kan betraktas som en mycket specialiserad cirkulär buffert med exakt två stora element med fast längd.
Den bip buffert (bipartit buffert) är mycket lik en cirkulär buffert, förutom att det alltid återvänder angränsande block som kan vara variabel längd. Detta ger nästan alla effektivitetsfördelar med en cirkulär buffert samtidigt som bufferten kan användas i API: er som endast accepterar sammanhängande 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 av hela storleken på hela datasekvensen.