Representation of a FIFO queue
In computing and in
systems theory, FIFO is an
acronym
An acronym is a word or name formed from the initial components of a longer name or phrase. Acronyms are usually formed from the initial letters of words, as in ''NATO'' (''North Atlantic Treaty Organization''), but sometimes use syllables, as ...
for first in, first out (the first in is the first out), a method for organizing the manipulation of a data structure (often, specifically a
data buffer) where the oldest (first) entry, or "head" of the
queue, is processed first.
Such processing is analogous to servicing people in a
queue area on a
first-come, first-served (FCFS) basis, i.e. in the same sequence in which they arrive at the queue's tail.
FCFS is also the
jargon
Jargon is the specialized terminology associated with a particular field or area of activity. Jargon is normally employed in a particular communicative context and may not be well understood outside that context. The context is usually a partic ...
term for the FIFO
operating system scheduling algorithm, which gives every process
central processing unit
A central processing unit (CPU), also called a central processor, main processor or just processor, is the electronic circuitry that executes instructions comprising a computer program. The CPU performs basic arithmetic, logic, controlling, a ...
(CPU) time in the order in which it is demanded.
FIFO's opposite is
LIFO, last-in-first-out, where the youngest entry or "top of the stack" is processed first.
A
priority queue is neither FIFO or LIFO but may adopt similar behaviour temporarily or by default.
Queueing theory encompasses these methods for processing
data structures
In computer science, a data structure is a data organization, management, and storage format that is usually chosen for efficient access to data. More precisely, a data structure is a collection of data values, the relationships among them, ...
, as well as interactions between strict-FIFO queues.
Computer science
300px, Representation of a FIFO queue with enqueue and dequeue operations.
Depending on the application, a FIFO could be implemented as a hardware shift register, or using different memory structures, typically a
circular buffer or a kind of
list. For information on the abstract data structure, see
Queue (data structure)
In computer science, a queue is a collection of entities that are maintained in a sequence and can be modified by the addition of entities at one end of the sequence and the removal of entities from the other end of the sequence. By convention ...
. Most software implementations of a FIFO queue are not
thread safe and require a locking mechanism to verify the data structure chain is being manipulated by only one thread at a time.
The following code shows a
linked list FIFO
C++ language implementation. In practice, a number of list implementations exist, including popular Unix systems C sys/queue.h macros or the C++
standard library
In computer programming, a standard library is the library made available across implementations of a programming language. These libraries are conventionally described in programming language specifications; however, contents of a language's a ...
std::list template, avoiding the need for implementing the data structure from scratch.
#include
#include
using namespace std;
template
class FIFO ;
In computing environments that support the
pipes-and-filters model for
interprocess communication, a FIFO is another name for a
named pipe.
Disk controllers can use the FIFO as a
disk scheduling algorithm to determine the order in which to service disk
I/O requests, where it is also known by the same FCFS initialism as for CPU scheduling mentioned before.
Communication
network bridge
A network bridge is a computer networking device that creates a single, aggregate network from multiple communication networks or network segments. This function is called network bridging. Bridging is distinct from routing. Routing allows ...
s,
switches and
routers used in
computer network
A computer network is a set of computers sharing resources located on or provided by network nodes. The computers use common communication protocols over digital interconnections to communicate with each other. These interconnections are ...
s use FIFOs to hold data packets in route to their next destination. Typically at least one FIFO structure is used per network connection. Some devices feature multiple FIFOs for simultaneously and independently queuing different types of information.
Electronics
400px, A FIFO schedule
FIFOs are commonly used in
electronic circuits for buffering and flow control between hardware and software. In its hardware form, a FIFO primarily consists of a set of read and write
pointers, storage and control logic. Storage may be
static random access memory
Static random-access memory (static RAM or SRAM) is a type of random-access memory (RAM) that uses latching circuitry (flip-flop) to store each bit. SRAM is volatile memory; data is lost when power is removed.
The term ''static'' differ ...
(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 dedicated to writing and the other to reading.
The first known FIFO implemented in electronics was by Peter Alfke in 1969 at
Fairchild Semiconductor.
Alfke was later a director at
Xilinx.
Synchronicity
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 and they can introduce
metastability issues. A common implementation of an asynchronous 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
The leaky bucket is an algorithm based on an analogy of how a bucket with a constant leak will overflow if either the average rate at which water is poured in exceeds the rate at which the bucket leaks or if more water than the capacity of the ...
approach or pointer arithmetic to generate flags in synchronous FIFO implementations.
A hardware FIFO is used for synchronization purposes. It is often implemented as a
circular queue
In computer science, a circular buffer, circular queue, cyclic buffer or ring buffer is a data structure that uses a single, fixed-size buffer as if it were connected end-to-end. This structure lends itself easily to buffering data streams. Ther ...
, and thus has two
pointers:
* Read pointer / read address register
* Write pointer / write address register
Status flags
Examples of FIFO status flags include: full, empty, almost full, and almost empty. A FIFO is empty when the read
address register reaches the write address register. A FIFO is full when the write address register reaches the read address register. Read and write addresses are initially both at the first memory location and the FIFO queue is ''empty''.
In both cases, the read and write addresses end up being equal. To distinguish between the two situations, a simple and robust solution is to add one extra
bit for each read and write address which is inverted each time the address wraps. With this set up, the disambiguation conditions are:
* When the read address register equals the write address register, the FIFO is empty.
* When the read and write address registers differ only in the extra
most significant bit and the rest are equal, the FIFO is full.
See also
*
FIFO and LIFO accounting
*
FINO
*
Queueing theory
References
External links
Cummings et al., Simulation and Synthesis Techniques for Asynchronous FIFO Design with Asynchronous Pointer Comparisons, SNUG San Jose 2002
{{Queueing theory
Scheduling algorithms
Queue management
Inter-process communication