Abstract
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.
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.
| Original language | English |
|---|---|
| Qualification | Doctor of Philosophy |
| Awarding Institution |
|
| Supervisors/Advisors |
|
| Publication status | Published - Jul 1995 |
Keywords
- real-time
- scheduling
- fixed priority
- priority assignment
- spare capacity
- servers
- dual priority
- slack stealing
- value based scheduling
- utility