BALANCING USAGE OF HARDWARE DEVICES AMONG CLIENTS

• US 20100082851A1
• Filed: 09/30/2008
• Published: 04/01/2010
• Est. Priority Date: 09/30/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Worthington, Bruce L., Chin, Yau Ning, Green, Dustin L.
• Granted Patent: US 8,346,995 B2
• Time in Patent Office: Days
• 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;

determining that a hardware device has spent an estimated amount of time completing jobs associated with the client that exceeds an amount of time that was allocated to complete IO jobs from the client; and

storing the IO job in a queue.

2. The method of claim 1, further comprising:

receiving an IO job completion signal from the hardware device;

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

sending the IO job to the hardware 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:

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 hardware device can spend completing job requests from the second client; and

sending the IO job request associated with the second client to the hardware device.

6. The method of claim 5, further comprising:

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

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

7. The method of claim 5, further comprising:

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

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

9. A computer system comprising:

circuitry for storing a value indicative of an amount of time a hardware device can spend completing IO jobs from the client;

circuitry for receiving IO jobs associated with the client;

circuitry for estimating an amount of time the hardware device will need to complete the IO jobs;

circuitry for revising the value based on the estimated amount of time required to complete the IO jobs; and

circuitry for sending the IO jobs to the hardware device.

10. The computer system of claim 9, further comprising:

circuitry for determining that the amount of time the hardware device can spend completing IO jobs from the client is greater than a maximum amount of time a client can use the hardware device; and

circuitry for reducing the amount of time the hardware device can spend completing IO jobs to the maximum amount of time.

11. The computer system of claim 9, further comprising:

circuitry for revising the value based a priority level for the client.

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

circuitry for receiving additional IO jobs from the client;

circuitry for determining that the client has overused the hardware device based on the revised value; and

circuitry for storing the additional IO jobs in a queue.

13. The computer system of claim 10, further comprising:

circuitry for storing an IO job associated with a second client in the queue; and

circuitry for storing a second value indicative of the amount of time the second client has overused the hardware device.

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

circuitry for determining that an estimated amount of time associated with jobs issued to the hardware device is lower than a predetermined value;

circuitry for increasing the value and the second value;

circuitry for determining that the value is greater than the second value;

circuitry for sending the additional IO jobs associated with the client to the hardware device; and

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

15. A computer readable storage medium including processor executable instructions for balancing IO requests, the computer readable storage medium comprising:

instructions for storing 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 hardware device spent completing IO jobs associated with the client;

instructions for storing 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 hardware device;

instructions for receiving a job completion signal from the hardware device;

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

instructions for sending IO jobs that are eligible based on the advanced issue line to the hardware device.

16. The computer readable storage medium of claim 15, further comprising:

instructions for setting a maximum positive time value.

17. The computer readable storage medium of claim 15, further comprising:

instructions for receiving IO jobs from a client associated with a positive time value;

instructions for sending the IO jobs from the client associated with the positive time value to the hardware device; and

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

18. The computer readable storage medium of claim 15, further comprising:

instructions for adjusting 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 hardware device and a priority level for a client associated with the newly positive time value.

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

20. The computer readable storage medium of claim 19, further comprising:

instructions for dynamically updating the maximum positive time value based on average latency of IO jobs.