Patent US2294748A successfully refreshed from Google Patents.
Patent US3112909A successfully refreshed from Google Patents.
Patent US3647175A successfully refreshed from Google Patents.
Patent US5872938A successfully refreshed from Google Patents.
US5872938A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Service priority queue implemented with ordered sub-queues and sub-queue pointers pointing to last entries in respective sub-queues
Assignee: International Business Machines Corp
•
Filing: 1996-06-28
•
Granted: 1999-02-16
•
Expires: 2016-06-28
Abstract
Abstract A priority queue structure and algorithm for managing the structure which in most cases performs in constant time. In other words, most of the time the inventive algorithm performs its work in an amount of time that is independent on the number of priority classes or elements that exist in the queue. The queue itself consists of a linked list of elements ordered into subqueues corresponding to priority classes, with higher priority subqueues appearing earlier in the queue. An array of priority pointers contains an entry for each subqueue that points to the last element of each subqueue. Elements are removed for processing from the top of the queue. Removal takes constant time. Items are inserted into an appropriate subqueue by linking it at the end of its respective subqueue. The only case that requires a variable amount of time depending on the length of the queue and the number of priority classes occurs when an item is added to an empty subqueue which is of lower priority than the element at the top of the queue. All subsequent additions to that subqueue consume constant time until the subqueue becomes empty once again. A feature of the invention prevents the possibility of perpetually locking out lower priority items in the queue by promoting the priority of a preempted item residing directly below a newly inserted item on the queue.
Inventors
- 👤 Byron A. Williams
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 04:03
CPC Classifications
H; H04; H04L; H04L49/00; H04L49/90; H04L49/901; G; G06; G06F; G06F16/00; G06F16/90; G06F16/901; G06F16/9024; H04L47/00; H04L47/50; H04L47/62; H04L47/6215; H04L49/9021
Claims Analysis
Total Claims: 25
Claim 1
Independent Claim
353 words
A method of administering a service priority queue structure, wherein the structure includes a queue partitioned into subqueues corresponding to different priorities of elements to be serviced from the queue and ordered within the queue according to the respective priorities of the subqueues, a priority pointer array that contains a pointer for each subqueue that points to the last entry in respective subqueue, and further wherein each element of the queue comprises a next pointer to the next element in the queue if any and a back pointer which for each last entry of a subqueue points to the respective entry in the priority pointer array. said method comprising the steps of determining the priority class of a new element arriving for insertion into the queue inserting the new element as the last entry of the subqueue corresponding to the determined priority class of the new element, and periodically servicing the priority queue by removing the top entry from the queue, wherein the priority queue structure further includes a head pointer that points to the first element on the queue and the step of inserting the new entry further comprises determining if the subqueue corresponding to the priority class of the new element is empty, if the subqueue is empty, initializing the back pointer of the new element to point to the corresponding subqueue pointer of the priority pointer array and initializing the corresponding pointer of the priority pointer array to point to the new element, determining from the head pointer if the queue is marked as empty, if the queue is marked as empty, initializing the head pointer to point to the new element, if the queue is not marked as empty, determining if the priority class of the new element is higher than that of the first element on the queue, if the priority class of the new element is higher than that of the first element on the queue, initializing the next pointer of the new element to point to the present element at the top of the queue, and initializing the head pointer to point to the new element.
Claim 2
Independent Claim
353 words
A method of administering a service priority queue structure, wherein the structure includes a queue partitioned into subqueues corresponding to different priorities of elements to be serviced from the queue and ordered within the queue according to the respective priorities of the subqueues, a priority pointer array that contains a pointer for each subqueue that points to the last entry in respective subqueue, and further wherein each element of the queue comprises a next pointer to the next element in the queue if any and a back pointer which for each last entry of a subqueue points to the respective entry in the priority pointer array. said method comprising the steps of determining the priority class of a new element arriving for insertion into the queue inserting the new element as the last entry of the subqueue corresponding to the determined priority class of the new element, and periodically servicing the priority queue by removing the top entry from the queue, wherein the priority queue structure further includes a head pointer that points to the first element on the queue and the step of inserting the new entry further comprises determining if the subqueue corresponding to the priority class of the new element is empty, if the subqueue is empty, initializing the back pointer of the new element to point to the corresponding subqueue pointer of the priority pointer array and initializing the corresponding pointer of the priority pointer array to point to the new element, determining from the head pointer if the queue is marked as empty, if the queue is marked as empty, initializing the head pointer to point to the new element, if the queue is not marked as empty, determining if the priority class of the new element is higher than that of the first element on the queue, if the priority class of the new element is higher than that of the first element on the queue, initializing the next pointer of the new element to point to the present element at the top of the queue, and initializing the head pointer to point to the new element.
Claim 3
Dependent Claim
92 words
The method of claim 1 further comprising the steps of if the priority class of the new element is not higher than that of the first element on the queue, searching the priority pointer array for the first subqueue of priority higher than that of the new element that is not empty and initializing the next pointer of the last element of that subqueue to point to the new entry and initializing the next pointer of the new element to point to the next entry in the queue following the new element.
Claim 4
Dependent Claim
40 words
The method of claim 1 further comprising the steps of determining if the new element preempts a present element in the queue, if the new element preempts a present element in the queue, promoting the priority of the preempted element.
Claim 5
Dependent Claim
136 words
The method of claim 3 wherein each queue element further comprises a priority counter field, said method further comprising initializing the priority counter of a new element to a first priority value determined by a prescribed function of the priority class of the new element, said priority value being one of a set of priority values that are defined to reside in the priority class of the new element, and the step of promoting a preempted element further comprises setting the priority value of the preempted element to a higher priority value, determining if the higher priority value of the preempted element is within the set of priority values that correspond to a higher priority class, and if so, relinking the preempted element into the subqueue corresponding to the priority class of the higher priority value.
Claim 6
Dependent Claim
37 words
The method of claim 4 wherein the prescribed function is priority value=3 x-1 , where X is the priority class of a new element, and the initial priority value is the value calculated by the prescribed function.
Claim 7
Dependent Claim
23 words
The method of claim 5 wherein the step of promoting a preempted element comprises decrementing its present priority value by a prescribed amount.
Claim 8
Dependent Claim
47 words
The method of claim 6 wherein the step of determining if the priority value of a promoted element resides in a higher priority class further comprises determining if the promoted priority value is equal to the value determined by the prescribed function for the higher priority class.
Claim 9
Dependent Claim
201 words
Apparatus for administering a service priority queue structure, wherein the structure includes a queue partitioned into subqueues corresponding to different priorities of elements to be serviced from the queue and ordered within the queue according to the respective priorities of the subqueues, a priority pointer array that contains a pointer for each subqueue, that points to the last entry in respective subqueue, and further wherein each element of the queue comprises a next pointer to the next element in the queue, if any, and a back pointer which for each last entry of a subqueue points to the respective entry in the priority pointer array, said method comprising means for determining the priority class of a new element arriving for insertion into the queue, means for inserting the new element as the last entry of the subqueue corresponding to the determined priority class of the new element, means for determining if the new element preempts a present element in the queue, means responsive to a determination that the new element preempts a present element in the queue for promoting the priority of the preempted element, and means for periodically servicing the priority queue by removing the top entry from the queue.
Claim 10
Dependent Claim
201 words
Apparatus for administering a service priority queue structure, wherein the structure includes a queue partitioned into subqueues corresponding to different priorities of elements to be serviced from the queue and ordered within the queue according to the respective priorities of the subqueues, a priority pointer array that contains a pointer for each subqueue, that points to the last entry in respective subqueue, and further wherein each element of the queue comprises a next pointer to the next element in the queue, if any, and a back pointer which for each last entry of a subqueue points to the respective entry in the priority pointer array, said method comprising means for determining the priority class of a new element arriving for insertion into the queue, means for inserting the new element as the last entry of the subqueue corresponding to the determined priority class of the new element, means for determining if the new element preempts a present element in the queue, means responsive to a determination that the new element preempts a present element in the queue for promoting the priority of the preempted element, and means for periodically servicing the priority queue by removing the top entry from the queue.
Claim 11
Dependent Claim
117 words
The apparatus of claim 8 wherein the means for inserting the new entry further comprises means for determining if the subqueue corresponding to the priority class of the new element is empty, means responsive to the determining means for clearing the back pointer of the present last element of the subqueue if the subqueue is not empty, means for pointing the next pointer of the present last element of the subqueue to point to the new element, means for initializing the back pointer of the new element to point to the corresponding subqueue pointer of the priority pointer array, and means for initializing the corresponding pointer of the priority pointer array to point to the new element.
Claim 12
Dependent Claim
130 words
The apparatus of claim 8 wherein the priority queue structure further includes a head pointer that points to the first element on the queue and the means for inserting the new entry further comprises means for determining if the subqueue corresponding to the priority class of the new element is empty, means responsive to the determining means for initializing the back pointer of the new element to point to the corresponding subqueue pointer of the priority pointer array if the subqueue is empty, means for initializing the corresponding pointer of the priority pointer array to point to the new element, means for determining from the head pointer if the queue is empty, and means for initializing the head pointer to point to the new element if the queue is empty.
Claim 13
Dependent Claim
101 words
The apparatus of claim 10 further comprising means responsive to a determination of the determining means that the queue is not empty, for further determining if the priority class of the new element is higher than that of the first element on the queue, means responsive to a determination that the priority class of the new element is higher that of the first element on the queue for initializing the next pointer of the new element to point to the present element at the top of the queue, and means for initializing the head pointer to point to the new element.
Claim 14
Dependent Claim
98 words
The apparatus of claim 11 further comprising means responsive to a determination that the priority class of the new element is not higher than that of the first element on the queue for searching the priority pointer array for the first subqueue of priority higher than that of the new element that is not empty, means for initializing the next pointer of the last element of that subqueue to point to the new entry, and means for initializing the next pointer of the new element to point to the next entry in the queue following the new element.
Claim 15
Dependent Claim
151 words
The apparatus of claim 8 or claim 9 or claim 11 wherein each queue element further comprises a priority counter field, said apparatus further comprising means for initializing the priority counter of a new element to a first priority value determined by a prescribed function of the priority class of the new element, said priority value being one of a set of priority values that are defined to reside in the priority class of the new element, and wherein the apparatus for promoting a preempted element further comprises means for setting the priority value of the preempted element to a higher priority value, means for determining if the higher priority value of the preempted element is within the set of priority values that correspond to a higher priority class, and if so, means for relinking the preempted element into the subqueue corresponding to the priority class of the higher priority value.
Claim 16
Dependent Claim
205 words
A storage medium containing stored instructions executable by a computer, which when so executed causes the computer to perform a method for administering a service priority queue structure, wherein the stored instructions further define a queue partitioned into subqueues corresponding to different priorities of elements, said subqueues being ordered within the queue according to the respective priorities, a priority pointer array that contains a pointer for each, subqueue that points to the last entry in its respective subqueue, and wherein each queue entry contains a next pointer that points to the next element in the queue, if any, and a back pointer which for each last entry of a subqueue points to the respective entry in the priority pointer array, said method comprising the steps of determining the priority class of a new element arriving for insertion into the queue, inserting the new element as the last entry of the subqueue corresponding to the determined priority class of the new element, determining if the new element preempts a present element in the queue, if the new element preempts a present element in the queue, promoting the priority of the preempted element, and periodically servicing the priority queue by removing the top entry from the queue.
Claim 17
Dependent Claim
205 words
A storage medium containing stored instructions executable by a computer, which when so executed causes the computer to perform a method for administering a service priority queue structure, wherein the stored instructions further define a queue partitioned into subqueues corresponding to different priorities of elements, said subqueues being ordered within the queue according to the respective priorities, a priority pointer array that contains a pointer for each, subqueue that points to the last entry in its respective subqueue, and wherein each queue entry contains a next pointer that points to the next element in the queue, if any, and a back pointer which for each last entry of a subqueue points to the respective entry in the priority pointer array, said method comprising the steps of determining the priority class of a new element arriving for insertion into the queue, inserting the new element as the last entry of the subqueue corresponding to the determined priority class of the new element, determining if the new element preempts a present element in the queue, if the new element preempts a present element in the queue, promoting the priority of the preempted element, and periodically servicing the priority queue by removing the top entry from the queue.
Claim 18
Dependent Claim
111 words
The storage medium of claim 14 wherein the stored instructions for performing the step of inserting the new entry further comprises stored instructions for determining if the subqueue corresponding to the priority class of the new element is empty, if the subqueue is not empty, clearing the back pointer of the present last element of the subqueue, pointing the next pointer of the present last element of the subqueue to point to the new element, initializing the back pointer of the new element to point to the corresponding subqueue pointer of the priority pointer array and initializing the corresponding pointer of the priority pointer array to point to the new element.
Claim 19
Dependent Claim
120 words
The storage medium of claim 14 wherein the priority queue structure further includes a head pointer that points to the first element on the queue and the stored instructions for inserting the new entry further comprises stored instructions for determining if the subqueue corresponding to the priority class of the new element is empty, if the subqueue is empty, initializing the back pointer of the new element to point to the corresponding subqueue pointer of the priority pointer array and initializing the corresponding pointer of the priority pointer array to point to the new element, determining from the head pointer if the queue is empty, if the queue is empty, initializing the head pointer to point to the new element.
Claim 20
Dependent Claim
88 words
The storage medium of claim 16 further comprising stored instructions for if the queue is not empty, determining if the priority class of the new element is higher than that of the first element on the queue, if the priority class of the new element is higher than that of the first element on the queue, initializing the next pointer of the new element to point to the present element at the top of the queue, and initializing the head pointer to the point to the new element.
Claim 21
Dependent Claim
93 words
The storage medium of claim 17 further comprising stored instructions for if the priority class of the new element is not higher than that of the first element on the queue, searching the priority pointer array for the first subqueue of priority higher than that of the new element that is not empty and initializing the next pointer of the last element of that subqueue to point to the new entry and initializing the next pointer of the new element to point to the next entry in the queue following the new element.
Claim 22
Dependent Claim
145 words
The storage medium of claim 14 or claim 15 or claim 17 wherein each queue element further comprises a priority counter field and further comprising stored instructions for initializing the priority counter of a new element to a first priority value determined by a prescribed function of the priority class of the new element, said priority value being one of a set of priority values that are defined to reside in the priority class of the new element, and the step of promoting a preempted element further comprises setting the priority value of the preempted element to a higher priority value, determining if the higher priority value of the preempted element is within the set of priority values that correspond to a higher priority class, and if so, relinking the preempted element into the subqueue corresponding to the priority class of the higher priority value.
Claim 23
Dependent Claim
43 words
The storage medium of claim 19 further comprising stored instructions for generating the prescribed function of priority value=3 X-1 , where X is the priority class of a new element, and the initial priority value is the value calculated by the prescribed function.
Claim 24
Dependent Claim
29 words
The storage medium of claim 20 wherein the stored instructions for promoting a preempted element further comprises stored instructions for decrementing its present priority value by a prescribed amount.
Claim 25
Dependent Claim
52 words
The storage medium of claim 21 wherein the stored instructions for determining if the priority value of a promoted element resides in a higher priority class further comprises stored instructions for determining if the promoted priority value is equal to the value determined by the prescribed function for the higher priority class.
References Cited (Backward Citations)
US4320455A
Cited
US4423480A
Cited
US5040127A
Cited
US4965716A
Cited
US5278969A
Cited
US5491799A
Cited
US5485586A
Cited
US5410722A
Cited
US5546546A
Cited
US5630123A
Cited
US5521916A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-02-15 | 2002-08-17 | 2003-02-16 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-02-15 | 2006-08-17 | 2007-02-16 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-02-15 | 2010-08-17 | 2011-02-16 | $7700.00 | Window Closed / Lapsed |