Method and system for efficient queue management
View Patent ↗Embodiments of the present invention are directed to methods for efficient queue management, and device implementations that incorporate these methods, for systems that include two or more electronic devices that share a queue residing in the memory of one of the two or more electronic devices. In certain embodiments of the present invention, a discard field or bit is included in each queue entry. The bit or field is set to a first value, such as the Boolean value “0,” by a producing device to indicate that the entry is valid, or, in other words, that the entry can be consumed by the consuming device. After placing entries into the queue, the producing device may subsequently remove one or more entries from the queue by setting the discard field or bit to a second value, such as Boolean value “1.” The consuming device removes each entry from the queue, in turn, as the consuming device processes queue entries, discarding, without further processing, those entries with the discard bit or field set to the second value.
1. A queue shared by a producing device and a consuming device, the queue comprising:
a region of an electronic memory allocated for the queue, the memory region containing queue slots, each slot having a size sufficient to store a queue entry, and each queue entry including a discard field;
additional memory locations that store values corresponding to a producer index, a consumer index, and a queue length;
producer-device logic that queues a queue entry to the queue and correspondingly updates the producer index; and
consumer-device logic that dequeues an entry from the queue and correspondingly updates the consumer index, processing the dequeued entry when the contents of the discard field of the entry indicate that the entry should be processed, and discarding the entry when the contents of the discard field of the entry indicate that the entry should be discarded.
2. The queue of claim 1 wherein the queue operates as a circular queue, with each of the producer index and the consumer index updated by incrementing the stored value corresponding to the index and computing the remainder after division by the queue size.
3. The queue of claim 1 wherein the queue and the value corresponding to the consumer index are stored in a memory within the producer device, and the value corresponding to the producer index is stored in a memory within the consumer device.
4. The queue of claim 1 wherein the value corresponding to the consumer index is stored in a memory within the producer device, and the queue and the value corresponding to the producer index are stored in a memory within the consumer device.
5. The queue of claim 1 wherein the queue, the value corresponding to the consumer index, and the value corresponding to the producer index are stored in a memory device separate from the consumer device and the producer device.
6. The queue of claim 1 wherein the queue, the value corresponding to the consumer index, and the value corresponding to the producer index are stored in one or more of:
a memory device separate from the consumer device and the producer device;
consumer-device memory; and
producer-device memory.
7. The queue of claim 1 wherein, when the producer device queues an entry to the queue, the producer device sets the discard field of the entry to indicate that the entry should be consumed by the consuming device.
8. The queue of claim 7 wherein, when the producer device determines, after queuing an entry to the queue, that the entry should not be processed by the consuming device, the producer device sets the discard field of the entry to indicate that the entry should not be consumed by the consuming device.
9. The queue of claim 8 wherein, when the producer device determines, after queuing an entry to the queue, that the entry should not be processed by the consuming device, the producer first freezes the queue, prior to setting the discard field of the entry to indicate that the entry should not be consumed by the consuming device.
10. The queue of claim 1 wherein the consumer device is a single integrated circuit.
11. The queue of claim 1 wherein the producer device is a single integrated circuit.
12. A method of efficiently managing a queue shared by a producing device and a consuming device, the method comprising:
providing a queue in a region of an electronic memory allocated for the queue, the memory region containing queue slots, each slot having a size sufficient to store a queue entry, and each queue entry including a discard field;
providing additional memory locations that store values corresponding to a producer index, a consumer index, and a queue length;
queuing a queue entry, by a producing device, to the queue and correspondingly updating the producer index; and
dequeuing an entry from the queue, by a consuming device, and correspondingly updating the consumer index, processing the dequeued entry when the contents of the discard field of the entry indicate that the entry should be processed, and discarding the entry when the contents of the discard field of the entry indicate that the entry should be discarded.
13. The method of claim 12 further comprising:
operating the queue as a circular queue, updating each of the producer index and the consumer index by incrementing the stored value corresponding to the index and computing the remainder after division by the queue size.
14. The method of claim 12 further comprising:
storing the queue and the value corresponding to the consumer index in a memory within the producer device; and
storing the value corresponding to the producer index in a memory within the consumer device.
15. The method of claim 12 further comprising:
storing the value corresponding to the consumer index in a memory within the producer device; and
storing the value corresponding to the producer index in a memory within the consumer device.
16. The method of claim 12 further comprising:
storing the queue, the value corresponding to the consumer index, and the value corresponding to the producer index in a memory device separate from the consumer device and the producer device.
17. The method of claim 12 further comprising:
storing the value corresponding to the consumer index and the value corresponding to the producer index in one or more of:
a memory device separate from the consumer device and the producer device;
a memory within the consumer device; and
a memory within the producer device.
18. The method of claim 12 further comprising:
when queuing an entry to the queue, setting the discard field of the entry to indicate that the entry should be consumed by the consuming device.
19. The method of claim 18 further comprising:
after determining, following queuing of an entry to the queue, that the entry should not be processed by the consuming device, setting the discard field of the entry to indicate that the entry should not be consumed by the consuming device.
20. The method of claim 19 further comprising:
prior to setting the discard field of the entry to indicate that the entry should not be consumed by the consuming device, freezing the queue.
21. The method of claim 12 wherein the consumer device is a single integrated circuit.
22. The method of claim 12 wherein the producer device is a single integrated circuit.