System-aware resource scheduling

• US 8,347,302 B1
• Filed: 10/09/2008
• Issued: 01/01/2013
• Est. Priority Date: 10/09/2008
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Vincent, Pradeep, Sivasubramanian, Swaminathan
• Primary Examiner(s): Coleman, Eric
• Application Number:
  US12/248,770
• Time in Patent Office: 1,545 Days
• Field of Search: None
• US Class Current: 718/104
• CPC Class Codes: G06F 2209/485 Resource constraint
• CPC Class Codes: G06F 2209/506 Constraint
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06F 9/5011 the resources being hardware resources other than CPUs, Servers and Terminals

Abstract

Technology is provided to manage requests for physical resources in computing systems using system-aware scheduling techniques. Transactions having two or more dependent requests for a physical resource are identified by the computing system. Information identifying the requests as part of a dependent transaction is passed with the requests for the physical resource. In at least one mode of operation, a scheduler corresponding to the physical resource allocates submission of the requests to the physical resource using the dependent transaction information.

Claims

1. A method of managing input/output (I/O) requests for physical resources in computing systems, comprising:

receiving from a file system of an operating system a first plurality of I/O requests at an I/O scheduler of the operating system for one or more storage systems, the first plurality of I/O requests from the file system each including a first identifier indicating that the I/O requests of the first plurality are part of a first dependent transaction;

receiving from the file system of the operating system a second plurality of I/O requests at the I/O scheduler;

determining that the I/O requests of the first plurality are part of the first dependent transaction using the first identifier and determining that the I/O requests of the second plurality are not part of a dependent transaction; and

based on the first identifier, providing by the I/O scheduler the first plurality of I/O requests to the one or more storage systems prior to providing the second plurality of I/O requests to the one or more storage systems based on the first identifier.

2. The method of according to claim 1, further comprising:

receiving a third plurality of I/O requests at the I/O scheduler, the third plurality of I/O requests including a second identifier indicating that the I/O requests of the third plurality are part of a second dependent transaction;

determining that the I/O requests of the third plurality are part of the second dependent transaction at the I/O scheduler using the second identifier;

calculating a first transaction cost for the first dependent transaction;

calculating a second transaction cost for the second dependent transaction;

sending the first plurality of I/O requests under the control of the I/O scheduler to the one or more storage systems prior to sending the third plurality of I/O requests to the one or more storage systems if the first transaction cost is lower than the second transaction cost; and

sending the third plurality of I/O requests under the control of the I/O scheduler to the one or more storage systems prior to providing the first plurality of I/O requests to the one or more storage systems if the second transaction cost is lower than the first transaction cost.

3. The method of claim 2, wherein:

calculating the first transaction cost includes determining a first I/O cost for the first dependent transaction, determining a first deviation from fairness factor for the first dependent transaction, and adjusting the first I/O cost using the first deviation from fairness factor; and

calculating the second transaction cost includes determining a second I/O cost for the first transaction, determining a second deviation from fairness factor for the second dependent transaction, and adjusting the second I/O cost using the second deviation from fairness factor.

4. The method of claim 3, wherein:

the one or more storage systems includes a non-volatile storage system; and

the I/O requests of the first plurality and the second plurality designate the non-volatile storage system.

5. The method of claim 4, wherein:

determining the first I/O cost for the first dependent transaction includes determining a first seek time and a first size of each I/O request of the first dependent transaction; and

determining the second I/O cost for the second dependent transaction includes determining a second seek time and a second size of each I/O request of the second dependent transaction.

6. The method of claim 1, further comprising:

receiving at the file system the first plurality of I/O requests including the first identifier from an application thread that is allocated processing windows by a CPU scheduler of the operating system.

7. The method of claim 6, wherein the first dependent transaction is associated with a first process, the method further comprising:

adding to the first plurality of I/O requests an identification of importance of the first dependent transaction to the first process.

8. The method of claim 6, wherein the first dependent transaction is an I/O job, the method further comprising:

receiving the I/O job at the file system;

generating by the file system the first plurality of I/O requests in response to receiving the I/O job, wherein generating the first plurality of I/O requests includes adding the first identifier; and

sending the first plurality of I/O requests to the I/O scheduler.

9. A method of scheduling requests for resources in computing systems, comprising:

generating by a plurality of threads under control of a central processing unit (CPU) scheduler of an operating system a plurality of resource requests designating one or more physical resources, the plurality of resource requests including two or more resource requests that are part of a dependent transaction and at least one additional resource request;

adding by a file system of the operating system a dependent transaction identifier to the two or more resource requests; and

providing the plurality of resource requests to a resource scheduler of the operating system associated with the one or more physical resources.

10. The method of claim 9, further comprising:

receiving the plurality of resource requests at the resource scheduler;

determining from the dependent transaction identifier that the two or more resource requests are part of the dependent transaction and that the at least one additional resource request is not part of the dependent transaction; and

providing the two or more resource requests to the one or more physical resources prior to providing the at least one additional resource request to the one or more physical resources based on determining that the two or more resource requests are part of the dependent transaction.

11. The method of claim 10, wherein:

the dependent transaction is an I/O job;

the method further comprises receiving the I/O job at the file system; and

generating the plurality of resource requests includes generating the two or more resource requests by the file system in response to receiving the I/O job.

12. A method of scheduling requests for resources in computing systems, comprising:

receiving a plurality of resource requests including a first set of two or more resource requests having a first dependent transaction identifier, a second set of two or more resource requests having a second dependent transaction identifier, and at least one resource request not having a dependent transaction identifier, the plurality of resource requests designating one or more physical resources;

queuing the plurality of resource requests;

determining from the first dependent transaction identifier that the first set of two or more resource requests is part of a first dependent transaction, from the second dependent transaction identifier that the second set of two or more resource requests is part of a second dependent transaction, and that the at least one resource request is not part of a dependent transaction;

calculating a first dependency weight measure for the first dependent transaction, the first dependency weight measure comprising a first ratio of a first expected increase in processor utilization resulting from completion of the first dependent transaction to a first cost associated with completing the first dependent transaction;

calculating a second dependency weight measure for the second dependent transaction, the second dependency weight measure comprising a second ratio of a second expected increase in processor utilization resulting from completion of the second dependent transaction to a second cost associated with completing the second dependent transaction;

providing the at least one resource request to the one or more physical resources after the first set of two or more resource requests and the second set of two or more resource requests based on determining that the at least one resource request is not part of a dependent transaction;

providing the first set of two or more resource requests to the one or more physical resources prior to providing the second set of two or more resource requests to the one or more physical resources if the first dependency weight measure is greater than the second dependency weight measure; and

providing the second set of two or more resource requests to the one or more physical resources prior to providing the first set of two or more resource requests to the one or more physical resources if the second dependency weight measure is greater than the first dependency weight measure.

13. The method of claim 12, wherein:

receiving the plurality of resource requests includes receiving the two or more resource requests having the dependent transaction identifier from a first application process and receiving the at least one resource request from a second application process.

14. The method of claim 12, wherein:

the one or more physical resources is a non-volatile storage system;

the plurality of resource requests is a plurality of I/O requests designating the non-volatile storage system;

the two or more resource requests of the first set are two or more I/O requests; and

the at least one resource request is at least one I/O request.

15. The method of claim 14, wherein the first dependent transaction is an I/O job designating the non-volatile storage system, the method further comprising:

receiving the I/O job at a file system from a first application process;

generating the two or more I/O requests of the first set to fulfill the I/O job; and

adding the first dependent transaction identifier to the two or more I/O requests,

wherein receiving the plurality of I/O requests includes receiving the plurality of I/O requests from the file system.

16. The method of claim 12, wherein:

the one or more physical resources includes one or more physical resources accessible over a first network;

