Real-Time Scheduling of Parallel Task Graphs with Critical Sections Across Different Vertices

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

1 Scopus Citations
View graph of relations


  • Xu Jiang
  • Maolin Yang
  • Yang Wang
  • Yue Tang
  • Wang Yi

Related Research Unit(s)


Original languageEnglish
Pages (from-to)4117-4133
Journal / PublicationIEEE Transactions on Parallel and Distributed Systems
Issue number12
Online published31 May 2022
Publication statusPublished - Dec 2022


All existing work on real-time scheduling of parallel task graph models with shared resources assumes that a critical section must be contained inside a single vertex. However, this assumption does not hold in many realistic parallel real-time software. In this work, we conduct the first study on real-time scheduling and analysis of parallel task graphs where critical sections are allowed to cross different vertices. We show that allowing this may potentially lead to deadlocks and the so-called resource unrelated blocking time problem. We formalize the conditions for the deadlocks and resource unrelated blocking time to happen, and propose two different solutions to address them and develop corresponding schedulability analysis techniques. We conduct comprehensive experiments to evaluate our method. The results indicate that there is a significant impact to the system schedulability when tasks incur deadlock and resource unrelated blocking. Moreover, the schedulability can benefit from the execution of workload in parallel with critical sections if tasks can be carefully designed so that all deadlocks and resource unrelated blocking time can be avoided, and our methods are efficient to determine the schedulability of systems where critical sections across different vertices exist.

Research Area(s)

  • Analytical models, Computational modeling, critical section, Heuristic algorithms, multi-core, parallel tasks, Protocols, real-time scheduling, Real-time systems, System recovery, Task analysis

Bibliographic Note

Full text of this publication does not contain sufficient affiliation information. With consent from the author(s) concerned, the Research Unit(s) information for this record is based on the existing academic department affiliation of the author(s).

Citation Format(s)