Back to results
US 11,960,933 B2Granted
Versioned progressive chunked queue for a scalable multi-producer and multi-consumer queue
AssigneeRed Hat, Inc.
InventorFrancesco Nigro
Life of this patent
Estimating the term…
Abstract
A method includes receiving, by a producer thread of a plurality of producer threads, an offer request associated with an item. The producer thread increases a sequence and determines (i) a chunk identifier of a memory chunk from a pool of memory chunks and (ii) a first slot position in the memory chunk to offer the item. The producer thread also writes the item into the memory chunk at the first slot position. Then, a first consumer thread of a plurality of consumer threads determines the first slot position of the item and consumes the item at the first slot position. A second consumer thread consumes another item at a second slot position in the memory chunk and recycles the memory chunk.
Claims20
A method comprising:
- receiving, by a producer thread of a plurality of producer threads, an offer request associated with an item;
- responsive to receiving the offer request, increasing arithmetically, by the producer thread, a sequence according to a fetch-and-add instruction;
- determining, by the producer thread, (i) a chunk identifier, associated with the sequence, of a memory chunk from a pool of memory chunks and (ii) a first slot position, from the sequence, in the memory chunk to offer the item, wherein the sequence contains values corresponding with slot positions and the first slot position is a next slot position in the sequence which corresponds to a second slot within the memory chunk;
- comparing the chunk identifier with a current producer memory chunk;
- walking the current producer memory chunk backwards to match the chunk identifier;
- writing, by the producer thread, the item into the memory chunk at the first slot position;
- determining, by a first consumer thread of a plurality of consumer threads, the first slot position of the item;
- consuming, by the first consumer thread, the item at the first slot position;
- consuming, by a second consumer thread of the plurality of consumer threads, another item at a second slot position in the memory chunk;
- determining, by the second consumer thread referring to a consumer buffer coordinating the plurality of consumer threads, that the memory chunk is recyclable;
- and
- recycling, by the second consumer thread, the memory chunk.
9 more elements
A system comprising:
- a memory configured to store a plurality of memory chunks;
- at least one processor configured to execute a plurality of producer threads and a plurality of consumer threads, wherein a producer thread of the plurality of producer threads is configured to:
- receive an offer request associated with an item,
- responsive to receiving the offer request, arithmetically increase a sequence according to a fetch-and-add instruction,
- determine (i) a chunk identifier, associated with the sequence, of a memory chunk from a pool of memory chunks and (ii) a first slot position, from the sequence, in the memory chunk to offer the item, wherein the sequence contains values corresponding with slot positions and the first slot position is a next slot position in the sequence which corresponds to a second slot within the memory chunk,
- compare the chunk identifier with a current producer memory chunk,
- walk the current producer memory chunk backwards to match the chunk identifier, and
- write the item into the memory chunk at the first slot position;
- wherein a first consumer thread of the plurality of consumer threads is configured to:
- consume the item at the first slot position;
- and
- wherein a second consumer thread of the plurality of consumer threads is configured to:
- consume another item at a second slot position in the memory chunk,
- determine that the memory chunk is recyclable by referring to a consumer buffer coordinating the plurality of consumer threads, and
- recycle the memory chunk.
12 more elements
A method comprising:
- receiving, by a consumer thread of a plurality of consumer threads, a consume request associated with an element;
- responsive to receiving the consume request, reading, by the consumer thread, a consumer sequence and a consumer buffer;
- extracting, by the consumer thread, (i) a chunk identifier, associated with the consumer sequence and (ii) a slot position in a memory chunk from the consumer sequence, wherein the sequence contains values corresponding with slot positions and the first slot position is a next slot position in the sequence which corresponds to a second slot within the memory chunk;
- determining, by the consumer thread, that a position of the element mismatches the slot position in the memory chunk from the consumer sequence;
- determining, by the consumer thread referring to the consumer buffer coordinating the plurality of consumer threads, that the memory chunk is recyclable;
- arithmetically increasing according to a fetch-and-add instruction, by the consumer thread, the consumer sequence;
- and
- consuming, by the consumer thread, the element at the slot position.
5 more elements
Dependencies are inferred from the claim text.