the plurality of resource requests is a plurality of requests designating the one or more physical resources; and

providing the two or more resource requests includes providing the two or more requests to the first network.

17. The method of claim 12, further comprising:

determining a first expected increase in processor utilization resulting from completion of the first dependent transaction by determining a first CPU scheduling priority for a first process associated with the first dependent transaction; and

determining a second expected increase in processor utilization resulting from completion of the second dependent transaction by determining a second CPU scheduling priority for a second process associated with the second dependent transaction.

18. The method of claim 12, wherein the plurality of resource requests is a first plurality of resource requests, the method further comprising:

determining a first increase in processor utilization resulting from completion of the first dependent transaction, the first dependent transaction is associated with a first process;

determining a second increase in processor utilization resulting from completion of the second dependent transaction, the second dependent transaction is associated with a second process;

maintaining an indication of the first increase in processor utilization and the second increase in processor utilization;

receiving a second plurality of resource requests, the second plurality of resource requests including a third set of resource requests and a fourth set of resource requests, the third set of resource requests being part of a third dependent transaction and having a third dependent transaction identifier, the fourth set of resource requests being part of a fourth dependent transaction and having a fourth dependent transaction identifier, the third dependent transaction being associated with the first process and the fourth dependent transaction being associated with the second process;

calculating a third dependency weight measure for the third dependent transaction using the indication of the first increase in processor utilization resulting from completion of the first dependent transaction; and

calculating a fourth dependency weight measure for the fourth dependent transaction using the indication of the second increase in processor utilization resulting from completion of the second dependent transaction.

19. One or more processor readable non-transitory storage devices having processor readable code embodied on said one or more processor readable storage devices, said processor readable code for programming one or more processors to perform a method comprising:

receiving a plurality of I/O requests designating one or more physical resources, the plurality of I/O requests including a first set of I/O requests having a first dependent transaction identifier and a second set of I/O requests having a second dependent transaction identifier;

queuing the plurality of I/O requests;

calculating a first dependency weight measure for the first dependent transaction, the first dependency weight measure is a first ratio of a first expected increase in processor utilization resulting from completion of the first dependent transaction to a first cost associated with completing the first dependent transaction;

calculating a second dependency weight measure for the second dependent transaction, the second dependency weight measure is a second ratio of a second expected increase in processor utilization resulting from completion of the second dependent transaction to a second cost associated with completing the second dependent transaction;

providing a first set of two or more resource requests to the one or more physical resources prior to providing a second set of two or more resource requests to the one or more physical resources if the first dependency weight measure is greater than the second dependency weight measure; and

providing the second set of two or more resource requests to the one or more physical resources prior to providing the first set of two or more resource requests to the one or more physical resources if the second dependency weight measure is greater than the first dependency weight measure.

20. The one or more processor readable storage devices of claim 19, wherein receiving the plurality of I/O requests comprises receiving the plurality of I/O requests at an I/O scheduler for the one or more physical resources, the method further comprising, prior to receiving the plurality of I/O requests at the I/O scheduler:

receiving the plurality of I/O requests at a file system;

adding the first dependent transaction identifier to the first set of two or more I/O requests of the plurality that are associated with the first dependent transaction; and

providing the first set of two or more I/O requests with the first dependent transaction identifier to the I/O scheduler.

21. A computing system, comprising:

a central processing unit;

one or more physical resources in communication with the central processing unit;

an operating system executable by the central processing unit, the operating system including a CPU scheduler, a file system and an input/output (I/O) scheduler for providing I/O requests to the one or more physical resources, the CPU scheduler controls execution of one or more application threads that provide the I/O requests using the file system;

code for instructing the I/O scheduler to receive the I/O requests for the one or more physical resources from the file system and to determine whether each I/O request as received from the file system includes a dependent transaction identifier; and

code for instructing the I/O scheduler to provide a set of two or more of the I/O requests having a common dependent transaction identifier to the one or more physical resources prior to providing ones of the I/O requests that do not include a dependent transaction identifier.

