RAID卡集群对队列的处理方法、系统、设备和介质

摘要

本发明涉及存储服务器领域。本发明提供一种RAID卡集群对队列的处理方法、系统、设备和存储介质，处理方法包括：读取环形队列的原始头部和原始全局原子变量；根据原始头部和原始全局原子变量确定队列剩余空间，根据队列剩余空间和需要加入环形队列的队列元素的数量的大小确定入队操作的队列元素个数；根据原始全局原子变量和入队操作的队列元素个数构造新全局原子变量，根据原始全局原子变量和新全局原子变量做原子操作；响应于原子操作的返回值为原始全局原子变量，将需要加入环形队列的队列元素填充环形队列中的对应位置；响应于存在需要离开环形队列的队列元素，从队列头部开始删除对应数量的队列元素。本发明提高了环形队列的处理性能。

权利要求

1.一种RAID卡集群对队列的处理方法，其特征在于，包括如下步骤：响应于存在需要加入环形队列的队列元素，读取环形队列的原始头部和原始全局原子变量，所述原始全局原子变量包括原始引用索引、原始队列元素索引和原始当前相位；

根据所述原始头部和原始全局原子变量确定队列剩余空间，并根据所述队列剩余空间和需要加入环形队列的队列元素的数量的大小确定入队操作的队列元素个数；

根据所述原始全局原子变量和所述入队操作的队列元素个数构造新全局原子变量，并根据所述原始全局原子变量和所述新全局原子变量做原子操作；

响应于所述原子操作的返回值为所述原始全局原子变量，将需要加入环形队列的队列元素填充到环形队列中的对应位置；以及响应于存在需要离开环形队列的队列元素，从队列头部开始删除对应数量的队列元素。

2.根据权利要求1所述的RAID卡集群对队列的处理方法，其特征在于，所述根据所述原始头部和原始全局原子变量确定队列剩余空间包括：将所述原始全局原子变量中的原始队列元素索引与所述原始头部的差值减一得到中间结果；以及将所述中间结果除以环形队列能容纳的最大队列元素数得到的余数作为队列剩余空间。

3.根据权利要求1所述的RAID卡集群对队列的处理方法，其特征在于，所述根据所述队列剩余空间和需要加入环形队列的队列元素的数量的大小确定入队操作的队列元素个数包括：将所述队列剩余空间和需要加入环形队列的队列元素的数量之间的最小值作为入队操作的队列元素个数。

4.根据权利要求3所述的RAID卡集群对队列的处理方法，其特征在于，所述根据所述原始全局原子变量和所述入队操作的队列元素个数构造新全局原子变量包括：将所述原始全局原子变量的原始引用索引加一作为所述新全局原子变量的新引用索引；以及将所述原始全局原子变量的原始队列元素索引与所述入队操作的队列元素个数的和作为第二中间结果，并将所述第二中间结果除以环形队列能容纳的最大队列元素数得到的余数作为所述新全局原子变量的新队列元素索引。

5.根据权利要求1所述的RAID卡集群对队列的处理方法，其特征在于，所述处理方法还包括：响应于所述原子操作的返回值不为所述原始全局原子变量，重新检查队列剩余空间。

6.根据权利要求1所述的RAID卡集群对队列的处理方法，其特征在于，所述将需要加入环形队列的队列元素填充到环形队列中的对应位置包括：填充原始队列元素索引到新队列元素索引之间的队列元素。

7.根据权利要求6所述的RAID卡集群对队列的处理方法，其特征在于，所述填充原始队列元素索引到新队列元素索引之间的队列元素包括：将原始全局原子变量的原始当前相位设置为当前相位，并设置每个队列元素的序号逐个减小。

8.根据权利要求7所述的RAID卡集群对队列的处理方法，其特征在于，所述设置每个队列元素的序号逐个减小包括：将从入队操作的队列元素个数减一作为队列元素的序号的初始值，并设置出首个队列元素之外的每个队列元素的序号相比于前一个相邻队列元素的序号小一。

9.根据权利要求8所述的RAID卡集群对队列的处理方法，其特征在于，所述将需要加入环形队列的队列元素填充到环形队列中的对应位置包括：设置填充操作的最后一步为对原始队列元素索引对应的队列元素的当前相位的进行赋值。

10.根据权利要求1所述的RAID卡集群对队列的处理方法，其特征在于，所述处理方法还包括：根据队列尾部、原始队列元素索引和新队列元素索引做第二原子操作以判断尾部寄存器是否更新成功。

11.根据权利要求10所述的RAID卡集群对队列的处理方法，其特征在于，所述根据队列尾部、原始队列元素索引和新队列元素索引做第二原子操作以判断尾部寄存器是否更新成功包括：响应于所述第二原子操作返回值为原始队列元素索引，则表明尾部寄存器更新成功，否则尾部寄存器更新失败。

12.根据权利要求11所述的RAID卡集群对队列的处理方法，其特征在于，所述处理方法还包括：根据新队列元素索引后的第一个队列元素判断尾部寄存器是否更新成功。

13.根据权利要求12所述的RAID卡集群对队列的处理方法，其特征在于，所述根据新队列元素索引后的第一个队列元素判断尾部寄存器是否更新成功包括：响应于新队列元素索引后的第一个队列元素的队列元素索引不为零且所述第一个队列元素的当前相位等于原始当前相位，则表示尚未更新所述尾部寄存器。

14.根据权利要求13所述的RAID卡集群对队列的处理方法，其特征在于，所述根据新队列元素索引后的第一个队列元素判断尾部寄存器是否更新成功包括：响应于新队列元素索引后的第一个队列元素的队列元素索引为零且所述第一个队列元素的当前相位不等于原始当前相位，则表示尚未更新所述尾部寄存器。

15.根据权利要求14所述的RAID卡集群对队列的处理方法，其特征在于，所述方法还包括：响应于尚未更新所述尾部寄存器，设置所述原始队列元素索引等于新队列元素索引。

