Dynamically adjustable load-sharing circular queues
AssigneeIntel Corporation
InventorSiu H Lam
Life of this patent
Estimating the term…
Abstract
Dynamically adjustable load-sharing circular queues are disclosed. That is, a method of reversing the processing order of a second queue placed adjacent to a first queue to allow the space allocated to both queues to be dynamically adjusted, without copying or moving queue data or affecting the performance of the input and output queue functions is described. These advantages are attained without adding any overhead to conventional circular queues, in terms of processing and memory requirements. Dynamically adjustable circular queues are particularly useful in reducing memory requirements for simple circular queues used in serving either a primary/backup or load-sharing configuration of two input queues. A simple way of determining when the queue sizes can be adjusted is further described.
Claims17
A system of adjustable circular queues, comprising:
- a first circular queue, placed end-to-end to a second circular queue, having an input pointer, an output pointer, a start, and an end;
- the second circular queue, placed end-to-end to the first circular queue, having an input pointer, an output pointer, a start, and an end;
- and
- a partition between the first circular queue and the second circular queue as defined by the end-to-end meeting of the first circular queue end and the second circular queue end;
- wherein the system functions to:
- set a first straddling flag when the first circular queue input pointer wraps around the first circular queue end;
- set a second straddling flag when the second circular queue input pointer wraps around the second circular queue end;
- reset the first straddling flag when the first circular queue output pointer wraps around the first circular queue end;
- reset the second straddling flag when the second circular queue output pointer wraps around the second circular queue end;
- and
- adjust the first circular queue end and the second circular queue end provided that the first circular queue and the second circular queue do not wrap around the first circular queue end and the second circular queue end.
A method of adjusting circular queues, comprising:
- fixing a first straddling flag when a first circular queue input pointer wraps around a first circular queue end, in which a first circular queue is placed end-to-end with a second circular queue;
- fixing a second straddling flag when a second circular queue input pointer wraps around a second circular queue end, in which a second circular queue is placed end-to-end with the first circular queue;
- refixing the first straddling flag when a first circular queue output pointer wraps around the first circular queue end;
- refixing the second straddling flag when a second circular queue output pointer wraps around the second circular queue end;
- and
- moving the first circular queue end and the second circular queue end provided that the first circular queue and the second circular queue do not wrap around the first circular queue end and the second circular queue end, while a first circular queue start and a second circular queue start remain fixed.
A computer readable medium and a computer readable program code stored on the computer readable medium having instructions to:
- set a straddling flag when an input pointer of a circular queue that is placed end-to-end with another circular queue wraps around an endpoint of the circular queue;
- reset the straddling flag when an output pointer of the circular queue wraps around the endpoint of the circular queue;
- and
- adjust circular queue size by allowing the endpoint of the circular queue to move if the input pointer of the circular queue and the output pointer of the circular queue do not straddle the endpoint of the circular queue.
A data structure for circular queues, comprising:
- a first circular queue having a first circular queue start and a first circular queue end;
- a second circular queue having a second circular queue start and a second circular queue end;
- a partition between the first circular queue and the second circular queue, as defined by the end-to-end meeting of the first circular queue end and the second circular queue end;
- and
- at least one data element occupying at least one of the first circular queue and the second circular queue.
Dependencies are inferred from the claim text.