9 评论

架构设计:生产者/消费者模式[3]:环形缓冲区

  前一个帖子提及了队列缓冲区可能存在的性能问题及解决方法:环形缓冲区。今天就专门来描述一下这个话题。
  为了防止有人给咱扣上“过度设计”的大帽子,事先声明一下:只有当存储空间的分配/释放非常【频繁】并且确实产生了【明显】的影响,你才应该考虑环形缓冲区的使用。否则的话,还是老老实实用最基本、最简单的队列缓冲区吧。还有一点需要说明一下:本文所提及的“存储空间”,不仅包括内存,还可能包括诸如硬盘之类的存储介质。

★环形缓冲区 vs 队列缓冲区


◇外部接口相似


  在介绍环形缓冲区之前,咱们先来回顾一下普通的队列。普通的队列有一个写入端和一个读出端。队列为空的时候,读出端无法读取数据;当队列满(达到最大尺寸)时,写入端无法写入数据。
  对于使用者来讲,环形缓冲区和队列缓冲区是一样的。它也有一个写入端(用于 push)和一个读出端(用于 pop),也有缓冲区“满”和“空”的状态。所以,从队列缓冲区切换到环形缓冲区,对于使用者来说能比较平滑地过渡。

◇内部结构迥异


  虽然两者的对外接口差不多,但是内部结构和运作机制有很大差别。队列的内部结构此处就不多啰嗦了。重点介绍一下环形缓冲区的内部结构。
  大伙儿可以把环形缓冲区的读出端(以下简称 R)和写入端(以下简称 W)想象成是两个人在体育场跑道上追逐。当 R 追上 W 的时候,就是缓冲区为空;当 W 追上 R 的时候(W 比 R 多跑一圈),就是缓冲区满。
  为了形象起见,去找来一张图并略作修改,如下:
不见图 请翻墙

  从上图可以看出,环形缓冲区所有的 push/pop 操作都是在一个【固定】的存储空间内进行。而队列缓冲区在 push 的时候,可能会分配存储空间用于存储新元素;在 pop 时,可能会释放废弃元素的存储空间。所以环形方式相比队列方式,少掉了对于缓冲区元素所用存储空间的分配、释放。这是环形缓冲区的一个主要优势。

★环形缓冲区的实现


  如果你手头已经有现成的环形缓冲区可供使用,并且你对环形缓冲区的内部实现不感兴趣,可以跳过这段。

◇数组方式 vs 链表方式


  环形缓冲区的内部实现,即可基于数组(此处的数组,泛指连续存储空间)实现,也可基于链表实现。
  数组在物理存储上是一维的连续线性结构,可以在初始化时,把存储空间【一次性】分配好,这是数组方式的优点。但是要使用数组来模拟环,你必须在逻辑上把数组的头和尾相连。在顺序遍历数组时,对尾部元素(最后一个元素)要作一下特殊处理。访问尾部元素的下一个元素时,要重新回到头部元素(第0个元素)。如下图所示:
不见图 请翻墙

  使用链表的方式,正好和数组相反:链表省去了头尾相连的特殊处理。但是链表在初始化的时候比较繁琐,而且在有些场合(比如后面提到的跨进程的 IPC)不太方便使用。

◇读写操作


  环形缓冲区要维护两个索引,分别对应写入端(W)和读取端(R)。写入(push)的时候,先确保环没满,然后把数据复制到 W 所对应的元素,最后 W 指向下一个元素;读取(pop)的时候,先确保环没空,然后返回 R 对应的元素,最后 R 指向下一个元素。

◇判断“空”和“满”


  上述的操作并不复杂,不过有一个小小的麻烦:空环和满环的时候,R 和 W 都指向同一个位置!这样就无法判断到底是“空”还是“满”。大体上有两种方法可以解决该问题。
  办法1:始终保持一个元素不用
  当空环的时候,R 和 W 重叠。当 W 比 R 跑得快,追到距离 R 还有一个元素间隔的时候,就认为环已经满。当环内元素占用的存储空间较大的时候,这种办法显得很土(浪费空间)。
  办法2:维护额外变量
  如果不喜欢上述办法,还可以采用额外的变量来解决。比如可以用一个整数记录当前环中已经保存的元素个数(该整数>=0)。当 R 和 W 重叠的时候,通过该变量就可以知道是“空”还是“满”。

◇元素的存储


  由于环形缓冲区本身就是要降低存储空间分配的开销,因此缓冲区中元素的类型要选好。尽量存储【值类型】的数据,而不要存储【指针(引用)类型】的数据。因为指针类型的数据又会引起存储空间(比如堆内存)的分配和释放,使得环形缓冲区的效果大打折扣。

★应用场合


  刚才介绍了环形缓冲区内部的实现机制。按照前一个帖子的惯例,我们来介绍一下在线程和进程方式下的使用。
  如果你所使用的编程语言和开发库中带有现成的、成熟的环形缓冲区,强烈建议使用现成的库,不要重新制造轮子;确实找不到现成的,才考虑自己实现。(如果你纯粹是业余时间练练手,那另当别论)

