logo SBA

ETD

Digital archive of theses discussed at the University of Pisa

 

Thesis etd-04072004-201214


Thesis type
Tesi di laurea vecchio ordinamento
Author
Pellizzoni, Rodolfo
email address
rodolfo@sssup.it
URN
etd-04072004-201214
Thesis title
Efficient feasibility analysis of real-time asynchronous task sets
Department
INGEGNERIA
Course of study
INGEGNERIA INFORMATICA
Supervisors
relatore Di Natale, Marco
relatore Ancilotti, Paolo
relatore Lipari, Giuseppe
Keywords
  • EDF
  • Schedulability
  • Transaction
  • DSP
  • Hard Real-Time
  • Offset
  • Multiprocessor
Graduation session start date
05/05/2004
Availability
Full
Summary
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