Hybrid-sched: a QoS adaptive offline–online scheduler for real-time tasks on multi-cores

The performance of safety-critical systems implemented on multi-core platforms depends heavily on the scheduling mechanism used. This paper addresses the problem of multi-core scheduling of a real-time application modelled as a Directed Acyclic Graph (DAG) with multiple service levels (where, a higher service level implies higher Quality-of-Service (QoS)), by proposing a novel two-phase offline–online scheduling mechanism called HYBRID-SCHED. The offline phase constructs a static schedule assuming worst-case execution behaviour, in order to ensure desired predictability with a minimum guaranteed QoS under all possible execution scenarios. Two alternative offline solution strategies have been designed. While the first strategy is a fast but reasonably good heuristic solution called Service-level Aware Scheduler (SAS), the second is a branch-and-bound based optimal solution-space search technique. However, online execution based on strict adherence to the static schedule may result in poor resource utilization as actual execution time of tasks at run time may be significantly less than worst-case estimates. In order to improve the situation, an online scheduler called Actual Execution-time Aware Scheduler (AEAS) has been developed. The basic goal of AEAS is to strategically reclaim resources that were provided for tasks at design time but are in fact being used inactively at run time. By gradually raising the service levels of the remaining (yet-to-be-completed) jobs, AEAS can then use the recovered resources to improve system-level QoS. Using real-world benchmark applications, we assessed the performance of the suggested framework. Results obtained demonstrate the usefulness of our plan.