Adaptive partitioning for operating system

• US 20060206887A1
• Filed: 08/31/2005
• Published: 09/14/2006
• 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 Van Der, Danko, Attila
• Granted Patent: US 8,387,052 B2
• Time in Patent Office: Days
• US Class Current: 717/161
• 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

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. Even when overloaded, the scheduler provides real-time guarantees to a set of critical threads, as specified by the system architect.

Claims

1. A method for scheduling in an operating system comprising:

creating one or more adaptive partitions comprising one or more threads or one or more group of threads in an operating system;

designating one or more critical threads;

executing the threads by the operating system if a CPU budget is available for use by the partition; and

allowing use of an additional amount of CPU budget for critical threads even when the adaptive partition comprising the critical thread has exhausted its CPU budget.

2. The method of claim 1, further comprising:

specifying one or more adaptive partition parameters;

assigning each adaptive partition a CPU time budget as a percentage of an overall system budget; and

applying one or more minimum CPU percentage execution time guarantees to the threads or the groups of threads when the operating system is overloaded.

3. The method of claim 1, further comprising:

calculating the CPU budget consumed by the adaptive partition over a sliding time window for all partitions; and

deducting amounts of CPU budget consumed by the adaptive partition.

4. The method of claim 2, where specifying adaptive partition parameters comprises:

designating the adaptive partition as critical;

specifying a list of processes that are initially part of each adaptive partition;

specifying a length of the sliding time window;

specifying a guaranteed CPU utilization allocated to an individual adaptive partition; and

setting a maximum critical time budget of the individual adaptive partition, where the maximum critical time budget is an amount of time all critical threads in the adaptive partition are allowed to use over the adaptive partition'"'"'s CPU time budget.

5. The method of claim 4, where the maximum number of adaptive partitions is dynamically configured.

6. The method of claim 4, further comprising modifying the adaptive partition parameters at run time.

7. The method of claim 4, where modifying comprises:

re-distributing the guaranteed CPU utilization between different adaptive partitions; and

modifying the critical time budget.

8. The method of claim 6, further comprising allowing modifications to the adaptive partition parameters by a code with a specified privilege level.

9. The method of claim 6, further comprising:

specifying one or more operating modes comprising a set of adaptive partition parameters specified at boot-up; and

switching automatically from a first operating mode to a second operating mode at run-time.

10. The method of claim 1, further comprising providing a notification mechanism to notify a system monitor when an overload condition arises.

11. The method of claim 1, further comprising:

automatically marking an interrupt thread initiated by an I/O interrupt as critical;

specifying an operating system wake-up event as critical, where the wake-up event marks an associated handler thread as critical; and

allowing a selected thread to be marked as critical by an API.

12. The method of claim 2, further comprising applying a critical thread'"'"'s execution time against a critical thread'"'"'s adaptive partition critical time budget if and only if the operating system would not have otherwise run the critical thread.

13. The method of claim 1, further comprising designating a critical thread as non-critical when the critical thread enters a blocking state.

14. The method of claim 12, further comprising responding to a critical thread that has exceeded its adaptive partition critical time budget by forcing the operating system to reboot, notifying an operating system watchdog monitor, terminating a designated process, notifying the designated process, or adding an entry to a system log.

21. The method of claim 2 where the method is adapted to run in a POSIX environment.

22. The method of claim 2, where the method is adapted for use in an automobile control operating system.

23. The method of claim 3, where the sliding time window is derived from a microprocessor clock from a microprocessor running the operating system.

24. The method of claim 1, where creating adaptive partitions comprises:

selecting one or more software components to be executed by the operating system, where an individual software component has a priority level, and where all the selected software components have substantially similar priority levels; and

grouping the software components into the same adaptive partition.

25. The method of claim 1, where the method is adapted to run in a transaction processing system in an event of an overload in processing capacity, and further comprising processing a fraction of an offered load.

26. The method of claim 25, where the method is adapted to run in an Internet router or telephone switch system.

27. The method of claim 1, further comprising spawning a new thread or a new process from a parent process, where the new thread or new process automatically becomes a member of the parent process.

28. The method of claim 27, where the new process spawned by the parent process starts in a new adaptive partition.

29. The method of claim 1, further comprising dividing the adaptive partition to create more than one adaptive partition subdivisions, where the adaptive partition subdivisions comprise one or more of the threads contained in the adaptive partition.

15. A method for scheduling an adaptive partition comprising:

determining if one or more threads in one or more adaptive partitions comprising one or more threads in an operating system is critical;

evaluating an ordering function for the one or more adaptive partitions to determine the thread with the highest value of the ordering function;

executing the thread from the adaptive partition that has the highest value;

applying a time spent executing the thread against a CPU budget of the thread'"'"'s adaptive partition; and

applying the time spent executing the thread against a critical time budget of the adaptive partition if and only if the thread is critical and if the thread would not have been scheduled if it had not been critical.

