The shape of a DAG: bounding the response time using long paths

Qingqiang He, Nan Guan, Mingsong Lv, Xu Jiang, Wanli Chang

Research output: Journal article publicationJournal articleAcademic researchpeer-review

1 Citation (Scopus)

Abstract

In 1969, Graham developed a well-known response time bound for a DAG task using the total workload and the longest path of the DAG, which has been widely applied to solve many scheduling and analysis problems of DAG-based task systems. This paper presents a new response time bound for a DAG task using the total workload and the lengths of multiple long paths of the DAG, instead of the longest path in Graham’s bound. Our new bound theoretically dominates and empirically outperforms Graham’s bound. Based on the insight of the new bound, we propose a new task model called the multi-path model, which intuitively describes the shape of a DAG task. We further extend the proposed approach to multi-task systems using the new task model under both federated scheduling and global scheduling. Our schedulability test theoretically dominates federated scheduling and significantly outperforms the state-of-the-art.

Original languageEnglish
Pages (from-to)1-40
JournalReal-Time Systems
DOIs
Publication statusPublished - May 2023

Keywords

  • DAG task
  • Long paths
  • Real-time scheduling
  • Response time bound

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Modelling and Simulation
  • Computer Science Applications
  • Computer Networks and Communications
  • Control and Optimization
  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'The shape of a DAG: bounding the response time using long paths'. Together they form a unique fingerprint.

Cite this