一种环形缓冲区读写方法和装置

摘要

本申请公开了一种环形缓冲区读写方法和装置，该方法包括：获取环形缓冲区的长度N，其中，环形缓冲区的长度为N标识环形缓冲区中有N个元素，环形缓冲区的相邻元素之间的地址间隔是相同的；将环形缓冲区分为M个组，其中，M个组中的每个组中的相邻元素之间的地址间隔是相同的；M个组分别作为环形缓冲区的子环形缓冲区，每个组为一个子环形缓冲区，子环形缓冲区的数量为M个；对M个子环形缓冲区中的一个或多个进行读操作，或者进行写操作。通过本申请解决了现有技术中的环形缓冲区对于同一操作一次只能有一个用户进行从而导致读写效率低的问题，在一定程度上提高了环形缓冲区的读写效率。

说明书

技术领域

本申请涉及到软件领域，具体而言，涉及一种环形缓冲区读写方法和装置。

背景技术

在程序中(例如，通信程序)，经常使用环形缓冲区作为数据结构来存放通信中发送和接收的数据。环形缓冲区是一个先进先出的循环缓冲区，可以向通信程序提供对缓冲区的互斥访问。

环形缓冲区通常有一个读指针和一个写指针。读指针指向环形缓冲区中可读的数据，写指针指向环形缓冲区中可写的缓冲区。通过移动读指针和写指针就可以实现缓冲区的数据读取和写入。在通常情况下，环形缓冲区的读用户仅仅会影响读指针，而写用户仅仅会影响写指针。如果仅仅有一个读用户和一个写用户，那么不需要添加互斥保护机制就可以保证数据的正确性。如果有多个读写用户访问环形缓冲区，那么必须添加互斥保护机制来确保多个用户互斥访问环形缓冲区。

也就是说，对于环形缓冲区的读操作或者写操作来说，其最多有一个用户来进行，这就在一定程度上降低了读写数据的效率。

发明内容

本申请实施例提供了一种环形缓冲区读写方法和装置，以至少解决现有技术中的环形缓冲区对于同一操作一次只能有一个用户进行从而导致读写效率低的问题。

根据本申请的一个方面，提供了一种环形缓冲区读写方法，包括：获取环形缓冲区的长度N，其中，所述环形缓冲区的长度为N标识所述环形缓冲区中有N个元素，所述环形缓冲区的相邻元素之间的地址间隔是相同的；将所述环形缓冲区分为M个组，其中，所述M个组中的每个组中的相邻元素之间的地址间隔是相同的；所述M个组分别作为所述环形缓冲区的子环形缓冲区，每个组为一个子环形缓冲区，所述子环形缓冲区的数量为M个；对所述M个子环形缓冲区中的一个或多个进行读操作，或者进行写操作。

进一步地，对所述M个子环形缓冲区中的一个或多个进行读操作包括：在对所述环形缓冲区进行写操作的情况下，从所述M个子环形缓冲区中的多个子环形缓冲区进行读操作；或者，对所述M个子环形缓冲区中的一个或多个进行写操作包括：在对所述环形缓冲区进行读操作的情况下，从所述M个子环形缓冲区中的多个子环形缓冲区进行写操作。

进一步地，所述N大于等于所述M，所述N和所述M均为正整数，所述N能被所述M整除。

进一步地，每个所述子环形缓冲区中的相邻元素之间的地址间隔均相同。

进一步地，所述环形缓冲区的第p个元素的地址为：(i*p+offset)％N，其中，i为所述环形缓冲区的相邻元素之间的地址间隔，offset为第0个元素的地址，N为所述环形缓冲区的长度，％为模运算；每个所述子环形缓冲区的第p个元素的地址为：(j*p+m)％N，其中，j为所述子环形缓冲区的相邻元素之间的地址间隔，m为每个子环形缓冲区第0个元素的地址，其中，j大于i。

根据本申请的另一个方面，还提供了一种环形缓冲区读写装置，包括：获取模块，用于获取环形缓冲区的长度N，其中，所述环形缓冲区的长度为N标识所述环形缓冲区中有N个元素，所述环形缓冲区的相邻元素之间的地址间隔是相同的；划分模块，用于将所述环形缓冲区分为M个组，其中，所述M个组中的每个组中的相邻元素之间的地址间隔是相同的，所述M个组分别作为所述环形缓冲区的子环形缓冲区，每个组为一个子环形缓冲区，所述子环形缓冲区的数量为M个；读写模块，用于对所述M个子环形缓冲区中的一个或多个进行读操作，或者进行写操作。

