FIFO

this article is about FIFOs in computing and electronic design. For the term in accounting, see .

FIFO is an for First In, First Out, an abstraction in ways of organizing and manipulation of data relative to time and prioritization. This expression describes the principle of a processing technique or servicing conflicting demands by ordering process by (FCFS) behaviour: what comes in first is handled first, what comes in next waits until the first is finished, etc.

Thus it is analogous to the behaviour of persons standing in line, where the persons leave the queue in the order they arrive, or waiting one's turn at a traffic control signal. FCFS is also the shorthand name (see and acronym) for the FIFO operating system scheduling algorithm, which gives every process time in the order they come. In the broader sense, the abstraction , or Last-In-First-Out is the opposite of the abstraction FIFO organization, the difference perhaps is clearest with considering the less commonly used synonym of LIFO, FILO—meaning First-In-Last-Out. In essence, both are specific cases of a more generalized list (which could be accessed anywhere). The difference is not in the list (data), but in the rules for accessing the content. One sub-type adds to one end, and takes off from the other, its opposite takes and puts things only on one end.

A is a variation on the queue which does not qualify for the name FIFO, because it is not accurately descriptive of that 's behavior. encompasses the more general concept of queu

Computer science

Data structure

In this term refers to the way data stored in a queue is processed. Each item in the queue is stored in a queue (simpliciter) data structure. The first data to be added to the queue will be the first data to be removed, then processing proceeds sequentially in the same order. This is typical behavior for a queue, but see also the algorithms. and

A typical data structure will look like

struct fifo_node 
{
  struct fifo_node *next;
  value_type value;
};
 
class fifo
{
  fifo_node *front;
  fifo_node *back;
 
  fifo_node *dequeue(void)
  {
    fifo_node *tmp = front;
    front = front->next;
    return tmp;
  }
 
  queue(value)
  {
    fifo_node *tempNode = new fifo_node;
    tempNode->value = value;
    back->next = tempNode;
    back = tempNode;
  }
};

(For information on the abstract data structure, see . For details of a common implementation, see Circular buffer.)

Popular Unix systems include a sys/queue.h / header file which provides macros usable by applications which need to create FIFO queues.

Head or tail first

Controversy over the terms "head" and "tail" exists in reference to FIFO queues. To many people, items should enter a queue at the tail, 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 objects 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 might be considered authoritative, such as the .

Pipes

In computing environments that support the model for , a FIFO is another name for a .

Disk scheduling

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

Communications and networking

Communications , and used in 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.

Electronics

