队列分配方法及装置

本申请涉及网络数据处理领域，具体涉及一种队列分配方法及装置。

在云计算虚拟化场景中，Virtio是一个通用的半虚拟化I/O框架，Hypervisor通过它模拟出一系列的虚拟化设备。其中，云计算中，为了让多个虚拟机的Guest OS可以独立运行于同一个物理机的Host OS上，通常需要在物理机的Host OS上增加一个虚拟化层来实现，该虚拟化层称为Hypervisor。

Virtio框架主要包含三个部分：前端驱动(front-end)、后端设备(back-end)以及virtqueue队列。Virtio使用virtqueue来实现I/O机制，每个virtqueue就是一个队列。

随着云计算虚拟化技术的演进，当前出现了一些硬件卸载Virtio back-end的智能网卡。这些智能网卡通常采用FPGA(Field Programmable Gate Array，现场可编程门阵列)或者ASIC(Application Specific Integrated Circuit，专用集成电路)芯片实现，通过SR-IOV(Single Root I/O Virtualization，单根I/O虚拟化)在物理机侧虚拟出多个网卡设备，并在芯片内部实现一定数量的virtqueue队列承载暴露给物理机侧的网卡设备。

如果一个智能网卡可以在物理机侧虚拟出M个网卡设备，在智能网卡芯片内部实现N个队列，其中，M和N均为正整数，M和N均大于等于2，且N大于等于M，那么针对N个队列如何分配到M个网卡设备上去的问题，目前的做法通常是按需分配，用户需要在物理机侧虚拟出多少个网卡设备，就分配相应数量的队列资源给虚拟网卡设备。但是，为了便于硬件实现，队列需要连续分配，即分配的队列在芯片内部是连续的。故在虚拟网卡设备经过多次创建和删除之后，容易造成多个已释放的小队列空间因不连续而无法分配给大队列空间申请请求的问题，进而多个不连续的已释放的小队列空间在队列空间中形成了“空洞”，导致队列空间的利用率低。

本申请提供一种队列分配方法及装置，可以减少在队列空间中形成“空洞”，从而提高队列空间的利用率。

第一方面，本申请提供一种队列分配方法，包括：

构建一个数据结构单元，数据结构单元被配置为存储多个不同的队列数目S，队列数目S是虚拟设备要申请的队列数量，及对应每个队列数目S，数据结构单元还被配置为存储至少一组连续S个队列的地址，其中，S是正整数；

接收虚拟设备的队列申请请求，若队列申请请求要申请的队列数量与存储在数据结构单元中的任一队列数目S匹配，则将与匹配的队列数目S对应的存储在数据结构单元的空闲的一组连续S个队列的地址分配给队列申请请求，并且将分配给队列申请请求的一组连续S个队列的地址标记为被占用；

接收虚拟设备的队列释放请求，将队列释放请求要释放的一组连续S个队列的地址标记为空闲。

第二方面，本申请提供一种队列分配装置，包括：

数据结构构建模块，用于构建一个数据结构单元，数据结构单元被配置为存储多个不同的队列数目S，队列数目S是虚拟设备要申请的队列数量，及对应每个队列数目S，数据结构单元还被配置为存储至少一组连续S个队列的地址，其中，S是正整数；

队列申请请求模块，用于接收虚拟设备的队列申请请求，若队列申请请求要申请的队列数量与存储在数据结构单元中的任一队列数目S匹配，则将与匹配的队列数目S对应的存储在数据结构单元的空闲的一组连续S个队列的地址分配给队列申请请求，并且将分配给队列申请请求的一组连续S个队列的地址标记为被占用；

队列释放请求模块，用于接收虚拟设备的队列释放请求，将队列释放请求要释放的一组连续S个队列的地址标记为空闲。

进一步地，数据结构单元包括一个长度为L的数组，数组被配置为存储多个不同的队列数目S，第i个数组元素存储虚拟设备要申请的队列数目S＝S[i]，其中，L、i和S[i]是正整数，i大于等于1，且i小于等于L。

进一步地，数组被配置为存储根据第一规则设置的多个队列数目S，其中，第一规则是，第i个数组元素存储的队列数目S[i]是虚拟设备要申请的最小队列数目的i次方，且第L个数组元素存储的队列数据S[L]是虚拟设备要申请的最大队列数目。

