中国科学院沈阳自动化研究所机构知识库
Advanced  
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(王义)
作者部门: 工业控制网络与系统研究室
关键词: Design ; Algorithms ; Performance ; Fork-join ; digraph-based task ; EDF-schedulability ; tractability
刊名: ACM TRANSACTIONS ON EMBEDDED COMPUTING SYSTEMS
ISSN号: 1539-9087
出版日期: 2016
卷号: 15, 期号:1, 页码:1-28
收录类别: SCI ; EI
产权排序: 2
项目资助者: Natural 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
摘要: 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.
语种: 英语
WOS记录号: WOS:000373654000014
Citation statistics:
内容类型: 期刊论文
URI标识: http://ir.sia.cn/handle/173321/18493
Appears in Collections:工业控制网络与系统研究室_期刊论文

Files in This Item: Download All
File Name/ File Size Content Type Version Access License
Feasibility of Fork-Join Real-Time Task Graph Models.pdf(968KB)期刊论文作者接受稿开放获取View Download

Recommended Citation:
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.
Service
Recommend this item
Sava as my favorate item
Show this item's statistics
Export Endnote File
Google Scholar
Similar articles in Google Scholar
[Sun JH(孙景昊)]'s Articles
[Guan N(关楠)]'s Articles
[Wang, Yang]'s Articles
CSDL cross search
Similar articles in CSDL Cross Search
[Sun JH(孙景昊)]‘s Articles
[Guan N(关楠)]‘s Articles
[Wang, Yang]‘s Articles
Related Copyright Policies
Null
Social Bookmarking
Add to CiteULike Add to Connotea Add to Del.icio.us Add to Digg Add to Reddit
文件名: Feasibility of Fork-Join Real-Time Task Graph Models.pdf
格式: Adobe PDF
所有评论 (0)
暂无评论
 
评注功能仅针对注册用户开放,请您登录
您对该条目有什么异议,请填写以下表单,管理员会尽快联系您。
内 容:
Email:  *
单位:
验证码:   刷新
您在IR的使用过程中有什么好的想法或者建议可以反馈给我们。
标 题:
 *
内 容:
Email:  *
验证码:   刷新

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

 

 

Valid XHTML 1.0!
Copyright © 2007-2016  中国科学院沈阳自动化研究所 - Feedback
Powered by CSpace