logo SBA

ETD

Archivio digitale delle tesi discusse presso l’Università di Pisa

Tesi etd-04072004-201214


Tipo di tesi
Tesi di laurea vecchio ordinamento
Autore
Pellizzoni, Rodolfo
Indirizzo email
rodolfo@sssup.it
URN
etd-04072004-201214
Titolo
Efficient feasibility analysis of real-time asynchronous task sets
Dipartimento
INGEGNERIA
Corso di studi
INGEGNERIA INFORMATICA
Relatori
relatore Di Natale, Marco
relatore Ancilotti, Paolo
relatore Lipari, Giuseppe
Parole chiave
  • EDF
  • Schedulability
  • Transaction
  • DSP
  • Hard Real-Time
  • Offset
  • Multiprocessor
Data inizio appello
05/05/2004
Consultabilità
Completa
Riassunto
Several schedulability tests for real-time periodic task sets scheduled under the Earliest Deadline First algorithm have been proposed in literature, including analyses for precedence and resource constraints. However, all available tests consider synchronous task sets only, that are task sets in which all tasks are initially activated at the same time. In fact, every necessary and sufficient feasibility condition for asynchronous task sets, also known as task sets with offsets, is proven to be NP-complete in the number of tasks. We propose a new schedulability test for asynchronous task sets that, while being only sufficient, performs extremely better than available tests at the cost of a slight complexity increase. The test is further extended to task sets with resource constraints, and we discuss the importance of task offsets on the problems of feasibility and release jitter. We then show how our methodology can be extended in order to account for precedence constraints and multiprocessor and distributed computation applying holistic response time analysis to a real-time transaction-based model. This analysis is finally applied to asymmetric multiprocessor systems where it is able to achieve a dramatic performance increase over existing schedulability tests.
File