FIFO (computing and electronics): Difference between revisions

Revision as of 19:16, 10 June 2022

Revision as of 23:20, 20 July 2022

Line 1:

{{Short description|Scheduling algorithm, the first piece of data inserted into a queue is processed first}}

{{refimprove|date=March 2015}}

[[file:Data Queue.svg|thumb|Representation of a FIFO queue]]

In computing and in [[systems theory]], '''FIFO''' is an [[acronym]] for '''first in, first out''' (the first in is the first out), 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 (data structure)|queue]], is processed first.

Line 14 ⟶ 12:

Depending on the application, a FIFO could be implemented as a hardware shift register, or using different memory structures, typically a [[circular buffer]] or a kind of [[List (abstract data type)|list]]. For information on the abstract data structure, see [[Queue (data structure)]]. Most software implementations of a FIFO queue are not [[thread 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 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 Template Library|standard library]] std::list template, avoiding the need for implementing the data structure from scratch.70

<syntaxhighlight lang="cpp">

Line 79 ⟶ 77:

=== Status flags ===

Examples of FIFO status flags include: full, empty, almost full, and almost empty. A FIFO is empty when the read [[address register]] reaches the write address register. A FIFO is full when the write address register reaches the read address0address register. Read and write addresses are initially both at the first memory ___location and the FIFO queue is ''empty''.

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 extra [[bit]] for each read and write address which is inverted each time the address wraps. With this set up, the disambiguation conditions are:

Line 91 ⟶ 89:

== References ==

{{reflist}}

== External links ==

* Removi

* [http://www.sunburst-design.com/papers/CummingsSNUG2002SJ_FIFO2.pdf Cummings et al., Simulation and Synthesis Techniques for Asynchronous FIFO Design with Asynchronous Pointer Comparisons, SNUG San Jose 2002]

*

{{Authority control}}