不使用原子指令而适当处理大量处理器的读复制更新的宽限期检测方法和装置

摘要

本发明公开一种在要求延迟移除共享的数据元素直到先存在的对数据元素的引用被移除的读复制更新的子系统或其它处理环境中不使用原子指令而进行宽限期的检测的方法、系统和计算机程序产品。宽限期的检测包括建立在共享对所述数据元素的访问的处理实体间循环的令牌。无论何时令牌在处理实体间往返，宽限期都消逝。与每一个处理实体相关联的分布式的指示器指示是否需要在任何共享的数据元素上执行移除处理。在后面的参与令牌处理之前，处理在每一个处理实体处的分布式的指示器。仅当由分布式的指示器保证时，执行令牌处理。这样，当分布式的指示器未保证此处理时，可以避免不必要的令牌处理。

权利要求

1.一种用于检测用于延迟移除共享的数据元素直到先存在的对数据元素的引用被移除的宽限期的方法，包括：建立在共享对所述数据元素的访问的处理器间循环的令牌；

当所述令牌在所述处理器间往返时，确定所述宽限期已经结束；

将分布式的指示器与每一个所述处理器联系在一起，该指示器指示是否需要在所述数据元素或由所述处理器所共享的其它数据元素上执行移除处理；

在参与所述处理器处的令牌处理之前，处理在每一个所述处理器处的所述分布式的指示器；和仅当由所述分布式的指示器批准令牌处理时，执行所述处理器处的令牌处理；

从而当所述分布式的指示器未批准令牌处理时，避免不必要的令牌处理。

2.如权利要求1所述的方法，其中每一个所述分布式的指示器被作为局部变量存储在与所述处理器中的一个相关联的缓冲存储器中。

3.如权利要求1所述的方法，其中分布式的指示器进一步表示那些具有移除由所述处理器所共享的数据元素的未决请求的所述处理器的数目或移除由所述处理器所共享的数据元素的未决请求的数目。

4.如权利要求1、2或3所述的方法，其中所述分布式的指示器进一步表示识别具有移除由所述处理器所共享的数据元素的未决请求的所述处理器的位图。

5.如权利要求1所述的方法，其中在一个所述处理器处对一个所述分布式的指示器所产生的改变被传播至其它所述处理器。

6.如权利要求1所述的方法，其中第一所述处理器处的一个所述分布式的指示器的数值，反映在根据反映在所述第一处理器处的数据元素移除请求活动的需要而调整的相邻的第二所述处理器处的第二所述分布式的指示器的数值。

7.如权利要求1所述的方法，其中对所述分布式的指示器的所述处理包括确定在一个所述处理器处是否有未决的数据元素移除的请求的阈值数量以保证所述令牌的循环，或者，确定在一个所述处理器处是否有任何未决的数据元素移除的请求。

8.如权利要求1所述的方法，其中所述的方法作为读复制更新互斥技术的部分而实现，通过登记在所述处理器处的回调实现所述数据元素的移除，并且，所述分布式的指示器是反映读复制更新的子系统中的回调活动的分布式的回调指示器。

9.一种具有一个或多个处理器、存储器和一个或多个处理器与存储器间的通信路径的数据处理系统，适于用于延迟由一个所述处理器进行的对共享的数据元素的移除直到先存在的对由其它所述处理器所保持的数据元素的引用被移除的宽限期的检测，还包括：用于在所述处理器间循环令牌的装置；

与每一个所述处理器相关联的令牌操纵器，适于循环所述令牌和依靠在所述处理器间往返的所述令牌来确定所述宽限期是否已经结束；

与每一个所述处理器相关联的分布式的指示器，该指示器指示是否需要在所述数据元素或由所述处理器所共享的其它数据元素上执行移除处理；

与每一个所述处理器相关联的分布式的指示器的处理装置，适于在由所述令牌操纵器进行令牌处理之前处理所述分布式的指示器；和所述分布式的指示器的处理装置，还适于允许所述令牌操纵器只有当由所述分布式的指示器批准令牌处理时在所述处理器处执行令牌处理；

从而当所述分布式的指示器未批准令牌处理时，避免不必要的令牌处理。

10.一种用于检测用于延迟移除共享的数据元素直到先存在的对数据元素的引用被移除的宽限期的设备，包括：建立在共享对所述数据元素的访问的处理器间循环的令牌的装置；

当所述令牌在所述处理器间往返时，确定所述宽限期已经结束的装置；

将分布式的指示器与每一个所述处理器联系在一起的装置，该指示器指示是否需要在所述数据元素或由所述处理器所共享的其它数据元素上执行移除处理；

在参与所述处理器处的令牌处理之前，处理在每一个所述处理器处的所述分布式的指示器的装置；和仅当由所述分布式的指示器批准令牌处理时，执行所述处理器处的令牌处理的装置；

从而当所述分布式的指示器未批准令牌处理时，避免不必要的令牌处理。

11.一种用于检测读复制更新的子系统中的宽限期以确定何时执行未决的回调的方法，包括：在共享对数据元素的访问的处理器集的每一个处理器处实现静态计数器；