16.根据权利要求15所述的RAID卡集群对队列的处理方法，其特征在于，所述处理方法还包括：将新队列元素索引后的第一个队列元素的序号和原始队列元素索引值的和作为第三中间结果，将所述第三中间结果除以环形队列能容纳的最大队列元素数得到的余数作为新队列元素索引。

17.根据权利要求1所述的RAID卡集群对队列的处理方法，其特征在于，所述处理方法还包括：每次写访问将引用索引加一，在每个当前轮次中将当前相位按照一和零交替变化。

18.一种RAID卡集群对队列的处理系统，其特征在于，包括：设置模块，配置用于响应于存在需要加入环形队列的队列元素，读取环形队列的原始头部和原始全局原子变量，所述原始全局原子变量包括原始引用索引、原始队列元素索引和原始当前相位；

确定模块，配置用于根据所述原始头部和原始全局原子变量确定队列剩余空间，并根据所述队列剩余空间和需要加入环形队列的队列元素的数量的大小确定入队操作的队列元素个数；

构造模块，配置用于根据所述原始全局原子变量和所述入队操作的队列元素个数构造新全局原子变量，并根据所述原始全局原子变量和所述新全局原子变量做原子操作；

填充模块，配置用于响应于所述原子操作的返回值为所述原始全局原子变量，将需要加入环形队列的队列元素填充到环形队列中的对应位置；以及删除模块，配置用于响应于存在需要离开环形队列的队列元素，从队列头部开始删除对应数量的队列元素。

19.一种计算机设备，其特征在于，包括：

至少一个处理器；以及

存储器，所述存储器存储有可在所述处理器上运行的计算机指令，所述指令由所述处理器执行时实现权利要求1‑17任意一项所述处理方法的步骤。

20.一种计算机可读存储介质，所述计算机可读存储介质存储有计算机程序，其特征在于，所述计算机程序被处理器执行时实现权利要求1‑17任意一项所述处理方法的步骤。

说明书

RAID卡集群对队列的处理方法、系统、设备和介质

技术领域

[0001] 本发明涉及存储服务器领域，更具体地，特别是指一种RAID卡集群对队列的处理方法、系统、设备和存储介质。

背景技术

[0002] 近些年随着芯片技术的不断发展，硬RAID（Redundant Array of Independent Disks，独立磁盘冗余阵列）存储技术应运而生，硬RAID存储技术中最重要的组成单元便是RAID卡，RAID卡将软RAID存储系统中的一些算法、数据管理以及一些逻辑功能都交给硬件管理和实现，以达到提高存储系统的数据安全性和存储I/O性能的目的。目前业界将单CPU核的RAID卡升级为多核RAID卡，由多个CPU核组成一个加速集群，其中每个CPU核都为一个加速单元。

[0003] 当队列存在多CPU核向其抛出分块落盘操作任务时（即缓存队列存在多个生产者时），多个生产者需要使用一定的机制来避免多个入队操作之间发生冲突。目前业界采用的技术方案是：多个CPU核生产者使用互斥机制、并对入队行为做串行化，保证同一时间只能有一个生产者在做入队操作，但是这样一来由于互斥锁的存在就必然会降低并发性能。当前持有互斥锁的CPU核负责执行自己和其他CPU核移交的QE的入队工作。这样的技术实现细节就需要多个CPU核共同维护入队互斥锁EQlock，和一个无锁的单链表等待队列Qwait，这个等待队列Qwait是所有CPU核生产者共享的。这样，在执行入队和出队操作时，如果其他CPU核持有互斥锁，当前CPU核必须等待持有互斥锁的CPU核对该锁释放后才能执行入队和出队的操作；在RAID卡中申请一个等待队列Qwait会致使本来就紧张的内存资源更加紧张，进而导致RAID卡的读写I/O性能降低；可能会产生额外的Qwait链表操作开销和QE的拷贝开销。

发明内容

[0004] 有鉴于此，本发明实施例的目的在于提出一种RAID卡集群对队列的处理方法、系统、计算机设备及计算机可读存储介质，本发明设计了无锁的多CPU核生产者的入队和出队操作，在原始队列定义的基础上，对环形队列增加了轮次（Round）的定义，从QE0到QEN‑1的一次完整的入队称为一轮，生产者和消费者需要各自维护一个“当前轮次”的变量current_phase，该变量按照每轮1‑>0‑>1‑>0的顺序，对环形队列中的QE增加了序号（SN：sequence number）的概念，增加了一个全局原子变量Tail_Req，以实现队列吞吐率峰值不再受限于多CPU核的互斥锁和等待队列对性能的瓶颈影响。

[0005] 基于上述目的，本发明实施例的一方面提供了一种RAID卡集群对队列的处理方法，包括如下步骤：响应于存在需要加入环形队列的队列元素，读取环形队列的原始头部和原始全局原子变量，所述原始全局原子变量包括原始引用索引、原始队列元素索引和原始当前相位；根据所述原始头部和原始全局原子变量确定队列剩余空间，并根据所述队列剩余空间和需要加入环形队列的队列元素的数量的大小确定入队操作的队列元素个数；根据所述原始全局原子变量和所述入队操作的队列元素个数构造新全局原子变量，并根据所述原始全局原子变量和所述新全局原子变量做原子操作；响应于所述原子操作的返回值为所述原始全局原子变量，将需要加入环形队列的队列元素填充到环形队列中的对应位置；以及响应于存在需要离开环形队列的队列元素，从队列头部开始删除对应数量的队列元素。

[0006] 在一些实施方式中，所述根据所述原始头部和原始全局原子变量确定队列剩余空间包括：将所述原始全局原子变量中的原始队列元素索引与所述原始头部的差值减一得到中间结果；以及将所述中间结果除以环形队列能容纳的最大队列元素数得到的余数作为队列剩余空间。

[0007] 在一些实施方式中，所述根据所述队列剩余空间和需要加入环形队列的队列元素的数量的大小确定入队操作的队列元素个数包括：将所述队列剩余空间和需要加入环形队列的队列元素的数量之间的最小值作为入队操作的队列元素个数。