进一步地，数据结构单元还包括L个双向链表，第i个双向链表包括T[i]个结点，并且第i个双向链表以数组中的第i个数组元素作为头结点，除头结点之外的每个结点存储连续S[i]个队列的地址，其中，T[i]是正整数。

进一步地，第i个双向链表包括根据第二规则设置的T[i]个结点，其中，第二规则是，若第i个双向链表被配置的队列数量是S[i]与T[i]-1的乘积，则L个双向链表被配置的队列总数量等于芯片内部配置的队列数量，其中，T[i]-1与S[i]的乘积等于S[L]，若S[i]大于S[i-1]，则T[i]小于T[i-1]；若S[i]小于S[i-1]，则T[i]大于T[i-1]。

进一步地，在队列申请请求要申请的队列数量与存储在数据结构单元中的一队列数目S匹配时，所述队列申请请求模块还用于，

若第i个双向链表中每个结点存储的一组连续S[i]个队列的地址均标记为被占用，而第j个双向链表的第k个结点存储有空闲的一组连续S[j]个队列的地址，其中，S[i]小于S[j]，j和k为正整数，j小于等于L，k大于1，且k小于等于T[i]，

则将第j个双向链表的第k个结点连接到第i个双向链表的表尾，将第k个结点存储的一组连续S[j]个队列的地址拆分成倍数组连续S[i]个队列的地址，以及将倍数组连续S[i]个队列的地址中的一组地址分配给队列申请请求，并且标记为被占用。

进一步地，在接收虚拟设备的队列释放请求，以及将队列释放请求要释放的一组连续S个队列的地址标记为空闲时，所述队列释放请求模块还用于，

若队列释放请求要释放的一组连续S[i]个队列的地址是由第j个双向链表的第k个结点的一组连续S[j]个队列的地址拆分得到的倍数组连续S[i]个队列的地址中的一组地址，则在倍数组连续S[i]个队列的地址中的其它组地址均是空闲时，将连接到第i个双向链表的表尾的第j个双向链表的第k个结点恢复至第j个双向链表第k个结点的位置。

进一步地，在队列申请请求要申请的队列数量与存储在数据结构单元中的一队列数目S匹配时，所述队列申请请求模块还用于，

若第i个双向链表中每个结点存储的一组连续S[i]个队列的地址均标记为被占用，而第j个双向链表的第k至个结点分别存储有空闲的一组连续S[j]个队列的地址，其中，S[i]大于S[j]，j和k为正整数，j小于等于L，k大于1，且k小于等于T[i]，

则将第j个双向链表的第k至个结点连接至第i个双向链表的表尾，将第k至个结点分别存储的一组连续S[j]个队列的地址合并成一组连续S[i]个队列的地址，以及将合并成一组连续S[i]个队列的地址分配给队列请求，并且标记为被占用。

进一步地，在接收虚拟设备的队列释放请求，以及将队列释放请求要释放的一组连续S个队列的地址标记为空闲时，所述队列释放请求模块还用于，

若队列释放请求要释放的一组连续S[i]个队列的地址是由第j个双向链表的第k至个结点分别存储的一组连续S[j]个队列的地址合并得到的，则将连接到第i个双向链表的表尾的第j个双向链表的第k至个结点恢复连接至第j个双向链表第k至个结点的位置。

第三方面，本申请提供一种电子设备，包括存储器、处理器及存储在存储器上并在处理器上运行的计算机程序，所述处理器执行所述程序时实现所述第一方面提供的队列分配方法的步骤。

第四方面，本申请提供一种计算机可读存储介质，其上存储有计算机程序，该计算机程序被处理器执行时实现所述第一方面提供的队列分配方法的步骤。

第五方面，本申请提供一种计算机程序产品，包括计算机程序或指令，该计算机程序或指令被处理器执行时实现所述第一方面提供的队列分配方法的步骤。

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

图1为本申请第一实施例提供的队列分配方法的流程示意图；

图2为本申请第一实施例提供的队列分配方法中构建数据结构单元的示意图；

图3为本申请第一实施例提供的队列分配方法中将大队列空间拆分成小队列空间的示意图；

图4为本申请第一实施例提供的队列分配方法中将小队列空间组合成大队列空间的示意图；

图5为本申请第二实施例提供的队列分配装置的模块示意图；

