Research On Global Real-Time Scheduling For Embedded Multi-core Systems

Recently,with the increasing requirement for high computational capacity and low power consumption in embedded real-time systems,there is a trend to deploy multi-core platforms.The analysis of multi-core scheduling is more difficult than its uni-core counterpart.Due to the unknown worst case execution scenario,existing techniques use over approximations of task interference for efficient yet pessimistic analysis.Global multi-core scheduling analysis is a hot topic in real-time scheduling area.The global scheduling strategy is based on the similar calculation framework,as following.First,compute the workload upper bound of tasks with higher priority that can interfere with the execution of the analyzed task.Then sum them up to upper bound the total interference and response time analysis test can be carried out as in uniprocessor form.An important concept in these techniques is called carry-in,which describes the workload or interference of an interfering task whose release time is before the beginning of a problem window while the absolute deadline is inside.The already known methods are not yet mature and still need further research and new technologies.This dissertation studied the global multi-core scheduling problems for sequential tasks and studied the pessimistic of global scheduling.Based on the scheduling theory of sequential tasks,this dissertation studied the global multi-core scheduling problems for parallel tasks.Finally,based on the above studies this dissertation studied the schedulability problems of parallel tasks on heterogeneous multi-core platform.(1)For precisely bounding the carry-in interference problem of sequential task model,this dissertation presents a new estimation technology for each interfering task's carry-in workload.The key is to identify and resolve contradicting assumptions made in the analysis procedure.The resulting new analysis method improves the analysis precision at the price of a higher complexity.Then we introduce techniques to optimize the new method for better efficiency.(2)For solving the pessimistic caused by execution sequence of tasks based on G-FP(Global Fixed-Priority),this dissertation studied the execution properties and proposed the execution constraints between higher priority tasks.This dissertation presented a method to construct the execution dependency between two tasks,which improves the precise of G-FP response time analysis.(3)For the limited preemption based on G-EDF(Global Earliest Deadline First)problem,this dissertation studied the advantages and disadvantages of preemptive scheduling and non-preemptive scheduling of G-EDF,and proposed hybrid scheduling of limited preemption for G-EDF scheduling to reduce the overheads caused by preemption and migration.(4)For reducing the pessimistic of parallel tasks based on G-FP,this dissertation studied the difficulties in the schedulability analysis of parallel tasks.Based on the window sliding technique,this dissertation proposed a new workload estimation techniques by extending the busy period.The improved analyzing techniques for each interfering task result in improved the precise of parallel tasks analysis.(5)For bounding the carry-in interference of parallel tasks based on G-EDF,this dissertation proposed a schedulability analysis for parallel tasks based on the workload estimation of each carry-in job.To improve the schedulability of parallel tasks,the stateof-the-art carry-in workload estimation technique for sequential tasks are adjusting to parallel tasks,based on the conclusion of the already existing techniques to parallel tasks schedulability on G-EDF.(6)For analysing the response time of typed parallel tasks,this dissertation studies the schedulability analysis of heterogeneous multi-core typed parallel task model.Firstly,this dissertation proposes a highly efficient schedulability analysis method that solves the pessimistic and security problems of the currently known method.However,this method still suffers great pessimism.Secondly,this dissertation proposes a more accurate schedulability analysis method based on the internal structural characteristics of the typed parallel task model.In summary,this dissertation studied the schedulability problems of G-FP and G-EDF for different task modes.The proposed methods in the dissertation provides some theoretical foundations as well as practical insights for embedded real-time systems design.