Method and apparatus for atomically accessing a queue in a memory

Abstract

A method and apparatus for storing and retrieving data from a queue implemented on a computer system. A queue memory structure is allocated in a memory device, the queue including a a last-in-fast-out (LIFO) and a first-in-first-out (FIFO). A data element is atomically added to the LIFO when the data element is enqueued to the queue structure, and a data element is atomically removed from the FIFO when the data element is to be dequeued from the queue, thus preventing concurrent processes from disordering the data in the queue. When the FIFO becomes empty, the LIFO is converted to a new FIFO, and this new FIFO is stored in place of the old (empty) FIFO. In one embodiment, a lock is set and the LIFO is converted to a new FIFO only when the lock is previously determined to be clear to prevent additional dequeuers from interrupting a dequeuing process. A high-priority data element can be atomically added to a head list that stores the data element at the front of the queue memory structure. The present invention allows multiple enqueuers and dequeuers on one or more processing elements, including interrupt handlers and other programs, to access the queue without altering interrupt levels and without risk of deadlock.