Ringbuffer

in Wikipedia, die vrye ensiklopedie
Jump to navigation Jump to search
'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.

'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.

Gebruike[wysig | wysig bron]

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[wysig | wysig bron]

'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:

Circular buffer - empty.svg

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):

Circular buffer - XX1XXXX.svg

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

Circular buffer - XX123XX.svg

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:

Circular buffer - XXXX3XX.svg

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

Circular buffer - 6789345.svg

'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:

Circular buffer - 6789AB5.svg

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:

Circular buffer - X789ABX.svg

Implementasie van die ringbuffer[wysig | wysig bron]

'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:

Circular buffer - XX123XX with pointers.svg

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

Circular buffer - 6789AB5 with pointers.svg

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.[1] 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.[2]

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.

Verwysings[wysig | wysig bron]

  1. Fout met oproep van Sjabloon:webaanhaling: Parameter url moet verskaf word, en verkieslik 'n titel ook.
  2. Fout met oproep van Sjabloon:webaanhaling: Parameter url moet verskaf word, en verkieslik 'n titel ook.

Eksterne skakels[wysig | wysig bron]