Process Scheduling to Maximize Input Throughput

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.

What is claimed is: 
     
         1 . A system comprising:
 a plurality of processors;   an operating system executing on said plurality of processors;   a queue manager that:
 receives a scheduling graph comprising executable elements and relationships between said executable elements, said relationships comprising data dependency relationships; 
 from said scheduling graph, identifies a set of executable elements dependent on a first executable element that receives a first input; and 
 schedules said set of executable elements such that a process scheduler causes said set of executable elements to process said first input. 
   
     
     
         2 . The system of  claim 1 , said queue manager that further:
 from said scheduling graph, identifies a second set of executable elements from which said first executable element is dependent; and   schedules said second set of executable elements.   
     
     
         3 . The system of  claim 2 , said second set of executable elements being executed at an elevated priority. 
     
     
         4 . The system of  claim 1  further comprising:
 a load manager that:
 identifies a second executable element downstream from said first executable element, said second executable element being a chokepoint for processing output from said first executable element; and 
 allocates additional processing resources to said second executable element. 
 
 
     
     
         5 . The system of  claim 1 , said source being a network input device. 
     
     
         6 . The system of  claim 1 , said source being a data storage device. 
     
     
         7 . A method comprising:
 receiving a scheduling graph comprising executable elements and relationships between said executable elements;   identifying a first executable element 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;   scheduling said second executable element such that a process scheduler causes said second executable element to be executed after said first executable element.   
     
     
         8 . The method of  claim 7 , said second executable element not having a message passing relationship with said first executable element. 
     
     
         9 . The method of  claim 8  further comprising:
 identifying a third executable element from said scheduling graph, said first executable element being dependent on said third executable element; and 
 scheduling said third executable element such that said process scheduler causes said third executable element to be executed prior to said first executable element. 
 
     
     
         10 . The method of  claim 7 , said second executable element being scheduled with an elevated priority. 
     
     
         11 . The method of  claim 7  further comprising:
 receiving a plurality of input data items consumed by said first executable element. 
 
     
     
         12 . The method of  claim 11  further comprising:
 identifying a fourth executable element being dependent on said first executable element, said fourth executable element being causing said first executable element to wait to process said plurality of input data items; and 
 allocating additional memory resources to said fourth executable element. 
 
     
     
         13 . The method of  claim 12  further comprising:
 determining a current rate at which said first executable element processes said input data items; and 
 measuring a change in said current rate when said fourth executable element has been allocated said additional processing resources. 
 
     
     
         14 . The method of  claim 13  further comprising:
 when said change is positive, adding additional memory resources; and 
 when said change is not positive, removing at least some of said additional memory resources. 
 
     
     
         15 . The method of  claim 14  further comprising:
 updating said scheduling graph with said additional memory resources.