Reducing pessimism in mixed-criticality system designs
Miss Fei Guan - ETRO, Vrije Universiteit Brussel [Email] [URL]
Embedded systems are more and more taking part in everyones daily live. In some industry standards, functions hosted by these embedded systems are classified into multiple criticality or safety levels. These are used to identify the hazard caused by their failure. The concept of Mixed Criticality Systems (MCS) is defined aiming at software where functions with different criticality levels coexist on a shared hardware platform. MCS design, especially considering the task scheduling issue, has been recently an important topic. However, most of the work in this area tends to pessimistically allocate processor resource to the tasks with higher criticality levels sacrificing the lower criticality ones. These approaches can cause under-utilization of the processor and make less critical tasks stop running unnecessarily.
In this thesis we analyse the pessimism in the existing designs and reduce it in two phases. In the first phase, we extend the well-known Earliest Deadline First with Virtual Deadlines scheduling mechanism or EDF-VD, to have an increased processor utilization for low-criticality tasks. In a second phase, we propose a new MCS model that uses an adaptive reservation mechanism. It allocates to a task a variable processor bandwidth in function of its changing requirements deducted from run time measurements. The new approach reduces the pessimism of the classical models who rely on the correctness of offline Worst Case Execution Time (WCET) estimations. In a more elaborated approach, a concept of degraded service is introduced. In this way, each task requires less bandwidth to execute accepting some reduction in output quality. Taking this concept into account, scheduling algorithms are proposed based on genetic algorithms. With proper mathematical modelling, the algorithms are able to allow an increased processor utilization during resource insufficiency conditions while limiting the computation complexity.
Theoretical considerations are complemented with simulation and experiments to demonstrate that the proposed models and algorithms are valid and efficient in an embedded system environment.
Master in Engineering, Harbin Institute of Technology