Búfer circular

En informática , un búfer circular , cola circular , búfer cíclico o búfer de anillo es una estructura de datos que utiliza un único búfer de tamaño fijo como si estuviera conectado de extremo a extremo. Esta estructura se presta fácilmente al almacenamiento en búfer de flujos de datos . ^{[ 1 ]} Hubo implementaciones tempranas de búferes circulares en hardware. ^{[ 2 ] [ 3 ]}

Un búfer circular comienza vacío y tiene una longitud fija. En el siguiente diagrama se muestra un búfer de 7 elementos:

Supongamos que el número 1 está escrito en el centro de un búfer circular (la ubicación inicial exacta no es importante en un búfer circular):

Supongamos entonces que se añaden dos elementos más al búfer circular — 2 y 3 — que se colocan después del 1:

Si se eliminan dos elementos, se eliminarán los dos valores más antiguos del búfer circular. Los búferes circulares utilizan la lógica FIFO ( primero en entrar, primero en salir ). En el ejemplo, 1 y 2 fueron los primeros en entrar al búfer circular, por lo que son los primeros en eliminarse, dejando 3 dentro del búfer. Cuando se eliminan elementos, solo el puntero de lectura se mueve al siguiente elemento. Los elementos eliminados permanecen en el búfer, a la espera de ser sobrescritos por nuevos elementos.

Si el búfer tiene 7 elementos, entonces está completamente lleno:

Una propiedad del búfer circular es que, cuando está lleno y se realiza una escritura posterior, comienza a sobrescribir los datos más antiguos. En el ejemplo actual, se agregan dos elementos más —A y B— que sobrescriben los elementos 3 y 4:

Alternativamente, las rutinas que gestionan el búfer podrían impedir la sobrescritura de los datos y devolver un error o generar una excepción . La decisión de si se sobrescriben o no los datos depende de la semántica de las rutinas del búfer o de la aplicación que utiliza el búfer circular.

Finalmente, si ahora se eliminan dos elementos, lo que se eliminaría no es A y B, sino 5 y 6 porque 5 y 6 son ahora los elementos más antiguos, lo que produce el búfer con:

La ventaja de un búfer circular radica en que no es necesario reorganizar sus elementos al consumirse uno. (Si se utilizara un búfer no circular, sería necesario desplazar todos los elementos al consumirse uno). En otras palabras, el búfer circular es idóneo como búfer FIFO ( primero en entrar, primero en salir ), mientras que un búfer estándar no circular es idóneo como búfer LIFO ( último en entrar, primero en salir ).

El almacenamiento en búfer circular es una buena estrategia de implementación para colas con tamaño máximo fijo. Si se adopta un tamaño máximo para la cola, el búfer circular es una implementación ideal, ya que todas las operaciones se realizan en tiempo constante. Sin embargo, expandir un búfer circular requiere desplazamiento de memoria, lo cual es relativamente costoso. Para colas de tamaño variable, puede ser preferible utilizar listas enlazadas .

En ciertas situaciones, se puede utilizar un búfer circular con sobrescritura, por ejemplo, en multimedia. Si el búfer se utiliza como búfer limitado en el problema productor-consumidor , probablemente sea conveniente que el productor (por ejemplo, un generador de audio) sobrescriba los datos antiguos si el consumidor (por ejemplo, la tarjeta de sonido ) no puede procesarlos a tiempo. Asimismo, la familia LZ77 de algoritmos de compresión de datos sin pérdidas parte de la premisa de que las cadenas vistas más recientemente en un flujo de datos tienen más probabilidades de aparecer pronto en dicho flujo. Las implementaciones almacenan los datos más recientes en un búfer circular.

Se puede implementar un búfer circular utilizando un puntero y cuatro enteros: ^{[ 4 ]}

• inicio del búfer en memoria
• capacidad de amortiguación (longitud)
• "Escribir en" índice del búfer (fin)
• "leer desde" índice del búfer (inicio)

Esta imagen muestra un búfer parcialmente lleno con una longitud de 7:

Esta imagen muestra un búfer lleno con cuatro elementos (del 1 al 4) que han sido sobrescritos:

Al principio, los índices de inicio y fin se establecen en 0. La operación de escritura circular del búfer escribe un elemento en la posición del índice de fin, y este índice se incrementa a la siguiente posición del búfer. La operación de lectura circular del búfer lee un elemento desde la posición del índice de inicio, y este índice se incrementa a la siguiente posición del búfer.

Los índices de inicio y fin por sí solos no son suficientes para distinguir entre el estado de búfer lleno o vacío al utilizar todas las ranuras del búfer, ^{[ 5 ]} pero sí pueden serlo si el búfer solo tiene un tamaño máximo en uso de Longitud − 1. ^{[ 6 ]} En este caso, el búfer está vacío si los índices de inicio y fin son iguales y lleno cuando el tamaño en uso es Longitud − 1. Otra solución es tener otro contador entero que se incremente en una operación de escritura y se decremente en una operación de lectura. Entonces, comprobar si está vacío significa comprobar que el contador sea igual a 0 y comprobar si está lleno significa comprobar que el contador sea igual a Longitud. ^{[ 7 ]}

El siguiente código fuente es una implementación en C junto con una prueba mínima. La función `put()` coloca un elemento en el búfer, la función `get()` obtiene un elemento del búfer. Ambas funciones tienen en cuenta la capacidad del búfer  :

#include <stdio.h>enum { N = 10 }; // tamaño del búfer circularint buffer [ N ]; // nota: solo se pueden almacenar (N - 1) elementos a la vez int writeIndx = 0 ; int readIndx = 0 ;int put ( int item ) { if (( writeIndx + 1 ) % N == readIndx ) { // El búfer está lleno, evitar desbordamiento return 0 ; } buffer [ writeIndx ] = item ; writeIndx = ( writeIndx + 1 ) % N ; return 1 ; }int obtener ( int * valor ) { if ( readIndx == writeIndx ) { // el búfer está vacío return 0 ; }* valor = buffer [ readIndx ]; readIndx = ( readIndx + 1 ) % N ; return 1 ; }int main () { // prueba de búfer circular int valor = 1001 ; while ( put ( valor ++ )); while ( get ( & valor )) printf ( "leído %d \n " , valor ); return 0 ; }

Una implementación de búfer circular puede optimizarse asignando el búfer subyacente a dos regiones contiguas de memoria virtual . ^{[ 8 ]} (Naturalmente, la longitud del búfer subyacente debe ser entonces un múltiplo del tamaño de página del sistema ). La lectura y escritura en el búfer circular pueden realizarse con mayor eficiencia mediante acceso directo a memoria; aquellos accesos que se encuentren más allá del final de la primera región de memoria virtual se reiniciarán automáticamente al principio del búfer subyacente. Cuando el desplazamiento de lectura avanza a la segunda región de memoria virtual, ambos desplazamientos (lectura y escritura) se decrementan en la longitud del búfer subyacente.

Quizás la versión más común del búfer circular utiliza bytes de 8 bits como elementos.

Algunas implementaciones del búfer circular utilizan elementos de longitud fija mayores que 8 bits: enteros de 16 bits para búferes de audio, celdas ATM de 53 bytes para búferes de telecomunicaciones, etc. Cada elemento es contiguo y tiene la alineación de datos correcta , por lo que el software que lee y escribe estos valores puede ser más rápido que el software que maneja valores no contiguos y no alineados.

El almacenamiento en búfer tipo ping-pong puede considerarse un búfer circular muy especializado con exactamente dos elementos grandes de longitud fija.

El búfer bipartito (bip buffer) es muy similar a un búfer circular, con la diferencia de que siempre devuelve bloques contiguos de longitud variable. Esto ofrece prácticamente todas las ventajas de eficiencia de un búfer circular, manteniendo la capacidad de que el búfer se utilice en API que solo aceptan bloques contiguos. ^{[ 9 ]}

Los búferes circulares comprimidos de tamaño fijo utilizan una estrategia de indexación alternativa basada en la teoría elemental de números para mantener una representación comprimida de tamaño fijo de toda la secuencia de datos. ^{[ 10 ]}

• CircularBuffer en el repositorio de patrones de Portland
• Aumentar:

  Contenedor de búfer circular con plantilla : circular_buffer/base.hpp

  Cola limitada sincronizada : sync_bounded_queue.hpp

• CB en el kernel de Linux
• CB en DSP
• Cola circular en C. Archivado el 29/10/2018 en Wayback Machine.