Análisis de planificabilidad basado en offsets en sistemas distribuidos de tiempo real con prioridades dinámicas

Abstract:

The thesis presented in this report is dedicated to schedulability analysis in real-time systems. This analysis is carried out through worst case response time techniques and the targets are event-driven multiprocessor and distributed systems.

The main purpose of this thesis is to enhance the use of dynamic priorities schedulers, in particular those using EDF(Earliest Deadline First) scheduling algorithm, for distributed systems. Although it has been demonstrated that EDF scheduling can reach higher levels of utilization than fixed-priority scheduling techniques in uniprocessor systems, studies and techniques for distributed or multiprocessor systems in EDF than in fixed-priority scheduling. In these systems exact analysis techniques are too expensive and, thus, the usual techniques are aproximate. Thus, the aim of this thesis is to improve analysis techniques for EDF scheduled systems decreasing the pesimism of the current techniques.

To achieve this aim, the first step is to validate previously used methods. Then, some improvements have been implemented to reduce the pesimism of the calculation. These improvements have been achieved by adapting to EDF methods developed for fixed priorities. In particular, the methods used are the offset-based model and the technique that exploits precedence relations between tasks of the same end-to-end flow. The study of the offsets between
releases of the different tasks and of the precedence relations between tasks of the same end-to-end flow allows reducing the pessimism of the analysis
and, consequently, to increasing the overall utilization of the system.

Finally, a modification in the end-to-end flow model has been introduced to represent atomic task sections. This modification allows us to expand the type of real-time applications representable by the task model. This new model allow us to represent threads that suspend themself on delay operations or blocking calls (usually remote procedure calls). The EDF analysis techniques have been extended to cover this new model.