What Is FIFO?

FIFO, short for first-in, first-out, is an ordering principle for data processing in which the first element inserted into a collection is the first element removed. It describes both a data structure and a scheduling discipline used throughout computer science, operating systems, and hardware design. The term comes from inventory and queuing theory but is applied broadly wherever order of arrival must determine order of service.

The canonical data structure implementing FIFO is the queue, which maintains a front end for removal (dequeue) and a rear end for insertion (enqueue). Both operations run in O(1) time when implemented with a circular array or a singly linked list, making queues efficient even at large scale. FIFO stands in contrast to LIFO (last-in, first-out), the ordering principle behind stacks, where the most recently inserted element is removed first.

Queue Data Structure and Implementation

A queue stores elements in sequence and guarantees that retrieval preserves insertion order. In practice, queues are implemented as arrays with head and tail pointers, linked lists, or ring buffers. Ring buffers (also called circular queues) are common in hardware and embedded systems because they allow bounded, fixed-memory operation without dynamic allocation. Thread-safe and lock-free variants, which use atomic compare-and-swap operations, are used in concurrent systems where multiple threads enqueue or dequeue simultaneously. The ScienceDirect overview of first-in-first-out structures surveys how FIFO queues appear in both classical and concurrent algorithm design.

Scheduling and Resource Management

Beyond data structures, FIFO names a scheduling policy in which processes, threads, or I/O requests are served in the order they arrive. Operating system schedulers apply FIFO (also called FCFS, first-come, first-served) to run queues and disk I/O queues. Network routers use FIFO queuing as the baseline packet-scheduling discipline before more sophisticated policies such as weighted fair queuing are applied. Memory systems use FIFO replacement policies for cache and TLB management, evicting the oldest resident entry when space is needed. Hardware FIFOs are small, dedicated memories built into chips to buffer data between components operating at different clock rates, a pattern common in digital signal processing pipelines and peripheral interfaces such as UART receive buffers. The POSIX standard (IEEE Std 1003.1) defines FIFO special files as named pipes, allowing unrelated processes to communicate through a kernel-managed first-in, first-out byte stream.

Hardware FIFO Buffers

In digital hardware design, a FIFO buffer is a synchronizer used to transfer data between two clock domains or to absorb bursts of incoming data. The depth of the buffer determines how many items can be held before the producer must stall or data is dropped. Hardware description languages such as VHDL and Verilog include standard templates for synthesizing FIFO blocks, and FPGA vendors supply parameterized FIFO IP cores. Dual-clock FIFOs, which use separate read and write clocks, are standard components in system-on-chip designs where different subsystems operate at different frequencies. The correct sizing of a hardware FIFO is a classical problem in design: too shallow causes overflow, too deep wastes area and power.

Applications

FIFO ordering has applications across a wide range of systems and disciplines, including:

• Operating system process scheduling, where tasks are dispatched in arrival order
• Network packet queuing in routers and switches
• Print spoolers and job queues in batch processing systems
• Hardware serial interfaces (UART, SPI, I2C) using receive and transmit FIFOs
• Audio and video streaming buffers that absorb jitter between producer and consumer
• Breadth-first search algorithms, which rely on queue traversal order

The principle is also foundational in queuing theory, where the M/M/1/FIFO model provides a baseline for analyzing throughput and wait times in systems ranging from telephone networks to manufacturing lines. A thorough treatment of queue-based scheduling appears in the Princeton course notes on algorithms and data structures.