Federated Scheduling of Mixed-Criticality Sporadic DAG Tasks on Uniform Multiprocessors

Abstract

In designing real-time systems, there is an emerging trend in moving towards the mixed-criticality(MC) system, where functionalities with different degrees of importance (i.e., criticality) are implemented upon a shared platform, and the level of heterogeneity in the modern multiprocessors systems is gradually increasing. This thesis develops algorithms to schedule and allocate implicit-deadline sporadic mixedcriticality DAGs upon the uniform heterogeneous multiprocessors.

A two-level scheduler is designed based on the federated scheduling paradigm. Tasks are categorized into heavy and light tasks according to their utilization. Each heavy task exclusively executes on a number of dedicated processors (cluster). Light tasks are treated as sequential tasks and share the remaining processors. The workconserving scheduler is used at the cluster level, and EDF-VD is used to schedule the light tasks. The upper bound of the response time for a heavy task under the work-conserving scheduler and utilisation bound for light tasks under EDF-VD are proposed to verify offline that the design constraints are met.

Task allocation upon the multiprocessors is known to be NP-Hard. This thesis describes an approach to solving the task allocation problem using bin-packing heuristics and simulated annealing. There are two stages for task allocation. The light tasks are assigned to processors using partitioned scheduling in the first stage. A group of bin-packing heuristics will be considered, and a metric QoP is defined to compare the quality of partitioned scheduling under different heuristics. The allocation partition with the best QoP will be used. In the second stage, simulated annealing is employed and tries to find a feasible solution by gradually minimizing the total task lateness in the system.

There is a service abrupt problem at the traditional mixed criticality system. Elastic mixed criticality task model is introduced to address this problem. This thesis also develop schedulability test and discusses the task allocation for elastic mixed criticality task.

Empirical evaluation is presented to show the effectiveness of our approach.