为使本申请实施例的目的、技术方案和优点更加清楚，下面将结合本申请实施例中的附图，对本申请实施例中的技术方案进行清楚、完整的描述，显然，所描述的实施例是本申请一部分实施例，而不是全部的实施例。基于本申请中的实施例，本领域普通技术人员在没有作出创造性劳动前提下所获得的所有其他实施例，都属于本申请保护的范围。

基于目前的队列分配方式，虚拟网卡设备在经过多次创建和删除之后，容易造成多个已释放的小队列空间因不连续而无法分配给大队列空间申请请求的问题，进而所述多个不连续的已释放的小队列空间在队列空间中形成了“空洞”，导致队列空间的利用率低。

可以理解的是，本申请所述小队列空间是指，相对于大队列空间，小队列空间包括的队列数量小于大队列空间包括的队列数量。

本申请提供一种队列分配方法，可以改善目前的队列分配方式存在的问题。本申请所述队列分配方法包括：构建一个数据结构单元，数据结构单元被配置为存储多个不同的队列数目S，队列数目S是虚拟设备要申请的队列数量，及对应每个队列数目S，数据结构单元还被配置为存储至少一组连续S个队列的地址，其中，S是正整数；接收虚拟设备的队列申请请求，若队列申请请求要申请的队列数量与存储在数据结构单元中的任一队列数目S匹配，则将与匹配的队列数目S对应的存储在数据结构单元的空闲的一组连续S个队列的地址分配给队列申请请求，并且将分配给队列申请请求的一组连续S个队列的地址标记为被占用；接收虚拟设备的队列释放请求，将队列释放请求要释放的一组连续S个队列的地址标记为空闲。

本申请提供的队列分配方法，通过将待分配的队列分成多种大小与虚拟设备要申请的队列数目对应的队列空间，相同大小的队列空间构成一排，从而构成多排不同大小的队列空间。分配队列空间时，可以优先在排内进行分配，当小队列空间不够分配时，可以拆分大队列空间，当大队列空间不够分配时，可以组合小队列空间，从而可以减少在队列空间中形成空洞，提高队列空间的利用率。

为了详细阐述本申请，本申请在第一实施例中，提供一种队列分配方法。请参见图1，图1是本申请第一实施例提供的队列分配方法的流程示意图，所述队列分配方法可以包括如下步骤：

步骤S10，构建一个数据结构单元，数据结构单元被配置为存储多个不同的队列数目S，队列数目S是虚拟设备要申请的队列数量，及对应每个队列数目S，数据结构单元还被配置为存储至少一组连续S个队列的地址。

本申请所述队列分配方法，在芯片上电运行时，芯片上的系统会构建一个数据结构单元。数据结构单元被配置为存储多个不同的队列数目S，其中，队列数目S是虚拟设备要申请的队列数量，S是正整数。以及，对应每个队列数目S，数据结构单元还被配置为存储至少一组连续S个队列的地址。

可以理解的是，本申请所述芯片可以是数据处理芯片，例如DPU。而芯片上的系统可以是片上系统，例如，SOC系统等。

在第一实施例的变更实施例中，数据结构单元可以包括一个长度为L的数组，其中，L是正整数。数组被配置为存储多个不同的队列数目S，数组的第i个数组元素存储虚拟设备要申请的队列数目S＝S[i]，其中，i、S[i]均是正整数，i大于等于1，且i小于等于L。通过数组来存储虚拟设备要申请的队列数目，可以将虚拟设备所有可能要申请的队列数目进行分类管理，进而可以根据虚拟设备所有可能要申请的队列数目，将待分配的队列分成多种大小与虚拟设备要申请的队列数目对应的队列空间，相同大小的队列空间构成一排，从而构成多排不同大小的队列空间。

可以理解的是，虚拟设备可以是物理机虚拟出的虚拟网卡设备，也可以是物理机虚拟出的虚拟显卡设备、虚拟声卡设备等其他虚拟设备。其中，物理机可以是提供云计算服务的服务器。

在本申请第一实施例或第一实施例的变更实施例中，数组被配置为存储根据第一规则设置的多个队列数目S，其中，第一规则是本申请队列分配方法在构建数据结构单元之前预设的规则。具体地，第一规则可以是：第i个数组元素存储的队列数目S[i]是虚拟设备要申请的最小队列数目的i次方，且第L个数组元素存储的队列数据S[L]是虚拟设备要申请的最大队列数目。通常，虚拟设备申请的队列数目是2的幂数。