建立作为由所述静态计数器所保持的计数数值的突变的宽限期令牌；

当所述令牌在所述处理器集间往返从而返回一个所述处理器时，确定在所述的一个所述处理器处的所述宽限期已经结束；

将作为在相关缓冲存储器中的局部变量的分布式的回调指示器与每一个所述处理器相关联，该指示器指示是否需要处理所述回调；

在参与所述处理器处的令牌处理之前，处理在每一个所述处理器处的所述分布式的回调指示器；和仅当由所述分布式的回调指示器批准令牌处理时，执行所述处理器处的令牌处理；

从而当所述分布式的回调指示器未批准令牌处理时，避免不必要的令牌处理。

12.一种用于检测用于延迟移除共享的数据元素直到先存在的对数据元素的引用被移除的宽限期的方法，包括：建立在共享对所述数据元素的访问的处理器间循环的令牌；

当所述令牌在所述处理器间往返时，确定所述宽限期已经结束；

将分布式的指示器与每一个所述处理器联系在一起，该指示器表示那些具有移除由所述处理器所共享的数据元素的未决请求的所述处理器的数目；

在参与所述处理器处的令牌处理之前，处理在每一个所述处理器处的所述分布式的指示器；

对所述分布式的指示器的所述处理包括在相邻的一个所述处理器处根据所述分布式的指示器的数值修改所述分布式的指示器，以及根据下列内容对所述数值的修改，(1)是否有与当前宽限期相关联的移除请求而没有与先前的宽限期相关联的移除请求，在有与当前宽限期相关联的移除请求而没有与先前的宽限期相关联的移除请求的情况下增加分布式的指示器，或(2)是否没有与当前宽限期相关联的移除请求而有与先前的宽限期相关联的移除请求，在没有与当前宽限期相关联的移除请求而有与先前的宽限期相关联的移除请求的情况下减少分布式的指示器，或(3)是否有与当前和先前的宽限期都关联的移除请求，或既没有与当前的宽限期关联的移除请求也没有和先前的宽限期关联的移除请求，在有与当前和先前的宽限期都关联的移除请求，或既没有与当前的宽限期关联的移除请求也没有和先前的宽限期关联的移除请求的情况下分布式的指示器保持不变；和仅当由所述分布式的指示器批准令牌处理时，执行所述处理器处的令牌处理；

从而当所述分布式的指示器未批准令牌处理时，避免不必要的令牌处理。

13.一种用于检测用于延迟移除共享的数据元素直到先存在的对数据元素的引用被移除的宽限期的方法，包括：建立在共享对所述数据元素的访问的处理器间循环的令牌；

当所述令牌在所述处理器间往返时，确定所述宽限期已经结束；

将分布式的指示器与每一个所述处理器联系在一起，该指示器表示移除由所述处理器所共享的数据元素的未决请求的总数；

在参与所述处理器处的令牌处理之前，处理在每一个所述处理器处的所述分布式的指示器；

对所述分布式的指示器的所述处理包括在相邻的一个所述处理器处根据所述分布式的指示器的数值修改所述分布式的指示器，以及根据在当前宽限期期间添加的移除请求的数目与在先前的宽限期期间处理的移除请求的数目之间的差别对所述数值进行的修改；和仅当由所述分布式的指示器批准令牌处理时，执行所述处理器处的令牌处理；

从而当所述分布式的指示器未批准令牌处理时，避免不必要的令牌处理。

14.一种用于检测用于延迟移除共享的数据元素直到先存在的对数据元素的引用被移除的宽限期的方法，包括：建立在共享对所述数据元素的访问的处理器间循环的令牌；

当所述令牌在所述处理器间往返时，确定所述宽限期已经结束；

将分布式的指示器与每一个所述处理器联系在一起，该指示器表示那些具有移除由所述处理器所共享的数据元素的未决请求的所述处理器的位图；

在参与所述处理器处的令牌处理之前，处理在每一个所述处理器处的所述分布式的指示器；

对所述分布式的指示器的所述处理包括在相邻的一个所述处理器处根据所述分布式的指示器的数值修改所述分布式的指示器，以及根据下列内容设置与评估的处理器相对应的位，(1)是否有与当前宽限期相关联的移除请求，在有与当前宽限期相关联的移除请求的情况下将该位设为1，或(2)是否没有与当前宽限期相关联的移除请求，在没有与当前宽限期相关联的移除请求的情况下将该位设为0；和仅当由所述分布式的指示器批准令牌处理时，执行所述处理器处的令牌处理；

从而当所述分布式的指示器未批准令牌处理时，避免不必要的令牌处理。

说明书

技术领域

本发明涉及计算机系统和方法，其中数据资源在相对于每一个数据使用者保留数据的完整性和一致性的同时由并行的数据使用者共享。更特别的，本发明涉及对称为“读复制更新”的互斥机制的改进，该机制中，无锁的数据读取操作与数据更新操作并行运行。

背景技术

