Realtime-safe read copy update with lock-free readers
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 perform realtime-safe grace detection of a grace period for deferring removal of a shared data element until pre-existing references to the data element are removed, and comprising:
- a pair of counters for each of said one or more processors;
a global counter selector that determines which counter of each per-processor counter pair is a current counter;
a reader adapted to read a shared data element at a processor;
a counter incrementer adapted to;
increment the current counter of said processor'"'"'s counter pair that corresponds to said global counter selector;
test for reversal of said processor'"'"'s counter pair to ensure that the incremented counter is still the current counter corresponding to said global counter selector; and
responsive to said counter pair reversal occurring such said incremented counter has become the non-current counter, incrementing the other counter of said processor'"'"'s counter pair that has become the current counter;
a data referencer adapted to reference said shared data element;
a counter decrementer adapted to decrement whichever counter of said processor'"'"'s counter pair remains incremented; and
a subsystem adapted to process the destruction of a pre-update version of said shared data element following updating thereof in a manner that preserves a pre-update version of said data element, said subsystem including;
a counter switch adapted to switch said global counter selector to establish a new current counter of each per-processor counter pair;
a counter monitor adapted to test the non-current counter of each per-processor counter pair for zero; and
a callback processor adapted to destroy said shared data element'"'"'s pre-update version upon the non-current counter of each per-processor counter pair being zero.
2 Assignments
0 Petitions
Accused Products
Abstract
A technique for realtime-safe detection of a grace period for deferring the destruction of a shared data element until pre-existing references to the data element have been removed. A pair of counters is established for each of one or more processors. A global counter selector determines which counter of each per-processor counter pair is a current counter. When reading a shared data element at a processor, the processor'"'"'s current counter is incremented. Following counter incrementation, the processor'"'"'s counter pair is tested for reversal to ensure that the incremented counter is still the current counter. If a counter reversal has occurred, such that the incremented counter is no longer current, the processor'"'"'s other counter is incremented. Following referencing of the shared data element, any counter that remains incremented is decremented. Following an update to the shared data element wherein a pre-update version of the element is maintained, the global counter selector is switched to establish a new current counter of each per-processor counter pair. The non-current counter of each per-processor counter pair is tested for zero. The shared data element'"'"'s pre-update version is destroyed upon the non-current counter of each per-processor counter pair being zero.
67 Citations
11 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 perform realtime-safe grace detection of a grace period for deferring removal of a shared data element until pre-existing references to the data element are removed, and comprising:
-
a pair of counters for each of said one or more processors; a global counter selector that determines which counter of each per-processor counter pair is a current counter; a reader adapted to read a shared data element at a processor;
a counter incrementer adapted to;increment the current counter of said processor'"'"'s counter pair that corresponds to said global counter selector; test for reversal of said processor'"'"'s counter pair to ensure that the incremented counter is still the current counter corresponding to said global counter selector; and responsive to said counter pair reversal occurring such said incremented counter has become the non-current counter, incrementing the other counter of said processor'"'"'s counter pair that has become the current counter; a data referencer adapted to reference said shared data element; a counter decrementer adapted to decrement whichever counter of said processor'"'"'s counter pair remains incremented; and a subsystem adapted to process the destruction of a pre-update version of said shared data element following updating thereof in a manner that preserves a pre-update version of said data element, said subsystem including; a counter switch adapted to switch said global counter selector to establish a new current counter of each per-processor counter pair; a counter monitor adapted to test the non-current counter of each per-processor counter pair for zero; and a callback processor adapted to destroy said shared data element'"'"'s pre-update version upon the non-current counter of each per-processor counter pair being zero. - View Dependent Claims (2, 3, 4, 5)
-
-
6. A computer program product for realtime-safe grace detection of a grace period for deferring the destruction of a shared data element until pre-existing references to the data element are removed, comprising:
-
one or more machine-useable storage media; programming logic provided by said one or more media for programming a data processing platform to operate as by; establishing a pair of counters for each of one or more processors; establishing a global counter selector that determines which counter of each per-processor counter pair is a current counter; when reading a shared data element at a processor; incrementing the current counter of said processor'"'"'s counter pair that corresponds to said global counter selector; testing for reversal of said processor'"'"'s counter pair to ensure that the incremented counter is still the current counter corresponding to said global counter selector; if a counter pair reversal has occurred such said incremented counter has become the non-current counter, incrementing the other counter of said processor'"'"'s counter pair that has become the current counter; referencing said shared data element; and decrementing whichever counter of said processor'"'"'s counter pair remains incremented; updating said shared data element in a manner that preserves a pre-update version of the shared data element; switching said global counter selector to establish a new current counter of each per-processor counter pair; testing the non-current counter of each per-processor counter pair for zero; and destroying said shared data element'"'"'s pre-update version upon the non-current counter of each per-processor counter pair being zero. - View Dependent Claims (7, 8, 9, 10, 11)
-
Specification