队列管理方法和队列管理器、队列消息的处理方法和系统

摘要

一种队列管理方法，包括：初始设置队列指针和队列计数器，所述队列指针包括头指针、虚尾指针和实尾指针；发送对应于接收到的队列消息的写请求，并根据发送的写请求的数量累加虚尾指针；根据接收到的写结束确认更新队列计数器，并根据所述写结束确认所包含的元素空间的地址和更新后的队列计数器更新实尾指针，所述头指针和实尾指针之间的元素空间为可消费的队列空间。本发明还公开了一种队列管理器、队列消息的处理方法和系统，不需要顺序执行写请求也能保证队列尾指针的更新和数据写入队列的元素空间的同步，可适用于在大规模并行计算机系统上实现高效的基于队列消息的传送机制，扩大了队列消息的应用范围。

说明书

技术领域

本发明涉及计算机技术，特别是涉及一种队列管理方法和队列管理器、队列消息的处理方法和系统。

背景技术

在大规模并行计算机网络系统中，共享存储和消息传递是并行计算的两个主要编程模型。通常，系统包含有多个节点，每个节点内有多个处理器(CPU)，节点内存储器为分布共享存储器结构，因此，节点内的CPU可以直接读写本节点内的所有存储器(即共享存储)的数据；而当一个节点的CPU要访问另一个节点的存储器时，需要通过消息传递来实现。

采用队列消息是实现一个节点的CPU向另一个节点的存储器写入数据的一种方式，队列消息是将源存储空间上的数据发送到目的方指定的队列上，队列是预先分配(一般是由软件配置)的一段连续的存储器的物理空间或虚空间，队列的基本单位即用于存放一个队列元素的存储空间称为元素空间。

通常来说，队列消息的目的方(即接收方)的队列采用的是循环队列，接收方通过队列管理器和软件管理队列：队列的基地址、队列容量、队列属性等信息可以由软件初始化配置；在队列元素的生产(即写入数据)后通过队列管理器修改队列尾指针；在队列元素的消费(即读取数据)后通过软件修改队列头指针。在申请号为200610057353.0的中国发明专利申请中可以找到有关队列及其数据存储方法的信息。

在队列消息传递时，发送方并不知道目的队列的地址，只需要知道一个队列号，并发送包含有队列号和队列元素的队列消息；当接收方的队列管理器接收到队列消息时，根据队列的初始化配置和发送方发送的队列号，向队列所在的存储器发送对应的包含有待写入的数据和待写入数据的元素空间的地址的写请求，收到存储器返回的写结束确认后将队列尾指针加一，以指示队列最新空闲的元素空间；进程在队列头指针的指示下消费队列，每次取走队列的一部分队列元素后，根据消费的队列元素的数量更新队列头指针，以指示队列中下一个可消费的元素空间。

进程可使用中断或查询方式消费队列，无论采用哪种方式，都要先读取队列管理器中相应队列的头指针和尾指针，判断队列中有多少队列元素可以消费以及队列头元素的位置(可消费的数据的首地址)，然后读取相应元素空间的队列元素。这就存在队列尾指针的更新和消息数据写入队列的元素空间两者之间的同步问题，在队列管理中，必须保证消息数据已写入队列的元素空间后，才能修改队列尾指针，以确保头指针和尾指针之间的队列元素可以消费，即进程能够访问到有效的数据。

然而，在采用多处理器和分布共享存储器的并行计算机网络系统中，由于存储器的分布特性，或者，由于要支持置无效、写更新等缓存(CACHE)一致性协议，写结束确认的返回顺序一般和写请求的发送顺序不一致，也就是说，写请求不是顺序执行，而是乱序执行，这样就限制了队列消息的应用，队列管理器无法根据收到的写结束确认所包含的元素空间的地址来按序对队列尾指针加一。

为了使队列管理器根据收到的写结束确认所包含的元素空间的地址来按序对队列尾指针加一，就需要保证队列的写请求是顺序执行。一种解决方法是串行执行写请求，队列管理器要收到上一个写请求的写结束确认后，才开始处理新的写请求，这种方法降低了队列消息的传送效率。

另一种解决方法由硬件和软件共同保证写请求的顺序执行，例如硬件确保写请求和写结束确认在通路上按序流动(即写结束确认的返回顺序和写请求的发送顺序一致)，软件则限制队列的存储空间为不可缓存空间，确保队列的存储空间无缓存一致性问题。采用硬件和软件结合的方法不仅不利于编程，也限制了硬件的实现。

发明内容

本发明解决的问题是，提供一种队列管理方法和队列管理器、队列消息的处理方法和系统，不需要顺序执行写请求就能保证队列尾指针的更新和数据写入队列的元素空间的同步，因而扩大了队列消息的应用范围。

为解决上述问题，本发明提供一种队列管理方法，包括下述步骤：

初始设置队列指针和队列计数器，所述队列指针包括头指针、虚尾指针和实尾指针，所述头指针和实尾指针之间的元素空间为可消费的队列空间；

发送对应于接收到的队列消息的写请求，并根据发送的写请求的数量累加虚尾指针；

根据接收到的写结束确认更新队列计数器，并根据所述写结束确认所包含的元素空间的地址和更新后的队列计数器更新实尾指针。

