Balancing usage of hardware devices among clients

• US 8,346,995 B2
• Filed: 09/30/2008
• Issued: 01/01/2013
• Est. Priority Date: 09/30/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Green, Dustin L., Chin, Yau Ning, Worthington, Bruce L.
• Primary Examiner(s): RHU, KRIS M
• Application Number:
  US12/242,624
• Publication Number:
  US 20100082851A1
• Time in Patent Office: 1,554 Days
• Field of Search: 710/29
• US Class Current: 710/29
• CPC Class Codes: G06F 2009/4557 Distribution of virtual machine instances; Migration and load balancing
• CPC Class Codes: G06F 2009/45579 I/O management, e.g. providing access to device drivers or storage
• CPC Class Codes: G06F 9/45558 Hypervisor-specific management and integration aspects
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues

Abstract

Techniques are disclosed for managing the flow of IO jobs from a client to a hardware device such that resource starvation is reduced without significantly impacting throughput. Each flow can be assigned an amount of time that a hardware device can deplete completing IO jobs from the client. When the allocated amount of time is used IO jobs associated with the client can be stored in a queue until the client obtains more time.

Claims

1. A method for balancing hardware usage, the method comprising:

receiving an IO job associated with a client;

estimating an amount of time a storage device will take to complete IO jobs associated with the client;

determining that the estimated amount of time the storage device will take to complete IO jobs associated with the client exceeds an amount of time that was allocated to complete IO jobs from the client; and

storing the IO job in a queue

receiving an IO job associated with a second client;

determining that the second client is associated with information that identifies an amount of time that the storage device can spend completing IO job requests from the second client;

sending the IO job request associated with the second client to the storage device;

determining that the amount of time that the storage device can spend completing IO job requests from the second client exceeds a predetermined maximum amount of time; and

reducing the amount of time that the storage device can spend completing IO job requests from the second client to the predetermined maximum amount of time.

2. The method of claim 1, further comprising:

receiving an IO job completion signal from the storage device;

determining that estimated completion times for IO jobs pending in the storage device total to a completion time value that is lower than a predetermined value; and

sending the IO job to the storage device.

3. The method of claim 1, wherein the client is a virtual machine.

4. The method of claim 1, wherein the client is a terminal server session.

5. The method of claim 1, further comprising:

reducing the amount of time that the storage device can spend completing IO job requests from the second client based on a priority level associated with the client.

6. The method of claim 1, wherein the predetermined maximum amount of time is dynamically updated based on average latency of IO jobs.

7. A computer system comprising:

a processor;

a storage device; and

a memory in communication with at least the processor when powered, the memory including instructions stored thereon that upon execution by the processor cause the processor to;

store a value indicative of an amount of time the storage device can spend completing IO jobs from a client;

receive IO jobs associated with the client;

estimate an amount of time the storage device will need to complete the IO jobs;

revise the value based on the estimated amount of time required to complete the IO jobs; and

send the IO jobs to the storage device.

8. The computer system of claim 7, wherein the memory further comprises instructions that upon execution cause the processor to:

determine that the amount of time the storage device can spend completing IO jobs from the client is greater than a maximum amount of time a client can use the storage device; and

reduce the amount of time the storage device can spend completing IO jobs to the maximum amount of time.

9. The computer system of claim 7, wherein the memory further comprises instructions that upon execution cause the processor to:

revise the value based a priority level for the client.

10. The computer system of claim 7, wherein the memory further comprises instructions that upon execution cause the processor to:

receive additional IO jobs from the client;

determine that the client has overused the storage device based on the revised value; and

store the additional IO jobs in a queue.

11. The computer system of claim 8, wherein the memory further comprises instructions that upon execution cause the processor to:

store an IO job associated with a second client in the queue; and

store a second value indicative of the amount of time the second client has overused the storage device.

12. The computer system of claim 11, wherein the memory further comprises instructions that upon execution cause the processor to:

determine that an estimated amount of time associated with IO jobs issued to the storage device is lower than a predetermined value;

increase the value and the second value;

determine that the value is greater than the second value;

send the additional IO jobs associated with the client to the storage device; and

revise the value based on an additional estimated amount of time required to complete the additional IO jobs.

13. A computer readable medium excluding signals per se including processor executable instructions for balancing IO requests, the computer readable storage medium comprising instructions that upon execution by a processor cause the processor to:

store a plurality of negative time values, each negative time value associated with a client, each negative time value being indicative of an estimated amount of time that a storage device spent completing IO jobs associated with the client;

store a value indicative of an issue line, the value indicative of the issue line separating positive time values from the negative values, the positive time values associated with clients that are eligible to send IO jobs to the storage device;

receive a IO job completion signal from the storage device;

advance the issue line an amount of time to make IO jobs associated with at least one negative time value eligible for sending to the storage device; and

send IO jobs that are eligible based on the advanced issue line to the storage device; and

reduce an amount of time from the time value associated with the eligible IO jobs, the amount of time calculated based on an estimated amount of time required to complete the IO jobs sent to the storage device and a priority level for a client associated with the newly positive time value.

14. The computer readable storage medium of claim 13, wherein the computer readable storage medium further comprises instructions that upon execution by the processor cause the processor to:

set a maximum positive time value.

15. The computer readable storage medium of claim 13, wherein the computer readable storage medium further comprises instructions that upon execution by the processor cause the processor to:

receive IO jobs from a client associated with a positive time value;

send the IO jobs from the client associated with the positive time value to the storage device; and

adjust an amount of time from the positive time value, the amount of time calculated based on an estimated amount of time required to complete the IO jobs sent to the storage device and a priority level for a client associated with the positive time value.

16. The computer readable storage medium of claim 13, wherein the computer readable storage medium further comprises instructions that upon execution by the processor cause the processor to:

adjust an amount of time from the time value associated with the eligible IO jobs, the amount of time calculated based on an estimated amount of time required to complete the IO jobs sent to the storage device and a priority level for a client associated with the newly positive time value.

17. The computer readable storage medium of claim 16, wherein the issue line is advanced in units of time.

18. The computer readable storage medium of claim 17, wherein the computer readable storage medium further comprises instructions that upon execution by the processor cause the processor to:

update the maximum positive time value based on average latency of IO jobs.