Response Time Analysis of Sporadic DAG Tasks under Partitioned Scheduling
Ref: CISTER-TR-160502 Publication Date: 23 to 25, May, 2016
Response Time Analysis of Sporadic DAG Tasks under Partitioned Scheduling
Ref: CISTER-TR-160502 Publication Date: 23 to 25, May, 2016Abstract:
Several schedulability analyses have been proposed
for a variety of parallel task systems with real-time constraints.
However, these analyses are mostly restricted to global scheduling
policies. The problem with global scheduling is that it adds
uncertainty to the lower-level timing analysis which on multicore
systems are heavily context-dependent. As parallel tasks typically
exhibit intense communication and concurrency among their sequential computational units, this problem is further exacerbated.
This paper considers instead the schedulability of partitioned
parallel tasks. More precisely, we present a response time analysis
for sporadic DAG tasks atop multiprocessors under partitioned
fixed-priority scheduling. We assume the partitioning to be given.
We show that a partitioned DAG task can be modeled as a set of
self-suspending tasks. We then propose an algorithm to traverse a
DAG and characterize such worst-case scheduling scenario. With
minor modifications, any state-of-the-art technique for sporadic
self-suspending tasks can thus be used to derived the worstcase response time of a partitioned DAG task. Experiments show
that the proposed approach significantly tightens the worst-case
response time of partitioned parallel tasks comparatively to the
state-of-the-art when the most accurate technique is chosen.
José Fonseca
Geoffrey Nelissen
Vincent Nélis
Luis Miguel PinhoDocument:
View
Download11th IEEE International Symposium on Industrial Embedded Systems (SIES 2016).
Krakow, Poland.
Record Date: 2, May, 2016