Efficiently boosting priority of read-copy update readers while resolving races with exiting and unlocking processes

• US 8,495,641 B2
• Filed: 06/29/2007
• Issued: 07/23/2013
• Est. Priority Date: 06/29/2007
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: McKenney, Paul E.
• Primary Examiner(s): Puente, Emerson
• Assistant Examiner(s): SWIFT, CHARLES M
• Application Number:
  US11/771,570
• Publication Number:
  US 20090006403A1
• Time in Patent Office: 2,216 Days
• Field of Search: 718/100, 718/103, 711/147, 711/150, 711/151, 711/152
• US Class Current: 718/103
• CPC Class Codes: G06F 9/4831 with variable priority
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores

Abstract

A technique for efficiently boosting the priority of a preemptable data reader while resolving races between the priority boosting and the reader exiting a critical section or terminating in order to eliminate impediments to grace period processing that defers the destruction of one or more shared data elements that may be referenced by the reader until the reader is no longer capable of referencing the one or more data elements. A determination is made that the reader is in a read-side critical section and the reader is designated as a candidate for priority boosting. A verification is made that the reader has not exited its critical section or terminated, and the reader'"'"'s priority is boosted to expedite its completion of the critical section. The reader'"'"'s priority is decreased following its completion of the critical section.

Claims

1. A method for efficiently boosting the priority of a preemptable data reader while resolving races between said priority boosting and said reader exiting a critical section or terminating in order to eliminate impediments to grace period processing that defers the destruction of one or more shared data elements that may be referenced by said reader until said reader is no longer capable of referencing said one or more data elements, comprising:

a scheduler determining that said reader is in a read-side critical section;

said scheduler designating said reader as a candidate for priority boosting;

a priority booster determining again by performing a verifying operation that said reader has not exited its critical section or terminated;

said priority booster boosting said reader'"'"'s priority by performing a boosting operation to expedite said reader'"'"'s completion of said critical section; and

a reader deregistration component decreasing said reader'"'"'s priority following said reader'"'"'s completion of said critical section.

2. A method in accordance with claim 1 wherein said designating operation comprises changing a state of said reader from a first state that is indicative of said reader'"'"'s priority not requiring boosting to a second state that is indicative of said reader'"'"'s priority requiring boosting, and wherein said priority boosting operation includes changing said state of said reader from said second state to a third state that is indicative of said reader'"'"'s priority having been boosted, and further wherein said priority decreasing operation includes changing said state of said reader from said third state to said first state.

3. A method in accordance with claim 1 wherein said designating operation comprises adding a reference to said reader on a first list of readers requiring priority boosting, and wherein said verifying operation comprises determining whether said reference to said reader is still on said first list of readers, and wherein said priority boosting operation comprises moving said reference to said reader from said first list to a second list of readers whose priority has been boosted, and further wherein said priority decreasing operation comprises removing said reference to said reader from whichever of said first list and said second list said reference is on.

4. A method in accordance with claim 3 wherein said first list and said second list are protected by a lock or other mutual exclusion mechanism to serialize access thereto during said priority boosting operation and said priority decreasing operation.

5. A method in accordance with claim 4 wherein said first list and said second list represent a list pair that is an element of an array of similar list pairs each comprising a first list portion and a second list portion.

6. A method in accordance with claim 5 wherein said designating operation comprises acquiring a first list pair index to a list pair of said array that is to be used for adding reader references, and wherein said priority boosting operation comprises acquiring a second list pair index to a second list pair of said array that has been least recently used by said designating operation to add reader references.

7. A method in accordance with claim 1 further including one or more of said priority boosting operation boosting said reader'"'"'s priority more aggressively under low memory conditions, said priority boosting operation successively boosting said reader'"'"'s priority, said priority boosting operation re-boosting an already boosted reader to account for changes in the priority of said priority boosting operation, and said priority boosting operation being implemented in multiple per-processor or per-multiprocessor node instances in the event that said method is implemented in a multi-processor or multi-mode environment.

8. 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 efficiently boost the priority of a preemptable data reader while resolving races between said priority boosting and said reader exiting a critical section or terminating in order to eliminate impediments to grace period processing that defers the destruction of one or more shared data elements that may be referenced by said reader until said reader is no longer capable of referencing said one or more data elements, said system further comprising:

a real-time preemptive scheduler adapted to preemptively schedule said reader for execution;

critical section entry determining logic in said scheduler adapted to determine that a reader is in a read-side critical section;

designating logic in said scheduler adapted to designate said reader as a candidate for priority boosting;

a priority booster;

critical section non-exit verification logic in said priority booster adapted to determine again that said reader has not exited its critical section;