需要说明的是，本申请第一规则还可以是其他设置多个队列数目S的类似规则，本申请并不以第一实施例或第一实施例的变更实施例中提供的第一规则为限制，其他与第一实施例或第一实施例的变更实施例中提供的第一规则类似的规则均在本申请的保护范围之内。

在第一实施例的变更实施例中，数据结构单元还可以包括L个双向链表。L个双向链表中的第i个双向链表包括T[i]个结点。T[i]是正整数，T[i]代表第i个双向链表所包括的结点数量。第i个双向链表以数组中的第i个数组元素作为头结点，并且，除头结点之外的每个结点存储连续S[i]个队列的地址。

可以理解的是，队列的地址是指队列在物理机的存储空间中的物理地址，连续S[i]个队列的地址是指S[i]个队列的地址是连续的。

在本申请第一实施例或第一实施例的变更实施例中，第i个双向链表包括根据第二规则设置的T[i]个结点，其中，第二规则是本申请队列分配方法在构建数据结构单元之前预设的规则。具体地，第二规则可以是：若第i个双向链表被配置的队列数量是S[i]与T[i]-1的乘积，则L个双向链表被配置的队列总数量等于芯片内部的队列数量，其中，T[i]-1与S[i]的乘积等于S[L]，若S[i]大于S[i-1]，则T[i]小于T[i-1]；若S[i]小于S[i-1]，则T[i]大于T[i-1]。

需要说明的是，本申请第二规则还可以是其他设置第i个双向链表的T[i]个结点的类似规则，本申请并不以第一实施例或第一实施例的变更实施例中提供的第二规则为限制，其他与第一实施例或第一实施例的变更实施例中提供的第二规则类似的规则均在本申请的保护范围之内。

为了易于理解本申请第一实施例或第一实施例的变更实施例中提供的队列分配方法，请参见图2，本申请结合图2举例说明数据结构单元的构建过程。

假设芯片内部配置24个队列，即芯片内部的可供分配的队列数量是24，虚拟设备申请的最小队列数目是2，虚拟设备申请的最大队列数目是8。

那么，本申请队列分配方法在构建数据结构单元之前可以将第一规则设置为：

第1个数组元素201存储的队列数目S[1]是虚拟设备要申请的最小队列数目2的1次方，即第1个数组元素201存储的队列数目S＝2。

第2个数组元素202存储的队列数目S[2]是虚拟设备要申请的最小队列数目2的2次方，即第2个数组元素202存储的队列数目S＝4。

第3个数组元素203存储的队列数目S[3]是虚拟设备要申请的最小队列数目2的3次方，即第3个数组元素203存储的队列数目S＝8。

也就是说，数组的长度L＝3。相应地，可以将第二规则设置为：

以第1个数组元素201作为头结点，第1个双向链表211除头结点外还可配置4个结点：Q0-1、Q2-3、Q4-5、Q6-7，其中，Q0-1结点代表包括Q0和Q1两个队列，Q2-3结点代表包括Q2和Q3两个队列，Q4-5结点代表包括Q4和Q5两个队列，Q6-7结点代表包括Q6和Q7两个队列。第1个双向链表211被配置的队列数量是S[1]与T[1]-1的乘积，即第1个双向链表211被配置的队列数量是2与4的乘积。

以第2个数组元素202作为头结点，第2个双向链表212除头结点外还可配置2个结点：Q8-11、Q12-15，其中，Q8-11结点代表包括Q8、Q9、Q10及Q1四个队列，Q12-15结点代表包括Q12、Q13、Q14及Q15四个队列。第2个双向链表212被配置的队列数量是S[2]与T[2]-1的乘积，即第2个双向链表212被配置的队列数量是4与2的乘积。

以第3个数组元素203作为头结点，第3个双向链表213除头结点外还可配置1个结点Q16-23，其中，Q16-23结点代表包括Q16、Q17、Q18、Q19、Q20、Q21、Q22及Q23八个队列。第3个双向链表213被配置的队列数量是S[3]与T[3]-1的乘积，即第3个双向链表213被配置的队列数量是8与1的乘积。

