Adaptive partitioning for operating system

• US 9,361,156 B2
• Filed: 02/25/2013
• Issued: 06/07/2016
• Est. Priority Date: 03/14/2005
• Status: Active Grant

• Current Assignee: Malikie Innovations Limited (Key Patent Innovations Limited)
• Original Assignee: 2236008 Ontario Inc. (Blackberry Limited)
• Inventors: Dodge, Dan, Danko, Attila, Marineau-Mes, Sebastien, van der Veen, Peter, Burgess, Colin, Fletcher, Thomas, Stecher, Brian
• Primary Examiner(s): Lee, Adam
• Application Number:
  US13/776,465
• Publication Number:
  US 20140245311A1
• Time in Patent Office: 1,198 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06F 9/4887 involving deadlines, e.g. rate based, periodic
• CPC Class Codes: G06F 9/50 Allocation of resources, e.g. of the central processing unit [CPU]

Abstract

An adaptive partition scheduler is a priority-based scheduler that also provides execution time guarantees (fair-share). Execution time guarantees apply to threads or groups of threads when the system is overloaded. When the system is not overloaded, threads are scheduled based strictly on priority, maintaining strict real-time behavior. When the system is overloaded, threads are scheduled based priority of threads that are in a ready state and based on the available guaranteed processor time budget of the adaptive partition associated with each thread.

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 and comprises;

a plurality of adaptive partitions each having a respective guaranteed processor time budget and one or more process threads;

a plurality of process threads each having a priority and each belonging to any one of the plurality of adaptive partitions; and

a process scheduler executable by the processor configured to;

when the system is under a normal load, allocate the processor to a process thread, of the plurality of process threads, that is ready for execution and having the highest priority amongst process threads, of the plurality of process threads, that are ready for execution; and

when the system is in overload, allocate the processor to a process thread, of the plurality of process threads, that is ready for execution, having the highest priority amongst process threads, of the plurality of process threads, that are ready for execution and for which the adaptive partition having the process thread has an available guaranteed processor time budget.

2. The system of claim 1, where the guaranteed processor time budget of each of the plurality of adaptive partitions is dynamic and can be reallocated while the system executes.

3. The system of claim 1, where the guaranteed processor time budget is allocated and billed over successive averaging windows;

and where a portion of the guaranteed processor time budget of each adaptive partition is billed when the processor is allocated to a process thread belonging to the respective adaptive partition.

4. The system of claim 3, where the system is in overload when the processor cannot be allocated to all of the process threads that are ready for execution over the duration of one averaging window, of the successive averaging windows, and where the system is under normal load otherwise.

5. The system of claim 1, where the process thread to which the processor is allocated runs until the process thread is finished, is blocked, or the guaranteed processor time budget of the adaptive partition having the process thread is exhausted.

6. The system of claim 1, where the process thread to which the processor is allocated further runs until the process thread is preempted and the processor is allocated to another process thread, of the plurality of process threads, that is ready for execution and that has a priority higher than the priority of the process thread to which the processor is currently allocated.

7. The system of claim 1, where a process thread, of the plurality of process threads, is ready for execution when the process thread is any of:

in a ready state and in a ready queue.

8. A method of scheduling a plurality of process threads, each having a priority, for execution by a processor of a system, the method comprising:

creating a plurality of adaptive partitions each having a respective guaranteed processor time budget;

assigning one or more process threads from the plurality of process threads to each of the plurality of adaptive partitions;

when the processor is under a normal load, allocating the processor to a process thread, of the plurality of process threads, that is ready for execution and having the highest priority amongst process threads, of the plurality of process threads, that are ready for execution; and

when the processor is in overload, allocating the processor to a process thread, of the plurality of process threads, that is ready for execution, having the highest priority amongst process threads, of the plurality of process threads, that are ready for execution state and for which the adaptive partition having the process thread has an available guaranteed processor time budget.

9. The method of claim 8, where the guaranteed processor time budget of each of the plurality of adaptive partitions is dynamic and can be reallocated while the system executes.

10. The method of claim 8, where the guaranteed processor time budget is allocated and billed over successive averaging windows;

and where a portion of the guaranteed processor time budget of each adaptive partition is billed when the processor is allocated to a process thread belonging to the adaptive partition.

11. The method of claim 10, where the system is in overload when the processor cannot be al located to all of the process threads that are ready for execution over the duration of one averaging window, of the successive averaging windows, and where the system is under normal load otherwise.

12. The method of claim 8, where the process thread to which the processor is allocated runs until the process thread is finished, is blocked, or the guaranteed processor time budget of the adaptive partition having the process thread is associated is exhausted.

13. The method of claim 8, where the process thread to which the processor is allocated further runs until the process thread is preempted and the processor is allocated to another process thread, of the plurality of process threads, that is ready for execution and that has a priority higher than the priority of the process thread to which the processor is currently allocated.

14. The method of claim 8, where a process thread, of the plurality of process threads, is ready for execution when the process thread is any of:

in a ready state and in a ready queue.