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

• US 20070061788A1
• Filed: 03/08/2006
• Published: 03/15/2007
• Est. Priority Date: 03/14/2005
• Status: Active Grant

• Current Assignee: Malikie Innovations Limited (Key Patent Innovations Limited)
• Original Assignee: QNX Software Systems Limited (Canada) (Blackberry Limited)
• Inventors: Danko, Attilla, Stecher, Brian, Dodge, Dan, Fletcher, Thomas, Marineau-Mes, Sebastien, Burgess, Colin, Veen, Peter
• Granted Patent: US 7,870,554 B2
• Time in Patent Office: Days
• US Class Current: 717/140
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues

Abstract

A system is set forth that includes a processor, one or more memory storage units, and software code stored in the one or more 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 the plurality of adaptive partitions has one or more corresponding scheduling attributes that are assigned to it. The software code further includes a scheduling system that is executable by the processor for selectively allocating the processor to run the process threads based on a comparison between ordering function values for each adaptive partition. The ordering function value for each adaptive partition is calculated using one or more of the scheduling attributes of the corresponding adaptive partition. The scheduling attributes that may be used to calculate the ordering function value include, for example, 1) the process budget, such as a guaranteed time budget, of the adaptive partition, 2) the critical budget, if any, of the adaptive partition, 3) the rate at which the process threads of an adaptive partition consume processor time, or the like. For each adaptive partition that is associated with a critical thread, a critical ordering function value also may be calculated. The scheduling system may compare the ordering function value with the critical ordering function value of the adaptive partition to determine the proper manner of billing the 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 that are each associated with one or more process threads, and where each of the plurality of adaptive partitions has one or more corresponding scheduling attributes,

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

where the ordering function value for each adaptive partition is calculated using one or more of the scheduling attributes of the corresponding adaptive partition.

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

3. The system of claim 1, where the ordering function value for an adaptive partition is dependent on whether the adaptive partition is associated with a critical thread.

4. The system of claim 1, where the ordering function value for an adaptive partition is 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 run priority level that is the highest run priority level of any ready process thread associated with the adaptive partition.

5. The system of claim 3, where the scheduling attributes of an adaptive partition associated with a critical thread comprise a critical budget, and where the ordering function value for the adaptive partition is further dependent on whether an amount of the critical budget is available for running the critical thread of the adaptive partition or has otherwise been exhausted.

6. The system of claim 1, 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.

7. The system of claim 6, where the scheduling system microbills the guaranteed time budget of an adaptive partition for processor allocation used to run process threads associated with the adaptive partition.

8. The system of claim 3, where the scheduling attributes of each adaptive partition comprises 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.

9. The system of claim 1, where the ordering function value of a given adaptive partition is dependent on a current rate of processor time consumption used to run the process threads associated with the given adaptive partition.

10. The system of claim 6, where the ordering function value of a given adaptive partition is dependent on a current rate of processor time consumption used to run the process threads associated with the given adaptive partition.

11. The system of claim 8, where the ordering function value of a given adaptive partition is dependent on a rate of processor time consumption used to run the process threads associated with the given adaptive partition.

12. A method of operating a process scheduler in a processing system having a processor and a plurality of adaptive partitions that are each associated with one or more process threads, each of the adaptive partitions having one or more scheduling attributes, the method comprising:

generating an ordering function value for each adaptive partition based on the scheduling attributes of 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.

13. The method of claim 12, where the ordering function value that is generated for an adaptive partition is dependent on whether the adaptive partition is associated with a critical thread.

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

a run priority level for the critical thread; and

a ready state of the critical thread.

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

16. The method of claim 13, where the scheduling attributes of an adaptive partition associated with a critical thread comprise a critical budget, and where the ordering function value that is generated for the adaptive partition is dependent on whether an amount of the critical budget is available for running the critical thread of the adaptive partition or has otherwise been exhausted.

17. The method of claim 12, 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 generated for the adaptive partition is dependent on an available amount of the guaranteed time budget of the adaptive partition.

18. The method of claim 17, where the scheduling system microbills the guaranteed time budget of an adaptive partition for processor allocation used to run process threads associated with the adaptive partition.

19. The method of claim 12, where the ordering function value generated for an adaptive partition is dependent on a rate of processor time consumption used to run the process threads associated with the adaptive partition.

20. One or more memory storage units comprising:

software code executable by a processor to generate a plurality of adaptive partitions that are each associated with one or more process threads, where each of the plurality of adaptive partitions has a corresponding processor budget, and where each of the plurality of adaptive partitions has one or more corresponding scheduling attributes; 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 each adaptive partition, and where the ordering function value for each adaptive partition is calculated using one or more of the scheduling attributes of the corresponding adaptive partition.

21. The one or more memory storage units of claim 20, where the ordering function value for an adaptive partition is dependent on whether the adaptive partition is associated with a critical thread.

22. The one or more memory storage units of claim 20, where the ordering function value for an adaptive partition is 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 the highest run priority level of any ready process thread associated with the adaptive partition.

23. The one or more memory storage units of claim 21, where the scheduling attributes of an adaptive partition associated with a critical thread comprise a critical budget, and where the ordering function value for the adaptive partition is further dependent on whether an amount of the critical budget is available for running the critical thread of the adaptive partition or has otherwise been exhausted.

24. The one or more memory storage units of claim 20, 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.

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

26. The one or more memory storage units of claim 23, 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.

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

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

29. A method of operating a process scheduler in a processing system having a processor and a plurality of adaptive partitions that are each associated with one or more process threads, where each of the adaptive partitions has one or more scheduling attributes, the method comprising:

assigning a processor budget to each of the adaptive partitions as one of the scheduling attributes;

assigning a critical budget to each adaptive partition associated with a critical thread as a further one of the scheduling attributes;

generating an ordering function value for each adaptive partition based on one or more of the scheduling attributes of the adaptive partition;

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

generating a critical ordering function value for each adaptive partition associated with a critical thread, where the critical ordering function value is dependent on the processor budget for the adaptive partition;

billing the processor budget of an adaptive partition for processor allocation used to run the process threads associated with the adaptive partition; and

billing the critical budget of an adaptive partition for processor allocation used to run critical threads associated with an adaptive partition, where billing of the critical budget is based on a comparison between the ordering function value and the critical ordering function value of the adaptive partition.

30. The method of claim 29, where the ordering function value that is generated for an adaptive partition is dependent on whether the adaptive partition is associated with a critical thread.

31. The method of claim 29, where the processor budget comprises 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 generated for the adaptive partition is dependent on an available amount of the guaranteed time budget of the adaptive partition.

32. The method of claim 29, where the processor budget of an adaptive partition is microbilled for processor allocation used to run the process threads associated with the adaptive partition.

33. The method of claim 29, where the critical budget of an adaptive partition is microbilled for processor allocation used to run critical threads associated with the adaptive partition, and where microbilling of the critical budget is based on a comparison between the ordering function value and the critical ordering function value of the adaptive partition.