FACTOID # 24: Looking for table makers? Head to Mississippi, with an overwhlemingly large number of employees in furniture manufacturing.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
RELATED ARTICLES
People who viewed "FIFO" also viewed:
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > FIFO

FIFO is an acronym for First In, First Out. This expression describes the principle of a queue or first-come, first-served (FCFS) behaviour: 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 queueing (or "standing in line", in common American parlance), 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. In a stack, the topmost item, which is added last, is taken out first. ... It has been suggested that this article or section be merged with Backronym and Apronym (Discuss) Acronyms and initialisms are abbreviations, such as NATO, laser, and ABC, written as the initial letter or letters of words, and pronounced on the basis of this abbreviated written form. ... A queue (pronounced /kuː/) is a particular kind of collection in which the entities in the collection are kept in order and the principal (or only) operations on the collection are the addition of entities to the rear terminal position and removal of entities from the front terminal position. ... First come, first served (sometimes first-come, first-served or simply FCFS) 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. ... CPU can stand for: in computing: Central processing unit in journalism: Commonwealth Press Union in law enforcement: Crime prevention unit in software: Critical patch update, a type of software patch distributed by Oracle Corporation in Macleans College is often known as Ash Lim. ...


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. Queueing theory encompasses the more general concept of queue, as well as interactions between strict-FIFO queues. A priority queue is an abstract data type in computer programming, supporting the following three operations: add an element to the queue with an associated priority remove the element from the queue that has the highest priority, and return it (optionally) peek at the element with highest priority without removing... A binary tree, a simple type of branching linked data structure. ... Queueing theory (also commonly spelled queuing theory) is the mathematical study of waiting lines (or queues). ...


The expression FIFO can be used in different contexts.

Contents

People

Queue at US Air Force station in Iraq, for food at a birthday celebration. Queue areas are areas in which people queue (first-come, first-served), that is they wait in line for something. ...

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. Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ... In a stack, the topmost item, which is added last, is taken out first. ... Simple representation of a stack In computer science, a stack is a temporary abstract data type and data structure based on the principle of Last In First Out (LIFO). ...


A typical data structure will look like

 struct fifo_node { struct 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; tempNode->next = back; back = tempNode; } } 

(For information on the abstract data structure, see Queue. For details of a common implementation, see Circular buffer.) A queue (pronounced /kuː/) is a particular kind of collection in which the entities in the collection are kept in order and the principal (or only) operations on the collection are the addition of entities to the rear terminal position and removal of entities from the front terminal position. ... A circular buffer is a method of using memory within a computer program. ...


Popular UNIX systems include a sys/queue.h C/C++ header file which provides macros usable by applications which need to create FIFO queues.


Head or tail first

Authors and users of FIFO queue software should consider carefully the use of the terms "head" and "tail" to refer to the two ends of the queue. 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, however, believe that you 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, making the point of view hard to dismiss however repugnant you find the idea of getting your data from a snake's rear-end.


Pipes

In computing environments that support the pipes and filters model for interprocess communication, a FIFO is another name for a named pipe. In software engineering, a pipeline consisting of chain of processes or other data processing entities, arranged so that the output of each element of the chain is the input of the of the next one. ... Inter-process communication (IPC) is the exchange of data between one process and another, either within the same computer or over a network. ... In computing, a named pipe (also FIFO for its behaviour) is an extension to the traditional pipe concept on Unix and Unix-like systems, and is one of the methods of inter-process communication. ...


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. This article is about the engineering discipline. ...


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. A metastable system with a weakly stable state (1), an unstable transition state (2) and a strongly stable state (3) Metastability is the ability of a non-equilibrium state to persist for some period of time. ... 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 digit. ... Although the leaky bucket algorithm has several uses, it is best understood in the context of network traffic shaping or rate limiting. ...


Examples of FIFO status flags include: full, empty, almost full, or almost empty.


The first known FIFO implemented in electronics is done by Peter Alfke in 1969 at Fairchild Semiconductors. Peter Alfke is now a Director at Xilinx. Xilinx, Inc. ...


FIFO FULL/EMPTY

In hardware FIFO is used for synchronization purposes. It is often implemented as a circular queue, and thus has two pointers: ...


1. Read Pointer/Read Address Register


2. 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.


See also

In a stack, the topmost item, which is added last, is taken out first. ... Garbage In, Garbage Out (abbreviated to GIGO) is an aphorism in the field of computer science. ...

References

  • Cummings et al., Simulation and Synthesis Techniques for Asynchronous FIFO Design with Asynchronous Pointer Comparisons, SNUG San Jose 2002

  Results from FactBites:
 
EDN Access--03.14.97 FIFO memories supply the glue for high-speed systems (2198 words)
The disadvantage of a strobed FIFO device is that it cannot fully synchronize the status signals with the corresponding clock signals.
Clocked FIFOs are similar, except that during writes or reads the system sometimes (depending on the device) asserts the chip select, and the input (output) flag is multistage synchronized to the write (read) clock.
This scheme ensures that the upstream FIFO device does not attempt to force another data word upon the downstream FIFO device when the downstream device is full and vice versa for reads when the device is empty.
  More results at FactBites »

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m