Process scheduler employing adaptive partitioning of process threads

• US 9,424,093 B2
• Filed: 04/29/2013
• Issued: 08/23/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): KAWSAR, ABDULLAH AL
• Application Number:
  US13/872,885
• Publication Number:
  US 20130247066A1
• Time in Patent Office: 1,212 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/5038 considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration scheduling strategies G06F9/4881 and subgroups
• CPC Class Codes: G06F 9/505 considering the load
• CPC Class Codes: G06F 9/5077 Logical partitioning of resources; Management or configuration of virtualized resources specific details on emulation or internal functioning of virtual machines G06F9/455

Abstract

A system includes a processor and memory storage units storing software code. The software code comprises code for a scheduling system and for generating a plurality of adaptive partitions that are each associated with one or more process threads and that each have a corresponding processor budget. The code also is executable to, when the system is under a normal load, allocate the processor to one of the threads that is in a ready state and has the highest priority among the process threads that are in a ready state. The code is also executable to, when the system is in overload, allocate the processor to one of the process threads that is in a ready state and has the highest priority among the process threads that are in a ready state and for which the adaptive partition that the process thread is associated with has available guaranteed processor budget.

Claims

1. A system comprising:

a processor;

one or more memory storage units;

instructions stored in the one or more memory storage units, where the instructions are executable by the processor to configure the system to;

create a plurality of adaptive partitions each having an associated guaranteed processor time budget;

create a plurality of process threads each having a priority;

dynamically associating each of the plurality of process threads with any one of the plurality of adaptive partitions; and

implement a process scheduler to;

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

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

where a portion of the guaranteed processor time budget associated with each adaptive partition is billed whenever the processor is allocated to a process thread associated with the adaptive partition.

2. The system of claim 1, the plurality of process threads comprising a sending thread that sends a message and a receiving thread that receives the message;

where the guaranteed processor time budget associated the adaptive partition with which the sending thread is associated is billed when the processor is allocated to the receiving thread to process the message.

3. The system of claim 2, where the receiving thread is temporarily associated with the adaptive partition with which the sending thread is associated while the receiving thread is processing the message.

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

and where the system is in overload when all of the process threads in the ready state cannot be allocated the processor 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 guaranteed processor time budget associated with each of the plurality of adaptive partitions is dynamic and can be reallocated while the system executes.

6. 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 associated with adaptive partition with which the process thread is associated is exhausted.

7. The system of claim 6, 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 in the ready state and that has a priority higher than the priority of the process thread to which the processor is currently allocated.

8. A method of scheduling a plurality of process threads, each having a priority and each dynamically associable with an adaptive partition, for execution by a processor of a system, the method comprising:

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

associating one or more process threads from the plurality of process threads with 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 in a ready state and having a highest priority amongst process threads, of the plurality of process threads, that are in the ready state; and

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

where a portion of the guaranteed processor time budget associated with each adaptive partition is billed whenever the processor is allocated to a process thread associated with the adaptive partition,

where the guaranteed processor time budget associated with each of the plurality of adaptive partitions is dynamic and can be reallocated while the system executes.

9. The method of claim 8, further comprising:

sending a message from a sending thread of the plurality of process threads;

receiving the message by a receiving thread of the plurality of process threads; and

billing the guaranteed processor time budget associated the adaptive partition with which the sending thread is associated when the processor is allocated to the receiving thread to process the message.

10. The method of claim 9, further comprising:

temporarily associating the receiving thread with the adaptive partition with which the sending thread is associated while the receiving thread is processing the message.

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

and where the system is in overload when all of the process threads in the ready state cannot be allocated the processor 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 associated with adaptive partition with which the process thread is associated is exhausted.

13. The method of claim 12, 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 in the ready state and that has a priority higher than the priority of the process thread to which the processor is currently allocated.