Process scheduler having multiple adaptive partitions associated with process threads accessing mutexes and the like

• US 8,544,013 B2
• Filed: 03/08/2006
• Issued: 09/24/2013
• 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: Dodge, Dan, Danko, Attilla, Marineau-Mes, Sebastien, van der Veen, Peter, Burgess, Colin, Fletcher, Thomas, Stecher, Brian
• Primary Examiner(s): An, Meng
• Assistant Examiner(s): LEE, TAMMY EUNHYE
• Application Number:
  US11/371,639
• Publication Number:
  US 20070061809A1
• Time in Patent Office: 2,757 Days
• Field of Search: 718/100, 718/102, 718/104
• US Class Current: 718/103
• 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 a corresponding processor budget that is assigned to it. The process threads include a mutex holding thread and a mutex waiting thread. The mutex holding thread is associated with a first adaptive partition and may gain exclusive access to a mutex object. The mutex waiting thread is associated with a second adaptive partition and must wait for access to the mutex object while the mutex object is held by the mutex holding thread. The software code further includes a scheduling system that selectively allocates the processor to run the process threads based, at least in part, on the processor budget of the associated adaptive partitions. The scheduling system bills processor allocation used to run the mutex holding thread to the processor budget of the second adaptive partition when the processor budget of the first adaptive partition has been exhausted.

Claims

1. A system comprising:

a processor;

one or more memory storage units;

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 a plurality of process threads, where each of the plurality of adaptive partitions has a corresponding processor budget and the process threads comprise;

a mutex holding thread associated with a first adaptive partition of the plurality of adaptive partitions, where the mutex holding thread is configured to gain exclusive access to a mutex object,

a mutex waiting thread associated with a second adaptive partition of the plurality of adaptive partitions, where the mutex waiting thread waits for access to the mutex object when the mutex object is held by the mutex holding thread,

where the software code further comprises a scheduling system executable by the processor for selectively allocating the processor to run the process threads based, at least in part, on the processor budget of the associated adaptive partitions, and

where the scheduling system bills processor allocation used to run the mutex holding thread to the processor budget of the second adaptive partition when the processor budget of the first adaptive partition has been exhausted.

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

3. The system of claim 1, where the scheduling system bills processor allocation used to run one or more process threads working on behalf of the mutex holding thread to the processor budget of the first adaptive partition.

4. The system of claim 1, and further comprising one or more mutex waiting threads associated with one or more further adaptive partitions of the plurality of adaptive partitions, where the one or more mutex waiting thread wait for access to the mutex object when the mutex object is held by the mutex holding thread.

5. The system of claim 4, where the mutex waiting thread associated with the second adaptive partition is the process thread which, of all the mutex waiting threads, the scheduling system is most likely to run next upon availability of the mutex object.

6. The system of claim 1, where the scheduling system generates an ordering function value for each of the plurality of adaptive partitions associated with a mutex waiting thread, and where the scheduling system compares one or more of the ordering function values to one another to determine which, of all the mutex waiting threads, the scheduling system is most likely to run next upon availability of the mutex object.

7. The system of claim 1, where the mutex holding thread has a first run priority level and the mutex waiting thread has a second run priority level that is higher than the first run priority level, and where the scheduling system raises the priority level of the mutex holding thread to the second priority level.

8. 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 a plurality of process threads, each of the adaptive partitions having a processor budget, the method comprising:

generating a mutex holding thread associated with a first adaptive partition of the plurality of adaptive partitions;

holding a mutex object using the mutex holding thread;

generating a mutex waiting thread associated with a second adaptive partition of the plurality of adaptive partitions;

preventing the mutex waiting thread from accessing the mutex object while the mutex object is held by the mutex holding thread; and

billing processor allocation used to run the mutex holding thread to the processor budget of the second adaptive partition when the processor budget of the first adaptive partition has been exhausted.

9. The method of claim 8, where the mutex holding thread has a first run priority level and the mutex waiting thread has a second run priority level that is higher than the first run priority level, and where the method further comprises raising the priority level of the mutex holding thread to the second priority level.

10. The method of claim 8, and further comprising billing processor allocation used to run one or more process threads working on behalf of the mutex holding thread to the processor budget of the first adaptive partition.

11. 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 a plurality of process threads, each of the adaptive partitions having scheduling attributes including a processor budget, the method comprising:

generating a mutex holding thread associated with a first adaptive partition of the plurality of adaptive partitions;

holding a mutex object using the mutex holding thread;

generating a plurality of mutex waiting threads associated with two or more further adaptive partitions of the plurality of adaptive partitions;

preventing the mutex waiting thread from accessing the mutex object while the mutex object is held by the mutex holding thread; and

