|
|
| Line 2: |
Line 2: |
| {{more citations needed|date=March 2015}} | | {{more citations needed|date=March 2015}} |
| [[file:Data Queue.svg|thumb|Representation of a FIFO queue]] | | [[file:Data Queue.svg|thumb|Representation of a FIFO queue]] |
| | [[file:Fifo queue.png|thumb|Representation of a FIFO queue with enqueue and dequeue operations]] |
| | [[file:Fifo schedule.png|thumb|A FIFO schedule]] |
|
| |
|
| In computing and in [[systems theory]], '''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. | | In computing and in [[systems theory]], '''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 (abstract data type)|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.
| | FIFOs are used for a wide variety of applications. Depending on the application, a FIFO may be implemented in hardware as an electronic logic circuit, or in software. |
|
| |
|
| 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 | 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.
| | ==Applications== |
|
| |
|
| == Computer science == | | FIFOs are used extensively, in a wide variety of applications. For example, disk controllers use a FIFO as a [[I/O scheduling|disk scheduling]] algorithm to determine the order in which to service disk [[Input/output|I/O]] requests.<ref name="TanenbaumBos2015"/> Communication [[network bridge]]s, [[Network switch|switches]] and [[Network router|routers]] used in [[computer network]]s use FIFOs to hold data packets in route to their next destination; typically at least one FIFO is used per network connection.<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> FIFOs are used in [[Scheduling (computing)|operating system scheduling]] to give 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> FIFOs are used to buffer digital video and audio streams, to facilitate the exchange of stream data between software or hardware (or both) that would otherwise have incompatible data rates. |
| [[file:Fifo queue.png|thumb|300px|Representation of a FIFO queue with enqueue and dequeue 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.
| | ==Software FIFO== |
| | |
| | Software FIFOs typically are based on a [[circular buffer]] or [[List (abstract data type)|list]] structure. Most software implementations are not [[thread safe]] and require a locking mechanism to ensure the data structure chain is being manipulated by only one thread at a time. |
| | |
| | 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]]. |
| | |
| | ===C++ language example=== |
|
| |
|
| 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. | | 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. |
| Line 57: |
Line 64: |
| </syntaxhighlight> | | </syntaxhighlight> |
|
| |
|
| 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]].
| | ==Electronic FIFO== |
| | |
| 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"/>
| |
| | |
| Communication [[network bridge]]s, [[Network switch|switches]] and [[Network router|routers]] used in [[computer network]]s 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.<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>
| |
| | |
| == Electronics ==
| |
| [[file:Fifo schedule.png|thumb|400px|A FIFO schedule]]
| |
| | |
| 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 ===
| | {{Main|FIFO (electronic)}} |
| 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.
| | [[File:ΜPD485505G-25.jpg|thumb|Integrated circuit, 5,048 words by 8 bits FIFO ([[NEC]] D485505g-25)]] |
| | [[FIFO (electronic)|Electronic FIFOs]] are commonly used for buffering and flow control between hardware devices or between software and hardware devices which, over finite intervals, operate at different data rates. |
|
| |
|
| A hardware FIFO is used for synchronization purposes. It is often implemented as a [[circular queue]], and thus has two [[Pointer (computer programming)|pointers]]: | | A FIFO consists of two counters that serve as read and write memory address registers, a memory array, and status and control logic. The memory typically is dual-ported to allow concurrent FIFO read and write operations, and consists of a [[register file]] or [[dual-ported RAM]] (random access memory). |
| * Read pointer / read address register
| |
| * Write pointer / write address register
| |
| | |
| === 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 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.
| |
|
| |
|
| == See also == | | == See also == |
| * [[FIFO and LIFO accounting]]
| |
| * [[FINO]] | | * [[FINO]] |
| | * [[Leaky bucket]] approach |
| * [[Queueing theory]] | | * [[Queueing theory]] |
| * <code>[[SCHED_FIFO]]</code> | | * <code>[[SCHED_FIFO]]</code> |
| Line 94: |
Line 81: |
| {{Reflist}} | | {{Reflist}} |
|
| |
|
| == 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]
| |
|
| |
|
| {{Authority control}} | | {{Authority control}} |
|
| |
| {{Queueing theory}} | | {{Queueing theory}} |
|
| |
|