Processor scheduling using a contention model
A computer-implemented method schedules a plurality of tasks for execution by a multi-processor system. A first schedule is generated that assigns each task of the plurality of tasks a time window and a processor of the multi-processor system. A contention model for the multi-processor system is queried to determine a contention delay for the assignment of tasks to processors according to the first schedule. The contention delay determined from the contention model is used to generate, from the first schedule, a revised schedule that assigns each task a time window and a processor of the multi-processor system, wherein the revised schedule is determined in dependence on the determined contention delay.
1 . A computer-implemented method of scheduling a plurality of tasks for execution by a multi-processor system, the method comprising:
generating a first schedule that assigns each task of the plurality of tasks a time window and a processor of the multi-processor system;
querying a contention model for the multi-processor system to determine a contention delay for the assignment of tasks to processors according to the first schedule; and
using the contention delay determined from the contention model to generate, from the first schedule, a revised schedule that assigns each task a time window and a processor of the multi-processor system, wherein the revised schedule is determined in dependence on the determined contention delay.
2 . The computer-implemented method of claim 1 , wherein the first schedule is a schedule that does not account for contention delays in the multi-processor system.
3 . The computer-implemented method of claim 1 , wherein the revised schedule is a final schedule, and the method comprises storing or outputting the final schedule for use in executing the plurality of tasks on the multi-processor system.
4 . The computer-implemented method of claim 1 , comprising iteratively generating a succession of revised schedules that assign each task a time window and a processor of the multi-processor system, wherein each schedule is generated from a respective preceding schedule in the succession by:
querying the contention model to determine a respective contention delay for the assignment of tasks to processors according to the preceding schedule; and
using the determined contention delay to generate the schedule in dependence on the determined contention delay.
5 . The computer-implemented method of claim 4 , comprising determining whether each generated schedule accounts for all contention delays that arise from the schedule, and iteratively generating revised schedules until a schedule is generated that accounts for all contention delays.
6 . The computer-implemented method of claim 5 , comprising storing or outputting a revised schedule that accounts for all contention delays as a final schedule for use in executing the plurality of tasks on the multi-processor system.
7 . The computer-implemented method of claim 1 , wherein the contention model models any one or more of cache contention, volatile-memory contention, non-volatile memory contention, bus contention, and peripheral contention, in the multi-processor system.
8 . The computer-implemented method of claim 1 , wherein the contention delay determined by the contention model represent a worst-case execution time.
9 . The computer-implemented method of claim 1 , wherein querying the contention model comprises querying a contention model system that comprise the contention model and a cache for caching queries made to the contention model and responses from the contention model.
10 . The computer-implemented method of claim 9 , wherein the contention model system is configured to determine whether a received query has been cached and to respond with a contention delay retrieved from the cache when the query is determined to be cached.
11 . The computer-implemented method of claim 1 , wherein plurality of tasks are tasks of a real-time software application.
12 . The computer-implemented method of claim 1 , wherein the multi- processor system is a multi-core processor of an avionics system.
13 . A computer system for scheduling a plurality of tasks for execution by a multi-processor system, wherein the computer system is configured to perform the method of claim 1 .
14 . Computer software comprising instructions which, when executed on a computer system, cause the computer system to schedule a plurality of tasks for execution by a processor system, by performing the method of claim 12 .
15 . Computer software comprising instructions for executing a plurality of tasks on a multi-processor system according to a schedule determined using the method of claim 1 .