FIFO算法的解释

发布网友发布时间：2022-04-21 15:20

共1个回答

热心网友时间：2022-05-13 01:54

先进先出算法是最简单的分页替换算法，是指每次有新的分页需要调入时，会选择调入内存时间最久的分页换出。它简单，容易实现，但这种绝对的公平方式容易导致效率的降低。

最简单的分页替换算法就是先进先出算法，当每次有新的分页需要调入时，会选择调入内存时间最久的分页换出。

有两种实现的方法：第一种是记录每个分页被调入到页框的时间，当每次需要换出分页时，会找到调入时间最早的一页，也就是在主存储器中存在最久的分页。另外一种方式就是利用FIFO队列来实现，当要进行分页替换时，就把队列最前端的分页换出，再把要调入的分页放到队列的末端。

一、实现机制

使用链表将所有在内存的页面按照进入时间的早晚链接起来，然后每次置换链表头上的页面就行了。新加进来的页面则挂在链表的末端。

二、特点

1、优点

简单，且容易实现。

2、缺点

这种绝对的公平方式容易导致效率的降低。例如，如果最先加载进来的页面是经常被访问的页面，这样做很可能造成常被访问的页面替换到磁盘上，导致很快就需要再次发生缺页中断，从而降低效率。

电子产品

FIFO通常在电子电路中用于硬件和软件之间的缓冲和流控制。FIFO以其硬件形式主要由一组读写指针，存储和控制逻辑组成。

存储可以是静态随机存取存储器（SRAM），触发器，锁存器或任何其他合适的存储形式。对于非平凡大小的FIFO，通常使用双端口SRAM，其中一个端口专用于写入，另一端口专用于读取。

电子设备中实现的第一个已知FIFO是1969年在飞兆半导体公司的Peter Alfke 。[4] Alfke后来担任Xilinx的董事。

1、同步性

同步FIFO是其中相同的时钟用于读取和写入的FIFO。异步FIFO使用不同的时钟进行读取和写入，它们可能会引入亚稳定性问题。异步FIFO的常见实现方式是对读和写指针使用格雷码（或任何单位距离码），以确保可靠的标志生成。

关于标志生成的另一条注释是，必须使用指针算法为异步FIFO实现生成标志。相反，在同步FIFO实现中，可以使用泄漏存储区方法或指针算法来生成标志。

2、状态标志

FIFO状态标志的示例包括：已满，为空，几乎已满和几乎为空。当读地址寄存器到达写地址寄存器时，FIFO为空。当写地址寄存器到达读地址寄存器时，FIFO已满。读写地址最初都位于第一个存储器位置，并且FIFO队列为空。

在这两种情况下，读和写地址最终都是相等的。为了区分这两种情况，一种简单而强大的解决方案是为每个读取和写入地址添加一个额外的位，该地址在每次换行时都会反转。

以上内容参考百度百科-先进先出算法