Process scheduler employing adaptive partitioning of critical process threads
View Patent ↗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 time budget. One or more of the process threads are designated as critical threads. Each adaptive partition associated with a critical thread is assigned a corresponding critical time budget. The software code also includes a scheduling system that is executable by the processor for selectively allocating the processor to run the process threads based, at least in part, on the processor time budgets of the respective adaptive partitions. The scheduling system may allocate the processor to run a critical thread based on the available critical time budget of the associated adaptive partition even when the processor time budget of the associated adaptive partition has been exhausted. In one example, the scheduling system functions so that it only bills the critical time budget of an adaptive partition for time used to run an associated critical thread when the processor is overloaded and the critical time budget for the adaptive partition is concurrently exhausted. Methods of implementing such a system are also set forth.
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 and to associate one or more process threads with each of the plurality of adaptive partitions, where each of the one or more process threads has a corresponding priority in the associated adaptive partition, where each of the plurality of adaptive partitions is assigned a corresponding standard processor time budget, and where the plurality of adaptive partitions comprise at least one critical adaptive partition to which at least one critical thread is assigned, and where the at least one critical adaptive partition is assigned a critical time budget as well as a standard processor time budget;
where the software code further comprises a scheduling system executable by the processor for allocating the processor to the process threads using the standard processor time budgets of the respective associated adaptive partitions, where execution of each thread of the one or more process threads of the plurality of adaptive partitions are individually attributed and accounted against the standard processor time budget of the adaptive partition associated with the executed thread;
where the scheduling system allocates the processor to the at least one critical thread based on an available amount of the critical time budget of the at least one critical adaptive partition when the standard processor time budget of the at least one critical adaptive partition has been exhausted, where execution of the at least one critical thread assigned to the at least one critical adaptive partition is individually attributed and counted against the critical time budget of the at least one critical adaptive partition when the standard processor time budget of the at least one critical adaptive partition is exhausted and the processor is overloaded;
where the scheduling system microbills the standard processor time budget of an adaptive partition of the plurality of adaptive partitions associated with a given thread for a processor allocation used by the given thread, where the microbillinq takes place using a time interval less than a duration of a system tick.
2. The system of claim 1 , where the at least one critical thread is initiated by a processor interrupt.
3. The system of claim 1 , where the at least one critical thread is a child thread of a critical parent thread.
4. The system of claim 1 , where the at least one critical thread is designated as non-critical when it enters a blocking state.
5. The system of claim 1 , where the at least one critical thread is designated as critical by an API.
6. The system of claim 1 , where the scheduling system is a part of an operating system.
7. The system of claim 1 , where the processor is a symmetric multiprocessor.
8. The system of claim 1 , where the scheduling system microbills the critical time budget of the at least one critical adaptive partition for a processor allocation used by the critical thread, where the microbilling takes place using a time interval less than a duration of a system tick.
9. The system of claim 1 , where the standard processor time budget of one or more of the plurality of adaptive partitions comprises a guaranteed portion of an entire time budget available for running the process threads on the processor.
10. A method of operating a process scheduler in a processing system having a processor and a plurality of software threads executable by the processor, the method comprising:
associating a first set of software threads with a first adaptive partition, where the first set of software threads have respective priority levels;
assigning a first standard processor time budget to the first adaptive partition;
associating a second set of software threads with a second adaptive partition, where the second set of software threads have respective priority levels;
assigning a second standard processor time budget to the second adaptive partition;
assigning a critical state to one or more software threads of the first and/or second set of software threads;
assigning a critical time budget to each of the first and/or second adaptive partitions having the one or more software threads assigned the critical state;
allocating the processor to run the software threads of the first and second set of software threads using the standard processor time budgets of the first and second adaptive partitions, respectively;
individually attributing and accounting execution of each software thread of the first and second set of software threads of the first and second adaptive partitions against the standard processor time budget of the first or second adaptive partition associated with each software thread;
allocating the processor to run the one or more software threads assigned the critical state using an available amount of the critical time budget of the first or second adaptive partition associated with the one or more software threads assigned the critical state when the standard processor time budget of the first or second adaptive partition associated with the one or more software threads assigned the critical state is exhausted; and
microbilling the critical time budget of the first or second adaptive partition for a processor allocation used by the one or more software threads assigned the critical state when the standard processor time budget of the first or second adaptive partition associated with the one or more software threads assigned the critical state is exhausted and the processor is concurrently overloaded, where the microbilling takes place using a time interval less than a duration of a system tick.
11. The method of claim 10 , and further comprising:
billing the critical time budget of the first or second adaptive partition associated with the one or more software threads assigned the critical state for a processor allocation used by the one or more software threads assigned the critical state of the first or second adaptive partition when the standard processor time budget of the first or second adaptive partition associated with the one or more software threads assigned the critical state is exhausted and the processor is concurrently overloaded.
12. The method of claim 10 , and further comprising:
generating an interrupt thread in response to a processor interrupt; and
assigning a critical state to the interrupt thread.
13. The method of claim 10 , and further comprising:
generating a child thread from a critical parent thread; and
assigning a critical state to the child thread.
14. The method of claim 10 , and further comprising:
designating a critical thread as non-critical when the critical thread enters a blocking state.
15. The method of claim 10 , and further comprising:
using an API to assign a critical state to one or more of the software threads of the first and/or second set of software threads.
16. The method of claim 10 , and further comprising:
microbilling the standard processor time budget of the first or second adaptive partition associated with a given software thread for a processor allocation used by the given software thread, where the microbilling takes place using a time interval less than a duration of a system tick.
17. 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 and to associate one or more process threads with each of the plurality of adaptive partitions, where each of the one or more process threads has a corresponding priority in the associated adaptive partition, where each of the plurality of adaptive partitions is assigned a corresponding standard processor time budget comprising a guaranteed portion of an entire time budget available for the processor, and where the plurality of adaptive partitions comprise at least one critical adaptive partition to which at least one critical thread is assigned, and where the at least one critical adaptive partition is assigned a critical time budget as well as a standard processor time budget;
where the software code further comprises a scheduling system executable by the processor for allocating the processor to the process threads using the standard processor time budgets of the respective associated adaptive partitions, where execution of each thread of the one or more process threads of the plurality of adaptive partitions are individually attributed and accounted against the standard processor time budget of the adaptive partition associated with the executed thread;
where the scheduling system designates a critical thread as non-critical when the critical thread enters a blocking state; and
where the scheduling system allocates the processor to the at least one critical thread based on an available amount of the critical time budget of the at least one critical adaptive partition when the standard processor time budget of the at least one critical adaptive partition has been exhausted, where execution of the at least one critical thread assigned to the at least one critical adaptive partition is individually attributed and microbilled against the critical time budget of the at least one critical adaptive partition when the standard processor time budget of the at least one critical adaptive partition is exhausted and the processor is overloaded.
18. The system of claim 17 , where the at least one critical thread is initiated by a processor interrupt.
19. The system of claim 17 , where the at least one critical thread is a child thread of a critical parent thread.
20. The system of claim 17 , where the at least one critical thread is designated as non-critical when it enters a blocking state.
21. The system of claim 17 , where the at least one critical thread is designated as critical by an API.
22. The system of claim 17 , where the scheduling system is a part of an operating system.
23. 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 and to associate one or more process threads with each of the plurality of adaptive partitions, where each of the one or more process threads has a corresponding priority in the associated adaptive partition, where each of the plurality of adaptive partitions is assigned a corresponding standard processor time budget, and where the plurality of adaptive partitions comprise at least one critical adaptive partition to which at least one critical thread is assigned, and where the at least one critical adaptive partition is assigned a critical time budget as well as a standard processor time budget;
where the software code further comprises a scheduling system executable by the processor for allocating the processor to the process threads using the standard processor time budgets of the respective associated adaptive partitions, where execution of each thread of the one or more process threads of the plurality of adaptive partitions are individually attributed and accounted against the standard processor time budget of the adaptive partition associated with the executed thread; and
where the scheduling system allocates the processor to the at least one critical thread based on an available amount of the critical time budget of the at least one critical adaptive partition when the standard processor time budget of the at least one critical adaptive partition has been exhausted, where execution of the at least one critical thread assigned to the at least one critical adaptive partition is individually attributed and microbilled against the critical time budget of the at least one critical adaptive partition when the standard processor time budget of the at least one critical adaptive partition is exhausted and the processor is overloaded, where the microbilling takes places using a time interval less than a duration of a system tick.
24. 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 and to associate one or more process threads with each of the plurality of adaptive partitions, where each of the one or more process threads has a corresponding priority in the associated adaptive partition, where each of the plurality of adaptive partitions is assigned a corresponding standard processor time budget, and where the plurality of adaptive partitions comprise at least one critical adaptive partition to which at least one critical thread is assigned, and where the at least one critical adaptive partition is assigned a critical time budget as well as a standard processor time budget;
where the software code further comprises a scheduling system executable by the processor for allocating the processor to the process threads using the standard processor time budgets of the respective associated adaptive partitions, where execution of each thread of the one or more process threads of the plurality of adaptive partitions are individually attributed and accounted against the standard processor time budget of the adaptive partition associated with the executed thread;
where the scheduling system allocates the processor to the at least one critical thread based on an available amount of the critical time budget of the at least one critical adaptive partition when the standard processor time budget of the at least one critical adaptive partition has been exhausted, where execution of the at least one critical thread assigned to the at least one critical adaptive partition is individually attributed and counted against the critical time budget of the at least one critical adaptive partition when the standard processor time budget of the at least one critical adaptive partition is exhausted and the processor is overloaded; and
where the scheduling system microbills the critical time budget of the at least one critical adaptive partition for a processor allocation used by the critical thread, where the microbilling takes place using a time interval less than a duration of a system tick.
25. The system of claim 24 , where the at least one critical thread is initiated by a processor interrupt.
26. The system of claim 24 , where the at least one critical thread is a child thread of a critical parent thread.
27. The system of claim 24 , where the at least one critical thread is designated as non-critical when it enters a blocking state.
28. The system of claim 24 , where the at least one critical thread is designated as critical by an API.
29. The system of claim 24 , where the scheduling system is a part of an operating system.
30. The system of claim 24 , where the processor is a symmetric multiprocessor.
31. The system of claim 24 , where the scheduling system microbills the standard processor time budget of an adaptive partition of the plurality of adaptive partitions associated with a given thread for a processor allocation used by the given thread, where the microbilling takes place using a time interval less than a duration of a system tick.
32. The system of claim 24 , where the standard processor time budget of one or more of the plurality of adaptive partitions comprises a guaranteed portion of an entire time budget available for running the process threads on the processor.