Tampó circular

Un anell que mostra, conceptualment, un buffer circular. Això mostra visualment que el buffer no té un final real i que es pot circular al voltant del mateix. De fet, com que la memòria mai es crea físicament com un anell, es sol utilitzar una representació lineal com es fa a continuació.

En informàtica, un tampó circular, buffer circular o buffer en anell, és una estructura de dades que utilitza un buffer únic i de mida fixa com si estigués connectat d'extrem a extrem el cap amb la cua. Aquesta estructura és molt pràctica per a ser emprada com a buffer de flux d'entrada/sortida de dades. Hi va haver implementacions primitives de buffer circular fetes amb components discrets i circuits integrats.

Visió general

Un buffer circular de teclat de 24 bytes. Quan el punter d'escriptura està a prop d'arribar al punter de lectura — perquè el microprocessador no respon — es deixen d'enregistrar les pulsacions de tecla en el buffer En alguns ordinadors pot sonar un bip.

Un buffer circular comença primer buit i té una longitud determinada. Al diagrama següent hi ha un buffer de 7 elements:

Suposem que 1 està escrit al centre d'un buffer circular (la ubicació inicial exacta no és important en un buffer circular):

A continuació, suposa que s'afegeixen dos elements més a el buffer circular — 2 i 3 — que es posen després de l'1:

Si s'eliminen dos elements, s'eliminaran els dos valors més antics dins del buffer circular. Els buffers circulars utilitzen la lògica FIFO (primer en entrar, primer en sortir). A l'exemple, 1 i 2 van ser els primers a entrar al buffer circular, són els primers a eliminar-se, deixant 3 dins del buffer.

Si el buffer té 7 elements, llavors està completament ple:

Una propietat del buffer circular és que quan està ple i es realitza una escriptura posterior, comença a sobreescriure les dades més antigues. A l'exemple actual, s'afegeixen dos elements més — A i B — i sobreescriuen els 3 i 4:

Alternativament, les rutines que gestionen el buffer podrien evitar sobreescriure les dades i retornar un error o generar una excepció . Si les dades es sobreescriuen o no, depèn de la semàntica de les rutines de memòria intermèdia o de l'aplicació que utilitza el buffer circular.

Finalment, si ara s'eliminen dos elements, el que es retornaria no és 3 i 4 sinó 5 i 6 perquè ara 5 i 6 són els elements més antics, donant lloc al buffer amb:

Usos

La propietat útil d'un buffer circular és que no cal que els seus elements es barregin quan se'n consumeix un. (Si s'utilitzi un buffer no circular, caldria desplaçar tots els elements quan es consumeix un. ) En altres paraules, el buffer circular s'adapta bé com a buffer FIFO (primer en entrar, primer en sortir ), mentre que un buffer estàndard no circular s'adapta bé com a buffer LIFO (última entrada, primera sortida ).

el buffer circular és una bona estratègia d'implementació per a un buffer que té una mida màxima fixada. Si s'adopta una mida màxima per a un buffer, llavors un buffer circular és una implementació completament ideal; totes les operacions del buffer són de temps constant. Tanmateix, expandir un buffer circular requereix canviar la memòria, que és relativament costós. Per a l'expansió arbitrària de les cues, es pot preferir un enfocament de llista enllaçada.

En algunes situacions, es pot utilitzar la sobreescriptura del buffer circular, per exemple en multimèdia. Si el buffer s'utilitza com a memòria intermèdia limitada en el problema productor-consumidor, probablement es desitgi que el productor (per exemple, un generador d'àudio) sobreescrigui dades antigues si el consumidor (per exemple, la targeta de so) no pot mantenir-se al dia momentàniament. . A més, la família LZ77 d'algoritmes de compressió de dades sense pèrdues funciona en el supòsit que és més probable que les cadenes vistes més recentment en un flux de dades es produeixin aviat al flux. Les implementacions emmagatzemen les dades més recents en el buffer circular.

Mecànica del tampó circular

Implementació del buffer circular a la Hardware patent U.S.A 3979733, fig4

Es pot implementar un buffer circular mitjançant un punter i tres nombres enters:

• inici del buffer en memòria
• capacitat del buffer (longitud)
• escriure l'índex del buffer (final)
• llegir des de l'índex del buffer (inici)

