先入先出队列(First Input First Output)的缩写，是一种传统的顺序执行方法。先入指令先完成并退休，然后执行第二条指令。它是一个先进先出的数据缓冲器。它和普通内存的区别在于没有外部的读写地址线，所以使用起来非常简单。但缺点是数据只能顺序写入，数据可以顺序读出。它的数据地址是内部读写指针自动加1的，所以不可能像普通存储器一样通过地址线读写指定地址。

这是最简单的队列机制。每个接口上只有一个FIFO队列。从表面上看，FIFO队列不提供任何QoS保证。甚至很多人认为FIFO不是严格意义上的队列技术，其实不是。FIFO是其他队列的基础，也会影响到衡量QoS的关键指标：

消息的丢弃、延迟和抖动。由于只有一个队列，自然不需要考虑如何对消息的复杂流量进行分类，也不需要考虑下一条消息取多少，即FIFO不需要流分类和调度机制，而且由于消息是按顺序取的，FIFO不需要对消息进行重新排序。简化这些实现实际上提高了消息延迟的保证。

FIFO关注的是队列长度，队列长度会影响延迟、抖动和丢包率。因为队列长度有限，所以可能会被填满，这就涉及到这种机制的丢弃原理。FIFO使用尾部丢弃机制。如果定义了一个长的队列长度，那么这个队列就不容易填满，被丢弃的消息就更少。但是，如果队列长度太长，就会出现延迟的问题。一般来说，延迟的增加会导致抖动的增加。如果定义一个较短的队列，可以解决时延的问题，但是会有更多的消息出现抛尾。其他排队方式也存在类似问题。

尾丢弃机制简单地说就是如果队列已满，后续传入的消息将被丢弃，但是没有机制保证后续的消息能够挤出队列中已经存在的消息。

先进先出原理简介

FIFO不对消息进行分类。当消息进入接口的速度快于接口能够发送的速度时，FIFO会按照消息到达接口的顺序让消息进入队列。同时，FIFO会根据队列顺序在队列出口处让消息出队列。先进的消息将首先离开队列，落后的消息将稍后离开队列。

FIFO的优点是处理简单，开销低。但是FIFO不区分消息的类型，采用尽力而为的转发方式，使得时间敏感的实时应用(如VoIP)的延迟无法保证，关键业务的带宽也无法保证。

应用FIFO

通常，FIFO用于不同时钟域之间的数据传输。比如FIFO的一端是AD数据采集，另一端是计算机PCI总线。假设其AD采集速率为16位100K SPS，每秒数据量为100K16bit=1.6Mbps，而PCI总线的速度为33MHz，总线宽度为32bit，最大传输速率为1056Mbps，因此FIFO可以作为两个不同时钟域之间的数据缓冲。

此外，FIFO还可以用于不同宽度的数据接口，如单片机的8位数据输出，DSP的16位数据输入。当单片机与DSP相连时，可以利用FIFO来达到数据匹配的目的。

FIFO的宽度：

也就是英文资料中经常看到的宽度，指的是FIFO在一次读写操作中的数据位数，就像MCU有8位和16位，ARM32位等。在单个成品IC中，FIFO的宽度是固定的和可选的。如果使用FPGA实现FIFO，数据位(即宽度)可以自行定义。

FIFO的深度：

深度，指的是FIFO中可以存储多少N位数据(如果宽度为N)。例如，如果一个8位FIFO的深度是8，它可以存储8个8位数据，如果深度是12，它可以存储12个8位数据。FIFO的深度可大可小。个人认为FIFO深度的计算没有固定的公式。

在FIFO的实际操作中，其数据的满/空标志可以控制数据的连续写入或读取。在具体应用中，无法通过某些参数精确计算出所需的FIFO深度，在写入速度高于读取速度的理想状态下是可行的，但实际使用的FIFO深度往往大于计算值。

一般来说，根据电路的具体情况，在兼顾系统性能和FIFO成本的情况下，估算一个大概的宽度和深度就足够了。对于写入速度慢于读取速度的应用，FIFO的深度应根据读取数据结构和读取数据的具体要求来确定。

满载和空载标志：

满标志(Full flag):当FIFO已满或即将满时，FIFO的状态电路发出的信号，以防止FIFO继续向FIFO中写入数据，导致溢出。

空标志(Empty flag):当FIFO为空或即将为空时，FIFO的状态电路发出的信号，以防止FIFO的读操作继续从FIFO中读取数据，导致无效数据下溢。

读写时钟：

读时钟：读操作所跟随的时钟，数据在每个时钟边沿被读取。

时钟：写操作后的时钟，数据在每个时钟沿写入。

读写指针

读指针：指向下一个读地址。看完自动加1。

写指针：如果指向下一个要写的地址，写完后自动加1。

读写指针其实就是读写地址，但是这个地址不能任意选择，而是连续的。

分类FIFO

根据FIFO工作的时钟域，FIFO可分为同步FIFO和异步FIFO。

同步FIFO意味着读时钟和写时钟是同一个时钟。当时钟边沿到来时，读和写操作同时发生。

异步FIFO是指读写时钟不一致，读写时钟相互独立。

FIFO设计中的难点

FIFO设计的难点是如何判断FIFO的空/满状态。

为了保证数据的正确写入或读取，不发生溢出或空读，需要保证FIFO已满，不能写入。你不能在空的状态下阅读。如何判断FIFO是满还是空，成为FIFO设计的核心问题。因为很少使用同步FIFO，所以这里只描述异步FIFO的空/满标志。

在触发器的设计中，亚稳态的问题是不可避免的(对于亚稳态，可以看FPGA中的亚稳态)。在涉及触发器的电路中，亚稳态不可能被完全消除，所以我们必须找到一种方法来最小化它出现的概率。

方法之一是使用格雷码。格雷码仅通过两个相邻符号之间的一位进行变换(很多情况下，二进制码的多个符号同时发生变化)。当计数器与时钟同步时，这将避免亚稳态。但是格雷码有一个缺点就是只能定义2 N的深度，不能像二进制码那样任意定义FIFO的深度，因为格雷码必须循环2 N，否则无法保证相邻两个符号相差一位的情况，所以不是真正的格雷码。

第二种是使用冗余触发器。假设一个触发器的亚稳态概率为P，两个级联触发器的亚稳态概率为P的平方，但这样会导致延迟增加。亚稳态的出现会造成FIFO出错，读/写时钟采样的地址指针会与真实值不同，导致写或读时地址出错。

由于延迟，当FIFO确实为空/满时，空/满标志不一定出现。空/满标志可能出现在FIFO空/满之前。这个没什么问题，只要保证FIFO没有上溢或者下溢就可以了。

以上，我们已经清楚地看到，FIFO设计中最重要的是，不同的空/满标志生成算法产生不同的FIFO。但是，无论是准确还是保守，都是为了保证FIFO的可靠运行。

japan quarterly 日本季刊

标签：FIFO数据队列