US 7,353,346 B2Granted

Read-copy-update (RCU) operations with reduced memory barrier usage

AssigneeInternational Business Machines Corporation

InventorsPaul E. McKenney, Suparna Bhattacharya

Life of this patent

Estimating the term…

Loading patent…

Abstract

Read-copy-update (RCU) is performed within real-time and other types of systems, such that memory barrier usage within RCU is reduced. A computerized system includes processors, memory, updaters, and readers. The updaters update contents of a section of the memory by using first and second sets of per-processor counters, first and second sets of per-processor need-memory-barrier bits, and a global flip-counter bit. The global flip-counter bit specifies which of the first or second set of the per-processor counters and the per-processor need-memory-barrier bits is a current set, and which is a last set. The readers read the contents of the section of the memory by using the first and second sets of per-processor counters, the first and second sets of per-processor need-memory-barrier bits, and the global flip-counter bit, in a way that significantly reduces the need for memory barriers during such read operations.

Claims18

Dependent claims

A method comprising:

to update contents of a section of memory,
copying a global flip-counter bit to a local flip-counter bit, the global flip-counter bit specifying which of a first set of per-processor counters and a second set of per-processor counters is a current set of per-processor counters and which is a last set of per-processor counters, the global flip-counter bit also specifying which of a first set of per-processor need-memory-barrier bits and a second set of per-processor need-memory-barrier bits is a current set of per-processor need-memory-barrier bits and which is a last set of per-processor need-memory-barrier bits;
where attempting to acquire a flip-counter-bit lock on the global-flip-counter bit is successful,
where the global flip-counter bit has not changed while acquiring the flip-counter-bit lock,
where all of the last set of per-processor counters are zero, such that none of a plurality of threads being executed by a plurality of processors corresponding to the last set of per-processor counters are currently executing a critical read operation on the section of memory,
where all of the last set of per-processor need-memory-barrier bits are zero, such that none of the processors needs to execute a memory barrier,
setting each of the current set of per-processor need-memory-barrier bits to one, using the local flip-counter bit;
inverting the global flip-counter bit;
and,
releasing the flip-counter-bit lock.

7 more elements

A method comprising:

to update contents of a section of memory,
copying a global flip-counter bit to a local flip-counter bit, the global flip-counter bit specifying which of a first set of per-processor counters and a second set of per-processor counters is a current set of per-processor counters and which is a last set of per-processor counters, the global flip-counter-bit also specifying which of a first set of per-processor need-memory-barrier bits and a second set of per-processor need-memory-barrier bits is a current set of per-processor need-memory-barrier bits and which is a last set of per-processor need-memory-barrier bits;
where attempting to acquire a flip-counter-bit lock on the global-flip-counter bit is successful,
where the global flip-counter bit has not changed while acquiring the flip-counter-bit lock,
where any of the last set of per-processor need-memory-barrier bits is equal to zero,
where a sum of all of the last set of per-processor counters is equal to zero,
incrementing each of the last set of per-processor need-memory-barrier bits, using the local flip-counter bit;
where all of the last set of per-processor need-memory-barrier bits are equal to two,
setting each of the current set of per-processor need-memory-barrier bits to zero, using the local flip-counter bit,
inverting the global flip-counter bit;
and,
releasing the flip-counter-bit lock.

9 more elements

Dependencies are inferred from the claim text.

Facts

Application: 11/388,364Filed 24 Mar 2006
Published: US 2007/0226431 A127 Sep 2007
Granted: 1 Apr 2008
Term ends: Not estimatedThe source records don’t support an estimate.

Classification4 codes

G06F 9/3851
Instruction issuing, e.g. dynamic instruction scheduling or out of order instruction execution: from multiple instruction streams, e.g. multistreaming
G06F 9/522
Program synchronisation; Mutual exclusion, e.g. by means of semaphores: barrier synchronisation
G06F 9/526
Program synchronisation; Mutual exclusion, e.g. by means of semaphores: mutual exclusion algorithms
G06F
Computing and data processing