FIFO (computing and electronics)
   HOME

TheInfoList



OR:

Representation of a FIFO queue In computing and in
systems theory Systems theory is the interdisciplinary study of systems, i.e. cohesive groups of interrelated, interdependent components that can be natural or human-made. Every system has causal boundaries, is influenced by its context, defined by its structu ...
, 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 In computer science, a data buffer (or just buffer) is a region of a memory used to temporarily store data while it is being moved from one place to another. Typically, the data is stored in a buffer as it is retrieved from an input device (such a ...
) where the oldest (first) entry, or "head" of the
queue __NOTOC__ Queue () may refer to: * Queue area, or queue, a line or area where people wait for goods or services Arts, entertainment, and media *''ACM Queue'', a computer magazine * ''The Queue'' (Sorokin novel), a 1983 novel by Russian author ...
, is processed first. Such processing is analogous to servicing people in a
queue area Queue areas are places in which people queue ( first-come, first-served) for goods or services. Such a group of people is known as a ''queue'' ( British usage) or ''line'' (American usage), and the people are said to be waiting or standing ''i ...
on a
first-come, first-served Queueing theory is the mathematical study of waiting lines, or queues. A queueing model is constructed so that queue lengths and waiting time can be predicted. Queueing theory is generally considered a branch of operations research because the ...
(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 Context (language use), communicative context and may not be well understood outside that context. The conte ...
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, an ...
(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 In computer science, a priority queue is an abstract data-type similar to a regular queue or stack data structure in which each element additionally has a ''priority'' associated with it. In a priority queue, an element with high priority is se ...
is neither FIFO or LIFO but may adopt similar behaviour temporarily or by default.
Queueing theory Queueing theory is the mathematical study of waiting lines, or queues. A queueing model is constructed so that queue lengths and waiting time can be predicted. Queueing theory is generally considered a branch of operations research because the ...
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, a ...
, 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 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 ...
or a kind of
list A ''list'' is any set of items in a row. List or lists may also refer to: People * List (surname) Organizations * List College, an undergraduate division of the Jewish Theological Seminary of America * SC Germania List, German rugby union ...
. 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 Thread safety is a computer programming concept applicable to multi-threaded code. Thread-safe code only manipulates shared data structures in a manner that ensures that all threads behave properly and fulfill their design specifications without uni ...
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 In computer science, a linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes whic ...
FIFO
C++ C++ (pronounced "C plus plus") is a high-level general-purpose programming language created by Danish computer scientist Bjarne Stroustrup as an extension of the C programming language, or "C with Classes". The language has expanded significan ...
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 as ...
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 In computer science, inter-process communication or interprocess communication (IPC) refers specifically to the mechanisms an operating system provides to allow the processes to manage shared data. Typically, applications can use IPC, categori ...
, a FIFO is another name for a
named pipe In computing, a named pipe (also known as a FIFO for its behavior) is an extension to the traditional pipe concept on Unix and Unix-like systems, and is one of the methods of inter-process communication (IPC). The concept is also found in OS/2 and ...
. Disk controllers can use the FIFO as a
disk scheduling Input/output (I/O) scheduling is the method that computer operating systems use to decide in which order I/O operations will be submitted to storage volumes. I/O scheduling is sometimes called disk scheduling. Purpose I/O scheduling usually ...
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 mu ...
s,
switches In electrical engineering, a switch is an electrical component that can disconnect or connect the conducting path in an electrical circuit, interrupting the electric current or diverting it from one conductor to another. The most common type of ...
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 Electronic may refer to: *Electronics, the science of how to control electric energy in semiconductor * ''Electronics'' (magazine), a defunct American trade journal *Electronic storage, the storage of data using an electronic device *Electronic co ...
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 Pointer may refer to: Places * Pointer, Kentucky * Pointers, New Jersey * Pointers Airport, Wasco County, Oregon, United States * The Pointers, a pair of rocks off Antarctica People with the name * Pointer (surname), a surname (including a l ...
, 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'' differen ...
(SRAM),
flip-flops Flip-flops are a type of light sandal, typically worn as a form of casual footwear. They consist of a flat sole held loosely on the foot by a Y-shaped strap known as a toe thong that passes between the first and second toes and around both side ...
, 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 Fairchild Semiconductor International, Inc. was an American semiconductor company based in San Jose, California. Founded in 1957 as a division of Fairchild Camera and Instrument, it became a pioneer in the manufacturing of transistors and of int ...
. Alfke was later a director at
Xilinx Xilinx, Inc. ( ) was an American technology and semiconductor company that primarily supplied programmable logic devices. The company was known for inventing the first commercially viable field-programmable gate array (FPGA) and creating the fi ...
.


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 In chemistry and physics, metastability denotes an intermediate energetic state within a dynamical system other than the system's state of least energy. A ball resting in a hollow on a slope is a simple example of metastability. If the ball i ...
issues. A common implementation of an asynchronous FIFO uses a
Gray code The reflected binary code (RBC), also known as reflected binary (RB) or Gray code after Frank Gray, is an ordering of the binary numeral system such that two successive values differ in only one bit (binary digit). For example, the representati ...
(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, and thus has two
pointers Pointer may refer to: Places * Pointer, Kentucky * Pointers, New Jersey * Pointers Airport, Wasco County, Oregon, United States * The Pointers, a pair of rocks off Antarctica People with the name * Pointer (surname), a surname (including a l ...
: * 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 In a computer, the memory address register (MAR) is the CPU register that either stores the memory address from which data will be fetched to the CPU registers, or the address to which data will be sent and stored via system bus. In other words, ...
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 The bit is the most basic unit of information in computing and digital communications. The name is a portmanteau of binary digit. The bit represents a logical state with one of two possible values. These values are most commonly represente ...
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 In computing, bit numbering is the convention used to identify the bit positions in a binary number. Bit significance and indexing In computing, the least significant bit (LSB) is the bit position in a binary integer representing the binary 1 ...
and the rest are equal, the FIFO is full.


See also

*
FIFO and LIFO accounting FIFO and LIFO accounting are methods used in managing inventory and financial matters involving the amount of money a company has to have tied up within inventory of produced goods, raw materials, parts, components, or feedstocks. They are used to ...
* FINO *
Queueing theory Queueing theory is the mathematical study of waiting lines, or queues. A queueing model is constructed so that queue lengths and waiting time can be predicted. Queueing theory is generally considered a branch of operations research because the ...


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