SIA OpenIR  > 工业控制网络与系统研究室
Feasibility of Fork-Join Real-Time Task Graph Models: Hardness and Algorithms
Sun JH(孙景昊); Guan N(关楠); Wang, Yang; Deng QX(邓庆绪); Zeng P(曾鹏); Wang Y(王义)
Department工业控制网络与系统研究室
Source PublicationACM TRANSACTIONS ON EMBEDDED COMPUTING SYSTEMS
ISSN1539-9087
2016
Volume15Issue:1Pages:1-28
Indexed BySCI ; EI
EI Accession number20161902352739
WOS IDWOS:000373654000014
Contribution Rank2
Funding OrganizationNatural Science Foundation of China [61300194, 61300022, 61472072] ; National Basic Pre-research Program of China [2014CB360509] ; Opening Project of Key Laboratory of Networked Control Systems of Chinese Academy of Sciences
KeywordDesign Algorithms Performance Fork-join Digraph-based Task Edf-schedulability Tractability
AbstractIn 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.
Language英语
Citation statistics
Cited Times:5[WOS]   [WOS Record]     [Related Records in WOS]
Document Type期刊论文
Identifierhttp://ir.sia.cn/handle/173321/18493
Collection工业控制网络与系统研究室
Corresponding AuthorGuan N(关楠)
Affiliation1.School of Information Science and Engineering, Northeastern University, China
2.Laboratory of Networked Control Systems, Shenyang Institute of Automation, Chinese Academy of Sciences, China
3.Department of Information Technology, Uppsala University, Sweden
Recommended Citation
GB/T 7714
Sun JH,Guan N,Wang, Yang,et al. Feasibility of Fork-Join Real-Time Task Graph Models: Hardness and Algorithms[J]. ACM TRANSACTIONS ON EMBEDDED COMPUTING SYSTEMS,2016,15(1):1-28.
APA Sun JH,Guan N,Wang, Yang,Deng QX,Zeng P,&Wang Y.(2016).Feasibility of Fork-Join Real-Time Task Graph Models: Hardness and Algorithms.ACM TRANSACTIONS ON EMBEDDED COMPUTING SYSTEMS,15(1),1-28.
MLA Sun JH,et al."Feasibility of Fork-Join Real-Time Task Graph Models: Hardness and Algorithms".ACM TRANSACTIONS ON EMBEDDED COMPUTING SYSTEMS 15.1(2016):1-28.
Files in This Item: Download All
File Name/Size DocType Version Access License
Feasibility of Fork-(968KB)期刊论文作者接受稿开放获取ODC PDDLView Download
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Sun JH(孙景昊)]'s Articles
[Guan N(关楠)]'s Articles
[Wang, Yang]'s Articles
Baidu academic
Similar articles in Baidu academic
[Sun JH(孙景昊)]'s Articles
[Guan N(关楠)]'s Articles
[Wang, Yang]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Sun JH(孙景昊)]'s Articles
[Guan N(关楠)]'s Articles
[Wang, Yang]'s Articles
Terms of Use
No data!
Social Bookmark/Share
File name: Feasibility of Fork-Join Real-Time Task Graph Models.pdf
Format: Adobe PDF
All comments (0)
No comment.
 

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.