[0008] 在一些实施方式中，所述根据所述原始全局原子变量和所述入队操作的队列元素个数构造新全局原子变量包括：将所述原始全局原子变量的原始引用索引加一作为所述新全局原子变量的新引用索引；以及将所述原始全局原子变量的原始队列元素索引与所述入队操作的队列元素个数的和作为第二中间结果，并将所述第二中间结果除以环形队列能容纳的最大队列元素数得到的余数作为所述新全局原子变量的新队列元素索引。

[0009] 在一些实施方式中，所述处理方法还包括：响应于所述原子操作的返回值不为所述原始全局原子变量，重新检查队列剩余空间。

[0010] 在一些实施方式中，所述将需要加入环形队列的队列元素填充环形队列中的对应位置包括：填充原始队列元素索引到新队列元素索引之间的队列元素。

[0011] 在一些实施方式中，所述填充原始队列元素索引到新队列元素索引之间的队列元素包括：将原始全局原子变量的原始当前相位设置为当前相位，并设置每个队列元素的序号逐个减小。

[0012] 在一些实施方式中，所述设置每个队列元素的序号逐个减小包括：将从入队操作的队列元素个数减一作为队列元素的序号的初始值，并设置出首个队列元素之外的每个队列元素的序号相比于前一个相邻队列元素的序号小一。

[0013] 在一些实施方式中，所述将需要加入环形队列的队列元素填充环形队列中的对应位置包括：设置填充操作的最后一步为对原始队列元素索引对应的队列元素的当前相位的进行赋值。

[0014] 在一些实施方式中，所述处理方法还包括：根据队列尾部、原始队列元素索引和新队列元素索引做第二原子操作以判断尾部寄存器是否更新成功。

[0015] 在一些实施方式中，所述根据队列尾部、原始队列元素索引和新队列元素索引做第二原子操作以判断尾部寄存器是否更新成功包括：响应于所述第二原子操作返回值为原始队列元素索引，则表明尾部寄存器更新成功，否则尾部寄存器更新失败。

[0016] 在一些实施方式中，所述处理方法还包括：根据新队列元素索引后的第一个队列元素判断尾部寄存器是否更新成功。

[0017] 在一些实施方式中，所述根据新队列元素索引后的第一个队列元素判断尾部寄存器是否更新成功包括：响应于新队列元素索引后的第一个队列元素的队列元素索引不为零且所述第一个队列元素的当前相位等于原始当前相位，则表示尚未更新所述尾部寄存器。

[0018] 在一些实施方式中，所述根据新队列元素索引后的第一个队列元素判断尾部寄存器是否更新成功包括：响应于新队列元素索引后的第一个队列元素的队列元素索引为零且所述第一个队列元素的当前相位不等于原始当前相位，则表示尚未更新所述尾部寄存器。

[0019] 在一些实施方式中，所述处理方法还包括：响应于尚未更新所述尾部寄存器，设置所述原始队列元素索引等于新队列元素索引。

[0020] 在一些实施方式中，所述处理方法还包括：将新队列元素索引后的第一个队列元素的序号和原始队列元素索引值的和作为第三中间结果，将所述第三中间结果除以环形队列能容纳的最大队列元素数得到的余数作为新队列元素索引。

[0021] 在一些实施方式中，所述设置包括引用索引、队列元素索引和当前相位的全局原子变量包括：每次写访问增加一次引用索引，当前相位在每个当前轮次中都按照一和零交替变化。

[0022] 本发明实施例的另一方面，提供了一种RAID卡集群对队列的处理系统，包括：设置模块，配置用于响应于存在需要加入环形队列的队列元素，读取环形队列的原始头部和原始全局原子变量，所述原始全局原子变量包括原始引用索引、原始队列元素索引和原始当前相位；确定模块，配置用于根据所述原始头部和原始全局原子变量确定队列剩余空间，并根据所述队列剩余空间和需要加入环形队列的队列元素的数量的大小确定入队操作的队列元素个数；构造模块，配置用于根据所述原始全局原子变量和所述入队操作的队列元素个数构造新全局原子变量，并根据所述原始全局原子变量和所述新全局原子变量做原子操作；填充模块，配置用于响应于所述原子操作的返回值为所述原始全局原子变量，将需要加入环形队列的队列元素填充到环形队列中的对应位置；以及删除模块，配置用于响应于存在需要离开环形队列的队列元素，从队列头部开始删除对应数量的队列元素。

[0023] 本发明实施例的又一方面，还提供了一种计算机设备，包括：至少一个处理器；以及存储器，所述存储器存储有可在所述处理器上运行的计算机指令，所述指令由所述处理器执行时实现如上处理方法的步骤。

[0024] 本发明实施例的再一方面，还提供了一种计算机可读存储介质，计算机可读存储介质存储有被处理器执行时实现如上处理方法步骤的计算机程序。

[0025] 本发明具有以下有益技术效果：

[0026] 1、本发明实施例在环形队列中增加了轮次的定义，从而在无互斥锁的情况下实现了多CPU核生产者的入队和出队操作，充分发挥了加速集群中多个CPU核的性能；

[0027] 2、本发明实施例增加了全局原子变量，从而实现了队列吞吐率峰值不再受限于多CPU核的互斥锁和等待队列对性能的瓶颈影响；

[0028] 3、不存在额外的等待队列链表操作开销以及队列元素的拷贝开销，提高了加速集群中多个CPU核性能的稳定性；

[0029] 4、在不增加硬件的情况下，可以很好提高主机读写I/O任务在切分为分块后，将各个分块为单位分发到环形队列，提高环形队列的处理性能，以大幅度提高RAID卡处理I/O的能力，增强在RAID卡市场的竞争力。

附图说明

[0030] 为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的实施例。

[0031] 图1为本发明提供的RAID卡集群对队列的处理方法的实施例的示意图；

[0032] 图2为本发明提供的主机I/O按条带切分后再按分块切分框图；

