FIFO (computing and electronics): Difference between revisions

Revision as of 21:13, 30 January 2020

Latest revision as of 04:19, 19 May 2025

(47 intermediate revisions by 37 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:Fifo queue.png|thumb|350px|Representation of a FIFO (queue) with ''enqueue'' and ''dequeue'' operations.]]

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

In computing and in [[systems theory]], '''FIFOfirst in, first out''' (the first in is anthe first out), [[acronym]]ized foras '''first in, first outFIFO''', is a method for organisingorganizing andthe manipulatingmanipulation of a data bufferstructure (often, specifically a [[data buffer]]) where the oldest (first) entry, or '"head'" of the queue, is processed first. It is analogous to processing a [[Queue (data structure)|queue]], withis [[first-come,processed first-served]] (FCFS) behaviour: where the people leave the queue in the order in which they arrive.

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. 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|origyear=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|quote="The definition of a finite sequence immediately makes it possible for us to attempt a definition of a list: A 'list' of terms of type T is simply a finite sequence of elements of the set T. ... The only difference among stacks and queues and more general lists is the '''operations''' by which changes or accesses can be made to the list."|pages=[https://archive.org/details/datastructurespr0000krus_n1p0/page/150 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]]<nowiki/>, as well as interactions between strict-FIFO queues.

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 |origyear 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 |quote="The definitionpages of= a150 finite sequence immediately makes it possible for us to attempt a definition of a list: A 'list' of terms of type T is simply a finite sequence of elements of the set T. ... The only difference among stacks and queues and more general lists is the '''operations''' by which changes or accesses can be made to the list."|pages=[https://archive.org/details/datastructurespr0000krus_n1p0/page/150 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]]<nowiki/>, as well as interactions between strict-FIFO queues.

==Computer science==

== Computer science ==

===Data structure===

[[Imagefile:DataFifo Queuequeue.svgpng|thumb|300px|Representation of a FIFO (firstqueue in,with firstenqueue out)and queuedequeue operations.]]

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.

{{clear}}

=== Code ===

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.

<sourcesyntaxhighlight lang="cpp">

#include <memory>

#include <stdexcept>

Line 27 ⟶ 26:

struct Node {

T value;

unique_ptrshared_ptr<Node> next = nullptr;

Node(T _value): value(_value) {}

};

unique_ptrshared_ptr<Node> front = nullptr;

unique_ptrshared_ptr<Node>* back = &frontnullptr;

public:

void enqueue(T _value) {

backif (front == make_unique<Node>(_valuenullptr); {

back front = &make_shared<Node>(**back_value).next;

back = front;

} else {

back->next = make_shared<Node>(_value);

back = back->next;

}

}

Line 45 ⟶ 49:

throw underflow_error("Nothing to dequeue");

unique_ptr<Node>T tempvalue = nullptrfront->value;

temp.swapfront = move(front->next);

front.swap(temp);

return temp->value;

return temp->value;

}

};

</syntaxhighlight>

</source>

In computing environments that support the [[pipes and filters|pipes-and-filters]] model for [[interprocess communication]], a FIFO is another name for a [[named pipe]].

===Head or tail first===

Disk controllers can use the FIFO as a [[I/O scheduling|disk scheduling]] algorithm to determine the order in which to service disk [[Input/output|I/O]] requests, where it is also known by the same FCFS initialism as for CPU scheduling mentioned before.<ref name="TanenbaumBos2015"/>

The ends of a FIFO queue are often referred to as ''head'' and ''tail''. Unfortunately, a controversy exists regarding those terms:

* To many people, items should enter a queue at the tail, and remain in the queue until they reach the head and leave the queue from there. This point of view is justified by analogy with queues of people waiting for some kind of service and parallels the use of ''front'' and ''back'' in the above example.

* Other people believe that items enter a queue at the head and leave at the tail, in the manner of food passing through a snake. Queues written in that way appear in places that could be considered authoritative, such as the [[operating system]] [[Linux]].

Communication [[network bridge]]s, [[Network switch|switches]] and [[Network router|routers]] used in [[computer networksnetwork]]s use FIFOs to hold data packets enin 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.<ref name="KuroseRoss2006">{{cite book|author1=James F. Kurose|author2=Keith W. Ross|title=Computer Networking: A Top-Down Approach|url=https://books.google.com/books?id=QXIwPwAACAAJ|date=July 2006|publisher=Addison-Wesley|isbn=978-0-321-41849-4}}</ref>

===Pipes===

In computing environments that support the [[pipes and filters]] model for [[interprocess communication]], a FIFO is another name for a [[named pipe]].

===Disk scheduling=Electronics ==

[[Filefile:Fifo schedule.png|thumb|400px|A FIFO schedule.]]

Disk controllers can use the FIFO as a disk scheduling algorithm to determine the order in which to service disk I/O requests.

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.

===Communications and networking===

Communication [[network bridge]]s, [[Network switch|switches]] and [[Network router|routers]] used in [[computer networks]] use FIFOs to hold data packets en 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.

The first known FIFO implemented in electronics was done by Peter Alfke in 1969 at [[Fairchild Semiconductors 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>. Peter Alfke was later a director at [[Xilinx]].

==Electronics==

=== Synchronicity ===

[[File:Fifo schedule.png|thumb|FIFO schedule.]]

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 introduce [[metastability]] issues. A common implementation of an asynchronous FIFO uses a [[Gray 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 a ''[[leaky 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 a [[circular queue]], and thus has two [[Pointer (computer programming)|pointers]]:

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 pointers, storage and control logic. Storage may be [[static 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.

#* Read pointer / read address register

#* Write pointer / write address register

=== Status flags ===

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. Asynchronous FIFOs introduce [[metastability]] issues.

A common implementation of an asynchronous FIFO uses a [[Gray 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 a ''[[leaky bucket]]'' approach or pointer arithmetic to generate flags in synchronous FIFO implementations.

Examples of FIFO status flags include: full, empty, almost full, and almost empty,. etcA 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:

The first known FIFO implemented in electronics was done by Peter Alfke in 1969 at Fairchild Semiconductors <ref>[http://www.fpga-faq.com/archives/10775.html#10794 Peter Alfke's post at comp.arch.fpga on 19 Jun 1998]</ref>. Peter Alfke was later a director at [[Xilinx]].

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

* When the read and write address registers differ only in the extra [[Bit numbering#Most significant bit|most significant bit]] and the rest are equal, the FIFO is full.

=== FIFO full-empty ===

A hardware FIFO is used for synchronization purposes. It is often implemented as a [[circular queue]], and thus has two pointers:

#Read pointer / read address register

#Write pointer / write address register

Read and write addresses are initially both at the first memory ___location and the FIFO queue is ''empty''.

;FIFO empty: When the read [[address register]] reaches the write address register, the FIFO triggers the ''empty'' signal.

;FIFO full: When the write address register reaches the read address register, the FIFO triggers the ''full'' signal.

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 address LSBs equal the write address LSBs and the extra MSBs are different, the FIFO is full.

== See also ==

* [[FIFO and LIFO accounting]]

* [[FINO]] (first in, never out)

* [[Garbage in, garbage outFINO]]

* [[Queueing theory]]

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

== References ==

{{Reflist}}

=== CitationsExternal links ===

{{reflist}}

=== Sources ===

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

Line 110 ⟶ 102:

{{Queueing theory}}

{{DEFAULTSORT:Fifo (Computing)}}

[[Category:Cybernetics]]

[[Category:Scheduling algorithms]]

[[Category:Queue management]]