Apportioned queue for resource allocation

摘要

An apportioned queue data structure allows a server to specify allocation of resources to return requests according to a prescribed usage request. The data structure comprises an input queue comprising of a set of subqueues (also known as windows). Windows contain requests that will be processed over a fixed window of time. Received items are removed from the input queue and packed into the subqueues according to the service level agreement. These windows (and the elements present within) are then processed in the order of the windows queue (and the order in the window) are arranged. The time for each task is not known until after the request is processed and may be estimated. In a steady state of high load, a queue is created that returns requests tending toward requested percentages of the service level agreement.

主权项

1. A computer-implemented method comprising:
providing a server configured to receive a plurality of requests; providing a first category map specifying a first allocation between a first priority type, a second priority type, and a third priority type in a saturated condition wherein the server receives requests of the first priority type, the second priority type, and the third priority type; providing a second category map specifying a second allocation between the first priority type and the second priority type in a semi-saturated condition wherein the server receives requests of the first priority type and the second priority type, but not of the third priority type; receiving at the server a first request of the first priority type in the semi-saturated condition; receiving at the server a second request of the second priority type in the semi-saturated condition; scaling a slot size based upon an estimated time of processing a request of the first priority type, wherein the estimated time is based upon an actual processing time of a previous request of the first priority type only that has been received by the server; and causing the server to process the first request and the second request in an order according to a single queue created by a queuing procedure referencing the second category map based upon a desired percentage of output of the first priority type and of the second priority type over a plurality of requests, wherein the desired percentage is based upon a service level agreement, wherein the queuing procedure creates the single queue comprising a window comprising a first number of slots apportioned for processing requests of the first priority type, and comprising a second number of slots apportioned for processing requests of the second priority type.