Method and apparatus for atomically accessing a queue in a memory structure where LIFO is converted to FIFO

A computer apparatus with a queue memory structure comprising:

• a digital processor;
• read/write memory coupled to a digital processor;
• means for providing a queue memory structure in said read/write memory, said queue memory structure implementing a last-in-first-out list (LIFO) and a first-in-first-out list (FIFO);
• means for enqueuing a data element to said queue memory structure by atomically adding said data element to said LIFO;
• means for dequeuing a data element from said queue memory structure by atomically removing said data element from said FIFO;
• and
• means for converting said LIFO to a new FIFO when said FIFO is empty.

A method for enqueuing and dequeuing data on a computer system comprising the steps of:

• atomically enqueuing data to a queue memory structure when a call to enqueue is received by said computer system, such that said enqueuing step cannot be interrupted by different enqueuers attempting to enqueue data to said queue memory structure, wherein said step of atomically enqueuing data to said queue memory structure includes inserting said data into a a LIFO;
• and
• atomically dequeuing data from said queue memory structure when a call to dequeue is received by said computer system, such that said dequeuing step cannot be interrupted by different dequeuers attempting to dequeue data from said queue memory structure, wherein said step of atomically dequeuing data from said queue memory structure includes removing said data from a FIFO and converting said LIFO into said FIFO;
• whereby said enqueuing and dequeuing steps are performed without altering the level of interrupts used on said computer system and without risk of deadlock.

A computer system for providing a queue memory structure, the system comprising:

• a LIFO for storing data elements input to said queue memory structure;
• a FIFO list for storing data elements to be output from said queue memory structure;
• means for converting said LIFO to said FIFO;
• a plurality of enqueuers, each enqueuer for storing data elements in said LIFO, wherein one of said enqueuers cannot be interrupted by other enqueuers accessing said queue memory structure when said enqueuer is storing said data elements;
• and
• a plurality of dequeuers, each dequeuer for retrieving data elements from said FIFO, wherein one of said dequeuers cannot be interrupted when retrieving said data elements by other dequeuers accessing said queue memory structure;
• whereby said dam elements are stored and retrieved in a first-in-first-out order without altering the level of interrupts used on said computer system and without risk of deadlock.

A computer readable medium including program instructions for storing and retrieving data from a queue memory structure, wherein a plurality of enqueuers and at least one dequeuer have access to said queue memory structure, said program instructions performing steps comprising:

• (a) allocating a queue memory structure in a memory device, said memory structure having a last-in-first-out list (LIFO) and a first-in-first-out list (FIFO);
• (b) atomically adding a data element to said LIFO from an enqueuer when said dam element is enqueued to said queue memory structure, such that said adding is performed without interruption from other enqueuers adding data elements to said LIFO;
• (c) atomically removing a data element from said FIFO to a dequeuer when said data element is to be dequeued from said queue memory structure;
• and
• (d) converting said LIFO to a new FIFO and storing said new FIFO as said FIFO when said FIFO is empty, said converting and storing step performed by said dequeuer.

A queue memory structure accessible by a plurality of enqueuers and dequeuers implemented in a computer system, the queue memory structure comprising:

• a read/write memory device coupled to said computer system for providing said queue memory structure;
• a LIFO structure implemented in said read/write memory for storing data elements input to said queue memory structure by an enqueuer, wherein said LIFO is atomically accessed by said enqueuer such that said enqueuer cannot be interrupted by other enqueuers accessing said queue memory structure when said enqueuer is storing said data elements;
• a FIFO list implemented in said read/write memory for storing data elements to be output from said queue memory structure by a dequeuer, wherein said LIFO is atomically accessed by said enqueuer such that said enqueuer cannot be interrupted by other enqueuers accessing said queue memory structure when said enqueuer is storing said data elements, and wherein said LIFO is reversed to create said FIFO by said dequeuer when said FIFO is empty;
• and
• a lock flag implemented in a memory device coupled to said computer system that can be set by a dequeuer accessing said queue memory structure, said lock indicating that said queue memory structure is currently being accessed and may not be accessed by different dequeuers while said lock is set,
• whereby said data elements in said queue memory structure are stored and retrieved in a first-in-first-out order without altering the level of interrupts used on said computer system and without risk of deadlock.