US5867734A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Multiple-reader multiple-writer queue for a computer system
Assignee: Intel Corp
•
Filing: 1997-07-08
•
Granted: 1999-02-02
•
Expires: 2017-07-08
Abstract
Abstract 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.
Inventors
- 👤 Paul Drews
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 20:34
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/46; G06F9/52
Claims Analysis
Total Claims: 18
Claim 1
Independent Claim
330 words
A multiple-reader, multiple-writer circular queue mechanism comprising: a storage element including, a set of instructions and data for generating and maintaining a circular queue, said circular queue having, a) a plurality of slots for storage of resources. b) boundary markers marking boundaries in the circular queue dividing said circular queue into three different regions including, i) a first region with a next slot of said plurality of slots available for writing resources, said next slot not yet acquired for writing, boundaries for said region being marked by a next-available marker, ii) a second region with a next slot of said plurality of slots available for reading, said next slot not yet ready for reading, boundaries for said region being marked by a next-ready marker, ii) a third region in between said first and second regions with slots to which resources are in the process of being written in, c) a writing-available slot count for indicating the number of said plurality of slots available for writing, said writing-available slot count coupled to said next-available marker, d) a reading-available slot count for indicating the number of said plurality of slots available for reading, said reading-available slot count coupled to said next-ready marker, and said set of instructions and data for acquiring said plurality of slots, said set of instructions and data executing an indivisible processor instruction for decrementing said writing-available slot count, and executing an indivisible processor instruction for incrementing said next-available marker, placing said resource in the slot indicated by said next-available marker, and making a slot with said resource available for reading, said slot indicated by said next-ready marker, and executing an indivisible processor instruction for modifying said consumer-available slot count, said set of instructions and data acquiring a mutual exclusion token, to limit access to said plurality of slots available for writing to only one source of writing said resources and a processor coupled to said storage element, said processor executing said set of instructions and manipulating said data.
Claim 2
Dependent Claim
330 words
A multiple-reader, multiple-writer circular queue mechanism comprising: a storage element including, a set of instructions and data for generating and maintaining a circular queue, said circular queue having, a) a plurality of slots for storage of resources. b) boundary markers marking boundaries in the circular queue dividing said circular queue into three different regions including, i) a first region with a next slot of said plurality of slots available for writing resources, said next slot not yet acquired for writing, boundaries for said region being marked by a next-available marker, ii) a second region with a next slot of said plurality of slots available for reading, said next slot not yet ready for reading, boundaries for said region being marked by a next-ready marker, ii) a third region in between said first and second regions with slots to which resources are in the process of being written in, c) a writing-available slot count for indicating the number of said plurality of slots available for writing, said writing-available slot count coupled to said next-available marker, d) a reading-available slot count for indicating the number of said plurality of slots available for reading, said reading-available slot count coupled to said next-ready marker, and said set of instructions and data for acquiring said plurality of slots, said set of instructions and data executing an indivisible processor instruction for decrementing said writing-available slot count, and executing an indivisible processor instruction for incrementing said next-available marker, placing said resource in the slot indicated by said next-available marker, and making a slot with said resource available for reading, said slot indicated by said next-ready marker, and executing an indivisible processor instruction for modifying said consumer-available slot count, said set of instructions and data acquiring a mutual exclusion token, to limit access to said plurality of slots available for writing to only one source of writing said resources and a processor coupled to said storage element, said processor executing said set of instructions and manipulating said data.
Claim 3
Dependent Claim
22 words
The multiple-reader, multiple-writer queue mechanism as claimed in claim 1 wherein said set of instructions and data executes an indivisible processor instruction.
Claim 4
Dependent Claim
33 words
The multiple-reader, multiple-writer queue mechanism as claimed in claim 1 wherein said slot acquired by said set of instructions and data is acquired by one and only one source of writing said resources.
Claim 5
Dependent Claim
46 words
The multiple-reader, multiple-writer queue mechanism as claimed in claim 1 further including a plurality of boolean values, a distinct boolean value of said plurality of boolean values associated with each slot of said plurality of slots, said distinct boolean value indicating if said slot is busy.
Claim 6
Dependent Claim
35 words
The multiple-reader, multiple-writer queue mechanism as claimed in claim 4 wherein said set of instructions and data examining said plurality of booleans starting from a slot indicated by said next-ready marker for a busy indication.
Claim 7
Dependent Claim
26 words
The multiple-reader, multiple-writer queue mechanism as claimed in claim 1 wherein said set of instructions and data releasing said mutual exclusion after modifying said next-ready marker.
Claim 8
Dependent Claim
82 words
The multiple-reader, multiple-writer queue mechanism as claimed in claim 1 further including a plurality of boolean values, a distinct boolean value of said plurality of boolean values being associated with each slot of said plurality of slots, said distinct boolean value indicating if said slot is busy, said multiple-reader, multiple-writer queue further including means for releasing said mutual exclusion token after modifying said next-ready marker, said distinct boolean value being examined after said means for releasing has released said mutual exclusion token.
Claim 9
Independent Claim
180 words
A method for a multiple-reader, multiple-writer queue comprising the steps of: indicating a first region with a next slot of said plurality of slots available for writing, but not yet acquired for writing, said indicating being performed by a next-available marker, said next-available marker placed between said first region and a third region having slots to which said resources are in the process of being written in; indicating a second region with a next slot of said plurality of slots available for reading, but not yet made ready for reading, said indicating being performed by a next-ready marker, said next-ready marker placed between said third region with said slots to which said resources are in the process of being written in and said second region; indicating the number of said plurality of slots available for writing; indicating the number of said plurality of slots available for reading; acquiring a slot for a resource, said resource in the slot indicated by said next-available marker; and making a slot with a resource available for reading, said slot indicated by said next-ready marker.
Claim 10
Independent Claim
180 words
A method for a multiple-reader, multiple-writer queue comprising the steps of: indicating a first region with a next slot of said plurality of slots available for writing, but not yet acquired for writing, said indicating being performed by a next-available marker, said next-available marker placed between said first region and a third region having slots to which said resources are in the process of being written in; indicating a second region with a next slot of said plurality of slots available for reading, but not yet made ready for reading, said indicating being performed by a next-ready marker, said next-ready marker placed between said third region with said slots to which said resources are in the process of being written in and said second region; indicating the number of said plurality of slots available for writing; indicating the number of said plurality of slots available for reading; acquiring a slot for a resource, said resource in the slot indicated by said next-available marker; and making a slot with a resource available for reading, said slot indicated by said next-ready marker.
Claim 11
Dependent Claim
66 words
The method of claim 8 wherein said step of acquiring further comprises the steps of: executing an indivisible processor instruction for decrementing said number of said plurality of slots that is available for use by a producer; and executing an indivisible processor instruction for incrementing the number of slot of a plurality of slots for storage of resources that is available for use by a producer.
Claim 12
Dependent Claim
27 words
The method of claim 9 further comprising the step of releasing said mutual exclusion after modifying said slot indicated as being available for use by a consumer.
Claim 13
Dependent Claim
64 words
The method of claim 8 wherein said step of making a slot with a resource available to a consumer further comprises the steps of: acquiring a mutual exclusion token, said mutual exclusion token being held by one and only one producer; and executing an indivisible processor instruction for modifying said number of said plurality of slots that is available for use by a consumer.
Claim 14
Dependent Claim
24 words
The method of claim 11 wherein said step of acquiring a mutual exclusion token further comprises the step of executing an indivisible processor instruction.
Claim 15
Dependent Claim
16 words
The method of claim 9 wherein said slot is acquired by one and only one producer.
Claim 16
Dependent Claim
45 words
The method of claim 9 further comprises the step of including a plurality of boolean values, a distinct boolean value of said plurality of boolean values associated with each slot of said plurality of slots, said distinct boolean value indicating if said slot is busy.
Claim 17
Dependent Claim
28 words
The method of claim 14 further comprising the step of examining said plurality of booleans starting from said slot indicated as being available for use by a consumer.
Claim 18
Dependent Claim
89 words
The method of claim 8 further comprising the step of including a plurality of boolean values, a distinct boolean value of said plurality of boolean values being associated with each slot of said plurality of slots, said distinct boolean value indicating if said slot is busy, said multiple-reader, multiple-writer queue further including means for releasing said mutual exclusion token after modifying said slot indicated as being available for use by a consumer, said distinct boolean value being examined after said step of releasing has released said mutual exclusion token.
References Cited (Backward Citations)
US4914570A
Cited
US4916658A
Cited
US5003471A
Cited
US5175829A
Cited
US5125083A
Cited
US5155820A
Cited
US5093912A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-02-01 | 2002-08-03 | 2003-02-02 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-02-01 | 2006-08-03 | 2007-02-02 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-02-01 | 2010-08-03 | 2011-02-02 | $7700.00 | Window Closed / Lapsed |