Process scheduler employing ordering function to schedule threads running in multiple adaptive partitions

• US 7,870,554 B2
• Filed: 03/08/2006
• Issued: 01/11/2011
• Est. Priority Date: 03/14/2005
• Status: Active Grant

• Current Assignee: Malikie Innovations Limited (Key Patent Innovations Limited)
• Original Assignee: QNX Software Systems Company (Blackberry Limited)
• Inventors: Danko, Attilla, Stecher, Brian, Fletcher, Thomas, Marineau-Mes, Sebastien, Burgess, Colin, Dodge, Dan, van der Veen, Peter
• Primary Examiner(s): Puente; Emerson C
• Assistant Examiner(s): Truong; Camquy
• Application Number:
  US11/371,634
• Publication Number:
  US 20070061788A1
• Time in Patent Office: 1,770 Days
• Field of Search: 718102-104
• US Class Current: 718/102
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues

Abstract

A system includes a processor, one or more memory storage units, and software code stored in the memory storage units. The software code is executable by the processor to generate a plurality of adaptive partitions that are each associated with one or more process threads. Each of adaptive partition has one or more corresponding assigned scheduling attributes. The software code includes a scheduling system for selectively allocating the processor to run process threads based on a comparison between ordering function values for each adaptive partition. Ordering function values are calculated based on scheduling attributes of the corresponding adaptive partition. A critical ordering function value also may be calculated and used to determine the proper manner of billing an associated adaptive partition for the processor allocation used to run its associated critical threads. Methods of implementing various aspects of such a system are also set forth.

Claims

1. A system comprising:

a processor;

one or more memory storage units; and

software code stored in the one or more memory storage units,

where the software code is executable by the processor to generate a plurality of adaptive partitions, where one or more process threads are associated with each adaptive partition and each process thread has a corresponding priority value within the associated adaptive partition, where each of the plurality of adaptive partitions has one or more corresponding scheduling attributes, where the one or more corresponding scheduling attributes of each of the plurality of adaptive partitions comprise a guaranteed budget corresponding to a guaranteed amount of processor allocation that may be used to run the one or more process threads associated with the adaptive partition, and where execution of each process thread of the one or more process threads of the associated adaptive partition is individually attributed and accounted against one or more of the scheduling attributes of the associated adaptive partition,

where the software code further comprises a scheduling system executable by the processor for selectively allocating the processor to run the process threads of the plurality of adaptive partitions based on a comparison between ordering function values of the plurality of adaptive partitions, and

where the ordering function value for each adaptive partition is calculated using variables respectively associated with each adaptive partition, where the variables comprise two or more variables comprising

(a) whether the adaptive partition has available guaranteed budget,

(b) whether the adaptive partition has available critical budget,

(c) the corresponding priority value of the process thread associated with the adaptive partition having a highest corresponding priority value that is ready to run,

(d) a relative fraction of the guaranteed budget used during an averaging window over which the guaranteed budget is assigned, and

(e) a current rate of processor consumption by the adaptive partition,

where the ordering function value generated for the adaptive partition is dependent on an amount of the available guaranteed budget of the adaptive partition.

2. The system of claim 1, where the processor comprises a symmetric multiprocessor.

3. The system of claim 1, where an adaptive partition of the plurality of adaptive partitions is assigned a critical budget when the adaptive partition is associated with a critical thread.

4. The system of claim 1, where the two or more variables include whether the adaptive partition has the available critical budget.

5. The system of claim 1, where the two or more variables include whether the adaptive partition has the available guaranteed budget.

6. The system of claim 5, where the scheduling system microbills the guaranteed time budget of an adaptive partition of the plurality of adaptive partitions for a processor allocation used to run the one or more process threads associated with the adaptive partition.

7. The system of claim 1, where the two or more variables include the current rate of processor consumption used to run the one or more process threads associated with the adaptive partition.

8. The system of claim 1, where the two or more variables include the relative fraction of guaranteed budget used during the averaging window over which the guaranteed budget is assigned.

9. A method of operating a processing system to execute scheduling system software stored in a memory of the processing system, where the processing system includes a processor that executes the scheduling system software stored in the memory where the processor executes the scheduling system software stored in memory to perform operations comprising:

generating a plurality of adaptive partitions;

associating one or more process threads with each adaptive partition, where each of the one or more process threads has a corresponding priority value within the adaptive partition;

executing the process scheduler software to assign scheduling attributes to each adaptive partition, where the scheduling attributes of each adaptive partition comprise a guaranteed budget corresponding to a guaranteed amount of processor allocation that may be used to run the one or more process threads associated with the adaptive partition, and where execution of each process thread of the one or more process threads of the adaptive partition is individually attributed to and accounted against one or more of the scheduling attributes of the adaptive partition;

generating an ordering function value for each adaptive partition based on the scheduling attributes of the adaptive partition, where the ordering function value for each adaptive partition is determined using variables respectively associated with each adaptive partition, where the variables include two or more variables comprising

