Research On Fault-tolerant Scheduling Algorithm For Mixed-Criticality Systems

The modern embedded systems which integrate varieties of different functions on the same platform is becoming a trend.The real-time scheduling algorithms of mixed-criticality systems have become a hotspot in academic and industry field,and they already had achieved fruitful results,which focus on real-time.However,the hard real-time systems not only have real-time requirements,but also have stringent reliability requirements.For example,the military and industrial embedded system will lead to disaster when the system fails.Therefore,mixed-criticality systems should have fault-tolerant strategy to ensure that systems provide reliable service in the case of system fault.The classical model of fault-tolerant scheduling algorithm is software fault-tolerant model,and each task in the model includes alternate version and primary version.The system will execute backup tasks when the primary task failed,so it can ensure that each task completes either version before deadline,and the start time of alternate version is called notification time.Therefore,this fault-tolerant strategy has high resource utilization.The existing research on fault-tolerant scheduling algorithm aimed at traditional embedded systems,therefore they can't apply to mixed-criticality systems directly.This thesis proposes a mixed-criticality scheduling algorithm called ENF-VD and EDL-VD based on fault-tolerant strategy in software fault-tolerant model.The ENF-VD algorithm schedules primary version of each task,and the EDL-VD algorithm schedules alternate version of each task.The main idea is that the necessary resource is reserved for the alternative version of each task as late as possible before the system runs,which can make the primary version of the job get more resources before the notification time of the job.The system schedules jobs according to the notification time when the system is running.This thesis proposes a mixed-criticality scheduling algorithm base on last chance strategy.If the primary version of the job completed successfully before its notification time,this algorithm will repeal the resource of alternative version,otherwise the system will execute alternative version.Compared with the similar algorithm,the mixed-criticality scheduling algorithm proposed by this thesis improves the resource utilization of the system observably,at the same time,this algorithm can guarantee a high success rate of the primary version of task.