FIFO is an acronym for First In, First Out, an abstraction related to ways of organizing and manipulation of data relative to time and prioritization. This expression describes the principle of a queue processing technique or servicing conflicting demands by ordering process by first-come, first-served
First-come, first-served
First-come, first-served – sometimes first-in, first-served and first-come, first choice – is a service policy whereby 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 sales orders,...
(FCFS) behaviour: what comes in first is handled first, what comes in next waits until the first is finished, analogous to the behaviour of persons standing in line, where the persons leave the queue in the order they arrive, or waiting one's turn at a traffic control signal.
Jargon is terminology which is especially defined in relationship to a specific activity, profession, group, or event. The philosophe Condillac observed in 1782 that "Every science requires a special language because every science has its own ideas." As a rationalist member of the Enlightenment he...
term for the FIFO operating system scheduling algorithm, which gives every process CPU
Central processing unit
The central processing unit is the portion of a computer system that carries out the instructions of a computer program, to perform the basic arithmetical, logical, and input/output operations of the system. The CPU plays a role somewhat analogous to the brain in the computer. The term has been in...
time in the order they come. In the broader sense, the abstraction LIFO, or Last-In-First-Out is the opposite of the abstraction FIFO organization. The difference perhaps is clearest with considering the less commonly used synonym of LIFO, FILO (meaning First-In-Last-Out). In essence, both are specific cases of a more generalized list (which could be accessed anywhere). The difference is not in the list (data), but in the rules for accessing the content. One sub-type adds to one end, and takes off from the other, its opposite takes and puts things only on one end.
A slang variation on an ad-hoc approach to removing items from the queue has been coined as OFFO, which stands for On-Fire-First-Out.
A priority queue
Priority queue
A priority queue is an abstract data type in computer programming.It is exactly like a regular queue or stack data structure, but additionally, each element is associated with a "priority"....
is a variation on the queue which does not qualify for the name FIFO, because it is not accurately descriptive of that data structure
Data structure
In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks...
Queueing theory is the mathematical study of waiting lines, or queues. The theory enables mathematical analysis of several related processes, including arriving at the queue, waiting in the queue , and being served at the front of the queue...
encompasses the more general concept of queue, as well as interactions between strict-FIFO queues.
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
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
Stack (data structure)
In computer science, a stack is a last in, first out abstract data type and linear data structure. A stack can have any abstract data type as an element, but is characterized by only three fundamental operations: push, pop and stack top. The push operation adds a new item to the top of the stack,...
algorithms.
A typical data structure will look like
struct fifo_node
{
struct fifo_node *next;
value_type value;
};
queue(value)
{
fifo_node *tempNode = new fifo_node;
tempNode->value = value;
back->next = tempNode;
back = tempNode;
}
};
(For information on the abstract data structure, see Queue. For details of a common implementation, see Circular buffer
Circular buffer
A circular buffer, 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.-Uses:...
C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell...
header file which provides macros usable by applications which need to create FIFO queues.
Head or tail first
Controversy over the terms "head" and "tail" exists in reference to FIFO queues. To many people, items should enter a queue at the tail, remain in the queue until they reach the head and leave the queue from there. This point of view is justified by analogy with queues of people waiting for some kind of service and parallels the use of "front" and "back" in the above example. Other people believe that objects enter a queue at the head and leave at the tail, in the manner of food passing through a snake. Queues written in that way appear in places that might be considered authoritative, such as the GNU/Linux operating system
Operating system
An operating system is a set of programs that manage computer hardware resources and provide common services for application software. The operating system is the most important type of system software in a computer system...
.
Pipes
In computing environments that support the pipes and filters model for interprocess communication, a FIFO is another name for a named pipe
Named pipe
In computing, a named pipe is an extension to the traditional pipe concept on Unix and Unix-like systems, and is one of the methods of inter-process communication. The concept is also found in Microsoft Windows, although the semantics differ substantially...
.
Disk scheduling
Disk controllers can use the FIFO as a disk scheduling algorithm to determine the order to service disk I/O requests.
A network switch or switching hub is a computer networking device that connects network segments.The term commonly refers to a multi-port network bridge that processes and routes data at the data link layer of the OSI model...
and routers used in Computer networks 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 is the branch of science, engineering and technology that deals with electrical circuits involving active electrical components such as vacuum tubes, transistors, diodes and integrated circuits, and associated passive interconnection technologies...
circuits for buffering and flow control which is from hardware to software. In hardware form a FIFO primarily consists of a set of read and write pointers, storage and control logic. Storage may be SRAM
Static random access memory
Static random-access memory is a type of semiconductor memory where the word static indicates that, unlike dynamic RAM , it does not need to be periodically refreshed, as SRAM uses bistable latching circuitry to store each bit...
, 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
Metastability
Metastability describes the extended duration of certain equilibria acquired by complex systems when leaving their most stable state after an external action....
issues.
A common implementation of an asynchronous FIFO uses a Gray code
Gray code
The reflected binary code, also known as Gray code after Frank Gray, is a binary numeral system where two successive values differ in only one bit. It is a non-weighted 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
Leaky bucket
The leaky bucket is an algorithm used in packet switched computer networks and telecommunications networks to check that data transmissions conform to defined limits on bandwidth and burstiness . The leaky bucket algorithm is also used in leaky bucket counters, e.g...
" approach or pointer arithmetic to generate flags in synchronous FIFO implementations.
Examples of FIFO status flags include: full, empty, almost full, almost empty, etc.
The first known FIFO implemented in electronics was done by Peter Alfke in 1969 at Fairchild Semiconductors. Peter Alfke was a Director at Xilinx
Xilinx
Xilinx, Inc. is a supplier of programmable logic devices. It is known for inventing the field programmable gate array and as the first semiconductor company with a fabless manufacturing model....
.
FIFO full/empty
In hardware FIFO is used for synchronization purposes. It is often implemented as a circular queue, and thus has two pointers:
Read Pointer/Read Address Register
Write Pointer/Write Address Register
Read and write addresses are initially both at the first memory location and the FIFO queue is Empty.
FIFO Empty: When read address register reaches to write address register, the FIFO triggers the Empty signal.
FIFO FULL: When write address register reaches to read address register, the FIFO triggers the FULL signal.
Garbage in, garbage out is a phrase in the field of computer science or information and communication technology. It is used primarily to call attention to the fact that computers will unquestioningly process the most nonsensical of input data and produce nonsensical output...
(Garbage In, Garbage Out)
The source of this article is wikipedia, the free encyclopedia. The text of this article is licensed under the GFDL.
