Partitioned Scheduling Algorithm And Implementation For Multicore Mixed-criticality Systems

Mixed-Criticality(MC)System,where multiple functionalities with diverse certification requirements share a hardware platform,has been extensively studied and widely exploited to address the issues of ever-increasing complexity demands and design costs.The partitioned scheduling for MC systems has attracted much attention due to its practicability(i.e.,low run-time overhead).However,the existing mapping schemes only focus on the dual-criticality systems and more importantly,it is difficult for them to guarantee both high schedulability ratio and practical viability.Therefore,the study on the partitioned algorithm for multicore MC systems has significant importance for both theory and applicability concerning MC systems.With the characteristics of EDF-VD(Earliest-Deadline-First with Virtual Deadline)scheduler being considered,this thesis explores a criticality-aware utilization bound for a set of periodic MC tasks of multiple criticality running on multicore systems.Then,the characteristics of the bound associated with other system parameters are identified.Through the pessimistic analysis of this bound,the utilizations of a MC task at different critical levels can significantly affect the schedulability of tasks scheduled by the EDF-VD scheduler.Based on such observations,this thesis investigates an effective partitioned scheme: Criticality-Aware Task Partitioning Algorithm(CA-TPA)under EDF-VD scheduler,where several heuristics are incorporated to conduct the partitioning of MC tasks with multiple criticality levels.With the objective to improve the schedulability ratio of tasks,CA-TPA first determines the prioritization of tasks based on tasks`s utilization contributions to the system.Next,for each task-to-core mapping,allocate a task to the core that can result in the minimized system utilization increment for better tasks' schedulability.Moreover,for partitions with more balanced workload among cores,CA-TPA defines a workload imbalance factor and a threshold to reduce run-time overhead.The extensive simulation results demonstrate that CA-TPA with partitioned EDF-VDcan achieve higher acceptance ratio(e.g.,30% more)when compared to other mapping schemes and can generate partitions with workload balance comparable to WFD mapping heuristic.To measure the practicability of the partitioned schemes tested,we implemented the EDF-VD scheduler and all mapping schemes in LINUX kernel.The empirical results show that CA-TPA has run-time overhead comparable to WFD and outperforms other schemes(e.g.,20% less)due to its inherent criticality-aware workload balance strategy.