作为背景技术，读复制更新是一互斥技术，它不使用锁、不对共享存储器进行写入、不需要内存栅、不使用原子指令或其它计算昂贵的同步机制，而允许对共享数据进行读取访问，同时还允许数据被更新(修改、删除、插入等等)。该技术特别适合于多处理器计算环境，其中访问共享数据集的读操作(读取器)的数目相比较而言大于更新操作(更新器)的数目，并且其中对每一个读取操作来说使用其它互斥技术(如锁)的开销会高。作为例子，在网络路由表至多每几分钟更新一次但每一秒却被检索数千次这样的情形下，读取端的锁捕获会相当繁重。
读复制更新技术在两个阶段中实现数据更新。在第一阶段(初始更新)中，实际的数据更新以暂时保留正被更新的数据的两个视图的方式来完成。一个视图是旧的(更新前)数据状态，为利于当前可能正在引用数据的操作而保持该旧的数据状态。另一个视图是新的(更新后)数据状态，为利于在更新后对数据进行访问操作，该数据状态是可用的。在第二个阶段(延迟更新)中，旧的数据状态在“宽限期”后被移除，该宽限期足够长以保证所有的正在执行的操作不再保持对更新前的数据的引用。
图1A-1D示出了使用读复制更新修改数据元素A、B和C的组中的数据元素B。数据元素A、B和C排在以非循环的方式遍历的单向链表中，除了存储一些数据项，其中每一个元素包括指向链表中下一个元素的指针(或对最后的元素为NULL指针)。假定全局指针(未显示)指向表的第一个成员-数据元素A。本领域的技术人员将认识到数据元素A、B和C可以使用多个传统的程序构件的任何一个而实现，这些程序构件包括但不仅限于由C语言“结构体”变量所定义的数据结构。
假设图1A-1D中的数据元素表由多个并行读取器遍历(不锁定)，并且偶尔由那些删除、插入或修改表中的数据元素的更新器更新.图1A中，如数据元素下面的垂直箭头所示，数据元素B正被读取器r1引用.图1B中，更新器u1希望通过修改数据元素B来更新链表.在产生更新后的数据元素的版本(如图1C中所示的数据元素B’)并将其插入到链表中的同时，u1保留B，而不是不考虑r1正在引用它而简单地更新数据元素(这可能破坏r1).这是通过u1获得自旋锁、为B’分配新的存储空间、复制B的内容到B’、如果需要的话修改B’、更新从A到B的指针以使其指向B’以及释放该自旋锁来完成的.所有随后(更新后)的遍历链表的读取器，如读取器r2，将因此通过遍历到B’看到更新操作的效果.另一方面，旧的读取器r1将是未受影响的，因为B的原始版本及其指向C的指针是保留的.尽管r1现在将读取陈旧的数据，但在许多情形中这是可以容忍的，如当数据元素跟踪计算机系统外部的成分的状态(如网络连通性)以及由于通信延迟必须容忍旧的数据的时候.
在更新之后的一些随后时间里，r1将继续它对链表的遍历并除去它对B的引用。此外，将有一时间没有其它的读取器过程有权访问B。如图1D所示，正是在这一点上，代表以上提及的宽限期的期满，u1可以释放B。
图2A-2C示出了使用读复制更新删除数据元素A、B和C的单向链表中的数据元素B。如图2A所示，假定读取器r1当前正引用B并且更新器u1希望删除数据元素B。如图2B所示，更新器u1更新从A到B的指针，这样现在A指向C。这样，r1未被扰乱，但随后的读取器r2看到了删除的效果。如图2C所示，随后r1将除去它对B的引用，允许B在宽限期期满后被释放。
在读复制更新机制的语境中，宽限期代表某一点，在此所有有途经访问使用读复制更新所保护的数据元素的运行进程都经过了“静态”，在“静态”中它们不再保持对数据元素的引用、在其上发布锁或对数据元素的状态做出任何假设。相反地，对操作系统内核代码路径来说，对任何特定的CPU，语境(进程)切换、空循环和用户模式执行都代表静态(如其它操作能做的那样，将不在此处列出)。
在图3中，显示了运行在四个独立的CPU上的四个进程0、1、2和3周期性地经过静态(由双竖条表示)。宽限期(由点竖条表示)包括某时间帧，该时间帧中所有的四个进程经过一个静态。如果四个进程0、1、2和3是遍历图1A-1D或图2A-2C中的链表的读取器进程，则这些在宽限期之前引用旧的数据元素B的进程中没有一个能够在宽限期之后仍保持引用数据元素B。通过跟随由更新器所插入的链接，所有的宽限期后的、由这些进程所引导的检索会绕过B。
可使用多种方法来实现在宽限期之后的延迟的数据更新，包括但不仅限于使用如共同受让的标题为“Apparatus And Method ForAchieving Reduced Overhead Mutual-Exclusion And MaintainingCoherency In A Multiprocessor System Utilizing Execution History AndThread Monitoring”的美国专利5727209所描述的回调处理。美国专利5727209的内容据此在这里通过参考并入本说明书。
回调处理技术希望共享的数据元素的更新器将执行创建正被更新的数据的新的视图的初始(第一阶段)数据更新操作，并接着指定执行移除正被更新的数据的旧的视图的延迟(第二阶段)数据更新操作的回调函数。更新器将利用读复制更新子系统登记该回调函数(下文中称之为“回调”)，这样可以在宽限期结束时执行它。为检测每一个处理器的当前宽限期何时期满，读复制更新子系统为每一个处理器保持对未决的回调的跟踪，并监视每一处理器的静态的活动。当每一个宽限期期满时，执行所有对处理来说时机成熟的预定的回调。
读复制更新的成功实现要求有效的机制以推导出宽限期的长度.一类重要的实现将宽限期令牌从一个处理器传递到下一个，以表示对拥有该令牌的处理器来说已经到达了宽限期的尽头.该宽限期令牌可以是在处理器之间明白地传递的特异值.然而，当使用这个技术时要求两个存储器写入访问-一个从其当前拥有者处移除令牌而另一个将该令牌传递给其新的拥有者.一个处理宽限期令牌的更有效的方法是使用每一处理器的静态计数器和相关联的轮询机制暗中地传递它.根据这个技术，无论何时处理器经过静态，它的轮询机制都检查相邻的处理器的静态计数器以了解相邻的计数器在当前处理器的最后的宽限期后是否改变过.如果改变过，则当前处理器确定自从它最后拥有该令牌后新的宽限期已经结束.它执行其未决的回调并接着改变其静态计数器至比其邻居更高的数值.接着，下一个处理器看到这个处理器改变了计数器的数值，处理其未决的回调，并提高其自身的计数器.这个次序继续，由宽限期令牌以轮转的方式最终一路向前通过所有的处理器.
不考虑宽限期令牌是怎样实现的，当每一个处理器接收到令牌时它仅仅处理回调。在一定程度上讲，宽限期令牌在到达作为当前持有者的处理器之前必须通过所有其它的处理器，当前处理器通常被保证其它处理器自从当前处理器最后拥有该令牌后已经经过静态，这样确保宽限期已经结束。
当处理器经过其静态时，使用令牌操纵的宽限期检测消耗处理器周期，因此不希望出现这种开销，除非在读复制更新子系统中有未决的回调。出于该原因，有效的基于令牌的读复制更新的实现使用共享指示器(即全局变量)，该指示器在宽限期令牌处理之前被测试以确定读复制更新子系统是否空闲。如果是的话，不需要传递宽限期令牌，并且可以避免相关联的处理开销。典型地，共享指示器是未决的回调的数目的计数。无论何时在给定的处理器处登记回调，都操纵共享指示器以反映新的回调。其后，当处理了那个回调时，再次操纵共享指示器以反映回调从读复制更新子系统处被删除。
使用共享指示器测试未决的回调的存在性的一个缺点是每一次操纵共享指示器时原子指令、锁或其它相对昂贵的互斥机制都必须被调用以用多处理器对指示器进行同步操作。而且，每一个处理器传统的共享指示器的硬件缓存易于导致通信缓存错误和缓冲线弹回。在位图指示器的情况下，另一个缺点是不能从容地适应大量处理器。
解决前述的问题是本发明的目的。特别地，所需要的是新的读复制更新的宽限期的检测技术，该技术避免不必要的宽限期令牌处理，且没有招致对未决的回调的状况的共享指示器的管理开销。

