Read-copy update grace period detection without atomic instructions that gracefully handles large numbers of processors
First Claim
1. 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 at any of said processors relative to any data element shared by said processors;
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.
0 Assignments
0 Petitions
Accused Products
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.
-
Citations
21 Claims
-
1. 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 at any of said processors relative to any data element shared by said processors; 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
11. 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; programming means recorded on said data storage media for programming a data processing platform to operate as by; 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 at any of said processing entities relative to any data element 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. - View Dependent Claims (12, 13, 14, 15, 16, 17, 18, 19, 20)
-
-
21. 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 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; means for processing said distributed callback indicator at each of said processors before engaging in token processing at said processors; and means for performing token processing at said processors only when warranted by said distributed callback indicator.
-
Specification