请再次参见图1，在第一实施例中，本申请队列分配方法还包括如下步骤：

步骤S20，接收虚拟设备的队列申请请求，若队列申请请求要申请的队列数量与存储在数据结构单元中的任一队列数目S匹配，则将与匹配的队列数目S对应的存储在数据结构单元的空闲的一组连续S个队列的地址分配给队列申请请求，并且将分配给队列申请请求的一组连续S个队列的地址标记为被占用。

具体地，当虚拟设备被创建时，芯片的系统会收到虚拟设备的队列申请请求。芯片的系统以遍历的方式，逐一将存储在数据结构单元中的队列数目S与虚拟设备要申请的队列数量进行匹配，以判断虚拟设备要申请的队列数量是否存在于数据结构单元中。若虚拟设备的队列申请请求要申请的队列数量与存储在数据结构单元中的一队列数目S匹配，即虚拟设备要申请的队列数量存在于数据结构单元中，则将与匹配的队列数目S对应的存储在数据结构单元的空闲的一组连续S个队列的地址分配给队列申请请求，并且将分配给队列申请请求的一组连续S个队列的地址标记为被占用。若虚拟设备的队列申请请求要申请的队列数量与存储在数据结构单元中的任一队列数目S都不匹配，即虚拟设备要申请的队列数量不存在于数据结构单元中，则芯片的系统反馈申请失败。

在第一实施例的变更实施例中，在队列申请请求要申请的队列数量与存储在数据结构单元中的一队列数目S匹配时，本申请队列分配方法还包括，

若第i个双向链表中除头结点外的每个结点存储的一组连续S[i]个队列的地址均标记为被占用，而第j个双向链表的第k个结点存储有空闲的一组连续S[j]个队列的地址，则将第j个双向链表的第k个结点连接到第i个双向链表的表尾，将第k个结点存储的一组连续S[j]个队列的地址拆分成倍数组连续S[i]个队列的地址，以及将倍数组连续S[i]个队列的地址中的一组地址分配给队列申请请求，并且将分配给队列申请请求的一组地址标记为被占用。其中，S[i]小于S[j]，j和k为正整数，j小于等于L，k大于1，且k小于等于T[i]。

为便于理解，结合图2和图3举例说明将大队列空间拆分成小队列空间的过程。

具体地，若第2个双向链表212中除头结点外的每个结点存储的一组连续S[2]＝4个队列的地址均标记为被占用，而第3个双向链表213的第1个结点(Q16-23)存储有空闲的一组连续S[3]＝8个队列的地址，则将第3个双向链表213的第1个结点连接到第2个双向链表212的表尾，将第1个结点存储的一组连续S[3]＝8个队列的地址拆分成二组连续S[2]＝4个队列的地址，以及将二组连续S[2]＝4个队列的地址中的一组地址分配给队列申请请求，并且将分配给队列申请请求的一组地址标记为占用。当小队列空间不够分配时，通过拆分大队列空间可以减少在队列空间中形成空洞，提高队列空间的利用率。

在第一实施例的变更实施例中，在队列申请请求要申请的队列数量与存储在数据结构单元中的一队列数目S匹配时，本申请队列分配方法还包括，

若第i个双向链表中除头结点外的每个结点存储的一组连续S[i]个队列的地址均标记为被占用，而第j个双向链表的第k至个结点分别存储有空闲的一组连续S[j]个队列的地址，其中，S[i]大于S[j]，j和k为正整数，j小于等于L，k大于1，且k小于等于T[i]，

则将第j个双向链表的第k至个结点连接至第i个双向链表的表尾，将第k至个结点分别存储的一组连续S[j]个队列的地址合并成一组连续S[i]个队列的地址，以及将合并成一组连续S[i]个队列的地址分配给队列请求，并且将分配给队列请求的一组连续S[i]个队列的地址标记为被占用。

为便于理解，结合图2和图4举例说明将小队列空间组合成大队列空间的过程。

具体地，若第2个双向链表212中除头结点外的每个结点存储的一组连续S[2]＝4个队列的地址均标记为被占用，而第1个双向链表211除头结点外的第3个结点和第4个结点分别存储有空闲的一组连续S[1]＝2个队列的地址，则将第1个双向链表211的第3个结点和第4个结点整体连接至第2个双向链表212的表尾，将第3个结点和第4个结点分别存储的一组连续S[1]＝2个队列的地址合并成一组连续S[2]＝4个队列的地址，以及将合并成一组连续S[2]＝4个队列的地址分配给队列请求，并且将分配给队列请求的一组连续S[2]＝4个队列的地址标记为被占用。