发明内容

在要求延迟移除共享的数据元素直到先存在的对数据元素的引用被移除的读复制更新的子系统或其它处理环境中，利用不使用原子指令而进行宽限期的检测的方法、系统和计算机程序产品，解决前述问题并获得技术上的进步。宽限期检测包括建立在共享对共享的数据元素的访问的处理实体间循环的令牌。无论何时令牌在处理实体间往返，都可以确定宽限期结束。分布式的指示器与每一个处理实体相关联，该指示器指示是否需要在数据元素或其它由处理实体所共享的数据元素上执行移除处理(例如，如果本发明在基于回调的读复制更新系统中实现，指示是否有保证回调处理的未决的回调)。在处理实体处参与令牌处理之前，在每一个处理实体处处理分布式的指示器。仅当由分布式的指示器批准令牌处理时，才在处理实体处执行令牌处理。这样，当分布式的指示器未批准此处理时，可以避免不必要的令牌处理。
在本发明的示例实施例中，分布式的指示器被作为局部变量存储在与处理实体相关联的缓冲存储器中(并在经由传统的缓存一致性机制的处理的过程中从一个缓冲存储器复制到另一个中).在此实施例中，分布式的指示器可表示依赖于设计偏好的不同种类的信息.例如，分布式的指示器也可表示那些具有执行对处理实体所共享的数据元素的更新的未决请求的处理实体的数目、更新的总数，或者识别具有未决的更新请求的处理实体的位图.
根据设计偏好，由各种处理实体所产生的对分布式的指示器的改变的传播，也可以以不同的方法执行。在具体实施例中，处理实体周期性地咨询相邻的处理实体所保持的分布式的指示器，并根据反映在当前处理实体处数据元素移除的请求活动中的改变(如回调登记)的需要来调整指示器。在数据元素移除的请求活动中是否有改变可以包括多种因素的确定，如在一个处理实体处是否有未决的数据元素移除的请求的数量阈值以保证令牌的循环。或者，此确定可以基于在一个处理实体处是否有任何未决的数据元素移除的请求。