[0033] 图3为本发明提供的环形队列入队和出队示意图；

[0034] 图4为本发明提供的两个CPU核并发入队流程示意图；

[0035] 图5为本发明提供的并发入队时队列状态示意图；

[0036] 图6为本发明提供的RAID卡集群对队列的处理系统的实施例的示意图；

[0037] 图7为本发明提供的RAID卡集群对队列的处理方法的计算机设备的实施例的硬件结构示意图；

[0038] 图8为本发明提供的RAID卡集群对队列的处理方法的计算机存储介质的实施例的示意图。

具体实施方式

[0039] 为使本发明的目的、技术方案和优点更加清楚明白，以下结合具体实施例，并参照附图，对本发明实施例进一步详细说明。

[0040] 需要说明的是，本发明实施例中所有使用“第一”和“第二”的表述均是为了区分两个相同名称非相同的实体或者非相同的参量，可见“第一”“第二”仅为了表述的方便，不应理解为对本发明实施例的限定，后续实施例对此不再一一说明。

[0041] 本发明实施例的第一个方面，提出了一种RAID卡集群对队列的处理方法的实施例。图1示出的是本发明提供的RAID卡集群对队列的处理方法的实施例的示意图。如图1所示，本发明实施例包括如下步骤：

[0042] S1、响应于存在需要加入环形队列的队列元素，读取环形队列的原始头部和原始全局原子变量，所述原始全局原子变量包括原始引用索引、原始队列元素索引和原始当前相位；

[0043] S2、根据所述原始头部和原始全局原子变量确定队列剩余空间，并根据所述队列剩余空间和需要加入环形队列的队列元素的数量的大小确定入队操作的队列元素个数；

[0044] S3、根据所述原始全局原子变量和所述入队操作的队列元素个数构造新全局原子变量，并根据所述原始全局原子变量和所述新全局原子变量做原子操作；

[0045] S4、响应于所述原子操作的返回值为所述原始全局原子变量，将需要加入环形队列的队列元素填充到环形队列中的对应位置；

[0046] S5、响应于存在需要离开环形队列的队列元素，从队列头部开始删除对应数量的队列元素。

[0047] RAID（Redundant Array of Independent Disks，独立磁盘冗余阵列）是由很多块独立的磁盘组合成一个容量巨大的磁盘组。RAID是一种把多块独立的硬盘（物理硬盘）按不同的方式组合起来形成一个硬盘组（逻辑硬盘），从而提供比单个硬盘更高的存储性能和提供数据备份技术。利用这项技术，将数据切割成许多区段，分别存放在各个磁盘上。环形队列：使用数组模拟环形队列对前面的数组模拟队列的优化，充分利用数组，将数组看做是一个环形的（通过取模的方式来实现即可）。

[0048] RAID卡中的RAID卡控制器是一颗芯片，由缓存、I/O处理器、磁盘控制器和磁盘连接器等一系列组件组成，从物理连接层面来讲，RAID卡就是实现将存储服务器连接的磁盘按照RAID级别组织成多个RAID阵列的功能板卡，具体来讲是将RAID卡挂载在PCIe总线上，这样可以将RAID卡看做存储服务器的外设，RAID卡是在软RAID存储技术基础上提出的硬RAID存储技术。

[0049] RAID卡在收到前台主机下发的I/O读写任务后，将I/O长度按照RAID阵列的条带stripe进行切分，然后将条带再按照各磁盘分块strip切分（如图2所示），将切分后的各个分块strip数据提交至环形队列，磁盘控制器从环形队列依次取走各个分块strip数据进行落盘操作，当一个环形队列的吞吐率较高，超过了一个CPU核的处理能力时，业界使用多个CPU核组成一个服务于同一个队列的加速集群，因此目前业界将单CPU核的RAID卡升级为多核RAID卡，由多个CPU核组成一个加速集群，其中每个CPU核都为一个加速单元。条带：又称为stripe；是阵列的不同分区上的位置相关的strip的集合，是组织不同分区上分块的单位。分块：又称为strip/chunk；将一个分区分成多个大小相等的、地址相邻的块（Block），这些块称为分块。分块通常被认为是条带的元素。虚拟磁盘以它为单位将虚拟磁盘的地址映射到成员磁盘的地址。

[0050] 响应于存在需要加入环形队列的队列元素，读取环形队列的原始头部和原始全局原子变量，所述原始全局原子变量包括原始引用索引、原始队列元素索引和原始当前相位。

[0051] 在一些实施方式中，所述处理方法还包括：每次写访问将引用索引加一，在每个当前轮次中将当前相位按照一和零交替变化。

[0052] 本发明实施例增加一个全局原子变量Tail_Req，该变量由环形队列的所有CPU核生产者共享。包含三部分，即引用索引（RC：Reference Counter），QE索引（QEI：QE index）和当前相位（PB：Phase bit）。其中RC表示Tail_Req变量的引用计数，每次对Tail_Req写操作时需要对RC加1，其中N为环形队列的队列深度大小（即环形队列能容纳的最大QE数）。QEI表示QE在环形缓冲区中的位置索引。PB表示当前CPU核生产者相位的值。定义Tail_Req变量宽度为64个比特位（即8个字节byte）。

[0053]

[0054] 假设一个CPU核存在需要加入环形队列的M个队列元素，读取Head（头部），记为Headold（原始头部）。读取Tail_Req，记为Tail_Reqold（原始全局原子变量），包含RCold（原始引用索引）和QEIold（原始队列元素索引）和PBold（原始当前相位）。

[0055] 根据所述原始头部和原始全局原子变量确定队列剩余空间，并根据所述队列剩余空间和需要加入环形队列的队列元素的数量的大小确定入队操作的队列元素个数。

[0056] 在一些实施方式中，所述根据所述原始头部和原始全局原子变量确定队列剩余空间包括：将所述原始全局原子变量中的原始队列元素索引与所述原始头部的差值减一得到中间结果；以及将所述中间结果除以环形队列能容纳的最大队列元素数得到的余数作为队列剩余空间。计算QEIold‑1‑Headold得到中间结果，并计算（QEIold‑1‑Headold）modN得到队列剩余空间，其中，N为环形队列能容纳的最大队列元素数。

