循环缓冲区的用途是什么？

Question

循环缓冲区有哪些用途？

使用循环缓冲区有什么好处？

它是双链表的替代品吗？

Answer 1

我已经将它用于大小受限的内存日志.例如,应用程序将在处理用户请求时写入日志条目.每当发生异常(这会对处理造成破坏)时,当前在内存中的日志记录将与其一起转储.

循环缓冲区的好处是,您不需要无限量的内存,因为较旧的条目会被自动覆盖."挑战"是,您需要为您的用例找到合适的尺寸.在上面的示例中,如果已经覆盖了有关异常的最重要信息的日志记录,那将是非常不幸的.

某些系统/应用程序具有工具,可以让您按需提取缓冲区的当前内容,而不仅仅是在自动提取时(如果有的话).

我相信ETW和CLRs 压力日志,以及许多其他系统的内核或高性能跟踪/日志记录,都是以这种方式实现的.

使用这种缓冲区进行内存中跟踪/日志记录的概念实际上很常见(并不是说这是唯一的用途 - 当然不是),因为它比文件/数据库的写入记录更快,你可能永远不会感兴趣,除非发生错误.在相关的说明中,它节省了硬盘空间.

Answer 2

循环缓冲区适用于嵌入式系统中的串行数据流.微控制器通常有一个UART来处理进入的串行字节,这些需要按顺序存储并稍后处理(字节通常以比它们可以处理的更快的速率进入).

缓冲区有效地将所需的时序关键响应(当字节进入时,以微秒为单位)分解为对整个消息的非时序关键响应(例如显示以毫秒为单位的消息),例如:

1)收到一个字节后,UART可以通过快速获取接收到的字节并将其推送到缓冲区的末尾来生成软件响应的中断.

2)然后,后台软件程序可以定期检查缓冲区中是否有任何内容,并根据需要清空它.

由于可以在预编译时定义循环缓冲区大小,因此大小受到限制.这有助于提高空间效率,并且应该消除内存损坏,以便在数据开始丢失之前可以接收多少字节.

Answer 3

循环缓冲区是一种很好的机制,用于以有序的方式有效地维护滑动/移动的值/项列表.一个例子可能是维持最后N个项目的滑动平均值.假设您要跟踪计算某些值的最后100次操作的平均成本.为此,您需要删除最早的成本并添加最新的成本.

如果没有循环缓冲区,执行此操作(C样式)的昂贵机制将是具有100个元素的数组.每次计算新成本时,您都可以记下99个元素并将新元素放在最后一个位置.这显然是昂贵的.使用循环缓冲区构思,您只需跟踪缓冲区的"结束"(位置0-99).它会标记最旧的(或最新的...无论您选择哪个)成本项目的位置.读取旧值(用于更新运行平均值)后,将其替换为最新值并增加缓冲区位置(如果为99,则将其设置为0 ...因此,圆形部分).

将它与双向链表进行比较并没有多大意义.当然可以使用双向链表(甚至是单链表)来实现循环缓冲区.但比较它们有点像比较苹果和橙子.

Answer 4

我知道这是作弊,但维基百科确实有很好的解释.

http://en.wikipedia.org/wiki/Circular_buffer

循环缓冲区,循环缓冲区或环形缓冲区是一种数据结构,它使用单个固定大小的缓冲区,就好像它是端到端连接一样.这种结构很容易缓冲数据流

可能使用覆盖循环缓冲区的示例是多媒体.如果缓冲区被用作生产者 - 消费者的问题,那么它可能是期望的生产者(例如,音频发生器)以覆盖旧数据如果消费者(如声卡)是无法瞬间跟上界缓冲区.另一个例子是数字波导合成方法,其使用循环缓冲器来有效地模拟振动弦或管乐器的声音.

关于与双链表的比较,我想它确实取决于你使用列表的内容...圆形缓冲区的实现似乎更复杂,请(再次)参考维基页面; 这解释了实现,注意事项等,并且还显示了示例代码.

谢谢,尼尔