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 used
to construct an equivalent FJRT model for the original CRT model. Finally, we present
the counterexample of the parallel task that can be expressed by the FJRT model but
cannot be expressed by the CRT model.
Definition 2.5 (Concurrent Real-Time Task System [Ejsing-Duun et al. 2013]). A
Concurrent Real-Time Task System ( CRT) S isatupleS = (τ, J, e, d), where
—J is a finite set of jobs,
—e: J → N is a mapping from jobs to worst-case execution times,
—d: J → N is a mapping from jobs to relative deadlines, and
—τ is a configuration defined by the following grammar.
—Configuration: τ ::= T | T τ
—Task: T ::= j | T
1
xT
2
| S
1
S
2
| T
1
+ T
2
| T
ω
—Subtask: S ::= j | S
1
xS
2
| S
1
S
2
| S
1
+ S
2
Here, j ∈ J is a job and x ∈ N, T
1
xT
2
is the sequential composition of tasks T
1
and
T
2
, with interrelease time x, T
1
+ T
2
is the choice between tasks T
1
and T
2
, S
1
S
2
is
the parallel composition of subtasks S
1
and S
2
,andT
ω
is one or more iterations of T .
In contrast to the definition of our FJRT model, the CRT model is inductively defined
by some regular grammar. The grammar of the configuration defines the task system,
which can be viewed as a composition of arbitrarily many independent tasks running in
parallel (intertask parallelism). Moreover, a nondeterministic choice between different
execution paths or subtasks running in parallel can be expressed by the grammar of
tasks and subtasks. Note that the subtasks defined in the CRT are restricted t o not
include any cycles. This article considers only acyclic parallel subtasks in the FJRT
model.
Example 2.6. Figure 3 represents the CRT task τ = ( j
1
30(( j
2
40 j
3
)( j
4
+ j
5
)))
ω
,
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
) =
2, d( j
4
) = 25; and e( j
5
) = 4, d( j
5
) = 25. As shown in Figure 3, the vertices in the
graph represent jobs, each labeled with an execution time and a deadline. The arcs in
the graph represent dependencies between jobs and are labeled with their minimum
interrelease time.
The combination of Theorem 2.7 and Example 2.8 proves that our digraph-based
FJRT model is more expressive than the CRT models.
T
HEOREM 2.7. The FJRT model is at least as expressive as the CRT model.
P
ROOF. We prove by induction that each grammar rule listed in Definition 2.5 can
be fully expressed by a substructure of the hypergraph. We do this by first introducing
the prefix and suffix operations for tasks, as follows.
ACM Transactions on Embedded Computing Systems, Vol. 15, No. 1, Article 14, Publication date: February 2016.
剩余27页未读，继续阅读
weixin_38724106
- 粉丝: 3
- 资源: 911
我的内容管理
展开
最新资源
- 新型矿用本安直流稳压电源设计：双重保护电路
- 煤矿掘进工作面安全因素研究：结构方程模型
- 利用同位素位移探测原子内部新型力
- 钻锚机钻臂动力学仿真分析与优化
- 钻孔成像技术在巷道松动圈检测与支护设计中的应用
- 极化与非极化ep碰撞中J/ψ的Sivers与cos2φ效应：理论分析与COMPASS验证
- 新疆矿区1200m深孔钻探关键技术与实践
- 建筑行业事故预防：综合动态事故致因理论的应用
- 北斗卫星监测系统在电网塔形实时监控中的应用
- 煤层气羽状水平井数值模拟：交替隐式算法的应用
- 开放字符串T对偶与双空间坐标变换
- 煤矿瓦斯抽采半径测定新方法——瓦斯储量法
- 大倾角大采高工作面设备稳定与安全控制关键技术
- 超标违规背景下的热波动影响分析
- 中国煤矿选煤设计进展与挑战：历史、现状与未来发展
- 反演技术与RBF神经网络在移动机器人控制中的应用
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
