Resource sharing protocols for real-time task graph systems

Nan Guan, Pontus Ekberg, Martin Stigge, Wang Yi

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

14 Citations (Scopus)

Abstract

Previous works on real-time task graph models have ignored the crucial resource sharing problem. Due to the non-deterministic branching behavior, resource sharing in graph-based task models is significantly more difficult than in the simple periodic or sporadic task models. In this work we address this problem with several different scheduling strategies, and quantitatively evaluate their performance. We first show that a direct application of the well-known EDF+SRP strategy to graph-based task models leads to an unbounded speedup factor. By slightly modifying EDF+SRP, we obtain a new scheduling strategy, called EDF+saSRP, which has a speedup factor of 2. Then we propose a novel resource sharing protocol, called ACP, to better manage resource sharing in the presence of branching structures. The scheduling strategy EDF+ACP, which applies ACP to EDF, can achieve a speedup factor of √5+1/2 ≈ 1.618, the golden ratio.
Original languageEnglish
Title of host publicationProceedings of the 23rd Euromicro Conference on Real-Time Systems, ECRTS 2011
Pages272-281
Number of pages10
DOIs
Publication statusPublished - 26 Sep 2011
Externally publishedYes
Event23rd Euromicro Conference on Real-Time Systems, ECRTS 2011 - Porto, Portugal
Duration: 5 Jul 20118 Jul 2011

Conference

Conference23rd Euromicro Conference on Real-Time Systems, ECRTS 2011
Country/TerritoryPortugal
CityPorto
Period5/07/118/07/11

Keywords

  • real-time systems
  • resource sharing
  • speedup factor
  • task graph

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture

Cite this