缓冲和排队有什么区别?

信息处理 即时的
2022-02-07 03:56:10

我对排队和缓冲的定义有一些问题,那么缓冲和排队有什么区别?

3个回答

我认为,尤其是在 实时 DSP的背景下,这些术语实际上是在谈论同一个话题。

也许关于缓冲区的最一般的 Wikipedia 参考将包括先进先出 (FIFO)后进先出 (LIFO),但 LIFO 缓冲区通常称为“堆栈”

如果是 FIFO 缓冲区,我们通常称其为“队列”,特别是如果缓冲区的输入和输出是异步的并且由独立的源和目标控制,那么科学的一个角落我们称之为队列理论,令人担忧关于 FIFO 缓冲区的大小、输入和输出指针的位置,以及需要做些什么来避免缓冲区饥饿(我认为我没有滥用这个术语)。

就实时 DSP 而言,采用统一采样,与此主题相关的唯一我担心的是,简单的双缓冲,我无法立即找到一个好的在线参考。通过 FIFO 缓冲 DSP 进程的输入和输出,可以编写更高效的代码,其中处理块时间是填充或清空缓冲区所需的时间(即倍采样时间,其中是采样数在缓冲块中)。在该块时间开始时,该过程保证个有效样本等待输入,并且该过程不需要保证任何的正确性BBB输出样本的数量,直到块周期的最后。这可以通过仅加载一次状态和系数以及其他参数(而不是次,每个样本一次)并仅存储一次状态来节省处理开销。个样本中摊销。付出的代价是延迟样品。BB2B

队列可以是多个结构,例如优先级队列,有时称为堆。他们可以按到达或大小排序。它们是高效的数据结构。我已经看到它们用于多目标跟踪分配例程。

缓冲区也是一个队列,通常通过信号量等控制机制用于异步数据传输。

缓冲器是用于存储数字数据的存储设备脑海中的图像是一个(长)移位寄存器,数据从一端进入,从另一端退出,实际上曾几何时,缓冲器实际上是用分立元件(如真空管和晶体管配置为翻转)构建的。由于不必要的能量消耗,现代实现避开了移位寄存器的概念,移位寄存器的位从输入到输出(以及触发器改变状态),并且简单地将数据放入 RAM 单元中,每个位都保持在分配的位置单元,直到它被读出:唯一改变状态的触发器是 RAM 的地址解码器中的触发器。但是,缓冲区的概念是 FIFO 设备的概念。

缓冲器的例子是那些与纠错码解码器相关的缓冲器。例如,Reed-Solomon 或 BCH 码的现代解码器通常同时处理三个连续接收到的字。最近接收到的字(字#N)仍未完全接收:随着符号一一到达,它们进入校正子生成器单元并同时存储在缓冲区中。先前接收到的字(字#(N-1))已经在缓冲区中(已经计算了它的校正子),并且校正子当前正在由 Berlekamp-Massey 算法或欧几里得算法处理以找出错误定位器和误差评估多项式。在此之前收到的消息(word #(N-2)) 正在从缓冲区中读出,并且在每个符号离开缓冲区时“即时”纠正其中的错误:这就是 Chien 搜索和处理 Forney 算法的重点错误定位多项式和错误评估多项式分别确定离开缓冲区的符号是否需要更正(如果需要,需要纠正什么),还是因为符号中没有错误而不管。符号(两个接收字)的FIFO 设备作为缓冲区。2n[n,k]

缓冲器的其他用途是改变数据速率:当输入和输出使用不同的时钟速率时。示例是在纠错码的编码器的输入端。在一个码字时间内,个符号进入编码器,符号退出编码器。这是通过以个符号读入两个缓冲器中的一个,同时另一个缓冲器以较高的时钟速率将其清空到编码器中来实现的。更接近 dsp.SE 核心的考虑是用于上采样的多相插值滤波器。输入处于原始速率并保存在缓冲区中。在一个慢样本的时间内,kn>kkL插值样本被创建为缓冲区内容的不同线性组合,并以输出样本的($L 倍)更高的速率吐出。

另一方面,队列可以是一个更复杂的数据结构,其中数据可以以不同的顺序进入和退出设备,并且顺序可以根据各种条件动态改变(与周期性交织器相反,其中数据以应用于数据的固定排列进入和离开。)。有关详细信息,请参阅其他答案。