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

• US 20060123100A1
• Filed: 10/27/2004
• Published: 06/08/2006
• Est. Priority Date: 10/27/2004
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Sarma, Dipankar, McKenney, Paul E., Russell, Paul F.
• Granted Patent: US 7,454,581 B2
• Time in Patent Office: Days
• US Class Current: 709/223
• CPC Class Codes: G06F 2209/522 Manager
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99957 Garbage collection

Abstract

A method, system and computer program product for avoiding unnecessary grace period token processing while detecting a grace period without atomic instructions in a read-copy update subsystem or other processing environment that requires deferring removal of a shared data element until pre-existing references to the data element are removed. Detection of the grace period includes establishing a token to be circulated between processing entities sharing access to the data element. A grace period elapses whenever the token makes a round trip through the processing entities. A distributed indicator associated with each processing entity indicates whether there is a need to perform removal processing on any shared data element. The distributed indicator is processed at each processing entity before the latter engages in token processing. Token processing is performed only when warranted by the distributed indicator. In this way, unnecessary token processing can be avoided when the distributed indicator does not warrant such processing.

Claims

1. 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 is indicative of whether there is a need to perform removal processing on said data element or on other 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; and

performing token processing at said processing entities only when warranted by said distributed indicator.

2. A method in accordance with claim 1 wherein each of said distributed indicators is stored as a local variable in a cache memory associated with one of said processing entities.

3. A method in accordance with claim 1 wherein said distributed indicators represent a number of said processing entities that have pending requests to remove data elements shared by said processing entities.

4. A method in accordance with claim 1 wherein said distributed indicators represent a number of pending requests to remove data elements shared by said processing entities.

5. A method in accordance with claim 1 wherein said distributed indicators represent a bit map identifying said processing entities that have pending requests to remove data elements shared by said processing entities.

6. A method in accordance with claim 1 wherein a change made to one of said distributed indicators at one of said processing entities is propagated to other ones of said processing entities.

7. A method in accordance with claim 1 wherein a value of one of said distributed indicators at first one of said processing entities reflects a value of a second one of said distributed indicators at a neighboring second one of said processing entities adjusted as necessary to reflect data element removal request activity at said first one of said processing entities.

8. A method in accordance with claim 1 wherein said processing of said distributed indicator includes determining whether there are a threshold number of pending data element removal requests at one of said processing entities to warrant circulation of said token.

9. A method in accordance with claim 1 wherein said processing of said distributed indicator includes determining whether there any pending data element removal requests at one of said processing entities.

10. A method in accordance with claim 1 wherein said method is implemented as part of a read-copy update mutual exclusion technique, said data element removals are implemented by registering callbacks at said processing entities, and said distributed indicator is a distributed callback indicator reflecting callback activity in a read-copy update subsystem.

11. A data processing system having one or more processors, a memory and a communication pathway between the one or more processors and the memory, said system being adapted to avoid unnecessary grace period token processing while detecting a grace period for deferring a removal by one of said processors of a shared data element until pre-existing references to the data element maintained by other of said processors are removed, and comprising:

a token to be circulated between said processors;

a token manipulator associated with each of said processors adapted to circulate said token and determine whether said grace period has elapsed by virtue of said token making a round trip through said processors;

a distributed indicator associated with each of said processors that is indicative of whether there is a need to perform removal processing on said data element or on other data elements shared by said processing entities;

a distributed indicator handling mechanism associated with each of said processors adapted to process said distributed indicator before token processing by said token manipulator; and

said distributed indicator handling mechanisms being further adapted to permit said token manipulators to performing token processing at said processors only when warranted by said distributed indicator.

12. A system in accordance with claim 11 wherein each of said distributed indicators is stored as a local variable in a cache memory associated with one of said processors.

13. A system in accordance with claim 11 wherein said distributed indicators represent a number of said processors that have pending requests to remove data elements shared by said processors.

14. A system in accordance with claim 11 wherein said distributed indicators represent a number of pending requests to remove data elements shared by said processors.

15. A system in accordance with claim 11 wherein said distributed indicators represent a bit map identifying said processors that have pending requests to remove data elements shared by said processors.

16. A system in accordance with claim 11 wherein said distributed indicator handling mechanisms are adapted to propagate a change made to one of said distributed indicators at one of said processors to other ones of said processors.

17. A system in accordance with claim 11 wherein a value of one of said distributed indicators at first one of said processors reflects a value of a second one of said distributed indicators at a neighboring second one of said processors adjusted as necessary to reflect data element removal request activity at said first one of said processors.

18. A system in accordance with claim 11 wherein said distributed indicator handling mechanisms are adapted to process said distributed indicator by determining whether there are a threshold number of pending data element removal requests at one of said processors to warrant circulation of said token.

19. A system in accordance with claim 11 wherein said distributed indicator handling mechanisms are adapted to process said distributed indicators by determining whether there any pending data element removal requests at one of said processors.

20. A system in accordance with claim 11 wherein said token, said token manipulator, said distributed indicator, and said distributed indicator handling mechanism are implemented as part of a read-copy update subsystem, said data element removals are implemented by registering callbacks at said processors, and said distributed indicator is a distributed callback indicator reflecting callback activity in said read-copy update subsystem.

21. A computer program product 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:

one or more data storage media;

means recorded on said data storage media for programming a data processing platform to operate as by;

establishing a token to be circulated between processors 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 is indicative of whether there is a need to perform removal processing on said data element or on other 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; and

performing token processing at said processing entities only when warranted by said distributed indicator.

22. A computer program product in accordance with claim 21 wherein each of said distributed indicators is stored as a local variable in a cache memory associated with one of said processing entities.

23. A computer program product in accordance with claim 21 wherein said distributed indicators represent a number of said processing entities that have pending requests to remove data elements shared by said processing entities.

24. A computer program product in accordance with claim 21 wherein said distributed indicators represent a number of pending requests to remove data elements shared by said processing entities.

25. A computer program product in accordance with claim 21 wherein said distributed indicators represent a bit map identifying said processing entities that have pending requests to remove data elements shared by said processing entities.

26. A computer program product in accordance with claim 21 wherein a change made to one of said distributed indicators at one of said processing entities is propagated to other ones of said processing entities.

27. A computer program product in accordance with claim 21 wherein a value of one of said distributed indicators at first one of said processing entities reflects a value of a second one of said distributed indicators at a neighboring second one of said processing entities adjusted as necessary to reflect data element removal request activity at said first one of said processing entities.

28. A computer program product in accordance with claim 21 wherein said processing of said distributed indicator includes determining whether there are a threshold number of pending data element removal requests at one of said processing entities to warrant circulation of said token.

29. A computer program product in accordance with claim 21 wherein said processing of said distributed indicator includes determining whether there any pending data element removal requests at one of said processing entities.

30. A computer program product in accordance with claim 21 wherein said program means are implemented as part of a read-copy update subsystem computer program product, said data element removals are implemented by registering callbacks at said processing entities, and said distributed indicator is a distributed callback indicator reflecting callback activity in said read-copy update subsystem.

31. 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 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;

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.

32. A data processing system having one or more processors, a memory and a communication pathway between the one or more processors and the memory, said system including a read-copy update subsystem adapted to avoid unnecessary grace period token processing while detecting a grace period to determine when pending callbacks may be executed, and comprising:

means for implementing a quiescent state counter at each of a set of processors sharing access to said a data element;

means for 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;

means for associating a distributed callback indicator as 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;

means for processing said distributed callback indicator at each of said processors before engaging in token processing at said processing entities; and

means for performing token processing at said processors only when warranted by said distributed callback indicator.

33. 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.

34. 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.

35. 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.