Fairly partitioning resources while limiting the maximum fair share

• US 6,909,691 B1
• Filed: 08/07/2000
• Issued: 06/21/2005
• Est. Priority Date: 08/07/2000
• Status: Expired due to Term

• Current Assignee: ServStor Technologies, LLC (IP Investments Group LLC)
• Original Assignee: Ensim Corporation (Techstep ASA)
• Inventors: Goyal, Pawan, Keshav, Srinivasan
• Primary Examiner(s): Nguyen, Brian
• Assistant Examiner(s): Moore, Ian N
• Application Number:
  US09/633,575
• Time in Patent Office: 1,779 Days
• Field of Search: 370/230, 370/235, 370/236, 370/236.1, 370/252, 370/395.2, 370/395.21, 370/395.4, 37039541-39543, 370/468, 370/443, 370/428, 370/412, 709/226, 709/229, 709102-104, 709/234, 711/173, 711/104
• US Class Current: 370/230
• CPC Class Codes: G06F 13/36 for access to common bus or bus system
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues

Abstract

Resource requests from a plurality of schedulable entities are scheduled while limiting the maximum and minimum quality of service allocated to each schedulable entity. The resource scheduler of the present invention requires less memory maintain state information than existing rate-controlling schedulers, and is thus more easily scalable to large numbers of users. The resource scheduler also schedules resources fairly among competing schedulable entities. A fair-share scheduling algorithm is used by a resource scheduler to select resource requests to service. A rate controller checks to ensure that servicing the selected request will not cause the associated user'"'"'s maximum quality of service to be exceeded. If the maximum quality of service will not be exceeded, the virtual time used in the scheduling algorithm is incremented, and the request is serviced. If the maximum quality of service will be exceeded, the virtual time is still incremented, but the request is not serviced and remains pending.

Claims

1. A method for scheduling resource requests from a plurality of schedulable entities, wherein each resource request includes a requested duration and each schedulable entity has a maximum resource allocation, the maximum resource allocation being specified as a maximum quality of service guarantee, the method comprising:

assigning a start number tag to a each resource request using a start-time fair queuing algorithm with virtual time scheduling;

selecting a resource request with the smallest start number tag, the selected resource request having an associated schedulable entity;

limiting the requested duration of the selected resource request to a pre-determined duration upper bound;

servicing the selected resource request if servicing the selected resource request will not exceed the associated schedulable entity'"'"'s maximum quality of service guarantee; and

advancing a virtual time value.

2. The method of claim 1, further including updating the start number tag for a resource request associated with the schedulable entity that made the selected resource request is not serviced.

3. The method of claim 1, further including leaving the selected resource request pending if servicing the selected resource request will exceed the schedulable entity'"'"'s maximum quality of service guarantee.