Read-copy update method

• US 7,472,228 B2
• Filed: 10/27/2004
• Issued: 12/30/2008
• Est. Priority Date: 10/27/2004
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: McKenney, Paul E., Sarma, Dipankar, Krieger, Orran Y., Appavoo, Jonathan
• Primary Examiner(s): Kim; Matt
• Assistant Examiner(s): Krofcheck; Michael C
• Application Number:
  US10/974,515
• Publication Number:
  US 20060100996A1
• Time in Patent Office: 1,525 Days
• Field of Search: 711/141, 711/147, 711/159
• US Class Current: 711/141
• CPC Class Codes: G06F 16/2358 Change logging, detection, and notification replication G06F16/27
• CPC Class Codes: G06F 16/2379 Updates performed during online database operations; commit processing
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

A method for managing requests for deferred updates to shared data elements while minimizing grace period detection overhead associated with determining whether pre-existing references to the data elements have been removed. Plural update requests that are eligible for grace period detection are buffered without performing grace period detection processing. One or more conditions that could warrant commencement of grace period detection processing are monitored while the update requests are buffered. If warranted by such a condition, grace period detection is performed relative to the update requests so that they can be processed. In this way, grace period detection overhead can be amortized over plural update requests while being sensitive to conditions warranting prompt grace period detection.

Claims

1. A method for managing requests for deferred updates to shared data elements while minimizing grace period detection overhead associated with determining whether pre-existing references to the data elements have been removed, comprising:

buffering plural update requests that are eligible for grace period detection without performing grace period detection processing that determines whether a grace period has elapsed to signify it is safe to process said update requests;

monitoring a set of conditions that are indicative of whether said grace period detection processing should be commenced, said conditions comprising buffer queue conditions, system conditions and explicit conditions, including;

(1) said buffered update requests reaching a threshold number, (2) said buffered update requests being buffered for a threshold time period, (3) said buffered update requests including an update request designated as urgent, (4) a low-memory event being encountered, and (5) a low-memory event being encountered on a memory type and said buffered update requests including an update request corresponding to said memory type;

determining whether any of said conditions warrants commencement of said grace period detection processing; and

if warranted by one of said conditions, performing said grace period detection processing relative to said update requests.

2. The method of claim 1 wherein said one of said conditions is identified by an explicit indicator associated with one of said update requests.

3. The method of claim 2 wherein said explicit indicator is passed as parameter when a function associated with said update request is invoked.

4. The method of claim 2 wherein said explicit indicator is generated by said update request being invoked using a pre-designated update request function.

5. The method of claim 1 wherein said buffered update requests are buffered on a queue.

6. The method of claim 1 wherein said method is implemented in conjunction with a read-copy update subsystem and said buffered update requests are buffered on a staging queue that is separate from a current generation or next generation update request queue of said read-copy update subsystem.

7. The method of claim 6 wherein said buffered update requests are moved from said staging queue into one of said current generation or next generation update request queues of said read-copy update subsystem upon the occurrence of said condition warranting grace period detection processing.

8. The method of claim 1 wherein said method is implemented in conjunction with a read-copy update subsystem that includes one or more queues of update requests, and wherein said buffered update requests are buffered on one of said queues.

9. The method of claim 1 wherein said method is implemented in conjunction with a read-copy update subsystem that includes a first queue of update requests awaiting expiration of a grace period and a second queue of update requests awaiting processing of said update requests in said first queue, and wherein said buffered update requests are buffered on said second queue.

10. A method for managing callbacks processed by a read-copy update subsystem while minimizing grace period detection overhead, comprising:

buffering plural callbacks that are eligible for grace period detection without performing grace period detection processing that determines whether a grace period has elapsed to signify it is safe to process said callbacks;

monitoring a set of conditions that are indicative of whether said grace period detection processing should be commenced, said conditions comprising buffer queue conditions, system conditions and explicit conditions, including;

(1) said buffered callbacks reaching a threshold number, (2) said buffered callbacks being buffered for a threshold time period, (3) said buffered callbacks including a callback designated as urgent, (4) a low-memory event being encountered, and (5) a low-memory event being encountered on a memory type and said buffered callbacks including a callback corresponding to said memory type;

determining whether any of said conditions warrants commencement of grace period detection processing; and

if warranted by one of said conditions, performing said grace period detection processing relative to said callbacks;

whereby grace period detection overhead can be amortized over plural callbacks while being sensitive to conditions warranting prompt grace period detection.

11. A method for managing requests for deferred updates to shared data elements while minimizing grace period detection overhead associated with determining whether pre-existing references to the data elements have been removed, comprising:

establishing a buffer to hold plural update requests that are eligible for grace period detection without performing grace period detection processing that determines whether a grace period has elapsed to signify it is safe to process said update requests;

monitoring a set of conditions that are indicative of whether said grace period detection processing should be commenced, said conditions comprising buffer queue conditions, system conditions and explicit conditions, including;

(1) said update requests reaching a threshold number, (2) said update requests being buffered for a threshold time period, (3) said update requests including an update request designated as urgent, (4) a low-memory event being encountered, and (5) a low-memory event being encountered on a memory type and said update requests including an update request corresponding to said memory type;

establishing an indicator for indicating the existence of any of said conditions warranting commencement of said grace period detection processing; and

establishing an activator responsive to said indicator indicating said condition and adapted to activate grace period detection relative to said update requests;

whereby grace period detection overhead can be amortized over plural update requests while being sensitive to conditions warranting prompt grace period detection.