FIFO
FIFO se utiliza en estructuras de datos para implementar colas. La implementación puede efectuarse con ayuda de arrays o vectores, o bien mediante el uso de punteros y asignacion dinámica de memoria
Si se implementa mediante vectores el número máximo de elementos que puede almacenar está limitado al que se haya establecido en el código del programa antes de la compilación (cola estática) o durante su ejecución (cola pseudoestática ó dinámica). Sea cual sea la opción elegida, el número de elementos que podrá almacenar la cola quedará determinado durante toda la ejecución del programa. Así, el sistema debe reservar el tamaño de memoria necesario para acoger todos los datos, sea cual sea el número de elementos usados.
En algunas aplicaciones, esto supone un problema ya que puede desconocerse el número de elementos a contener en la cola. La sencilla solución de reservar más memoria de la que se supone que se necesitará, puede conducir a un despilfarro de la memoria (la cola puede esté llena, aprovechando toda la memoria reservada; o bien, nunca terminar de llenarse, ocupando recursos innecesarios en memoria). Sin embargo, si se usa asignación dinámica de memoria, el número máximo no está declarado en tiempo de compilación sino en tiempo de ejecución, es decir, se reserva memoria a medida que se necesite expandir el tamaño de la cola (adaptándose al tamaño necesario en cada momento en función de los elementos que hay en la cola), haciendo un mejor uso de la memoria disponible.
Los FIFOs se usan comúnmente en circuitos de electrónica para almacenaje y hacer control de flujo. Hablando de hardware un FIFO consiste básicamente en un conjunto de punteros de lectura/escritura, almacenamiento y lógica de control. El almacenamiento puede ser SRAM, flip-flops, latches o cualquier otra forma adecuada de almacenamiento. Para FIFOs de un tamaño importante se usa usualmente una SRAM de doble puerto, donde uno de los puertos se usa para la escritura y el otro para la lectura.
Un FIFO sincrónico maneja el mismo reloj (clock) tanto para las lecturas como para las escrituras. Un FIFO asicrónico es aquel que utiliza diferentes relojes (clocks) uno para lectura y otro para la escritura. Cuando se habla de FIFOs asincrónicos se introduce el tema de la meta-estabilidad. Una implementación común de un FIFO asincrónico usa un Código Gray (o cualquier código de unidad de distancia) para los punteros de lectura y escritura de modo de asegurarse una generación de banderas (flags) segura/estable. Otra nota adicional respecto de la generación de banderas es que uno debe necesariamente usar punteros aritméticos para generar banderas para implementaciones asincrónicas de FIFO. Por otro lado, uno puede usar tanto un acercamiento "leaky bucket" o punteros aritméticos para generar banderas en una implementación FIFO sincrónica.
Si se implementa mediante vectores el número máximo de elementos que puede almacenar está limitado al que se haya establecido en el código del programa antes de la compilación (cola estática) o durante su ejecución (cola pseudoestática ó dinámica). Sea cual sea la opción elegida, el número de elementos que podrá almacenar la cola quedará determinado durante toda la ejecución del programa. Así, el sistema debe reservar el tamaño de memoria necesario para acoger todos los datos, sea cual sea el número de elementos usados.
En algunas aplicaciones, esto supone un problema ya que puede desconocerse el número de elementos a contener en la cola. La sencilla solución de reservar más memoria de la que se supone que se necesitará, puede conducir a un despilfarro de la memoria (la cola puede esté llena, aprovechando toda la memoria reservada; o bien, nunca terminar de llenarse, ocupando recursos innecesarios en memoria). Sin embargo, si se usa asignación dinámica de memoria, el número máximo no está declarado en tiempo de compilación sino en tiempo de ejecución, es decir, se reserva memoria a medida que se necesite expandir el tamaño de la cola (adaptándose al tamaño necesario en cada momento en función de los elementos que hay en la cola), haciendo un mejor uso de la memoria disponible.
Los FIFOs se usan comúnmente en circuitos de electrónica para almacenaje y hacer control de flujo. Hablando de hardware un FIFO consiste básicamente en un conjunto de punteros de lectura/escritura, almacenamiento y lógica de control. El almacenamiento puede ser SRAM, flip-flops, latches o cualquier otra forma adecuada de almacenamiento. Para FIFOs de un tamaño importante se usa usualmente una SRAM de doble puerto, donde uno de los puertos se usa para la escritura y el otro para la lectura.
Un FIFO sincrónico maneja el mismo reloj (clock) tanto para las lecturas como para las escrituras. Un FIFO asicrónico es aquel que utiliza diferentes relojes (clocks) uno para lectura y otro para la escritura. Cuando se habla de FIFOs asincrónicos se introduce el tema de la meta-estabilidad. Una implementación común de un FIFO asincrónico usa un Código Gray (o cualquier código de unidad de distancia) para los punteros de lectura y escritura de modo de asegurarse una generación de banderas (flags) segura/estable. Otra nota adicional respecto de la generación de banderas es que uno debe necesariamente usar punteros aritméticos para generar banderas para implementaciones asincrónicas de FIFO. Por otro lado, uno puede usar tanto un acercamiento "leaky bucket" o punteros aritméticos para generar banderas en una implementación FIFO sincrónica.
LIFO
Refiere generalmente a los principios abstractos del proceso de lista y del almacenamiento temporal, particularmente cuando hay ua necesidad de tener acceso a datos en cantidades limitadas y en cierta orden. lifo es utilizado en caso de que los datos pasados agregados a la estructura deben ser los primeros datos que se quitaran a ser evaluado.
No hay comentarios:
Publicar un comentario