Apparatus and method for priority queuing with segmented buffers

Abstract

Apparatus and methods for efficient queuing and dequeuing using segmented output buffers comprising sub-buffers and priority queues. Output buffers are monitored for empty sub-buffers. When a newly empty sub-buffer is discovered, a refill request is enqueued in a ranked priority queue wherein the rank of the destination priority queue is based on the number of empty-sub-buffers in the requesting output buffer. All high priority refill requests are dequeued before lower priority refill requests, thereby reducing the possibility of starvation. Optionally, by using simple dequeuing criteria, such as a FIFO discipline, instead of complex algorithms designed to improve fairness, system resources may be conserved thereby improving system throughput.

1 . A method for efficient queuing, the method comprising:
 providing at least one output buffer wherein each output buffer comprises a multiplicity of sub-buffers;   providing a plurality of priority queues for holding refill requests for the output buffers wherein the priority queues are ranked from highest priority to lowest priority;   monitoring the output buffers for empty sub-buffers and establishing a refill request in one of the priority queues when at least one newly empty sub-buffer is discovered wherein the rank of the destination priority queue for the refill request is calculated according to the number of empty sub-buffers in the output buffer; and,   dequeuing refill requests in an order according to the rank of the priority queues, thereby dequeuing all requests in the highest rank priority queue before dequeuing any requests of any other priority.   
     
     
         2 . The method of  claim 1  further comprising the step of servicing refill requests after they are dequeued, thereby filling empty sub-buffers. 
     
     
         3 . The method of  claim 1  wherein the step of dequeuing refill requests further comprises using a first-in first-out (FIFO) queuing discipline per priority queue. 
     
     
         4 . The method of  claim 1  wherein each output buffer has the same number of sub-buffers. 
     
     
         5 . The method of  claim 1  wherein each sub-buffer is the same size. 
     
     
         6 . The method of  claim 1  wherein each sub-buffer holds a reference to an item and wherein each referenced item has the same maximum magnitude. 
     
     
         7 . The method of  claim 1  wherein each sub-buffer holds items selected from the list comprising:
 data, pointers, process identifiers, thread identifiers, queries, transactions, transaction identifiers or network packets or any combination thereof.   
     
     
         8 . The method of  claim 1  wherein each request comprises an output buffer identifier. 
     
     
         9 . An efficient computer queuing system:
 at least one output buffer wherein each output buffer comprises a plurality of sub-buffers;   a plurality of priority queues for holding refill requests for the output buffers wherein the priority queues are ranked from highest priority to lowest priority;   a buffer monitor for monitoring the output buffers for empty sub-buffers and establishing refill requests in the priority queues wherein the rank of the destination priority queue for the requests are based on the number of empty sub-buffers in the output buffer; and,   a queue servicer for dequeuing refill requests in the priority queues in an order according to the rank of the priority queues, thereby dequeuing all refill requests in the highest rank priority queue before dequeuing any refill requests in a lower rank priority queue.   
     
     
         10 . A computer system for efficient data queuing comprising:
 a queuing system comprising:
 at least one output buffer wherein each output buffer comprises a multiplicity of sub-buffers; 
 a plurality of priority queues for holding refill requests for the output buffers wherein the priority queues are ranked from highest priority to lowest priority; 
 a buffer monitor for monitoring the output buffers for empty sub-buffers and establishing refill requests in the priority queues wherein the rank of the destination priority queue for the requests are based on the number of empty sub-buffers in the output buffer; and, 
 a queue servicer for dequeuing and servicing refill requests in the priority queues in an order according to the rank of the priority queues, thereby dequeuing all refill requests in the highest rank priority queue before dequeuing any refill requests in a lower rank priority queue; and, 
 one or more interfaces for coupling said queuing apparatus to targets and sources wherein a target may be coupled to an outgoing queue enabling a target to receive items from an output buffer and wherein a source may provide items for servicing data refill requests.