High Performance Real-Time Read-Copy Update

• US 20110055183A1
• Filed: 09/02/2009
• Published: 03/03/2011
• Est. Priority Date: 09/02/2009
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: McKenney, Paul E.
• Granted Patent: US 8,185,704 B2
• Time in Patent Office: Days
• US Class Current: 707/704
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

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.

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.

2. The method of claim 1, further including:

implementing a blocked reader handler at reader context switch time to check said per-reader quiescent state indicator to determine whether context switching said reader will block said reader inside said read-side critical section;

if said reader will block inside said read-side critical section as a result of said context switching, implementing said blocked reader handler to (1) provide a blocking notification to said reader, and (2) manipulate a non-local blocked reader indicator maintained on behalf of plural readers to indicate that there is a blocked reader;

said reader that has received said blocking notification implementing a read-side helper to manipulate said non-local blocked reader indicator when leaving said read-side critical section to indicate that said reader is no longer blocked; and

implementing a second-level quiescent state detector that designates said blocked reader to be quiescent based on checking said blocked reader indicator for manipulation to a no-blocked reader condition.

3. The method of claim 2, wherein said first-level quiescent state detector advises said reader that a quiescent state is needed and said read-side helper responds if it has left said read-side critical section, and wherein said first-level quiescent state detector designates said processor as quiescent based on said response being received.

4. The method of claim 2, wherein said blocked reader indicator is associated with a single one of said processors, a group of said processors, or all of said processors.

5. The method of claim 2, wherein said second-level quiescent state detector is implemented as part of a hierarchical grace period detection scheme.

6. The method of claim 2, wherein said blocked reader handler designates said reader for priority boosting if said reader will block as a result of said context switching, and wherein said read-side helper redesignates said reader to receive no priority boosting as a result of said reader leaving said read-side critical section.

8. The system of claim 1, further including:

implementing a blocked reader handler at reader context switch time to check said per-reader quiescent state indicator to determine whether context switching said reader will block said reader inside said read-side critical section;

if said reader will block inside said read-side critical section as a result of said context switching, implementing said blocked reader handler to (1) provide a blocking notification to said reader, and (2) manipulate a non-local blocked reader indicator maintained on behalf of plural readers to indicate that there is a blocked reader;

said reader that has received said blocking notification implementing a read-side helper to manipulate said non-local blocked reader indicator when leaving said read-side critical section to indicate that said reader is no longer blocked; and

implementing a second-level quiescent state detector that designates said blocked reader to be quiescent based on checking said blocked reader indicator for manipulation to a no-blocked reader condition.

9. The system of claim 8, wherein said first-level quiescent state detector advises said reader that a quiescent state is needed and said reader-side helper responds if it has left said read-side critical section, and wherein said first-level local quiescent state detector designates said processor as quiescent based on said response being received.

10. The system of claim 8, wherein said blocked reader indicator is associated with a single one of said processors, a group of said processors, or all of said processors.

11. The system of claim 8, wherein said second-level quiescent state detector is implemented as part of a hierarchical grace period detection scheme.

12. The system of claim 8, wherein said blocked reader handler designates said reader for priority boosting if said reader will block as a result of said context switching, and wherein said read-side helper redesignates said reader to receive no priority boosting as a result of said reader leaving said read-side critical section.

18. The computer program product of claim 2, wherein said blocked reader handler designates said reader for priority boosting if said reader will block as a result of said context switching, and wherein said read-side helper redesignates said reader to receive no priority boosting as a result of said reader leaving said read-side critical section.

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 media;

program instructions stored on said one or more 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.

14. The computer program product of claim 13, wherein said program instructions further program said data processing platform for:

implementing a blocked reader handler at reader context switch time to check said per-reader quiescent state indicator to determine whether context switching said reader will block said reader inside said read-side critical section;

if said reader will block inside said read-side critical section as a result of said context switching, implementing said blocked reader handler to (1) provide a blocking notification to said reader, and (2) manipulate a non-local blocked reader indicator maintained on behalf of plural readers to indicate that there is a blocked reader;

said reader that has received said blocking notification implementing a read-side helper to manipulate said non-local blocked reader indicator when leaving said read-side critical section to indicate that said reader is no longer blocked; and

implementing a second-level quiescent state detector that designates said blocked reader to be quiescent based on checking said blocked reader indicator for manipulation to a no-blocked reader condition.

15. The computer program product of claim 14, wherein said first-level quiescent state detector advises said reader that a quiescent state is needed and said reader-side helper responds if it has left said read-side critical section, and wherein said first-level quiescent state detector designates said processor as quiescent based on said response being received.

16. The computer program product of claim 14, wherein said blocked reader indicator is associated with a single one of said processors, a group of said processors, or all of said processors.

17. The computer program product of claim 14, wherein said second-level quiescent state detector is implemented as part of a hierarchical grace period detection scheme.

19. A method for reducing reader overhead when referencing a shared data element while facilitating realtime-safe detection of a grace period for deferring destruction of said shared data element, comprising:

said grace period being determined by a condition in which all readers that are capable of referencing said shared data element have reached a quiescent state subsequent to a request for a quiescent state;

performing common case local quiescent state tracking using only local per-reader state information for all of said readers that have not blocked while in a read-side critical section in which said data element is referenced;

performing uncommon case non-local quiescent state tracking using non-local multi-reader state information for all of said readers that have blocked while in said read-side critical section; and

said common case local quiescent state tracking requiring less processing overhead than said uncommon case non-local quiescent state tracking.

20. The method of claim 19, wherein said local per-reader state information is maintained by a per-reader quiescent state counter and wherein said non-local state information is maintained by a global, per-CPU, or per-CPU group blocked reader counter.