En informática , un búfer circular , cola circular , búfer cíclico o búfer en anillo es una estructura de datos que utiliza un único búfer de tamaño fijo como si estuviera conectado de un extremo a otro. 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 primero comienza vacío y tiene una longitud establecida. En el siguiente diagrama se muestra un búfer de 7 elementos:
Supongamos que 1 está escrito en el centro de un búfer circular (la ubicación inicial exacta no es importante en un búfer circular):
Luego suponga que se agregan dos elementos más al búfer 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 buffers 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 ser eliminados, 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 el 3 y el 4:
Alternativamente, las rutinas que administran el búfer podrían evitar la sobrescritura de los datos y devolver un error o generar una excepción . Si los datos se sobrescriben o no 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, entonces 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 produce el búfer con:
La propiedad útil de un buffer circular es que no necesita que sus elementos se mezclen cuando se consume uno. (Si se utilizara un búfer no circular, sería necesario desplazar todos los elementos cuando se consuma uno). En otras palabras, el búfer circular es adecuado como búfer FIFO ( primero en entrar, primero en salir ), mientras que un búfer estándar, El búfer no circular es muy adecuado como búfer 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 buffer circular es una implementación completamente ideal; Todas las operaciones de cola son de tiempo constante. Sin embargo, expandir un buffer circular requiere cambiar la memoria, lo cual es comparativamente costoso. Para colas que se expanden arbitrariamente, puede preferirse un enfoque de lista vinculada .
En algunas situaciones, se puede utilizar la sobrescritura del buffer circular, por ejemplo en multimedia. Si el búfer se utiliza como búfer limitado en el problema productor-consumidor , entonces probablemente sea deseable 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érdidas opera bajo el supuesto de que es más probable que las cadenas vistas más recientemente en un flujo de datos aparezcan pronto en el 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 tres números enteros: [4]
Esta imagen muestra un búfer parcialmente lleno con Longitud = 7:
Esta imagen muestra un búfer lleno con cuatro elementos (números del 1 al 4) que se han sobrescrito:
Al principio, los índices final e inicio se establecen en 0. La operación de escritura del búfer circular escribe un elemento en la posición final del índice y el índice final se incrementa hasta la siguiente posición del búfer. La operación de lectura del búfer circular lee un elemento desde la posición del índice inicial y el índice inicial 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 del búfer lleno o vacío al mismo tiempo que se utilizan 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 En este caso, el búfer está vacío si los índices inicial y final son iguales y lleno cuando el tamaño en uso es Longitud - 1. Otra solución es tener otro recuento de enteros que se incrementa en una operación de escritura y se reduce en una operación de lectura. Luego, verificar el vacío significa que el recuento de pruebas es igual a 0 y verificar que 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 buffer:
#incluir <stdio.h> enumeración { N = 10 }; // N elementos del buffer circular búfer int [ norte ]; int escribirIndx = 0 ; int readIndx = 0 ; int put ( int item ) { if (( writeIndx + 1 ) % N == readIndx ) { // el búfer está lleno, evita el desbordamiento return 0 ; } buffer [ writeIndx ] = elemento ; escribirIndx = ( escribirIndx + 1 ) % N ; devolver 1 ; } int get ( int * valor ) { if ( readIndx == writeIndx ) { // el búfer está vacío return 0 ; } * valor = búfer [ readIndx ]; índice de lectura = ( índice de lectura + 1 ) % N ; devolver 1 ; } int main () { // prueba el búfer circular int valor = 1001 ; mientras ( poner ( valor ++ )); while ( obtener ( y valor )) printf ( "leer %d \n " , valor ); devolver 0 ; } Una implementación de búfer circular se puede optimizar asignando el búfer subyacente a dos regiones contiguas de memoria virtual . [8] [ disputado ] (Naturalmente, la longitud del buffer subyacente debe entonces ser igual a algún múltiplo del tamaño de página del sistema .) La lectura y escritura en el buffer circular se puede llevar a cabo con mayor eficiencia mediante el acceso directo a la memoria; aquellos accesos que caen más allá del final de la primera región de memoria virtual se ajustará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) disminuyen 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 que son mayores que bytes de 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 tanto, 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 buffer de ping-pong puede considerarse un buffer circular muy especializado con exactamente dos elementos grandes de longitud fija.
El búfer bip (búfer bipartito) 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 y, al mismo tiempo, mantiene la capacidad de utilizar el búfer 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]