FIFO (computing and electronics)

FIFOs are used extensively, in a wide variety of applications. For example, 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 is used per network connection.^[2] FIFOs are used in operating system scheduling to give every process central processing unit (CPU) time in the order in which it is demanded.^[1] FIFOs are used to buffer digital video and audio streams, to facilitate the exchange of stream data between software or hardware (or both) that would otherwise have incompatible data rates.

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.

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

• FINO
• Leaky bucket approach
• Queueing theory
• SCHED_FIFO