uu.seUppsala University Publications
Change search
ReferencesLink to record
Permanent link

Direct link
Feasibility of Fork-Join Real-Time Task Graph Models: Hardness and Algorithms
Northeastern Univ, Sch Informat Sci & Engn, Shenyang, Peoples R China..
Northeastern Univ, Sch Informat Sci & Engn, Shenyang, Peoples R China..
Northeastern Univ, Sch Informat Sci & Engn, Shenyang, Peoples R China..
Northeastern Univ, Sch Informat Sci & Engn, Shenyang, Peoples R China..
Show others and affiliations
2016 (English)In: ACM Transactions on Embedded Computing Systems, ISSN 1539-9087, E-ISSN 1558-3465, Vol. 15, no 1, 14Article in journal (Refereed) PublishedText
Abstract [en]

In the formal analysis of real-time systems, modeling of branching codes and modeling of intratask parallelism structures are two of the most important research topics. These two real-time properties are combined, resulting in the fork-join real-time task (FJRT) model, which extends the digraph-based task model with forking and joining semantics. We prove that the EDF schedulability problem on a preemptive uniprocessor for the FJRT model is coNP-hard in the strong sense, even if the utilization of the task system is bounded by a constant strictly less than 1. Then, we show that the problem becomes tractable with some slight structural restrictions on parallel sections, for which we propose an exact schedulability test with pseudo-polynomial time complexity. Our results thus establish a borderline between the tractable and intractable FJRT models.

Place, publisher, year, edition, pages
2016. Vol. 15, no 1, 14
Keyword [en]
Design, Algorithms, Performance, Fork-join, digraph-based task, EDF-schedulability, tractability
National Category
Computer Engineering
Identifiers
URN: urn:nbn:se:uu:diva-296790DOI: 10.1145/2809780ISI: 000373654000014OAI: oai:DiVA.org:uu-296790DiVA: diva2:939833
Available from: 2016-06-20 Created: 2016-06-20 Last updated: 2016-06-20Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Yi, Wang
By organisation
Computer Systems
In the same journal
ACM Transactions on Embedded Computing Systems
Computer Engineering

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 9 hits
ReferencesLink to record
Permanent link

Direct link