请再次参见图1，在第一实施例中，本申请队列分配方法还包括如下步骤：

步骤S30，接收虚拟设备的队列释放请求，将队列释放请求要释放的一组连续S个队列的地址标记为空闲。

具体地，当虚拟设备被删除时，芯片的系统会收到虚拟设备的队列释放请求。芯片的系统将队列释放请求要释放的一组连续S个队列的地址标记为空闲。

在第一实施例的变更实施例中，本申请队列分配方法，在接收虚拟设备的队列释放请求时，将队列释放请求要释放的一组连续S个队列的地址标记为空闲的步骤之后，还包括：

若队列释放请求要释放的一组连续S[i]个队列的地址是由第j个双向链表的第k个结点的一组连续S[j]个队列的地址拆分得到的倍数组连续S[i]个队列的地址中的一组地址，则在倍数组连续S[i]个队列的地址均是空闲时，将连接到第i个双向链表的表尾的第j个双向链表的第k个结点恢复至第j个双向链表第k个结点的位置。

为便于理解，结合图2和图3举例说明大队列空间拆分成小队列空间后的队列释放过程。

具体地，若队列释放请求要释放的一组连续S[2]＝4个队列的地址是由第3个双向链表213除头结点外的第1个结点的一组连续S[3]＝8个队列的地址拆分得到的二组连续S[2]＝4个队列的地址中的一组地址，则在二组连续S[2]＝4个队列的地址中的另一组地址均是空闲时，将连接到第2个双向链表212的表尾的第3个双向链表213第1个结点恢复至第3个双向链表213第1个结点的位置。

在第一实施例的变更实施例中，本申请队列分配方法，在接收虚拟设备的队列释放请求时，将队列释放请求要释放的一组连续S个队列的地址标记为空闲的步骤之后，还包括：

若队列释放请求要释放的一组连续S[i]个队列的地址是由第j个双向链表的第k至个结点分别存储的一组连续S[j]个队列的地址合并得到的，则将连接到第i个双向链表的表尾的第k至个结点恢复连接至第j个双向链表第k至个结点的位置。

为便于理解，结合图2和图4举例说明小队列空间组合成大队列空间后的队列释放过程。

具体地，若队列释放请求要释放的一组连续S[2]＝4个队列的地址是由第1个双向链表211的第3个结点至第4个结点分别存储的一组连续S[1]＝2个队列的地址合并得到的，则将连接到第2个双向链表212的表尾的第1个双向链表211的第3个结点至第4个结点恢复连接至第1个双向链表211的第3个结点至第4个结点的位置。

本申请第一实施例或第一实施例的变更实施例提供的队列分配方法，通过将待分配的队列分成多种大小与虚拟设备要申请的队列数目对应的队列空间，相同大小的队列空间构成一排，从而构成多排不同大小的队列空间。分配队列空间时，可以优先在排内进行分配，当小队列空间不够分配时，可以拆分大队列空间，当大队列空间不够分配时，可以组合小队列空间，从而可以减少在队列空间中形成空洞，提高队列空间的利用率。

本申请第二实施例提供一种队列分配装置，请参见图5，所述队列分配装置包括：数据结构构建模块501。

数据结构构建模块501，用于构建一个数据结构单元。数据结构单元被配置为存储多个不同的队列数目S，其中，S是正整数。队列数目S是虚拟设备要申请的队列数量。以及对应每个队列数目S，数据结构单元还被配置为存储至少一组连续S个队列的地址。

在第二实施例的变更实施例中，数据结构单元包括一个长度为L的数组，数组被配置为存储多个不同的队列数目S，第i个数组元素存储虚拟设备要申请的队列数目S＝S[i]，其中，L、i和S[i]是正整数，i大于等于1，且i小于等于L。

在第二实施例的变更实施例中，数组被配置为存储根据第一规则设置的多个队列数目S，其中，第一规则是，第i个数组元素存储的队列数目S[i]是虚拟设备要申请的最小队列数目的i次方，且第L个数组元素存储的队列数据S[L]是虚拟设备要申请的最大队列数目。