附图说明

如下列附图所示，本发明的前述的以及其它特征和优点将由下面对本发明的示例实施例的更为具体的描述而变得明显，附图中：
图1A-1D是根据传统的读复制更新机制经历数据元素替换的数据元素的链表的图示；
图2A-2C是根据传统的读复制更新机制经历数据元素删除的数据元素的链表的图示；
图3是示例说明其中的四个进程经过一个静态的宽限期流程图；
图4是显示表示一个在其中可以实现本发明的示例实施例的多处理器计算系统的功能块框图；
图5是显示由图4的多处理器计算机系统中的每个处理器所实现的读复制更新的子系统的功能块框图；
图6是显示与图4的多处理器计算机系统中的每个处理器相关联的缓冲存储器的功能块框图；
图7是显示在假定的实现读复制更新的四处理器数据处理系统中示例的静态计数器的数值的表格；
图8是显示在读复制更新处理期间当图7的四个处理器不时地传递宽限期令牌时该四个处理器的功能块框图；
图9是显示分布式的回调指示器的操纵的流程图，该指示器作为具有未决的回调的处理器的计数而实现；
图10是显示在实现读复制更新的假定的四处理器数据处理系统中具体的静态计数器的数值和分布式的回调指示器的数值的表格；
图11是显示在处理读复制更新期间当图10的四个处理器不时地传递宽限期令牌时该四个处理器的功能块框图；
图12是表示图9的流程图的修改的流程图；
图13是显示分布式的回调指示器的操纵的流程图，该指示器作为未决的回调的计数而实现；
图14是显示分布式的回调指示器的操纵的流程图，该指示器作为识别具有未决的回调的处理器的位图而实现；和
图15是示例说明根据本发明可用来存储计算机程序产品以实现读复制更新的周期检测功能的存储介质的示图。

具体实施方式

