Efficiently boosting priority of read-copy update readers in a real-time data processing system

• US 7,734,879 B2
• Filed: 07/27/2006
• Issued: 06/08/2010
• Est. Priority Date: 07/27/2006
• Status: Active Grant

• Current Assignee: Twitter Inc (X Holdings Corp.)
• Original Assignee: International Business Machines Corporation
• Inventors: Bhattacharya, Suparna, McKenney, Paul E.
• Primary Examiner(s): Thomas; Shane M
• Application Number:
  US11/460,465
• Publication Number:
  US 20080040720A1
• Time in Patent Office: 1,412 Days
• Field of Search: 711/147, 711150-152
• US Class Current: 711/151
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

A technique for efficiently boosting the priority of a preemptable data reader 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 data elements. Upon the reader being subject to preemption or blocking, it is determined whether the reader is in a read-side critical section referencing any of the shared data elements. If it is, the reader'"'"'s priority is boosted in order to expedite completion of the critical section. The reader'"'"'s priority is subsequently decreased after the critical section has completed. In this way, delays in grace period processing due to reader preemption within the critical section, which can result in an out-of-memory condition, can be minimized efficiently with minimal processing overhead.

Claims

1. A method for efficiently boosting the priority of a preemptable data reader 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:

upon said reader being subject to preemption or blocking;

determining whether said reader is in a read-side critical section referencing any of said one or more shared data elements;

detecting the existence of a predetermined condition other than whether said reader is in said critical section;

boosting said reader'"'"'s priority when said reader is in said critical section from an existing priority level to a priority boost level that is higher than said existing priority level to expedite said reader'"'"'s completion of said critical section, said priority boost level having a first magnitude when said predetermined condition is not detected and a second magnitude that is greater than said first magnitude when said predetermined condition is detected; and

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

2. A method in accordance with claim 1 wherein said priority boosting is performed by one of a scheduler or a lock priority subsystem.

3. A method in accordance with claim 1 wherein said priority boosting comprises boosting said reader'"'"'s priority to a priority boost level that is higher than a base priority of all non-realtime processes that would otherwise be capable of preempting said reader.

4. A method in accordance with claim 1 wherein said priority boosting comprises boosting said reader'"'"'s priority to a first priority boost level having said first magnitude if said reader is in said critical section and to a second priority boost level having said second magnitude upon the occurrence of said predetermined condition.

5. A method in accordance with claim 4 wherein said predetermined condition is one of a grace period delay signifying an impending out-of-memory condition or said reader having entered said critical section prior to a current grace period.

6. A method in accordance with claim 1 further including placing said reader on a first list of priority boosted readers if said reader entered said critical section during a current grace period and placing said reader on a second list of priority boosted readers if said reader entered said critical section during a previous grace period, said second list being used to identify readers whose priorities may need to be boosted higher than readers on said first list.

7. A method in accordance with claim 6 further including moving readers on said first list to said second list when said current grace period ends.

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 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, and comprising:

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

a lock priority subsystem adapted to implement priority inheritance management of a sharable lock that may be held by said reader;

a grace period detection component adapted to detect the end of a current grace period and initiate a new grace period;

a callback advancer adapted to advance shared data element destruction callbacks for processing when said grace period detection component initiates a new grace period;

a reader registration component adapted to indicate to said grace period detection component that said reader is entering said critical section;

a reader deregistration component adapted to indicate to said grace period detection component that said reader is exiting said critical section;

said scheduler and said lock priority subsystem being respectively responsive to said reader being subject to preemption or blocking by;

determining whether said reader is in a read-side critical section referencing any of said one or more shared data elements; and

boosting said reader'"'"'s priority if said reader is in said critical section to expedite said reader'"'"'s completion of said critical section; and

said reader deregistration component being responsive to said reader having a boosted priority level by decreasing said reader'"'"'s priority following said reader'"'"'s completion of said critical section.

9. A system in accordance with claim 8 wherein said priority boosting comprises boosting said reader'"'"'s priority to a priority boost level that is higher than a base priority of all non-realtime processes that would otherwise be capable of preempting said reader.

10. A system in accordance with claim 8 wherein said priority boosting comprises boosting said reader'"'"'s priority to a first priority boost level if said reader is in said critical section and to a second priority boost level upon the occurrence of a predetermined condition.

11. A system in accordance with claim 10 wherein said predetermined condition is one of a grace period delay determined by said grace period detection component and signifying an impending out-of-memory condition or said reader having entered said critical section prior to a current grace period.

12. A system in accordance with claim 8 wherein said scheduler is further responsive to preemption said reader by placing said reader on a first list of priority boosted readers if said reader entered said critical section during a current grace period and placing said reader on a second list of priority boosted readers if said reader entered said critical section during a previous grace period, said second list being used to identify reader whose priorities may need to be boosted higher than readers on said first list.

13. A system in accordance with claim 12 wherein said callback advancer is adapted to move readers on said first list to said second list when said current grace period ends.

14. A computer program product for efficiently boosting the priority of a preemptable data reader 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:

one or more machine-useable storage media;

programming logic provided by said one or more storage media for programming a data processing platform to operate as by;

upon said reader being subject to preemption or blocking;

determining whether said reader is in a read-side critical section referencing any of said one or more shared data elements;

detecting the existence of a predetermined condition other than whether said reader is in said critical section;

boosting said reader'"'"'s priority when said reader is in said critical section from an existing priority level to priority boost level that is higher than said existing priority level to expedite said reader'"'"'s completion of said critical section, said priority boost level having a first magnitude when said predetermined condition is not detected and a second magnitude that is greater than said first magnitude when said predetermined condition is detected; and

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 priority boosting is performed by one of a scheduler or a lock priority subsystem.

16. A computer program product in accordance with claim 14 wherein said priority boosting comprises boosting said reader'"'"'s priority to a priority boost level that is higher than a base priority of all non-realtime processes that would otherwise be capable of preempting said reader.

17. A computer program product in accordance with claim 14 wherein said priority boosting comprises boosting said reader'"'"'s priority to a first priority boost level having said first magnitude if said reader is in said critical section and to a second priority boost level having said second magnitude upon the occurrence of said predetermined condition.

18. A computer program product in accordance with claim 17 wherein said predetermined condition is one of a grace period delay signifying an impending out-of-memory condition or said reader having entered said critical section prior to a current grace period.

19. A computer program product in accordance with claim 14 wherein said programming logic is further adapted to program said data processing platform to place said reader on a first list of priority boosted readers if said reader entered said critical section during a current grace period and place said reader on a second list of priority boosted readers if said reader entered said critical section during a previous grace period, said second list being used to identify readers whose priorities may need to be boosted higher than readers on said first list.

20. A computer program product in accordance with claim 19 wherein said programming logic is further adapted to program said data processing platform to move readers on said first list to said second list when said current grace period ends.