22. The computing system of claim 21, wherein the operating system includes a file system, the computing system further comprises:

code for instructing the file system to receive the I/O requests and determine whether each of the I/O requests is part of a dependent transaction; and

code for instructing the file system to add the common dependent transaction identifier to the set of two or more I/O requests after determining that the two or more I/O requests are part of a first dependent transaction.

23. The computing system of claim 21, further comprising:

one or more applications executable by the central processing unit, the one or more applications add the common dependent transaction identifier to the set of two or more I/O requests when the two or more I/O requests are part of a first dependent transaction, the one or more applications provide the I/O requests to the I/O scheduler after adding the common dependent transaction identifier.

24. A method of scheduling requests for resources in computing systems, comprising:

receiving a plurality of requests for one or more physical resources in a computing system;

determining a measure of processor utilization in the computing system;

determining whether the measure of processor utilization is within a threshold utilization;

if the measure of processor utilization is within the threshold, providing the plurality of requests to the one or more physical resources in a first sequence; and

if the measure of processor utilization is outside of the threshold;

determining if individual requests of the plurality are associated with one or more dependent transactions, and;

providing the plurality of requests to the one or more physical resources in a second sequence, the providing includes providing requests of the plurality that are associated with the one or more dependent transactions prior to providing requests of the plurality that are not associated with the one or more dependent transactions.

25. The method of claim 24, wherein:

determining the measure of processor utilization comprises determining an amount of time a processor has been idle;

determining whether the measure of processor utilization is within the threshold comprises determining if the amount of time the processor has been idle is less than a threshold idle time;

the measure of processor utilization is within the threshold if the amount of time the processor has been idle is less than the threshold idle time; and

the measure of processor utilization is outside of the threshold if the amount of time the processor has been idle is greater than the threshold idle time.

26. The method of claim 24, wherein:

the one or more physical resources include a non-volatile storage system;

the plurality of requests is a plurality of I/O requests designating the non-volatile storage system;

providing the plurality of I/O requests to the non-volatile storage system in the first sequence includes;

determining an I/O cost of each I/O request in the plurality of I/O requests; and

sequentially providing the I/O requests to the non-volatile storage system based on the I/O cost beginning with a first I/O request having a lowest I/O cost and ending with a second I/O request having a largest I/O cost.

27. The method of claim 26, wherein:

determining if individual requests of the plurality are associated with the one or more dependent transactions includes determining that a first set of two or more I/O requests is associated with a first dependent transaction and that a second set of two or more I/O requests is associated with a second dependent transaction;

the method further comprises determining a first dependency weight measure for the first set of two or more I/O requests and determining a second dependency weight measure for the second set of two or more I/O requests; and

providing the plurality of requests to the one or more physical resources in the second sequence includes providing the first set of two or more I/O requests prior to providing the second set of two or more I/O requests if the first dependency weight measure is greater than the second dependency weight measure and providing the second set of two or more I/O requests prior to providing the first set of two or more I/O requests if the second dependency weight measure is greater than the first dependency weight measure.

28. The method of claim 24, wherein:

determining the measure of processor utilization is performed by a processor scheduler;

providing the plurality of resource requests to the one or more physical resources is performed by a resource scheduler associated with the one or more physical resources, the resource scheduler including a first operational mode and a second operational mode;

the method further comprises placing the resource scheduler into the second operational mode if the measure of processor utilization is not within the threshold and the resource scheduler is currently in the first operational mode, the second sequence being associated with the second operational mode.

29. The method of claim 28, further comprising:

placing the resource scheduler into the first operational mode if the measure of processor utilization is within the threshold and the resource scheduler is currently in the second operational mode, the first sequence being associated with the first operational mode.

30. The method of claim 28, further comprising:

placing the resource scheduler into the first operational mode if the resource scheduler is currently in the second operational mode and there are no outstanding resource requests for the one or more physical resources that are associated with a dependent transaction.