fifoFIFO算法的解释

什么是FIFO缓存队列

FIFO是英文First In First Out 的缩写，是一种先进先出的数据缓存器，他与普通存储器的区别是没有外部读写地址线，这样使用起来非常简单，但缺点就是只能顺序写入数据，顺序的读出数据，其数据地址由内部读写指针自动加1完成，不能像普通存储器那样可以由地址线决定读取或写入某个指定的地址。

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为满。

若写指针的高两位MSB大于读指针的高两位MSB则FIFO为“几乎空”。

在Vijay A. Nebhrajani的《异步FIFO结构》第三部分的文章中也提到了一种方法，那就是方向标志与门限。

设定了FIFO容量的75%作为上限，设定FIFO容量的25%为下限。

当方向标志超过门限便输出满/空标志，这与Clifford E. Cummings的文章中提到的STYLE #2可谓是异曲同工。

他们都属于保守的空满判断。

其实这时输出空满标志FIFO并不一定真的空/满。

说到此，我们已经清楚地看到，FIFO设计最关键的就是产生空/满标志的算法的不同产生了不同的FIFO。

FEFO和FIFO分别什么意思

LIFO(后进先出)、FIFO(先进先出)、FEFO(先到期先出) “FEFO意味着，生鲜产品基于货架销售的供应链，而不只是基于其在供应链中运输的时间。

例如，同那些前置时间(Lead times，指订货至交货的时间)短而且配送条件比较适合的产品相比，前置时间长并且在配送过程中已经处于高温环境的产品将会较早的送往零售货架。

仓库中的FIFO代表什么？

FirstInFirstOut（FIFO）先进先出： 　　先进先出法是指根据先入库先发出的原则，对于发出的存货以先入库存货的单价计算发出存货成本的方法.采用这种方法的具体做法是：先按存货的期初余额的单价计算发出的存货的成本，领发完毕后，再按第一批入库的存货的单价计算，依此从前向后类推，计算发出存货和结存货的成本。

　　先进先出法是存货的计价方法之一。

它是根据先购入的商品先领用或发出的假定计价的。

用先进先出法计算的期末存货额，比较接近市价。

　　先进先出法是以先购入的存货先发出这样一种存货实物流转假设为前提，对发出存货进行计价的一种方法。

采用这种方法，先购入的存货成本在后购入的存货成本之前转出，据此确定发出存货和期末存货的成本。

　　先进先出法和后进先出法的区别： 　　1、先进先出：发出存货计价时，坚持先购进先发出的原则进行计价。

　　2、后进先出：发出存货计价时，坚持后购进先发出的原则进行计价。

　　先进先出法的优缺点： 　　其优点是使企业不能随意挑选存货计价以调整当期利润，缺点是工作量比较繁琐，特别对于存货进出量频繁的企业更是如此。

而且当物价上涨时，会高估企业当期利润和库存存货价值；反之，会低估企业存货价值和当期利润。

FIFO调度算法和LRU算法

FIFO：先进先出调度算法 LRU：最近最久未使用调度算法 两者都是缓存调度算法，经常用作内存的页面置换算法。

打一个比方，帮助你理解。

你有很多的书，比如说10000本。

由于你的书实在太多了，你只能放在地下室里面。

你看书的时候不会在地下室看书，而是在书房看书。

每次，你想看书都必须跑到地下室去找出来你想看的书， 然后抱回来放到书桌上，之后才开始看。

还有就是，有一些书你会反复的看，今天看了也许过几天又要看。

总之，你自己是不知道你哪天会需要看哪本书的。

你的老师每天下课的时候会给你布置一个书单，让你晚上回去去看哪本书。

（假设你老师让你看的书在你的地下室里面都有） 跑地下室当然是非常麻烦的，所以你希望你的经常看的那些书最好放在书桌上。

但是你的书房的书桌同时只能摆放10本书（这个是假设的啊）。

那么，问题来了。

