2.6.1. FIFO

FIFO: First In First Out

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 finalización 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.

FIFO

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.

Esquema de funcionamiento de una cola 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 asignación 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). 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.

El sistema debe reservar el tamaño de memoria necesario para acoger todos los datos, sea cual sea el número de elementos usados, lo que en algunas aplicaciones supone un despilfarro de la memoria. Sin embargo, si se usan punteros, el número máximo no está declarado sino que se hace un uso dinámico de la memoria, adaptándose al tamaño necesario en cada momento en función de los elementos que hay en la cola. Uno de los usos de las colas es la exploración “en anchura” de un árbol de búsqueda. Otro uso típico de las colas, es la gestión de descargas de una aplicación p2p.

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.

Como ejemplo de banderas de estado FIFO, se pueden enumerar: full (lleno), empty (vacio), almost full (casi lleno) o almost empty (casi vacio).

FIFO FULL (LLENO)/EMPTY (VACIO) [editar]En el hardware FIFO se usa para propósitos de sincronización. Comportándose como una cola circular . Tiene dos punteros:

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

Las direcciones de lectura y escritura están ambas inicialmente en la primer ubicación de la memoria y la cola FIFO está Vacía.

FIFO Vacía: Cuando registro de dirección de lectura alcanza al registro de dirección de escritura, la cola FIFO dispara la señal Vacio.

FIFO Llena: Cuando el registro de dirección de escritura alcanza al registro de dirección de lectura, la cola FIFO dispara la señal LLENO. [15-A]

_____________________________
[15-A] Sistemas operativos. (n.d.) Extraído el 24 de octubre de 2008 desde http://www.mitecnologico.com/Main/SistemasOperativos