Feasibility of Fork-Join Real-Time Task Graph Models: Hardness and Algorithms
文献类型：期刊论文
| 作者 | Sun JH(孙景昊); Guan N(关楠); Wang, Yang; Deng QX(邓庆绪); Zeng P(曾鹏) ; Wang Y(王义)
|
| 刊名 | ACM TRANSACTIONS ON EMBEDDED COMPUTING SYSTEMS
 |
| 出版日期 | 2016 |
| 卷号 | 15期号:1页码:1-28 |
| 关键词 | Design Algorithms Performance Fork-join digraph-based task EDF-schedulability tractability |
| ISSN号 | 1539-9087 |
| 产权排序 | 2 |
| 通讯作者 | 关楠 |
| 中文摘要 | 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. |
| 收录类别 | SCI ; EI |
| 语种 | 英语 |
| WOS记录号 | WOS:000373654000014 |
| 源URL | [http://ir.sia.cn/handle/173321/18493]  |
| 专题 | 沈阳自动化研究所_工业控制网络与系统研究室 |
| 推荐引用方式 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. |
入库方式： OAI收割
来源：沈阳自动化研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。