Study On The Schedulability Analysis And Performance Optimization Of Graph-based Real-time Task Models

In recent years,embedded real-time systems have been widely applied into various industries such as aviation,aerospace,shipbuilding,aotomoiles,trains,industrial control,home appliances and the like.On the one hand,the degrees of the automation,electrification,digitization and intelligence of modern control systems continue to increase.On the other hand,there are higher and higher needs for the functions and performance of the system such as the safety,stability and comfort.To confront these changes,real-time systems have to provide more supporting power.Hence,this raises more and more stringent requirements for the time prediction and performance of real-time systems.In this thesis,we explore and research the schedulability analysis and performance optimization techniques of real-time tasks.The main contributions include the following four aspects:(1)Schedulability analysis of the digraph real-time task modelAs a strict extension of many kinds of task models,the digraph real-time task model provides more expressive ability for real-time applications in the real world and can be formally studied with respect to the problem of time constraint.However,the schedulability analysis of digraph real-time tasks with arbitrary deadlines has not been studied.And currently there exists no an efficient computing method of interference bound function.In order to further study and optimize the response time analysis of digraph real-time task model,this thesis presents a set of(exact and sufficient)response time analysis methods for digraph real-time tasks with arbitrary deadlines.Based on the theoretical results of max-plus algebra,we prove that the interference bound function is almost linear periodic,that is,it can be represented by a finite aperiodic part and a periodic part repeated infinitely often.This makes the asymptotic complexity of computing interference bound function independent from the length of the time interval.In addition,we also develop a linear upper bound on interference bound function,and study the effectiveness of the approach by demonstrating that it provides a tighter upper bound on the response time than existing approaches.The proposed calculation method of interference bound function based on the linear periodicity is more efficient than the state-of-the-art one,and its application can significantly reduce the runtime of the schedulability test.(2)Schedulability analysis of the synchronous finite state machine task modelThe synchronous reactive(SR)model is very widely used in the development of the embedded applications.Matlab/Simulink,including two types of blocks: Dataflow and Stateflow,can effectively support the analysis and simulation of the SR model.However,the current time analysis method only provides the sufficient condition for the stateflows where each one is implemented by one single task,while the more precise anlysis has not been studied.In this thesis,we study the schedulability analysis of the synchronous finite state machine task model(Simulink/Stateflow).Since the synchronous finite state machine is triggered according to the synchronization cycle time,the analysis in this thesis considers periodic tasks with synchronous offsets.First,it provides an exact response time analysis of finite state machine tasks,and at the same time proves that the exact analysis of finite state machine is coNP-hard in the strong sense.The core of the proof is to find a pseudo-polynomial time reduction from the exact schedulability analysis of the digraph real-time task model(a known strong coNP-hard problem)to the exact analysis of the synchronous finite state machines.this thesis also studies the approximate response time analysis based on the request or interference bound function,and their speedup factors relative to the exact response time.In order to further speed up the response time analysis,this thesis also presents an algorithmic solution for the exact computation of the request bound function leveraging its periodicity.The proposed analysis methods has better accuracy,smaller runtime and higher scalability compared with the related analysis work.(3)Schedulability analysis of the dynamic adaptive variable-rate task modelIn vehicles powered by the internal combustion engine,there are certain tasks are activated according to a rotation source,such as angular tasks in engine control unit triggered whenever the engine crankshaft reaches a specific angular position.In system design,to reduce the workload at high speeds,these tasks also adopt different implementations at different rotation speed intervals.However,the current studies limit to the case that the switching speeds at which task implementations should change are configured at design time.As a result,the off-line fixed approaches do not suit the dynamic cases.In this thesis,we propose to study the task model where switching speeds are dynamically adjusted.We develop schedulability analysis techniques for such systems,including a new digraph-based task model to safely approximate the workload from software tasks triggered at predefined rotation angles.The proposed task model and analysis method provide substantial benefits on system schedulability and are very effective in reducing the time complexity.(4)Performance optimization of the dynamic adaptive variable-rate task modelThe current practice is that the switching speeds at which the engine control system changes control strategy is fixed offline,typically based on the average driving need in a standard driving cycle.This is clearly suboptimal since the actual driving cycle may be considerably different from the standard one,and it fails to capture the variation in the driving cycle.In this thesis,we show that any valid speed partition has the bounded speedup factor,and thus the proposed analysis has the bounded pessimism,which provides the potential value for the optimization problems.And aiming to solve the performance optimization problem,we propose an optimization algorithm to dynamically adjust switching speeds,based on the predicted driving cycle from connected and automated vehicle techniques.This algorithm carefully leverages a hybrid set of schedulability analysis techniques with different accuracy and complexity to avoid the analysis difficulty.The proposed algorithm provides significant performance improvement over static approach and is very close to a performance upper bound with significantly less runtime.In summary,this thesis studies the schedulability analysis and performance optimization of real-time tasks,and focuses on three task models: digraph real-time tasks,synchronous finite state machine tasks and dynamic adaptive variable-rate tasks.This work puts forward a series of analysis and performance optimization methods,and make a positive contribution to the analysis of real-time task theory,has a certain theoretical significance and application value.