Precise Scheduling of Mixed-Criticality Tasks on Varying-Speed Multiprocessors

In conventional real-time systems analysis, each system parameter is specified by a single estimate, which must pessimistically cover the worst case. Mixed-criticality (MC) design has been proposed to mitigate such pessimism by providing a single system parameter with multiple estimates, which often lead to low-critical and high-critical modes. The majority of the works on MC scheduling is based on the approach that low-critical workloads are (fully or partially) sacrificed at the transition instant from low- to high-critical mode. Recently, another approach called precise MC scheduling has been investigated, where no low-critical workload is sacrificed at the mode switch, but instead a processor speed boosting is committed. In this paper, we extend the work on uniprocessor precise MC scheduling to multiprocessor platforms. To tackle this new scheduling problem, we propose two novel algorithms based on the virtual-deadline and fluid-scheduling approaches. For each approach, we present a sufficient schedulability test and prove its correctness. We also evaluate their effectiveness theoretically with speedup bounds and approximation factors as well as experimentally via randomly generated task sets