可选的，所述初始设置队列指针和队列计数器包括：在系统初始状态时，将队列指针指向队列的第一个元素空间的位置，将队列计数器清零。

在本发明的一种实施方式中，所述队列指针还包括最大捕获尾指针，指向已写入数据的最后一个元素空间的后一元素空间的位置；所述队列计数器为最大捕获写结束计数器，对所述最大捕获尾指针和实尾指针之间已写入数据的元素空间的数量进行计数。

所述根据接收到的写结束确认更新队列计数器，并根据所述写结束确认所包含的元素空间的地址和更新后的队列计数器更新实尾指针，包括下述步骤：

根据接收到的写结束确认的数量，累加最大捕获写结束计数器的计数值；

从接收到的写结束确认中获取已写入数据的元素空间的地址；

在所述获取的元素空间的地址大于或等于最大捕获尾指针的值时，将最大捕获尾指针指向所述已写入数据的元素空间的后一元素空间的位置；

在所述最大捕获尾指针与实尾指针的差值等于最大捕获写结束计数器的计数值时，将实尾指针指向最大捕获尾指针所指向的位置，并将最大捕获写结束计数器清零。

所述队列管理方法还包括：在虚尾指针和实尾指针的差值大于或等于预设的最大消息处理量时，阻塞新的队列消息直到实尾指针被更新，或者，丢弃新的队列消息并发送队列消息的失败确认给所述新的队列消息的发送方。

在本发明的另一种实施方式中，所述队列指针还包括第一捕获尾指针和最大捕获尾指针，所述最大捕获尾指针指向已写入数据的最后一个元素空间的后一元素空间的位置，所述第一捕获尾指针在收到写结束确认并且实尾指针的值等于第一捕获尾指针的值时指向对应于所述写结束确认的元素空间的后一元素空间的位置；所述队列计数器包括对最大捕获尾指针和第一捕获尾指针之间已写入数据的元素空间的数量进行计数的最大捕获写结束计数器和对第一捕获尾指针和实尾指针之间已写入数据的元素空间的数量进行计数的第一捕获写结束计数器。

所述根据所述写结束确认更新队列计数器，并根据所述写结束确认所包含的元素空间的地址和更新后的队列计数器更新实尾指针，包括下述步骤：

从接收到的写结束确认中获取已写入数据的元素空间的地址；

在实尾指针的值等于第一捕获尾指针的值时，将第一捕获尾指针、最大捕获尾指针指向所述已写入数据的元素空间的后一元素空间的位置，并将第一捕获写结束计数器加一；

在实尾指针的值不等于第一捕获尾指针的值并且所述获取的元素空间的地址大于或等于第一捕获尾指针的值时，将最大捕获写结束计数器加一；

在实尾指针的值不等于第一捕获尾指针的值并且所述获取的元素空间的地址小于第一捕获尾指针的值时，将第一捕获写结束计数器加一；

在实尾指针的值不等于第一捕获尾指针的值并且在所述获取的元素空间的地址大于或等于最大捕获尾指针的值时，将最大捕获尾指针指向所述已写入数据的元素空间的后一元素空间的位置；

在第一捕获写结束计数器更新后并且第一捕获尾指针与实尾指针的差值等于第一捕获写结束计数器的计数值时，将实尾指针指向第一捕获尾指针所指向的位置，再将第一捕获尾指针指向最大捕获尾指针所指向的位置，将第一捕获写结束计数器的计数值设为最大捕获写结束计数器的计数值，再将最大捕获写结束计数器清零。

对应于上述队列管理方法，本发明还提供一种队列管理器，包括：

队列指针寄存器，储存队列指针，所述队列指针包括头指针、虚尾指针和实尾指针，所述头指针和实尾指针之间的元素空间为可消费的队列空间；

队列计数器，对已写入数据的元素空间的数量进行计数；

设置单元，初始设置队列指针寄存器和队列计数器；

发送单元，发送对应于接收到的队列消息的写请求，并根据发送的写请求的数量累加虚尾指针；

更新单元，根据接收到的写结束确认更新队列计数器，并根据所述写结束确认所包含的元素空间的地址和更新后的队列计数器更新实尾指针。

为解决上述问题，本发明还提供一种队列消息的处理方法，包括下述步骤：

发送方向接收方发送访问接收方的队列存储器的队列消息；

接收方的队列管理器在接收到队列消息后，向接收方的队列存储器发送对应于所述队列消息的写请求，并根据发送的写请求的数量累加队列管理器的虚尾指针；

接收方的队列存储器在接收到写请求后，将写请求中的数据写入对应的元素空间，并向所述接收方的队列管理器返回对应的写结束确认；

接收方的队列管理器在接收到写结束确认后，根据所述写结束确认更新队列管理器的队列计数器，并根据所述写结束确认所包含的元素空间的地址和更新后的队列计数器更新队列管理器的实尾指针；

接收方的队列管理器根据所述写结束确认，向发送方返回对应的队列消息的确认。

对应于上述队列消息的处理方法，本发明还提供一种队列消息的处理系统，包括发送方和接收方，所述接收方包括队列存储器和队列管理器，其中，

所述发送方，向接收方发送访问接收方的队列存储器的队列消息，并接收所述接收方返回的对应的队列消息的确认；

