FIFO (computing and electronics)

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

#include <memory>
#include <stdexcept>

using namespace std;

template <typename T>
class FIFO {
    struct Node {
        T value;
        unique_ptr<Node> next = nullptr;

        Node(T _value): value(_value) {}
    };

    unique_ptr<Node> front = nullptr;
    unique_ptr<Node>* back = &front;

public:
    void enqueue(T _value) {
        *back = make_unique<Node>(_value);
        back = &(**back).next;
    }

    T dequeue() {
        if (front == nullptr)
            throw underflow_error("Nothing to dequeue");

        T value = front->value;
        front = move(front->next);
        
        return value;
    }
};

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 controllers can use the FIFO as a disk scheduling algorithm to determine the order in which to service disk I/O requests.

Communication network bridges, switches 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.

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.

FIFO full

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.

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