Research On Virtualization-based Scheduling Techniques For Multi-core Mixed-criticality Systems

With the growing demand for computation resources in embedded system applications,multi-core processors have become an important direction for the development of modern realtime embedded systems.Although from the perspective of hardware,system computation resources are simply replaced from single-core processors to multi-core processors,this change poses significant challenges for real-time system analysis.Since the architecture of a singlecore processor is transparent to the software designer,the system performance bottleneck is mainly the responsibility of the hardware designer.But for multi-core processor platforms,software designers redesign software architectures and participate in managing core computation resources based on processor architecture.Therefore,according to the principle of software and hardware collaborative design,software designers are also beginning to take responsibility for solving system performance problems.Furthermore,in order to make full use of computing resources of multi-core processors,system designers often integrate different criticality tasks into the same hardware platform.The so-called criticality refers to the level of correctness of a task in the case of different degrees of abnormal errors.However,this integration also introduces a corresponding safety risk to the system,that is,abnormal behaviors of low-critical tasks may interfere with the execution of high-critical tasks.For example,low-critical tasks preempt the resources of high-critical tasks due to incorrect priority configuration,causing high-critical tasks to miss their deadlines and causing serious disaster consequences.Therefore,for the multi-core mixed-criticality model,how to reduce or even eliminate the interference caused by shared resources between different critical tasks becomes a problem that researchers must solve.In the follow-up study,researchers used isolation strategies based on virtualization technology to isolate resources of different critical tasks.For example,high-critical and low-critical tasks are deployed in different virtual machines to achieve isolation between tasks with different attributes.However,these traditional virtualization technologies may cause serious problems in terms of CPU,memory,and power consumption,especially for embedded systems with limited computing resources and memory resources.Therefore,based on the above problems,this dissertation focuses on the principle of“how to build efficient and lightweight resource isolation technology for multi-core mixed-criticality systems”,according to the principle from simple to complex:the structure of this dissertation is as follows.(1)Aiming at how to design a high-performance multi-core processor real-time scheduling algorithm,this dissertation proposes a Job-level Priority Assignment(JPA)algorithm,and optimizes the algorithm to ensure the quality of service of the multi-core processor system in terms of scalability and runtime performance.The JPA algorithm can be seen as a general extension of both the fixed task priority algorithm and the EDF algorithm,i.e.,when the priority of all jobs of one task is set higher or lower than all jobs of another task,JPA is equivalent the fixed job priority algorithm;When the priority of all jobs in the system is strictly set according to the deadline,JPA is equivalent to the EDF scheduling algorithm.By introducing the effective variable JPA_z,the JPA algorithm not only considers the schedulability performance,but also weighs the runtime performance.The efficient variant JPA_z can achieve almost as good performance as JPA,even with very small constant Z(for example Z=4,with which the size of each task's priority and index list is at most 4).Therefore,we can conclude that in global scheduling the schedulability of a task mainly depends on a very small number of jobs at the beginning of a busy interval,and the remaining jobs can be scheduled using rather naive strategies without causing deadline misses.This dissertation also cleverly coordinates the offline design and runtime management of the algorithm,and solves the incompleteness of the operation information of the algorithm in the design stage which can bring great difficulty to the task priority order of the infrequent task system.Although the JPA algorithm does not solve the problem of isolation between tasks with different attributes,it still lays a foundation for the future multi-core processor real-time system scheduling analysis work;(2)For the real-time scheduling problem of multi-core processor DAG model,this dissertation proposes a hierarchical resource isolation technology based on lightweight virtualization strategy,in order to achieve the purpose of isolation between different DAG tasks while maintaining high resource utilization.For the real-time DAG task model,the usually optimal scheduling algorithm is the federated scheduling algorithm.Although it has better schedulability performance,it may cause resources waste due to the inaccuracy of the allocation of core computation resources.In the worst case,half of the core computation resources may be wasted,which is unacceptable in computing resource-sensitive systems.Therefore,this dissertation proposes a hierarchical scheduling strategy with more refined allocation of resources:(1)Dispatching DAG tasks to execute on the virtual cores;(2)Scheduling virtual cores to execute on the physical cores.This layering strategy allocates some virtual core resources that can be occupied by each DAG task(and the task can only be executed on these virtual cores).According to the appropriate description of the characteristics of the virtual core providing resources,this dissertation uses the extended federated scheduling algorithm to analyze each DAG task independently.In addition,the virtual core is scheduled to the physical core in the running state,which effectively enables different DAG tasks to share physical core resources.Therefore,the hierarchical scheduling method proposed in this dissertation inherits the advantages of federated scheduling and global scheduling,thus achieving better schedulability.We evaluate its runtime performance.Although the in-troduction of hierarchical scheduling will will reduce perfor-mance,it can be tolerated.We conduct comprehensive experi-ments to evaluate the schedulability of our hierarchical schedul-ing against the state-of-the-art.The results show that our pro-posed method has more better performance than other state-of-the-art analysis technicals for scheduling DAG tasks with con-strained deadlines which are G-MEL and SF-XU;(3)For the real-time scheduling problem of more complex mixed-criticality DAG task model,this dissertation extends the above lightweight virtualization technology to the mixedcriticality system to solve the resource isolation requirements of complex task models with different attributes.For the mixed-criticality real-time DAG task model,the researchers proposed different federated scheduling algorithms.The similarity of these algorithms is that they assigned tasks to their own core computing resources according to different critical states.Different algorithms use different resource allocation strategy.However,these algorithms face the same resource waste problem as the federated scheduling algorithm of the non-mixed-criticality DAG task model.Therefore,the resource isolation technology based on virtualization strategy is introduced into the mixed-criticality system model for the first time.From the experimental results,SFMC has much better schedulability performance than FMC-Li.When m=8 and normalized utilization exceeds 0.7,DAG task sets can hardly be schedulable by FMC-Li.But the acceptance of our algorithm is still over 90 percent when normalized utilization is 0.9.The reason is that the middleware of a lightweight virtualization technology,the core computation resources can be allocated in a more granular manner under different critical states,thereby improving the resource utilization of the system.In summary,this dissertation studies the virtualization-based scheduling techniques for multicore mixed-criticality systems,which contributes to theoretical foundations and technology for the design and analysis of modern multi-core embedded systems.