到底把哪些说留在书桌上最好呢？ 这里说的最好，就是说你尽量少的跑地下室去找书。

为了解决这个问题，人们发明了很多的算法。

其中，比较常见的就是上面这两种：FIFO算法和LRU算法。

FIFO算法 很简单，我把书桌上的10本书按照放置时间先后堆放成一堆。

这里的放置时间，就是说这本书在我的书桌上放了几天了。

每次要看书的时候，我先在书桌上找，找到就直接可以读了。

读完之后放回原来的位置就可以，不打乱顺序。

如果书桌上面没有我要读的书，就去地下室找。

找来之后，我就把书桌上放的时间最长的那本（也就是 书堆里面最下面的那本书）放回地下室。

然后把我今天需要看的这本书放在书堆的最上面。

LRU算法 也不难，我把书桌上的10本书按照阅读时间先后堆放成一堆。

这里的阅读时间，就是说我最近一次读这本书是几天之前。

每次要看书的时候，我先在书桌上找，找到就直接可以读了。

读完之后放在书堆的最上面。

如果书桌上面没有我要读的书，就去地下室找。

找来之后，我就把书桌上最久没有阅读的那本 （也就是书堆里面最下面的那本书）放回地下室。

然后把我今天需要看的这本书放在书堆的最上面。

上面这个比方，相信你可以看明白吧。

这里的地下室对应内存，书桌对应缓存，书对应页面。

FIFO算法的解释

/*我知道FIFO算法的原理，可还是不理解这代码，哪位高手指教下各个程序段的意思啊？不胜感激！ */ #include <stdio.h> #include <stdlib.h> #define mSIZE 3//分配三个内存页框 #define pSIZE 12//总共12个进程 static int memery[mSIZE] = {0}; static int process[pSIZE] = {1,2,3,4,1,2,5,1,2,3,4,5};//页面访问序列 void FIFO(); int main() { get(); printf(" (FIFO) count "); FIFO(); system("PAUSE"); return 0; } get() { int w[12]={1,2,3,4,1,2,5,1,2,3,4,5}; //需要访问的资源序列 int i,n; for(i=0;i<12;i++) //输出序列 { printf("%d ",w[i]); } } void FIFO() { int time[mSIZE] = {0}; //分配的三个页框初始化为0 int i = 0, j = 0; int m = -1, n = -1; int max = -1,maxtime = 0; int count = 0; for(i = 0; i<pSIZE; i++) //开始循环，在页框中寻找所需资源 { for(j=0; j<mSIZE; j++) //判断页框中是否满 { if(memery[j] == 0) //寻找空页框，并且记录页号 { m = j; break; } } for(j = 0; j < mSIZE; j++) { if(memery[j] == process[i]) //判断页框中是否有进程所需访问的资源 { n = j; } } for(j = 0; j < mSIZE;j++) //记录在页框中存放最长时间的资源，即第一个进入的资源 { if(time[j]>maxtime) { maxtime = time[j]; //将存放最长时间资源的计数器的值赋给maxtime max = j; } } if(n == -1) //由于没有在页框中找到所需资源，并且也表已满，发生缺页中断。

{ if(m != -1) { memery[m] = process[i]; //没有替换的资源，则它对应的计数器加一 time[m] = 0; for(j = 0;j <= m; j++) { time[j]++; } m = -1; } else { memery[max] = process[i]; //发生缺页中断，从前面的标记中寻找第一个进入页表的资源替换 time[max] = 0; //替换后原来的最长则清0， for(j = 0;j < mSIZE; j++) { time[j]++; //替换后，此资源对应的计数器加一 } max = -1; maxtime = 0; count++; } } else { memery[n] = process[i]; for(j = 0;j < mSIZE; j++) //一次分配对所有在页表中的资源的计数器加一 { time[j]++; } n = -1; } for(j = 0 ;j < mSIZE; j++) { printf("%d ",memery[j]); //输出此次资源访问时页表中资源的情况。

} printf(" %d ",count); } }