Schedulability Analysis Of Real-Time Systems With Synchronization

Real-time systems have strict requirements for satisfying time requirements.In such systems,the processor is not only supposed to complete tasks,but also in required time interval.The increasing application of real-time systems stimulates the design and analysis of them.One of the most popular models is digraph real-time task model(DRT task model for short).DRT task model is highly expressive and efficient for analysis,making it the basic model in our work.Worst case response time is a critical standard when analyzing the schedulability of a real-time system modeled by DRT task model.If every vertex in the task model has worst case response time no larger than its relative deadline,the whole system proves to be schedulable.At the same time,real-time calculus(RTC)is a powerful framework to model real-time workload.It uses variability characteristic curves to analyze system performance parameters.However,the semantics of DRT task model are still limited.It can only model independent systems,but not dependent ones.If we use DRT to model dependent systems,the analysis result could be imprecise.To solve the problem,we add signals to DRT to model synchronization among tasks.Accordingly,the refinement based analysis technique is modified to compute the worst case response time of a vertex.Our method returns the same analysis results as Timestool,proving its correctness.On the other hand,we combine path abstraction technique(PAT)with real-time calculus(RTC)to compute the delay bound of each individual vertex.In the process,we obtain the request bound function of a DRT task,compute the delay bound of each vertex,and input the remaining service curve as service curve of the next task.However,directly combining these two models causes over-approximate results.We propose two algorithms to modify the combination and get precise results with pseudo-polynomial time complexity.Experiments prove the precision and efficiency of these two algorithms.