进一步地，所述读写模块用于在对所述环形缓冲区进行写操作的情况下，从所述M个子环形缓冲区中的多个子环形缓冲区进行读操作；或者，所述读写模块用于在对所述环形缓冲区进行读操作的情况下，从所述M个子环形缓冲区中的多个子环形缓冲区进行写操作。

进一步地，所述N大于等于所述M，所述N和所述M均为正整数，所述N能被所述M整除。

进一步地，每个所述子环形缓冲区中的相邻元素之间的地址间隔均相同。

进一步地，所述环形缓冲区的第p个元素的地址为：(i*p+offset)％N，其中，i为所述环形缓冲区的相邻元素之间的地址间隔，offset为第0个元素的地址，N为所述环形缓冲区的长度，％为模运算；每个所述子环形缓冲区的第p个元素的地址为：(j*p+m)％N，其中，j为所述子环形缓冲区的相邻元素之间的地址间隔，m为每个子环形缓冲区第0个元素的地址，其中，j大于i。

在本申请实施例中，采用了获取环形缓冲区的长度N，其中，所述环形缓冲区的长度为N标识所述环形缓冲区中有N个元素，所述环形缓冲区的相邻元素之间的地址间隔是相同的；将所述环形缓冲区分为M个组，其中，所述M个组中的每个组中的相邻元素之间的地址间隔是相同的；所述M个组分别作为所述环形缓冲区的子环形缓冲区，每个组为一个子环形缓冲区，所述子环形缓冲区的数量为M个；对所述M个子环形缓冲区中的一个或多个进行读操作，或者进行写操作。通过本申请解决了现有技术中的环形缓冲区对于同一操作一次只能有一个用户进行从而导致读写效率低的问题，在一定程度上提高了环形缓冲区的读写效率。

附图说明

构成本申请的一部分的附图用来提供对本申请的进一步理解，本申请的示意性实施例及其说明用于解释本申请，并不构成对本申请的不当限定。在附图中：

图1是根据本申请实施例的环形缓冲区读写方法的流程图。

具体实施方式

需要说明的是，在不冲突的情况下，本申请中的实施例及实施例中的特征可以相互组合。下面将参考附图并结合实施例来详细说明本申请。

需要说明的是，在附图的流程图示出的步骤可以在诸如一组计算机可执行指令的计算机系统中执行，并且，虽然在流程图中示出了逻辑顺序，但是在某些情况下，可以以不同于此处的顺序执行所示出或描述的步骤。

在本实施例中，提供了一种环形缓冲区读写方法，图1是根据本申请实施例的环形缓冲区读写方法的流程图，如图1所示，该流程包括如下步骤：

步骤S102，获取环形缓冲区的长度N，其中，环形缓冲区的长度为N标识环形缓冲区中有N个元素，环形缓冲区的相邻元素之间的地址间隔是相同的；

步骤S104，将环形缓冲区分为M个组，其中，M个组中的每个组中的相邻元素之间的地址间隔是相同的；M个组分别作为环形缓冲区的子环形缓冲区，每个组为一个子环形缓冲区，子环形缓冲区的数量为M个；

步骤S106，对M个子环形缓冲区中的一个或多个进行读操作，或者进行写操作。

在环形缓冲区中，如果仅仅有一个读用户和一个写用户，那么不需要添加互斥保护机制就可以保证数据的正确性。如果有多个读写用户访问环形缓冲区，那么必须添加互斥保护机制来确保多个用户互斥访问环形缓冲区。因此，对于一个环形缓冲区中读操作是不能并发的，同理多个写操作也是不能并发的，这导致读写的效率比较低。通过上述步骤，将一个环形缓冲区分为了多个子环形缓冲区，在进行读操作的时候，只要保证在一个子环形缓冲区的读操作或者写操作只有一个用户在进行即可，因此，对于环形缓冲区来说，这是由于子环形缓冲区的划分，可以并发M个读操作，或者也可以并发M个写操作，这种读写效率相对于为划分子环形缓冲区来说，提高了很多。通过上述步骤解决了现有技术中的环形缓冲区对于同一操作一次只能有一个用户进行从而导致读写效率低的问题，在一定程度上提高了环形缓冲区的读写效率。

对于一个环形缓冲区而言，可以同时进行读操作和写操作。为了方便描述，在下文中将环形缓冲区称为父环，将子环形缓冲区称为子环。如果将父环看做是一个环形缓冲区来进行写操作的时候，此时，如果需要进行数据读取操作，而这些数据恰好分布在不同的子环中，此时，可以将每个子环看成是一个独立的环形缓冲区。即在对环形缓冲区进行写操作的情况下，从M个子环形缓冲区中的多个子环形缓冲区进行读操作。