◇用于并发线程


  和线程中的队列缓冲区类似,线程中的环形缓冲区也要考虑线程安全的问题。除非你使用的环形缓冲区的库已经帮你实现了线程安全,否则你还是得自己动手搞定。线程方式下的环形缓冲区用得比较多,相关的网上资料也多,下面就大致介绍几个。
  对于 C++ 的程序员,强烈推荐使用 boost 提供的 circular_buffer 模板,该模板最开始是在 boost 1.35版本中引入的。鉴于 boost 在 C++ 社区中的地位,大伙儿应该可以放心使用该模板。
  对于 C 程序员,可以去看看开源项目 circbuf,不过该项目是 GPL 协议的(可能有人会觉得不爽);而且活跃度不太高;而且只有一个开发人员。大伙儿慎用!建议只拿它当参考。
  对于 C# 程序员,可以参考 CodeProject 上的一个示例

◇用于并发进程


  进程间的环形缓冲区,似乎少有现成的库可用。大伙儿只好自己动手、丰衣足食了。
  适合进行环形缓冲的 IPC 类型,常见的有“共享内存和文件”。在这两种方式上进行环形缓冲,通常都采用数组的方式实现。程序事先分配好一个固定长度的存储空间,然后具体的读写操作、判断“空”和“满”、元素存储等细节就可参照前面所说的来进行。
  共享内存方式的性能很好,适用于数据流量很大的场景。但是有些语言(比如 Java)对于共享内存不支持。因此,该方式在多语言协同开发的系统中,会有一定的局限性。
  而文件方式在编程语言方面支持很好,几乎所有编程语言都支持操作文件。但它可能会受限于磁盘读写(Disk I/O)的性能。所以文件方式不太适合于快速数据传输;但是对于某些“数据单元”很大的场合,文件方式是值得考虑的。
对于进程间的环形缓冲区,同样要考虑好进程间的同步、互斥等问题,限于篇幅,此处就不细说了。

  下一个帖子,咱们来聊一下双缓冲区的使用

回到本系列的目录
版权声明
本博客所有的原创文章,作者皆保留版权。转载必须包含本声明,保持本文完整,并以超链接形式注明作者编程随想和本文原始地址:
https://program-think.blogspot.com/2009/04/producer-consumer-pattern-3-circle.html

9 条评论

  1. 博主没有讲清楚为什么环形缓冲区相对于队列缓冲区具有性能优势。

    回复删除
  2. 感谢楼上的同学提意见,我又补充说明了一下两者实现上的差别。

    回复删除
  3. circbuf发布的代码里附带的License是GPL

    回复删除
  4. 楼上的同学,
    就因为circbuf是GPL协议,所以我才说它不太爽。象它这种以“库”的形式提供的开源项目,通常都采用LGPL而不是GPL。

    回复删除
  5. 在C++里面,STL中的容器默认使用STL提供的allocator实现来获取内存。至少在gcc的STL实现中,那东东就是个内存池,是只分配不释放的。而gcc中的deque实现,采用的是分段数组(不知道这玩意有没学名)的方式,也在很大程度上减少了队列长度增长时的重分配效应。而且这种方案没长度限制,在一定程度上。当然,还是要自个搞定并发的问题。

    回复删除
  6. 楼上的同学,
    allocator确实能够优化内存分配和释放。不过C++之外的语言,不一定有类似STL allocator的东东可用。这时候还是得考虑环形缓冲区。
    另外,circular_buffer相比STL的容器还是有某些优势的(否则boost也不会加入这个玩意儿了:-)。

    回复删除
  7. 另外,补充一下circular_buffer的介绍(摘自boost官方网站):
    The basic motivation behind the circular_buffer was to create a container which would work seamlessly with STL. Additionally, the design of the circular_buffer was guided by the following principles:
    1. Maximum efficiency for envisaged applications.
    2. Suitable for general purpose use.
    3. The behaviour of the buffer as intuitive as possible.
    4. Suitable for specialization by means of adaptors. (The circular_buffer_space_optimized is such an example of the adaptor.)
    5. Easy to debug. (See Debug Support for details.)

    In order to achieve maximum efficiency, the circular_buffer stores its elements in a contiguous region of memory, which then enables:
    1. Use of fixed memory and no implicit or unexpected memory allocation.
    2. Fast constant-time insertion and removal of elements from the front and back.
    3. Fast constant-time random access of elements.
    4. Suitability for real-time and performance critical applications.

    回复删除
  8. 多谢,看到这里,感觉到楼主在真心分享一些一线的经验。
    环形缓冲区也类似一种模式,有其使用场景的限定的,这点楼主也说的很明白。而且,模式一般也会稍微脱离一下具体实现语言的限制。

    回复删除
  9. 看来楼上的同学是老读者兼热心读者,经常发表一些评论,非常感谢 :)

    回复删除