"Response-Time Analysis of Conditional DAG Tasks in Multiprocessor Systems", 27th Euromicro Conference on Real-Time Systems (ECRTS 2015), July 7-10, 2015, Lund (Sweden).
Different task models have been proposed to represent the parallel structure of real-time tasks executing on manycore platforms: fork/join, synchronous parallel, DAG-based, etc. Despite different schedulability tests and resource augmentation bounds are available for these task systems, we experience difficulties in applying such results to real application scenarios, where the execution flow of parallel tasks is characterized by multiple (and nested) conditional structures. When a conditional branch drives the number and size of sub-jobs to spawn, it is hard to decide which execution path to select for modeling the worst-case scenario. To circumvent this problem, we integrate control flow information in the task model, considering conditional parallel tasks (cp-tasks) represented by DAGs composed of both precedence and conditional edges. For this task model, we identify meaningful parameters that characterize the schedulability of the system, and derive efficient algorithms to compute them. A response time analysis based on these parameters is then presented for different scheduling policies. A set of simulations shows that the proposed approach allows efficiently checking the schedulability of the addressed systems, and that it significantly tightens the schedulability analysis of non-conditional (e.g., Classic DAG) tasks over existing approaches.
"Timing Analysis of Fixed Priority Self-Suspending Sporadic Tasks", 27th Euromicro Conference on Real-Time Systems (ECRTS 2015), July 7-10, 2015, Lund (Sweden)
Many real-time systems include tasks that need to suspend their execution in order to externalize some of their operations or to wait for data, events or shared resources. Although commonly encountered in real-world systems, study of their timing analysis is still limited due to the problem complexity. In this paper, we invalidate a claim made in one of the earlier works , that led to the common belief that the timing analysis of one self-suspending task interacting with non-self suspending sporadic tasks is much easier than in the periodic case. This work highlights the complexity of the problem and presents a method to compute the exact worst-case response time (WCRT) of a self-suspending task with one suspension region. However, as the complexity of the analysis might rapidly grow with the number of tasks, we also define an optimization formulation to compute an upper-bound on the WCRT for tasks with multiple suspension regions. In the experiments, our optimization framework outperforms all previous analysis techniques and often finds the exact WCRT.