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

• US 20080140951A1
• Filed: 01/27/2008
• Published: 06/12/2008
• Est. Priority Date: 03/24/2006
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Inventors: McKenney, Paul E., Bhattacharya, Suparna
• Granted Patent: US 8,055,860 B2
• Time in Patent Office: Days
• US Class Current: 711/154
• CPC Class Codes: G06F 9/3851 from multiple instruction streams, e.g. multistreaming
• CPC Class Codes: G06F 9/522 Barrier synchronisation
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

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.

Claims

1. A computerized system comprising:

a plurality of processors;

memory accessible by the processors;

one or more updating tasks to update contents of a section of the memory by using a first set and a second set of per-processor counters, a first set and a second set of per-processor need-memory-barrier bits, and a global flip-counter bit specifying which of the first set or the 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; and

,

one or more reading tasks to read the contents of the section of the memory by using the first set and the second set of per-processor counters, the first set and the second set of per-processor need-memory-barrier bits, and the global flip-counter bit.

2. An article of manufacture comprising:

a tangible computer-readable medium; and

,

means in the medium for updating and/or reading a section of memory accessible by a plurality of processors by using a first set and a second set of per-processor counters, a first set and a second set of per-processor need-memory-barrier bits, and a global flip-counter bit specifying which of the first set or the second set of the per-processor counters and per-processor need-memory-barrier bits is a current set and which is a last set.