现在参照这些图，在所有的几个视图中，相似附图标记代表相似的元素，图4说明示例的计算环境，在其中可以实现本发明。特别地，图4显示了对称式多处理器(SMP)计算系统2，其中多处理器41、42...4n通过公用总线6连接至共享存储器8。分别与每个处理器41、42...4n相关联的是传统的缓冲存储器101、102...10n和缓存控制器121、122...12n。传统的存储器控制器14与共享存储器8相关联。假定计算系统2受适用于SMP环境的单个多任务操作系统的管理。
进一步假定在内核或用户模式进程、线程或者在存储于共享存储器8中的共享数据集16上将周期性地执行更新的其它执行文本的内部执行更新操作。附图标记181、182...18n说明单独的数据更新操作(更新器)，该操作可以周期性在多个处理器41、42...4n上执行。如上文的背景技术介绍所述，由数据更新器181、182...18n所执行的更新可以包括修改链表的元素、插入新的元素到表中、从表中删除元素以及许多其它类型的操作。为便于这些更新，由于通过周期性地执行作为它们操作系统功能的部分的各自的读复制更新的实例201、202...20n，多个处理器41、42...4n被编程以实现读复制更新(RCU)子系统20。虽然没有在图中显示，可以想到处理器41、42...4n在共享数据集16上也执行读取操作。典型地，在作为读复制更新的使用下的一个前提的情况下，这些读取操作将远比更新执行得更频繁。
如图5所示，每一个读复制更新的子系统的实例201、202...20n包括回调登记构件22。回调登记构件22用作可由更新器181、182...18n调用的读复制更新的子系统20的API(应用程序接口)，为由更新器自身所执行的初始(第一阶段)的更新之后的延迟(第二阶段)的数据元素更新的请求进行登记。如本领域人员所知道的那样，这些延迟更新的请求包括移除过期的数据元素，并且在读复制更新的子系统20的内部将被作为回调来处理。每一个读复制更新的子系统20的实例201、202...20n还包括静态计数器的操纵和轮询机制24(或用于传递令牌的其它功能)，以及回调处理系统26。注意，按惯例，功能24和26可以作为内核调度器的部分而实现。
与处理器41、42...4n相关的缓冲存储器101、102...10n分别存储静态计数器281、282...28n和一个或多个回调队列301、302...30n。出于在处理器41、42...4n中传递宽限期令牌的目的，静态计数器281、282...28n由计数器的操纵和轮询机制24(令牌操纵器)管理。可以想到如果使用一些其它形式的令牌传递，则静态计数器281、282...28n将不是必需的。用像回调登记构件22所登记的回调那样的新的回调对回调队列301、302...30n进行添加(或前插)。回调处理系统26负责执行在回调队列301、302...30n上所引用的回调，并接着在处理该回调后移除之。
图7和8说明了当处理器经过静态时静态计数器281、282...28n是怎样被用来在示例的四处理器系统中的处理器之间传递宽限期令牌的。图7中的每一列显示了在给定的时间点上所有处理器静态计数器的示例数值。带有阴影的单元格象征相对应的处理器是宽限期令牌的所有者。在每一情况下，所有者是某一处理器，该处理器的计数器具有最小数值，而且该处理器的邻居具有表示相对于令牌所有者的计数器数值的突变的计数器数值。
图7和8所表示的令牌传递技术为本领域人员所知，并且因此这些图被标注为“现有技术”.如上文的背景技术所述，通过参考一个邻居(如，以处理器号为模(％)，处理器号比当前处理器号大一的那个处理器)所保持的静态计数器，给定的处理器进行核对以了解它是否拥有宽限期令牌.如果自从当前处理器的最后的宽限期以来该邻居的静态计数器未发生改变(即计数器数值没有突变)，则当前处理器确定新的宽限期还没有结束并继续常规处理.如果自从当前处理器的最后的宽限期以来该邻居的静态计数器发生了改变(即计数器数值有突变)，则当前处理器确定新的宽限期已经结束.它处理其未决的回调并增加其自身的静态计数器值到比邻居的数值大一，由此将计数器值中的突变移至自身.当作例子，图7中在t＝0时，具有最低静态计数器数值(1)的处理器3看到了在处理器0处的突变计数器值(4).对处理器3来说，这意味着自从处理器3的最后的宽限期后由与其同等的处理器经历了三个(4-1)静态.处理器3因此断定新的宽限期已经结束且它现在已经拥有了宽限期令牌.它执行回调处理并将其静态计数器的数值设为4+1＝5.在t＝1时，具有静态计数器的数值为2的处理器2看到了在处理器0处的不连续的计数器数值5.它断定它现在已经拥有了宽限期令牌，执行回调处理并将其计数器数值设为5+1＝6.继续这个顺序，在t＝2时处理器1获得宽限期令牌，而在t＝3时处理器0获得令牌.在t＝4时，令牌返回到处理器3，并如此重演.此外，如图8所示，处理器3将在t＝0、4和8时获得令牌(T)，处理器2将在t＝1和5时获得令牌，处理器1将在t＝2和6时获得令牌，处理器0将在t＝3和7时获得令牌.
又如上文的背景技术所述，现有技术的读复制更新的实现通过操纵某一全局变量来寻求避免不必要的令牌处理，该全局变量用作在需要处理的读复制更新的子系统中指示是否有未决的回调的共享指示器。例如，如P.McKenney等人在“Read Copy Update(读复制更新)”Ottawa Linux论坛(2002)上所公开的那样，被称为“rcu-sched”的读复制更新的Linux实现使用表示读复制更新的子系统中的未决的回调的数目的计数的共享变量“rcu_pending”。当通过函数调用“atomic_inc(&rcu_pending)”登记新的回调时，调用Linux原子增加基元“atomic_inc”以增加rcu_pending。接着，在通过函数调用“atomic_dec(&rcu_pending)”处理回调后，调用Linux原子减少基元“atomic_dec”以减少rcu_pending。还应该指出，rcu-sched是使用如图7和8所示的基于计数器的宽限期令牌传递方案的读复制更新的实现的例子。
为了避免与使用原子操作去增加和减少回调未决的共享指示器相关联的缺点(或其它并发控制机制)，本发明提出了一种替代方法。如图6所示，可以在每个处理器41、42...4n的缓冲存储器10中将分布式的回调指示器32作为局部变量来保持和操纵，以反映在读复制更新的子系统20中的改变。每个分布式的回调指示器32显示一个读复制更新的子系统20的状态。接着，在每一个读复制更新的子系统的实例201、202...20n内部的相关的回调指示器处理机制34(图6也显示了)可以咨询局部的分布式的回调指示器32，以确定是否需要宽限期令牌处理。局部的分布式的回调指示器32可以显示该读复制更新的子系统是空闲的，在这种情况下不必传递令牌。另一方面，局部的分布式的回调指示器32可以显示在读复制更新的子系统中有未决的回调，并且在当前处理器处需要宽限期令牌处理。
为保持当读复制更新的子系统20内部条件改变时分布式的回调指示器32是最近的，可以使用与图7和8所示的宽限期令牌传递方案有些类似的传播技术。其它实现也是可以的。根据该传播技术，当每一个处理器41、42...4n经过静态时，它的回调指示器处理机制34咨询相邻的处理器的分布式的回调指示器32，并根据邻居的数值外加考虑自从当前处理器的最后的宽限期以来的局部回调的历史对其自身的局部的回调指示器32进行调整.
在本发明的一个实施例中，分布式的回调指示器32作为每一处理器的具有未决的回调的处理器的数目的计数器而实现。这些处理器可以被称为“回调处理器”，而且分布式的回调指示器32可以被认为是回调处理器的计数器。为操纵这个计数器，一处理器进行核对以了解自从这个处理器的最后的宽限期以来在它的局部的回调状态中是否已有任何的改变。如果没有出现改变，则当前处理器计数器将被设为与相邻的处理器的计数器相同的数值。如果处理器的回调历史显示宽限期令牌最后一次离开这个处理器时没有登记局部的回调，但自从最后的宽限期以来已经登记了新局部的回调的必需数目，则增加当前处理器计数器到比相邻的处理器计数器的数值大一。如果处理器的回调历史显示宽限期令牌最后一次离开这个处理器时登记了局部的回调，但自从最后的宽限期以来还未登记新局部的回调的必需数目，则当前处理器计数器将被降低到比相邻的处理器计数器的数值小一。
在本发明的第二实施例中，实现分布式的回调指示器32以跟踪未决的回调的总数的示数。在该情况下，分布式的回调指示器32可以被认为是回调计数器。为操纵这个计数器，一处理器将自从这个处理器的最后的宽限期以来所登记的局部的回调的数目与宽限期令牌最后一次离开处理器时登记了的局部的回调的数目进行比较。通过调整将当前处理器计数器设为相邻的处理器计数器的数值，以反映局部的回调的净增益或损耗。
在本发明的第三实施例中，分布式的回调指示器32作为识别具有未决的回调的处理器的位图而实现。为操纵该位图，一处理器确定自从宽限期令牌最后一次离开这个处理器以来是否有已经登记了的局部的回调的必需数目。如果有，则将当前处理器的位图设为与相邻的处理机的位图相符，但当前处理器的位设为1。否则，如果自从最后的宽限期以来还没有登记局部的回调的必需数目，则位图中当前处理器的位的值设为0。这个实现的一个缺点是，由于需要相应地处理大位图而不能从容地处理大量的处理器。
图9说明根据上述第一实施例可以被执行的处理步骤的一个示例流程，其中分布式的回调指示器32是具有未决的回调的处理器41、42...4n的数目的计数。图9的进程使用被称为“cbcpus”(由“callback cpus”简化而来)的每个处理器的局部变量作为分布式的回调指示器。这个变量是具有需要处理的回调的处理器的计数。另一个被称为“lastcbs”(由“last callbacks”简化而来)的每个处理器的局部变量，是指示宽限期令牌最后一次离开这个处理器时当前处理器是否有登记的回调的标记。第三个每个处理器的局部变量被称为“numcbs”(由“number ofcallbacks”简化而来)，是最后的宽限期令牌以来在当前处理器处登记的回调的数目的计数。
在图9的步骤40中，第n个处理器的回调指示器处理机制34获得处理器n+1的cbcpus的数值(处理器n-1也可以被使用，这取决于所要求的传播方向).在步骤42中，处理器n确定是否有符合启动宽限期的标准的任何新的回调.在一些情况下，单一回调的存在将满足这个标准.在其它情况下，可能希望通过建立一个指定启动宽限期所必需的回调数目的回调阈值以对回调进行批处理，和一个即使没有达到回调阈值仍然触发回调处理的消逝时间的阈值.如果在步骤42中有新的回调要求处理，那么在步骤44中当前处理器的cbcpus的数值被设为比相邻的处理器cbcpus的数值减去当前处理器的lastcbs的数值大一.当且仅当当前处理器上的回调符合启动宽限期的标准时，在步骤46中lastcbs的数值被设为1.如果在步骤42中没有新的回调要求处理，那么在步骤48中当前处理器的cbcpus的数值被设为与相邻的处理器cbcpus的数值减去当前处理器的lastcbs的数值相等.当且仅当当前处理器上没有符合启动宽限期的标准的新的回调时，在步骤50中lastcbs的数值被设为0.
由于当经过静态时每个处理器执行前述的处理，因此每一个分布式的回调指示器(在这个例子中的cbcpus)将迅速地反映由登记新的回调或处理旧的回调而引起的改变。通过在每个处理器处测试被传播的分布式的回调指示器，可以在没有足够的保证宽限期令牌循环的回调时避免潜在的昂贵令牌处理。图10的表格示例说明在示例的四处理器系统中的这种处理。图10是基于图7的，但为每个处理器0、1、2和3显示了每个表格元素左侧的宽限期令牌和每个表格元素右侧的分布式的回调指示器(在这个例子中的cbcpus)。带有阴影的单元格仍象征相对应的处理器是宽限期令牌的所有者。在每一情况下，所有者是某一处理器，该处理器的计数器具有最小数值，而且该处理器的邻居具有表示相对于令牌所有者的计数器数值的突变的计数器数值。
在图10中，处理器3从处理器0处接收宽限期令牌。然而，因为处理器3的分布式的回调指示器具有数值0，因此没有发生令牌处理。在分布式的回调指示器32是回调处理器的计数(cbcpus)的当前例子中，数值0意味着没有处理器具有保证处理的回调的必需数目。这样，处理器3确定用于这个处理器组的读复制更新子系统是空闲的。图10中，在t＝1时，处理器2确定它已经有新的回调活动，并且将其分布式的回调指示器的数值设为1。处理器3未受影响(因为，根据当前的例子，它由于回调指示器的活动仅仅关注处理器0)并且仍没有执行宽限期令牌处理。在t＝2时，将处理器2的分布式的回调指示器的数值传给处理器1。处理器3未受影响并且仍没有执行宽限期令牌处理。在t＝3时，处理器1的分布式的回调指示器的数值已经传给了处理器0。处理器3未受影响并且仍没有执行宽限期令牌处理。在t＝4时，处理器0的分布式的回调指示器的数值已经传给处理器3，致使处理器3执行宽限期令牌处理并将令牌传递给处理器2。在t＝5时，处理器2已经执行了执行宽限期令牌处理并将令牌传递给了处理器1。在t＝6时，处理器1已经执行了执行宽限期令牌处理并将令牌传递给了处理器0。此外，假定处理器2已经确定它的回调已经被处理并将其分布式的回调指示器设为0。在t＝7时，处理器0已经执行了宽限期令牌处理并将令牌传递给了处理器3。此外，处理器2的分布式的回调指示器已经被传给处理器1。在t＝8时，处理器3已经执行了宽限期令牌处理并将令牌传递给了处理器2。此外，处理器1的分布式的回调指示器已经被传给处理器0。假定在图9的系统中没有登记新的回调，则现在处理器2处的宽限期令牌将空闲，因为它的分布式的回调指示器为0。
图11总结了前述的处理。它显示，在t＝0和7时，处理器3将获得令牌(T)。接着，在t＝1、2和3期间，在处理器3处令牌将空闲。在t＝4和8时，处理器2将获得令牌。在t＝5时，处理器1将获得令牌。在t＝6时，处理器0将获得令牌。
现在参照图12，它显示了图9的分布式的回调指示器处理的一个替换方法.根据这个新的方法，不考虑是否已经达到了阈值，步骤42a(与图9的步骤42相对应)询问numbcbs是否为非0.当且仅当numbcbs大于0时，步骤46a(与图9的步骤46相对应)将lastcbs设为1.当且仅当numbcbs为0时，步骤50a(与图9的步骤50相对应)将lastcbs设为0.这个新的方法的优点是它允许处理器仅利用少数回调来在另一个处理器的宽限期令牌循环上“捎带”他们的回调处理需求并保持令牌不停地运动.缺点是可导致额外的宽限期的检测操作.
图13说明根据上述第二实施例可以执行的处理步骤的示例流程，在该实施例中分布式的回调指示器32是未决的回调的数目的计数。图13的进程使用被称为“cbspen”(由“callbacks pending”简化而来)的每个处理器的局部变量作为分布式的回调指示器。另一个被称为“lastcbs”(由“last callbacks”简化而来)的每个处理器的局部变量，是指示宽限期令牌最后一次离开这个处理器时当前处理器已登记的回调数目的数值。第三个每个处理器的局部变量被称为“numcbs”(由“number of callbacks”简化而来)，是最后的宽限期以来在当前处理器处登记的回调的数目的计数。
在图13的步骤60中，第n个处理器的回调指示器处理机制34获得处理器n+1的cbspen的数值(处理器n-1也可以被使用，这取决于所要求的传播方向)。在步骤62中，将当前处理器的cbspen的数值设为相邻的处理器的cbspen的数值加上当前处理器的numcbs的数值再减去当前处理器的lastcbs的数值。接着，在步骤66中，将lastcbs的数值设为numcbs。
图14说明根据上述第三实施例可以执行的处理步骤的示例流程，在该实施例中分布式的回调指示器32是显示哪些处理器具有未决的回调的位图。图14的进程使用被称为“cbcpumap”(由“callback cpumap”简化而来)的每个处理器的局部位图变量作为分布式的回调指示器。另一个每个处理器的局部变量被称为“numcbs”(由“number ofcallbacks”简化而来)，是最后的宽限期以来在当前处理器处登记的回调的数目的计数。
在图14的步骤80中，第n个处理器的回调指示器处理机制34获得处理器n+1的cbcpumap的数值(处理器n-1也可以被使用，这取决于所要求的传播方向)。在步骤82中，处理器n确定在这个处理器处是否登记有满足某些所设定的阈值(如与图9相关的上述讨论)的任何新的回调(numcbs)。如果在步骤82中有新的回调要求处理，那么在步骤84中当前处理器的cbcpumap的数值设为与处理器n+1相等，但cbcpumap第n位设为1。如果在步骤82中没有新的回调要求处理，那么在步骤86中当前处理器的cbcpumap的数值设为与处理器n+1相等，但cbcpumap第n位设为0。
因此，这里公开了用于读复制更新的宽限期检测的技术，该技术不使用原子指令并且可以实现对大量处理器的从容处理。可以想到，前述的概念可以在任何数据处理系统、机器实现的方法和计算机程序产品中进行各种实施，其中编程方法被记录在一个或多个数据存储介质上以控制数据处理系统执行所要求的功能。图15中由附图标记100显示用于存储这些编程方法的示例的数据存储介质。介质100作为传统的用于商用软件销售的那类便携式光盘而显示。这类介质可独自或与操作系统或合并了读复制更新功能的其它软件产品一起存储本发明的编程方法。该编程方法也可存储在便携式的磁介质(如软盘、闪存棒等)上或与合并在计算机平台中的驱动系统(如磁盘驱动器)结合的磁介质上。
虽然已经描述了本发明的各种实施例，但显然依照本发明可实现许多变化和新的实施例。因此，可以理解，本发明不以任何方式受限，除了依照附加的权利要求的精神及其等价物。