En informática y en teoría de sistemas , el principio "primero en entrar, primero en salir " (el primero en entrar es el primero en salir), acrónimo FIFO , es 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 análogo a atender a las personas en un área de cola según el orden de llegada (FCFS), es decir, en la misma secuencia en la que llegan al final 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 a cada unidad central de procesamiento (CPU) de proceso tiempo en el orden en que se lo demanda. [1] El opuesto de FIFO es LIFO , último en entrar, primero en salir, donde la entrada más joven o "parte superior de la pila" se procesa primero. [2] Una cola de prioridad no es FIFO ni LIFO, pero puede adoptar un comportamiento similar temporalmente o por defecto. La teoría de colas abarca estos métodos para procesar estructuras de datos , así como interacciones entre colas FIFO estrictas.
Dependiendo de la aplicación, un FIFO podría implementarse como un registro de desplazamiento de hardware o utilizando diferentes estructuras de memoria, típicamente 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 código siguiente muestra una implementación en lenguaje C++ de lista enlazada FIFO . En la práctica, existen varias implementaciones de listas, incluidas las macros sys/queue.h de C en sistemas Unix populares 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 <memoria> #include <stdexcept> utilizando el espacio de nombres std ; plantilla < typename T > clase FIFO { struct Node { T valor ; shared_ptr < Node > siguiente = nullptr ; Nodo ( T _valor ) : valor ( _valor ) {} }; shared_ptr < Nodo > frente = nullptr ; shared_ptr < Nodo > atrás = nullptr ; público : void enqueue ( T _value ) { if ( front == nullptr ) { front = make_shared < Nodo > ( _value ); back = front ; } else { back -> next = make_shared < Nodo > ( _value ); back = back -> next ; } } T dequeue () { if ( front == nullptr ) throw underflow_error ( "No hay nada que sacar de la cola" ); Valor T = frente -> valor ; frente = mover ( frente -> siguiente ); valor de retorno ; } }; En entornos informáticos que admiten el modelo de tuberías y filtros para la comunicación entre procesos , un FIFO es otro nombre para una tubería con nombre .
Los controladores de disco pueden usar el FIFO como un algoritmo de programación de disco para determinar el orden en el que se atenderán las solicitudes de E/S de disco , donde también se lo conoce por las mismas siglas FCFS que para la programación de CPU mencionada anteriormente. [1]
Los puentes , conmutadores y enrutadores de redes de comunicación que se utilizan en redes informáticas utilizan FIFO para almacenar paquetes de datos en ruta hacia su próximo destino. Normalmente, 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. [3]
Los FIFO se utilizan habitualmente en circuitos electrónicos para el almacenamiento en búfer y el control de flujo entre hardware y software. En su forma de hardware, un FIFO consta principalmente de un conjunto de punteros de lectura y escritura , almacenamiento y lógica de control. El almacenamiento puede ser una memoria de acceso aleatorio estática (SRAM), flip-flops , pestillos o cualquier otra forma adecuada de almacenamiento. Para los FIFO de tamaño no trivial, se suele utilizar una SRAM de doble puerto, donde un puerto está dedicado a la escritura y el otro a la lectura.
El primer FIFO conocido implementado en electrónica fue realizado por Peter Alfke en 1969 en Fairchild Semiconductor . [4] Alfke fue posteriormente director de Xilinx .
Un FIFO sincrónico es un FIFO en el que se utiliza el mismo reloj tanto para la lectura como para la escritura. Un FIFO asincrónico utiliza diferentes relojes para la lectura y la escritura y pueden introducir problemas de metaestabilidad . Una implementación común de un FIFO asincrónico utiliza un código Gray (o cualquier código de distancia unitaria) para los punteros de lectura y escritura para garantizar una generación de indicadores confiable. Otra nota sobre la generación de indicadores es que uno debe usar necesariamente la aritmética de punteros para generar indicadores para las implementaciones de FIFO asincrónicos. Por el contrario, uno puede usar un enfoque de cubo con fugas o aritmética de punteros para generar indicadores en implementaciones de FIFO sincrónicos.
Se utiliza un FIFO de hardware para fines de sincronización. A menudo se implementa como una cola circular y, por lo tanto, tiene dos punteros :
Algunos 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 por cada dirección de lectura y escritura, que se invierte cada vez que la dirección se reinicia. Con esta configuración, las condiciones de desambiguación son: