2.6.1 FIFO (First In First Out )

(Segun J. Boria, 2002 ) Mecanismo de scheduling en el cual los procesos se ordenan en una fila, en la cual se ejecutan cada uno de los procesos hasta su finalizacion secuencialmente. Es tremendamente ineficiente.
Cuando se tiene que elegir a qué proceso asignar la CPU se escoge al que llevara más tiempo listo. El proceso se mantiene en la CPU hasta que se bloquea voluntariamente.

Para implementar el algoritmo sólo se necesita mantener una cola con los procesos listos ordenada por tiempo de llegada. Cuando un proceso pasa de bloqueado a listo se sitúa el último de la cola.

(Segun J. Boria, 2002 ) FIFO es el acrónimo inglés de First In, First Out (primero en entrar, primero en salir). Un sinónimo de FIFO es FCFS, acrónimo inglés de First Come First Served ( primero en llegar, primero en ser servido). Es un método utilizado en estructuras de datos, contabilidad de costes y teoría de colas. Guarda analogía con las personas que esperan en una cola y van siendo atendidas en el orden en que llegaron, es decir, que la primera persona que entra es la primera persona que sale.

Los FIFOs se usan comúnmente en circuitos de electrónica para almacenaje y hacer control de flujo. Hablando de hardware form un FIFO consiste básicamente en una 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 par a la lectura.

Un FIFO sincrónico maneja el mismo reloj (clock) tanto para las lecturas como para las escrituras. Una asicrónico es aquel que utiliza diferentes relojes (clocks) una 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 Gray code ( 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.

El hardware FIFO se utiliza para propositos de sincronizacion como:

1. Puntero de Lectura/Registro de Dirección de Lectura.
2. Puntero de Escritura/Registro de Dirección de Escritura.