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

深碍√TFBOYSˉ_ 2022-05-31 05:57 500阅读 0赞

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

文章目录

[★环形缓冲区 vs 队列缓冲区][vs]  
[★环形缓冲区的实现][Link 1]  
[★应用场合][Link 2]

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

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

### ◇外部接口相似 ###

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

### ◇内部结构迥异 ###

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

![不见图 请翻墙][KowoSKul1tsiKZX-Wv7rJ0BClVdrp8XWLElUklzft62PGTrL9LOwrX7oJhVxy2drCbIx-Wt2qSzyK-vpWbnFC8huDfWgX2h-V2Zaxo-t2njr_fEpWqf4cYI56WkYt7QyOAhuGWqW]

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

## ★环形缓冲区的实现 ##

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

### ◇数组方式 vs 链表方式 ###

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

![不见图 请翻墙][2NuMql3dVig1XdMDcDQ8T0FBgfSnukU0xsoi9etifAiyFxyKuV_neuaL_bbEb0DswdyR8mTWDkFJHvxZ1Jepl2KcvNFk8y3EPtc_RNDXtEjvHKHb1GWqpqPv2j8UtOg88LR6nZe9]

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

### ◇读写操作 ###

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

### ◇判断“空”和“满” ###

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

### ◇元素的存储 ###

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

## ★应用场合 ##

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

### ◇用于并发线程 ###

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

### ◇用于并发进程 ###

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

[3]: https://program-think.blogspot.com/2009/04/producer-consumer-pattern-3-circle.html
[vs]: https://program-think.blogspot.com/2009/04/producer-consumer-pattern-3-circle.html#head-1
[Link 1]: https://program-think.blogspot.com/2009/04/producer-consumer-pattern-3-circle.html#head-2
[Link 2]: https://program-think.blogspot.com/2009/04/producer-consumer-pattern-3-circle.html#head-3
[Link 3]: https://program-think.blogspot.com/2009/03/producer-consumer-pattern-2-queue.html
[KowoSKul1tsiKZX-Wv7rJ0BClVdrp8XWLElUklzft62PGTrL9LOwrX7oJhVxy2drCbIx-Wt2qSzyK-vpWbnFC8huDfWgX2h-V2Zaxo-t2njr_fEpWqf4cYI56WkYt7QyOAhuGWqW]: https://lh6.googleusercontent.com/KowoSKul1tsiKZX-Wv7rJ0BClVdrp8XWLElUklzft62PGTrL9LOwrX7oJhVxy2drCbIx-Wt2qSzyK-vpWbnFC8huDfWgX2h-V2Zaxo-t2njr_fEpWqf4cYI56WkYt7QyOAhuGWqW
[2NuMql3dVig1XdMDcDQ8T0FBgfSnukU0xsoi9etifAiyFxyKuV_neuaL_bbEb0DswdyR8mTWDkFJHvxZ1Jepl2KcvNFk8y3EPtc_RNDXtEjvHKHb1GWqpqPv2j8UtOg88LR6nZe9]: https://lh6.googleusercontent.com/2NuMql3dVig1XdMDcDQ8T0FBgfSnukU0xsoi9etifAiyFxyKuV_neuaL_bbEb0DswdyR8mTWDkFJHvxZ1Jepl2KcvNFk8y3EPtc_RNDXtEjvHKHb1GWqpqPv2j8UtOg88LR6nZe9
[boost]: http://www.boost.org/
[circular_buffer]: http://www.boost.org/libs/circular_buffer/
[circbuf]: http://sourceforge.net/projects/circbuf/
[CodeProject]: http://www.codeproject.com/KB/recipes/circularbuffer.aspx
[Link 4]: https://en.wikipedia.org/wiki/Shared_memory#In_software
[Link 5]: https://program-think.blogspot.com/2009/03/producer-consumer-pattern-1-data.html
[Link 6]: https://program-think.blogspot.com/2009/04/producer-consumer-pattern-4-double.html
[Link 7]: https://program-think.blogspot.com/2009/03/producer-consumer-pattern-0-overview.html#index