文档章节

架构设计:生产者/消费者模式 第5页:环形缓冲区

冰雷卡尔
 冰雷卡尔
发布于 2014/05/06 15:27
字数 1072
阅读 128
收藏 0

[3]:环形缓冲区

    前一个帖子提及了队列缓冲区可能存在的性能问题及解决方法:环形缓冲区。今天就专门来描述一下这个话题。

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

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

    ◇外部接口相似

    在介绍环形缓冲区之前,咱们先来回顾一下普通的队列。普通的队列有一个写入端和一个读出端。队列为空的时候,读出端无法读取数据;当队列满(达到最大尺寸)时,写入端无法写入数据。

    对于使用者来讲,环形缓冲区和队列缓冲区是一样的。它也有一个写入端(用于push)和一个读出端(用于pop),也有缓冲区“满”和“空”的状态。所以,从队列缓冲区切换到环形缓冲区,对于使用者来说能比较平滑地过渡。

    ◇内部结构迥异

    虽然两者的对外接口差不多,但是内部结构和运作机制有很大差别。队列的内部结构此处就不多啰嗦了。重点介绍一下环形缓冲区的内部结构。

    大伙儿可以把环形缓冲区的读出端(以下简称R)和写入端(以下简称W)想象成是两个人在体育场跑道上追逐(R追W)。当R追上W的时候,就是缓冲区为空;当W追上R的时候(W比R多跑一圈),就是缓冲区满。

    为了形象起见,去找来一张图并略作修改,如下:

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

    ★环形缓冲区的实现

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

    ◇数组方式 vs 链表方式

    环形缓冲区的内部实现,即可基于数组(此处的数组,泛指连续存储空间)实现,也可基于链表实现。

    数组在物理存储上是一维的连续线性结构,可以在初始化时,把存储空间一次性分配好,这是数组方式的优点。但是要使用数组来模拟环,你必须在逻辑上把数组的 头和尾相连。在顺序遍历数组时,对尾部元素(最后一个元素)要作一下特殊处理。访问尾部元素的下一个元素时,要重新回到头部元素(第0个元素)。如下图所 示:

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

    ◇读写操作

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

本文转载自:http://blog.csdn.net/caisini_vc/article/details/5599537

冰雷卡尔
粉丝 30
博文 116
码字总数 81854
作品 0
深圳
程序员
私信 提问
架构设计:生产者/消费者模式 第3页:队列缓冲区

[2]:队列缓冲区 经过前面两个帖子的铺垫,今天终于开始聊一些具体的编程技术了。由于不同的缓冲区类型、不同的并发场景对于具体的技术实现有较大的影响。为了深入浅出、便 于大伙儿理解,咱...

冰雷卡尔
2014/05/06
98
0
读program_think生产者消费者模式有感

针对个人在开发的一个搜索工具,因为之前并没有设计,有现成的,但是需要做一个内部使用的工具,所以就做了个山寨版,没有设计,直接上手开发,看了program_think的博文后,突然想起以前的自...

shawn chen
2011/02/12
210
0
架构设计:生产者/消费者模式 第6页:环形缓冲区的实现

◇判断“空”和“满” 上述的操作并不复杂,不过有一个小小的麻烦:空环和满环的时候,R和W都指向同一个位置!这样就无法判断到底是“空”还是“满”。大体上有两种方法可以解决该问题。 办法...

冰雷卡尔
2014/05/06
223
0
架构设计:生产者/消费者模式 第1页:“生产者/消费者模式”介绍

★简介 在实际的软件开发过程中,经常会碰到如下场景:某个模块负责产生数据,这些数据由另一个模块来负责处理(此处的模块是广义的,可以是类、函数、线程、进程等)。产生数据的模块,就形...

冰雷卡尔
2014/05/06
125
0
架构设计:生产者/消费者模式 第4页:注意事项

顺便补充几个注意事项,大伙儿留意一下: 1、对stdio进行读写操作是以阻塞方式进行。比如管道中没有数据,消费者进程的读操作就会一直停在哪儿,直到管道中重新有数据。 2、由于stdio内部带有...

冰雷卡尔
2014/05/06
63
0

没有更多内容

加载失败,请刷新页面

加载更多

二叉树交换左右子树

树的实现类 public class TreeNode {public int val;public TreeNode left;public TreeNode right;public TreeNode(int x) {val = x;}public TreeNode(int val, TreeN......

jxlgzwh
21分钟前
9
0
在Workstation 15上测试vShere 6.7+vCenter Server

想学习vSphere,最好能在自己的电脑上搭建相应的学习环境,如下图所示: _________________________________ | ...

大别阿郎
24分钟前
8
0
centos7上部署vnc服务器并实现远程桌面

centos7上部署vnc服务器并实现远程桌面 centos7上进行一下操作 [root@localhost ~]# yum install tigervnc-server -y#安装vnc服务器 Loaded plugins: fastestmirror, langpacks base | 3.6 ......

恩多
27分钟前
9
0
CSS--表格

一、表格的常用属性 1、边距属性padding(td的mrgin无效) 2、边框属性border 3、尺寸属性 width height 4、文本格式 font-* text-* line-height 5、背景属性 颜色,图片,渐变 二、特有属性...

wytao1995
44分钟前
5
0
zookeeper - leader选举

让我们分析如何在ZooKeeper集合中选举leader节点。考虑一个集群中有N个节点。leader选举的过程如下: 所有节点创建具有相同路径 /app/leader_election/guid_ 的顺序、临时节点。 ZooKeeper集...

Canaan_
55分钟前
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部