所述队列存储器，接收所述队列管理器发送的写请求，将写请求中的数据写入对应的元素空间，并向所述队列管理器返回对应的写结束确认；

所述队列管理器，接收所述发送方发送的队列消息、向所述队列存储器发送对应于所述队列消息的写请求、并根据发送的写请求的数量累加虚尾指针，接收所述队列存储器返回的写结束确认、根据所述写结束确认更新队列计数器、并根据所述写结束确认所包含的元素空间的地址和更新后的队列计数器更新实尾指针，根据所述写结束确认，向发送方返回对应的队列消息的确认。

与现有技术相比，上述技术方案设置了头指针、虚尾指针、实尾指针和队列计数器，根据接收的写结束确认更新队列计数器，并且根据写结束确认所包含的元素空间的地址和更新后的队列计数器更新实尾指针，这样，头指针和实尾指针之间的元素空间表示可消费的队列空间；实尾指针和虚尾指针之间的元素空间表示不可消费的队列空间。因此，即使写结束确认的返回顺序和存储器写请求的发送顺序不一致，也能保证队列尾指针(实尾指针)的更新和数据写入队列的元素空间的同步，因而扩大了队列消息的应用范围。

附图说明

图1是本发明第一实施方式的队列管理方法的指针设置的流程图；

图2是图1所示的队列管理方法的实例图；

图3是本发明第一实施方式的队列管理器的结构示意图；

图4是本发明第二实施方式的队列管理方法的指针设置的流程图；

图5是图4所示的队列管理方法的实例图；

图6是本发明第二实施方式的队列管理器的结构示意图；

图7是本发明实施方式的队列消息的处理方法的流程图。

具体实施方式

本发明实施方式增加了队列指针和队列计数器，并根据写结束确认更新队列计数器，并根据所述写结束确认所包含的元素空间的地址和队列计数器更新实尾指针，以确保头指针和实尾指针之间的元素空间为可消费的队列空间。因此，即使写结束确认的返回顺序和写请求的发送顺序不一致，也能保证队列尾指针的更新和数据写入队列的元素空间的同步。

本发明实施方式的队列管理方法包括下述步骤：

初始设置队列指针和队列计数器，所述队列指针包括头指针、虚尾指针和实尾指针；

发送对应于接收到的队列消息的写请求，并根据发送的写请求的数量累加虚尾指针；

根据接收到的写结束确认更新队列计数器，并根据所述写结束确认所包含的元素空间的地址和更新后的队列计数器更新实尾指针，所述头指针和实尾指针之间的元素空间为可消费的队列空间。

本发明实施方式的队列管理器包括：

队列指针寄存器，储存队列指针，所述队列指针包括头指针、虚尾指针和实尾指针；

队列计数器，对已写入数据的元素空间的数量进行计数；

设置单元，初始设置队列指针寄存器和队列计数器；

发送单元，发送对应于接收到的队列消息的写请求，并根据发送的写请求的数量累加虚尾指针；

更新单元，根据接收到的写结束确认更新队列计数器，并根据所述写结束确认所包含的元素空间的地址和更新后的队列计数器更新实尾指针，所述头指针和实尾指针之间的元素空间为可消费的队列空间。

下面即结合附图对本发明的实施方式做详细的说明。

第一实施方式

本实施方式的队列管理方法设置了四个队列指针和一个队列计数器，所述队列指针包括：头指针(hp，Head Pointer)、实尾指针(tp，Real Tail Pointer)、虚尾指针(v_tp，Virtual Tail Pointer)和最大捕获尾指针(mc_tp，MaximalCapture Tail Pointer)。所述队列计数器为最大捕获写结束计数器(mc_cnt，Maximal Capture End Counter)。

所述头指针和实尾指针之间的元素空间为可消费的队列空间，头指针指向可消费的队列头元素所在的元素空间的位置，实尾指针指向可消费的队列尾元素所在的元素空间的后一元素空间的位置。所述虚尾指针指向最后一个写请求的待写入数据的元素空间的后一元素空间的位置，实尾指针和虚尾指针之间的元素空间为不可消费的队列空间，包括至少一个没有写入数据的元素空间。初始状态时，头指针、实尾指针和虚尾指针都设置为指向队列的第一个元素空间的位置。

所述最大捕获尾指针指向已写入数据的最后一个元素空间的后一元素空间的位置。初始状态时，最大捕获尾指针设置为指向队列的第一个元素空间的位置，随着写结束确认的返回，最大捕获尾指针根据写结束确认所包含的元素空间的地址更新。

所述最大捕获写结束计数器，对最大捕获尾指针和实尾指针之间已写入数据的元素空间的数量进行计数。

本实施方式的队列管理方法包括：初始化流程、队列消息处理流程和指针设置流程。

所述初始化流程包括：初始配置队列，初始设置队列指针和队列计数器。在系统初始状态时，在系统存储器空间中为队列配置数据的存储空间，完成对队列的基地址、容量、空间属性和访问权限等属性的定义，将头指针、实尾指针、虚尾指针和最大捕获尾指针都指向队列的第一个元素空间的位置，将最大捕获写结束计数器清零。本实施方式中，头指针、实尾指针、虚尾指针和最大捕获尾指针的值是相对于队列的基地址的偏移量。

