Lock-free bounded FIFO queue mechanism
View Patent ↗A system includes a processor and a size bounded first-in first-out (FIFO) memory that is connected to the processor and a display is connected to the processor. A managing process to run on the processor to manage the FIFO memory structure. The FIFO memory includes a counter portion and a value portion for each of a tail portion and a head portion, and the managing process is non-blocking. The counter portion is used as a timestamp to maintain FIFO order.
1. A machine-accessible medium containing instructions that, when executed, cause a machine to:
perform a managing process to manage a size bounded first-in first-out (FIFO) memory structure having a head portion and a tail portion, the memory structure to store a plurality of data structures, said managing process including instructions for:
adding a data structure to the tail portion, adjusting a counter portion of the tail portion if the tail portion is empty and using the counter portion as a timestamp to maintain FIFO order,
removing a data structure from the head portion and inserting an invalid value for the head portion if a timestamp associated with the head portion matches a current timestamp, wherein the data structure includes the counter portion and a value portion, and said managing process is non-blocking.
2. The machine-accessible medium of claim 1 , wherein the adding and the removing occur concurrently.
3. The machine-accessible medium of claim 1 , wherein the counter portion has a size equal to three times a size of the value portion.
4. The machine-accessible medium of claim 1 , wherein an order of data structures added to the memory structure is tracked by the timestamp.
5. The machine-accessible medium of claim 1 , wherein the adding and the removing each include a single compare and swap instruction.
6. The machine-accessible medium of claim 1 , wherein a value equal to an address of one of the tail portion and the head portion, modulus a size of the FIFO memory structure to index the FIFO memory structure.
7. A machine-accessible medium containing instructions that, when executed, cause a machine to:
perform a queue managing process to manage a size bounded first-in first-out (FIFO) memory structure having a head portion and a tail portion, the memory structure to store a plurality of data structures, said managing process including instructions for:
enqueueing a data structure, adjusting a counter portion of the tail portion if the tail portion is empty and using the counter portion as a timestamp to maintain FIFO order,
dequeueing a data structure from the head portion and inserting an invalid value for the head portion if a timestamp associated with the head portion matches a current timestamp, wherein said queue managing process is non-blocking.
8. The machine-accessible medium of claim 7 , wherein the enqueueing and the dequeueing occur concurrently.
9. The machine-accessible medium of claim 7 , wherein the data structure having a timestamp portion and a value portion, the timestamp portion having a size equal to three times a size of the value portion.
10. The machine-accessible medium of claim 7 , wherein an order of data structures added to the queue is tracked by the timestamp.
11. The machine-accessible medium of claim 7 , wherein the enqueueing and the dequeueing each include a single compare and swap instruction.
12. The machine-accessible medium of claim 7 , wherein a value equal to an address of one of the tail portion and the head portion, modulus a size of the FIFO memory structure to index the FIFO memory structure.
13. A system comprising:
a processor;
a size bounded first-in first-out (FIFO) memory coupled to the processor;
a display coupled to the processor;
a managing process to run on the processor to manage the FIFO memory structure;
wherein the FIFO memory includes a counter portion and a value portion for each of a tail portion and a head portion, said managing process is non-blocking, and the counter portion is used as a timestamp to maintain FIFO order.
14. The system of claim 13 , wherein the managing process operates to add a data structure to the tail portion, and to adjust a counter portion of the tail portion if the tail portion is empty.
15. The system of claim 13 , wherein the managing process is to remove a data structure from the head portion and insert an invalid value for the head portion if a timestamp associated with the head portion matches a current timestamp.
16. The system of claim 13 , wherein adding a data structure to the head portion and removing another data structure from the tail portion occur concurrently.
17. The system of claim 13 , wherein the counter portion has a size larger than a size of the value portion.
18. The system of claim 13 , wherein the timestamp tracks an order of data structures added to the FIFO memory.
19. The system of claim 13 , wherein a value equal to an address of a size of the FIFO memory modulus one of the tail portion and the head portion to index the FIFO memory.
20. A machine implemented method comprising:
adding a data structure to a tail portion of a first-in-first-out (FIFO) memory structure,
adjusting a counter portion of the tail portion if the tail portion is empty and using the counter portion as a timestamp to maintain FIFO order,
removing a data structure from a head portion of the FIFO and inserting an invalid value for the head portion if a timestamp associated with the head portion matches a current timestamp,
wherein the data structure includes the counter portion and a value portion.
21. The machine implemented method of claim 20 , wherein the adding and the removing occur concurrently.
22. The machine implemented method of claim 20 , wherein an order of data structures added to the memory structure is tracked by the timestamp.