同理，将父环看成一个环形缓冲区进行读操作的时候，此时，如果需要写数据，如果需要写入的数据只有一个，那么可以将父环看成是一个环形缓冲区来进行写数据。如果需要写入数据为多个，那么可以将每个子环看成是一个独立的环形缓冲区来进行写操作。即在对环形缓冲区进行读操作的情况下，从M个子环形缓冲区中的多个子环形缓冲区进行写操作。

上述这种处理方式可以看作数据扇入和数据扇出，一个父环写入数据，多个子环读取数据，这就实现了数据扇出，以此可以构建数据广播。多个子环写入数据，一个父环读取数据，这就实现了数据扇入，以此可以构建数据汇总。

在上述两种实施方式中，可以忽略父环写数据或者读数据的互斥机制，作为另一种实施时方式，可以在多个子环中读数据，也可以在多个子环中写数据，但是，在同一个子环中保持互斥机制，即在同一子环中同时读数据的只能有一个操作，在同一子环写数据的也只能只有一个操作。

为了更快的进行数据处理，当环形缓存(称为父环，下同)经过同态寻址而切分成多个环形缓存(称为子环，下同)之后，子环之间可以无锁寻址；父环与子环之间也可以通过无锁的方式寻址。因为寻址是无锁的，所以环与环之间的读写相互不影响。这种无锁缓存可以提高环形缓冲的i/o吞吐率。

作为另一个可选的实施方式，当需要同时写入的数据量超过子环的数量的情况下，从多个子环中选择至少一个子环继续划分，将选择出来的每个子环再分别划分出多个子环(孙子环)。在选择子环的时候，可以选择存储数据量最少的子环进行划分。

划分子环的方式有很多个，例如，可以将父环平均划分中容量相同(即长度相同)的几个子环，即，N大于等于M，N和M均为正整数，N能被M整除。或者，也可以每个子环均由不同的长度，或者，在划分几个子环之后，父环剩余的部分仍然按照父环数据读写的方式来进行读写。

作为一个优选的实施方式，每个子环形缓冲区中的相邻元素之间的地址间隔均相同。例如，环形缓冲区的第p个元素的地址为：(i*p+offset)％N，其中，i为环形缓冲区的相邻元素之间的地址间隔，offset为第0个元素的地址，N为环形缓冲区的长度，％为模运算；每个子环形缓冲区的第p个元素的地址为：(j*p+m)％N，其中，j为子环形缓冲区的相邻元素之间的地址间隔，m为每个子环形缓冲区第0个元素的地址，其中，j大于i。

在这种情况，父环和子环的寻址方式是一致的，可以采用同一套程序，从而简化程序设计。在读数据和写数据之前，均需要寻址，同一套寻址程序会使得开发读写数据的功能变得简洁。

这种方式可以应该用在IC设计中，以父环或者若干子环的读写端，作为缓存的i/o端，可以实现多端缓存。各个i/o端之间的读写，可以做到相互不影响。经过适当的环资源管理，还可以支持端的动态分配。因为父环和子环的具有相同的寻址方法，所以寻址逻辑电路可以一定程度的复用和简化。

在本实施例中，还提供一种电子装置，包括存储器和处理器，存储器中存储有计算机程序，处理器被设置为运行计算机程序以执行以上实施例中的方法。

这些计算机程序也可装载到计算机或其他可编程数据处理设备上，使得在计算机或其他可编程设备上执行一系列操作步骤以产生计算机实现的处理，从而在计算机或其他可编程设备上执行的指令提供用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的步骤，对应与不同的步骤可以通过不同的模块来实现。

上述程序可以运行在处理器中，或者也可以存储在存储器中(或称为计算机可读介质)，计算机可读介质包括永久性和非永久性、可移动和非可移动媒体可以由任何方法或技术来实现信息存储。信息可以是计算机可读指令、数据结构、程序的模块或其他数据。计算机的存储介质的例子包括，但不限于相变内存(PRAM)、静态随机存取存储器(SRAM)、动态随机存取存储器(DRAM)、其他类型的随机存取存储器(RAM)、只读存储器(ROM)、电可擦除可编程只读存储器(EEPROM)、快闪记忆体或其他内存技术、只读光盘只读存储器(CD-ROM)、数字多功能光盘(DVD)或其他光学存储、磁盒式磁带，磁带磁磁盘存储或其他磁性存储设备或任何其他非传输介质，可用于存储可以被计算设备访问的信息。按照本文中的界定，计算机可读介质不包括暂存电脑可读媒体(transitory media)，如调制的数据信号和载波。