[0057] 在一些实施方式中，所述根据所述队列剩余空间和需要加入环形队列的队列元素的数量的大小确定入队操作的队列元素个数包括：将所述队列剩余空间和需要加入环形队列的队列元素的数量之间的最小值作为入队操作的队列元素个数。取剩余空间和M之间的最小值作为入队操作的QE个数，记做EQN（Enqueue Number）。

[0058] 根据所述原始全局原子变量和所述入队操作的队列元素个数构造新全局原子变量，并根据所述原始全局原子变量和所述新全局原子变量做原子操作。

[0059] 在一些实施方式中，所述根据所述原始全局原子变量和所述入队操作的队列元素个数构造新全局原子变量包括：将所述原始全局原子变量的原始引用索引加一作为所述新全局原子变量的新引用索引；以及将所述原始全局原子变量的原始队列元素索引与所述入队操作的队列元素个数的和作为第二中间结果，并将所述第二中间结果除以环形队列能容纳的最大队列元素数得到的余数作为所述新全局原子变量的新队列元素索引。

[0060] 构造新全局原子变量Tail_Reqnew，其中，RCnew=（RCold+1），QEInew=（QEIold+EQN）modN，N为环形队列能容纳的最大队列元素数。Tail_Reqold和Tail_Reqnew是每个CPU核独有的变量，而Tail_Req是所有CPU核共享的变量。

[0061] 在一些实施方式中，所述处理方法还包括：响应于所述原子操作的返回值不为所述原始全局原子变量，重新检查队列剩余空间。

[0062] 做原子操作CAS（&Tail_Req，Tail_Reqold，Tail_Reqnew）。如果返回值为Tail_Reqold，则说明Tail_Reqnew已成功写入Tail_Req，进行后续步骤。如果返回值不等于Tail_Reqold，说明有其它的CPU核已经完成了CAS操作，抢占了以QEIold为起始index的一段空间，此时重新检查队列剩余空间，再次发起抢占。原子操作CAS（Compare And Swap，比较与交换）：通常指的是这样一种原子操作：针对一个变量，首先比较它的内存值和某个期望值是否相同，如果相同，就给它赋一个新值。

[0063] 响应于所述原子操作的返回值为所述原始全局原子变量，将需要加入环形队列的队列元素填充环形队列中的对应位置。

[0064] 在一些实施方式中，所述将需要加入环形队列的队列元素填充到环形队列中的对应位置包括：填充原始队列元素索引到新队列元素索引之间的队列元素。

[0065] 在一些实施方式中，所述填充原始队列元素索引到新队列元素索引之间的队列元素包括：将原始全局原子变量的原始当前相位设置为当前相位，并设置每个队列元素的序号逐个减小。

[0066] 在一些实施方式中，所述设置每个队列元素的序号逐个减小包括：将从入队操作的队列元素个数减一作为队列元素的序号的初始值，并设置出首个队列元素之外的每个队列元素的序号相比于前一个相邻队列元素的序号小一。

[0067] 在一些实施方式中，所述将需要加入环形队列的队列元素填充到环形队列中的对应位置包括：设置填充操作的最后一步为对原始队列元素索引对应的队列元素的当前相位的进行赋值。

[0068] 填充QEIold到QEInew之间的QE。Phase bit赋值为PBold（考虑轮次翻转），首个队列元素的SN值为EQN‑1，然后每个队列元素的序号相对于前一个队列元素的序号少1。特别的，QEIold对应QE的phase bit赋值需要放在所有QE填充动作的最后一步进行。

[0069] 响应于存在需要离开环形队列的队列元素，从队列头部开始删除对应数量的队列元素。

[0070] 在一些实施方式中，所述处理方法还包括：根据队列尾部、原始队列元素索引和新队列元素索引做第二原子操作以判断尾部寄存器是否更新成功。

[0071] 在一些实施方式中，所述根据队列尾部、原始队列元素索引和新队列元素索引做第二原子操作以判断尾部寄存器是否更新成功包括：响应于所述第二原子操作返回值为原始队列元素索引，则表明尾部寄存器更新成功，否则尾部寄存器更新失败。

[0072] 做原子操作CAS（&Tail，QEIold，QEInew）。如果返回值为QEIold，则说明Tail寄存器更新成功。

[0073] 在一些实施方式中，所述处理方法还包括：根据新队列元素索引后的第一个队列元素判断尾部寄存器是否更新成功。

[0074] 在一些实施方式中，所述根据新队列元素索引后的第一个队列元素判断尾部寄存器是否更新成功包括：响应于新队列元素索引后的第一个队列元素的队列元素索引不为零且所述第一个队列元素的当前相位等于原始当前相位，则表示尚未更新所述尾部寄存器。

[0075] 在一些实施方式中，所述根据新队列元素索引后的第一个队列元素判断尾部寄存器是否更新成功包括：响应于新队列元素索引后的第一个队列元素的队列元素索引为零且所述第一个队列元素的当前相位不等于原始当前相位，则表示尚未更新所述尾部寄存器。

[0076] 在一些实施方式中，所述处理方法还包括：响应于尚未更新所述尾部寄存器，设置所述原始队列元素索引等于新队列元素索引。

[0077] 在一些实施方式中，所述处理方法还包括：将新队列元素索引后的第一个队列元素的序号和原始队列元素索引值的和作为第三中间结果，将所述第三中间结果除以环形队列能容纳的最大队列元素数得到的余数作为新队列元素索引。

[0078] 读取QEInew之后的第一个QE，即index = QEInew的QE。如果index != 0 且该QE的phase bit等于PBold，或者index == 0且该QE的phase bit不等于PBold，则表示接下来一段的QE已经被另一个CPU核填充过。但是因为前序QE未填充完成，所以尚未更新Tail。此时更新QEIold= QEInew，QEInew= (QEIold+ SN)modN。

