FIFO (computing and electronics)

Representation of a FIFO queue

Representation of a FIFO queue with enqueue and dequeue operations

A FIFO schedule

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.

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

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 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>usingnamespacestd;template<typenameT>classFIFO{structNode{Tvalue;shared_ptr<Node>next=nullptr;Node(T_value):value(_value){}};shared_ptr<Node>front=nullptr;shared_ptr<Node>back=nullptr;public:voidenqueue(T_value){if(front==nullptr){front=make_shared<Node>(_value);back=front;}else{back->next=make_shared<Node>(_value);back=back->next;}}Tdequeue(){if(front==nullptr)throwunderflow_error("Nothing to dequeue");Tvalue=front->value;front=move(front->next);returnvalue;}};

Electronic FIFO

Main article: FIFO (electronic)

Integrated circuit, 5,048 words by 8 bits FIFO (NEC D485505g-25)

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

See also

• FINO
• Leaky bucket approach
• Queueing theory
• SCHED_FIFO

References

1. Andrew S. Tanenbaum; Herbert Bos (2015). Modern Operating Systems. Pearson. ISBN   978-0-13-359162-0.
2. James F. Kurose; Keith W. Ross (July 2006). Computer Networking: A Top-Down Approach. Addison-Wesley. ISBN   978-0-321-41849-4.

External links

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