FIFO (computing and electronics)

Scheduling algorithm, the first piece of data inserted into a queue is processed first From Wikipedia, the free encyclopedia

In computing and in systems theory, first in, first out (the first in is the first out), acronymized as FIFO, is a method for organizing the manipulation of a data structure (often, specifically a data buffer) where the oldest (first) entry, or "head" of the queue, is processed first.

Representation of a FIFO queue
Representation of a FIFO queue with enqueue and dequeue operations
A FIFO schedule

FIFOs are used for a wide variety of applications. Depending on the application, a FIFO may be implemented in hardware as an electronic logic circuit, or in software.

Applications

Disk controllers use a FIFO as a disk scheduling algorithm to determine the order in which to service disk I/O requests.[1] 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.[2] FIFO is analogous to first-come, first-served (FCFS), 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.[1]

Software FIFO

Software FIFOs typically are based on a circular buffer or list structure. Most software implementations are not thread safe and require a locking mechanism to ensure the data structure chain is being manipulated by only one thread at a time.

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

C++ language example

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;
        shared_ptr<Node> next = nullptr;

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

    shared_ptr<Node> front = nullptr;
    shared_ptr<Node> back  = nullptr;

public:
    void enqueue(T _value) {
        if (front == nullptr) {
            front = make_shared<Node>(_value);
            back = front;
        } else {
            back->next = make_shared<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;
    }
};

Electronic FIFO

Electronic FIFOs are commonly used for buffering and flow control between hardware devices or between software and hardware devices which, over finite intervals, operate at different data rates. A FIFO primarily consists of a pair of counters that serve as read and write memory address registers, an addressable memory array, and status and control logic. The memory typically is dual-ported to allow concurrent FIFO read and write operations, and consists of a register file or dual-ported RAM (random access memory).

Excerpt of a FIFO schematic showing memory address registers and dual-port RAM

Memory address registers

An electronic FIFO is typically implemented as a circular buffer which employs two memory address registers (MARs) to store the addresses of (pointers to) the next memory locations to be accessed:

  • Read MAR (RMAR) - contains next location to read data from
  • Write MAR (WMAR) - contains next location to write data to

Each MAR is implemented as a counter, with the count incremented every time data is transferred (WMAR incremented upon FIFO write; RMAR incremented upon FIFO read). Initially both MARs point to the first memory location and the FIFO is empty. A FIFO becomes full when the write address reaches the read address, and empty when the read address reaches the write address. Consequently, upon FIFO becoming full or empty, the read and write memory addresses are equal.

To distinguish between empty and full, each MAR has an additional bit beyond what is needed to address memory. All MAR output bits except the most significant bit (MSB) (i.e., the LSBs) serve as the memory address. Conversely, all output bits, including the MSB, are used to monitor the FIFO level (number of words stored). In cases where the MARs employ binary counters, the current FIFO level is the difference between their binary output values: . For other output encodings (e.g., Gray code), the MAR outputs must be converted to binary before computing the difference. In either case, the following hold true:

  • The FIFO is empty when RMAR and WMAR are equal
  • The FIFO is full when RMAR and WMAR differ only in their MSBs

Status flags

A FIFO typically outputs status signals that indicate whether particular data level thresholds are met. Common examples of such status flags include full, empty, half full, almost full, and almost empty.

Synchronous FIFO

Symbolic representation of a synchronous FIFO

A synchronous FIFO is an electronic FIFO that uses a common clock for reading and writing. Because read and write operations take place in the same clock domain, flags may be generated via either pointer arithmetic or by using a dedicated counter to monitor the FIFO level.

Asynchronous FIFO

Symbolic representation of an asynchronous FIFO

An asynchronous FIFO is an electronic FIFO that uses different clocks for reading and writing. To avoid errors due to metastability, asynchronous FIFOs typically use Gray code for the read and write pointers, and flags are generated via pointer arithmetic.

See also

References

External links

Related Articles

Wikiwand AI