High performance real-time read-copy update

• US 8,307,173 B2
• Filed: 02/13/2012
• Issued: 11/06/2012
• Est. Priority Date: 09/02/2009
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: McKenney, Paul E.
• Primary Examiner(s): Lo, Kenneth
• Application Number:
  US13/371,551
• Publication Number:
  US 20120144129A1
• Time in Patent Office: 267 Days
• Field of Search: 711/156, 711/152, 711/153, 711/159, 707/704
• US Class Current: 711/156
• 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. 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.

2. The method of claim 1, 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.

3. The method of claim 1, wherein said local quiescent state tracking comprises checking said per-reader state information for a currently running reader and designating a processor on which said reader is running as being in a local quiescent state if said per-reader state information indicates that said reader is not in a read-side critical section or that said processor has already passed through a local quiescent state.

4. The method of claim 3, wherein said local quiescent state tracking further comprises determining that a local quiescent state is needed from said processor and manipulating said per-reader state information to request acknowledgment of a local quiescent state.

5. The method of claim 1, wherein said non-local quiescent state tracking comprises checking said non-local multi-reader state information until there are no blocked readers for a particular grace period, and then noting a non-local quiescent state to end said grace period.

6. The method of claim 5, wherein said non-local quiescent state tracking is initiated when said local quiescent state tracking has determined that a group of processors that run said readers have passed through a local quiescent state.

7. A data processing system, comprising:

two or more processors;

a memory operatively coupled to said two or more processors;

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 a shared data element while facilitating realtime-safe detection of a grace period for deferring destruction of said shared data element, said operations 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.

8. The system of claim 7, 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.

9. The system of claim 7, wherein said local quiescent state tracking comprises checking said per-reader state information for a currently running reader and designating a processor on which said reader is running as being in a local quiescent state if said per-reader state information indicates that said reader is not in a read-side critical section or that said processor has already passed through a local quiescent state.

10. The system of claim 9, wherein said local quiescent state tracking further comprises determining that a local quiescent state is needed from said processor and manipulating said per-reader state information to request acknowledgment of a local quiescent state.

11. The system of claim 7, wherein said non-local quiescent state tracking comprises checking said non-local multi-reader state information until there are no blocked readers for a particular grace period, and then noting a non-local quiescent state to end said grace period.

12. The system of claim 11, wherein said non-local quiescent state tracking is initiated when said local quiescent state tracking has determined that a group of processors that run said readers have passed through a local quiescent state.

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 and a memory operatively coupled to said processors;

said program instructions programming said data processing platform to implement operations 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, said operations 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.

14. The computer program product of claim 13, 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.

15. The computer program product of claim 13, wherein said local quiescent state tracking comprises checking said per-reader state information for a currently running reader and designating a processor on which said reader is running as being in a local quiescent state if said per-reader state information indicates that said reader is not in a read-side critical section or that said processor has already passed through a local quiescent state.

16. The computer program product of claim 15, wherein said local quiescent state tracking further comprises determining that a local quiescent state is needed from said processor and manipulating said per-reader state information to request acknowledgment of a local quiescent state.

17. The computer program product of claim 13, wherein said non-local quiescent state tracking comprises checking said non-local multi-reader state information until there are no blocked readers for a particular grace period, and then noting a non-local quiescent state to end said grace period.

18. The computer program product of claim 17, wherein said non-local quiescent state tracking is initiated when said local quiescent state tracking has determined that a group of processors that run said readers have passed through a local quiescent state.