 | This articleneeds additional citations forverification. Please helpimprove this article byadding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "FIFO" computing and electronics – news ·newspapers ·books ·scholar ·JSTOR(March 2015) (Learn how and when to remove this message) |
In computing and insystems theory,first in, first out (the first in is the first out),acronymized asFIFO, is a method for organizing the manipulation of a data structure (often, specifically adata buffer) where the oldest (first) entry, or "head" of thequeue, is processed first.
Such processing is analogous to servicing people in aqueue area on afirst-come, first-served (FCFS) basis, i.e. in the same sequence in which they arrive at the queue's tail.
FCFS is also thejargon term for the FIFOoperating system scheduling algorithm, which gives every processcentral processing unit (CPU) time in the order in which it is demanded.[1] FIFO's opposite isLIFO, last-in-first-out, where the youngest entry or "top of the stack" is processed first.[2] Apriority queue is neither FIFO or LIFO but may adopt similar behaviour temporarily or by default.Queueing theory encompasses these methods for processingdata structures, as well as interactions between strict-FIFO queues.
Depending on the application, a FIFO could be implemented as a hardware shift register, or using different memory structures, typically acircular buffer or a kind oflist. For information on the abstract data structure, seeQueue (data structure). Most software implementations of a FIFO queue are notthread 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 alinked list FIFOC++ 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;}};
In computing environments that support thepipes-and-filters model forinterprocess communication, a FIFO is another name for anamed pipe.
Disk controllers can use the FIFO as adisk scheduling algorithm to determine the order in which to service diskI/O requests, where it is also known by the same FCFS initialism as for CPU scheduling mentioned before.[1]
Communicationnetwork bridges,switches androuters used incomputer 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.[3]
FIFOs are commonly used inelectronic circuits for buffering and flow control between hardware and software. In its hardware form, a FIFO primarily consists of a set of read and writepointers, storage and control logic. Storage may bestatic random access memory (SRAM),flip-flops, latches or any other suitable form of storage. For FIFOs of non-trivial size, a dual-port SRAM is usually used, where one port is dedicated to writing and the other to reading.
The first known FIFO implemented in electronics was by Peter Alfke in 1969 atFairchild Semiconductor.[4] Alfke was later a director atXilinx.
A synchronous FIFO is a FIFO where the same clock is used for both reading and writing. An asynchronous FIFO uses different clocks for reading and writing and they can introducemetastability issues. A common implementation of an asynchronous FIFO uses aGray code (or any unit distance code) for the read and write pointers to ensure reliable flag generation. One further note concerning flag generation is that one must necessarily use pointer arithmetic to generate flags for asynchronous FIFO implementations. Conversely, one may use either aleaky bucket approach or pointer arithmetic to generate flags in synchronous FIFO implementations.
A hardware FIFO is used for synchronization purposes. It is often implemented as acircular queue, and thus has twopointers:
Examples of FIFO status flags include: full, empty, almost full, and almost empty. A FIFO is empty when the readaddress register reaches the write address register. A FIFO is full when the write address register reaches the read address register. Read and write addresses are initially both at the first memory location and the FIFO queue isempty.
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 extrabit for each read and write address which is inverted each time the address wraps. With this set up, the disambiguation conditions are:
| Single queueing nodes | |
|---|---|
| Arrival processes | |
| Queueing networks | |
| Service policies | |
| Key concepts | |
| Limit theorems | |
| Extensions | |
| Information systems | |
