Scheduling and analysis of parallel real-time tasks with semaphores

Xu Jiang, Nan Guan, Weichen Liu, Maolin Yang

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

7 Citations (Scopus)


This paper for the first time studies the scheduling and analysis of parallel real-time tasks with semaphores. In parallel task systems, each task may issue multiple requests to a semaphore, which raises new challenges to the design and analysis problems. We propose a new locking protocol LPP that limits the maximal number of requests to a semaphore by a task that can block other tasks at any time. We develop analysis techniques to safely bound the task response times, with which we prove that the best real-time performance is achieved if only one request to a semaphore by a task is allowed to block other tasks at a time. Experiments under different parameter settings are conducted to compare our proposed protocol and analysis techniques with the state-of-the-art spinlock protocol and analysis techniques for parallel real-time tasks.

Original languageEnglish
Title of host publicationProceedings of the 56th Annual Design Automation Conference 2019, DAC 2019
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9781450367257
Publication statusPublished - 2 Jun 2019
Event56th Annual Design Automation Conference, DAC 2019 - Las Vegas, United States
Duration: 2 Jun 20196 Jun 2019

Publication series

NameProceedings - Design Automation Conference
ISSN (Print)0738-100X


Conference56th Annual Design Automation Conference, DAC 2019
Country/TerritoryUnited States
CityLas Vegas

ASJC Scopus subject areas

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

Cite this