Aquesta imatge mostra un buffer parcialment ple amb Longitud = 7:

Aquesta imatge mostra un buffer complet amb quatre elements (números de l'1 al 4) que s'han sobreescrit:

Al principi, els índexs acaben i comencen s'estableixen a 0. L'operació d'escriptura del buffer circular escriu un element a la posició de l'índex final i l'índex final s'incrementa a la següent posició del buffer. L'operació de lectura del buffer circular llegeix un element des de la posició de l'índex inicial i l'índex inicial s'incrementa fins a la següent posició del buffer.

Els índexs inicial i final no són suficients per indicar l'estat del buffer plena o buida alhora que s'utilitzen totes les ranures del buffer, però sí si el buffer només té una mida màxima en ús de Longitud - 1. En aquest cas, el buffer està buida si els índexs inicial i final són iguals i plens quan la mida en ús és Longitud - 1. Una altra solució és tenir un altre recompte d'enters que s'incrementi en una operació d'escriptura i disminueixi en una operació de lectura. Aleshores, comprovar el buit significa que el recompte de proves és igual a 0 i comprovar la plenitud significa que el recompte de proves és igual a la longitud.

El següent codi font és una implementació en llenguatge C juntament amb una prova mínima. La funció put() posa un element al buffer, la funció get() obté un element del buffer. Ambdues funcions tenen cura de la capacitat del buffer :

#include <stdio.h>

enum { N = 10 }; // N elements of the circular buffer

int buffer [N]; // Note that N-1 is the actual capacity, see put function
int writeIndx = 0;
int readIndx = 0;

int put (int item) 
{
 if ((writeIndx + 1) % N == readIndx)
 {
 // buffer is full, avoid overflow
 return 0;
 }
 buffer[writeIndx] = item;
 writeIndx = (writeIndx + 1) % N;
 return 1;
}

int get (int * value) 
{
 if (readIndx == writeIndx)
 {
 // buffer is empty
 return 0;
 }

 *value = buffer[readIndx];
 readIndx = (readIndx + 1) % N;
 return 1;
}

int main ()
{
 // test circular buffer
 int value = 1001;
 while (put (value ++));
 while (get (& value))
 printf ("read %d\n", value);
 return 0;
}

Optimització

Es pot optimitzar una implementació del buffer circular assignant el buffer subjacent a dues regions contigües de memòria virtual. (Naturalment, la longitud del buffer subjacent ha de ser igual a algun múltiple de la mida de la pàgina del sistema . ) La lectura i l'escriptura des del buffer circular es poden dur a terme amb més eficiència mitjançant l'accés directe a la memòria; aquells accessos que queden més enllà del final de la primera regió de memòria virtual s'ajustaran automàticament al començament del buffer subjacent. Quan el desplaçament de lectura s'avança a la segona regió de memòria virtual, ambdós desplaçaments (lectura i escriptura) disminueixen per la longitud del buffer subjacent.

Element de longitud fixa i buffer circular de blocs contigus

Potser la versió més generalitzada del buffer circular utilitza bytes de 8 bits com elements gestionats.

Algunes implementacions del buffer circular utilitzen elements de longitud fixa que són més grans que els bytes de 8 bits: enters de 16 bits per als buffers d'àudio, cèl·lules ATM de 53 bytes per als buffers de telecomunicacions, etc. Cada element és contigu i té l'alineació de dades correcta, de manera que el programari de lectura i escriptura d'aquests valors pot ser més ràpid que el programari que gestiona valors no contigus i no alineats.

El buffer de ping-pong es pot considerar un buffer circular molt especialitzat amb exactament dos grans elements de longitud fixa.

El buffer bip (búfer bipartit) és molt semblant a un buffer circular, excepte que sempre retorna blocs contigus que poden ser de longitud variable. Això ofereix gairebé tots els avantatges d'eficiència d'un buffer circular, alhora que manté la capacitat d'utilitzar el buffer en API que només accepten blocs contigus.

Els buffers circulars comprimits de mida fixa utilitzen una estratègia d'indexació alternativa basada en la teoria elemental de nombres per mantenir una representació comprimida de mida fixa de tota la seqüència de dades.