Real-Time Applications with Stochastic Task Execution Times: Analysis and Optimisation

Embedded systems have become indispensable in our lives: household appliances, cars, airplanes, power plant control systems, medical equipment, telecommunication systems, space technology, they all contain digital computing systems with dedicated functionality. Most of them, if not all, are real-time systems, i.e. their responses to stimuli have timeliness constraints.

The timeliness requirement has to be met despite some unpredictable, stochastic behaviour of the system. In this book, we address one cause of such stochastic behaviour, namely the application and platform-dependent stochastic task execution times.

The problem of accurately determining the deadline miss ratio of an application and to optimise the performance of a system taking the aforementioned ratio into consideration is extremely important as it has a significant impact on the cost of the end product.

Real-Time Applications with Stochastic Task Execution Times presents three approaches to the analysis of the deadline miss ratio of applications with stochastic task execution times. Each of the three approaches fits best to a different context. The first approach is an exact one and is efficiently applicable to monoprocessor systems. The second approach is an approximate one, which allows for designer-controlled trade-off between analysis accuracy and analysis speed. It is efficiently applicable to multiprocessor systems. The third approach is less accurate but sufficiently fast in order to be placed inside optimisation loops. Based on the last approach, we propose a heuristic for task mapping and priority assignment for deadline miss ratio minimisation.