在初始化流程后，可以并行执行队列消息处理流程和指针设置流程，也可以串行执行队列消息处理流程和指针设置流程。

所述队列消息处理流程包括：在接收到队列消息后，发送对应于所述队列消息的写请求，再根据发送的写请求的数量，累加虚尾指针，即更新虚尾指针。本实施方式中，写请求包含待写入的数据和待写入数据的元素空间的地址，所述待写入数据的元素空间的地址是根据队列的基地址和更新前的虚尾指针的值得到的。

所述指针设置流程如图1所示：

步骤S11，在接收到写结束确认后，根据接收到的写结束确认的数量，累加最大捕获写结束计数器的计数值，即更新最大捕获写结束计数器。在数据写入所述待写入数据的元素空间后，将接收到存储器返回的包含元素空间的地址的写结束确认。

步骤S12，从接收到的写结束确认中获取已写入数据的元素空间的地址。在接收到写结束确认后，获取写结束确认所包含的元素空间的地址，该地址即为已写入数据的元素空间的地址。本实施方式中，写结束确认所包含的元素空间的地址是相对于队列的基地址的偏移量。

上述步骤S11和S12的顺序并不以本实施方式所述的顺序为限，也可以先执行步骤S12，再执行步骤S11。

步骤S13，判断所述从接收到的写结束确认中获取的元素空间的地址是否大于或等于最大捕获尾指针的值：若是，则执行步骤S14，若否，则执行步骤S15。

步骤S14，所述获取的元素空间的地址大于或等于最大捕获尾指针的值，则更新最大捕获尾指针，将最大捕获尾指针的值设为所述获取的元素空间的地址加一，即将最大捕获尾指针指向所述已写入数据的元素空间的后一元素空间的位置。

步骤S15，所述获取的元素空间的地址小于最大捕获尾指针的值，则判断最大捕获尾指针与实尾指针的差值是否等于最大捕获写结束计数器的计数值：若是，则执行步骤S16，若否，则执行步骤S11。

步骤S16，更新实尾指针，即将实尾指针指向最大捕获尾指针所指向的位置，并将最大捕获写结束计数器清零，继续执行步骤S11。当步骤S15的判断结果为最大捕获尾指针与实尾指针的差值等于最大捕获写结束计数器的计数值时，实尾指针和最大捕获尾指针之间的元素空间已写满数据，成为可消费的队列空间，因此，将实尾指针的值更新为最大捕获尾指针的值，最大捕获写结束计数器清零，以重新对最大捕获尾指针和实尾指针之间已写入数据的元素空间的数量进行计数。

当对应于写请求的写结束确认都已返回，说明已发送的写请求都处理完成，队列消息的数据都写入了对应的元素空间，实尾指针的值等于虚尾指针的值。

另外，在上述的指针设置流程中，可能会因为最大捕获尾指针的不断更新而出现实尾指针和最大捕获尾指针之间的元素空间长时间无法写满数据，实尾指针无法根据最大捕获尾指针更新，队列无法消费的情况。为了保证实尾指针和最大捕获尾指针之间的元素空间能够写满数据，本实施方式还设置最大消息处理量。

因此，上述队列消息处理流程还可以包括，在接收到新的队列消息时，判断虚尾指针和实尾指针的差值是否大于或等于预设的最大消息处理量：

若虚尾指针和实尾指针的差值大于或等于预设的最大消息处理量，则阻塞(不处理)所述新的队列消息，直到实尾指针被更新再对接收到的队列消息进行处理；

或者，若虚尾指针和实尾指针的差值大于或等于预设的最大消息处理量，则丢弃所述新的队列消息，并发送队列消息的失败确认给所述队列消息的发送方，通知发送方重新发送队列消息。

若虚尾指针和实尾指针的差值小于预设的最大消息处理量，则继续对接收到的队列消息进行处理。

下面以一个实例对本实施方式的队列管理方法进行说明，设定最大消息处理量为8，头指针、实尾指针、虚尾指针、最大捕获尾指针、最大捕获写结束计数器和队列的元素空间的变化如图2所示：

(2-1)系统处于初始状态时，头指针hp、实尾指针tp、虚尾指针v_tp、最大捕获尾指针mc_tp、最大捕获写结束计数器mc_cnt的初始值都为0。

(2-2)接收到来自多个远程进程的访问同一条队列的8个队列消息，将虚尾指针v_tp的值置为8。向存储器发送8个写请求，定义为MemW0、MemW1...MemW7，分别对队列的元素空间0～7写入数据。

(2-3)接收到对应写请求MemW3的写结束确认，更新最大捕获尾指针mc_tp的值为4，更新最大捕获写结束计数器mc_cnt的计数值为1。

(2-4)分别接收到对应写请求MemW1、MemW2、MemW6的写结束确认，更新最大捕获尾指针mc_tp的值为7，更新最大捕获写结束计数器mc_cnt的计数值为4。

(2-5)接收到对应写请求MemW0的写结束确认，更新最大捕获写结束计数器mc_cnt的计数值为5。

(2-6)接收到访问该队列的2个队列消息，由于虚尾指针和实尾指针的差值等于预设的最大消息处理量，无法处理后续该队列的异步消息，因此阻塞(不处理)这2个队列消息或向消息的发起方返回消息的失败确认，虚尾指针v_tp的值保持不变。