(a) whether the adaptive partition has available guaranteed budget,

(b) whether the adaptive partition has available critical budget,

(c) the corresponding priority value of the process thread associated with the adaptive partition having a highest corresponding priority value that is ready to run,

(d) a relative fraction of the guaranteed budget used during an averaging window over which the guaranteed budget is assigned, and

(e) a current rate of processor consumption by the adaptive partition; and

selectively allocating the processor to run the process threads of the plurality of adaptive partitions based on a comparison between the ordering function values of the plurality of adaptive partitions,

where the ordering function value generated for the adaptive partition is dependent on an amount of the available guaranteed budget of the adaptive partition.

10. The method of claim 9, where the ordering function value that is generated for an adaptive partition of the plurality of adaptive partitions is dependent on whether the adaptive partition has the available critical budget.

11. The method of claim 10, where generation of the ordering function value for an adaptive partition of the plurality of adaptive partitions associated with a critical thread is dependent on the scheduling attributes for the adaptive partition comprising:

a run priority level for the critical thread; and

a ready state of the critical thread.

12. The method of claim 11, where the ordering function value that is generated for the adaptive partition associated with the critical thread is dependent on whether the run priority level of the critical thread is a highest run priority level of any ready process thread associated with the adaptive partition.

13. The method of claim 9, where the scheduling system microbills the guaranteed time budget of an adaptive partition of the plurality of adaptive partitions for a processor allocation used to run the one or more process threads associated with the adaptive partition.

14. The method of claim 9, where the ordering function value generated for an adaptive partition of the plurality of adaptive partitions is dependent on a rate of processor time consumption used to run the one or more process threads associated with the adaptive partition.

15. The method of claim 9, where the ordering function value generated for an adaptive partition of the plurality of adaptive partitions is dependent on the relative fraction of the guaranteed budget used during the averaging window over which the guaranteed budget is assigned.

16. One or more memory storage units comprising:

software code executable by a processor to generate a plurality of adaptive partitions, where one or more process threads are associated with each adaptive partition and each process thread has a corresponding priority value within the associated adaptive partition, where each of the plurality of adaptive partitions has one or more corresponding scheduling attributes, where the one or more corresponding scheduling attributes of each the plurality of adaptive partitions comprise a guaranteed budget corresponding to a guaranteed amount of processor allocation that may be used to run the one or more process threads associated with the adaptive partition, and where execution of each process thread of the one or more process threads of each adaptive partition is individually attributed and accounted against one or more of the scheduling attributes of the associated adaptive partition; and

a scheduling system in the software code, where the scheduling system is executable by the processor for selectively allocating the processor to run the process threads based on a comparison between ordering function values calculated for the plurality of adaptive partition, and where the ordering function value for each adaptive partition is calculated using variables respectively associated with each adaptive partition, where the variables include two or more variables comprising

(a) whether the adaptive partition has available guaranteed budget,

(b) whether the adaptive partition has available critical budget, the corresponding priority value of the process thread associated with the adaptive partition having a highest corresponding priority value that is ready to run,

(c) a relative fraction of the guaranteed budget used during an averaging window over which the guaranteed budget is assigned, and

(d) a current rate of processor consumption by the adaptive partition,

where the ordering function value generated for the adaptive partition is dependent on an amount of the available guaranteed budget of the adaptive partition.

17. The one or more memory storage units of claim 16, where the ordering function value for an adaptive partition of the plurality of adaptive partitions is dependent on whether the adaptive partition has the available critical budget.

18. The one or more memory storage units of claim 16, where the ordering function value for an adaptive partition of the plurality of adaptive partitions is further dependent on whether the adaptive partition is associated with a critical thread, whether the critical thread is in a ready state, and whether the critical thread has a priority level that is a highest run priority level of any ready process thread associated with the adaptive partition.

19. The one or more memory storage units of claim 16, where the scheduling attributes of each adaptive partition comprise a guaranteed time budget corresponding to a guaranteed amount of processor allocation that may be used to run the process threads associated with the adaptive partition, and where the ordering function value of an adaptive partition is dependent on an available amount of the guaranteed time budget of the adaptive partition.

20. The one or more memory storage units of claim 19, where the scheduling system microbills the guaranteed time budget of an adaptive partition of the plurality of adaptive partitions for a processor allocation used to run one or more process threads associated with the adaptive partition.

21. The one or more memory storage units of claim 16, where the ordering function value of a given adaptive partition of the plurality of adaptive partitions is dependent on the current rate of processor consumption used to run the one or more process threads associated with the given adaptive partition.

22. The one or more memory storage units of claim 16, where the ordering function value of a given adaptive partition of the plurality of adaptive partitions is dependent on the current rate of processor time consumption used to run the one or more process threads associated with the given adaptive partition.

23. The one or more memory storage units of claim 16, where the ordering function value of a given adaptive partition of the plurality of adaptive partitions is dependent on the relative fraction of the guaranteed budget used during the averaging window over which the guaranteed budget is assigned.