Method and apparatus for atomically accessing a queue in a memory structure where LIFO is converted to FIFO
US5671446A · kind A · utility
Assignee
Inventors
Key dates
| Filing date | Mar 16, 1995 |
| Grant date | Sep 23, 1997 |
| Priority date | — |
| Expiry date | Mar 16, 2015 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F7/785
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
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 lev…
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.