16. The method of claim 15, where evaluating an ordering function comprises:

determining, for each adaptive partition, if the adaptive partition has a critical CPU budget;

evaluating the CPU budget used by the adaptive partition during a last averaging window;

determining if the adaptive partition has used less CPU budget time than a pre-defined adaptive partition budget;

determining a highest priority of all one or more threads that are ready for execution by the adaptive partition comprising the threads;

calculating, for each adaptive partition, a relative ratio of CPU budget time consumed during the last averaging window divided by the adaptive partition'"'"'s CPU budget time; and

determining which adaptive partition is to be run by evaluating an ordered triplet of an adaptive partition criticality status, an adaptive partition budget status, and the adaptive partition relative ratio of the CPU budget time consumed divided by the adaptive partition CPU budget time, where the adaptive partition with the highest value of the ordered triplet is executed.

17. The method of claim 16, where calculating a relative ratio comprises:

determining a percentage CPU budget for each adaptive partition at start-up of the operating system;

computing for each adaptive partition, at the operating system start-up, a factor f(ap), where f(ap) is the product of the percentage CPU budgets of all the other adaptive partitions;

determining a scaling factor k, where k is calculated as the product of the minimum value of all the adaptive partition f(ap) factors with a maximum averaging error value, where the maximum averaging error value is determined at start-up;

calculating a value c(ap), where c(ap)=f(ap)/k;

scaling the adaptive partition execution time by choosing a number of most significant bits of the CPU budget time used; and

calculating the relative ratio by multiplying the scaled adaptive partition'"'"'s execution time with the value c(ap).

18. A method for transferring status of a critical thread in a message-passing operating system comprising:

sending a message from a sending thread to a server, where the sending thread has a priority level, where the sending thread is part of an adaptive partition in an operating system, and where the adaptive partition has a CPU budget and a critical time budget;

receiving the message by a receiving thread where the receiving thread is configured to act on behalf of the sending thread;

assigning the priority level of the sending thread to the receiving thread; and

joining the receiving thread to the adaptive partition of the sending thread.

19. The method of claim 18, further comprising applying a CPU execution time of the receiving thread against the sending thread'"'"'s adaptive partition CPU budget and critical time budget.

20. The method of claim 18, further comprising:

if all receiving threads at the resource manager are busy, raising the priority level of all receiving threads at the server when the sending thread sends a message to the resource manager; and

applying the CPU execution time of all the receiving threads with raised priorities against the sending thread'"'"'s adaptive partition CPU budget and critical time budget.

33. The method of claim 18, where receiving a message further comprises sending the message to a server thread.

30. A method of prioritizing access to a mutex in a message-passing operating system, comprising:

determining, from one or more waiting threads in one or more adaptive partitions, a waiting thread that is most likely to run next after a current thread in an adaptive partition, where the current thread is holding a mutex, and the waiting threads are waiting for the mutex;

raising a priority level of the current thread in the adaptive partition to a priority level of the waiting thread most likely to run next after the current thread;

determining a CPU waiting time incurred by the current thread while the current thread is holding the mutex;

charging a current thread assigned CPU budget the amount of the CPU waiting time, where the current thread assigned CPU budget is charged until the CPU budget reaches zero; and

charging a waiting thread assigned CPU budget a remaining CPU waiting time if the current thread assigned CPU budget reaches zero, where the remaining CPU waiting time is the difference between the CPU waiting time and the amount of CPU budget charged to the current thread.

31. The method of claim 30, where determining a waiting thread that is most likely to run further comprises determining pairwise, for each of the waiting threads, an ordering function of the adaptive partition containing the waiting thread.

32. The method of claim 31, where the ordering function comprises:

determining, for each adaptive partition, a first value, a second value, and a third value, where the first value indicates whether the thread in the adaptive partition is a critical thread or has a CPU budget amount remaining, where the second value indicates whether the waiting thread has a highest priority level in the adaptive partition, and where the third value indicates an amount of relative budget fraction remaining to the adaptive partition;

ordering the first, second, and third values in an order of significance to create an ordered triplet, where a value is more significant if it has a higher value; and

selecting the adaptive partition that has an ordered triplet with the highest order of significance.

34. A system for scheduling processes comprising:

an operating system configured to control a transaction processing system;

a scheduler for scheduling one or more transactions in the operating system;

one or more adaptive partitions comprising one or more threads or one or more group of threads in the operating system, where the adaptive partitions are allocated a CPU budget; and

at least one thread designated as a critical thread by the operating system, where the adaptive partition associated with the critical thread is assigned a critical CPU budget,

where the scheduler allows the critical thread to execute when the critical thread'"'"'s adaptive partition CPU budget has a zero value and when the critical thread'"'"'s adaptive partition critical CPU budget has a non-zero value.