Scheduling Optimization Of Heterogeneous Distributed Mixed-criticality Systems

Modern automobile electronic systems are mixed-criticality systems based on heterogeneous distributed integrated architectures.These systems have the joint characteristics of real-time systems,mixed-criticality systems,and heterogeneous distributed systems,but still have some specific requirements on architectures,software systems,and functional safety,especially on the conflicts of performance and time-constraints.Overall scheduling length is the main concern of systems,while deadlines are the major time constraints of functionalities.Furthermore,the deadlines of all functionalities cannot be met,especially on large-scale resource constrained distributed embedded environments.How to improve the overall performance of systems while still meeting the real-time of higher-criticality functionalities is the major scheduling optimization object of heterogeneous distributed mixed-criticality systems.For the above problem,we first construct exact mixed-criticality model of distributed automotive electronic systems,and then propose several scheduling optimization algorithms from the viewpoint of “functionality-level” and “parallel and distributed computing” to minimize the conflicts between performance of systems and deadline miss ratio of functionalities,such that reasonable tradeoffs among the performance,real-time,resource efficiency and cost are made.The main work of this paper is given as follows:(1)Scheduling optimization of static multi-criticality systems.Different distributed functionalities with different criticality levels are integrated into the same heterogeneous distributed mixed-criticality systems.Scheduling optimization of static multi-criticality systems can effectively guide the design on distributed processing of automotive electronic systems.To meet the above requirements,we propose some static scheduling algorithms for different objectives based on the architecture of buses interconnected by a gateway and the severity level of functionality safety in automotive safety integration level.The F_MHEFT(Fairness on Mixed-criticality Heterogeneous Earliest Finish Time)algorithm is to obtain the minimum overall make span of systems by scheduling all different criticality functionalities with the round-robin fairness policy.The WP_MHEFT(Whole Priority on Mixed-criticality Heterogeneous Earliest Finish Time)algorithm is to meet the deadlines of a few higher-criticality functions by preferentially scheduling whole tasks of high-criticality functionalities.The PP_MHEFT(Partial Priority on Mixed-criticality Heterogeneous Earliest Finish Time)algorithm is to meet the deadlines of more higher-criticality functions by only preferentially scheduling minimum partial tasks of them.PP_MHEFT can obtain a shorter overall make span than WP_MHEFT by making the remaining tasks to be fairly scheduled with other functionalities.PP_MHEFT makes an improved optimization between performance and time-constraints to make more functionalities meet their deadlines while reducing the overall makespan of systems as much as possible.Extensive experimental evaluations are made and the significant improvement of the PP_MHEFT algorithm is demonstrated.(2)Scheduling optimization of dynamic dual-criticality systems.Mixed-critical automobile electronic systems are typical cyber-physical systems,where many higher-criticality functionalities are dynamically interacted with external physical world.Some types of functionalities,such as break-by-wire,are not only dynamically triggered,but also have higher certificated levels on timing.Dynamics and concurrency are the inherent property of automotive cyber-physical systems.To meet the above requirements,we propose some dynamic scheduling algorithms for different objectives based on the dynamic dual-criticality model.The F_DDHEFT(Fairness of Dynamic Dual-criticality Heterogeneous Earliest Finish Time)algorithm is to improve system's performance.The C_DDHEFT(Criticality of Dynamic Dual-criticality Heterogeneous Earliest Finish Time)algorithm is to meet the deadlines of higher-criticality functionalities.The D_DDHEFT(Deadline-span of Dynamic Dual-criticality Heterogeneous Earliest Finish Time)algorithm is to allow the lower-criticality functionalities to be processed positively for better overall performance while still meeting the deadlines of higher-criticality functionalities,such that a reasonable tradeoff between performance and timing is made.Extensive experimental evaluations demonstrate that significant optimization is made by using D_DDHEFT.(3)Scheduling optimization of dynamic dual-criticality systems with communication contention.High-end mixed-critical automobile electronic systems are on the basis of the heterogeneous distributed intergerated architectures.They are heterogeneous distributed embedded systems where the computing and networking are both heterogeneous and deeply integrated.For such systems,computing and networking have the same importance,and the calculation should be more precise,and the synchronized scheduling of tasks and messages should be implemented.To meet the above requirements,we focus on the research on scheduling optimization of dynamic dual-criticality systems with communication contention.First,heterogeneous computing and networking models are constructed to implement more precise calculation of upward rank value and earliest finish time(EFT)for reflecting the characteristics of heterogeneity and the synchronization between tasks and messages.Three algorithms named F_CC_DDHEFT(Fairness of Communication Contention Dynamic Dual-criticality Heterogeneous Earliest Finish Time),C_CC_DDHEFT(Criticality of Communication Contention Dynamic Dual-criticality Heterogeneous Earliest Finish Time)and D_CC_DDHEFT(Deadline-span of Communication Contention Dynamic Dual-criticality Heterogeneous Earliest Finish Time)are proposed to implement the final optimization.Extensive experimental evaluations demonstrate the significant improvement of D_CC_DDHEFT.(4)Criticality-aware scheduling optimization of multi-core mixed-criticality systems.The integration of multiple functionalities with different criticalities into the same hardware platform prompts the application of multi-core into the mixedcriticality systems like automotive electronic systems.However,one of the key problems needing to be solved for its application is the task assignment among the multiple cores.For those functionalities with higher-criticalities,their development and citification cost can be reduced by criticality decomposition.However,it also brings the overhead in both the CPU and bandwidth utilization.Therefore,there is a tradeoff between cost and resource efficiency for the task assignment of the multicore mixed-criticality systems.We propose a simulated annealing based heuristic algorithm to solve this problem,which can realize the joint optimization of cost and resource efficiency by conforming the constraint in schedulability.Finally,we conduct several comparison experiments based on real functions of automobiles and simulated dataset,and the effectiveness of CTM is verified.