ETD system

Electronic theses and dissertations repository

 

Tesi etd-04072004-201214


Thesis type
Tesi di laurea vecchio ordinamento
Author
Pellizzoni, Rodolfo
email address
rodolfo@sssup.it
URN
etd-04072004-201214
Title
Efficient feasibility analysis of real-time asynchronous task sets
Struttura
INGEGNERIA
Corso di studi
INGEGNERIA INFORMATICA
Commissione
relatore Di Natale, Marco
relatore Ancilotti, Paolo
relatore Lipari, Giuseppe
Parole chiave
  • Hard Real-Time
  • DSP
  • Transaction
  • Multiprocessor
  • Offset
  • EDF
  • Schedulability
Data inizio appello
05/05/2004;
Consultabilità
completa
Riassunto analitico
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