Buffer circular

Un buffer circular, buffer cíclico o buffer de anillo es una estructura de datos que utiliza un buffer único o array ordinario y que adopta su nombre por la forma en que se ponen o sacan sus elementos. Estos buffers son de tamaño fijo, internamente es como si estuviera conectado de extremo a extremo.

Un ejemplo de uso de un buffer circular de escritura puede ser en multimedia. Si este tipo de buffer es usado como un buffer delimitador en el problema del productor-consumidor, es probablemente deseado por el productor (por ejemplo, un generador de audio) sobrescribir los datos antiguos si el consumidor (como ser la tarjeta de audio) no está momentáneamente disponible para un mantenimiento. Otro ejemplo es el método de síntesis de guías de ondas digitales, el cual usa buffers circulares para simular de forma eficiente el sonido de la vibración de los instrumentos de cuerda o viento. El atributo preciado de los buffers circulares es que no se tiene la necesidad de mover los elementos por la cola en el momento de que uno de ellos es consumido. Por otra parte, si se usara un buffer no circular sería necesario modificar todos los elementos cuando uno sea consumido. En otras palabras, el buffer circular es bien visto como un buffer FIFO (primero en entrar es el primero en salir); mientras que un buffer no circular representaría un buffer LIFO (último en entrar es el primero en salir). Una buena estrategia de implementación para una cola con tamaño máximo es mediante el uso de buffers circulares; en este caso todas las operaciones de la cola se realizan en tiempo constante. Sin embargo, expandir un buffer circular requiere cambio de memoria, lo cual es costoso.

Un buffer circular trabaja básicamente con dos índices para acceder a los elementos del buffer, que aquí llamaremos Inpointer y Outpointer. Ambos índices tienen avance incremental y cíclico, es decir, se incrementan de uno en uno y luego de apuntar al último elemento del buffer vuelven a apuntar al primero.

Al inicio los dos índices apuntan al primer elemento del buffer. Veamos cómo y cuándo se incrementan:

Estos buffers tienen un comportamiento FIFO ("First In - First Out", "Primero en entrar - primero en salir").

Una consecuencia de la memoria intermedia circular es que cuando está lleno y se realiza la posterior escritura, entonces comienza a sobrescribir los datos más antiguos.

Para saber si en el buffer hay espacio para meter más datos o si hay al menos un dato para sacar, se debe usar la diferencia entre las posiciones de los punteros. Otra posible opción es utilizar una variable adicional que se incremente con cada dato ingresado y se decremente con cada dato extraído.

Un buffer circular comienza vacío y con un tamaño predefinido. Por ejemplo, este es un buffer de 7 elementos:

Asuma que un 1 es escrito en el medio del buffer (la locación exacta no importa en un buffer circular):

Luego, asuma que dos elementos más son añadidos — 2 & 3 — los cuales quedan añadidos después del 1:

Si dos elementos son eliminados del buffer, los valores más viejos dentro del buffer son borrados. Los dos elementos borrados, en este caso, son 1 & 2; quedando el buffer con solamente un 3:

Si el buffer tiene 7 elementos se encuentra lleno:

Una consecuencia de los buffers circulares es que cuando se encuentra lleno y se realiza una nueva escritura, se comienza a sobrescribir los datos antiguos. En este caso, se agregan dos elementos más — A & B — y sobrescriben el 3 & 4:

Como una alternativa, se puede hace que las rutinas que administran el buffer no permitan que los datos se sobrescriban y retornen un error o una excepción.

Finalmente, si dos elementos son borrados ahora, se va a retornar 5 & 6 y no 3 & 4, dado que A & B sobrescribió el 3 & 4:

Generalmente, un buffer circular requiere tres punteros:

Como alternativa para lenguajes que no soportan punteros, se puede utilizar un buffer de tamaño fijo, con dos enteros que contengan los índices de comienzo y fin de los datos válidos.

Existen varias maneras de etiquetar los punteros y la semántica puede variar; una manera de hacerlo es la siguiente:

Esta imagen muestra un buffer parcialmente lleno:

Esta imagen muestra un buffer completo con dos elementos que han sido sobrescritos:

Una nota sobre la segunda imagen es que después de que cada elemento es sobrescrito el puntero de comienzo es incrementado también.

Un buffer circular puede presentar ciertos problemas que hay que saber controlar. En concreto las situaciones problemáticas si no son controladas son en el caso de que el buffer se encuentre totalmente vacío o totalmente lleno, en estos casos el índice de escritura coincidirá con el de lectura, lo que provocará fallos tales como que se lea información incorrecta del buffer o que se escriba información destruyendo información útil del buffer, provocando que ésta no pueda ser leída.

Posibles métodos para controlar estos problemas:

Este método consiste en permitir realizar escrituras en el buffer hasta que el índice de escritura llegue a la posición anterior del índice de lectura, lo mismo ocurre para la operación de lectura.

Las Ventajas son:

Las desventajas son:

Un ejemplo de implementación en C: (Mantiene una ranura abierta)

Un ejemplo de implementación en C: (Usando todas las ranuras)

Esta técnica consiste en mantener un contador de llenado que se incrementa con cada operación de escritura y se decrementa en cada operación de lectura, esto permite conocer en todo momento el estado de uso del buffer, dándonos la posibilidad de no permitir la lectura si el contador de llenado esta a cero y de no permitir la escritura si el contador de llenado esta en el valor de máxima capacidad del buffer.

Este método consiste en utilizar dos contadores, uno para lectura y otro para escritura, dichos contadores se irán incrementando por cada operación correspondiente, de forma que cuando realizamos una escritura aumenta el contador de escritura y similar para el contador de lectura. Manteniendo este sistema, podemos comprobar el estado en el que se encuentra el buffer en cualquier momento.

POR EJEMPLO: el buffer podría estar en los siguientes estados:

Una implementación del buffer circular puede ser optimizada asignando al buffer dos regiones contiguas de memoria virtual. (Naturalmente, el tamaño del buffer debe ser múltiplo del tamaño de página del sistema.) La lectura y escritura en el buffer circular debe realizarse con gran eficiencia en cuanto al acceso directo a memoria.