[0079] 对环形队列增加了轮次（Round）的定义。从QE0到QEN‑1的一次完整的入队称为一轮。生产者的CPU核和消费者CPU核需要各自维护一个“当前轮次”的变量current_phase。该变量按照每轮1‑>0‑>1‑>0的顺序交替变化。在QE中增加1bit的phase bit表示QE所属轮次。生产者在做QE入队时，需要把current_phase填入QE的phase bit，而消费者在做出队操作时，需要校验QE的phase bit是否是与curret_phase相同。对环形队列中的QE增加了序号的概念（SN：sequence number），用来表示QE在一次突发入队操作中的降序编号，如果一次突发入队M个QE，则第一个QE的SN为M‑1，最后一个QE的SN为0。如图3所示，初始状态时为空队列。生产者和消费者的current_phase均为1。第一次突发入队5个QE后，这5个QE的phase bit均为1，且SN按照QE的顺序由4到0递减。之后队列经过3个QE的出队，以及9个元素的突发入队。生产者的phase由1转换为0，突发入队的9个QE的SN填充为8到0，而此时消费者仍位于在上一轮的phase 1。

[0080] 下面通过一个具体的实施例对本发明步骤进行说明：

[0081] 图4为本发明提供的两个CPU核并发入队流程示意图，图5为本发明提供的并发入队时队列状态示意图，如图4‑图5所示，有两个CPU(CPU_0&CPU_1)，每个CPU各有两个QE需要加入环形队列。入队的流程为：

[0082] 1、初始状态时，队列为空，Head=Tail=0，Tail_Req=0。

[0083] 2、CPU_0和CPU_1同时使用CAS操作，对队列中QEI=[0，1]的空间发起抢占。参数为Tail_Reqold=（0，0），即RCold=0，QEIold=0；Tail_Reqnew=（1，2），即RCnew=1，QEInew=2。其中CPU_1抢占成功，CAS返回值与Tail_Reqold相等。而CPU_0的CAS操作返回值已经是CPU_0修改过的Tail_Req，表示抢占失败。

[0084] 3、CPU_1向QEI=[0，1]中填充QE。

[0085] 4、CPU_0在失败后立即更新自己的Tail_Reqold=（1，2），Tail_Reqnew=（2，4），再次发起CAS操作对队列中QEI=[2，3]的空间发起抢占。CAS操作返回值与Tail_Reqold相同，表示CPU_0抢占成功。

[0086] 5、CPU_0向QEI=[2，3]中填充QE。

[0087] 6、CPU_1完成QEI=[0，1]的QE填充后，环形队列被其他CPU核抢占。

[0088] 7、CPU_0完成QEI=[2，3]的填充后，以自己的Tail_Reqold和Tail_Reqnew的QEI值（2，4）为参数，对Tail发起CAS操作，尝试更新Tail。返回值为0，表示前序QE尚未完成填充，CPU_
0入队流程结束。

[0089] 8、CPU_1以自己的Tail_Reqold和Tail_Reqnew的QEI值（0，2）为参数，对Tail发起CAS操作。返回值0，表示Tail更新成功。接着搜索QEI=2的QE，发现phase bit已经更新为1。且SN=1，表示有两个待入队QE。于是以（2，4）为参数对Tail再次发起CAS操作。返回值为2，表示Tail更新成功。再次搜索QEI=4的QE，发现phase bit为0，表示后续没有待入队QE。CPU_1入队流程结束。

[0090] 本发明提出的加速集群对队列处理效率的方法不仅可以应用于硬RAID存储技术（RAID卡），同时也适用于软RAID存储技术。描述的方法和系统不仅可以应用在存储领域，在云计算和人工智能等领域同样可以作为参考借鉴。

[0091] 需要特别指出的是，上述RAID卡集群对队列的处理方法的各个实施例中的各个步骤均可以相互交叉、替换、增加、删减，因此，这些合理的排列组合变换之于出入环形队列的方法也应当属于本发明的保护范围，并且不应将本发明的保护范围局限在实施例之上。

[0092] 基于上述目的，本发明实施例的第二个方面，提出了一种RAID卡集群对队列的处理系统。如图6所示，系统200包括如下模块：设置模块，配置用于响应于存在需要加入环形队列的队列元素，读取环形队列的原始头部和原始全局原子变量，所述原始全局原子变量包括原始引用索引、原始队列元素索引和原始当前相位；确定模块，配置用于根据所述原始头部和原始全局原子变量确定队列剩余空间，并根据所述队列剩余空间和需要加入环形队列的队列元素的数量的大小确定入队操作的队列元素个数；构造模块，配置用于根据所述原始全局原子变量和所述入队操作的队列元素个数构造新全局原子变量，并根据所述原始全局原子变量和所述新全局原子变量做原子操作；填充模块，配置用于响应于所述原子操作的返回值为所述原始全局原子变量，将需要加入环形队列的队列元素填充到环形队列中的对应位置；以及删除模块，配置用于响应于存在需要离开环形队列的队列元素，从队列头部开始删除对应数量的队列元素。

[0093] 在一些实施方式中，所述确定模块配置用于：将所述原始全局原子变量中的原始队列元素索引与所述原始头部的差值减一得到中间结果；以及将所述中间结果除以环形队列能容纳的最大队列元素数得到的余数作为队列剩余空间。

[0094] 在一些实施方式中，所述确定模块配置用于：将所述队列剩余空间和需要加入环形队列的队列元素的数量之间的最小值作为入队操作的队列元素个数。

[0095] 在一些实施方式中，所述构造模块配置用于：将所述原始全局原子变量的原始引用索引加一作为所述新全局原子变量的新引用索引；以及将所述原始全局原子变量的原始队列元素索引与所述入队操作的队列元素个数的和作为第二中间结果，并将所述第二中间结果除以环形队列能容纳的最大队列元素数得到的余数作为所述新全局原子变量的新队列元素索引。

