FIFO (computing and electronics): Difference between revisions

Revision as of 14:15, 21 July 2022

Latest revision as of 04:19, 19 May 2025

(9 intermediate revisions by 8 users not shown)

Line 1:

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

{{more citations needed|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.

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

Such processing is analogous to servicing people in a [[queue area]] on a [[first-come, first-served]] (FCFS) basis, i.e. in the same sequence in which they arrive at the queue's tail.

FCFS is also the [[jargon]] term for the FIFO [[Scheduling (computing)|operating system scheduling]] algorithm, which gives every process [[central processing unit]] (CPU) time in the order in which it is demanded.<ref name="TanenbaumBos2015">{{cite book|author1=Andrew S. Tanenbaum|author2=Herbert Bos|title=Modern Operating Systems|url=https://books.google.com/books?id=9gqnngEACAAJ|year=2015|publisher=Pearson|isbn=978-0-13-359162-0}}</ref> FIFO's opposite is [[LIFO (computing)|LIFO]], last-in-first-out, where the youngest entry or "top of the stack" is processed first.<ref name="Kruse">{{ cite book | last = Kruse | first = Robert L. | title = Data Structures & Program Design (second edition) | edition = second (hc) textbook | orig-year = 1984 | year = 1987 | others = Joan L. Stone, Kenny Beck, Ed O'Dougherty (production process staff workers) | publisher = Prentice-Hall, Inc. div. of Simon & Schuster | ___location = Englewood Cliffs, New Jersey 07632 | isbn = 0-13-195884-4 | pages = 150 | url-access = registration | url = https://archive.org/details/datastructurespr0000krus_n1p0/page/150 }}</ref> A [[priority queue]] is neither FIFO or LIFO but may adopt similar behaviour temporarily or by default. [[Queueing theory]] encompasses these methods for processing [[data structures]], as well as interactions between strict-FIFO queues.

== Computer science ==

Line 12 ⟶ 14:

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 77 ⟶ 79:

=== 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 0addressaddress 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:

* When the read address register equals the write address register, the FIFO is empty.

* When the read addressand [[Bitwrite numbering#Leastaddress significantregisters bit|leastdiffer significantonly bit]] (LSB) equals the write address LSBs andin the extra [[Bit numbering#Most significant bit|most significant bit]] and the rest are differentequal, the FIFO is full.

== See also ==

Line 87 ⟶ 89:

* [[FINO]]

* [[Queueing theory]]

* <code>[[SCHED_FIFO]]</code>

== References ==

Line 92 ⟶ 95:

== External links ==

* [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]

* Removi

*

{{Authority control}}