FIFOs are used commonly in circuits for buffering and flow control which is from hardware to software. In hardware form a FIFO primarily consists of a set of read and write pointers, storage and control logic. Storage may be , 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 used for writing and the other is used for reading.

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 issues. A common implementation of an asynchronous FIFO uses a (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 "" approach or pointer arithmetic to generate flags in synchronous FIFO implementations.

Examples of FIFO status flags include: full, empty, almost full, almost empty, etc...

The first known FIFO implemented in electronics was done by Peter Alfke in 1969 at Fairchild Semiconductors. Peter Alfke is now a Director at .

FIFO full/empty

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

1. Read Pointer/Read Address Register
2. 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 read address register reaches to write address register, the FIFO triggers the Empty signal.

FIFO FULL

When write address register reaches to read address register, the FIFO triggers the FULL signal.

e, as well as interactions between strict-FIFO queues.

FIFO：
　　一、先入先出队列(First Input First Output，FIFO)这是一种传统的按序执行方法，先进入的指令先完成并引退，跟着才执行第二条指令。
　　1．什么是FIFO？
　　FIFO是英文First In First Out 的缩写，是一种先进先出的数据缓存器，他与普通存储器的区别是没有外部读写地址线，这样使用起来非常简单，但缺点就是只能顺序写入数据，顺序的读出数据，其数据地址由内部读写指针自动加1完成，不能像普通存储器那样可以由地址线决定读取或写入某个指定的地址。
　　2．什么情况下用FIFO？
　　FIFO一般用于不同时钟域之间的数据传输，比如FIFO的一端时AD数据采集，另一端时计算机的PCI总线，假设其AD采集的速率为16位 100K SPS，那么每秒的数据量为100K×16bit=1.6Mbps,而PCI总线的速度为33MHz，总线宽度32bit,其最大传输速率为 1056Mbps,在两个不同的时钟域间就可以采用FIFO来作为数据缓冲。另外对于不同宽度的数据接口也可以用FIFO，例如单片机位8位数据输出，而 DSP可能是16位数据输入，在单片机与DSP连接时就可以使用FIFO来达到数据匹配的目的。
　　3．FIFO的一些重要参数
　　FIFO的宽度：也就是英文资料里常看到的THE WIDTH，它指的是FIFO一次读写操作的数据位，就像MCU有8位和16位，ARM 32位等等，FIFO的宽度在单片成品IC中是固定的，也有可选择的，如果用FPGA自己实现一个FIFO，其数据位，也就是宽度是可以自己定义的。
　　FIFO的深度：THE DEEPTH，它指的是FIFO可以存储多少个N位的数据（如果宽度为N）。如一个8位的FIFO，若深度为8，它可以存储8个8位的数据，深度为12 ，就可以存储12个8位的数据，FIFO的深度可大可小，个人认为FIFO深度的计算并无一个固定的公式。在FIFO实际工作中，其数据的满/空标志可以控制数据的继续写入或读出。在一个具体的应用中也不可能由一些参数算数精确的所需FIFO深度为多少，这在写速度大于读速度的理想状态下是可行的，但在实际中用到的FIFO深度往往要大于计算值。一般来说根据电路的具体情况，在兼顾系统性能和FIFO成本的情况下估算一个大概的宽度和深度就可以了。而对于写速度慢于读速度的应用，FIFO的深度要根据读出的数据结构和读出数据的由那些具体的要求来确定。
　　满标志：FIFO已满或将要满时由FIFO的状态电路送出的一个信号，以阻止FIFO的写操作继续向FIFO中写数据而造成溢出（overflow）。
　　空标志：FIFO已空或将要空时由FIFO的状态电路送出的一个信号，以阻止FIFO的读操作继续从FIFO中读出数据而造成无效数据的读出（underflow）。
　　读时钟：读操作所遵循的时钟，在每个时钟沿来临时读数据。
　　写时钟：写操作所遵循的时钟，在每个时钟沿来临时写数据。
　　读指针：指向下一个读出地址。读完后自动加1。
　　写指针：指向下一个要写入的地址的，写完自动加1。
　　读写指针其实就是读写的地址，只不过这个地址不能任意选择，而是连续的。
　　4．FIFO的分类
　　根均FIFO工作的时钟域，可以将FIFO分为同步FIFO和异步FIFO。同步FIFO是指读时钟和写时钟为同一个时钟。在时钟沿来临时同时发生读写操作。异步FIFO是指读写时钟不一致，读写时钟是互相独立的。
　　5．FIFO设计的难点
　　FIFO设计的难点在于怎样判断FIFO的空/满状态。为了保证数据正确的写入或读出，而不发生益处或读空的状态出现，必须保证FIFO在满的情况下，不能进行写操作。在空的状态下不能进行读操作。怎样判断FIFO的满/空就成了FIFO设计的核心问题。由于同步FIFO几乎很少用到，这里只描述异步FIFO的空/满标志产生问题。
　　在用到触发器的设计中，不可避免的会遇到亚稳态的问题（关于亚稳态这里不作介绍，可查看相关资料）。在涉及到触发器的电路中，亚稳态无法彻底消除，只能想办法将其发生的概率将到最低。其中的一个方法就是使用格雷码。格雷码在相邻的两个码元之间只由一位变换(二进制码在很多情况下是很多码元在同时变化)。这就会避免计数器与时钟同步的时候发生亚稳态现象。但是格雷码有个缺点就是只能定义2^n的深度，而不能像二进制码那样随意的定义FIFO的深度，因为格雷码必须循环一个2^n，否则就不能保证两个相邻码元之间相差一位的条件，因此也就不是真正的各雷码了。第二就是使用冗余的触发器，假设一个触发器发生亚稳态的概率为P，那么两个及联的触发器发生亚稳态的概率就为P的平方。但这回导致延时的增加。亚稳态的发生会使得FIFO出现错误，读/写时钟采样的地址指针会与真实的值之间不同，这就导致写入或读出的地址错误。由于考虑延时的作用，空/满标志的产生并不一定出现在FIFO真的空/满时才出现。可能FIFO还未空/满时就出现了空/满标志。这并没有什么不好，只要保证FIFO不出现overflow or underflow 就OK了。
　　很多关于FIFO的文章其实讨论的都是空/满标志的不同算法问题。
　　在Vijay A. Nebhrajani的《异步FIFO结构》一文中，作者提出了两个关于FIFO空/满标志的算法。
　　第一个算法：构造一个指针宽度为N+1，深度为2^N字节的FIFO（为便方比较将格雷码指针转换为二进制指针）。当指针的二进制码中最高位不一致而其它N位都相等时，FIFO为满（在Clifford E. Cummings的文章中以格雷码表示是前两位均不相同，而后两位LSB相同为满，这与换成二进制表示的MSB不同其他相同为满是一样的）。当指针完全相等时，FIFO为空。这也许不容易看出，举个例子说明一下：一个深度为8字节的FIFO怎样工作（使用已转换为二进制的指针）。FIFO_WIDTH=8，FIFO_DEPTH= 2^N = 8，N = 3，指针宽度为N+1=4。起初rd_ptr_bin和wr_ptr_bin均为“0000”。此时FIFO中写入8个字节的数据。wr_ptr_bin =“1000”，rd_ptr_bin=“0000”。当然，这就是满条件。现在，假设执行了8次的读操作，使得rd_ptr_bin =“1000”，这就是空条件。另外的8次写操作将使wr_ptr_bin 等于“0000”，但rd_ptr_bin 仍然等于“1000”，因此FIFO为满条件。
　　显然起始指针无需为“0000”。假设它为“0100”，并且FIFO为空，那么8个字节会使wr_ptr_bin =“1100”，, rd_ptr_bin 仍然为“0100”。这又说明FIFO为满。
　　在Vijay A. Nebhrajani的这篇《异步FIFO结构》文章中说明了怎样运用格雷码来设置空满的条件，但没有说清为什么深度为8的FIFO其读写指针要用3+1 位的格雷码来实现，而3+1位的格雷码可以表示16位的深度，而真实的FIFO只有8位，这是怎么回事？而这个问题在Clifford E. Cummings的文章中得以解释。三位格雷码可表示8位的深度，若在加一位最为MSB，则这一位加其他三位组成的格雷码并不代表新的地址，也就是说格雷码的0100表示表示7，而1100仍然表示7，只不过格雷码在经过一个以0位MSB的循环后进入一个以1为MSB的循环，然后又进入一个以0位MSB的循环，其他的三位码仍然是格雷码，但这就带来一个问题，在0100的循环完成后，进入1000，他们之间有两位发生了变换，而不是1位，所以增加一位 MSB的做法使得该码在两处：0100~1000，1100~0000有两位码元发生变化，故该码以不是真正的格雷码。增加的MSB是为了实现空满标志的计算。Vijay A. Nebhrajani的文章用格雷码转二进制，再转格雷码的情况下提出空满条件，仅过两次转换，而Clifford E. Cummings的文章中直接在格雷码条件下得出空满条件。其实二者是一样的，只是实现方式不同罢了。
　　第二种算法：Clifford E. Cummings的文章中提到的STYLE #2。它将FIFO地址分成了4部分，每部分分别用高两位的MSB 00 、01、 11、 10决定FIFO是否为going full 或going empty (即将满或空)。如果写指针的高两位MSB小于读指针的高两位MSB则FIFO为“几乎满”，
　　若写指针的高两位MSB大于读指针的高两位MSB则FIFO为“几乎空”。
　　在Vijay A. Nebhrajani的《异步FIFO结构》第三部分的文章中也提到了一种方法，那就是方向标志与门限。设定了FIFO容量的75%作为上限，设定 FIFO容量的25%为下限。当方向标志超过门限便输出满/空标志，这与Clifford E. Cummings的文章中提到的STYLE #2可谓是异曲同工。他们都属于保守的空满判断。其实这时输出空满标志FIFO并不一定真的空/满。
　　说到此，我们已经清楚地看到，FIFO设计最关键的就是产生空/满标志的算法的不同产生了不同的FIFO。但无论是精确的空满还是保守的空满都是为了保证FIFO工作的可靠。
　

FIFO存储器

FIFO( First In First Out)简单说就是指先进先出。由于微电子技术的飞速发展，新一代FIFO芯片容量越来越大，体积越来越小，价格越来越便宜。作为一种新型大规模集成电路，FIFO芯片以其灵活、方便、高效的特性，逐渐在高速数据采集、高速数据处理、高速数据传输以及多机处理系统中得到越来越广泛的应用。
　　在系统设计中，以增加数据传输率、处理大量数据流、匹配具有不同传输率的系统为目的而广泛使用 FIFO存储器，从而提高了系统性能。FIFO存储器是一个先入先出的双口缓冲器，即第一个进入其内的数据第一个被移出，其中一个存储器的输入口，另一个口是存储器的输出口。对于单片FIFO来说，主要有两种结构：触发导向结构和零导向传输结构。触发导向传输结构的FIFO是由寄存器阵列构成的，零导向传输结构的FIFO是由具有读和写地址指针的双口RAM构成。
　　FIFO存储器是系统的缓冲环节，如果没有FIFO存储器，整个系统就不可能正常工作，它主要有几方面的功能：
　　1）对连续的数据流进行缓存，防止在进机和存储操作时丢失数据；
　　2）数据集中起来进行进机和存储，可避免频繁的总线操作，减轻CPU的负担；
　　3）允许系统进行DMA操作，提高数据的传输速度。这是至关重要的一点，如果不采用DMA操作，数据传输将达不到传输要求，而且大大增加CPU的负担，无法同时完成数据的存储工作。
　　因此，选择合适的存储芯片对于提高系统性能很重要，在以往的设计中经常采用的是“乒乓型”存储方式，这种方式就是采用两片存储器，数据首先进入其中一片，当数据满时再让数据进入第二片存储器，同时通过逻辑控制，将第一片存储器中的数据取走，以此类推，两片轮流对数据进行缓存。这种方式有着较明显的缺点，首先是控制复杂，要有专门的逻辑来维护这种轮流机制;其次，数据流的流向要不断变化，限制了数据流的速率，还容易产生干扰。从数据传输上说，缓存芯片容量越大，对后续时序要求就越低，可减少总线操作的频次；但从数据存储上说，就意味着需要开辟更大的内存空间来进行进行缓冲，会增加计算机的内存开销，而且容量越大，成本也越高。因此，在综合考虑系统性能和成本的基础上，选择满足系统需要的芯片即可。
　　FIFO是First In／First－Out的缩写，是先入先出的意思。FIFO存储器分为写入专用区和读取专用区。读操作与写操作可以异步进行，写入区上写入的数据按照写入的顺序从读取端的区中读出，类似于吸收写入端与读出端速度差的一种缓冲器。计算机的串口，一般也都具有FIFO缓冲器（不是单一的FIFO存储器，而是嵌入在设备内部）。
　　FIFO存储器的连接模式如图所示。在FIFO存储器而不是地址总线上附加了表示内部缓冲器状态（Buffer Full，缓冲器已满；Buffer Empty，缓冲器为空）的状态引脚，连接于FIFO的双方利用该状态进行操作的控制。另外，还设计了在接通电源及复位（Reset）或由于操作中的某些异常等原因而重新初始化（无数据状态）FIFO的复位引脚，这可以说是FIFO存储器的特点