On exploiting spare capacity in hard real-time systems

摘要

Complex real-time systems such as those envisaged for future autonomous vehicle control, robotics and advanced avionics applications, need to exhibit dynamic and adaptive behaviour in order to function in unpredictable environments.These systems need to be resilient to software / hardware failures and imbibed with the property of graceful degradation under overload.Cost, space and weight constraints also dictate that they must make the most effective use of limited processing communications resources.To realise such complex systems, two potentially conflicting objectives need to be met: first, safety critical and mission critical services must be guaranteed to provide results of a minimum acceptable quality and reliability by their deadlines.Second, the utility of the system, as determined by the frequency, timeliness, precision and confidence level of the results produced, must be maximised.The research comprising this thesis, focuses on the development of analysis and mechanisms which enable this second objective to be met.System utility can be enhanced by the timely execution of optional components which refine or improve upon the results of their mandatory counterparts.To achieve this, a three tier strategy is proposed.Initially, algorithms are developed which identify spare capacity at run-time, enabling optional components with soft deadlines to be scheduled responsively.Second, a family of acceptance tests are introduced, which facilitate the on-line guarantee of optional components with firm deadlines.An optimal priority assignment policy is derived for such components.Third, an efficient, adaptive admission policy is developed which arbitrates between competing optional components on the basis of their value-densities, enabling system utility to be maximised.The effectiveness of these techniques is examined in terms of their coverage, simplicity, performance and overheads, via simulation studies and via a proof of concept implementation within a hard real-time kernel.