(2-7)分别接收到对应写请求Mem W4、Mem W5的写结束确认，实尾指针tp与最大捕获尾指针mc_tp之间的元素空间已写满数据，成为无缝数据空间，更新实尾指针tp的值为7，将最大捕获写结束计数器mc_cnt清0。

......

对应于上述队列管理方法，本实施方式的队列管理器如图3所示，包括：队列指针寄存器30、最大捕获写结束计数器31、设置单元32、发送单元33和更新单元(图中未标示)。

队列指针寄存器30，用于储存队列指针，所述队列指针包括：头指针hp、实尾指针tp、虚尾指针v_tp和最大捕获尾指针mc_tp。

最大捕获写结束计数器31，对最大捕获尾指针mc_tp和实尾指针tp之间已写入数据的元素空间的数量进行计数。

设置单元32，初始配置队列，初始设置队列指针寄存器30和最大捕获写结束计数器31。在系统初始状态时，将头指针hp、实尾指针tp、虚尾指针v_tp、最大捕获尾指针mc_tp、最大捕获写结束计数器31设置为0。

发送单元33，发送对应于接收到的队列消息的写请求，再根据发送的写请求的数量，累加虚尾指针。写请求包含待写入的数据和待写入数据的元素空间的地址。

所述更新单元包括：累加单元34、获取单元35、第一更新单元36和第二更新单元37。

累加单元34，根据接收到的写结束确认的数量，累加最大捕获写结束计数器31的计数值。

获取单元35，从接收到的写结束确认中获取已写入数据的元素空间的地址。在数据写入所述待写入数据的元素空间后，返回的写结束确认中包含所述已写入数据的元素空间的地址。

第一更新单元36，判断所述获取单元35获取的元素空间的地址是否大于或等于最大捕获尾指针mc_tp的值：若是，则将最大捕获尾指针mc_tp指向所述已写入数据的元素空间的后一元素空间的位置；若否，则不更新最大捕获尾指针mc_tp。

第二更新单元37，根据第一更新单元36得到的最大捕获尾指针mc_tp，判断最大捕获尾指针mc_tp与实尾指针tp的差值是否等于最大捕获写结束计数器mc_cnt的计数值：若是，则将实尾指针tp指向最大捕获尾指针mc_tp所指向的位置，将最大捕获写结束计数器31清零；若否，则不更新实尾指针tp。

接着，由累加单元34、获取单元35、第一更新单元36、第二更新单元37继续对接收到的写结束确认进行处理。

所述队列管理器还可以包括，阻止单元38，在接收到新的队列消息时，判断虚尾指针和实尾指针的差值是否大于或等于预设的最大消息处理量：

若虚尾指针和实尾指针的差值大于或等于预设的最大消息处理量，则阻塞(不处理)所述新的队列消息，直到实尾指针被更新后，再由发送单元33继续对接收到的队列消息进行处理；

或者，若虚尾指针和实尾指针的差值大于或等于预设的最大消息处理量，则丢弃所述新的队列消息，并发送队列消息的失败确认给所述队列消息的发送方；

若虚尾指针和实尾指针的差值小于预设的最大消息处理量，则由发送单元33继续对接收到的队列消息进行处理。

第二实施方式

本实施方式的队列管理方法设置了五个队列指针和二个队列计数器，所述队列指针包括：头指针、实尾指针、虚尾指针、最大捕获尾指针和第一捕获尾指针(fc_tp，First Capture Tail Pointer)。所述队列计数器包括：最大捕获写结束计数器和第一捕获写结束计数器。

所述头指针和实尾指针之间的元素空间为可消费的队列空间，头指针指向可消费的队列头元素所在的元素空间的位置，实尾指针指向可消费的队列尾元素所在的元素空间的后一元素空间的位置。所述虚尾指针指向最后一个写请求的待写入数据的元素空间的后一元素空间的位置，实尾指针和虚尾指针之间的元素空间为不可消费的队列空间，包括至少一个没有写入数据的元素空间。初始状态时，头指针、实尾指针和虚尾指针都设置为指向队列的第一个元素空间的位置。

所述最大捕获尾指针指向已写入数据的最后一个元素空间的后一元素空间的位置。所述第一捕获尾指针的值小于或等于最大捕获尾指针的值。初始状态时，第一捕获尾指针和最大捕获尾指针设置为指向队列的第一个元素空间的位置；在收到写结束确认并且实尾指针的值等于第一捕获尾指针的值时，第一捕获尾指针和最大捕获尾指针指向对应于所述写结束确认的元素空间的后一元素空间的位置(对应于所述写结束确认的元素空间的地址即为所述写结束确认所包含的元素空间的地址)；随着后续写结束确认的返回，最大捕获尾指针根据写结束确认所包含的元素空间的地址更新，第一捕获尾指针在实尾指针更新后根据最大捕获尾指针更新。

最大捕获写结束计数器，对最大捕获尾指针和第一捕获尾指针之间已写入数据的元素空间的数量进行计数；第一捕获写结束计数器，对第一捕获尾指针和实尾指针之间已写入数据的元素空间的数量进行计数。

