Sökning: onr:"swepub:oai:DiVA.org:uu-296790" >
Feasibility of fork...
Feasibility of fork-join real-time task graph models : Hardness and algorithms
-
Sun, Jinghao (författare)
-
Guan, Nan (författare)
-
Wang, Yang (författare)
-
visa fler...
-
Deng, Qingxu (författare)
-
Zeng, Peng (författare)
-
- Yi, Wang (författare)
- Uppsala universitet,Datorteknik,Embedded Systems
-
visa färre...
-
(creator_code:org_t)
- 2016-02-20
- 2016
- Engelska.
-
Ingår i: ACM Transactions on Embedded Computing Systems. - : Association for Computing Machinery (ACM). - 1539-9087 .- 1558-3465. ; 15:1
- Relaterad länk:
-
https://urn.kb.se/re...
-
visa fler...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- 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.
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datorteknik (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Engineering (hsv//eng)
Publikations- och innehållstyp
- ref (ämneskategori)
- art (ämneskategori)
Hitta via bibliotek
Till lärosätets databas