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 para almacenar en búfer flujos de datos . [1] Hubo implementaciones tempranas de búfer circular en hardware. [2] [3]
Un buffer circular comienza vacío y tiene una longitud determinada. En el diagrama siguiente se muestra un buffer de 7 elementos:
Supongamos que 1 está escrito en el centro de un buffer circular (la ubicación de inicio exacta no es importante en un buffer circular):
Supongamos entonces que se añaden dos elementos más al buffer circular (2 y 3), que se colocan después de 1:
Si se eliminan dos elementos, se eliminarán los dos valores más antiguos dentro 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 ingresar al búfer circular, son los primeros en eliminarse, dejando 3 dentro del búfer.
Si el buffer 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) y sobrescriben los elementos 3 y 4:
Como alternativa, las rutinas que administran el búfer podrían evitar la sobrescritura de los datos y devolver un error o generar una excepción . La sobrescritura de los datos depende de la semántica de las rutinas del búfer o de la aplicación que utilice el búfer circular.
Finalmente, si ahora se eliminan dos elementos, lo que se devolvería no sería 3 y 4 (o más bien ahora A y B), sino 5 y 6, porque 5 y 6 son ahora los elementos más antiguos, lo que genera el búfer con:
La propiedad útil de un buffer circular es que no necesita que sus elementos se reordenen cuando se consume uno. (Si se utilizara un buffer no circular, sería necesario cambiar todos los elementos cuando se consume uno). En otras palabras, el buffer circular es adecuado como un buffer FIFO ( primero en entrar, primero en salir ), mientras que un buffer estándar, no circular, es adecuado como un buffer LIFO ( último en entrar, primero en salir ).
El almacenamiento en búfer circular es una buena estrategia de implementación para una cola que tiene un tamaño máximo fijo. Si se adopta un tamaño máximo para una cola, entonces un búfer circular es una implementación completamente ideal; todas las operaciones de cola son de tiempo constante. Sin embargo, expandir un búfer circular requiere cambiar la memoria, lo que es comparativamente costoso. Para colas que se expanden arbitrariamente, puede ser preferible un enfoque de lista enlazada .
En algunas situaciones, se puede utilizar la sobrescritura de un búfer circular, por ejemplo, en multimedia. Si el búfer se utiliza como búfer limitado en el problema productor-consumidor , entonces es probable que se desee que el productor (por ejemplo, un generador de audio) sobrescriba los datos antiguos si el consumidor (por ejemplo, la tarjeta de sonido ) no puede mantener el ritmo momentáneamente. Además, la familia LZ77 de algoritmos de compresión de datos sin pérdida opera bajo el supuesto de que las cadenas vistas más recientemente en un flujo de datos tienen más probabilidades de aparecer pronto en el flujo. Las implementaciones almacenan los datos más recientes en un búfer circular.
Se puede implementar un buffer circular usando un puntero y tres números enteros: [4]
Esta imagen muestra un buffer parcialmente lleno con longitud = 7:
Esta imagen muestra un buffer lleno con cuatro elementos (números 1 a 4) que han sido sobrescritos:
Al principio, los índices de inicio y fin se establecen en 0. La operación de escritura de búfer circular escribe un elemento en la posición del índice de fin y el índice de fin se incrementa hasta la siguiente posición del búfer. La operación de lectura de búfer circular lee un elemento desde la posición del índice de inicio y el índice de inicio se incrementa hasta la siguiente posición del búfer.
Los índices de inicio y fin por sí solos no son suficientes para distinguir entre el estado lleno o vacío del búfer mientras se utilizan también todas las ranuras del búfer, [5] pero 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 está lleno cuando el tamaño en uso es Longitud - 1. Otra solución es tener otro recuento entero que se incrementa en una operación de escritura y se decrementa en una operación de lectura. Entonces, comprobar si está vacío significa que el recuento de pruebas es igual a 0 y comprobar si está lleno significa que el recuento de pruebas es 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 se ocupan de la capacidad del búfer:
#incluir <stdio.h> enum { N = 10 }; // tamaño del buffer circular int buffer [ N ]; // nota: solo se pueden almacenar (N - 1) elementos en un momento dado int writeIndx = 0 ; int readIndx = 0 ; int put ( int item ) { if (( writeIndx + 1 ) % N == readIndx ) { // el buffer está lleno, evitar desbordamiento return 0 ; } buffer [ writeIndx ] = item ; writeIndx = ( writeIndx + 1 ) % N ; return 1 ; } int get ( int * valor ) { if ( readIndx == writeIndx ) { // el buffer está vacío devuelve 0 ; } * valor = buffer [ readIndx ]; readIndx = ( readIndx + 1 ) % N ; devolver 1 ; } int main () { // prueba el buffer circular int valor = 1001 ; mientras ( poner ( valor ++ )); mientras ( obtener ( & valor )) printf ( "leer %d \n " , valor ); devolver 0 ; } Una implementación de búfer circular puede optimizarse asignando el búfer subyacente a dos regiones contiguas de memoria virtual . [8] [ disputado – discutir ] (Naturalmente, la longitud del búfer subyacente debe ser igual a algún múltiplo del tamaño de página del sistema ). La lectura y escritura en el búfer circular se puede realizar con mayor eficiencia mediante acceso directo a la memoria; aquellos accesos que caen más allá del final de la primera región de memoria virtual se envolverán automáticamente al comienzo del búfer subyacente. Cuando el desplazamiento de lectura avanza hacia la segunda región de memoria virtual, ambos desplazamientos (lectura y escritura) se reducen por la longitud del búfer subyacente.
Quizás la versión más común del buffer circular utiliza bytes de 8 bits como elementos.
Algunas implementaciones del búfer circular utilizan elementos de longitud fija que son más grandes que bytes de 8 bits: números 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 la lectura y escritura de estos valores por parte del software puede ser más rápida que el software que maneja valores no contiguos y no alineados.
El buffering de ping-pong puede considerarse un buffer 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, excepto que siempre devuelve bloques contiguos que pueden tener una longitud variable. Esto ofrece casi todas las ventajas de eficiencia de un búfer circular, al tiempo que mantiene la capacidad de que el búfer se utilice en API que solo aceptan bloques contiguos. [9]
Los buffers circulares comprimidos de tamaño fijo utilizan una estrategia de indexación alternativa basada en la teoría de números elemental para mantener una representación comprimida de tamaño fijo de toda la secuencia de datos. [10]