Research On Optimized Algorithm Of Mixed-Criticality Scheduling In Embedded System

In the embedded system nowadays,an important trend is integrating different functions with different important levels to a shared computing platform to balance the contradiction between the complexity of system and the constrained resources of computing,hardware size,energy consumption and cost.This kind of system is defined as Mixed-Criticality System(MCS),when the important level of functions is defined as criticality.In the scheduling area of MCS,on one hand,the system has to guarantee the completion of functions with high criticality to fix the demand of safety and reliability.And on the other hand,to improve the total performance,the system needs to configure the system resource to optimize the execution of functions with low criticality.As the traditional real-time scheduling theory can not solve the problems above,it is a hot topic to research the optimized scheduling mechanism of MCS.This dissertation takes the MCS as the research object,and researches the optimized scheduling mechanism of MCS to pursue the improvement of total system performance while guaranteeing the reliability of system.To get better optimized scheduling mechanisms and algorithms,the dissertation researches the Mixed-Criticality(MC)models,MC job scheduling,MC task scheduling,task partition and task migration by the method of demand bound function,utilization analysis,probability and expectation calculation,schedulability analysis and the key factor analysis.The main works and contributions are given as follows.(1)Optimizing the scheduling of mixed-criticality jobs by dynamic demand bound functionFor the problem that the existing MC job scheduling strategy can not lower the criticality level flexible,which leads to the problems that the low criticality(LO)jobs are discarded unnecessarily and the computing resource can not be utilized efficiently,the dissertation proposes the concept of Dynamic Demand Bound Function(DDBF),which considers the real-time property,the criticality and the run-time factor of MC jobs.The DDBF can describe the demand of jobs in multiple dimensions.Based on the DDBF,the dissertation then defines the concept of slack time,and proposes an algorithm of Criticality Switch based on Dynamic Demand Boundary(CSDDB).CSDDB chooses the criticality with the minimum slack time as the execution criticality to take full advantage of system resources and to guarantee the execution of jobs with lower criticality without affecting the schedulability of high criticality jobs.Experiments with randomly generated workload show that CSDDB has better performance in guaranteeing the system criticality and the completion of jobs set compared with the existing researches.(2)Optimizing the scheduling of mixed-criticality tasks by utilizationFor the problem that the classical MC scheduling algorithm EDF-VD(Earliest Deadline First-Virtual Deadline)has strict schedulability constrain,which leads to the waste of computing resource,the dissertation modifies the correctness condition of scheduling which allows the delayed completion of LO tasks.Then the dissertation proposes the algorithms of Earliest Deadline First-Worst Case Reservation(EDF-WCR)and Earliest Deadline First-Best Effort(EDF-BE)for different situations by the analysis of utilization.And an algorithm of MSBU(Mixed Scheduling Based on Utilization)is proposed which combines the algorithms of EDFWCR,EDF-VD and EDF-BE,takes different strategies in different situations to optimize the scheduling of LO tasks.The simulation experiment showed that MSBU can make better use of the utilization of computing resource and optimize the completion of LO tasks.(3)Optimizing the mixed-criticality scheduling by semi-partition algorithmConsidering the separate disadvantages of partition scheduling and global scheduling,the dissertation proposes a semi-partition algorithm of SPBU(Semi Partition Based on Utilization),which partitions the HI tasks and LO tasks separately off-line when admitting the migration of LO tasks in run-time.SPBU can take advantage use of system resource when controlling the frequency of migration in run-time.The experiment shows that SPBU can improve the completion of LO tasks in multi-processor platform.(4)Optimizing the scheduling of mixed-criticality tasks by switching the criticality seriatimFor the disadvantage of EDF-VD in the strategy of criticality switch,the dissertation proposes an optimizing algorithm of O-EDF-VD(Optimized-Earliest Deadline First-Virtual Deadline).The algorithm switches the criticality of high criticality(HI)tasks seriatim to reduce the length of HI stage and obtains more execution time for LO tasks.The simulation experiment shows that it can optimize the proportion of HI stage in the whole period and optimize the scheduling of LO tasks.(5)Optimizing the model and the partition of mixed-criticality tasks in multi-processor by probabilityFor the problem that the existing MC scheduling strategies are based on the analysis of worst case without considering the actual situation in run-time,the dissertation proposes a Probability MC model(PMC),which adds a parameter of overload probability for HI task to classic MC model and described the actual overload in run-time.Then the dissertation analyzes the situations in run-time,computed the expectations of the length of LO stage,HI stage and the total period.Then a key factor for the execution of LO tasks is discovered.In homogeneous multi-processor platform,the dissertation proposes a Partition algorithm based on Probability for Dual-Criticality(PPDC).The algorithm consideres the expectations in every stage,and allocated the tasks to the processor with the best key factor of LO task by greedy mechanism.The simulation experiments showed that PPDC can optimize the execution of LO tasks apparently.