The response time analysis (RTA) is one of the fundamental tools used to guarantee the schedulability of sets of real-time tasks scheduled by Fixed Priorities. Also, several analysis methods inspired by RTA have been successfully developed to address more sophisticated execution platforms (distributed systems, multiprocessor) and application models (DAGs). The major issue with RTA is its time complexity, which is NP-hard. Such a complexity shows up when the task set has high utilization and RTA needs to check all jobs until the first idle instant. In this paper, we propose a continuous upper bound to the response time with quadratic time complexity in the number of tasks. Such an upper bound is demonstrated to be tighter than previously proposed ones with linear time complexity. In addition, with two tasks only, we prove that the proposed bound is the tightest continuous function upper bounding the exact response time of sets of tasks with full utilization. Whether or not this property holds with more than two tasks is still an open problem.

A Quadratic-Time Response Time Upper Bound with a Tightness Property

BINI, Enrico;
2015-01-01

Abstract

The response time analysis (RTA) is one of the fundamental tools used to guarantee the schedulability of sets of real-time tasks scheduled by Fixed Priorities. Also, several analysis methods inspired by RTA have been successfully developed to address more sophisticated execution platforms (distributed systems, multiprocessor) and application models (DAGs). The major issue with RTA is its time complexity, which is NP-hard. Such a complexity shows up when the task set has high utilization and RTA needs to check all jobs until the first idle instant. In this paper, we propose a continuous upper bound to the response time with quadratic time complexity in the number of tasks. Such an upper bound is demonstrated to be tighter than previously proposed ones with linear time complexity. In addition, with two tasks only, we prove that the proposed bound is the tightest continuous function upper bounding the exact response time of sets of tasks with full utilization. Whether or not this property holds with more than two tasks is still an open problem.
2015
36th IEEE Real-Time Systems Symposium, RTSS 2015
usa
2015
Proceedings - Real-Time Systems Symposium
Institute of Electrical and Electronics Engineers Inc.
13
22
9781467395076
9781467395076
Software; Hardware and Architecture; Computer Networks and Communications
Bini, Enrico; Parri, Andrea; Dossena, Giacomo
File in questo prodotto:
File Dimensione Formato  
Bini_2015-RTSS.pdf

Accesso riservato

Tipo di file: PDF EDITORIALE
Dimensione 302.97 kB
Formato Adobe PDF
302.97 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2318/1615482
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 13
  • ???jsp.display-item.citation.isi??? 5
social impact