[0096] 在一些实施方式中，所述系统还包括返回模块，配置用于：响应于所述原子操作的返回值不为所述原始全局原子变量，重新检查队列剩余空间。

[0097] 在一些实施方式中，所述填充模块配置用于：填充原始队列元素索引到新队列元素索引之间的队列元素。

[0098] 在一些实施方式中，所述填充模块配置用于：将原始全局原子变量的原始当前相位设置为当前相位，并设置每个队列元素的序号逐个减小。

[0099] 在一些实施方式中，所述填充模块配置用于：将从入队操作的队列元素个数减一作为队列元素的序号的初始值，并设置出首个队列元素之外的每个队列元素的序号相比于前一个相邻队列元素的序号小一。

[0100] 在一些实施方式中，所述填充模块配置用于：设置填充操作的最后一步为对原始队列元素索引对应的队列元素的当前相位的进行赋值。

[0101] 在一些实施方式中，所述系统还包括判断模块，配置用于：根据队列尾部、原始队列元素索引和新队列元素索引做第二原子操作以判断尾部寄存器是否更新成功。

[0102] 在一些实施方式中，所述判断模块配置用于：响应于所述第二原子操作返回值为原始队列元素索引，则表明尾部寄存器更新成功，否则尾部寄存器更新失败。

[0103] 在一些实施方式中，所述系统还包括第二判断模块，配置用于：根据新队列元素索引后的第一个队列元素判断尾部寄存器是否更新成功。

[0104] 在一些实施方式中，所述第二判断模块配置用于：响应于新队列元素索引后的第一个队列元素的队列元素索引不为零且所述第一个队列元素的当前相位等于原始当前相位，则表示尚未更新所述尾部寄存器。

[0105] 在一些实施方式中，所述第二判断模块配置用于：响应于新队列元素索引后的第一个队列元素的队列元素索引为零且所述第一个队列元素的当前相位不等于原始当前相位，则表示尚未更新所述尾部寄存器。

[0106] 在一些实施方式中，所述系统还包括索引模块，配置用于：响应于尚未更新所述尾部寄存器，设置所述原始队列元素索引等于新队列元素索引。

[0107] 在一些实施方式中，所述系统还包括第二索引模块，配置用于：将新队列元素索引后的第一个队列元素的序号和原始队列元素索引值的和作为第三中间结果，将所述第三中间结果除以环形队列能容纳的最大队列元素数得到的余数作为新队列元素索引。

[0108] 在一些实施方式中，所述系统还包括更新模块，配置用于：每次写访问将引用索引加一，在每个当前轮次中将当前相位按照一和零交替变化。

[0109] 基于上述目的，本发明实施例的第三个方面，提出了一种计算机设备，包括：至少一个处理器；以及存储器，存储器存储有可在处理器上运行的计算机指令，指令由处理器执行以实现如下步骤：S1、响应于存在需要加入环形队列的队列元素，读取环形队列的原始头部和原始全局原子变量，所述原始全局原子变量包括原始引用索引、原始队列元素索引和原始当前相位；S2、根据所述原始头部和原始全局原子变量确定队列剩余空间，并根据所述队列剩余空间和需要加入环形队列的队列元素的数量的大小确定入队操作的队列元素个数；S3、根据所述原始全局原子变量和所述入队操作的队列元素个数构造新全局原子变量，并根据所述原始全局原子变量和所述新全局原子变量做原子操作；S4、响应于所述原子操作的返回值为所述原始全局原子变量，将需要加入环形队列的队列元素填充到环形队列中的对应位置；以及S5、响应于存在需要离开环形队列的队列元素，从队列头部开始删除对应数量的队列元素。

[0110] 在一些实施方式中，所述根据所述原始头部和原始全局原子变量确定队列剩余空间包括：将所述原始全局原子变量中的原始队列元素索引与所述原始头部的差值减一得到中间结果；以及将所述中间结果除以环形队列能容纳的最大队列元素数得到的余数作为队列剩余空间。

[0111] 在一些实施方式中，所述根据所述队列剩余空间和需要加入环形队列的队列元素的数量的大小确定入队操作的队列元素个数包括：将所述队列剩余空间和需要加入环形队列的队列元素的数量之间的最小值作为入队操作的队列元素个数。

[0112] 在一些实施方式中，所述根据所述原始全局原子变量和所述入队操作的队列元素个数构造新全局原子变量包括：将所述原始全局原子变量的原始引用索引加一作为所述新全局原子变量的新引用索引；以及将所述原始全局原子变量的原始队列元素索引与所述入队操作的队列元素个数的和作为第二中间结果，并将所述第二中间结果除以环形队列能容纳的最大队列元素数得到的余数作为所述新全局原子变量的新队列元素索引。

[0113] 在一些实施方式中，所述步骤还包括：响应于所述原子操作的返回值不为所述原始全局原子变量，重新检查队列剩余空间。

[0114] 在一些实施方式中，所述将需要加入环形队列的队列元素填充到环形队列中的对应位置包括：填充原始队列元素索引到新队列元素索引之间的队列元素。

[0115] 在一些实施方式中，所述填充原始队列元素索引到新队列元素索引之间的队列元素包括：将原始全局原子变量的原始当前相位设置为当前相位，并设置每个队列元素的序号逐个减小。

[0116] 在一些实施方式中，所述设置每个队列元素的序号逐个减小包括：将从入队操作的队列元素个数减一作为队列元素的序号的初始值，并设置出首个队列元素之外的每个队列元素的序号相比于前一个相邻队列元素的序号小一。

[0117] 在一些实施方式中，所述将需要加入环形队列的队列元素填充到环形队列中的对应位置包括：设置填充操作的最后一步为对原始队列元素索引对应的队列元素的当前相位的进行赋值。

[0118] 在一些实施方式中，所述步骤还包括：根据队列尾部、原始队列元素索引和新队列元素索引做第二原子操作以判断尾部寄存器是否更新成功。