该电子装置中还可以包括一个软件模块构成的装置或系统，该装置或系统中的模块与上述实施例中的步骤相对应，已经进行说明的，在此不再赘述。例如，在本实施例中该软件模块构成的装置或系统，可以称为环形缓冲区读写装置，包括：获取模块，用于获取环形缓冲区的长度N，其中，环形缓冲区的长度为N标识环形缓冲区中有N个元素，环形缓冲区的相邻元素之间的地址间隔是相同的；划分模块，用于将环形缓冲区分为M个组，其中，M个组中的每个组中的相邻元素之间的地址间隔是相同的，M个组分别作为环形缓冲区的子环形缓冲区，每个组为一个子环形缓冲区，子环形缓冲区的数量为M个；读写模块，用于对M个子环形缓冲区中的一个或多个进行读操作，或者进行写操作。

作为另一个优选实施方式，每个子环形缓冲区中的相邻元素之间的地址间隔均相同。在装置中，还可以包括寻址模块，该寻址模块用于根据如下元素地址的计算方式来对父环和子环进行寻址：环形缓冲区的第p个元素的地址为：(i*p+offset)％N，其中，i为环形缓冲区的相邻元素之间的地址间隔，offset为第0个元素的地址，N为环形缓冲区的长度，％为模运算；每个子环形缓冲区的第p个元素的地址为：(j*p+m)％N，其中，j为子环形缓冲区的相邻元素之间的地址间隔，m为每个子环形缓冲区第0个元素的地址，其中，j大于i。

在寻址模块进行寻址之后，作为一个优选的实施方式，读写模块用于在对环形缓冲区进行写操作的情况下，从M个子环形缓冲区中的多个子环形缓冲区进行读操作；或者，读写模块用于在对环形缓冲区进行读操作的情况下，从M个子环形缓冲区中的多个子环形缓冲区进行写操作。

下面结合一个在通信软件中使用的切分环形缓冲的例子进行说明。该例子可以用在通信软件中也可以用在其他软件中。

长度N(其中N为正整数，下同)的连续存储空间的成环机制，是将随机地址addr(其中addr>＝0)对N做模运算，所得数值会在[0,N-1]闭区间内循环分布。以此数值寻址就会使存储空间首尾相连而形成环。特别地，当N为2的非负整数次幂时，对N做模运算可以简化成对N-1做位与运算。该例子中讨论通常情况，至于这种特殊情况，包含在通常情况之中。

寻址方法

在长度N的环形缓冲中，相邻元素的地址间隔为1。假设以地址为offset的某个元素作为第0个元素，那么第p个元素的地址为：(1*p+offset)％N，其中％为模运算，下同。

对于长度N的环形缓冲，将元素次第反复地切分成M组(其中N、M均为正整数，N>＝M，N可被M整除)，使得任意1个元素属于且仅属于1个组。可知每组长度均为N/M。

由于N/M是正整数，依照上文的成环机制，可知切分得到的任意一组都是环。将第m组(其中0<＝m<＝M-1，下同)的第i个元素记为E_m_i，切分方法如下所示:

E_0_0,E_1_0,...,E_M-1_0,E_0_1,E_1_1,...,E_M-1_1,...,E_0_N/M-1,E_1_N/M-1,...,E_M-1_N/M-1

对于任意的第m组，相邻元素间隔为M，第0个元素地址为m。那么第p个元素的寻址方法为：(M*p+m)％N，由此可见，将长度N的环形缓冲(简称父环)，按照上述切分方法，可以切分成M个长度为N/M的环形缓冲(简称子环)，任意2个子环不相交。对比公式(0.1)和(1.1)可知，对于任意子环的任意元素，具有和父环元素同态的寻址方式。

由于父环和子环具有同态的寻址方式，可以仅使用一套程序实现父环或任意子环的寻址，简化程序设计。

切分之后，子环之间可以并发寻址；父环与子环之间也可以通过有锁或无锁的方式实现并发寻址。并发过程中，环与环之间的读写相互不影响。这种读写分离的实现，可以提高环形缓冲的i/o吞吐率。

可以构建若干拓扑应用。比如：1个父环写入，多个子环读取，可以实现数据扇出。多个子环写入，1个父环读取，可以实现数据归并。

以上仅为本申请的实施例而已，并不用于限制本申请。对于本领域技术人员来说，本申请可以有各种更改和变化。凡在本申请的精神和原理之内所作的任何修改、等同替换、改进等，均应包含在本申请的权利要求范围之内。