First in, first out

First in, first out

First in, first out o FIFO (en español "primero en entrar, primero en salir"), es un concepto 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.

También se lo llama first come first served o FCFS (en español "primero en llegar, primero en ser atendido").

Contenido

Informática

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 ó dinámica). 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. Así, el sistema debe reservar el tamaño de memoria necesario para acoger todos los datos, sea cual sea el número de elementos usados.

En algunas aplicaciones, esto supone un problema ya que puede desconocerse el número de elementos a contener en la cola. La sencilla solución de reservar más memoria de la que se supone que se necesitará, puede conducir a un despilfarro de la memoria (la cola puede esté llena, aprovechando toda la memoria reservada; o bien, nunca terminar de llenarse, ocupando recursos innecesarios en memoria). Sin embargo, si se usa asignación dinámica de memoria, el número máximo no está declarado en tiempo de compilación sino en tiempo de ejecución, es decir, se reserva memoria a medida que se necesite expandir el tamaño de la cola (adaptándose al tamaño necesario en cada momento en función de los elementos que hay en la cola), haciendo un mejor uso de la memoria disponible.

Uno de los usos de las colas es la exploración "en anchura" de un árbol binario de búsqueda. Otro uso típico de las colas, es la gestión de descargas de una aplicación P2P.

Contabilidad

Artículo principal: FIFO y LIFO (contabilidad)

En contabilidad FIFO es un método para registrar el valor de un inventario. Su uso es apropiado cuando se cuenta con varios lotes de un mismo producto. Este método presume que el primer producto ingresado en el almacén será el primero en salir por efectos del inventario.

Electrónica

Artículo principal: registro tubo

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

Un FIFO sincrónico maneja el mismo reloj (clock) tanto para las lecturas como para las escrituras. Un FIFO asicrónico es aquel que utiliza diferentes relojes (clocks) uno 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 Código Gray (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 (vacío), almost full (casi lleno) o almost empty (casi vacío).

FIFO full/empty (lleno/vacío)

En hardware, un FIFO se usa para propósitos de sincronización. Comportándose como una cola circular y, por lo tanto, contiene 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 primera ubicación de la memoria y la cola FIFO está Vacía.

FIFO Vacía
Cuando el registro de dirección de lectura alcanza al registro de dirección de escritura, la cola FIFO dispara la señal o bandera Vacío.
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 o bandera

Véase también


Wikimedia foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Mira otros diccionarios:

  • First-out alarm — A first out alarm is an alarm that indicates in some manner that it was the first of a series. This is necessary in circumstances such as an automatic trip or shutdown of equipment, where many alarms will annunciate as a result of a shutdown. The …   Wikipedia

  • First baseman — First base, or 1B , is the first of four stations on a baseball diamond which must be touched in succession by a baserunner in order to score a run for that player s team. A first baseman is the player on the team playing defense who fields the… …   Wikipedia

  • First-come, first-served — (sometimes first come, first served or simply FCFS) is a service policy where by the requests of customers or clients are attended to in the order that they arrived, without other biases or preferences. The policy can be employed when processing… …   Wikipedia

  • last-in first-out — adjective Date: 1934 of, relating to, or being a method of inventory accounting that values stock on hand according to costs at the time of acquisition and not according to the cost of replacement …   New Collegiate Dictionary

  • Out-of-body experience — Artist s depiction of the separation stage of an out of body experience, which often precedes free movement. An out of body experience (OBE or sometimes OOBE) is an experience that typically involves a sensation of floating outside of one s body… …   Wikipedia

  • Out of the Unknown — For the collection of short stories by A. E. van Vogt and E. Mayne Hull, see Out of the Unknown (collection). Out of the Unknown Format Anthology Science fiction Drama …   Wikipedia

  • Out-of-order execution — In computer engineering, out of order execution (OoOE or OOE) is a paradigm used in most high performance microprocessors to make use of instruction cycles that would otherwise be wasted by a certain type of costly delay. In this paradigm, a… …   Wikipedia

  • First Chechen War — Russian helicopter brought down by Chechen fighters near the capital Grozny in 1994 …   Wikipedia

  • First they came... — First they came… is a poem attributed to Pastor Martin Niemöller (1892–1984) about the inactivity of German intellectuals following the Nazi rise to power and the purging of their chosen targets, group after group.HistoryAn early supporter of… …   Wikipedia

  • First Sino-Japanese War — Japanese troops during the Sino Japanese war …   Wikipedia

  • Out 1 — The title card to Out 1 Directed by Jacques Rivette Suzanne Schiffman (co director) …   Wikipedia

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”