En informática y en teoría de sistemas , primero en entrar, primero en salir (el primero en entrar es el primero en salir), acrónimo como FIFO , es un método para organizar la manipulación de una estructura de datos (a menudo, específicamente un buffer de datos ) donde el más antiguo (el primero ) la entrada, o "cabeza" de la cola , se procesa primero.
Tal procesamiento es análogo 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 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 proporciona a cada proceso el tiempo de la unidad central de procesamiento (CPU) en el orden en que se solicita. [1] Lo opuesto a 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 ni 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.
Dependiendo de la aplicación, un FIFO podría implementarse como un registro de desplazamiento de hardware o utilizando diferentes estructuras de memoria, generalmente 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 vinculada de implementación del lenguaje FIFO C++ . En la práctica, existen varias implementaciones de listas, incluidas las populares macros C sys/queue.h de sistemas Unix o la plantilla std::list de la biblioteca estándar C++ , lo que evita la necesidad de implementar la estructura de datos desde cero.
#include <memoria> #include <stdexcept> usando el espacio de nombres estándar ; plantilla < nombre de tipo T > clase FIFO { estructura Nodo { valor T ; share_ptr <Nodo> siguiente = nullptr ; Nodo ( T _valor ) : valor ( _valor ) {} }; share_ptr <Nodo> frente = nullptr ; share_ptr <Nodo> atrás = nullptr ; público : cola vacía ( T _valor ) { if ( front == nullptr ) { front = make_shared <Nodo> ( _value ) ; atrás = frente ; } else { atrás - > siguiente = make_shared <Nodo> ( _valor ) ; atrás = atrás -> siguiente ; } } T quitar de la cola () { if ( front == nullptr ) throw underflow_error ( "Nada que quitar 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 , FIFO es otro nombre para una tubería con nombre .
Los controladores de disco pueden utilizar FIFO como 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 lo conoce por el mismo inicialismo FCFS que para la programación de CPU mencionada anteriormente. [1]
Los puentes , conmutadores y enrutadores de redes de comunicación utilizados en redes informáticas utilizan FIFO para contener 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 comúnmente en circuitos electrónicos para almacenamiento en búfer y 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 estática de acceso aleatorio (SRAM), flip-flops , pestillos o cualquier otra forma adecuada de almacenamiento. Para 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 más tarde director de Xilinx .
Un FIFO síncrono es un FIFO en el que se utiliza el mismo reloj para lectura y escritura. Un FIFO asíncrono utiliza diferentes relojes para lectura y escritura 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 confiable de indicadores. Una nota adicional sobre la generación de indicadores es que necesariamente se debe utilizar aritmética de punteros para generar indicadores para implementaciones FIFO asincrónicas. Por el contrario, se puede utilizar un enfoque de depósito con fugas o aritmética de punteros para generar indicadores en implementaciones FIFO síncronas.
Se utiliza un FIFO de hardware para fines de sincronización. A menudo se implementa como una cola circular y, por tanto, tiene dos punteros :
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 llega al registro de dirección de escritura. Un FIFO está lleno cuando el registro de dirección de escritura llega al registro de dirección de lectura. Las direcciones de lectura y escritura se encuentran inicialmente en la primera ubicación de memoria y la cola FIFO está vacía .
En ambos casos, las direcciones de lectura y escritura acaban siendo iguales. Para distinguir entre las dos situaciones, una solución simple y sólida es agregar un bit adicional para cada dirección de lectura y escritura, que se invierte cada vez que la dirección se ajusta. Con esta configuración, las condiciones de desambiguación son:
{{cite book}}: Mantenimiento CS1: ubicación ( enlace )