FIFO (informática y electrónica)

Representación de una cola FIFO

En informática y en teoría de sistemas, FIFO es un acrónimo de primero en entrar, primero en salir (el primero en entrar es el primero en salir), un método para organizar la manipulación de una estructura de datos (a menudo, específicamente un búfer de datos) donde la entrada más antigua (primera), o "cabeza" de la cola, se procesa primero.

Este procesamiento es similar a atender a las personas en un área de cola por orden de llegada (FCFS), es decir, en la misma secuencia en la que llegan a la cola de la cola.

FCFS es también el término de la jerga para el algoritmo de programación del sistema operativo FIFO, que otorga tiempo a cada unidad central de procesamiento (CPU) de proceso en el orden en que se solicita. El opuesto de FIFO es LIFO, último en entrar, primero en salir, donde la entrada más joven o "top of the stack" se procesa primero. Una cola de prioridad no es FIFO ni LIFO, pero puede adoptar un comportamiento similar de forma temporal o predeterminada. La teoría de colas abarca estos métodos para procesar estructuras de datos, así como las interacciones entre colas FIFO estrictas.

Ciencias de la computación

Representación de una cola de FIFO con operaciones enqueue y dequeue.

Dependiendo de la aplicación, un FIFO podría implementarse como un registro de desplazamiento de hardware o utilizando diferentes estructuras de memoria, normalmente un búfer circular o una especie de lista. Para obtener información sobre la estructura de datos abstracta, consulte Cola (estructura de datos). La mayoría de las implementaciones de software de una cola FIFO no son seguras para subprocesos y requieren un mecanismo de bloqueo para verificar que la cadena de estructura de datos está siendo manipulada por un solo subproceso a la vez.

El siguiente código muestra una lista enlazada de la implementación del lenguaje FIFO C++. En la práctica, existen varias implementaciones de listas, incluidas las populares macros C sys/queue.h de los sistemas Unix o la plantilla std::list de la biblioteca estándar de C++, lo que evita la necesidad de implementar la estructura de datos desde cero.

#include - No.#include - No.utilizando namespace std;plantilla .nombre T■clase FIFO {} struct Node {} T valor; shared_ptr.Node■ siguiente = nullptr; Node()T _value): valor()_value) {} }; shared_ptr.Node■ frontal = nullptr; shared_ptr.Node■ atrás = nullptr;público: vacío enqueue()T _value) {} si ()frontal == nullptr) {} frontal = make_shared.Node■()_value); atrás = frontal; } más {} atrás-siguiente = make_shared.Node■()_value); atrás = atrás-siguiente; } } T dequeue() {} si ()frontal == nullptr) tiro underflow_error()"Nada que desgarrar"); T valor = frontal-valor; frontal = Muévanse.()frontal-siguiente);  retorno valor; }};

En entornos informáticos que admiten el modelo de conductos y filtros para la comunicación entre procesos, FIFO es otro nombre para un conducto con nombre.

Los controladores de disco pueden usar FIFO como un algoritmo de programación de disco para determinar el orden en el que atender las solicitudes de E/S de disco, donde también se conoce por el mismo inicialismo FCFS que para la programación de CPU mencionada anteriormente.

Los puentes, conmutadores y enrutadores de las redes de comunicación que se utilizan en las redes informáticas utilizan FIFO para mantener los paquetes de datos en ruta hacia su próximo destino. Por lo general, se utiliza al menos una estructura FIFO por conexión de red. Algunos dispositivos cuentan con múltiples FIFO para poner en cola de forma simultánea e independiente diferentes tipos de información.

Electrónica

Un programa de FIFO

Los FIFO se usan comúnmente en circuitos electrónicos para almacenar en búfer y controlar el flujo entre el hardware y el software. En su forma de hardware, una FIFO consiste principalmente en un conjunto de punteros de lectura y escritura, almacenamiento y lógica de control. El almacenamiento puede ser una memoria estática de acceso aleatorio (SRAM), flip-flops, pestillos o cualquier otra forma adecuada de almacenamiento. Para FIFO de tamaño no trivial, generalmente se usa una SRAM de doble puerto, donde un puerto está dedicado a escribir y el otro a leer.

El primer FIFO conocido implementado en electrónica fue de Peter Alfke en 1969 en Fairchild Semiconductor. Alfke fue más tarde director en Xilinx.

Sincronicidad

Un FIFO síncrono es un FIFO en el que se utiliza el mismo reloj para leer y escribir. Un FIFO asíncrono usa diferentes relojes para leer y escribir y pueden introducir problemas de metaestabilidad. Una implementación común de un FIFO asíncrono utiliza un código Gray (o cualquier código de unidad de distancia) para los punteros de lectura y escritura para garantizar una generación de indicadores confiable. Una nota adicional sobre la generación de banderas es que necesariamente se debe usar aritmética de punteros para generar banderas para implementaciones FIFO asíncronas. Por el contrario, se puede utilizar un enfoque de cubeta con fugas o aritmética de punteros para generar indicadores en implementaciones FIFO sincrónicas.

Se utiliza un FIFO de hardware con fines de sincronización. A menudo se implementa como una cola circular y, por lo tanto, tiene dos punteros:

• Read pointer / read address register
• Escriba puntero / escriba dirección registro

Indicadores de estado

Los ejemplos de indicadores de estado FIFO incluyen: lleno, vacío, casi lleno y casi vacío. Un FIFO está vacío cuando el registro de dirección de lectura alcanza el registro de dirección de escritura. Un FIFO está lleno cuando el registro de dirección de escritura alcanza el registro de dirección de lectura. Las direcciones de lectura y escritura están inicialmente en la primera ubicación de memoria y la cola FIFO está vacía.

En ambos casos, las direcciones de lectura y escritura terminan siendo iguales. Para distinguir entre las dos situaciones, una solución simple y robusta es agregar un bit adicional para cada dirección de lectura y escritura que se invierte cada vez que se ajusta la dirección. Con esta configuración, las condiciones de desambiguación son:

• Cuando el registro de direcciones de lectura es igual al registro de direcciones, el FIFO está vacío.
• Cuando los registros de direcciones de lectura y escritura difieren sólo en el bit extra más significativo y el resto son iguales, el FIFO está lleno.