Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1998-08-20
2001-01-09
Banankhah, Majid (Department: 2755)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
C710S052000, C710S053000
Reexamination Certificate
active
06173307
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The field of the invention relates to queuing systems in a computer system. Specifically, the present invention relates to multiple-reader multiple-writer queues.
2. Description of Related Art
The circular queue invention herein provides a mechanism and method for producers of fixed-size data items to deliver those items to consumers even under circumstances in which multiple producers and multiple consumers share the same queue. Any producer or consumer can be permitted to preempt any producer or consumer at any time without interfering with the correctness of the queue.
Current queue implementations suffer from one or more disadvantages that stem from the need to maintain consistency of the queue data structures in spite of that fact that multiple agents manipulate them:
1. Queue implementations based on linked lists invariably involve a “critical region” within which several links must be manipulated indivisibly with respect to one another.
2. Queue implementations based on simple circular buffers avoid these critical regions by limiting themselves to a single variable being manipulated exclusively by either a reader or a writer, not both, but as a result they become limited to a single producer and a single consumer.
3. Avoiding the limitations of (1) and (2) usually involves preventing other agents such as interrupt handlers or preemptively scheduled processes from preempting an agent while it is in a critical region. On most prior art processors, instructions used to enforce critical regions require an additional privilege level not usually available to user code.
4. Avoiding the privilege limitation of (3) involves a performance burden in the form of either a procedure call to an operating system function that enforces critical regions or fault-handling code that “traps” some privileged instructions and simulates them.
5. In some cases it is possible to use a “spin-lock” implementation of critical regions without special privilege or performance overhead by appropriate use of a (non-privileged) “indivisible test-and-set” instruction. The use of a “spin-lock” is well known in the art. However, these cases are limited to ones in which the competing agents are independently scheduled, e.g., running on different processors or in a preemptively scheduled multitasking environment.
Thus, a queue supporting multiple producers and multiple consumers is needed.
SUMMARY OF THE INVENTION
The circular queue invention herein provides a mechanism and method for producers of fixed-size data items to deliver those items to consumers even under circumstances in which multiple producers and multiple consumers share the same queue. Any producer or consumer can be permitted to preempt any producer or consumer at any time without interfering with the correctness of the queue.
The present invention disclosed herein avoids the limitations of the prior art. The invention supports multiple readers and multiple writers. Any reader can preempt any other reader or writer. Any writer can preempt any other writer or reader. The implementation uses a combination of indivisible test-and-set and indivisible exchange-add instructions to enforce consistency. With the indivisible exchange-add and indivisible test-and-set instructions available on most conventional processors, no privileged instructions are required, so there is no performance penalty due to operating system overhead. There are no “critical sections” outside of the inherent indivisibility of the “indivisible” instructions, so even in cases where a task running on a single processor is preempted by an interrupt handler that must manipulate the queue before it returns control, both preempted and preempting queue operations succeed and the queue integrity is preserved. Indivisibility is typically implemented at the memory bus arbitration level, so this invention is applicable to concurrent, multiple-processor, shared-memory systems as well as preemptive, single-processor systems.
REFERENCES:
patent: 4914570 (1990-04-01), Peacock
patent: 4916658 (1990-04-01), Lee et al.
patent: 5003471 (1991-03-01), Gibson
patent: 5093912 (1992-03-01), Dong et al.
patent: 5125083 (1992-06-01), Fite et al.
patent: 5155820 (1992-10-01), Gibson
patent: 5175829 (1992-12-01), Stumpf et al.
patent: 5867734 (1999-02-01), Drews
patent: 5922057 (1999-07-01), Hoet
patent: 5925099 (1999-07-01), Futral et al.
Giao N. Pham et al., “A High Throughput, Asynchronous, Dual Port FIFO Memory Implemented in ASIC Technology,” 1989, pp. P3-1.1 to P3-1.4.
Ahmed E. Barbour et al., “A Parallel, High Speed Circular Queue Structure,” 1990, pp. 1089-1092.
Banankhah Majid
Blakely , Sokoloff, Taylor & Zafman LLP
Intel Corporation
LandOfFree
Multiple-reader multiple-writer queue for a computer system does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Multiple-reader multiple-writer queue for a computer system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multiple-reader multiple-writer queue for a computer system will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2434741