本实施方式的队列管理方法包括：初始化流程、队列消息处理流程和指针设置流程。

所述初始化流程包括：初始配置队列，初始设置队列指针和队列计数器。在系统初始状态时，在系统存储器空间中为队列配置数据的存储空间，完成对队列的基地址、容量、空间属性和访问权限等属性的定义，将头指针、实尾指针、虚尾指针、第一捕获尾指针和最大捕获尾指针都指向队列的第一个元素空间的位置，将第一捕获写结束计数器和最大捕获写结束计数器清零。本实施方式中，头指针、实尾指针、虚尾指针、第一捕获尾指针和最大捕获尾指针的值是相对于队列的基地址的偏移量。

在初始化流程后，可以并行执行队列消息处理流程和指针设置流程，也可以串行执行队列消息处理流程和指针设置流程。

所述队列消息处理流程包括：在接收到队列消息后，发送对应于所述队列消息的写请求，再根据发送的写请求的数量，累加虚尾指针，即更新虚尾指针。本实施方式中，写请求包含待写入的数据和待写入数据的元素空间的地址，所述待写入数据的元素空间的地址是根据队列的基地址和更新前的虚尾指针的值得到的。

所述指针设置流程如图4所示：

步骤S41，在接收到写结束确认后，从接收到的写结束确认中获取已写入数据的元素空间的地址。在数据写入所述待写入数据的元素空间后，将接收到存储器返回的包含元素空间的地址的写结束确认，该地址即为已写入数据的元素空间的地址。本实施方式中，写结束确认所包含的元素空间的地址是相对于队列基地址的偏移量。

步骤S42，判断实尾指针的值是否等于第一捕获尾指针的值：若是，则执行步骤S43；若否，则执行步骤S44。

步骤S43，将第一捕获尾指针、最大捕获尾指针的值设为所述获取的元素空间的地址加一，即将第一捕获尾指针、最大捕获尾指针指向所述已写入数据的元素空间的后一元素空间的位置，接着执行步骤S47。

步骤S44，判断所述获取的元素空间的地址是否大于或等于第一捕获尾指针的值：若是，则执行步骤S45，若否，则执行步骤S47。

步骤S45，将最大捕获写结束计数器加一，判断所述获取的元素空间的地址是否大于或等于最大捕获尾指针的值：若是，则执行步骤S46，若否，则执行步骤S41。

步骤S46，所述获取的元素空间的地址大于或等于最大捕获尾指针，更新最大捕获尾指针，将最大捕获尾指针的值设为所述获取的元素空间的地址加一，即将最大捕获尾指针指向所述已写入数据的元素空间的后一元素空间的位置。接着执行步骤S41。

步骤S47，将第一捕获写结束计数器加一，判断第一捕获尾指针与实尾指针的差值是否等于第一捕获写结束计数器的计数值：若是，则执行步骤S48；若否，则执行步骤S41。

步骤S48，更新实尾指针和第一捕获尾指针，即将实尾指针指向第一捕获尾指针所指向的位置，再将第一捕获尾指针指向最大捕获尾指针所指向的位置，并且，将第一捕获写结束计数器的计数值设为最大捕获写结束计数器的计数值，再将最大捕获写结束计数器清零，继续执行步骤S41。当步骤S47的判断结果为第一捕获尾指针与实尾指针的差值等于第一捕获写结束计数器的计数值时，实尾指针和第一捕获尾指针之间的元素空间已写满数据，成为可消费的队列空间，因此，将实尾指针的值更新为第一捕获尾指针的值，再将第一捕获尾指针的值更新为最大捕获尾指针的值，并且，将第一捕获写计数器的计数值更新为最大捕获写结束计数器的计数值，以对更新后的第一捕获尾指针和实尾指针之间已写入数据的元素空间的数量进行计数，再将最大捕获写结束计数器清零，以重新对最大捕获尾指针和第一捕获尾指针之间已写入数据的元素空间的数量进行计数。

当对应于写请求的写结束确认都已返回，说明已发送的写请求都处理完成，队列消息的数据都写入了对应的元素空间，实尾指针的值等于虚尾指针的值。

与第一实施方式相比，本实施方式增加设置了第一捕获尾指针和第一捕获写结束计数器，实尾指针、第一捕获尾指针、最大捕获尾指针通过传递赋值的方式完成对实尾指针的更新，即实尾指针根据第一捕获尾指针更新，而第一捕获尾指针在实尾指针更新后才根据最大捕获尾指针更新，因此，不会出现如第一实施方式所述的实尾指针无法更新，队列无法消费的情况。

下面以一个实例对本实施方式的队列管理方法进行说明，头指针、实尾指针、虚尾指针、第一捕获尾指针、最大捕获尾指针、第一捕获写结束计数器、最大捕获写结束计数器和队列的元素空间的变化如图5所示：

(5-1)系统处于初始状态时，头指针hp、实尾指针tp、虚尾指针v_tp、第一捕获尾指针fc_tp、最大捕获尾指针mc_tp、第一捕获写结束计数器fc_cnt和最大捕获写结束计数器mc_cnt的初始值都为0。

(5-2)接收到来自多个远程进程的访问同一条队列的8个队列消息，将虚尾指针v_tp置为8。向存储器发送8个写请求，定义为MemW0、MemW1...MemW7，分别对队列存储器的元素空间0～7写入数据。

