Effective management of blocked-tasks in preemptible read-copy update

• US 8,615,771 B2
• Filed: 06/20/2011
• Issued: 12/24/2013
• Est. Priority Date: 06/20/2011
• 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 C
• Assistant Examiner(s): Lee, Adam
• Application Number:
  US13/164,265
• Publication Number:
  US 20120324473A1
• Time in Patent Office: 918 Days
• Field of Search: None
• US Class Current: 718/107
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

A technique for managing read-copy update readers that have been preempted while executing in a read-copy update read-side critical section. A single blocked-tasks list is used to track preempted reader tasks that are blocking an asynchronous grace period, preempted reader tasks that are blocking an expedited grace period, and preempted reader tasks that require priority boosting. In example embodiments, a first pointer may be used to segregate the blocked-tasks list into preempted reader tasks that are and are not blocking a current asynchronous grace period. A second pointer may be used to segregate the blocked-tasks list into preempted reader tasks that are and are not blocking an expedited grace period. A third pointer may be used to segregate the blocked-tasks list into preempted reader tasks that do and do not require priority boosting.

Claims

1. A system, comprising:

one or more processors;

a memory coupled to said one or more processors, said memory including a computer useable medium tangibly embodying at least one program of instructions executable by said one or more processors to perform operations for managing all read-copy update reader tasks that have been preempted while executing in a read-copy update read-side critical section on some or all of said one or more processors, said operations comprising managing a single blocked-tasks list associated with said some or all of said one or more processors to track said preempted read-copy update reader tasks that are blocking an asynchronous grace period, preempted read-copy update reader tasks that are blocking an expedited grace period, and preempted read-copy update reader tasks that require priority boosting, wherein an expedited grace period forces or simulates a context switch on some or all of said one or more processors to preempt all read-copy update reader tasks.

2. A system in accordance with claim 1, wherein:

a first pointer is used to segregate said blocked-tasks list into preempted read-copy update reader tasks that are and are not blocking a current asynchronous grace period;

a second pointer is used to segregate said blocked-tasks list into preempted read-copy update reader tasks that are and are not blocking an expedited grace period; and

a third pointer is used to segregate said blocked-tasks list into preempted read-copy update reader tasks that do and do not require priority boosting.

3. A system in accordance with claim 2, wherein said blocked-tasks list is ordered such that:

said first pointer references a first preempted read-copy update reader task on said blocked-tasks list that is a newest preempted reader task blocking a current asynchronous grace period, and all preempted read-copy update reader tasks that follow said first preempted read-copy update reader task on said blocked-tasks list are also blocking said current asynchronous grace period;

said second pointer references a second preempted read-copy update reader task on said blocked-tasks list that is a newest preempted read-copy update reader task blocking an expedited grace period, and all preempted read-copy update reader tasks that follow said second preempted read-copy update reader task on said blocked-tasks list are also blocking said expedited grace period; and

said third pointer references a third preempted read-copy update reader task on said blocked-tasks list that is a newest preempted read-copy update reader task that requires priority boosting, and all preempted read-copy update reader tasks that follow said third preempted reader task on said blocked-tasks list also require priority boosting.

4. A system in accordance with claim 3, wherein said first preempted read-copy update reader task, said second preempted read-copy update reader task and said third preempted read-copy update reader task are the same preempted read-copy update reader task.

5. A system in accordance with claim 4, wherein said blocked-tasks list is further ordered such that all preempted read-copy update reader tasks that are ahead of said first preempted read-copy update reader task are blocking a subsequent asynchronous grace period that follows said current asynchronous grace period.

6. A system in accordance with claim 5, wherein said system is either (1) a uniprocessor system in which said blocked-tasks list maintains all of said preempted read-copy update reader tasks in strict reverse time order, or (2) a multiprocessor system in which said blocked-tasks list maintains all of said preempted read-copy update reader tasks starting from said first preempted read-copy update reader task in strict reverse time order.

7. A system in accordance with claim 6, further including one or more data structures that each maintain an instance of said blocked-tasks list, said first pointer, said second pointer and said third pointer on behalf of at least one of said one or more processors, and wherein each of said data structures further maintains a grace period number, a quiescent state indicator and a grace period completed indicator on behalf of said at least one processor.

8. A computer program product, comprising:

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

program instructions provided by said one or more media for programming a data processing platform to perform operations for managing all read-copy update reader tasks that have been preempted while executing in a read-copy update read-side critical section on one or more processors of said data processing platform, said operations comprising managing a single blocked-tasks list associated with said one or more processors to track said preempted read-copy update reader tasks that are blocking an asynchronous grace period, preempted read-copy update reader tasks that are blocking an expedited grace period, and preempted read-copy update reader tasks that require priority boosting, wherein an expedited grace period forces or simulates a context switch on some or all of said one or more processors to preempt all read-copy update reader tasks.

9. A computer program product in accordance with claim 8, wherein:

a first pointer is used to segregate said blocked-tasks list into preempted read-copy update reader tasks that are and are not blocking a current asynchronous grace period;

a second pointer is used to segregate said blocked-tasks list into preempted read-copy update reader tasks that are and are not blocking an expedited grace period; and

a third pointer is used to segregate said blocked-tasks list into preempted read-copy update reader tasks that do and do not require priority boosting.

10. A computer program product in accordance with claim 9, wherein said blocked-tasks list is ordered such that:

said first pointer references a first preempted read-copy update reader task on said blocked-tasks list that is a newest preempted reader task blocking a current asynchronous grace period, and all preempted read-copy update reader tasks that follow said first preempted read-copy update reader task on said blocked-tasks list are also blocking said current asynchronous grace period;

said second pointer references a second preempted read-copy update reader task on said blocked-tasks list that is a newest preempted read-copy update reader task blocking an expedited grace period, and all preempted read-copy update reader tasks that follow said second preempted read-copy update reader task on said blocked-tasks list are also blocking said expedited grace period; and

said third pointer references a third preempted read-copy update reader task on said blocked-tasks list that is a newest preempted read-copy update reader task that requires priority boosting, and all preempted read-copy update reader tasks that follow said third preempted reader task on said blocked-tasks list also require priority boosting.

11. A computer program product in accordance with claim 10, wherein said first preempted read-copy update reader task, said second preempted read-copy update reader task and said third preempted read-copy update reader task are the same preempted read-copy update reader task.

12. A computer program product in accordance with claim 11, wherein said blocked-tasks list is further ordered such that all preempted read-copy update reader tasks that are ahead of said first preempted read-copy update reader task are blocking a subsequent asynchronous grace period that follows said current asynchronous grace period.

13. A computer program product in accordance with claim 12, wherein said system is either (1) a uniprocessor system in which said blocked-tasks list maintains all of said preempted read-copy update reader tasks in strict reverse time order, or (2) a multiprocessor system in which said blocked-tasks list maintains all of said preempted read-copy update reader tasks starting from said first preempted read-copy update reader task in strict reverse time order.

14. A computer program product in accordance with claim 13, further including one or more data structures that each maintain an instance of said blocked-tasks list, said first pointer, said second pointer and said third pointer on behalf of said one or more processors, and wherein each of said data structures further maintains a grace period number, a quiescent state indicator and a grace period completed indicator on behalf of said at least one processor.