priority boosting logic in said priority booster responsive to said determining logic and adapted to boost said reader'"'"'s priority by performing a boosting operation to expedite said reader'"'"'s completion of said critical section;

a reader deregistration component; and

priority decreasing logic in said reader deregistration component adapted to decrease said reader'"'"'s priority following said reader'"'"'s completion of said critical section.

9. A system in accordance with claim 8 wherein said designating logic is adapted to change a state of said reader from a first state that is indicative of said reader'"'"'s priority not requiring boosting to a second state that is indicative of said reader'"'"'s priority requiring boosting, and wherein said priority boosting logic is adapted to change said state of said reader from said second state to a third state that is indicative of said reader'"'"'s priority having been boosted, and further wherein said priority decreasing logic is adapted to change said state of said reader from said third state to said first state.

10. A system in accordance with claim 8 further comprising a first list of readers requiring priority boosting and a second list of readers whose priority has been boosted, and wherein said designating logic is adapted to add a reference to said reader on said first list, and wherein said critical section non-exit verification logic is adapted to determine whether said reference to said reader is still on said first list, and wherein said priority boosting logic is adapted to move said reference to said reader from said first list to said second list, and further wherein said priority decreasing logic is adapted to remove said reference to said reader from whichever of said first list and said second list said reference is on.

11. A system in accordance with claim 10 wherein said first list and said second list are protected by a lock or other mutual exclusion mechanism to serialize access thereto during said priority boosting operation and said priority decreasing operation.

12. A system in accordance with claim 11 wherein said first list and said second list represent a list pair that is an element of an array of similar list pairs each comprising a first list portion and a second list portion.

13. A system in accordance with claim 12 wherein said designating logic is adapted to acquire a first list pair index to a list pair of said array that is to be used for adding reader references, and wherein said boosting logic is adapted to acquire a second list pair index to a second list pair of said array that has been least recently used by said designating logic to add reader references.

14. A computer program product, comprising:

one or more non-transitory machine-readable storage media;

programming logic provided by said one or more media for programming a data processing platform to efficiently boost the priority of a preemptable data reader while resolving races between said priority boosting and said reader exiting a critical section or terminating in order to eliminate impediments to grace period processing that defers the destruction of one or more shared data elements that may be referenced by said reader until said reader is no longer capable of referencing said one or more data elements, as by;

a scheduler determining that said reader has entered a read-side critical section;

said scheduler designating said reader as a candidate for priority boosting;

a priority booster determining again by performing a verification operation that said reader has not exited its critical section or terminated;

said priority booster boosting said reader'"'"'s priority by performing a boosting operation to expedite said reader'"'"'s completion of said critical section; and

a reader deregistration component decreasing said reader'"'"'s priority following said reader'"'"'s completion of said critical section.

15. A computer program product in accordance with claim 14 wherein said designating operation comprises changing a state of said reader from a first state that is indicative of said reader'"'"'s priority not requiring boosting to a second state that is indicative of said reader'"'"'s priority requiring boosting, and wherein said priority boosting operation includes changing said state of said reader from said second state to a third state that is indicative of said reader'"'"'s priority having been boosted, and further wherein said priority decreasing operation includes changing said state of said reader from said third state to said first state.

16. A computer program product in accordance with claim 14 wherein said designating operation comprises adding a reference to said reader on a first list of readers requiring priority boosting, and wherein said verifying operation comprises determining whether said reference to said reader is still on said first list of readers, and wherein said priority boosting operation comprises moving said reference to said reader from said first list to a second list of readers whose priority has been boosted, and further wherein said priority decreasing operation comprises removing said reference to said reader from whichever of said first list and said second list said reference is on.

17. A computer program product in accordance with claim 16 wherein said first list and said second list are protected by a lock or other mutual exclusion mechanism to serialize access thereto during said priority boosting operation and said priority decreasing operation.

18. A computer program product in accordance with claim 17 wherein said first list and said second list represent a list pair that is an element of an array of similar list pairs each comprising a first list portion and a second list portion.

19. A computer program product in accordance with claim 18 wherein said designating operation comprises acquiring a first list pair index to a list pair of said array that is to be used for adding reader references, and wherein said priority boosting operation comprises acquiring a second list pair index to a second list pair of said array that has been least recently used by said designating operation to add reader references.

20. A computer program product in accordance with claim 14 further including one or more of said priority boosting operation boosting said reader'"'"'s priority more aggressively under low memory conditions, said priority boosting operation successively boosting said reader'"'"'s priority, said priority boosting operation re-boosting an already boosted reader to account for changes in the priority of said priority boosting operation, and said priority boosting operation being implemented in multiple per-processor or per-multiprocessor node instances in the event that said method is implemented in a multi-processor or multi-mode environment.