determining which of the waiting threads is most likely to be run next on the processor upon release of the mutex object by the mutex holding thread;

billing processor allocation used to run the mutex holding thread to the processor budget of the adaptive partition associated with the waiting thread that is most likely to run next on the processor upon release of the mutex object by the mutex holding thread when the processor budget of the first adaptive partition has been exhausted.

12. The method of claim 11, where the mutex holding thread has a first run priority level and the waiting thread has a second run priority level that is higher than the first run priority level, and where the method further comprises raising the priority level of the mutex holding thread to the second priority level.

13. The method of claim 11, and further comprising billing processor allocation used to run one or more process threads working on behalf of the mutex holding thread to the processor budget of the first adaptive partition.

14. The method of claim 11, where the operation of determining which of the mutex waiting threads is most likely to be run next on the processor upon release of the mutex object by the mutex holding thread comprises:

calculating an ordering function value for each of the adaptive partitions associated with a mutex waiting thread, where the ordering function value of a given adaptive partition is determined from one or more scheduling attributes of the given adaptive partition; and

comparing the ordering function values for each of the adaptive partitions associated with a mutex waiting thread.

15. One or more memory storage units comprising:

software code that is executable by a processor to generate a plurality of adaptive partitions that are each associated with a plurality of process threads, where each of the plurality of adaptive partitions has a corresponding processor budget and the process threads comprise

a mutex holding thread associated with a first adaptive partition of the plurality of adaptive partitions, where the mutex holding thread operates to gain exclusive access to a mutex object,

a mutex waiting thread associated with a second adaptive partition of the plurality of adaptive partitions, where the mutex waiting thread waits for access to the mutex object when the mutex object is held by the mutex holding thread; and

a scheduling system forming part of the software code, where the scheduling system selectively allocates the processor to run the process threads based, at least in part, on the processor budget of the associated adaptive partitions, and where the scheduling system operates to determine which of the mutex waiting threads is most likely to be run next on the processor upon release of the mutex object by the mutex holding thread and bills processor allocation used to run the mutex holding thread to the processor budget of the adaptive partition associated with the mutex waiting thread that is most likely to run next on the processor upon release of the mutex object by the mutex holding thread when the processor budget of the first adaptive partition has been exhausted; and

where the scheduling system bills processor allocation used to run the mutex holding thread to the processor budget of the second adaptive partition when the processor budget of the first adaptive partition has been exhausted.

16. The one or more memory storage units of claim 15, where the scheduling system bills processor allocation used to run one or more process threads working on behalf of the mutex holding thread to the processor budget of the first adaptive partition.

17. The one or more memory storage units of claim 15, and further comprising one or more further mutex waiting threads associated with one or more further adaptive partitions of the plurality of adaptive partitions, where the one or more further mutex waiting threads wait for access to the mutex object when the mutex object is held by the mutex holding thread.

18. The one or more memory storage units of claim 17, where the mutex waiting thread associated with the second adaptive partition is the process thread which, of all the mutex waiting threads, the scheduling system is most likely to run next upon release of the mutex object.

19. The one or more memory storage units of claim 15, where the scheduling system generates an ordering function value for each of the plurality of adaptive partitions associated with a mutex waiting thread, and where the scheduling system compares one or more of the ordering function values to one another to determine which, of all the mutex waiting threads, the scheduling system is most likely to run next upon availability of the mutex object.

20. The one or more memory storage units of claim 15, where the mutex holding thread has a first run priority level and the mutex waiting thread has a second run priority level that is higher than the first run priority level, and where the scheduling system raises the priority level of the mutex holding thread to the second priority level.

21. A system comprising:

a processor;

one or more memory storage units;

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 a plurality of process threads, where each of the plurality of adaptive partitions has one or more corresponding scheduling attributes including a processor budget, and where the process threads comprise;

a mutex holding thread associated with a first adaptive partition of the plurality of adaptive partitions, where the mutex holding thread is configured to gain exclusive access to a mutex object, a plurality of mutex waiting threads associated with two or more further adaptive partitions of the plurality of adaptive partitions, where the mutex waiting threads wait for access to the mutex object when the mutex object is held by the mutex holding thread,

where the software code further comprises a scheduling system executable by the processor for selectively allocating the processor to run the process threads based, at least in part, on the processor budget of the associated adaptive partitions, where the scheduling system operates to determine which of the waiting threads is most likely to be run next on the processor upon release of the mutex object by the mutex holding thread and bills processor allocation used to run the mutex holding thread to the processor budget of the adaptive partition associated with the waiting thread that is most likely to run next on the processor upon release of the mutex object by the mutex holding thread when the processor budget of the first adaptive partition has been exhausted.