Process scheduler employing adaptive partitioning of process threads

• US 20070226739A1
• Filed: 12/22/2005
• Published: 09/27/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: Stecher, Brian, Dodge, Dan, Fletcher, Thomas, Marineau-Mes, Sebastien, Burgess, Colin, Veen, Peter, Danko, Attila
• Granted Patent: US 8,434,086 B2
• Time in Patent Office: Days
• US Class Current: 718/102
• 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 is set forth that comprises a processor, such as a single processor or symmetric multiprocessor, and one or more memory storage units. The system also includes software code that is stored in the memory storage units. The software code is executable by the processor and comprises code for generating a plurality of adaptive partitions that are each associated with one or more software threads. Each of the adaptive partitions has a corresponding processor budget. The code also is executable to generate at least one sending thread and at least one receiving thread. The receiving thread responds to communications from the sending thread to execute one or more tasks corresponding to the communications. A scheduling system also forms at least part of the code that is executable by the processor. In operation, the scheduling system selectively allocates the processor to each sending and receiving thread based, at least in part, on the processor budget of the adaptive partition associated with the respective thread. In this type of sending/receiving environment, the scheduling system bills the processor budget of the adaptive partition associated with the sending thread for processor allocation used by the receiving thread to respond to communications sent by the sending 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

at least one sending thread,

at least one receiving thread that is responsive to communications from the at least one sending thread to execute one or more tasks corresponding to the communications, and

a scheduling system executable by the processor for selectively allocating the processor to the at least one sending thread and the at least one receiving thread based, at least in part, on a processor budget associated with the at least one sending thread, where the scheduling system bills the processor budget associated with the at least one sending thread for processor allocation used by the at least one receiving thread to respond to the communications sent by the at least one sending thread.

2. The system of claim 1, where the scheduling system is a part of an operating system.

3. The system of claim 1, where the processor is a symmetric multiprocessor.

4. The system of claim 1, where the scheduling system microbills the processor budget associated with the at least one sending thread for processor allocation used by the at least one receiving thread to respond to the communications sent by the at least one sending thread.

5. The system of claim 1, where the scheduling system associates the at least one sending thread with an adaptive partition, and where the processor budget associated with the at least one sending thread corresponds to a processor budget that is assigned to the adaptive partition associated with the at least one sending thread.

6. The system of claim 5, where the scheduling system microbills the processor budget of the adaptive partition associated with the at least one sending thread for processor allocation used by the at least one receiving thread to respond to the communications sent by the at least one sending thread.

7. 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 as a plurality of threads, the plurality of threads including at least one sending thread and at least one receiving thread; and

a scheduling system included in the software code and executable by the processor for selectively allocating the processor to execute the at least one sending and the at least one receiving thread based, at least in part, on processor budgets associated with each thread, and where the scheduling system bills the processor budget associated with the at least one sending thread for processor allocation used by the at least one receiving thread to respond to communications sent by the at least one sending thread.

8. The system of claim 7, where the scheduling system is a part of an operating system.

9. The system of claim 7, where the processor is a symmetric multiprocessor.

10. The system of claim 7, where the scheduling system microbills the processor budget associated with the at least one sending thread for processor allocation used by the at least one receiving thread to respond to communications sent by the at least one sending thread.

11. The system of claim 7, where the scheduling system associates the at least one sending thread with an adaptive partition, and where the processor budget associated with the at least one sending thread corresponds to a processor budget that is assigned to the adaptive partition.

12. The system of claim 11, where the scheduling system microbills the processor budget of the adaptive partition associated with the at least one sending thread for processor allocation used by the at least one receiving thread to respond to communications sent by the at least one sending thread.

13. 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 that are each associated with one or more process threads, where each of the plurality of adaptive partitions has a corresponding processor budget,

at least one sending thread associated with a first adaptive partition of the plurality of adaptive partitions,

at least one receiving thread associated with a second adaptive partition of the plurality of adaptive partitions, where the at least one receiving thread responds to communications from the at least one sending thread by executing one or more tasks corresponding to the communication, and

a scheduling system executable by the processor for selectively allocating the processor to the at least one sending thread and the at least one receiving thread based, at least in part, on the processor budgets of the first and second adaptive partitions, where the scheduling system bills the processor budget of the first adaptive partition for processor allocation used by the at least one receiving thread to respond to the communications sent by the at least one sending thread.

14. The system of claim 13, where the scheduling system is a part of an operating system.

15. The system of claim 13, where the processor is a symmetric multiprocessor.

16. The system of claim 13, where the scheduling system microbills the processor budget of the adaptive partition associated with the at least one sending thread for processor allocation used by the at least one receiving thread to respond to the communications sent by the at least one sending thread.

17. A method of operating a process scheduler in a processing system having a plurality of software threads, where the plurality of software threads include at least one sending thread and at least one receiving thread responsive to communications sent by the at least one sending thread, and where the at least one sending thread is associated with a first adaptive partition having a predetermined processor budget and the at least one receiving thread is associated with a second adaptive partition having a further predetermined processor budget, the method comprising:

scheduling execution of the sending thread, where the sending thread sends a communication to the receiving thread;

scheduling execution of the receiving thread; and

billing the processor budget of the first adaptive partition for processor allocation used by the receiving thread to respond to communications sent by the sending thread.

18. The method of claim 17, where the billing operation comprises microbilling the processor budget of the first adaptive partition for processor allocation used by the receiving thread to respond to communications sent by the sending thread.

19. A storage medium including software code used to execute a method of operating a process scheduler in a processing system having a plurality of software threads, where the plurality of software threads include at least one sending thread and at least one receiving thread responsive to communications sent by the at least one sending thread, and where the at least one sending thread is associated with a first adaptive partition having a predetermined processor budget and the at least one receiving thread is associated with a second adaptive partition having a further predetermined processor budget, and where the method comprises:

scheduling execution of the sending thread, where the sending thread sends a communication to the receiving thread;

scheduling execution of the receiving thread; and

billing the processor budget of the first adaptive partition for processor allocation used by the receiving thread to respond to communications sent by the sending thread.

20. The storage medium of claim 19, where the billing operation comprises microbilling the processor budget of the first adaptive partition for processor allocation used by the receiving thread to respond to communications sent by the sending thread.

21. A process scheduling system comprising:

a first adaptive partition associated with a sending thread and having a first predetermined processor budget;

a second adaptive partition associated with a receiving thread and having a second predetermined processor budget, where the receiving thread responds to a communication sent by the sending thread by executing one or more tasks corresponding to the communication;

a process scheduler adapted to selectively allocate a processor to the sending thread and the receiving thread based, at least in part, on the first and second predetermined processor budgets of the first and second adaptive partitions, where the process scheduler bills the first predetermined processor budget of the first adaptive partition for processor allocation used by the receiving thread to respond to the communication sent by the sending thread.

22. The process scheduling system of claim 21, where the processor is a symmetric multiprocessor.

23. The process scheduling system of claim 21, where the process scheduler microbills the first predetermined processor budget of the first adaptive partition associated for processor allocation used by the receiving thread to respond to the communications sent by the sending thread.