Read-copy update grace period detection without atomic instructions that gracefully handles large numbers of processors

A method for avoiding unnecessary grace period token processing while detecting a grace period in a read-copy update subsystem to determine when pending callbacks may be executed, comprising:

• implementing a quiescent state counter at each of a set of processors sharing access to said a data element;
• establishing a grace period token as a discontinuity in count values maintained by said quiescent state counters;
• said token being indicative of a grace period having elapsed at one of said processors when said token makes a round trip through said set of processors to return to said one of said processors;
• associating a distributed callback indicator as a local variable in a cache memory associated with each of said processors that is indicative of whether there is a need to process said callbacks at any of said processors;
• processing said distributed callback indicator at each of said processors before engaging in token processing at said processing entities;
• and
• performing token processing at said processors only when warranted by said distributed callback indicator.

A method for avoiding unnecessary grace period token processing while detecting a grace period for deferring removal of a shared data element until pre-existing references to the data element are removed, comprising:

• establishing a token to be circulated between processing entities sharing access to said data element;
• said token being indicative of a grace period having elapsed when said token makes a round trip through said processing entities;
• associating a distributed indicator with each of said processing entities that represents a number of said processing entities that have pending requests to remove data elements shared by said processing entities;
• processing said distributed indicator at each of said processing entities before engaging in token processing at said processing entities;
• said processing including modifying said distributed indicator according to a value of said distributed indicator at a neighboring one of said processing entities and a modification of said value according to (1) whether there are removal requests associated with the current grace period and there were no removal requests associated with the preceding grace period, in which case the distributed indicator is incremented, or (2) whether there are no removal requests associated with the current grace period and there were removal requests associated with the preceding grace period, in which case the distributed indicator is decremented, or (3) whether there are removal requests for both the current and preceding grace periods, or no removal requests for both the current and preceding grace periods, in which case the distributed indicator remains the same;
• and
• performing token processing at said processing entities only when warranted by said distributed indicator.

A method for avoiding unnecessary grace period token processing while detecting a grace period for deferring removal of a shared data element until pre-existing references to the data element are removed, comprising:

• establishing a token to be circulated between processing entities sharing access to said data element;
• said token being indicative of a grace period having elapsed when said token makes a round trip through said processing entities;
• associating a distributed indicator with each of said processing entities that represents a total number of pending requests to remove data elements shared by said processing entities;
• processing said distributed indicator at each of said processing entities before engaging in token processing at said processing entities;
• said processing including modifying said distributed indicator according to a value of said distributed indicator at a neighboring one of said processing entities and a modification of said value according to a difference between the number of removal requests added during the current grace period and the number of removal requests processed during the previous grace period;
• and
• performing token processing at said processing entities only when warranted by said distributed indicator.

A method for avoiding unnecessary grace period token processing while detecting a grace period for deferring removal of a shared data element until pre-existing references to the data element are removed, comprising:

• establishing a token to be circulated between processing entities sharing access to said data element;
• said token being indicative of a grace period having elapsed when said token makes a round trip through said processing entities;
• associating a distributed indicator with each of said processing entities that represents a bitmap of said processing entities that have pending requests to remove data elements shared by said processing entities;
• processing said distributed indicator at each of said processing entities before engaging in token processing at said processing entities;
• said processing including modifying said distributed indicator according to a value of said distributed indicator at a neighboring one of said processing entities and setting a bit corresponding to the evaluating processing entity according to (1) whether there are removal requests associated with the current grace period, in which case the bit is set to one, or (2) whether there are no removal requests associated with the current grace period, in which case the bit is set to zero;
• and
• performing token processing at said processing entities only when warranted by said distributed indicator.