FIFO (computing and electronics): Difference between revisions

Revision as of 22:17, 30 October 2021

Latest revision as of 04:19, 19 May 2025

(14 intermediate revisions by 13 users not shown)

Line 1:

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

{{refimprovemore citations needed|date=March 2015}}

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

In computing and in [[systems theory]], '''FIFO''' 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 68:

FIFOs are commonly used in [[electronics|electronic]] circuits for buffering and flow control between hardware and software. In its hardware form, a FIFO primarily consists of a set of read and write [[Pointer (computer programming)|pointers]], storage and control logic. Storage may be [[static random access memory]] (SRAM), [[Flip-flop (electronics)|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 at [[Fairchild Semiconductor]].<ref name="Alfke">[{{cite web| url = http://www.fpga-faq.com/archives/10775.html#10794| title = Peter Alfke's post at comp.arch.fpga on 19 Jun 1998]}}</ref> Alfke was later a director at [[Xilinx]].

=== Synchronicity ===

Line 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 address 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 89:

* [[FINO]]

* [[Queueing theory]]

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

== References ==

{{reflistReflist}}

== 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]