[0119] 在一些实施方式中，所述根据队列尾部、原始队列元素索引和新队列元素索引做第二原子操作以判断尾部寄存器是否更新成功包括：响应于所述第二原子操作返回值为原始队列元素索引，则表明尾部寄存器更新成功，否则尾部寄存器更新失败。

[0120] 在一些实施方式中，所述步骤还包括：根据新队列元素索引后的第一个队列元素判断尾部寄存器是否更新成功。

[0121] 在一些实施方式中，所述根据新队列元素索引后的第一个队列元素判断尾部寄存器是否更新成功包括：响应于新队列元素索引后的第一个队列元素的队列元素索引不为零且所述第一个队列元素的当前相位等于原始当前相位，则表示尚未更新所述尾部寄存器。

[0122] 在一些实施方式中，所述根据新队列元素索引后的第一个队列元素判断尾部寄存器是否更新成功包括：响应于新队列元素索引后的第一个队列元素的队列元素索引为零且所述第一个队列元素的当前相位不等于原始当前相位，则表示尚未更新所述尾部寄存器。

[0123] 在一些实施方式中，所述步骤还包括：响应于尚未更新所述尾部寄存器，设置所述原始队列元素索引等于新队列元素索引。

[0124] 在一些实施方式中，所述步骤还包括：将新队列元素索引后的第一个队列元素的序号和原始队列元素索引值的和作为第三中间结果，将所述第三中间结果除以环形队列能容纳的最大队列元素数得到的余数作为新队列元素索引。

[0125] 在一些实施方式中，所述设置包括引用索引、队列元素索引和当前相位的全局原子变量包括：每次写访问增加一次引用索引，当前相位在每个当前轮次中都按照一和零交替变化。

[0126] 如图7所示，为本发明提供的上述RAID卡集群对队列的处理方法的计算机设备的一个实施例的硬件结构示意图。

[0127] 以如图7所示的装置为例，在该装置中包括一个处理器301以及一个存储器302。

[0128] 处理器301和存储器302可以通过总线或者其他方式连接，图7中以通过总线连接为例。

[0129] 存储器302作为一种非易失性计算机可读存储介质，可用于存储非易失性软件程序、非易失性计算机可执行程序以及模块，如本申请实施例中的出入环形队列的方法对应的程序指令/模块。处理器301通过运行存储在存储器302中的非易失性软件程序、指令以及模块，从而执行服务器的各种功能应用以及数据处理，即实现RAID卡集群对队列的处理方法。

[0130] 存储器302可以包括存储程序区和存储数据区，其中，存储程序区可存储操作系统、至少一个功能所需要的应用程序；存储数据区可存储根据RAID卡集群对队列的处理方法的使用所创建的数据等。此外，存储器302可以包括高速随机存取存储器，还可以包括非易失性存储器，例如至少一个磁盘存储器件、闪存器件、或其他非易失性固态存储器件。在一些实施例中，存储器302可选包括相对于处理器301远程设置的存储器，这些远程存储器可以通过网络连接至本地模块。上述网络的实例包括但不限于互联网、企业内部网、局域网、移动通信网及其组合。

[0131] 一个或者多个RAID卡集群对队列的处理方法对应的计算机指令303存储在存储器302中，当被处理器301执行时，执行上述任意方法实施例中的RAID卡集群对队列的处理方法。

[0132] 执行上述RAID卡集群对队列的处理方法的计算机设备的任何一个实施例，可以达到与之对应的前述任意方法实施例相同或者相类似的效果。

[0133] 本发明还提供了一种计算机可读存储介质，计算机可读存储介质存储有被处理器执行时执行RAID卡集群对队列的处理方法的计算机程序。

[0134] 如图8所示，为本发明提供的上述RAID卡集群对队列的处理方法的计算机存储介质的一个实施例的示意图。以如图8所示的计算机存储介质为例，计算机可读存储介质401存储有被处理器执行时执行如上方法的计算机程序402。

[0135] 最后需要说明的是，本领域普通技术人员可以理解实现上述实施例方法中的全部或部分流程，可以通过计算机程序来指令相关硬件来完成，RAID卡集群对队列的处理方法的程序可存储于一计算机可读取存储介质中，该程序在执行时，可包括如上述各方法的实施例的流程。其中，程序的存储介质可为磁碟、光盘、只读存储记忆体（ROM）或随机存储记忆体（RAM）等。上述计算机程序的实施例，可以达到与之对应的前述任意方法实施例相同或者相类似的效果。

[0136] 以上是本发明公开的示例性实施例，但是应当注意，在不背离权利要求限定的本发明实施例公开的范围的前提下，可以进行多种改变和修改。根据这里描述的公开实施例的方法权利要求的功能、步骤和/或动作不需以任何特定顺序执行。此外，尽管本发明实施例公开的元素可以以个体形式描述或要求，但除非明确限制为单数，也可以理解为多个。

[0137] 应当理解的是，在本文中使用的，除非上下文清楚地支持例外情况，单数形式“一个”旨在也包括复数形式。还应当理解的是，在本文中使用的“和/或”是指包括一个或者一个以上相关联地列出的项目的任意和所有可能组合。

[0138] 上述本发明实施例公开实施例序号仅仅为了描述，不代表实施例的优劣。

[0139] 本领域普通技术人员可以理解实现上述实施例的全部或部分步骤可以通过硬件来完成，也可以通过程序来指令相关的硬件完成，程序可以存储于一种计算机可读存储介质中，上述提到的存储介质可以是只读存储器，磁盘或光盘等。

[0140] 所属领域的普通技术人员应当理解：以上任何实施例的讨论仅为示例性的，并非旨在暗示本发明实施例公开的范围（包括权利要求）被限于这些例子；在本发明实施例的思路下，以上实施例或者不同实施例中的技术特征之间也可以进行组合，并存在如上的本发明实施例的不同方面的许多其它变化，为了简明它们没有在细节中提供。因此，凡在本发明实施例的精神和原则之内，所做的任何省略、修改、等同替换、改进等，均应包含在本发明实施例的保护范围之内。