FIFO (computing and electronics)
This article needs additional citations for verification. (March 2015) |
In computing and in
Such processing is analogous to servicing people in a
FCFS is also the
Computer science
Depending on the application, a FIFO could be implemented as a hardware shift register, or using different memory structures, typically a
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 library std::list template, avoiding the need for implementing the data structure from scratch.
#include <memory>
#include <stdexcept>
using namespace std;
template <typename T>
class FIFO {
struct Node {
T value;
shared_ptr<Node> next = nullptr;
Node(T _value): value(_value) {}
};
shared_ptr<Node> front = nullptr;
shared_ptr<Node> back = nullptr;
public:
void enqueue(T _value) {
if (front == nullptr) {
front = make_shared<Node>(_value);
back = front;
} else {
back->next = make_shared<Node>(_value);
back = back->next;
}
}
T dequeue() {
if (front == nullptr)
throw underflow_error("Nothing to dequeue");
T value = front->value;
front = move(front->next);
return value;
}
};
In computing environments that support the
Disk controllers can use the FIFO as a disk scheduling algorithm to determine the order in which to service disk I/O requests, where it is also known by the same FCFS initialism as for CPU scheduling mentioned before.[1]
Communication
Electronics
FIFOs are commonly used in
The first known FIFO implemented in electronics was by Peter Alfke in 1969 at Fairchild Semiconductor.[4] Alfke was later a director at Xilinx.
Synchronicity
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
- 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
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 most significant bit and the rest are equal, the FIFO is full.
See also
- FIFO and LIFO accounting
- FINO
- Queueing theory
- SCHED_FIFO