FIFO

Representació d'una cua FIFO (First-In-First-Out).

First in, first out o FIFO (en català, «primer a entrar, primer a sortir»), és un concepte utilitzat en estructures de dades, comptabilitat de costos i teoria de cues. Guarda analogia amb les persones que esperen en una cua i van sent ateses en l'ordre en què van arribar, és a dir, que la primera persona que entra és la primera persona que surt.

També s'anomena first come, first served o FCFS (en català, «primer a arribar, primer a ser atès»).

Aplicacions

Aquesta estructura s'utilitza per exemple:

• en general, per emmagatzemar temporalment les transaccions que han d'esperar per ser processades;
• servidors d'impressió, que processen consultes en l'ordre en què arriben, i els insereixen en una cua (també anomenada "spool" ';
• alguns motors multitasca, en un sistema operatiu, que han de concedir temps de màquinari a cada tasca, sense privilegiar-ne cap;
• Un BFS utilitza una cua per emmagatzemar els nodes visitats;
• per crear tot tipus de memòries intermèdies o buffers(en anglès);
• En gestió d'inventaris, els algorismes han de respectar la gestió d'inventaris físics per garantir la consistència/valoració física.

Informàtica

En informàtica, FIFO s'utilitza en estructures de dades per implementar cues. La implementació pot efectuar-se amb ajuda d'arranjaments o vectors, o bé mitjançant l'ús de punters i assignació dinàmica de memòria.

Si s'implementa mitjançant vectors, el nombre màxim d'elements que pot emmagatzemar FIFO està limitat al que s'hagi establert en el codi del programa abans de la compilació (cua estàtica) o durant la seva execució (cua pseudoestática o dinàmica). Sigui quina sigui l'opció triada, el nombre d'elements que podrà emmagatzemar la cua quedarà determinat durant tota l'execució del programa. Així, el sistema ha de reservar la mida de memòria necessari per acollir totes les dades, sigui quin sigui el nombre d'elements usats.

En algunes aplicacions, això suposa un problema, ja que pot desconèixer-se el nombre d'elements a contenir a la cua. La senzilla solució de reservar més memòria de la que se suposa que es necessitarà, pot conduir a un malbaratament de la memòria (la cua pot ser que estigui plena, aprofitant tota la memòria reservada, o bé, que mai s'acabi d'omplir-, ocupant recursos innecessaris en memòria). No obstant això, si es fa servir assignació dinàmica de memòria, el nombre màxim no està declarat en temps de compilació sinó en temps d'execució, és a dir, es reserva memòria a mesura que es necessiti expandir la mida de la cua (adaptant a la mida necessari en cada moment en funció dels elements que hi ha a la cua), fent un millor ús de la memòria disponible.

Un dels usos de les cues és l'exploració 'en amplada' d'un arbre binari de cerca. Un altre ús típic de les cues, és la gestió de descàrregues d'una aplicació peer-to-peer (P2P).

Estructura de dades

Representació d'una cua FIFO (primera entrada, primera sortida)

Depenent de l'aplicació, es podria implementar un FIFO com a registre de desplaçaments de maquinari o utilitzant diferents estructures de memòria, normalment un buffer circular o un tipus de llista. Per obtenir informació sobre l'estructura de dades abstractes, vegeu Cua (estructura de dades). La majoria de les implementacions de programari d'una cua FIFO no són segurs i requereixen un mecanisme de bloqueig per verificar que la cadena d'estructura de dades es manipula només per un fil a la vegada.

Codi

El codi següent mostra una implementació de llista enllaçada FIFO C . A la pràctica, existeixen diverses implementacions de llistes, incloses macros populars de sistemes Unix C sys/queue.h o la plantilla C biblioteca estàndard std :: list, evitant la necessitat d'implementar l'estructura de dades des de zero.

#include <iostream>
#include <stdexcept>

template <typename T>
class FIFO
{
private:

 struct Node {
 T value;
 Node *next;

 Node(T _value) : value(_value), next(NULL) {}
 };

 Node *front;
 Node *back;

public:
 FIFO() : front(NULL), back(NULL) {}

 ~FIFO() {
 while (front != NULL)
 dequeue();
 }

 void enqueue(T _value) {
 Node *newNode = new Node(_value);

 if (front == NULL)
 front = newNode;
 else
 back->next = newNode;

 back = newNode;
 }

 T dequeue() {
 if (front == NULL)
 throw std::underflow_error("Nothing to dequeue");

 Node *temp = front; 
 T result = front->value;

 front = front->next;
 delete temp;

 return result;
 }
};

Primer cap o cua

Els extrems d'una cua FIFO sovint s'anomenen "cap" i «cua». Malauradament, hi ha una controvèrsia sobre aquests termes:

• Per a moltes persones, els articles han d'introduir una cua al final i romandre a la cua fins que arribin al cap i deixar la cua des d'allà. Aquest punt de vista es justifica per analogia amb cues de persones que esperen algun tipus de servei i paral·lel a l'ús de "front" i "back" en l'exemple anterior.
• Altres persones creuen que els articles entren a la cua al davant i surten a la cua, a la manera del menjar que s'empassa una serp. Les cues escrites d'aquesta manera apareixen en llocs que es podrien considerar autoritzats, com el sistema operatiu Linux.

Canonades

En entorns informàtics que admeten el model de canonades per a Comunicació entre processos, un FIFO és un altre nom per a canonades anomenades o named pipe.

Programació de disc

Els controladors de disc poden utilitzar el FIFO com a algoritme de programació de discs per determinar l'ordre en què es pot atendre les sol·licituds d'E/S del disc.

Comunicacions i treball en xarxa

La comunicació per ponts de xarxes, commutadors i encaminadors (routers) utilitzats a xarxes informàtiques utilitzen FIFO per mantenir paquets de dades en ruta cap al següent destí. Normalment s'utilitza almenys una estructura FIFO per connexió de xarxa. Alguns dispositius disposen de múltiples FIFO per a la cua simultània i independent dels diferents tipus d'informació.

Comptabilitat

Article principal: FIFO (comptabilitat)

En comptabilitat FIFO és un mètode per registrar el valor d'un inventari. El seu ús és apropiat quan es compta amb diversos lots d'un mateix producte, de forma que és molt difícil identificar-los individualment. Aquest mètode presumeix que el primer producte ingressat al magatzem serà el primer a sortir per efectes de l'inventari.

El criteri FIFO és molt recurrent a l'hora de valorar inventaris compostos per productes caducs o peribles; en altres paraules, se seguirà l'ordre necessari perquè les peces a les que primer es doni sortida siguin les més pròximes a caducar o assolir una obsolescència.

Electrònica

Els FIFO s'usen comunament en circuits de electrònica per a emmagatzematge i fer control de flux. Parlant de maquinari, un FIFO consisteix bàsicament en un conjunt de punters de lectura/escriptura, emmagatzematge i lògica de control. L'emmagatzematge pot ser SRAM, flip-flops, latches o qualsevol altra forma adequada d'emmagatzematge. Per FIFO d'una mida important s'usa usualment una SRAM de doble port, on un dels ports s'usa per a l'escriptura i l'altre per a la lectura.

Un « FIFO sincrònic» fa servir el mateix rellotge tant per a les lectures com per a les escriptures. Un « FIFO asicrònic» és aquell que utilitza diferents rellotges, un per lectura i un altre per a l'escriptura. Quan es parla de FIFO asincrònic s'introdueix el tema de la meta-estabilitat.

Una implementació comuna d'un FIFO asincrònic fa servir un codi Gray (o qualsevol codi d'unitat de distància) per als punters de lectura i escriptura de manera d'assegurar-se una generació de banderes (flag) segures/estables.