在第二实施例的变更实施例中，数据结构单元还包括L个双向链表，第i个双向链表包括T[i]个结点，并且第i个双向链表以数组中的第i个数组元素作为头结点，除头结点之外的每个结点存储连续S[i]个队列的地址，其中，T[i]是正整数。

在第二实施例的变更实施例中，第i个双向链表包括根据第二规则设置的T[i]个结点，其中，第二规则是，若第i个双向链表被配置的队列数量是S[i]与T[i]-1的乘积，则L个双向链表被配置的队列总数量等于芯片内部配置的队列数量，其中，T[i]-1与S[i]的乘积等于S[L]，若S[i]大于S[i-1]，则T[i]小于T[i-1]；若S[i]小于S[i-1]，则T[i]大于T[i-1]。

本申请第二实施例提供的队列分配装置，请参见图4，还可以包括：队列申请请求模块502。

队列申请请求模块502，用于接收虚拟设备的队列申请请求，若队列申请请求要申请的队列数量与存储在数据结构单元中的一队列数目S匹配，则将与匹配的队列数目S对应的存储在数据结构单元的空闲的一组连续S个队列的地址分配给队列申请请求，并且将分配给队列申请请求的一组连续S个队列的地址标记为被占用。

在第二实施例的变更实施例中，在队列申请请求要申请的队列数量与存储在数据结构单元中的一队列数目S匹配时，所述队列申请请求模块502还用于：

若第i个双向链表中每个结点存储的一组连续S[i]个队列的地址均标记为被占用，而第j个双向链表的第k个结点存储有空闲的一组连续S[j]个队列的地址，其中，S[i]小于S[j]，j和k为正整数，j小于等于L，k大于1，且k小于等于T[i]，

则将第j个双向链表的第k个结点连接到第i个双向链表的表尾，将第k个结点存储的一组连续S[j]个队列的地址拆分成倍数组连续S[i]个队列的地址，以及将倍数组连续S[i]个队列的地址中的一组地址分配给队列申请请求，并且标记为被占用。

在第二实施例的变更实施例中，在队列申请请求要申请的队列数量与存储在数据结构单元中的一队列数目S匹配时，所述队列申请请求模块502还用于，

若第i个双向链表中每个结点存储的一组连续S[i]个队列的地址均标记为被占用，而第j个双向链表的第k至个结点分别存储有空闲的一组连续S[j]个队列的地址，其中，S[i]大于S[j]，j和k为正整数，j小于等于L，k大于1，且k小于等于T[i]，

则将第j个双向链表的第k至个结点连接至第i个双向链表的表尾，将第k至个结点分别存储的一组连续S[j]个队列的地址合并成一组连续S[i]个队列的地址，以及将合并成一组连续S[i]个队列的地址分配给队列请求，并且标记为被占用。

本申请第二实施例提供的队列分配装置，请参见图4，还可以包括：队列释放请求模块503。

队列释放请求模块503，用于接收虚拟设备的队列释放请求，将队列释放请求要释放的一组连续S个队列的地址标记为空闲。

在第二实施例的变更实施例中，在接收虚拟设备的队列释放请求，以及将队列释放请求要释放的一组连续S个队列的地址标记为空闲时，所述队列释放请求模块503还用于：

若队列释放请求要释放的一组连续S[i]个队列的地址是由第j个双向链表的第k个结点的一组连续S[j]个队列的地址拆分得到的倍数组连续S[i]个队列的地址中的一组地址，则在倍数组连续S[i]个队列的地址中的其它组地址均是空闲时，将连接到第i个双向链表的表尾的第j个双向链表的第k个结点恢复至第j个双向链表第k个结点的位置。

在第二实施例的变更实施例中，在接收虚拟设备的队列释放请求，以及将队列释放请求要释放的一组连续S个队列的地址标记为空闲时，所述队列释放请求模块503还用于：

若队列释放请求要释放的一组连续S[i]个队列的地址是由第j个双向链表的第k至个结点分别存储的一组连续S[j]个队列的地址合并得到的，则将连接到第i个双向链表的表尾的第j个双向链表的第k至个结点恢复连接至第j个双向链表第k至个结点的位置。

