Approximative real-time analysis

Abstract

Embedded systems, like driving assistance systems in cars, require not only a correct functional calculation but also the correct real-time behavior. With schedulability analysis algorithms a proof is possible that the deadlines of the systems are reached under all circumstances. Several approaches for such an analysis have been developed in recent years. For the development of such systems a fast but accurate schedulability analysis is required. The existing approaches have either an exponential or a pseudo-polynomial complexity, requiring a high effort for unfavorable systems or are only sufficient. In this work an approximative schedulability analysis is proposed allowing a fast but accurate analysis. The inexactness of the approximation is bounded by the capacity of the processor and is independent of all other parameters of the system. It is the first fully polynomial-time approximation scheme of such a kind for the schedulability analysis of systems with EDF scheduling. The best exact analysis and the best sufficient analysis are only special cases of this approximation. Based on this approximation, algorithms with an adaptive inexactness are proposed leading to the fastest schedulability analysis for EDF scheduling. Additionally approximations and adaptive algorithms for fixed-priority scheduling are developed. In a second part of the work hierarchical event spectren, a new powerful model for events patterns and task stimulations, are presented. They extend the event stream model and allow a compact and efficient description of bursts and nested bursts. A combination of the hierarchical event spectren with the approximation leads to an accurate but compact description for the real-time calculus curves, an advanced schedulability analysis approach, and therefore allows fast real-time analysis with this approach even for complex event patterns.