Ringbuffer

'n Ringbuffer of ringtou is 'n datastruktuur wat gebruik maak van 'n enkele buffer van 'n vaste grootte asof hy kop-aan-kop verbind is. Hierdie struktuur leen homself daartoe om datastrome te buffer.

'n Ring wat konsepsueel 'n ringbuffer toon. Hierdie wys visueel dat die buffer geen werklike einde het nie en dat dit weer aansluit by die begin van die buffer. Aangesien geheue nooit fisies as 'n ring gemaak word nie, word 'n lineêre voorstelling meestal gebruik soos onder aangetoon word.

Gebruike

Die nuttige eienskap van 'n ringbuffer is dat dit nie nodig is om sy elemente rond te skuif wanneer een verbruik word nie. As 'n buffer wat nié 'n ringbuffer is nie gebruik sou word, sou dit nodig wees om alle elemente te skuif wanneer een verbruik word. Met ander woorde is die ringbuffer goed geskik as 'n FIFO-buffer (eerste-in-eerste-uit of EIEU), terwyl 'n gewone buffer wat nie 'n ring is nie, goed geskik is as 'n LIFO-buffer (laaste-in-laaste-uit of LILU).

Die opstel van 'n buffer is 'n goeie implementeringstrategie vir 'n tou met 'n vaste maksimumgrootte. As 'n maksimumgrootte daargestel word vir 'n tou is 'n ringbuffer 'n ideale implementasie daarvan; alle toubewerkings voer uit in konstante tyd. Om 'n ringbuffer te vergroot benodig egter dat geheue geskuif word, wat relatief duur is. Vir arbitrêre toue kan 'n geskakelde lys dalk eerder gebruik word. 'n Moontlike voordeel van 'n ringbuffer bo 'n geskakelde lys is dat die ringbufer se geheue aaneenlopend is, wat beter geheuelokaliteit kan bied.

In sommige situasies kan 'n oorskrywende ringbuffer gebruik word, bv. in multimedia. As die buffer gebruik word as die begrensde buffer in die produsent-verbruiker-probleem is dit waarskynlik wenslik vir die produsent (bv. 'n klankgenerator) om ou data te oorskryf as die verbruiker (bv. die klankkaart) tydelik nie kan bybly nie. Verder werk die LZ77-familie van verlieslose saampersalgoritmes met die aanname dat stringe wat meer onlangs in 'n datastroom gesien is, met hoër waarskynlikheid binnekort in die stroom sal voorkom. Implementasies stoor die mees onlangse data in 'n ringbuffer.

Hoe dit werk

'n Sleutelbordringbuffer met 24 grepe. Wanneer die skryfwyser op die punt staan om die leeswyser te bereik omdat die mikroverwerker nie reageer nie, sal die buffer ophou om sleuteldrukke op te neem en — in sekere rekenaars — 'n foutklank genereer.

'n Ringbuffer begin aanvanklik leeg met 'n voorafbepaalde lengte. As voorbeeld, hier is 'n buffer met 7 elemente:

Kom ons neem aan dat 'n 1 na die middel van die buffer geskryf word (die presiese beginposisie maak nie saak in 'n ringbuffer nie):

Sê dat nog twee elemente bygevoeg word — 2 en 3 — wat ná die 1 bygevoeg word:

As twee elemente dan uit die buffer verwyder word, word die twee oudste waardes in die buffer verwyder. Die twee elemente wat verwyder word, is in hierdie geval 1 en 2, wat slegs 3 agter laat in die buffer:

As die buffer 7 elemente het, is dit heeltemal vol:

'n Gevolg van die ringbuffer is dat wanneer hy vol is en 'n daaropvolgende invoeging gedoen word, hy begin om die oudste data te oorskryf. In hierdie geval word twee nuwe elemente — A en B — bygevoeg en hulle oorskryf die 3 en die 4:

Andersins kan die roetines wat die buffer onderhou, keer dat die data oorskryf word en 'n fout lewer of 'n programuitsondering lewer. Of data oorskryf word of nie kom neer op die semantiek van die bufferroetines of die toepassing wat die ringbuffer gebruik.

Laastens, as daar nou twee elemente verwyder word, is dit nie 3 en 4 wat gelewer word nie, maar 5 en 6 omdat A en B die 3 en die 4 oorskryf het. Dit laat die buffer met:

Implementasie van die ringbuffer

'n Ringbuffer kan geïmplementeer word met vier wysers, of twee wysers en twee heelgetalle:

• die buffer se begin in die geheue
• die buffer se einde in die geheue, of die buffer se kapasiteit
• die begin van geldige data (indeks of wyser)
• die einde van geldige data (indeks of wyser), of die hoeveelheid data tans in die buffer (heelgetal)

Hierdie beeld wys 'n buffer wat gedeeltelik vol is:

Hierdie beeld wys 'n vol buffer met vier elemente (getalle 1 tot 4) wat oorskryf is:

Wanneer 'n element oorskryf word, word die beginwyser aangeskuif na die volgende element.

As die volle kapasiteit van die buffer gebruik word in 'n wysergebaseerde implementasie, kan daar nie met die begin- en eindindekse bepaal word of die buffer vol of leeg is nie. Daar moet dus hiervoor 'n verdere meganisme geïmplementeer word om hiervoor te toets. 'n Algemene manier om dit die hoof te bied wanneer twee wysers gebruik word, is om slegs (grootte - 1) items in die buffer toe te laat. Wanneer die twee wysers gelyk is, is die buffer leeg, en wanneer die eindwyser een minder is as die beginwyser, is die buffer vol.

Waar die buffer daarenteen ontwerp word om tred te hou van die aantal elemente n is 'n toets vir leegheid bloot 'n toets vir n = 0 en 'n toets vir volheid behels bloot om te toets of n gelyk is aan die kapasiteit.

Die aanskuif en terugsksuif van die wysers van die ringbuffer word gedoen in sagteware met die volgende modulusberekenings:

   skuif_adres_een_aan = (adres + 1) % lengte

   skuif_adres_een_terug = (adres + lengte -1) % lengte

Let wel: die byvoeging van die lengte by die terugskuifbewerking is nodig om negatiewe resultate te verhoed en sodat die eindadres van die ringbuffer korrek oorrol na die begin.

Eksterne skakels

• CircularBuffer by die Portland Pattern Repository
• Boost: Templated Circular Buffer Container
• Circular Buffering
• Circular queue in C Geargiveer 29 Oktober 2018 op Wayback Machine