本申请第二实施例或第二实施例的变更实施例提供的队列分配装置，通过将待分配的队列分成多种大小与虚拟设备要申请的队列数目对应的队列空间，相同大小的队列空间构成一排，从而构成多排不同大小的队列空间。分配队列空间时，可以优先在排内进行分配，当小队列空间不够分配时，可以拆分大队列空间，当大队列空间不够分配时，可以组合小队列空间，从而可以减少在队列空间中形成空洞，提高队列空间的利用率。

需要说明的是，本申请第二实施例或第二实施例的变更实施例提供的队列分配装置与本申请第一实施例或第一实施例的变更实施例提供的队列分配方法存在对应关系，本申请第二实施例或第二实施例的变更实施例可以参考本申请第一实施例或第一实施例的变更实施例的详细描述。

本申请还提供一种电子设备，所述电子设备可以包括处理器和存储器。存储器上存储有计算机程序或指令。计算机程序或指令被处理器运行时，可以实现本申请第一实施例或第一实施例的变更实施例提供的队列分配方法。

可以理解的是，电子设备可以是数据处理芯片、网络接口卡、服务器、移动终端等设备。

当电子设备是数据处理芯片时，数据处理芯片包括处理器和存储器。存储器上存储有计算机程序或指令。计算机程序或指令被处理器运行时，可以实现本申请第一实施例或第一实施例的变更实施例提供的队列分配方法。

当电子设备是网络接口卡时，网络接口卡包括至少一块数据处理芯片，数据处理芯片可以是带CPU能力的FPGA芯片或者一块带SOC能力的ASIC芯片。所述FPGA芯片或ASIC芯片包括所述处理器和存储器。存储器上存储有计算机程序或指令。计算机程序或指令被处理器运行时，可以实现本申请第一实施例或第一实施例的变更实施例提供的队列分配方法。

当电子设备是服务器时，服务器可以包括网络接口卡，网络接口卡包括至少一块数据处理芯片，数据处理芯片可以是带CPU能力的FPGA芯片或者一块带SOC能力的ASIC芯片。所述FPGA芯片或ASIC芯片包括所述处理器和存储器。存储器上存储有计算机程序或指令。计算机程序或指令被处理器运行时，可以实现本申请第一实施例或第一实施例的变更实施例提供的队列分配方法。

所述服务器可以包括单台计算机设备，也可以包括多个服务器组成的服务器集，或者分布式装置的服务器结构。

本申请还提供一种计算机可读存储介质，所述计算机可读存储介质上存储有计算机程序，该计算机程序被处理器执行时实现上述第一实施例或第一实施例的变更实施例提供的队列分配方法的部分或全部步骤。

本申请还提供一种计算机程序产品。计算机程序产品包括计算机程序或指令。该计算机程序或指令被处理器执行时实现所述队列分配方法的部分或全部步骤。

本领域内的技术人员应明白，本申请的实施例可提供方法、装置、计算机程序产品。因此，本申请可采用完全硬件实施例、完全软件实施例、或结合软件和硬件方面的实施例的形式。而且，本申请可采用在一个或多个其中包含有计算机可用程序代码的计算机可用存储介质(包括但不限于磁盘存储器、CD-ROM、光学存储器等)上实施的计算机程序产品的形式。

本申请是参照根据本申请实施例的方法、设备(装置)、计算机程序产品的流程图和/或方框图来描述的。应理解可由计算机程序指令实现流程图和/或方框图中的每一流程和/或方框、以及流程图和/或方框图中的流程和/或方框的结合。可提供这些计算机程序指令到通用计算机、专用计算机、嵌入式处理机或其他可编程数据处理设备的处理器以产生一个机器，使得通过计算机或其他可编程数据处理设备的处理器执行的指令产生用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的装置。

这些计算机程序指令也可存储在能引导计算机或其他可编程数据处理设备以特定方式工作的计算机可读存储器中，使得存储在该计算机可读存储器中的指令产生包括指令装置的制造品，该指令装置实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能。

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

本申请中应用了具体实施例对本申请的原理及实施方式进行了阐述，以上实施例的说明只是用于帮助理解本申请的方法及其核心思想；同时，对于本领域的一般技术人员，依据本申请的思想，在具体实施方式及应用范围上均会有改变之处，综上所述，本申请说明书内容不应理解为对本申请的限制。