High performance real-time read-copy update
First Claim
1. In a multiprocessor computing machine having two or more processors, a memory operatively coupled to the processors, and at least one shared data element stored in the memory, the shared data element being accessible by data reader tasks (readers) and a data updater task (updater) executing concurrently on the processors in operating system kernel context, the readers being subject to preemption while referencing the shared data element in order to support realtime data processing operations, and the updater being capable of modifying or deleting the shared data element while preserving a pre-update view thereof until a grace period has expired signifying that all of the readers have passed through a quiescent state in which their pre-update references to the data element have been removed, a method for reducing reader overhead when referencing the shared data element while facilitating realtime-safe detection of grace periods, comprising:
- each said reader maintaining a local per-reader quiescent state indicator that is manipulated by said reader when entering and leaving a read-side critical section in which said reader references said shared data element;
said manipulating of said per-reader quiescent state indicator being performed by said reader without use of locks, atomic instructions, memory barriers, or disabling of preemption or interrupts; and
implementing a first-level quiescent state detector that designates a processor on which said reader is running to be quiescent based on said per-reader quiescent state indicator for said reader being in a local quiescent state-indicating condition.
1 Assignment
0 Petitions
Accused Products
Abstract
A technique for reducing reader overhead when referencing a shared data element while facilitating realtime-safe detection of a grace period for deferring destruction of the shared data element. The grace period is determined by a condition in which all readers that are capable of referencing the shared data element have reached a quiescent state subsequent to a request for a quiescent state. Common case local quiescent state tracking may be performed using only local per-reader state information for all readers that have not blocked while in a read-side critical section in which the data element is referenced. Uncommon case non-local quiescent state tracking may be performed using non-local multi-reader state information for all readers that have blocked while in their read-side critical section. The common case local quiescent state tracking requires less processing overhead than the uncommon case non-local quiescent state tracking.
71 Citations
18 Claims
-
1. In a multiprocessor computing machine having two or more processors, a memory operatively coupled to the processors, and at least one shared data element stored in the memory, the shared data element being accessible by data reader tasks (readers) and a data updater task (updater) executing concurrently on the processors in operating system kernel context, the readers being subject to preemption while referencing the shared data element in order to support realtime data processing operations, and the updater being capable of modifying or deleting the shared data element while preserving a pre-update view thereof until a grace period has expired signifying that all of the readers have passed through a quiescent state in which their pre-update references to the data element have been removed, a method for reducing reader overhead when referencing the shared data element while facilitating realtime-safe detection of grace periods, comprising:
-
each said reader maintaining a local per-reader quiescent state indicator that is manipulated by said reader when entering and leaving a read-side critical section in which said reader references said shared data element; said manipulating of said per-reader quiescent state indicator being performed by said reader without use of locks, atomic instructions, memory barriers, or disabling of preemption or interrupts; and implementing a first-level quiescent state detector that designates a processor on which said reader is running to be quiescent based on said per-reader quiescent state indicator for said reader being in a local quiescent state-indicating condition. - View Dependent Claims (2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 18)
-
-
7. A data processing system, comprising:
-
two or more processors; a memory coupled to said two or more processors; at least one shared data element stored in said memory, said shared data element being accessible by data reader tasks (readers) and a data updater task (updater) executing concurrently on said processors in operating system kernel context; said readers being subject to preemption while referencing said shared data element in order to support realtime data processing operations; said updater being capable of modifying or deleting said shared data element while preserving a pre-update view thereof until a grace period has expired signifying that all of said readers have passed through a quiescent state in which their pre-update references to said data element have been removed; said memory including a computer useable medium tangibly embodying at least one program of instructions executable by said processors to perform operations for reducing reader overhead when referencing said shared data element while facilitating realtime-safe detection of grace periods, comprising; each said reader maintaining a local per-reader quiescent state indicator that is manipulated by said reader when entering and leaving a read-side critical section in which said reader references said shared data element; said manipulating of said per-reader quiescent state indicator being performed by said reader without use of locks, atomic instructions, memory barriers or disabling of preemption or interrupts; and implementing a first-level quiescent state detector that designates a processor on which said reader is running to be quiescent based on said per-reader quiescent state indicator for said reader being in a local quiescent state-indicating condition.
-
-
13. A computer program product, comprising:
-
one or more machine-readable storage media; program instructions stored on said one or more storage media for programming a data processing platform having two or more processors, a memory operatively coupled to said processors, and at least one shared data element stored in the memory, said shared data element being accessible by data reader tasks (readers) and a data updater task (updater) executing concurrently on said processors in operating system kernel context, said readers being subject to preemption while referencing said shared data element in order to support realtime data processing operations, and said updater being capable of modifying or deleting said shared data element while preserving a pre-update view thereof until a grace period has expired signifying that all of said readers have passed through a quiescent state in which their pre-update references to said data element have been removed; said program instructions programming said data processing platform to implement a method for reducing reader overhead when referencing said shared data element while facilitating realtime-safe detection of grace periods, comprising; each said reader maintaining a local per-reader quiescent state indicator that is manipulated by said reader when entering and leaving a read-side critical section in which said reader references said shared data element; said manipulating of said per-reader quiescent state indicator being performed by said reader without use of locks, atomic instructions, memory barriers or disabling of preemption or interrupts; and implementing a first-level quiescent state detector that designates a processor on which said reader is running to be quiescent based on said per-reader quiescent state indicator for said reader being in a local quiescent state-indicating condition. - View Dependent Claims (14, 15, 16, 17)
-
Specification