Method and apparatus for atomically accessing a queue in a memor

Details Method and apparatus for atomically accessing a queue in a memor Method and apparatus for atomically accessing a queue in a memor

1995-03-16

1997-09-23

Ellis, Richard L.

395250, 395873, 395732, 395736, G06F 1300, G06F 700

Patent

active

056714467

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.

REFERENCES:
patent: 4298954 (1981-11-01), Bigelow et al.
patent: 5111385 (1992-05-01), Hattori
patent: 5502822 (1996-03-01), Takebe
patent: 5539896 (1996-07-01), Lisle
PowerPC 601 RISC Microprocessor User s Manual, 1993, Chapter 3, pp. 53-55, 10-105, 10-197, Appendxi G.
MC68020 32-Bit Microprocessor User s Manual, 1985, 1984 by Motorola, Inc. Appendix B, pp. 54,55.
VAX Hardware Handbook by Digital, 1980, Chapter 17, pp. 311-317.
VAX 11 Architecture Handbook by Digital, 1979,, pp. 188-195.

Affiliated with

Also associated with

Rating

Method and apparatus for atomically accessing a queue in a memor does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method and apparatus for atomically accessing a queue in a memor, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for atomically accessing a queue in a memor will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1942523