Tampó circular
En informàtica, un tampó circular, buffer circular o buffer en anell, és una estructura de dades que utilitza un buffer única 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.[1] Hi va haver implementacions primitives de buffer circular fetes amb components discrets i circuits integrats.[2][3]
Visió general[modifica]
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[modifica]
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[modifica]
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:[4]
- 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,[5] però sí si el buffer només té una mida màxima en ús de Longitud - 1.[6] 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.[7]
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 :[8]
#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ó[modifica]
Es pot optimitzar una implementació del buffer circular assignant el buffer subjacent a dues regions contigües de memòria virtual .[9] (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[modifica]
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.[10]
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.[11]
Referències[modifica]
- ↑ .
- ↑ Hartl, Johann. «Impulswiederholer - Telephone Exchange (video)». Youtube. [Consulta: 15 desembre 2021].
- ↑ Fraser, Alexander Gibson. «US patent 3979733 Digital data communications system packet switch». US States Patent. [Consulta: 15 desembre 2021].
- ↑ Liu, Z.; Wu, F.; Das, S.K.. Wireless Algorithms, Systems, and Applications: 16th International Conference, WASA 2021, Nanjing, China, June 25–27, 2021, Proceedings, Part II. Springer International Publishing, 2021, p. 117. ISBN 978-3-030-86130-8 [Consulta: 4 setembre 2023].
- ↑ Chandrasekaran, Siddharth. «Implementing Circular/Ring Buffer in Embedded C». Embed Journal. EmbedJournal Team, 16-05-2014. Arxivat de l'original el 11 febrer 2017. [Consulta: 14 agost 2017].
- ↑ Circular buffers kernel.org
- ↑ Morin, Pat. «ArrayQueue: An Array-Based Queue». Open Data Structures (in pseudocode). Arxivat de l'original el 31 agost 2015. [Consulta: 7 novembre 2015].
- ↑ «Circular queue in C», 30-08-2016. Arxivat de l'original el 2022-01-21. [Consulta: 4 setembre 2023].
- ↑ Mike Ash. «mikeash.com: Friday Q&A 2012-02-17: Ring Buffers and Mirrored Memory: Part II». mikeash.com, 17-02-2012. Arxivat de l'original el 2019-01-11. [Consulta: 10 gener 2019].
- ↑ Simon Cooke (2003), "The Bip Buffer - The Circular Buffer with a Twist"
- ↑ Gunther, John C. ACM Transactions on Mathematical Software, 40, 2, març 2014, pàg. 1–12. DOI: 10.1145/2559995.