stringtranslate.com

Amortiguador circular

Un anillo que muestra, conceptualmente, un búfer circular. Esto muestra visualmente que el búfer no tiene un final real y que puede dar vueltas alrededor del búfer. Sin embargo, dado que la memoria nunca se crea físicamente como un anillo, generalmente se utiliza una representación lineal como se muestra a continuación.

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]

Descripción general

Un búfer circular de teclado de 24 bytes. Cuando el puntero de escritura está a punto de alcanzar el puntero de lectura (debido a que el microprocesador no responde), el búfer deja de registrar las pulsaciones de teclas. En algunas computadoras se escucharía un pitido.

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 eliminarí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 da como resultado el búfer con:

Usos

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.

Mecánica de amortiguación circular

Implementación de buffer circular en hardware, patente estadounidense 3979733, fig. 4

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 ; }                    

Mejoramiento

Una implementación de búfer circular puede optimizarse asignando el búfer subyacente a dos regiones contiguas de memoria virtual . [8] [ disputadodiscutir ] (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.

Buffer circular de elementos de longitud fija y bloques contiguos

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]

Referencias

  1. ^ Arpaci-Dusseau, Remzi H.; Arpaci-Dusseau, Andrea C. (2014), Sistemas operativos: tres piezas sencillas [Capítulo: Variables de condición, figura 30.13] (PDF) , Libros de Arpaci-Dusseau
  2. ^ Hartl, Johann (17 de octubre de 2011). "Impulswiederholer - Central telefónica (vídeo)". Youtube . Consultado el 15 de diciembre de 2021 .
  3. ^ Fraser, Alexander Gibson. «Patente estadounidense 3979733 Conmutador de paquetes de sistemas de comunicaciones de datos digitales». Patente de Estados Unidos . Consultado el 15 de diciembre de 2021 .
  4. ^ Liu, Z.; Wu, F.; Das, SK (2021). Algoritmos, sistemas y aplicaciones inalámbricas: 16.ª conferencia internacional, WASA 2021, Nanjing, China, del 25 al 27 de junio de 2021, Actas, Parte II. Apuntes de conferencias sobre informática. Springer International Publishing. pág. 117. ISBN 978-3-030-86130-8. Consultado el 4 de septiembre de 2023 .
  5. ^ Chandrasekaran, Siddharth (16 de mayo de 2014). "Implementación de un búfer circular/de anillo en C embebido". Embed Journal . Equipo de EmbedJournal. Archivado desde el original el 11 de febrero de 2017 . Consultado el 14 de agosto de 2017 .
  6. ^ Búferes circulares kernel.org
  7. ^ Morin, Pat . «ArrayQueue: una cola basada en matrices». Open Data Structures (en pseudocódigo) . Archivado desde el original el 31 de agosto de 2015. Consultado el 7 de noviembre de 2015 .
  8. ^ Mike Ash (17 de febrero de 2012). «mikeash.com: Preguntas y respuestas del viernes 17 de febrero de 2012: Ring Buffers y memoria reflejada: Parte II». mikeash.com . Archivado desde el original el 11 de enero de 2019. Consultado el 10 de enero de 2019 .
  9. ^ Simon Cooke (2003), "El búfer Bip: el búfer circular con un toque diferente"
  10. ^ Gunther, John C. (marzo de 2014). "Algoritmo 938: compresión de buffers circulares". ACM Transactions on Mathematical Software . 40 (2): 1–12. doi :10.1145/2559995. S2CID  14682572.

Enlaces externos