Realtime-safe read copy update with per-processor read/write locks

• US 20070101071A1
• Filed: 11/01/2005
• Published: 05/03/2007
• Est. Priority Date: 11/01/2005
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: McKenney, Paul
• Granted Patent: US 7,395,383 B2
• Time in Patent Office: Days
• US Class Current: 711/152
• CPC Class Codes: G06F 2209/523 Mode
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

A technique for realtime-safe detection of a grace period for deferring the destruction of a shared data element until pre-existing references to the data element have been removed. A per-processor read/write lock is established for each of one or more processors. When reading a shared data element at a processor, the processor'"'"'s read/write lock is acquired for reading, the shared data element is referenced, and the read/write lock that was acquired for reading is released. When starting a new grace period, all of the read/write locks are acquired for writing, a new grace period is started, and all of the read/write locks are released.

Claims

1. A method for realtime-safe detection of a grace period for deferring the destruction of a shared data element until pre-existing references to the data element are removed, comprising:

establishing a read/write lock for each of one or more processors;

when reading a shared data element at a processor;

acquiring said processor'"'"'s read/write lock for reading;

referencing said shared data element; and

releasing said read/write lock that was acquired for reading; and

when starting a new grace period;

acquiring all of said read/write locks for writing;

starting a new grace period; and

releasing all of said read/write locks.

2. A method in accordance with claim 1 further including:

following an update to a shared data element in a manner that preserves a pre-update version of said data element and a new request for deferred destruction of said data element;

testing for the start of a new grace period;

advancing previous requests for deferred data element destruction to a current generation queue upon a determination that a new grace period has started; and

placing said new request for deferred destruction on a next generation queue.

3. A method in accordance with claim 2 further including processing the destruction of one or more shared data elements on said current generation queue after starting a new grace period.

4. A method in accordance with claim 1 wherein said reading is performed by an executable task having an associated task structure, and wherein said task structure maintains a reference to said read/write lock that was acquired for reading until release thereof.

5. A method in accordance with claim 1 wherein no acquisition of said read/write lock for reading is performed in the event that said reading is a recursive read operation.

6. A method in accordance with claim 1 wherein said reading comprises disabling preemption and/or hardware interrupts when acquiring and releasing said read/write lock.

7. A method in accordance with claim 1 wherein a rate of acquisition of said read/write locks for writing is determined according to memory availability.

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 perform realtime-safe detection of a grace period for deferring removal of a shared data element until pre-existing references to the data element are removed, and comprising:

a read/write lock for each of said one or more processors;

a read lock/unlock component adapted to;

acquire said processor'"'"'s read/write lock for reading prior to said shared data element being referenced; and

release said read/write lock that was acquired for reading following said shared data element being referenced; and

a grace period controller adapted to;

acquire all of said read/write locks for writing;

start a new grace period; and

release all of said read/write locks.

9. A system in accordance with claim 8 further including:

a callback registration component adapted receive a request for deferred destruction of a shared data element following an update to said data element in a manner that preserves a pre-update version of said data element;

a callback advancer adapted to;

test for the start of a new grace period; and

advance previous requests for deferred data element destruction to a current generation queue upon a determination that a new grace period has started; and

said callback registration component being further adapted to place said new request for deferred destruction on a next generation queue.

10. A system in accordance with claim 9 further including a callback processor adapted to process the destruction of one or more shared data elements on said current generation queue after a new grace period has started.

11. A system in accordance with claim 8 wherein said shared data read lock/unlock component comprises an executable task having an associated task structure, and wherein said task structure maintains a reference to said read/write lock that was acquired for reading until release thereof.

12. A system in accordance with claim 8 wherein said read lock/unlock component is adapted to not acquire said read/write lock for reading in the event that said reading is a recursive read operation.

13. A system in accordance with claim 8 wherein said read lock/unlock component is adapted to disable preemption and/or hardware interrupts when acquiring and releasing said read/write lock.

14. A computer program product for realtime-safe detection of a grace period for deferring the destruction of a shared data element until pre-existing references to the data element are removed, comprising:

one or more machine-readable media;

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

establishing a read/write lock for each of one or more processors;

when reading a shared data element at a processor;

acquiring said processor'"'"'s read/write lock for reading;

referencing said shared data element; and

releasing said read/write lock that was acquired for reading; and

when starting a new grace period;

acquiring all of said read/write locks for writing;

starting a new grace period; and

releasing all of said read/write locks.

15. A computer program product in accordance with claim 14 wherein said means provided by said one or more media are adapted to further program said data processing platform to operate as by:

following an update to a shared data element in a manner that preserves a pre-update version of said data element and a new request for deferred destruction of said data element;

testing for the start of a new grace period;

advancing previous requests for deferred data element destruction to a current generation queue upon a determination that a new grace period has started; and

placing said new request for deferred destruction on a next generation queue.

16. A computer program product in accordance with claim 15 wherein said means provided by said one or more media are adapted to further program said data processing platform to operate as by processing the destruction of one or more shared data elements on said current generation queue after starting a new grace period.

17. A computer program product in accordance with claim 14 wherein said reading is performed by an executable task having an associated task structure, and wherein said task structure maintains a reference to said read/write lock that was acquired for reading until release thereof.

18. A computer program product in accordance with claim 14 wherein no acquisition of said read/write lock for reading is performed in the event that said reading is a recursive read operation.

19. A computer program product in accordance with claim 14 wherein said reading comprises disabling preemption and/or hardware interrupts when acquiring and releasing said read/write lock.

20. A computer program product in accordance with claim 14 wherein a rate of acquisition of said read/write locks for writing is determined according to memory availability.