c# - ¿Cuáles son los usos del búfer circular?
.net data-structures (6)
He utilizado un búfer de anillo en código multi-hilo. Básicamente, si todas las ranuras están llenas, los productores tienen que esperar. Los consumidores simplemente procesan los artículos en las ranuras que están "llenos".
Aquí hay un hilo que empecé en él. Tiene algunos buenos consejos sobre la implementación.
¿Cuáles son algunos de los usos del buffer circular?
¿Cuáles son los beneficios de usar un buffer circular?
¿Es una alternativa a la lista de enlaces dobles?
Lo he usado como una forma fácil de implementar la programación de round-robin. Básicamente, tenía un montón de objetos diferentes que pueden producir un valor que un consumidor podría procesar. Metí a todos los productores en un anillo y les pregunté a cada uno por turno.
Lo he usado para un registro en memoria con un tamaño restringido. Por ejemplo, la aplicación escribiría entradas de registro al procesar las solicitudes de los usuarios. Cada vez que se producía una excepción (que sería perjudicial para el procesamiento), los registros que actualmente se encuentran en la memoria se vuelcan junto con ella.
El beneficio de un búfer circular es que no necesita infinitas cantidades de memoria, ya que las entradas más antiguas se anulan automáticamente. El "desafío" es que necesita encontrar un tamaño adecuado para su caso de uso. En el ejemplo anterior, sería muy desafortunado que el registro con la información más importante sobre la excepción ya se hubiera anulado.
Algunos sistemas / aplicaciones tienen herramientas para permitirle extraer el contenido actual del búfer a pedido, y no solo cuando se extraerá automáticamente (si es que lo hace).
Creo que el registro de tensión de ETW y CLR, entre muchos otros kernel del sistema o rastreo / registro de alto rendimiento, se implementan de esa manera.
El concepto de usar dichos buffers para el rastreo / registro en memoria es bastante común (por no decir que este es el único uso, ciertamente no), porque es mucho más rápido que los registros escritos en un archivo / base de datos que nunca podría ser. interesado en menos que se produzca un error. Y en una nota relacionada, conserva espacio en el disco duro.
Los buffers circulares son buenos para los flujos de datos en serie en sistemas integrados. Los microcontroladores a menudo tienen un UART para manejar un byte serie que ingresa, estos deben almacenarse en orden y tratarse más tarde (los bytes a menudo vienen a una velocidad más rápida de la que pueden manejarse).
El búfer divide efectivamente la respuesta crítica de tiempo requerida (cuando los bytes entran, en microsegundos) a la respuesta no crítica de tiempo a todo el mensaje (por ejemplo, mostrando el mensaje que llegó, en milisegundos), por ejemplo:
1) Al recibir un byte, el UART puede generar una interrupción a la que el software responde tomando rápidamente el byte recibido y lo empuja hacia el final del búfer.
2) Las rutinas de software de fondo pueden entonces verificar regularmente si el búfer tiene algo aún y vaciarlo según sea necesario.
Como el tamaño del búfer circular se puede definir antes de la compilación, el tamaño se limita. Esto ayuda a mejorar la eficiencia del espacio y debería eliminar la corrupción de la memoria en un intercambio de cuántos bytes se pueden recibir antes de que los datos comiencen a perderse.
Sé que esto es hacer trampa, pero Wikipedia tiene una muy buena explicación.
http://en.wikipedia.org/wiki/Circular_buffer
Un búfer circular, un búfer cíclico o un búfer de anillo es una estructura de datos que utiliza un búfer de tamaño fijo como si estuviera conectado de extremo a extremo. Esta estructura se presta fácilmente al almacenamiento intermedio de flujos de datos.
Un ejemplo que podría utilizar un búfer circular de sobrescritura es con multimedia. Si el búfer se usa como el búfer acotado en el problema productor-consumidor, entonces probablemente 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 mantenerse momentáneamente . Otro ejemplo es el método de síntesis de guía de ondas digital que utiliza amortiguadores circulares para simular de manera eficiente el sonido de cuerdas vibratorias o instrumentos de viento.
Con respecto a las listas de enlaces dobles, me imagino que realmente depende de para qué se utiliza la lista ... La implementación de búferes circulares parece ser más compleja, por favor (nuevamente) consulte la página wiki; esto explica la implementación, consideraciones, etc. y también muestra código de ejemplo.
Gracias neil
Un búfer circular es un buen mecanismo para mantener de manera ordenada una lista de valores / elementos deslizante / en movimiento. Un ejemplo podría ser mantener un promedio móvil de los últimos N elementos. Supongamos que desea realizar un seguimiento del costo promedio de las últimas 100 operaciones de cálculo de algún valor. Para hacer esto, deberá eliminar el costo más antiguo y agregar el costo más reciente.
Sin un búfer circular, un mecanismo costoso para hacer esto (estilo C) sería tener una matriz de 100 elementos. Cada vez que se calcula un nuevo costo, puede eliminar los 99 elementos y colocar el nuevo en la última posición. Esto obviamente es costoso. Usando una idea de búfer circular, simplemente rastrearías el "final" del búfer (posición 0-99). Marcaría la posición del elemento de costo más antiguo (o el más nuevo ... el que elija). Después de leer el valor anterior (para actualizar el promedio de ejecución), lo reemplaza con el valor más reciente e incrementa la posición del búfer (si está en 99, lo vuelve a configurar en 0 ... por lo tanto, la parte circular).
Compararlo con una lista doblemente enlazada realmente no tiene sentido. Un búfer circular ciertamente podría implementarse con una lista doblemente enlazada (o incluso una lista enlazada individualmente). Pero compararlos es un poco como comparar manzanas y naranjas, por así decirlo.