World Library  
Flag as Inappropriate
Email this Article

FIFO (computing and electronics)

Article Id: WHEBN0000011347
Reproduction Date:

Title: FIFO (computing and electronics)  
Author: World Heritage Encyclopedia
Language: English
Subject: SCHED DEADLINE, Variable-length buffer, Snapshot algorithm, Queue, IronMQ
Publisher: World Heritage Encyclopedia

FIFO (computing and electronics)

Representation of a FIFO (queue) with enqueue and dequeue operations.

FIFO is an queue with first-come, first-served (FCFS) behaviour: where the people leave the queue in the order in which they arrive.

FCFS is also the jargon term for the FIFO operating system scheduling algorithm, which gives every process central processing unit (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.[1]

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, as well as interactions between strict-FIFO queues.

Computer science

Data structure

Representation of a FIFO (first in, first out) queue

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


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 std::list template, avoiding the need for implementing the data structure from scratch.

class FIFO

    struct Node {
        T     value;
        Node *next;

        Node(T _value) : value(_value), next(NULL) {}

    Node *front;
    Node *back;

    FIFO() : front(NULL), back(NULL) {}

    ~FIFO() {
        while (front != NULL)

    void enqueue(T _value) {
        Node *newNode = new Node(_value);

        if (front == NULL)
            front = newNode;
            back->next = newNode;

        back = newNode;

    T dequeue() {
        if (front == NULL)
           throw std::underflow_error("Nothing to dequeue");

        Node *temp   = front;        
        T     result = front->value;

        front = front->next;
        delete temp;

        return result;

Head or tail first

The ends of a FIFO queue are often referred to as head and tail. Unfortunately, a controversy exists regarding those terms:

  • To many people, items should enter a queue at the tail, and 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 items 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 could be considered authoritative, such as the operating system Linux.


In computing environments that support the pipes and filters model for interprocess communication, a FIFO is another name for a named pipe.

Disk scheduling

Disk controllers can use the FIFO as a disk scheduling algorithm to determine the order in which to service disk I/O requests.

Communications and networking

Communication network bridges, switches and routers used in computer networks use FIFOs to hold data packets en 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.


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

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 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 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 later a Director at Xilinx.

FIFO full-empty

A 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 the read address register reaches the write address register, the FIFO triggers the Empty signal.
When the write address register reaches the read address register, the FIFO triggers the FULL signal.

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:

  1. When the read address register equals the write address register, the FIFO is empty.
  2. When the read address LSBs equal the write address LSBs and the extra MSBs are different, the FIFO is full.

See also

Notes and references

  1. ^
  • Cummings et al., Simulation and Synthesis Techniques for Asynchronous FIFO Design with Asynchronous Pointer Comparisons, SNUG San Jose 2002
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.

Copyright © World Library Foundation. All rights reserved. eBooks from Hawaii eBook Library are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.