Adaptive partitioning scheduler for multiprocessing system

1. A method for operating a symmetric multiprocessing system comprising:

associating a first adaptive partition processing scheduler with a first processing unit of the symmetric multiprocessing system;

determining a merit function for each of a plurality of adaptive partitions associated with the first processing unit, where each adaptive partition associated with the first processing unit comprises a plurality of process threads, and where the merit function for each adaptive partition is based, at least in part, on whether the adaptive partition has available budget on the first processing unit;

assigning budgets for use by each partition of the adaptive partitions associated with the first processing unit based on a number of ticks occurring during an averaging window;

affirmatively determining that an adaptive partition associated with the first processing unit has available budget on the first processing unit when a number of ticks used by the adaptive partition associated with the first processing unit during a current averaging window is less than or equal to a number of ticks assigned as a budget to the adaptive partition for the first processing unit;

selectively allocating, using the first adaptive partition processing scheduler, the first processing unit of the symmetric multiprocessing system to run process threads of the adaptive partitions associated with the first processing unit based on a comparison between merit function values of the adaptive partitions associated with the first processing unit;

associating a second adaptive partition processing scheduler with a second processing unit of the symmetric multiprocessing system;

determining a merit function for each of a plurality of adaptive partitions associated with the second processing unit, where each adaptive partition associated with the second processing unit comprises a plurality of process threads, and where the merit function for each adaptive partition is based, at least in part, on whether the adaptive partition has available budget on the second processing unit; and

selectively allocating using the second adaptive partition processing scheduler, the second processing unit of the symmetric multiprocessing system to run process threads of the adaptive partitions associated with the second processing unit based on a comparison between merit function values of the adaptive partitions associated with the second processing unit.

2. The method of claim 1 , further comprising:

assigning budgets for use by each partition of the adaptive partitions associated with the second processing unit based on a number of ticks occurring during an averaging window; and

affirmatively determining that an adaptive partition associated with the second processing unit has available budget on the second processing unit when a number of ticks used by the adaptive partition associated with the second processing unit during a current averaging window is less than or equal to a number of ticks assigned as a budget to the adaptive partition for the second processing unit.

3. The method of claim 1 , further comprising:

determining the merit function for a particular partition, p, of the adaptive partitions associated with the first processing unit scheduler based, at least in part, on whether the adaptive partition has available global budget on the symmetric multiprocessing system.

4. The method of claim 2 , further comprising:

assigning a global budget for use by each partition of the adaptive partitions associated with the first processing unit based on a number of ticks occurring during an averaging window; and

affirmatively determining that an adaptive partition has available global budget on the first processing unit when a number of ticks used globally by the adaptive partition during a current averaging window is less than or equal to a number of ticks assigned as a global budget to the adaptive partition.

5. The method of claim 2 , further comprising:

determining the merit function for a particular partition, p, of the adaptive partitions associated with the second processing unit scheduler based, at least in part, on whether the adaptive partition has available global budget on the symmetric multiprocessing system.

6. The method of claim 5 , further comprising:

assigning a global budget for use by each partition of the adaptive partitions associated with the second processing unit based on a number of ticks occurring during an averaging window; and

affirmatively determining that an adaptive partition has available global budget on the second processing unit when a number of ticks used globally by the adaptive partition during a current averaging window is less than or equal to a number of ticks assigned as a global budget to the adaptive partition.

7. The method of claim 1 , further comprising:

determining the merit function for each partition, p, of the adaptive partitions associated with the first processing unit based, at least in part, on whether the adaptive partition has available global budget on the symmetric multiprocessing system; and

determining the merit function for each partition, p, of the adaptive partitions associated with the second processing unit based, at least in part, on whether the adaptive partition has available global budget on the symmetric multiprocessing system.

8. The method of claim 1 , further comprising:

determining the merit function for each partition, p, of the adaptive partitions associated with the first processing unit based, at least in part, on a priority value of a highest priority thread in the partition of the first processing unit; and

determining the merit function for each of the adaptive partitions associated with the second processing unit based, at least in part, on a priority value of a highest priority thread in the partition of the second processing unit.

9. The method of claim 1 , further comprising binding the threads of the adaptive partitions associated with the first and second processing units to one or both of the first and second processing units.

10. A method of operating a symmetric multiprocessing system having a plurality of processing units comprising:

instantiating an adaptive partition processing scheduler with respect to each of the plurality of processing units of the symmetric multiprocessing system;

assigning a budget for use by a partition of the one or more adaptive partitions based on a number of ticks occurring during an averaging window; and

determining that an adaptive partition has available budget on a corresponding processing unit when a number of ticks used by the adaptive partition during a current averaging window is less than or equal to a number of ticks assigned as a budget to the adaptive partition for the corresponding processing unit;

selectively allocating a corresponding processing unit of the symmetric multiprocessing system to run process threads of one or more adaptive partitions associated with the instantiated adaptive partition processing scheduler based on a comparison between merit function values of the one or more adaptive partitions, where each of the one or more adaptive partitions comprises a plurality of process threads, where the merit function for a particular partition, p, of the one or more adaptive partitions associated with an adaptive partition scheduler instance is based, at least in part, on whether the adaptive partition has available global budget on the corresponding processing unit of the symmetric multiprocessing system.

11. The method of claim 10 , further comprising basing a budget assigned to and used by a partition of the one or more adaptive partitions on a number of ticks occurring during an averaging window, where an adaptive partition has available global budget on a corresponding processing unit when a number of ticks used globally by the adaptive partition during a current averaging window is less than or equal to a number of ticks assigned as a global budget to the adaptive partition.

12. The method of claim 10 , further comprising basing the merit function for a particular partition, p, of the one or more adaptive partitions associated with an adaptive partition scheduler instance, at least in part, on a priority value of a highest priority thread in the particular partition.

13. The method of claim 10 , further comprising binding process threads to particular processors of the symmetric multiprocessing system.

14. A method for operating a bound multiprocessing system comprising:

instantiating an adaptive partition processing scheduler with respect to each of a plurality of processing units in the bound multiprocessing system;

assigning a budget for use by a partition of the one or more adaptive partitions based on a number of ticks occurring during an averaging window;

determining that an adaptive partition has available budget on a corresponding processing unit when a number of ticks used by the adaptive partition during a current averaging window is less than or equal to a number of ticks assigned as a budget to the adaptive partition for the corresponding processing unit

executing the instantiated adaptive partition processing schedulers to selectively allocate corresponding processing units of the bound multiprocessing system to run process threads of one or more adaptive partitions, where each of the adaptive partitions comprises a plurality of process threads,

determining a merit function value for each of the one or more adaptive partitions based, at least in part, on whether the adaptive partition has available global budget on the corresponding processing unit of the bound multiprocessing system; and

running process threads of the one or more adaptive partitions based on a comparison between merit function values of the one or more adaptive partitions.

15. The bound multiprocessing system of claim 14 , further comprising assigning a budget for use by a partition of the one or more adaptive partitions based on a number of ticks occurring during an averaging window, where an adaptive partition has available global budget on a corresponding processing unit when a number of ticks used globally by the adaptive partition during a current averaging window is less than or equal to a number of ticks assigned as a global budget to the adaptive partition.