Network aware process scheduling

• US 8,595,743 B2
• Filed: 05/01/2012
• Issued: 11/26/2013
• Est. Priority Date: 05/01/2012
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Concurix Corporation
• Inventors: Gounares, Alexander G., Garrett, Charles D.
• Primary Examiner(s): An, Meng
• Assistant Examiner(s): Lee, James J
• Application Number:
  US13/461,752
• Publication Number:
  US 20130117759A1
• Time in Patent Office: 574 Days
• Field of Search: None
• US Class Current: 718/104
• CPC Class Codes: G06F 9/50 Allocation of resources, e.g. of the central processing unit [CPU]
• CPC Class Codes: G06F 9/5083 Techniques for rebalancing the load in a distributed system

Abstract

A schedule graph may be used to identify executable elements that consume data from a network interface or other input/output interface. The schedule graph may be traversed to identify a sequence or pipeline of executable elements that may be triggered from data received on the interface, then a process scheduler may cause those executable elements to be executed on available processors. A queue manager and a load manager may optimize the resources allocated to the executable elements to maximize the throughput for the input/output interface. Such as system may optimize processing for input or output of network connections, storage devices, or other input/output devices.

Claims

1. A system comprising:

a plurality of processors, receiving input stream of data from a source;

a queue manager that;

receives a scheduling graph from an analyzer, said scheduling graph comprising executable elements and relationships between said executable elements, said relationships comprising data dependency relationships;

from said scheduling graph,

identifies a first executable element that receives said input stream from the source;

identifies a first set of executable elements comprising a plurality of executable elements being executed downstream from said first executable element; and

identifies a second set of executable elements comprising a plurality of executable elements being executed upstream from said first executable element;

schedules said second set of executable elements, said second set of executable elements being executed at an elevated priority by preempting other executable elements; and

schedules said first set of executable elements such that a process scheduler causes said first set of executable elements to process said input stream of data;

a load manager that;

monitors performance of said executable elements, by

when processing of said input stream of data is operating at maximum capacity, continues said monitoring;

when processing of said input stream is not operating at maximum capacity, identifies a second executable element downstream from said first executable element, said second executable element being a bottleneck for processing output from said first executable element; and

allocates additional processing resources to said second executable element until said executable elements is operating at full capacity.

2. The system of claim 1, said source being a network input device.

3. The system of claim 1, said source being a data storage device.

7. The system of claim 1, said scheduling graph being defined within a development environment.

8. The system of claim 1, said scheduling graph being defined by an analyzer executed after compilation.

9. The system of claim 1, said dependency relationships being identified after monitoring said executable elements.

10. The system of claim 9, said dependency relationships comprising a shared data object.

11. The system of claim 1, said queue manager being part of an execution environment.

12. The system of claim 1, said additional processing resources comprising executing said second executable element at an elevated priority.

13. The system of claim 1, said additional processing resources comprising assigning additional processors.

14. The system of claim 1, said additional processing resources comprising assigning additional memory resources.

4. A computerized method comprising:

receiving a scheduling graph from an analyzer, said scheduling graph comprising executable elements and relationships between said executable elements, said relationships comprising data dependency relationships;

receiving an input stream, comprising a plurality of data items from a data source, said input stream being consumed by a first executable element defined within said scheduling graph;

identifying a second executable element from said scheduling graph, said second executable element having a data dependency relationship with said first executable element;

identifying a third executable element from said scheduling graph, said first executable element being dependent on said third executable element prior to consuming said input stream;

scheduling said third executable element such that said process scheduler causes said third executable element to be executed prior to said first executable element;

scheduling said second executable element such that a process scheduler causes said second executable element to be executed after said first executable element;

identifying a fourth executable element being dependent on said first executable element, said fourth executable element causing said first executable element to wait to process said input stream; and

allocating additional processing resources to said fourth executable element;

determining a current rate at which said first executable element processes said input stream; and

measuring a change in said current rate when said fourth executable element has been allocated said additional processing resources;

when said change is positive, adding additional processing resources; and

when said change is not positive, removing at least some of said additional processing resources.

5. The method of claim 4, said second executable element not having a message passing relationship with said first executable element.

6. The method of claim 4 further comprising:

storing configuration of resource allocation in the scheduling graph.

15. The method of claim 4, said additional processing resources comprising executing said fourth executable element an elevated priority.

16. The method of claim 4, said additional processing resources comprising assigning additional processors.

17. The method of claim 4, said additional processing resources comprising assigning additional memory resources.