没有合适的资源?快使用搜索试试~ 我知道了~
首页Fork-Join实时任务图模型的NP-hardness与可调度算法研究
Fork-Join实时任务图模型的NP-hardness与可调度算法研究
0 下载量 41 浏览量
更新于2024-07-15
收藏 1MB PDF 举报
本文档深入探讨了Fork-Join(FJ)实时任务图模型在实际应用中的可行性,特别是在调度复杂性方面。首先,作者关注于实时系统分析中的两个关键主题:分支代码建模和任务内部并行结构建模。FJ模型结合了这两个特性,将传统的有向图任务模型扩展到支持并发的fork(分支)和join(合并)操作。 核心研究内容聚焦于FJ实时任务模型在预抢占单处理器环境下的可调度性问题。作者证明了一个重要的理论结果,即对于FJ模型的 earliest deadline first (EDF) 调度策略,即使任务系统的利用率被严格限制在一个常数小于1的范围内,该问题依然属于强NP-hard问题。这表明,在一般情况下,解决这个问题的困难程度极高,不容易找到有效的全局最优解。 然而,文章并未止步于负面结论,而是进一步探讨了通过施加特定的结构限制来提升问题的可处理性。作者提出,当任务中的并行部分受到某些约束时,调度问题变得可计算,即可以通过一种具有伪多项式时间复杂度的精确调度测试来解决。这意味着,尽管整体上问题很硬,但在某些特定条件下,我们能够找到相对高效的方法。 因此,这项研究为FJ实时任务图模型的可行性和算法设计提供了一条边界线,即在保持模型表达力的同时,如何通过适当的结构调整和优化策略来降低调度问题的复杂性。这对于理解和设计实时系统的调度算法具有重要的理论价值,也为工程实践中如何选择合适的模型和方法提供了指导。
资源详情
资源推荐
![](https://csdnimg.cn/release/download_crawler_static/15745107/bg6.jpg)
TECS1501-14 ACM-TRANSACTION January 2, 2016 10:1
14:6 J. Sun et al.
Fig. 3. An example CRT task τ .
Fig. 4. An example FJRT task that cannot be ex-
pressed by a CRT model.
model into a regular substructure of the hypergraph, which can subsequently be used205
to construct an equivalent FJRT model for the original CRT model. Finally, we present206
the counterexample of t he parallel task that can be expressed by the FJRT model but207
cannot be expressed by the CRT model.208
Definition 2.5 (Concurrent Real-Time Task System [Ejsing-Duun et al. 2013]). A209
Concurrent Real-Time Task System (CRT) S isatupleS = (τ, J, e, d), where210
—J is a finite set of jobs,211
—e: J → N is a mapping from jobs to worst-case execution times,212
—d: J → N is a mapping from jobs to relative deadlines, and213
—τ is a configuration defined by the following grammar.214
—Configuration: τ ::= T | T τ215
—Task: T ::= j | T
1
xT
2
| S
1
S
2
| T
1
+ T
2
| T
ω
216
—Subtask: S ::= j | S
1
xS
2
| S
1
S
2
| S
1
+ S
2
217
Here, j ∈ J is a job and x ∈ N, T
1
xT
2
is the sequential composition of tasks T
1
and218
T
2
, with interrelease time x, T
1
+ T
2
is the choice between tasks T
1
and T
2
, S
1
S
2
is219
the parallel composition of subtasks S
1
and S
2
,andT
ω
is one or more iterations of T .220
In contrast to the definition of our FJRT model, the CRT model is inductively defined221
by some regular grammar. The grammar of the configuration defines the task system,222
which can be viewed as a composition of arbitrarily many independent tasks running in223
parallel (intertask parallelism). Moreover, a nondeterministic choice between different224
execution paths or subtasks running in parallel can be expressed by the grammar of225
tasks and subtasks. Note that the subtasks defined in the CRT are restricted to not226
include any cycles. This article considers only acyclic parallel subtasks in the FJRT227
model.228
Example 2.6. Figure 3 represents the CRT task τ = ( j
1
30(( j
2
40 j
3
)( j
4
+ j
5
)))
ω
,229
where e( j
1
) = 1, d( j
1
) = 20; e( j
2
) = 4, d( j
2
) = 25; e( j
3
) = 6, d( j
3
) = 25; e( j
4
) =230
2, d( j
4
) = 25; and e( j
5
) = 4, d( j
5
) = 25. As shown in Figure 3, the vertices in the231
graph represent jobs, each labeled with an execution time and a deadline. The arcs in232
the graph represent dependencies between jobs and are labeled with their minimum233
interrelease time.234
The combination of Theorem 2.7 and Example 2.8 proves that our digraph-based235
FJRT model is more expressive than the CRT models.236
THEOREM 2.7. The FJRT model is at least as expressive as the CRT model.237
PROOF. We prove by induction that each grammar rule listed in Definition 2.5 can238
be fully expressed by a substructure of the hypergraph. We do this by first introducing239
the prefix and suffix operations for tasks, as follows.240
ACM Transactions on Embedded Computing Systems, Vol. 15, No. 1, Article 14, Publication date: December 2015.
剩余28页未读,继续阅读
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/default.jpg!1)
weixin_38747126
- 粉丝: 5
- 资源: 921
上传资源 快速赚钱
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
最新资源
- AirKiss技术详解:无线传递信息与智能家居连接
- Hibernate主键生成策略详解
- 操作系统实验:位示图法管理磁盘空闲空间
- JSON详解:数据交换的主流格式
- Win7安装Ubuntu双系统详细指南
- FPGA内部结构与工作原理探索
- 信用评分模型解析:WOE、IV与ROC
- 使用LVS+Keepalived构建高可用负载均衡集群
- 微信小程序驱动餐饮与服装业创新转型:便捷管理与低成本优势
- 机器学习入门指南:从基础到进阶
- 解决Win7 IIS配置错误500.22与0x80070032
- SQL-DFS:优化HDFS小文件存储的解决方案
- Hadoop、Hbase、Spark环境部署与主机配置详解
- Kisso:加密会话Cookie实现的单点登录SSO
- OpenCV读取与拼接多幅图像教程
- QT实战:轻松生成与解析JSON数据
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)