Dynamic scheduling of task streams in a multiple-resource system to ensure task stream quality of service

• US 6,711,607 B1
• Filed: 02/04/2000
• Issued: 03/23/2004
• Est. Priority Date: 02/04/2000
• Status: Expired due to Term

• Current Assignee: ServStor Technologies, LLC (IP Investments Group LLC)
• Original Assignee: Ensim Corporation (Techstep ASA)
• Inventors: Goyal, Pawan
• Primary Examiner(s): Dinh, Dung C.
• Application Number:
  US09/498,450
• Time in Patent Office: 1,509 Days
• Field of Search: 709/203, 709/229, 709/226, 709/235, 709/219, 709/225, 709/105, 709/103, 709/102
• US Class Current: 709/203
• CPC Class Codes: G06F 9/5044 considering hardware capabilities
• CPC Class Codes: G06F 9/505 considering the load

Abstract

A multi-resource system dynamically allocates its resources amongst multiple task streams to provide quality of service guarantees to the task streams. A quality of service manager maintains quality of service requirement information for a plurality of task streams, and requests processing of received tasks. An arbitrator assigns tasks streams and their tasks amongst various servers providing access to resources. The assignment is such that the total quality of service guarantees of the task streams assigned to each server does not exceed the total availability or capacity of the resource. When all assigned tasks for a server are blocked, the server notifies the arbitrator, which transfers an unblocked task to it. When a blocked task unblocks on a server handling a transferred task, the arbitrator transfers back the previously transferred task to its originating server.

Claims

1. In a system including a plurality of resources for servicing tasks, each resource associated with a server for managing tasks on the resource, a computer-implemented method of providing quality of service guarantees to task streams, each task stream having a plurality of associated tasks and a quality of service requirement for obtaining a defined portion of the availability of at least one of the resources, the method comprising;

assigning each task stream to one of the servers, the task streams assigned so that the total quality of service requirements of the task streams assigned to each server does not exceed the total resource availability of the resource associated with each server; and

responsive to all of the tasks of the task streams assigned to a first server being blocked, transferring at least one runnable task form a task stream assigned to a second server to the first server, to allow the runnable task to access the resource associated with the first server.

2. The method of claim 1, further comprising:

responsive to at least one blocked tasks on the first server becoming runnable, transferring at least one runnable task from the first server back to the second server to allow the at least one runnable task to be processed on the second server.

3. The method of claim 1, further comprising:

periodically re-assigning the task streams to the servers so that the total quality of service requirements of the task streams currently assigned to each server does not exceed the total resource availability of the resource associated with each server.

4. The method claim 1, further comprising:

receiving a task of a new task stream; and

assigning the new task stream to one of the servers by selecting a server so that the total quality of service requirements of the task streams currently assigned to the server and the new task stream does not exceed the total resource availability of the resource associated with the server.

5. The method of claim 4, wherein assigning the new task stream farther comprises:

re-assigning currently assigned task streams and the new task stream to the servers so that the total quality of service requirements of the task streams currently assigned to each server does not exceed the total resource availability of the resource associated with each server.

6. The method of claim 1, further comprising:

receiving a task of a new task stream;

determining whether the new task stream can be assigned to one of the servers so that the total quality of service requirements of the task streams currently assigned to the server and the new task stream does not exceed the total resource availability of the resource associated with the server; and

responsive to the new task stream not being capable of being assigned to any of the servers, rejecting the new task.

7. A computer-implemented method of providing quality of service guarantees to task streams by allocating resources in a computer, the method comprising:

receiving a plurality of tasks, and assigning each task to a task stream, each task stream having a quality of service requirement for obtaining a defined portion of at least one resource'"'"'s availability;

partitioning the task streams into a plurality of task stream queues, each task stream queue associated with a server for providing the task streams access to a resource managed by the server, the task streams partitioned so that the total quality of service requirements of the task streams in each server'"'"'s task stream queue does not exceed the total resource availability of the resource associated with the server; and

responsive to all of the tasks on a first server being blocked, transferring at least one runnable task from a second server to the first server, to allow the runnable task to be processed by the first server.

8. The method of claim 7, further comprising:

responsive to at least one blocked tasks on the first server becoming runnable, transferring at least one runnable task from the first server back to the second server to allow the at least one runnable task to be processed on the second server.

9. The method of claim 7, wherein partitioning the task streams into a plurality of task stream queues further comprises:

partitioning the task streams into the task stream queues using a best fit partitioning algorithm.

10. The method of claim 7, wherein partitioning the task streams into a plurality of task stream queues further comprises:

partitioning the task streams into the task stream queues using a first fit partitioning algorithm.

11. The method of claim 7, further comprising:

on each server, scheduling the task streams in the task stream queue associated with the server using a uniprocessor scheduling algorithm.

12. A computer system for providing quality of service guarantees to task streams by allocating resources in a computer, the system comprising:

a plurality of system resources, each resource having a maximum resource availability;

a plurality of servers, each server associated with one of the resources, each server having a task stream queue including runnable and blocked tasks;

a quality of service manager that maintains for each task stream a quality of service requirement; and

that determines for a received task the task stream associated with the task; and

an arbitrator communicatively coupled to the quality of service manager and the servers, that receives from the quality of service manager task requests including a quality of service requirement and the task stream associated with a task, and assigns a task to the task stream queue of one of the servers, so that each task stream queue contains only tasks of task streams having a total quality of service requirement That docs not exceed the maximum resource availability of the resource associated with the server.

13. The computer system of claim 12, wherein:

each server, responsive to all of its tasks being blocked notifies the arbitrator that it is idle, and responsive to at least one task becoming unblocked, notifies the arbitrator that it is no longer idle; and

the arbitrator, responsive to a first server being idle, transfers at least one runnable task from a second server to the first server, and responsive to the first server no longer being idle, re-transfers the runnable task to the second server.

14. The computer system of claim 12, further comprising:

a master quality of service table coupled to the arbitrator and storing information identifying each of the servers, the task streams assigned to each server, and the total quality of service requirement of the task streams assigned to each server.

15. The computer system of claim 12, further comprising:

a current assignment table coupled to the arbitrator and storing information identifying one or more task, the original server to which the one or more tasks is assigned, and a current server to which the one or more tasks is assigned, the arbitrator in response to transferring a task from a second server to a first, updating the current server information to indicate the second server as the current server of the task.

16. The computer system of claim 12, further comprising:

a quality of service assignment table coupled to the quality of service manager and storing information identiting each task stream, and the quality of service requirement of each task stream.

17. The computer system of claim 12, further comprising:

a quality of service table coupled to each server, and storing information identifying each task assigned to the server and the quality of service requirement of the task stream associated with the task.

18. In a computer system having a plurality system resources, each resource having a maximum resource availability, and a plurality of servers, each server associated with one of the resources, each server having a task stream queue including runnable and blocked tasks, a computer program product encoded on a computer readable medium, the computer program product for providing quality of service guarantees to the task streams, the computer program product comprising:

a quality of service manager that maintains for each task stream a quality of service requirement; and

that determines for a received task the task stream associated with the task; and

an arbitrator communicatively coupled to the quality of service manager and the servers that receives from the quality of service manager task requests including a quality of service requirement and the task stream associated with a task, and assigns a task to the task stream queue of one of the servers, so that each task stream queue contains only tasks of task streams having a total quality of service requirement that does not exceed the maximum resource availability of the resource associated with the server.