Read-copy-update (RCU) operations with reduced memory barrier usage
First Claim
1. 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 need-memory-barrier bits are equal to a first predetermined value, and where a sum of all of the last set of per-processor counters is equal to a second predetermined value,incrementing each of the last set of per-processor need-memory-barrier bits, using the local flip-counter bit;
sending an inter-processor interrupt to execute a memory barrier if needed;
where all of the last set of per-processor need-memory-barrier bits are equal to a second predetermined value,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.
3 Assignments
0 Petitions
Accused Products
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 eliminates the need for memory barriers during such read operations.
-
Citations
20 Claims
-
1. 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 need-memory-barrier bits are equal to a first predetermined value, and where a sum of all of the last set of per-processor counters is equal to a second predetermined value, incrementing each of the last set of per-processor need-memory-barrier bits, using the local flip-counter bit; sending an inter-processor interrupt to execute a memory barrier if needed; where all of the last set of per-processor need-memory-barrier bits are equal to a second predetermined value, 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
11. 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, wherein no memory barriers are executed by the reading tasks. - View Dependent Claims (12, 13, 14, 15)
-
-
16. An article of manufacture comprising:
-
a tangible computer-readable medium; and
,means in the medium for updating and 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, wherein the means does not execute any memory barriers in reading the section of memory. - View Dependent Claims (17, 18, 19, 20)
-
Specification