(5-3)接收到对应写请求MemW3的写结束确认，实尾指针tp的值等于第一捕获尾指针fc_tp的值，更新第一捕获尾指针fc_tp、最大捕获尾指针mc_tp的值为4，更新第一捕获写结束计数器fc_cnt的计数值为1。

(5-4)分别接收到对应写请求MemW1、MemW2、MemW6的写结束确认，更新最大捕获尾指针mc_tp的值为7，更新第一捕获写结束计数器fc_cnt的计数值为3，更新最大捕获写结束计数器mc_cnt的计数值为1。

(5-5)接收到对应写请求MemW0的写结束确认，更新第一捕获写结束计数器fc_cnt的计数值为4。此时，实尾指针tp与第一捕获尾指针fc_tp之间的元素空间已写满数据，成为无缝数据空间，更新实尾指针tp的值为4，更新第一捕获尾指针fc_tp的值为7，更新第一捕获写结束fc_cnt计数器的计数值为1，将最大捕获写结束计数器mc_cnt清0。

(5-6)接收到访问该队列的2个队列消息，将虚尾指针v_tp的值置为10。向存储器发送2个写请求，定义为Mem W8、Mem W9，分别对队列存储器的元素空间8～9写入数据。

(5-7)分别接收到对应写请求Mem W4、Mem W5、Mem W9的写结束确认，更新最大捕获尾指针的值为10，更新第一捕获写结束计数器fc_cnt的计数值为3，更新最大捕获写结束计数器mc_cnt的计数值为1。此时，实尾指针tp与第一捕获尾指针fc_tp之间的元素空间已写满数据，成为无缝数据空间，更新实尾指针tp的值为7，更新第一捕获尾指针fc_tp的值为10，更新第一捕获写结束fc_cnt计数器的计数值为1，将最大捕获写结束计数器mc_cnt清0。

......

对应于上述队列管理方法，本实施方式的队列管理器如图6所示，包括：队列指针寄存器60、队列计数器61、设置单元62、发送单元63、更新单元(图中未标示)。

队列指针寄存器60，用于储存队列指针，所述队列指针包括：头指针hp、实尾指针tp、虚尾指针v_tp、第一捕获尾指针fc_tp和最大捕获尾指针mc_tp。

队列计数器61，包括：对第一捕获尾指针fc_tp和实尾指针tp之间已写入数据的元素空间的数量进行计数的第一捕获写结束计数器fc_cnt，对最大捕获尾指针mc_tp和第一捕获尾指针fc_tp之间已写入数据的元素空间的数量进行计数的最大捕获写结束计数器mc_cnt。

设置单元62，初始配置队列，初始设置队列指针寄存器60和队列计数器61。在系统初始状态时，将头指针hp、实尾指针tp、虚尾指针v_tp、第一捕获尾指针fc_tp、最大捕获尾指针mc_tp、第一捕获写结束计数器fc_cnt、最大捕获写结束计数器mc_cnt设置为0。

发送单元63，发送对应于接收到的队列消息的写请求，再根据发送的写请求的数量，累加虚尾指针。写请求包含待写入的数据和待写入数据的元素空间的地址。

所述更新单元包括：获取单元64、第一更新单元65、第二更新单元66、第三更新单元67和第四更新单元68。

获取单元64，从接收到的写结束确认中获取已写入数据的元素空间的地址。在数据写入所述待写入数据的元素空间后，返回的写结束确认中包含已写入数据的元素空间的地址。

第一更新单元65，判断实尾指针的值是否等于第一捕获尾指针的值：若实尾指针等于第一捕获尾指针，则将第一捕获尾指针fc_tp、最大捕获尾指针mc_tp的值设为所述获取的元素空间的地址加一，即将第一捕获尾指针fc_tp、最大捕获尾指针mc_tp指向所述已写入数据的元素空间的后一元素空间的位置，并将第一捕获写结束计数器fc_cnt的计数值加一，将判断结果和得到的第一捕获尾指针fc_tp、第一捕获写结束计数器fc_cnt传送给第四更新单元68；若实尾指针不等于第一捕获尾指针，则将判断结果传送给第二更新单元66。

第二更新单元66，在第一更新单元65的判断结果为实尾指针的值不等于第一捕获尾指针的值时，判断所述获取的元素空间的地址是否大于或等于第一捕获尾指针fc_tp的值：若是，则将最大捕获写结束计数器mc_cnt的计数值加一，将判断结果传送给第三更新单元67；若否，则将第一捕获写结束计数器fc_cnt的计数值加一，将判断结果和得到的第一捕获写结束计数器fc_cnt传送给第四更新单元68。

第三更新单元67，在第二更新单元66的判断结果为所述获取的元素空间的地址大于或等于第一捕获尾指针fc_tp的值时，判断所述获取的元素空间的地址是否大于或等于最大捕获尾指针mc_tp的值：若所述获取的元素空间的地址大于或等于最大捕获尾指针mc_tp的值，则更新最大捕获尾指针mc_tp，将最大捕获尾指针mc_tp的值设为所述获取的元素空间的地址加一，即将最大捕获尾指针mc_tp指向所述已写入数据的元素空间的后一元素空间的位置，接着，由获取单元64、第一更新单元65、第二更新单元66、第三更新单元67、第四更新单元68继续对接收到的写结束确认进行处理。

第四更新单元68，在第一更新单元65的判断结果为实尾指针的值不等于第一捕获尾指针的值、或者第二更新单元66的判断结果为所述获取的元素空间的地址小于第一捕获尾指针fc_tp的值时(即在第一捕获写结束计数器fc_cnt的计数值更新后)，判断第一捕获尾指针fc_tp与实尾指针tp的差值是否等于第一捕获写结束计数器fc_cnt的计数值：若第一捕获尾指针fc_tp与实尾指针tp的差值等于第一捕获写结束计数器fc_cnt的计数值，则更新实尾指针tp和第一捕获尾指针fc_tp，即将实尾指针tp指向第一捕获尾指针fc_tp所指向的位置，再将第一捕获尾指针fc_tp指向最大捕获尾指针mc_tp所指向的位置，并且，将第一捕获写结束计数器fc_cnt的计数值设为最大捕获写结束计数器mc_cnt的计数值，再将最大捕获写结束计数器mc_cnt清零，接着，由获取单元64、第一更新单元65、第二更新单元66、第三更新单元67、第四更新单元68继续对接收到的写结束确认进行处理。

若所述第三更新单元67的判断结果为所述获取的元素空间的地址小于最大捕获尾指针mc_tp的值，或者所述第四更新单元68的判断结果为第一捕获尾指针fc_tp与实尾指针tp的差值不等于第一捕获写结束计数器fc_cnt的计数值，则由获取单元64、第一更新单元65、第二更新单元66、第三更新单元67、第四更新单元68继续对接收到的写结束确认进行处理。

本发明实施方式还提供一种队列消息的处理方法，如图7所示，包括下述步骤：

步骤S71，发送方71向接收方72发送访问接收方72的队列存储器721(即队列所在的存储器)的队列消息。

步骤S72，接收方72的队列管理器722在接收到队列消息后，向接收方的队列存储器721发送对应于所述队列消息的写请求，并根据发送的写请求的数量累加虚尾指针。

步骤S73，接收方72的队列存储器721在接收到写请求后，将写请求中的数据写入对应的元素空间，并向所述接收方72的队列管理器722返回对应的写结束确认。

步骤S74，接收方72的队列管理器722在接收到写结束确认后，根据所述写结束确认更新队列管理器722的队列计数器，并根据所述写结束确认所包含的元素空间的地址和更新后的队列计数器更新队列管理器722的实尾指针。步骤S74可以包括图1所示的步骤S11至S16，也可以包括图4所示的步骤S41至S48。

步骤S75，接收方72的队列管理器722根据所述写结束确认，向发送方71返回对应的队列消息的确认。

另外，若步骤S74包括图1所示的步骤S11至S16，则所述队列消息的处理方法还可以包括步骤S76，接收方72的队列管理器722在虚尾指针和实尾指针的差值大于或等于预设的最大消息处理量时，丢弃新的队列消息(不发送对应的写请求)，返回队列消息的失败确认给所述新的队列消息的发送方。此步骤为可选的步骤，在其他实施方式中也可以是，接收方72的队列管理器722在虚尾指针和实尾指针的差值大于或等于预设的最大消息处理量时，阻塞新的队列消息直到实尾指针被更新，再向队列所在的存储器721发送对应的写请求。

对应于上述队列消息的处理方法，本实施方式的队列消息的处理系统如图7所示，包括发送方71和接收方72，所述接收方72包括队列存储器721和队列管理器722。

发送方71，向接收方72发送访问接收方72的队列存储器721的队列消息，并接收所述接收方72返回的对应的队列消息的确认。

接收方72的队列存储器721，接收所述队列管理器722发送的写请求，将写请求中的数据写入对应的元素空间，并向所述队列管理器722返回对应的写结束确认。

所述队列管理器722，接收所述发送方71发送的队列消息、向所述队列存储器721发送对应于所述队列消息的写请求、并根据发送的写请求的数量累加虚尾指针，接收所述队列存储器721返回的写结束确认、根据所述写结束确认更新队列计数器、并根据所述写结束确认所包含的元素空间的地址和更新后的队列计数器更新实尾指针，根据所述写结束确认，向发送方71返回对应的队列消息的确认。

所述的队列管理器722可以如图3所示，也可以如图6所示。

综上所述，上述技术方案设置了头指针、虚尾指针、实尾指针和队列计数器，根据接收的写结束确认更新队列计数器，并且根据写结束确认所包含的元素空间的地址和更新后队列计数器更新实尾指针，这样，头指针和实尾指针之间的元素空间为可消费的队列空间；实尾指针和虚尾指针之间的元素空间为不可消费的队列空间。因此，上述技术方案不需要按序执行存储器写请求，也能保证队列尾指针(实尾指针)的更新和数据写入队列的元素空间的同步，因而扩大了队列消息的应用范围。

本发明虽然以较佳实施例公开如上，但其并不是用来限定本发明，任何本领域技术人员在不脱离本发明的精神和范围内，都可以做出可能的变动和修改，因此本发明的保护范围应当以本发明权利要求所界定的范围为准。