Patent ID: 6304924
Filing Date: 2001-10-16
Classification: G06F

Abstract:
A method of building a highly-concurrent first-in-first-out (FIFO) queue, wherein memory space of said FIFO queue is fully utilized, and said FIFO queue permits one or more readers and one writer to simultaneously access portions of memory space of said FIFO queue without utilizing synchronization primitives and/or special instructions, the method comprising the steps of:defining a FIFO queue in shared memory;creating reader pointers and a writer pointer for pointing to designated memory spaces associated with said FIFO queue, wherein each said reader pointer is associated with a particular reader that reads data from said designated memory spaces of said FIFO queue, and said writer pointer is associated with a writer that writes data to said designated memory spaces associated with said FIFO queue;defining a common direction in which said reader pointers and said writer pointer successively traverse adjacent said memory spaces;initializing said readers and writers with respect to a common memory space of said FIFO queue, wherein said writer writes data to said common memory space and said readers read data from said common memory space;writing new data to at least one but not greater than the number of memory spaces of said FIFO queue that are successively adjacent to and in said common direction with respect to said common memory space utilized to initialize said FIFO queue;updating said writer pointer to point to said memory space associated with most newly written data;utilizing atomic operations for reading data from and writing data to said memory spaces of said FIFO queue, wherein said writer actively or passively checks and waits for the successor of said writer pointer to be behind each said reader pointer and, upon satisfying this condition, said writer writes data to a memory space associated with said successor of said writer pointer, and said writer pointer is then modified to be the successor of itself; andin conjunction with said writer, said readers actively or passively checking and waiting for the successor of its associated reader pointer to be behind said writer pointer and, whereupon each reader that satisfies this condition reads data from a memory space associated with said successor of each said reader's pointer, computations being performed with said data, and each said reader's pointer is then being modified to be the successor of itself.