fifo算法是什么?

JavaScript012

fifo算法是什么?,第1张

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

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

有两种实现的方法:第一种是记录每个分页被调入到页框的时间,当每次需要换出分页时,会找到调入时间最早的一页,也就是在主存储器中存在最久的分页。另外一种方式就是利用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队列为空。

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

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

队列是常见的使用数组方法之一。在计算机科学中,这表示支持两个操作的一个有序元素的集合:

push 在末端添加一个元素。

shift 取出队列首端的一个元素,整个队列往前移,这样原先排第二的元素现在排在了第一。

这两种操作数组都支持。

队列的应用在实践中经常碰到。例如需要在屏幕上显示消息队列。

数组还有另外一个用例,就是数据结构 栈 。

栈支持两种操作:

push 在末端添加一个元素。

pop 从末端取出一个元素。

所以新元素的添加和取出都是从“末端”开始的。

栈通常被形容成一叠卡片:要么在最上面添加卡片,要么从最上面拿走卡片:

对于栈来说,最后放进去的内容是最先接收的,也叫做 LIFO (Last-In-First-Out) ,即后进先出法则。而与队列相对应的 FIFO (First-In-First-Out) ,即先进先出。

JavaScriptt 中的数组既可以用作队列,也可以用作栈。它们允许你从 首端/末端 来 添加/删除 元素。

在计算机科学中,允许这样操作的数据结构被称为 双端队列。

pop

//取出并返回数组的最后一个元素:

push

//在数组末端添加元素:

调用 fruits.push(...)   与 fruits[fruits.length] = ... 是一样的。

shift

//取出数组的第一个元素并返回它:

unshift

//在数组的首端添加元素:

push 和 unshift 方法都可以一次添加多个元素: