使用计数器来跟踪在多个队列中存储的事件的备选到达顺序

摘要

本发明公开了使用计数器来跟踪在多个队列中存储的事件的备选到达顺序的技术。顺序控制器随着在存储时间根据到达顺序计数器设置的单独计数器值在至少两个队列之一中的单独条目中存储每个接收的事件，其中在存储接收的事件中的每个事件之后递增到达顺序计数器并且在溢出时到达顺序计数器绕回到零。顺序控制器计算在随着来自至少两个队列之中的第一队列中的活跃第一接下来条目存储的第一计数器值与随着来自至少两个队列之中的第二队列中的活跃第二接下来条目存储的第二计数器值之间的差值的绝对值。顺序控制器比较绝对值与计数器中点值以确定第一计数器值是否在第二计数器值之前被存储。

说明书

技术领域

本发明的实施例主要地涉及管理队列并且具体地涉及在随着 每个到达事件存储来自计数器的计数器值以指示到达顺序并且随着 每个到达事件递增计数器时跟踪在多个队列中存储的事件的相对到 达顺序，其中计数器在溢出时绕回到零。

背景技术

在处置事件流的电子系统中，经常对一个或者多个队列进行定 位以存储事件直至可以处理事件。在向多个单独队列中存储到达流 的事件时，如果指明有序设置，则可能需要按照事件到达流的相同 顺序从队列处理事件。

发明内容

鉴于前文，需要一种用于在随着每个到达事件存储来自计数器 的计数器值以指示到达顺序并且随着每个到达事件递增计数器时计 算在多个队列中存储的事件的相对到达顺序的方法、系统和计算机 程序产品，其中计数器在溢出时绕回到零。

在一个实施例中，一种用于跟踪在至少两个队列中存储的事件 的相对到达顺序的方法涉及顺序控制器随着在存储时间根据到达顺 序计数器设置的单独计数器值，在来自至少两个队列之一中的多个 条目之中的单独条目中存储每个接收的事件，其中在存储接收的事 件中的每个事件之后递增到达顺序计数器，并且在溢出时到达顺序 计数器绕回到零。该方法还涉及顺序计数器计算在随着来自至少两 个队列之中的第一队列中的多个条目之中的活跃第一接下来条目而 存储的第一计数器值与随着来自至少两个队列之中的第二队列中的 多个条目之中的活跃第二接下来条目而存储的第二计数器值之间的 差值的绝对值。该方法涉及顺序控制器比较绝对值与计数器中点值 以确定第一计数器值是否按照接收的事件的到达顺序在第二计数器 值之前被存储。

在另一实施例中，一种用于跟踪在至少两个队列中存储的事件 的相对到达顺序的系统，包括：在至少一个硬件部件中实施的顺序 控制器，操作用于随着在存储时间根据到达顺序计数器设置的单独 计数器值、在来自至少两个队列之一中的多个条目之中的单独条目 中存储每个接收的事件，其中在存储接收的事件中的每个事件之后 递增到达顺序计数器，并且在溢出时到达顺序计数器绕回到零。顺 序计数器操作用于计算在随着来自至少两个队列之中的第一队列中 的多个条目之中的活跃第一接下来条目而存储的第一计数器值与随 着来自至少两个队列之中的第二队列中的多个条目之中的活跃第二 接下来条目而存储的第二计数器值之间的差值的绝对值。顺序控制 器操作用于比较绝对值与计数器中点值以确定第一计数器值是否按 照接收的事件的到达顺序在第二计数器值之前被存储。

在另一实施例中，一种用于跟踪在至少两个队列中存储的事件 的相对到达顺序的计算机程序产品。该计算机程序产品包括：在一 个或者多个存储设备中的至少一个存储设备上存储的程序指令，用 于随着在存储时间根据到达顺序计数器设置的单独计数器值、在来 自至少两个队列之一中的多个条目之中的单独条目中存储多个接收 的事件中的每个事件，其中在存储多个接收的事件中的每个事件之 后递增到达顺序计数器，并且在溢出时到达顺序计数器绕回到零。 该计算机程序产品包括：在一个或者多个存储设备中的至少一个存 储设备上存储的程序指令，用于计算在随着来自至少两个队列之中 的第一队列中的多个条目之中的活跃第一接下来条目而存储的第一 计数器值与随着来自至少两个队列之中的第二队列中的多个条目之 中的活跃第二接下来条目而存储的第二计数器值之间的差值的绝对 值。该计算机程序产品包括：在一个或者多个存储设备中的至少一 个存储设备上存储的程序指令，用于比较绝对值与计数器中点值以 确定第一计数器值是否在第二计数器值之前被存储。

附图说明

在所附权利要求中阐述被认为是本发明的一个或者多个实施 例的特点的新颖特征。然而在结合附图阅读时参照对示例实施例的 以下具体描述将最好地理解本发明本身的一个或者多个实施例，在 附图中：

图1图示系统的一个示例的框图，在该系统中，对于在多个队 列中存储的事件跟踪相对到达顺序；

图2图示用于多队列接口的顺序控制器的部件的一个示例的 框图，该多队列接口用于处置选择用于到达事件的可用队列并且跟 踪放置于多个队列之一中的事件的相对到达顺序；

图3图示随着每个队列条目而存储的值的一个示例的框图，这 些值包括顺序计数器值和状态位；

图4图示用于多队列接口的顺序控制器的部件的示例的框图， 该多队列接口用于处置按照到达顺序从多个队列中对放置于队列之 一中的待处理的事件的时间选择；

图5A、5B和5C图示顺序控制器的一个示例的框图，该顺序 控制器在随着每个到达事件存储来自计数器的计数器值以指示到达 顺序并且随着每个到达事件递增计数器时跟踪在多个队列中存储的 事件的相对到达顺序，其中计数器在溢出时绕回到零；

图6图示顺序控制器的一个示例的框图的一个示例，该顺序控 制器跟踪在多个队列中存储的事件的相对到达顺序，其中多个连续 的计算的绝对值大于计数器中点值；

图7A-7B图示用于跟踪在多个队列中存储的事件的相对到达 顺序的顺序控制器的一个示例的框图，其中将每个队列的深度设置 成八个条目；

图8图示其中可以实施本发明的一个实施例的计算机系统的 一个示例的框图；

图9图示存储器核控制器的一个示例的框图，该存储器核控制 器包括具有多个队列的队列接口，事件存储于这些队列中并且在这 些队列中跟踪事件的相对到达顺序；

图10图示用于在具有多个队列的队列接口中管理一个或者多 个计数器和一个或者多个指针的过程和程序的高级逻辑流程图，事 件放置于这些队列中并且在这些队列中跟踪事件的相对到达顺序；

图11图示用于在具有多个队列的队列接口中管理传入事件请 求的过程和程序的高级逻辑流程图，事件放置于这些队列中并且在 这些队列中跟踪事件的相对到达顺序；以及

图12图示用于在具有多个队列的队列接口中管理选择待处理 的接下来事件的过程和程序的高级逻辑流程图，事件放置于这些队 列中并且在这些队列中跟踪事件的相对到达顺序。

具体实施方式

在以下描述中，出于说明的目的而阐述许多具体细节以便提供 对本发明的透彻理解。然而本领域技术人员将清楚，没有这些具体 细节仍然可以实现本发明。在其他实例中，在框图形式中示出熟知 结构和设备以免不必要地模糊本发明。

此外，在以下描述中，出于说明的目的而描述许多系统。重要 的是注意并且本领域技术人员将清楚，本发明可以在多种系统中执 行，这些系统包括操作任何数目的不同类型的操作系统的多种计算 机系统和电子设备。

图1图示系统的一个示例的框图，在该系统中，对于在多个队 列中存储的事件跟踪相对到达顺序。

在该示例中，接收接口104从一个或者多个设备接收事件流 102。在该示例中，事件流102可以代表在一个或者多个时间段内从 一个或者多个设备按照特定顺序到达接收接口104的事件流。在该 示例中，接收接口104标识在事件流102中接收的每个事件的一个 或者多个分类并且基于分类从队列接口110中的一个或者多个队列 之中选择与每个事件关联的队列。在一个示例中，接收接口104可 以标识事件流102中的每个事件被分类为读取请求还是写入请求。

在该示例中，队列接口110包括深度为N个条目的队列106 和深度为M个条目的队列108。在一个示例中，在队列106中仅存 储事件流102中被分类为读取请求的事件，并且在队列108中仅存 储事件流102中被分类为写入请求的事件。在其他实施例中，队列 接口110可以包括单个队列或者可以包括附加队列。在一个实施例 中，队列106的深度N个条目等于队列108的深度M个条目。在另 一实施例中，队列106的深度N个条目不等于队列108的深度M个 条目。

在该示例中，顺序控制器112可以向接收接口104、队列接口 110和处理接口114中的一个或者多个接口以及在该一个或者多个 接口之间发送控制信号。在另一实施例中，可以在一个或者多个接 口内实施顺序控制器112中的一个或者多个部件或者可以通过多个 单独的控制器来实施顺序控制器112。

在一个示例中，顺序控制器112控制在接收接口104处在事件 流102中接收的事件被拒绝还是被放置于队列中。此外，顺序控制 器112控制选择非拒绝的事件在队列接口110内放置于其中的特定 队列。另外，顺序控制器112通过随着每个队列中的每个事件在顺 序计数器寄存器中存储顺序计数器值来控制跟踪每个队列中的每个 事件的相对到达顺序，其中计数器值由对于每个事件到达而递增并 且在溢出时绕回到零的到达顺序计数器来设置。此外，在该示例中， 顺序控制器112通过基于向队列106和队列108中的每个接下来活 跃事件条目指派的顺序计数器值而确定顺序计数器值中的哪个顺序 计数器值最旧，来控制从队列106和队列108之中选择接下来活跃 事件以由处理接口114处理，并且标记选择的事件条目为不再活跃。 在一个示例中，顺序控制器112通过计算在向接下来两个活跃事件 指派的顺序计数器值之间的差值的绝对值，并且比较绝对值与计数 器中点值以确定选择随着顺序计数器值中的更小还是更大值存储的 接下来活跃条目，来确定向接下来活跃事件中的每个事件指派的顺 序计数器值中的哪个顺序计数器值是先被存储的、并且因此是最旧 的。具体而言，通过计算在向接下来两个活跃事件指派的顺序计数 器值之间的差值的绝对值并且比较绝对值与计数器中点值以确定哪 个计数器值是先被存储，可以从随着事件存储的顺序计数器值、但 是与顺序计数器值中所示实际序列顺序独立地跟踪接下来两个活跃 事件的到达顺序。

在该示例中，通过计算在向接下来两个活跃事件指派的顺序计 数器值之间的差值的绝对值并且比较绝对值与计数器中点值以确定 选择随着顺序计数器值中的更小还是更大值存储的接下来活跃条 目，可以随着每个事件条目仅存储计数器值以跟踪放置于多个队列 中的事件的相对到达顺序，而无需计数器的溢出的任何附加计数并 且无需更大的计数器。在一个示例中，设置到达顺序计数器以计数 到“2(N+M)-1”，并且将计数器中点值设置成“N+M”，其中N是队列 106中的条目深度并且M是队列108中的条目深度，并且其中如果 绝对值小于计数器中点值则选择用更小顺序计数器值指向的条目。 在另一示例中，可以将到达顺序计数器设置成不同计数、诸如计数 “4(N+M)-1”，并且可以将计数器中点值设置成到达顺序计数器计数 到的值的不同中点、诸如“2(N+M)”。在另一示例中，可以将计数器 中点值设置成在到达顺序计数器的中点的范围内的值。在另一示例 中，在队列接口110包括多于两个队列时，可以实施多个到达顺序 计数器，并且可以设置多个计数器中点值。

图2图示用于多队列接口的顺序控制器的部件的一个示例的 框图，该多队列接口用于处置选择用于到达事件的可用队列并且跟 踪放置于多个队列之一中的事件的相对到达顺序。

在该示例中，顺序控制器112包括用于处置传入事件流的被设 置用于对N个条目进行计数的N条目队列计数器204和被设置用于 对M个条目进行计数的M条目队列计数器206，其中顺序控制器112 使用N条目队列计数器204以对队列106中的活跃条目数目进行计 数并且使用M条目队列计数器206以对队列108中的活跃条目数目 进行计数。

在该示例中，顺序控制器112包括用于处置传入事件流的到达 顺序计数器202。在一个示例中，设置到达顺序计数器202以计数到 等于“2(N+M)-1”的值，其中N是队列106中的条目数目并且M是队 列108中的条目数目。在到达顺序计数器202中的计数溢出时，到 达顺序计数器202绕回到零。在该示例中，可以设置到达顺序计数 器202以计数到备选值。

在该示例中，接收接口控制器210处置事件流102中的传入事 件。在一个示例中，接收接口控制器210通过分类检测器212处置 事件流102中的传入事件，该分类检测器标识用于每个事件的特定 分类并且选择与特定分类关联的队列。在一个示例中，队列状态检 测器214检测来自N条目队列计数器204和M条目队列计数器206 之中的用于选择的队列的条目队列计数器是否指示选择的队列为 满。在该示例中，如果队列状态检测器214检测到选择的队列为满， 则满队列处置器216拒绝传入事件。在一个示例中，队列状态检测 器214通过检查用于选择的队列的条目队列计数器中的计数器值是 否被设置成指示所有条目为活跃并且队列为满的值来高效地检测是 否可以向选择的队列添加传入条目。随着顺序控制器112选择队列 条目用于由处理接口114处理，顺序控制器112减少与处理的条目 所来自的队列关联的条目队列计数器中的计数，从而N条目队列计 数器204和M条目队列计数器206中的每个条目队列计数器中的值 反映每个队列中的活跃条目的当前数目。

在该示例中，如果队列状态检测器214检测到选择的队列未 满，则打开队列处置器218控制向来自队列106和队列108之中的 选择的队列添加传入事件作为条目，而用于该条目的顺序计数器值 被设置成在到达顺序计数器202中设置的当前计数器值，将用于该 条目的状态位设置成“活跃”，递增到达顺序计数器202并且递增来 自N条目队列计数器204和M条目队列计数器206之中的用于选择 的队列的条目队列计数器。在该示例中，通过设置到达顺序计数器 202以向上计数到“2(N+M)-1”并且通过随着顺序计数器值被设置成 到达顺序计数器202中的当前到达顺序计数器值而存储每个事件条 目，随着每个队列中的每个事件条目而存储的顺序计数器值允许顺 序控制器112即使在到达顺序计数器202溢出并且绕回到零时仍然 高效地跟踪队列106和队列108中的每个队列中的每个条目的相对 到达顺序。

图3图示随着每个队列条目存储的值的一个示例的框图，这些 值包括顺序计数器值和状态位。在该示例中，如在标号302所示， 队列106和队列108中的每个队列条目可以包括、但不限于用于存 储事件标识符310的事件寄存器304、用于存储顺序计数器值312 的具有与到达顺序计数器202相同长度的顺序计数器寄存器306和 用于存储一位长度的状态位314的状态位寄存器308。在该示例中， 事件标识符310可以包括一个或者多个属性、诸如事件的开始地址、 事务的大小和字节启用设置。在该示例中，顺序计数器值312可以 包括用于指示到达顺序的在到达时间的到达顺序计数器值。在该示 例中，状态位314可以包括状态位寄存器中设置的状态位，该状态 位用于指示事件未决或者“活跃”，还是已经被处理或者“完成”。在附 加或者备选示例中，如在标号302所示每个队列条目可以包括附加 或者备选数据。

图4图示用于多队列接口的顺序控制器的部件的一个示例的 框图，该多队列接口用于处置按照到达顺序从多个队列中对放置于 队列之一中的待处理的事件的事件选择。

在该示例中，顺序控制器112管理用于队列106和队列108中 的每个队列的单独前指针。在该示例中，前指针402指向队列106 中的条目，并且前指针404指向队列108中的条目。前指针402和 前指针404初始地被设置成零并且指向每个队列中的待处置的接下 来条目。在从队列106和队列108之一向处理接口114释放条目时， 将用于队列的前指针递增一个位置以指向待处置的接下来条目。在 该示例中，如果前指针402或者前指针404中的任一前指针指向条 目并且用于该条目的状态位被设置成“完成”，则在队列中未留下待 处置的条目。

在该示例中，顺序控制器112可以包括用于处置从队列106和 队列108中的事件选择待处理的接下来事件的处理接口控制器404。 在该示例中，如在标号406所示，处理接口控制器404触发队列处 理选择器408以确定待处理的接下来事件。在该示例中，如在标号 406所示，一旦队列处理选择器408选择待处理的事件，处理接口控 制器404释放待处理的选择的事件，将用于选择的事件的条目的状 态位设置成“完成”，递增来自前指针402和前指针404之中的用于 选择的事件队列的前指针，并且递减来自N条目队列计数器204和 M条目队列计数器206之中的选择的事件条目队列计数器。

在该示例中，队列处理选择器408可以包括可用条目检测器 412。可用条目检测器412检查向前指针402和前指针404中的每个 前指针指向的条目指派的状态位。如在标号414所示，如果前指针 402和前指针404二者都指向各自有状态位被设置成“完成”的条目， 则未选择条目用于处理。如在标号416所示，如果前指针402和前 指针404之一指向状态位被设置成“活跃”的条目，则选择状态位被 设置成“活跃”的被指向的条目以用于处理。如在标号418所示，如 果前指针402和前指针404二者各自指向状态位被设置成“活跃”的 条目，则触发绝对差值计算器420。绝对差值计算器420如在标号 422所示计算在第一队列、前指针条目、顺序计数器值与第二队列、 前指针条目、顺序计数器值之间的差值的绝对值。在该示例中，计 算的数字的绝对值是未考虑符号的数字的非负值。例如“1”的绝对值 是“1”并且“-1”的绝对值也是“1”。

在该示例中，绝对差值比较器430比较绝对值与计数器中点 值、诸如“N+M”。如在标号432所示，如果绝对值小于计数器中点 值，则选择具有更小顺序计数器值的前指针条目。如在标号434所 示，如果绝对值大于或者等于计数器中点值，则选择具有更大顺序 计数器值的前指针条目。

图5A、5B和5C图示顺序控制器的一个示例的框图，该顺序 控制器在随着每个到达事件存储来自计数器的计数器值以指示到达 顺序并且随着每个到达事件递增计数器时，跟踪在多个队列中存储 的事件的相对到达顺序，其中计数器在溢出时绕回到零。

在该示例中，如在标号500所示，针对两个队列图示事件流， 其中将N设置成2个条目的深度并且将M设置成2个条目的深度。 在该示例中，如在序列502中所示，到达顺序计数器、第一队列（Q1） 前指针、Q1条目队列计数器、第二队列（Q2）前指针和Q2条目队 列计数器都被设置成“0”。在该示例中，如在队列状态504中所示， Q1和Q2中的每项的前指针指向设置成“0”的条目，该条目是每个队 列中的第一条目，将用于Q1和Q2中的每项中的每个条目的顺序计 数器值设置成“0”，并且将用于Q1和Q2中的每项中的每个条目的状 态位设置成“0”，这是“完成”状态位设置。

在该示例中，指明Q1用于存储分类为“读取”事件的事件，并 且指明Q2用于存储分类为“写入”事件的事件。在该示例中，如在序 列506和队列状态508中所示，事件A到达，该事件被分类为读取 事件并且放置于Q1的第一打开队列条目中，而Q1条目队列计数器 被递增到“1”，事件A顺序计数器值被设置成当前到达顺序计数器值 “0”，并且事件A状态位被设置成“1”。接着如在序列506和队列状 态508中所示，将到达顺序计数器递增到“1”，并且事件B到达，该 事件被分类为写入事件并且放置于Q2的第一打开队列条目中，而 Q2条目队列计数器被递增到“1”，事件B顺序计数器值被设置成当 前到达顺序计数器值“1”并且事件B状态位被设置成“1”。接着如在 序列506和队列状态508中所示，将到达顺序计数器递增到“2”，并 且事件C到达，该事件被分类为读取事件并且放置于Q1的接下来 打开队列条目中，而Q1条目队列计数器被递增到“2”，事件C顺序 计数器值被设置成当前到达顺序计数器值“2”，并且事件C状态位被 设置成“1”。接着如在序列506和队列状态508中所示，将到达顺序 计数器递增到“3”，并且事件D到达，该事件被分类为写入事件并且 放置于Q2的接下来打开队列条目中，而Q2条目队列计数器被递增 到“2”，事件D顺序计数器值被设置成当前到达顺序计数器值“3”， 并且事件D状态位被设置成“1”。接着如在序列506中所示，将到达 顺序计数器递增到“4”。

在该示例中，如在序列510中所示，从均有状态位被设置成“活 跃”的、Q1前指针指向的事件A和Q2前指针指向的事件B之中， 选择处理事件A。具体而言，在该示例中，计算在事件A顺序计数 器“0”与事件B顺序计数器“1”之间的差值的绝对值，该绝对值是“1”。 在该示例中，绝对值“1”小于“N+M”，后者为“4”，因此选择具有更小 顺序计数器的条目用于处理，这是具有顺序计数器“0”的条目A。如 在序列510和队列状态512中所示，将事件A条目状态位设置成“0”， 将Q1条目队列计数器递减到“1”，并且Q1前指针被递增到“1”并且 指向用于事件C的条目。接着如在序列510和队列状态512中所示， 事件E到达，该事件被分类为读取事件并且放置于Q1中的第一打开 条目中，而Q1条目队列计数器被递增到“2”，事件E顺序计数器值 被设置成当前到达顺序计数器值“4”，并且事件E状态位被设置成 “1”。接着如在序列510中所示，将到达顺序计数器递增到“5”。

在该示例中，如在序列514中所示，从均有状态位被设置成“1” 的、Q1前指针指向的事件C和Q2前指针指向的事件B之中，选择 处理事件B。具体而言，在该示例中，计算在事件B顺序计数器“1” 与事件C顺序计数器“2”之间的差值的绝对值，该绝对值是“1”。在 该示例中，绝对值“1”小于“N+M”，后者为“4”，因此选择具有更小顺 序计数器的条目用于处理，这是具有顺序计数器“1”的条目B。如在 序列514和队列状态516中所示，将事件B状态位设置成“0”，将 Q2条目队列计数器递减到“1”，并且Q2前指针被递增到“1”并且指 向用于事件D的条目。接着如在序列514和队列状态516中所示， 事件F到达，该事件被分类为写入事件并且放置于Q2中的第一打开 条目中，而Q2条目队列计数器被递增回到“2”，事件F顺序计数器 值被设置成当前到达顺序计数器值“5”，并且事件F状态位被设置成 “1”。接着如在序列514中所示，将到达顺序计数器递增到“6”。

在该示例中，如在序列518中所示，从均有状态位被设置成“1” 的、Q1前指针指向的事件C和Q2前指针指向的事件D之中，选择 处理事件C。具体而言，在该示例中，计算在事件C顺序计数器“2” 与事件D顺序计数器“3”之间的差值的绝对值，该绝对值是“1”。在 该示例中，绝对值“1”小于“N+M”，后者为“4”，因此选择具有更小顺 序计数器的条目用于处理，这是具有顺序计数器“2”的条目C。如在 序列518和队列状态520中所示，将事件C状态位设置成“0”，将 Q1条目队列计数器递减到“1”，并且Q1前指针被递增并且溢出到 “0”，从而指向用于事件E的条目。接着如在序列518和队列状态520 中所示，事件G到达，该事件被分类为读取事件并且放置于Q1中 的第一打开条目中，而Q1条目队列计数器被递增回到“2”，事件G 顺序计数器值被设置成当前到达顺序计数器值“6”，并且事件G状态 位被设置成“1”。接着如在序列518中所示，将到达顺序计数器递增 到“7”。

在该示例中，如在序列522中所示，从均有状态位被设置成“1” 的、Q1前指针指向的事件E和Q2前指针指向的事件D之中，选择 处理事件D。具体而言，在该示例中，计算在事件D顺序计数器“3” 与事件E顺序计数器“4”之间的差值的绝对值，该绝对值是“1”。在 该示例中，绝对值“1”小于“N+M”，后者为“4”，因此选择具有更小顺 序计数器的条目用于处理，这是具有顺序计数器“3”的条目D。如在 序列522和队列状态524中所示，将Q2条目队列计数器递减到“1”， Q2前指针被递增并且溢出到“0”，从而指向用于事件F的条目。接 着如在序列522和队列状态524中所示，事件H到达，该事件被分 类为写入事件并且放置于Q2中的第一打开条目中，而Q2条目队列 计数器被递增回到“2”，事件H顺序计数器值被设置成当前到达顺序 计数器值“7”，并且事件H状态位被设置成“1”。接着如在序列522 中所示，到达顺序计数器被递增并且溢出到“0”。

在该示例中，如在序列526中所示，从均有状态位被设置成“1” 的、Q1前指针指向的事件E和Q2前指针指向的事件F之中，选择 处理事件E。具体而言，在该示例中，计算在事件E顺序计数器“4” 与事件F顺序计数器“5”之间的差值的绝对值，该绝对值是“1”。在该 示例中，绝对值“1”小于“N+M”，后者为“4”，因此选择具有更小顺序 计数器的条目用于处理，这是具有顺序计数器“4”的条目E。如在序 列526和队列状态528中所示，将Q1条目队列计数器递减到“1”， 并且Q1前指针被递增到“1”，从而指向用于事件G的条目。接着如 在序列526和队列状态528中所示，事件J到达，该事件被分类为 读取事件并且放置于Q1中的第一打开条目中，而Q1条目队列计数 器被递增回到“2”，事件J顺序计数器值被设置成当前到达顺序计数 器值“0”，并且事件J状态位被设置成“1”。接着如在序列526中所示， 将到达顺序计数器递增到“1”。

在该示例中，如在序列530中所示，从均有状态位被设置成“1” 的、Q1前指针指向的事件G和Q2前指针指向的事件F之中，选择 处理事件F。具体而言，在该示例中，计算在事件F顺序计数器“5” 与事件G顺序计数器“6”之间的差值的绝对值，该绝对值是“1”。在 该示例中，绝对值“1”小于“N+M”，后者为“4”，因此选择具有更小顺 序计数器的条目用于处理，这是具有顺序计数器“5”的条目F。如在 序列530和队列状态532中所示，将事件F状态位设置成“0”，将 Q2条目队列计数器递减到“1”，并且Q2前指针被递增到“1”，从而 指向用于事件H的条目。

在该示例中，如在序列534中所示，从均有状态位被设置成“1” 的、Q1前指针指向的事件G和Q2前指针指向的事件H之中，选择 处理事件G。具体而言，在该示例中，计算在事件G顺序计数器“6” 与事件H顺序计数器“7”之间的差值的绝对值，该绝对值是“1”。在 该示例中，绝对值“1”小于“N+M”，后者为“4”，因此选择具有更小顺 序计数器的条目用于处理，这是具有顺序计数器“6”的条目G。如在 序列534和队列状态536中所示，将事件G状态位设置成“0”，将 Q1条目队列计数器递减到“1”，并且Q1前指针被递增并且溢出到 “0”，从而指向用于事件J的条目。

在该示例中，如在序列538中所示，从均有状态位被设置成“1” 的、Q1前指针指向的事件J和Q2前指针指向的事件H之中，选择 处理事件H。具体而言，在该示例中，计算在事件H顺序计数器“7” 与事件J顺序计数器“0”之间的差值的绝对值，该绝对值是“7”。在该 示例中，绝对值“7”大于“N+M”，后者为“4”，因此选择具有更大顺序 计数器的条目用于处理，这是具有顺序计数器“7”的条目H。如在序 列538和队列状态540中所示，将事件H状态位设置成“0”，将Q2 条目队列计数器递减到“0”，并且Q2前指针被递增并且溢出到“0”， 从而指向事件F，该事件已经具有设置成“完成”的状态位。

在该示例中，如在序列542和队列状态544中所示，选择处理 事件J。具体而言，在该示例中，事件J是前指针被设置成状态位、 该状态位被设置成“活跃”的唯一条目，因此选择处理事件J，将用于 事件J的状态位设置成“0”，将Q1条目队列计数器递减到“0”，并且 将Q1前指针递增到“1”。如在队列状态542中所示，Q1前指针和 Q2前指针均指向状态为“0”的条目，因此在Q1和Q2中无条目留待 处理。

图6图示顺序控制器的一个示例的框图，该顺序控制器用于跟 踪在多个队列中存储的事件的相对到达顺序，其中多个连续的计算 的绝对值大于计数器中点值。在该示例中，如在标号600所示，针 对两个队列图示事件流，其中将N设置成2个条目的深度并且将M 设置成2个条目的深度。

在该示例中，如在队列状态602中所示，第一队列（Q1）当 前包括：用于事件A的第一事件条目，而顺序计数器为“6”并且状态 位被设置成“活跃”；以及用于事件B的第二事件条目，而顺序计数 器为“7”并且状态位被设置成“活跃”。此外，如在队列状态602中所 示，第二队列（Q2）当前包括：用于事件C的第一事件条目，而顺 序计数器为“0”并且状态位被设置成“活跃”；以及用于事件D的第二 事件条目，而顺序计数器为“1”并且状态位被设置成“活跃”。在该示 例中，Q1前指针指向用于事件A的在Q1中的第一条目，并且Q2 前指针指向用于事件C的在Q2中的第一条目。

在该示例中，如在序列604中所示，从均有状态位被设置成“活 跃”的事件A和事件C之中，选择接下来处理事件A。具体而言，在 该示例中，计算的绝对值是在事件A顺序计数器“6”与事件C顺序计 数器“0”之间的差值的绝对值，该绝对值是“6”。在该示例中，绝对值 “6”大于“N+M”，后者为“4”，因此选择具有更大顺序计数器的条目用 于处理，这是具有顺序计数器“6”的条目A。在该示例中，如在序列 604中所示，将用于事件A的状态位设置成“完成”，并且将Q1前指 针递增到“1”，从而指向事件B，如在序列状态606中所示。在该示 例中，在队列状态606中，Q1事件指针指向事件B，并且Q2事件 指针指向事件C。

接着在该示例中，如在序列608中所示，从均有状态位被设置 成“活跃”的事件B和事件C之中，选择接下来处理事件B。具体而 言，在该示例中，计算的绝对值是在事件B顺序计数器“7”与事件C 顺序计数器“0”之间的差值的绝对值，该绝对值是“7”。在该示例中， 绝对值“7”大于“N+M”，后者为“4”，因此选择具有更大顺序计数器的 条目用于处理，这是具有顺序计数器“7”的条目B。在该示例中，如 在序列608中所示，将用于事件B的状态位设置成“完成”，并且Q1 前指针被递增并且绕回到“0”，从而指向“完成”的事件A，如在队列 状态610中所示。

接着在该示例中，如在序列612中所示，在Q1前指针和Q2 前指针之中，仅Q2前指针指向状态位被设置成“活跃”的条目，因此 选择Q2前指针指向的事件C用于处理。在该示例中，如在序列612 中所示，将用于事件C的状态位设置成“完成”，并且Q2前指针被递 增到“1”，从而指向事件D，如在队列状态614中所示。在接下来周 期中，由于Q2前指针仍然是指向活跃条目的唯一指针，所以将选择 事件D用于处理，将用于事件D的状态位设置成“0”，并且Q2前指 针将被递增从而绕回到“0”。

图7A-7B图示用于跟踪在多个队列中存储的事件的相对到达 顺序的顺序控制器的一个示例的框图，其中将每个队列的深度设置 成八个条目。在该示例中，如在标号700所示，针对两个队列图示 事件流，其中将N设置成八个条目的深度并且将M设置成八个条目 的深度。在该示例中，设置到达顺序计数器701以计数到上至 “2(N+M)-1”的值——该值是31——并且在溢出时绕回到“0”。

在该示例中，如在序列状态702中所示，第一队列（Q1）当 前包括：用于事件A的第一事件条目，而顺序计数器为“20”并且状 态位被设置成“完成”；用于事件B的第二事件条目，而顺序计数器 为“21”并且状态位被设置成“完成”；用于事件C的第三事件条目， 而顺序计数器为“22”并且状态位被设置成“完成”；用于事件D的第 四事件条目，而顺序计数器为“23”并且状态位被设置成“完成”；用于 事件E的第五事件条目，而顺序计数器为“24”并且状态位被设置成 “完成”；用于事件F的第六事件条目，而顺序计数器为“25”并且状态 位被设置成“完成”；用于事件G的第七事件条目，而顺序计数器为 “26”并且状态位被设置成“完成”；以及用于事件M的第八事件条目， 而顺序计数器为“0”并且状态位被设置成“活跃”。此外，在该示例中， 如在队列状态702中所示，第二队列（Q2）当前包括：用于事件H 的第一事件条目，而顺序计数器为“27”并且状态位被设置成“活跃”； 用于事件I的第二事件条目，而顺序计数器为“28”并且状态位被设置 成“活跃”；用于事件J的第三事件条目，而顺序计数器为“29”并且状 态位被设置成“活跃”；用于事件K的第四事件条目，而顺序计数器 为“30”并且状态位被设置成“活跃”；用于事件L的第五事件条目， 而顺序计数器为“31”并且状态位被设置成“活跃”；用于事件N的第 六事件条目，而顺序计数器为“1”并且状态位被设置成“活跃”；用于 事件O的第七事件条目，而顺序计数器为“2”并且状态位被设置成“活 跃”；以及用于事件P的第八事件条目，而顺序计数器为“3”并且状 态位被设置成“活跃”。

在该示例中，在队列状态702中，Q1事件指针指向事件M， 并且Q2事件指针指向事件H。在该示例中，如在序列704中所示， 从各自有状态位被设置成“活跃”的事件M和事件H之中，选择接下 来处理事件H。具体而言，在该示例中，计算的绝对值是在事件M 顺序计数器“0”与事件H顺序计数器“27”之间的差值的绝对值，该绝 对值是“27”。在该示例中，绝对值“27”大于“N+M”，后者是“4”，因 此选择具有更大顺序计数器的条目用于处理，该条目是具有顺序计 数器“27”的条目H。

类似地，如在标号706、708、710和712所示，将在事件M 之前选择事件I、J、K和L用于处理，因为在每个步骤为指向的顺 序计数器而计算的绝对值大于或者等于计数器中点值“N+M”。作为 序列704、706、708、710和712的结果，队列状态从队列状态702 改变成队列状态714，而Q1前指针仍然指向顺序计数器为“0”的事件 M并且Q2事件指针指向顺序计数器为“1”的事件N。

接着如在序列716中所示，选择处理事件M，因为在事件M 计数器“0”与事件N计数器“1”之间的差值的绝对值是“1”，该值小于 为“16”的“N+M”，因此选择具有更小计数器值的事件或者事件M。 在该示例中，如在序列716和队列状态718中所示，将事件M状态 位设置成“0”，并且Q1前指针被递增并且绕回到0。

接着如在序列720中所示，选择处理事件N，因为事件N是前 指针指向的具有状态位被设置成活跃的唯一事件。在该示例中，如 在序列720和队列状态720中所示，将事件N状态位设置成“0”，并 且Q2前指针被递增到“6”，从而指向事件O。在接下来周期中，由 于Q2前指针仍然是指向活跃条目的唯一前指针，所以将选择事件O 用于处理，将用于事件O的状态位设置成“0”，并且将Q2前指针递 增到“7”。然后在接下来周期中，由于Q2前指针仍然是指向活跃条 目的唯一前指针，所以将选择事件P用于处理，将用于事件P的状 态位设置成“0”，并且Q2前指针将被递增从而绕回到“0”并且未留下 状态位被设置成“1”的剩余条目。

图8图示其中可以实施本发明的一个实施例的计算机系统的 一个示例的框图。可以在由功能部件、诸如参照计算机系统800描 述的功能部件组成并且可以通信地耦合到网络、诸如网络802的多 种系统和系统组合中实现本发明。

计算机系统800包括用于在计算机系统800内传送信息的总线 822或者其他通信设备，以及耦合到总线822用于处理信息的至少一 个硬件处理设备、诸如处理器812。总线822优选地包括由桥接器和 适配器连接并且在计算机系统800内由多个总线控制器控制的低延 时和更高延时路径。在实施为服务器或者节点时，计算机系统800 可以包括被设计用于提高网络服务能力的多个处理器。在多个处理 器共享总线822时，可以实施用于管理总线接入和锁定的附加控制 器（未描绘）。

处理器812可以是至少一个通用处理器、诸如处理器，该至少一个通用处理器在正常操作期间在软件850的控制 之下处理数据，该软件可以包括从动态存储设备如随机存取存储器 （RAM）814、静态存储设备如只读存储器（ROM）816、数据存储 设备如海量存储设备818或者其他数据存储介质可访问的应用软件、 操作系统、中间件以及其他代码和计算机可执行程序中的至少一项。 软件850可以包括但不限于用于控制网络内的一个或者多个系统的 代码、应用、协议、接口和过程，该一个或者多个系统包括但不限 于适配器、交换机、服务器、群集系统和网格环境。

在一个实施例中，处理器812执行的操作可以控制图10-图12 的流程图的操作和这里描述的其他操作。处理器812执行的操作可 以由软件850或者其他代码请求，或者本发明的一个实施例的步骤 可以由包含用于执行步骤的硬接线逻辑的具体硬件部件执行或者由 编程的计算机部件与定制硬件部件的任何组合执行。在一个实施例 中，计算机系统100的一个或者多个部件——该一个或者多个部件 包括但不限于处理器812、RAM814、ROM816、总线822和通信接 口832——或者可以向计算机系统100的一个或者多个部件中集成的 其他部件——该其他部件包括但不限于如图8中所示存储器核控制 器920——可以包含用于实施顺序控制器112、接收接口104、队列 接口110和处理接口114并且用于执行图10-图12的流程图的操作 的硬接线逻辑。

本领域普通技术人员将理解，可以体现本发明的一个实施例的 诸方面为系统、方法或者计算机程序产品。因而，本发明的一个实 施例的诸方面可以采用全硬件实施例、全软件实施例（包括固件、 常驻软件、微代码等）或者包含软件和硬件方面的实施例这样的形 式，这些软件和硬件方面可以都通称为“电路”、“模块”或者“系统”。 另外，本发明的一个实施例的诸方面可以采用在一个或者多个有形 计算机可读介质中体现的计算机程序产品的形式，该一个或者多个 有形计算机可读介质具有在其上体现的计算机可读程序代码。

可以利用一个或者多个计算机可读介质的任何组合。计算机可 读介质可以是计算机可读信号介质或者计算机可读存储介质。计算 机可读存储介质可以例如是但不限于电子、磁、光、电磁、红外线 或者半导体系统、装置、设备或者前述各项的任何适当组合。计算 机可读存储介质的更多具体示例（非穷尽列表）将包括以下各项： 具有一个或者多个接线的电连接、便携计算机盘、硬盘如海量存储 设备818、随机存取存储器（RAM）如RAM814、只读存储器（ROM） 816、可擦除可编程只读存储器（EPROM或者闪存）、光纤、便携 紧致盘只读存储器（CDROM）、光存储设备、磁存储设备或者前述 各项的任何适当组合。在本文的上下文中，计算机可读存储介质可 以是任何可以包含或者存储用于由指令执行系统、装置或者设备使 用或者与指令执行系统、装置或者设备结合使用的程序的有形介质。

计算机可读信号介质可以包括例如在基带中或者作为载波的 一部分的、传播的数据信号，该传播的数据信号具有在其中体现的 计算机可读程序代码。这样的传播的信号可以采用包括但不限于电 磁、光或者其任何适当组合的多种形式中的任何形式。计算机可读 信号介质可以是任何计算机可读介质，该计算机可读介质不是计算 机可读存储介质并且可以传送、传播或者传输用于由指令执行系统、 装置或者设备使用的或者与指令执行系统、装置或者设备结合使用 的程序。

可以使用任何适当介质来传输在计算机可读介质上体现的程 序代码，该介质包括但不限于无线、有线、光纤线缆、射频（RF） 等或者前述各项的任何适当组合。

可以用一种或者多种编程语言的任何组合来编写用于实现本 发明的一个实施例的操作的计算机程序代码，该一种或者多种编程 语言包括诸如Java^TM、Smalltalk、C++等面向对象的编程语言以及诸 如C编程语言或者类似编程语言这样的常规过程编程语言。程序代 码可以完全在用户的计算机、诸如计算机系统800上、部分在用户 的计算机上、作为独立软件包、部分在用户的计算机上而部分在远 程计算机上或者完全在远程计算机或者服务器、诸如服务器840上 执行。在后一种情况下，远程计算机可以通过任何类型的网络如网 络802、通过通信接口如网络接口832、通过可以例如连接到网络802 的网络链路连接到用户的计算机。

在该示例中，网络接口832包括用于通过链路将计算机系统 800连接到网络802并且用于经由网络802将计算机系统800通信地 连接到服务器840或者其他计算系统的适配器834。虽然未描绘，但 是网络接口832可以包括实现通信的附加软件、诸如设备驱动程序、 附加硬件和其他控制器。在实施为服务器时，计算机系统800可以 例如包括经由多个外围部件互连（PCI）总线桥接器可访问的多个通 信接口，这些PCI总线桥接器连接到输入/输出控制器。以这一方式， 计算机系统800允许经由多个单独端口的与多个客户端的连接，并 且每个端口也可以支持与多个客户端的连接。

以下参照根据本发明的实施例的方法、装置（系统）和计算机 程序产品的流程图图示和/或框图描述本发明的一个实施例。本领域 普通技术人员将理解计算机程序指令可以实施流程图图示和/或框图 的每个块和在流程图图示和/或框图中的块组合。可以向通用计算机、 专用计算机或者其他可编程数据处理装置的处理器提供这些计算机 程序指令以产生机器，从而经由计算机或者其他可编程数据处理装 置的处理器执行的指令创建用于实施在流程图和/或框图的一个或者 多个块中指定的功能/动作的装置。

也可以在计算机可读介质中存储这些计算机程序指令，该计算 机可读介质可以引导计算机、诸如计算机系统800或者其他可编程 数据处理装置以特定方式工作，从而在计算机可读介质中存储的指 令产生包括指令装置的制造品，这些指令装置实施在流程图和/或框 图的一个或者多个块中指定的功能/动作。

也可以向计算机、诸如计算机系统800或者其他可编程数据处 理装置上加载计算机程序指令以引起一系列操作步骤在计算机或者 其他可编程装置上执行以产生计算机实施的过程，从而在计算机或 者其他可编程装置上执行的指令提供用于实施在流程图和/或框图的 一个或者多个块中指定的功能/动作的过程。

网络接口832、通向网络802的网络链路和网络802可以使用 输送数字数据流的电、电磁或者光信号。输送去往和来自计算机系 统800的数字信号的、通过各种网络的信号以及在网络802、通向网 络802的网络链路和网络接口832上的信号可以是传送信息的载波 的形式。

此外，计算机系统800可以包括有助于输入和输出的多个外围 部件。这些外围部件连接到多个控制器、适配器和扩展槽、诸如输 入/输出（I/O）接口826，这些控制器、适配器和扩展槽耦合到总线 822的多级之一。例如输入设备824可以例如包括经由I/O接口826 在总线822上通信地启用的控制输入的麦克风、视频捕获设备、图 像扫描系统、键盘、鼠标或者其他输入外围设备。此外，例如经由 I/O接口826在总线822上通信地启用的用于控制输出的输出设备 820可以例如包括一个或者多个图形显示设备、音频扬声器和触觉可 检测输出接口，但是也可以包括其他输出接口。在本发明的备选实 施例中，可以添加附加或者备选输入和输出外围部件。

本领域普通技术人员将理解图8中描绘的硬件可以变化。另 外，本领域普通技术人员将理解描绘的示例不是为了意味着关于本 发明的架构限制。

图9是存储器核控制器的框图的一个示例，该存储器核控制器 包括具有多个队列的队列接口，事件放置在这些队列中并且在这些 队列中跟踪事件的相对到达顺序。

在示例中，系统900包括存储器核控制器920，该存储器核控 制器提供用于将一个或者多个设备、诸如主控设备910、从属设备 912和主控设备914附着和对接到一个或者多个外部存储器芯片924 的机制。在一个示例中，主控设备910、从属设备912和主控设备 914可以包括处理器本地总线（PLB）主控、PLB从属、直接存储器 存取（DMA）主控、DMA从属和I/O主控中的一项或者多项。在该 示例中，仲裁器916与主控设备910、从属设备912和主控设备914 对接并且管理在设备中的每个设备与存储器核控制器920之间的通 信。在该示例中，在设备中的每个设备与存储器核控制器920之间 的通信可以包括具有写入命令和写入数据的写入事件请求以及具有 读取命令和读取数据的读取事件请求。在该示例中，外部存储器接 口922在存储器核控制器920与一个或者多个外部存储器芯片924 之间对接。在一个示例中，外部存储器接口922代表一个或者多个 双数据速率（DDR）、DDR2和DDR3同步动态随机存取存储器 （SDRAM）接口，并且外部存储器芯片924代表一个或者多个DDR SDRAM、DDR2SDRAM和DDR3SDRAM存储器。外部存储器接口 922可以包括驱动器和接收器并且可以与在外部存储器接口922与 外部存储器芯片924之间的时钟缓冲器对接。在附加或者备选示例 中，外部存储器接口922可以代表用于一个或者多个附加或者备选 类型的存储器的一个或者多个接口，并且外部存储器924可以代表 一个或者多个附加或者备选类型的存储器。

在该示例中，存储器核控制器920可以通过管理请求来自外部 存储器924的数据的读取事件和请求向外部存储器924写入数据的 写入事件来提供在主控设备910、从属设备912和主控设备914与外 部存储器芯片924之间的桥接器。在一个示例中，接收器接口104 包括解码器932，该解码器用于从仲裁器916接收命令、标识每个命 令为读取命令还是写入命令并且在读取请求队列938中放置标识的 读取命令而在写入请求队列936中放置标识的写入命令，其中队列 接口110包括读取请求队列938和写入请求队列936。在该示例中， 处理接口114包括用于缓冲来自仲裁器916的写入数据的写入缓冲 器942、用于缓冲将由仲裁器916读取的读取数据的读取缓冲器950、 用于执行用于仲裁器916的写入控制逻辑的写入控制944、用于执行 用于仲裁器916的读取控制逻辑的读取控制946、用于跟踪来自外部 存储器接口922的返回的读取数据的返回读取数据队列948以及用 于与外部存储器接口922对接的存储器接口块952。

在该示例中，存储器芯接口920包括顺序控制器112作为遍及 存储器核控制器920的部件而分布的逻辑，该逻辑用于控制向读取 请求队列938和写入请求队列936中放入从仲裁器916接收的命令 并且用于控制从读取请求队列938和写入请求队列936选择将由外 部存储器接口922接下来处理的命令。在一个示例中，选择并且向 存储器接口块952传递来自读取请求队列和写入请求队列938的接 下来待处理的命令以用于由外部存储器接口922处理。

图10图示用于在具有多个队列的队列接口中管理一个或者多 个计数器和一个或者多个指针的过程和程序的高级逻辑流程图，事 件放置于这些队列中并且在这些队列中跟踪事件的相对到达顺序。 在该示例中，该过程始于块1000并且随后继续到块1002。块1002 图示将每个队列的前指针和条目队列计数器初始化成“0”并且将队 列中的所有状态位设置成“完成”。接着，块1004图示将到达顺序计 数器初始化成“0”。随后，块1006图示确定是否选择来自多个队列 之中的条目用于处理。在块1006，如果未选择条目用于处理，则该 过程传递到块1012。块1012图示确定是否选择序列重置。在块1012， 如果选择序列重置，则该过程返回到块1002并且重置指针和计数器。 在块1012，如果未选择序列重置，则该过程返回到块1006。

返回到块1006，在块1006，如果选择条目用于处理，则该过 程传递到块1008。块1008图示将用于选择的条目的状态位设置成“完 成”。接着，块1010图示递增选择的条目队列中的前指针以指向队 列中的接下来条目，在溢出时绕回到第一条目，并且该过程返回到 块1006。

图11图示用于在具有多个队列的队列接口中管理传入事件请 求的过程和程序的高级逻辑流程图，事件放置于这些队列中并且在 这些队列中跟踪事件的相对到达顺序。在该示例中，该过程始于块 1100并且随后继续到块1102。块1102图示确定是否检测到传入事 件请求。在块1102，如果检测到传入事件请求，则该过程传递到块 1104。块1104图示标识用于传入事件请求的事件特性。接着，块1106 图示确定与事件特性关联的事件队列是否为满。在块1106，如果与 事件特性关联的事件队列为满，则该过程传递到块1108。块1108 图示拒绝传入事件请求，并且该过程结束。

返回到块1106，在块1106，如果与事件特性关联的事件请求 未满，则该过程传递到块1110。块1110图示递增用于选择的队列的 条目队列计数器。随后，块1112图示在选择的事件队列中插入用于 该事件请求的条目。接着，块1114图示将用于此新条目的状态位设 置成“活跃”。随后，块1116图示将用于此新条目的计数器设置成当 前到达顺序计数器值。接着，块1118图示将到达顺序计数器值递增 上至4N-1、然后在溢出时绕回到0，并且该过程结束。

图12图示用于在具有多个队列的队列接口中管理选择待处理 的接下来事件的过程和程序的高级逻辑流程图，事件放置于这些队 列中并且在这些队列中跟踪事件的相对到达顺序。在该示例中，该 过程始于块1200并且随后继续到块1202。块1202图示确定顺序控 制器是否准备好选择待处理的接下来事件。在块1202，如果顺序控 制器准备好选择待处理的接下来事件，则该过程传递到块1204。块 1204图示确定每个队列中的前指针指向的条目是否具有设置成“活 跃”的状态位。在块1204，如果每个队列中的前指针指向的条目具有 设置成“活跃”的状态位，则该过程传递到块1220。块1220图示确定 队列之一中的前指针指向的条目之一是否具有设置成“活跃”的状态 位。在块1220，如果队列之一中的前指针指向的条目中仅一个条目 具有设置成“活跃”的状态位，则该过程传递到块1224。块1224图示 选择来自状态位被设置成“活跃”的被指向的条目的事件作为待处理 的接下来事件，并且该过程结束。返回到块1220，在块1220，如果 队列中的前指针指向的条目都无设置成“活跃”的状态位，则该过程 传递到块1222。块1222图示设置在队列中无未决事件的指示符，并 且该过程结束。

返回到块1204，如果每个队列中的前指针指向的条目具有设 置成“活跃”的状态位，则该过程传递到块1206。块1206图示计算在 第一队列前指针指向的第一顺序计数器值与第二队列前指针指向的 第二顺序计数器之间的差值的绝对值。接着，块1208图示确定绝对 值是否小于“N+M”。在块1208，如果绝对值小于“N+M”，则该过程 传递到块1210。块1210图示选择来自具有更小值的顺序计数器的、 所指向的条目的事件，并且该过程继续到块1214。返回到块1208， 如果绝对值不小于“N+M”，则该过程传递到块1212。块1212图示选 择来自具有更大值的顺序计数器的、所指向的条目的事件，并且该 过程继续到块1214。

块1214图示将用于选择的条目的状态位设置成“完成”。接着， 块1216图示递增用于选择的事件队列的队列指针。随后，块1218 图示递减用于选择的事件队列的条目队列计数器，并且该过程结束。

图中的流程图和框图举例说明根据本发明的各种实施例的系 统、方法和计算机程序产品的可能实现方式的架构、功能和操作。 就这一点而言，在流程图或者框图中的每个块可以代表代码模块、 段或者部分，该代码模块、段或者部分包括用于实施指定的逻辑功 能的一个或者多个可执行指令。也应当注意在一些备选实现方式中， 在块中指出的功能可以不按图中指出的顺序出现。例如事实上根据 涉及到的功能可以基本上并行执行接连示出的两个块或者有时可以 按相反顺序执行这些块。也将注意框图和/或流程图图示的每个块以 及在框图和/或流程图图示中的块组合可以由执行指定的功能或者动 作的基于专用硬件的系统实施或者由专用硬件与计算机指令的组合 实施。

这里所用术语仅为了描述具体实施例而未旨在于限制本发明。 如这里所用，除非上下文另有明示，单数形式“一个”和“该”旨在于也 包括复数形式。还将理解术语“包括”在说明书中使用时指定存在陈 述的特征、整件、步骤、操作、单元和/或部件、但是未排除存在或 者添加一个或者多个其他特征、整件、步骤、操作、单元、部件和/ 或其组合。

所附权利要求中的所有装置或者步骤加上功能要素的对应结 构、材料、动作和等效物旨在于包括用于与如具体要求保护的其他 权利要求要素组合执行该功能的任何结构、材料或者动作。已经出 于示例和描述的目的而呈现本发明的一个或者多个实施例的描述， 但是该描述未旨在于穷举本发明或者使本发明限于公开的实施例。 许多修改和变化将为本领域普通技术人员所清楚而未脱离本发明的 范围和精神实质。选择和描述实施例以便最好地说明本发明的原理 和实际应用并且使本领域其他普通技术人员能够对于具有如与设想 的特定使用相配的各种修改的各种实施例理解本发明。

尽管已经参照一个或者多个实施例具体示出和描述本发明，但 是本领域技术人员将理解可以在其中进行形式和细节上的各种改变 而未脱离本发明的精神实质和范围。