Research On Real-Time Scheduling Of Mixed-Criticality Systems And DTR Model

An increasingly important trend in the design of real-time and embedded systems is the integration of components with different levels of criticality onto a common hardware platform.At the same time,these platforms are migrating from single cores to multi-cores and,in the future,many-core architectures.Unfortunately,the scheduling problem of mixed-criticality systems appears to be challenging,even on single-processor platforms.Most of the complex embedded systems cannot be exactly described by traditional period based models.Real-time task graphs are used to model complex real-time systems with non-cyclic timing behaviors.However the exactly analysis of such graph-based systems are often intractable.This dissertation studied the design and analysis of real-time sheduling algorithm for mixed-criticality systems and DRT systems.As to the mixed-criticality scheduling,proposed an efficient online scheduling algorithm for single-processor systems,two partioned scheduling algorithms for multi-cores/processors.As to the DRT systems,proposed two efficient approx-imate response time analysis methods with speedup factor evaluation,and an effective graph transformation method to improve system schedulability.The main contribution of this dissertation can be summarized as follows:(1)This dissertation proposed a novel OCBP-based algorithm LPA,to schedule mixed-criticality sporadic tasks on preemptive single processor systems.Comparing with the previous OCBP-based algorithms,it can improve the online time efficiency,online space efficiency,as well as schedulability.The central idea of LPA is to make online priority adjustment as lazy as possible,in order to avoid redundant priority adjustments that are not relevant to the actual scheduling decisions.Experiments with synthetic workloads show the performance improve-ment of our new algorithm in online time efficiency,online space efficiency and schedulability.(2)This dissertation proposed a novel partitioned scheduling algorithm MPVD to extend the state-of-the-art single-processor mixed-criticality scheduling algorithm EY-VD to multipro-cessor platforms.The key idea of MPVD is to evenly allocate tasks with different criticality levels to different processors,in order to better explore the asymmetry between different crit-icality levels and improve the system schedulability.Then we propose two enhancements to further improve the schedulability of MPVD.Experiments with randomly generated task sets show significant performance improvement of our proposed approach over existing algorithms.(3)This dissertation proposed a novel partitioning policy for mixed-criticality scheduling on multiprocessor platforms.First,we integrate EY-VD into traditional workload partitioning schemes to get a multiprocessor mixed-criticality scheduling algorithm MC-PEDF.Although MC-PEDF performs better than previous solutions,we find that the traditional workload parti-tioning schemes are not suitable for mixed-criticality systems as it does not explore the asym-metricity of workload on different criticality levels.To overcome this problem,we propose a novel workload partitioning policy OCOP(one criticality one partition).OCOP allows tasks to be reassigned to a different processor when criticality mode switch occurs,thus can bet-ter balance the resource utilization among processors on different criticality levels.Based on OCOP,we propose our second partitioned scheduling algorithm MC-MP-EDF.Experiments with randomly generated workload show that MC-MP-EDF can drastically improve the system schedulability comparing with MC-PEDF and other previous algorithms,especially for systems with more processors.(4)This dissertation proposed two approximate response time analysis methods RBF and IBF to evaluate the DRT models,both of which have pseudo-polynomial complexity.We quan-titatively evaluate their analysis precision using the metric speedup factor.We prove that RBF has a speedup factor of 2,and this is tight even for dual-task systems.The speedup factor of IBF is an increasing function with respect to k,the number of interfering tasks.This function converges to 2 as k approaches infinity and equals 1 when k = 1,implying that the IBF analysis is exact for dual-task systems.We also conduct experiments to empirically evaluate the preci-sion and efficiency of RBF and IBF with randomly generated task sets.Results show that theproposed approximate analysis methods have very high efficiency with low precision loss.(5)This dissertation proposed a novel DRT task graph transformation method to improvesystem schedulability.The idea is to insert artificial delays to the release times of certain ver-tices of a task graph to get a new graph with a smoother workload,while still meeting the timing constraints of the original task graph.Delaying the release time of a vertex may smoothen the workload of some paths of the task graph,but at the same time make the workload of other paths even more bursty.We developed efficient techniques to search for an appropriate release time delay for each vertex.Experiments with randomly generated task systems show that the proposed transformation method can make a significant number of task systems that was origi-nally unschedulable to become schedulable,and the transformation procedure is very efficient and can easily handle large-scale task graph systems in very short time.In summary,this dissertation studied various real-time scheduling algorithms for mixed-criticality systems and DRT model.The results of this dissertation contribute to theoretical foundations,also provide practical insights for the design and analysis of modern real-time and embedded systems.