Patent ID: 7389291

Claim:
A method for performing computer system operations, comprising: implementing a concurrent first-in-first-out (FIFO) queue as a dynamically-sized doubly-linked list in a memory of a computer system; enqueuing a node in the concurrent FIFO queue, wherein the enqueuing comprises: performing an enqueue operation until a single-word synchronization operation is successful, the enqueue operation comprising: using a store operation to store a pointer to another node in a next field of the node, wherein the another node is pointed to by a tail pointer; using the single-word synchronization operation to attempt to store a pointer to the node in the tail pointer; and using a store operation to store a pointer to the node in a previous field of the another node when the single-word synchronization operation is successful, wherein the single-word synchronization operation is the only synchronization operation used during the enqueuing; and dequeuing an enqueued node, wherein the dequeueing comprises: performing a dequeue operation until one selected from a group consisting of the single-word synchronization operation is successful and the queue is empty, the dequeue operation comprising: determining whether a previous pointer of the enqueued node is inconsistent; traversing a plurality of next pointers in the doubly-linked list to correct inconsistent previous pointers in the doubly-linked list when the previous pointer is inconsistent; and using the single-word synchronization operation to attempt to store a pointer to another node in a head pointer, wherein the another node is pointed to by a previous pointer of the enqueued node, wherein the single-word synchronization operation is the only synchronization operation used during the dequeuing.