FIFO
From Free net encyclopedia
FIFO is an acronym for First In, First Out. This expression describes the principle of a queue or first-come, first-served (FCFS) behavior: what comes in first is handled first, what comes in next waits until the first is finished, etc. Thus it is analogous to the behaviour of persons "standing in a line" (preferred in American English) or "queueing" (preferred in Commonwealth English), where the persons leave the queue in the order they arrive. FCFS is also the other name for the FIFO operating system scheduling algorithm, which gives every process cpu time in the order they come.
A priority queue is a variation on the queue which does not qualify for the name FIFO, because it is not accurately descriptive of that data structure's behavior. Queuing theory encompasses the more general concept of queue, as well as interactions between strict-FIFO queues.
The expression FIFO can be used in different contexts.
Contents |
People
- For queues of people, see queue area.
Computer science
Data structure
In computer science this term refers to the way data stored in a queue is processed. Each item in the queue is stored in a queue (simpliciter) data structure. The first data to be added to the queue will be the first data to be removed, then processing proceeds sequentially in the same order. This is typical behavior for a queue, but see also the LIFO and stack algorithms.
A typical data structure will look like
struct fifo_node {
fifo_node *next;
value_type value;
};
class fifo
{
fifo_node *front;
fifo_node *back;
fifo_node *dequeue(void)
{
fifo_node *tmp = front;
front = front->next;
return tmp;
}
queue(value)
{
fifo_node *tempNode = new fifo_node;
tempNode->value = value;
back->next = tempNode;
back = tempNode;
}
}
(For information on the abstract data structure, and an implementation in scheme, see Queue. For details of a common implementation, see Circular buffer.)
Popular UNIX systems include a sys/queue.h C/C++ header file which provides macros usable by applications necessary to create FIFO queues.
Pipes
In computing environments that support the pipes and filters model for interprocess communication, a FIFO is another name for a named pipe.
Electronics
FIFOs are used commonly in electronic circuits for buffering and flow control. In hardware form a FIFO primarily consists of a set of read and write pointers, storage and control logic. Storage may be SRAM, flip-flops, latches or any other suitable form of storage. For FIFOs of non-trivial size a dual-port SRAM is usually used where one port is used for writing and the other is used for reading.
A synchronous FIFO is a FIFO where the same clock is used for both reading and writing. An asynchronous FIFO uses different clocks for reading and writing. Asynchronous FIFOs introduce metastability issues. A common implementation of an asychronous FIFO uses a Gray code (or any unit distance code) for the read and write pointers to ensure reliable flag generation. One further note concerning flag generation is that one must necessarily use pointer arithmetic to generate flags for asynchronous FIFO implementations. Conversely, one may use either a "leaky bucket" approach or pointer arithmetic to generate flags in synchronous FIFO implementations.
Examples of FIFO status flags include: full, empty, almost full, or almost empty.
See also
- LIFO (Last in, first out)de:First In – First Out
es:FIFO fr:First in, first out he:נכנס ראשון יוצא ראשון it:FIFO lt:FIFO nl:Fifo ja:FIFO pt:FIFO sv:FIFO