Una altra nota addicional respecte de la generació de banderes és que un ha de necessàriament usar punters aritmètics per generar banderes per implementacions asincròniques de FIFO.

D'altra banda, un pot usar tant un acostament leaky bucket o punters aritmètics per generar banderes en una implementació FIFO sincrònica.

En FIFO, es poden enumerar:

• Full (ple),
• Empty (buida),
• Almost full (gairebé ple),
• Almost empty (gairebé buit).

FIFO ple / buit

En maquinari, un FIFO s'usa per a propòsits de sincronització. Comportant-se com una cua circular i, per tant, conté dos punters:

• Punter de lectura / registre de direcció de lectura.
• Punter d'escriptura / registre de direcció d'escriptura.

Les adreces de lectura i escriptura estan ambdues inicialment en la primera ubicació de la memòria i la cua FIFO està buida.

FIFO buida (empty)

Quan el registre de direcció de lectura aconsegueix al registre de direcció d'escriptura, la cua FIFO dispara el senyal o bandera buit.

FIFO plena (full)

Quan el registre de direcció d'escriptura aconsegueix al registre de direcció de lectura, la cua FIFO dispara el senyal o bandera ple.

Vegeu també

• Last in, first out o LIFO, el contrari de FIFO. Guarda analogia amb una pila de plats, en què els plats van posant un sobre l'altre, i si es vol treure un, es treu primer l'últim que s'ha posat.
• GIGO, acrònim de Garbage In, Garbage Out, es pot traduir per brossa entra, brossa surt. Emprada per a posar en relleu que els ordinadors, a diferència dels éssers humans, processen incondicionalment dades d'entrada encara que siguin absurdes i aportaran dades de sortida sense sentit.

Bibliografia

• Knuth, Donald E. The Art of Computer Programming (en anglès). vol I. Fundamental Algorithms. 3. Addison Wesley, 1997.