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

• US 8,869,166 B2
• Filed: 04/02/2012
• Issued: 10/21/2014
• 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): Lee, Adam
• Application Number:
  US13/437,215
• Publication Number:
  US 20120324461A1
• Time in Patent Office: 932 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. In a computing system having one or more processors operatively coupled to one or more memory devices, a method 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 method 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 method 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 method 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 method 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 method 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 method 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 method 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. In a computing system having one or more processors operatively coupled to one or more memory devices, a method for managing read-copy update readers that have been preempted while executing in a read-copy update read-side critical section, comprising:

providing an in-memory data structure whose fields include a first data structure field storing a blocked-tasks list header, second, third and fourth data structure fields storing blocked-task list pointers, a fifth data structure field storing a grace period number, a sixth data structure field storing a quiescent state indicator for one or more processors and a seventh data structure field storing a grace period completion number;

using said first data structure field to build a single blocked-tasks list that tracks 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;

using said second data structure field to store a first pointer that segregates said blocked-tasks list into preempted reader tasks that are and are not blocking a current asynchronous grace period;

using said third data structure field to store a second pointer that segregates said blocked-tasks list into preempted reader tasks that are and are not blocking an expedited grace period;

using said fourth data structure field to store a third pointer that segregates said blocked-tasks list into preempted reader tasks that do and do not require priority boosting;

using said fifth data structure field to increment said grace period number and start a new grace period;

using said sixth data structure field to increment said quiescent state indicator and indicate that a processor quiescent state has been reached that initiates blocked reader task monitoring and an end of said new grace period once all preempted reader tasks on a tail portion of said blocked-tasks list that begins with said first preempted reader have completed read-copy update read-side critical section processing; and

using said seventh data structure field to increment said grace period completion number and declare said end of said new grace period.

9. A method in accordance with claim 8, wherein:

a blocked reader handler adds a preempted reader task to said blocked-tasks list and manipulates said first pointer to reference said preempted reader task if a processor quiescent state is not indicated by said quiescent state indicator;

an expedited grace period component manipulates said second pointer to reference a newest preempted reader task on said blocked-tasks list that is blocking an expedited grace period;

a boost reader component manipulates said third pointer to reference a newest preempted reader task on said blocked-tasks list that requires boosting; and

a read-side helper removes a preempted reader task from said blocked-tasks list and manipulates said first pointer, said second pointer and said third pointer to an extent that said pointers reference said preempted reader task being removed.

10. A method in accordance with claim 9, wherein:

a start normal grace period component increments said grace period number and manipulates said first pointer to reference a newest reader on said blocked-tasks list at a start of said new grace period; and

a record quiescent state/end grace period component increments said quiescent state indicator to record said processor quiescent state during said new grace period and increments said grace period completion number to end said new grace period.

11. A method in accordance with claim 10, wherein said record quiescent state/end grace period component periodically monitors said blocked-tasks list and, if there are no preempted reader tasks referenced by said first pointer, increments said grace period completion number to end said new grace period, and invokes callback processing if there are callbacks that requiring processing.